Weighted round robin
Weighted round robin (WRR) is a network scheduler for data flows, but also used to schedule processes.
Weighted round robin[1] is a generalisation of round-robin scheduling.
It serves a set of queues or tasks.
Whereas round-robin cycles over the queues or tasks and gives one service opportunity per cycle, weighted round robin offers to each a fixed number of opportunities, as specified by the configured weight which serves to influence the portion of capacity received by each queue or task.
In computer networks, a service opportunity is the emission of one packet, if the selected queue is non-empty.
If all packets have the same size, WRR is the simplest approximation of generalized processor sharing (GPS).
A weighted round-robin network scheduler has
, a positive integer, called the weight.
The WRR scheduler has a cyclic behavior.
In classical WRR[2][3][4] the scheduler cycles over the queues.
is selected, the scheduler will send packets, up to the emission of
With classical WRR, in the first cycle, the scheduler first selects
and transmits the five packets at head of queue,A,B,C,D,E (since
, and transmits the two packets at head of queue, U,V (since
), and last it selects the third queue, which has a weight equals to 3 but only two packets, so it transmits X,Y.
Immediately after the end of transmission of Y, the second cycle starts, and F,G from
With interleaved WRR, the first cycle is split into 5 rounds (since
quantum or slice of processor time .
[6][7] Like round-robin, weighted round robin scheduling is simple, easy to implement, work conserving and starvation-free.
When scheduling packets, if all packets have the same size, then WRR and IWRR are an approximation of Generalized processor sharing:[8] a queue
will receive a long term part of the bandwidth equals to
(if all queues are active) while GPS serves infinitesimal amounts of data from each nonempty queue and offer this part on any interval.
If the queues have packets of variable length, the part of the bandwidth received by each queue depends not only on the weights but also of the packets sizes.
, each queue will receive a long term part of the bandwidth equals to
[9] WRR for network packet scheduling was first proposed by Katevenis, Sidiropoulos and Courcoubetis in 1991,[1] specifically for scheduling in ATM networks using fixed-size packets (cells).
The primary limitation of weighted round-robin queuing is that it provides the correct percentage of bandwidth to each service class only if all the packets in all the queues are the same size or when the mean packet size is known in advance.
In the more general case of IP networks with variable size packets, to approximate GPS the weight factors must be adjusted based on the packet size.
That requires estimation of the average packet size, which makes a good GPS approximation hard to achieve in practice with WRR.
[1] Deficit round robin is a later variation of WRR that achieves better GPS approximation without knowing the mean packet size of each connection in advance.
More effective scheduling disciplines were also introduced which handle the limitations mentioned above (e.g. weighted fair queuing).
