Weighted round robin
Encyclopedia
Weighted round robin
(WRR) is a scheduling discipline. Each packet flow
or connection has its own packet queue in a network interface card. It is the simplest approximation of generalized processor sharing (GPS)
. While GPS serves infinitesimal amounts of data from each nonempty queue, WRR serves a number of packets for each nonempty queue:
.
// calculate number of packets to be served each round by connections
min = find smallest weight
for each flow f
f.packets_to_be_served = f.weight / min
// main loop
loop
for each non-empty flow queue f
min(f.packets_to_be_served, f.packets_waiting).times do
servePacket f.getPacket
Deficit round robin (DRR)
is a variation of WRR that achieves better GPS approximation without knowing the mean packet size of each connection in advance. There are more effective scheduling disciplines which handle both of these problems mentioned above (e.g. weighted fair queuing (WFQ)
).
Round-robin scheduling
Round-robin is one of the simplest scheduling algorithms for processes in an operating system. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority . Round-robin scheduling is simple, easy to...
(WRR) is a scheduling discipline. Each packet flow
Flow (computer networking)
In packet switching networks, traffic flow, packet flow or network flow is a sequence of packets from a source computer to a destination, which may be another host, a multicast group, or a broadcast domain...
or connection has its own packet queue in a network interface card. It is the simplest approximation of generalized processor sharing (GPS)
Generalized Processor Sharing
Generalized processor sharing was developed as a service discipline to share the capacity of congested communications links in an efficient, flexible and fair manner...
. While GPS serves infinitesimal amounts of data from each nonempty queue, WRR serves a number of packets for each nonempty queue:
.Algorithm
WRR mechanism (pseudo-code):// calculate number of packets to be served each round by connections
min = find smallest weight
for each flow f
f.packets_to_be_served = f.weight / min
// main loop
loop
for each non-empty flow queue f
min(f.packets_to_be_served, f.packets_waiting).times do
servePacket f.getPacket
Weaknesses
To obtain a normalized set of weights, required to approximate GPS, a mean packet size must be known. In IP networks with their variable packet size the mean has to be estimated which makes good GPS approximation hard to achieve in practice. Another weakness of WRR is that it cannot guarantee fair link sharing.Deficit round robin (DRR)
Deficit round robin
Deficit round robin , also deficit weighted round robin , is a modified weighted round robin scheduling discipline. DRR was proposed by M. Shreedhar and G. Varghese in 1995. It can handle packets of variable size without knowing their mean size...
is a variation of WRR that achieves better GPS approximation without knowing the mean packet size of each connection in advance. There are more effective scheduling disciplines which handle both of these problems mentioned above (e.g. weighted fair queuing (WFQ)
Weighted fair queuing
Weighted fair queuing is a data packet scheduling technique allowing different scheduling priorities to statistically multiplexed data flows.WFQ is a generalization of fair queuing . Both in WFQ and FQ, each data flow has a separate FIFO queue...
).
See also
- scheduling discipline
- A simple explanation of weight round-robin distribution