Big-O of Round Robin (RR) and Weighted (WRR)

Question

As I am implementing a simple load balancing service, I think Big-O is a key factor for it's future performance and scalability. But I could find no reference regarding the big-O of both algorithms (WRR & RR).

I made a try to calculate both of them.
(WARING my calculations might be wrong but I'll edit the post as soon as I get a rightful answer)

n-> number of serving nodes (and weights)
z-> number of waiting/incompleted tasks
For WRR: O(nnz)
For RR: O(z^2)

For WRR: O(1)
For RR: O(1)

So the real question is, if my calculations are right but most important which algorithm perform the fastest in a case of continuous load balanced (to each running node) thousand submitted tasks per second.

Some helpful references:

• A Very nice RR implementation
• A stackoverflow question regarding WRR

Cheers!

Answer 1

So what is it exactly you need to measure? As big O is for algorithm performance, it seems the reasonable thing to measure is the time complexity for each sheduling decision, i.e. how many operations are required to match one task to one node.

Round robin

Both the list of ready nodes and the list of waiting tasks can be implemented as queues, and operations on queues can be implemented constant amortized time. So except for the time required when you need to allocate new memory for your queue, you operate in O(1).

Weighted round robin

If your weights are fixed and commensurable, then you can achieve the same complexity here as well: simply place each node into the cyclic queue several times, proportional to its weight. One can formulate an algorithm to space them evenly within the queue. For most practical applications, some moderate quantization will lead to weights which can be represented as (i.e. scaled to) reasonably small integers.

Other considerations

Do you get any feedback at all about whether your nodes are busy or idle? If you do, then RR should work well enough, since you didn't state any fairness requirements. If you don't have idle feedback, then WRR might make sense. But in that case, the number z in your formulas appears somewhat confusing, since how can tasks be waiting if you don't know whether nodes are ready to accept them? If they are waiting because the balancer can't handle them fast enough, then this still shouldn't matter for your considerations, as you can imagine the queue of tasks as before the scheduling algo: the length of that queue has no impact on what happens in the scheduler. Again assuming all tasks are the same to you, without priorities, QoS guarantees or similar meta information.