Weighted round robin (WRR) is a
network scheduler
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
for data flows, but also used to
schedule processes.
Weighted round robin
is a generalisation of
round-robin scheduling
Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing. Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, , 2016.
As the term ...
. 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 Generalized processor sharing (GPS) is an ideal scheduling algorithm for process schedulers and network schedulers. It is related to the fair-queuing principle which groups packets into classes and shares the service capacity between them. GPS sh ...
(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
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
. It can also be used to schedule tasks in a similar way.
A weighted round-robin network scheduler has
input queues,
. To each queue
is associated
, a positive integer, called the ''weight''. The WRR scheduler has a cyclic behavior. In each cycle, each queue
has
emissions opportunities.
The different WRR algorithms differ on the distributions of these opportunities in the cycle.
Classical WRR
In classical WRR
[
]
the scheduler cycles over the queues. When a queue
is selected, the scheduler will send packets, up to the emission of
packet or the end of queue.
Interleaved WRR
Let
, be the maximum weight. In IWRR,
each cycle is split into
rounds. A queue with weight
can emit one packet at round
only if
.
Example
![WRR-Examples](https://upload.wikimedia.org/wikipedia/commons/2/25/WRR-Examples.svg)
Consider a system with three queues
and respective weights
. Consider a situation where they 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 is no more packet arrival.
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
), then it selects the second queue,
, 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
are transmitted, followed by W from
.
With interleaved WRR, the first cycle is split into 5 rounds (since
). 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
are allowed to send a packet (
,
and
), but since
is empty, only C from
is sent, and in the fourth and fifth rounds, only D,E from
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
active tasks, they are scheduled in a cyclic way, each task
gets
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 Generalized processor sharing (GPS) is an ideal scheduling algorithm for process schedulers and network schedulers. It is related to the fair-queuing principle which groups packets into classes and shares the service capacity between them. GPS sh ...
:
[
] 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.
If a mean packets size
is known for every queue
, each queue will receive a long term part of the bandwidth equals to
. If the objective is to give to each queue
a portion
of link capacity (with
), one may set
.
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,
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 network
The Internet protocol suite, commonly known as TCP/IP, is a framework for organizing the set of communication protocols used in the Internet and similar computer networks according to functional criteria. The foundational protocols in the suit ...
s 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.
Deficit round robin
Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) poli ...
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
Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in ...
).
See also
*
Fair queuing
*
Fairness measure Fairness measures or metrics are used in network engineering to determine whether users or applications are receiving a fair share of system resources. There are several mathematical and conceptual definitions of fairness.
TCP fairness
Congestion ...
*
Processor sharing
Processor sharing or egalitarian processor sharing is a service policy where the customers, clients or jobs are all served simultaneously, each receiving an equal fraction of the service capacity available. In such a system all jobs start service ...
*
Statistical time-division multiplexing
References
{{Reflist
Network scheduling algorithms