Editing Weighted round robin

{{Short description|Scheduling algorithm for tasks or data flows}}
{{Use mdy dates|date=May 2022}}

'''Weighted round robin''' ('''WRR''') is a [[network scheduler]] for data flows, but also used to [[Scheduling (computing)|schedule processes]].

Weighted round robin<ref name="WRR-ATM-1991">{{cite journal|last1=Katevenis|first1=M.|last2=Sidgiropoulos|first2=S.|last3=Courcoubetis|first3=C.|title=Weighted round-robin cell multiplexing in a general-purpose ATM switch chip|journal=IEEE Journal on Selected Areas in Communications|volume=9|issue=8|year=1991|pages=1265–1279|issn=0733-8716|doi=10.1109/49.105173}}</ref> 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.<ref name="WRR-2003">{{cite journal|last1=Chaskar|first1=H.M.|last2=Madhow|first2=U.|title=Fair scheduling with tunable latency: A round-robin approach|journal=IEEE/ACM Transactions on Networking|volume=11|issue=4|year=2003|pages=592–601|issn=1063-6692|doi=10.1109/TNET.2003.815290|s2cid=8010108 }}</ref> 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 on the distributions of these opportunities in the cycle.

=== Classical WRR ===

In classical WRR<ref name="WRR-2003" /><ref name="CPN-WRR-ETFA06">{{cite book|last1=Brahimi|first1=B.|last2=Aubrun|first2=C.|last3=Rondeau|first3=E.|title=2006 IEEE Conference on Emerging Technologies and Factory Automation |chapter=Modelling and Simulation of Scheduling Policies Implemented in Ethernet Switch by Using Coloured Petri Nets|year=2006|pages=667–674|doi=10.1109/ETFA.2006.355373|isbn=0-7803-9758-4 |s2cid=6089006 }}</ref><ref name="RFC-7806">
{{cite tech report
|author1= F. Baker
|author2= R.Pan
|title=On Queuing, Marking, and Dropping
|section= 2.2.2. Round-Robin Models
|number=RFC 7806
|institution=IETF
|date= May 2016}} 
</ref>
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 <math>w_i</math> packet or the end of 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,<ref name="WRR-ATM-1991"/><ref name="Juniper-Queuing">{{cite report
 | last= Semeria
 | first=Chuck
 | year= 2001
 | title       = Supporting Differentiated Service Classes: Queue Scheduling Disciplines
 | url         = http://users.jyu.fi/~timoh/kurssit/verkot/scheduling.pdf
 | pages       = 15–18
 | access-date = May 4, 2020
}}</ref> 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 ===

[[File:WRR-Examples.svg|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 is no more packet arrival.

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
.<ref name="Beaulieu-Course">{{cite web
|url=http://beaulieu.segfaults.net/courses/17w/EEE499/lecture/07%20-%20Scheduling%20and%20Schedulers.pdf
|title=Real Time Operating Systems – Scheduling & Schedulers
|last=Beaulieu
|first=Alain
|date=Winter 2017
|access-date=May 4, 2020
}}{{Dead link|date=March 2023 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref name="WRR-Pattent">
{{cite patent
| country	= United States
| number	= 20190266019
| title		= Task Scheduling Using Improved Weighted Round Robin Techniques 
| pubdate	= August 29, 2019 
| fdate		= May 15, 2019
| inventor	= Philip D. Hirsch
| url		= http://www.freepatentsonline.com/y2019/0266019.html
}}
</ref>

==Properties==

Like [[Round-robin scheduling|round-robin]], weighted round robin scheduling is simple, easy to implement, [[Work-conserving scheduler|work conserving]] and [[Starvation (computer science)|starvation-free]].

When scheduling packets, if all packets have the same size, then WRR and IWRR are an approximation of [[Generalized processor sharing]]:<ref name="kfall-lecture">{{cite web
 |url=http://kfall.net/ucbpage/EE122/lec27/sld006.htm
 |title=EECS 122, "Introduction to Communication Networks", Lecture 27, "Scheduling Best-Effort and Guaranteed Connections"
 |last=Fall
 |first=Kevin
 |date=April 29, 1999
|access-date=May 4, 2020
}}
</ref> a queue <math>q_i</math> will receive a long term part of the bandwidth equals 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 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 <math>s_i</math> is known for every queue <math>q_i</math>, each queue will receive a long term part of the bandwidth equals 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.<ref>{{cite conference
 | first1 = Seyed Mohammadhossein 
 | last1 = Tabatabaee
 | first2 = Jean-Yves
 | last2 = Le Boudec
 | first3= Marc
 | last3= Boyer
 | title =  Interleaved Weighted Round-Robin: A Network Calculus Analysis 
 | book-title = Proc. of the 32nd Int. Teletraffic Congress (ITC 32)
 | date = September 22–24, 2020
 | doi = 10.1109/ITC3249928.2020.00016
 | arxiv = 2003.08372
 }}
</ref>

== Limitations and improvements ==
WRR for network packet scheduling was first proposed by Katevenis, Sidiropoulos and Courcoubetis in 1991,<ref name="WRR-ATM-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]]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.<ref name="WRR-ATM-1991" />

[[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]]).

==See also==

* [[Fair queuing]]
* [[Fairness measure]]
* [[Processor sharing]]
* [[Statistical time-division multiplexing]]

==References==
{{Reflist}}

[[Category:Network scheduling algorithms]]