Weighted round robin

Weighted round robin (WRR) is a network scheduler for data flows, but also used to schedule processes.

Weighted round robin 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). Several variations of WRR exist. The main ones are the classical WRR, and the interleaved WRR.

Algorithm

Principles

WRR is presented in the following as a network scheduler. It can also be used to schedule tasks in a similar way.

A weighted round-robin network scheduler has <math>n</math> input queues, <math>q_1,...,q_n</math>. To each queue <math>q_i</math> is associated <math>w_i</math>, a positive integer, called the weight. The WRR scheduler has a cyclic behavior. In each cycle, each queue <math>q_i</math> has <math>w_i</math> emissions opportunities.

The different WRR algorithms differ in the distribution of these opportunities in the cycle.

Classical WRR

In classical WRR the scheduler cycles over the queues. When a queue <math>q_i</math> is selected, the scheduler will send packets, up to the emission of the <math>w_i</math> packet or the end of the queue.

|-valign="top"

| colspan="2" |

Constant and variables:

const N // Nb of queues

const weight[1..N] // weight of each queue

queues[1..N] // queues

i // queue index

c // packet counter

Instructions:

while true do

for i in 1 .. N do

c := 0

while (not queue[i].empty) and (c<weight[i]) do

send(queue[i].head())

queue[i].dequeue()

c:= c+1

Interleaved WRR

Let <math>w_{max}=\max\{ w_i \}</math>, be the maximum weight. In IWRR, each cycle is split into <math>w_{max}</math> rounds. A queue with weight <math>w_i</math> can emit one packet at round <math>r</math> only if <math>r \leq w_i</math>.

|-valign="top"

| colspan="2" |

Constant and variables:

const N // Nb of queues

const weight[1..N] // weight of each queue

const w_max

queues[1..N] // queues

i // queue index

r // round counter

Instructions:

while true do

for r in 1 .. w_max do

for i in 1 .. N do

if (not queue[i].empty) and (weight[i] >= r) then

send(queue[i].head())

queue[i].dequeue()

Example

thumb|500px|Example of scheduling for CWRR and IWRR

Consider a system with three queues <math>q_1,q_2,q_3</math> and respective weights <math>w_1=5,w_2=2,w_3=3</math>. Consider a situation where there are 7 packets in the first queue, A,B,C,D,E,F,G, 3 in the second queue, U,V,W and 2 in the third queue X,Y. Assume that there are no more packet arrivals.

With classical WRR, in the first cycle, the scheduler first selects <math>q_1</math> and transmits the five packets at head of queue,A,B,C,D,E (since <math>w_1=5</math>), then it selects the second queue, <math>q_2</math>, and transmits the two packets at head of queue, U,V (since <math>w_2=2</math>), 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 <math>q_1</math> are transmitted, followed by W from <math>q_2</math>.

With interleaved WRR, the first cycle is split into 5 rounds (since <math>max(w_1,w_2,w_3)=5</math>). In the first one (r=1), one packet from each queue is sent (A,U,X), in the second round (r=2), another packet from each queue is also sent (B,V,Y), in the third round (r=3), only queues <math>q_1,q_3</math> are allowed to send a packet (<math>w_1 >= r</math>, <math>w_2 < r</math> and <math>w_3 >= r</math>), but since <math>q_3</math> is empty, only C from <math>q_1</math> is sent, and in the fourth and fifth rounds, only D,E from <math>q_1</math> are sent. Then starts the second cycle, where F,W,G are sent.

Task scheduling

Task or process scheduling can be done in WRR in a way similar to packet scheduling: when considering a set of <math>n</math> active tasks, they are scheduled in a cyclic way, each task <math>\tau_i</math> gets <math>w_i</math> quantum or slice of processor time

Properties

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: a queue <math>q_i</math> will receive a long-term part of the bandwidth equal to <math>\frac{w_i}{\sum_{j=1}^n w_j}</math> (if all queues are active) while GPS serves infinitesimal amounts of data from each nonempty queue and offers 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 on the packet sizes.

If a mean packets size <math>s_i</math> is known for every queue <math>q_i</math>, each queue will receive a long-term part of the bandwidth equal to <math>\frac{s_i \times w_i}{\sum_{j=1}^n s_j \times w_j}</math>. If the objective is to give to each queue <math>q_i</math> a portion <math>\rho_i</math> of link capacity (with <math>\sum_{i=1}^n \rho_i=1</math>), one may set <math>w_i = \frac{\rho_i}{s_i}</math>.

Since IWRR has smaller per-class bursts than WRR, it implies smaller worst-case delays.

Limitations and improvements

WRR for network packet scheduling was first proposed by Katevenis, Sidiropoulos and Courcoubetis in 1991,