Weighted round robin (WRR) is a network scheduling discipline. Each packet flow or connection has its own packet queue in a network interface controller. 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:
Contents
Algorithm
WRR mechanism (pseudo-code):
// calculate number of packets to be served each round by connections for each flow f f.normalized_weight = f.weight / f.mean_packet_size min = findSmallestNormalizedWeight for each flow f f.packets_to_be_served = f.normalized_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.getPacketLimitations 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). In the more general case of IP networks with variable size packets, in order 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 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).