Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Fair queuing
open-in-new
<h2 id="history">History</h2> <p>The term <i>fair queuing</i> was coined by John Nagle in 1985 while proposing <a href="/facts/Round-robin_scheduling/7wpjbMRI">round-robin scheduling</a> in the gateway between a <a href="/facts/Local_area_network/edUDxJ6J">local area network</a> and the <a href="/facts/Internet/Xw1rVvJU">internet</a> to reduce network disruption from badly-behaving hosts.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>A byte-weighted version was proposed by Alan Demers, <a href="/facts/Srinivasan_Keshav/yPFnXV39">Srinivasan Keshav</a> and <a href="/facts/Scott_Shenker/cS6GjpRJ">Scott Shenker</a> in 1989, and was based on the earlier Nagle fair queuing algorithm.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> The byte-weighted fair queuing algorithm aims to mimic a bit-per-bit multiplexing by computing theoretical departure date for each packet. </p><p>The concept has been further developed into <a href="/facts/Weighted_fair_queuing/DU2FCx3p">weighted fair queuing</a>, and the more general concept of <a href="/facts/Traffic_shaping/VCF0Gb3b">traffic shaping</a>, where queuing priorities are dynamically controlled to achieve desired flow <a href="/facts/Quality_of_service/joz9VkUm">quality of service</a> goals or accelerate some flows. </p> <h2 id="principle">Principle</h2> <p>Fair queuing uses one queue per <a href="/facts/Packet_flow/Yp8UP6ys">packet flow</a> and services them in rotation, such that each flow can "obtain an equal fraction of the resources".<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>The advantage over conventional <a href="/facts/FIFO_(computing_and_electronics)/RctvBNgE">first in first out</a> (FIFO) or <a href="/facts/Priority_queuing/1uXVo4Uf">priority queuing</a> is that a high-data-rate flow, consisting of large packets or many data packets, cannot take more than its fair share of the link capacity. </p><p>Fair queuing is used in routers, switches, and <a href="/facts/Statistical_multiplexer/rLGcaGHV">statistical multiplexers</a> that forward packets from a <a href="/facts/Buffer_(computer_science)/tVy4j2Dc">buffer</a>. The buffer works as a queuing system, where the data packets are stored temporarily until they are transmitted. </p><p>With a link data-rate of <i>R</i>, at any given time the <i>N</i> active data flows (the ones with non-empty queues) are serviced each with an average data rate of <i>R/N</i>. In a short time interval the data rate may fluctuate around this value since the packets are delivered sequentially in turn. </p> <h3>Fairness</h3> <p>In the context of network scheduling, <i>fairness</i> has multiple definitions. Nagel's article uses <a href="/facts/Round-robin_scheduling/7wpjbMRI">round-robin scheduling</a> of packets,<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> which is fair in terms of the number of packets, but not on the bandwidth use when packets have varying size. Several formal notions of <a href="/facts/Fairness_measure/CFDslIwh">fairness measure</a> have been defined including <a href="/facts/Max-min_fairness/vbpvTzIN">max-min fairness</a>, <i>worst-case fairness</i>,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> and <i>fairness index</i>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h3>Generalisation to weighted sharing</h3> <p>The initial idea gives to each flow the same rate. A natural extension consists in letting the user specify the portion of bandwidth allocated to each flow leading to <a href="/facts/Weighted_fair_queuing/DU2FCx3p">weighted fair queuing</a> and <a href="/facts/Generalized_processor_sharing/1rIcHVkN">generalized processor sharing</a>. </p> <h2 id="a-byte-weighted-fair-queuing-algorithm">A byte-weighted fair queuing algorithm</h2> <p>This algorithm attempts to emulate the fairness of bitwise round-robin sharing of link resources among competing flows. Packet-based flows, however, must be transmitted packetwise and in sequence. The byte-weighted fair queuing algorithm selects transmission order for the packets by modeling the finish time for each packet as if they could be transmitted bitwise round robin. The packet with the earliest finish time according to this modeling is the next selected for transmission. </p><p>The complexity of the algorithm is <i>O(log(n))</i>, where <i>n</i> is the number of queues/flows. </p> <h3>Algorithm details</h3> <p>Modeling of actual finish time, while feasible, is computationally intensive. The model needs to be substantially recomputed every time a packet is selected for transmission and every time a new packet arrives into any queue. </p><p>To reduce computational load, the concept of <i>virtual time</i> is introduced. Finish time for each packet is computed on this alternate monotonically increasing virtual timescale. While virtual time does not accurately model the time packets complete their transmissions, it does accurately model the order in which the transmissions must occur to meet the objectives of the full-featured model. Using virtual time, it is unnecessary to recompute the finish time for previously queued packets. Although the finish time, in absolute terms, for existing packets is potentially affected by new arrivals, finish time on the virtual time line is unchanged - the virtual time line warps with respect to real time to accommodate any new transmission. </p><p>The virtual finish time for a newly queued packet is given by the sum of the virtual start time plus the packet's size. The virtual start time is the maximum between the previous virtual finish time of the same queue and the current instant. </p><p>With a virtual finishing time of all candidate packets (i.e., the packets at the head of all non-empty flow queues) computed, fair queuing compares the virtual finishing time and selects the minimum one. The packet with the minimum virtual finishing time is transmitted. </p> <h3>Pseudocode</h3> <table><tbody><tr><td colspan="2">Shared variables const N // Nb of queues queues[1..N] // queues lastVirFinish[1..N] // last virtual finish instant</td></tr><tr><td>receive(packet) queueNum := chooseQueue(packet) queues[queueNum].enqueue(packet) updateTime(packet, queueNum)</td><td>updateTime(packet, queueNum) // virStart is the virtual start of service virStart := max(now(), lastVirFinish[queueNum]) packet.virFinish := packet.size + virStart lastVirFinish[queueNum] := packet.virFinish</td></tr><tr><td>send() queueNum := selectQueue() packet := queues[queueNum].dequeue() return packet</td><td>selectQueue() it := 1 minVirFinish = ∞ {\displaystyle \infty } while it ≤ N do queue := queues[it] if not queue.empty and queue.head.virFinish < minVirFinish then minVirFinish = queue.head.virFinish queueNum := it it := it + 1 return queueNum</td></tr></tbody></table> <p>The function receive() is executed each time a packet is received, and send() is executed each time a packet to send must be selected, <i>i.e.</i> when the link is idle and the queues are not empty. This pseudo-code assumes there is a function now() that returns the current virtual time, and a function chooseQueue() that selects the queue where the packet is enqueued. </p><p>The function selectQueue() selects the queue with the minimal virtual finish time. For the sake of readability, the pseudo-code presented here does a linear search. But maintaining a sorted list can be implemented in logarithmic time, leading to a <i>O(log(n))</i> complexity, but with more complex code. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Active_queue_management/dPk4QqtM">Active queue management</a></li> <li><a href="/facts/Bufferbloat/mbtScFvU">Bufferbloat</a></li> <li><a href="/facts/Deficit_round_robin/exc9lWIz">Deficit round robin</a></li> <li><a href="/facts/Fairness_measure/CFDslIwh">Fairness measure</a></li> <li><a href="/facts/Generalized_processor_sharing/1rIcHVkN">Generalized processor sharing</a></li> <li><a href="/facts/Max-min_fairness/vbpvTzIN">Max-min fairness</a></li> <li><a href="/facts/Network_scheduler/7URA71LE">Network scheduler</a></li> <li><a href="/facts/Statistical_multiplexing/rLGcaGHV">Statistical multiplexing</a></li> <li><a href="/facts/Weighted_fair_queuing/DU2FCx3p">Weighted fair queuing</a></li> <li><a href="/facts/Weighted_round_robin/kS83Qt57">Weighted round robin</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>John Nagle: "On packet switches with infinite storage," RFC 970, IETF, December 1985. <a href="http://tools.ietf.org/html/rfc970" target="_blank">http://tools.ietf.org/html/rfc970</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Nagle, J. B. (1987). "On Packet Switches with Infinite Storage". IEEE Transactions on Communications. 35 (4): 435–438. CiteSeerX 10.1.1.649.5380. doi:10.1109/TCOM.1987.1096782. <a href="/wiki/IEEE_Transactions_on_Communications" target="_blank">/wiki/IEEE_Transactions_on_Communications</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Phillip Gross (January 1986), Proceedings of the 16-17 January 1986 DARPA Gateway Algorithms and Data Structures Task Force (PDF), IETF, pp. 5, 98, retrieved 2015-03-04, Nagle presented his "fair queuing" scheme, in which gateways maintain separate queues for each sending host. In this way, hosts with pathological implementations can not usurp more than their fair share of the gateway's resources. This invoked spirited and interested discussion. <a href="https://www.ietf.org/proceedings/01.pdf" target="_blank">https://www.ietf.org/proceedings/01.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1–12. doi:10.1145/75247.75248. <a href="https://doi.org/10.1145%2F75247.75248" target="_blank">https://doi.org/10.1145%2F75247.75248</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "Analysis and Simulation of a Fair Queueing Algorithm" (PDF). Internetworking: Research and Experience. 1: 3–26. <a href="http://people.csail.mit.edu/imcgraw/links/research/pubs/networks/WFQ.pdf" target="_blank">http://people.csail.mit.edu/imcgraw/links/research/pubs/networks/WFQ.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>John Nagle: "On packet switches with infinite storage," RFC 970, IETF, December 1985. <a href="http://tools.ietf.org/html/rfc970" target="_blank">http://tools.ietf.org/html/rfc970</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Nagle, J. B. (1987). "On Packet Switches with Infinite Storage". IEEE Transactions on Communications. 35 (4): 435–438. CiteSeerX 10.1.1.649.5380. doi:10.1109/TCOM.1987.1096782. <a href="/wiki/IEEE_Transactions_on_Communications" target="_blank">/wiki/IEEE_Transactions_on_Communications</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Nagle, J. B. (1987). "On Packet Switches with Infinite Storage". IEEE Transactions on Communications. 35 (4): 435–438. CiteSeerX 10.1.1.649.5380. doi:10.1109/TCOM.1987.1096782. <a href="/wiki/IEEE_Transactions_on_Communications" target="_blank">/wiki/IEEE_Transactions_on_Communications</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4. S2CID 17558577. <a href="978-0-8186-7293-4" target="_blank">978-0-8186-7293-4</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Ito, Y.; Tasaka, S.; Ishibashi, Y. (2002). "Variably weighted round robin queueing for core IP routers". Conference Proceedings of the IEEE International Performance, Computing, and Communications Conference (Cat. No.02CH37326). p. 159. doi:10.1109/IPCCC.2002.995147. ISBN 978-0-7803-7371-6. S2CID 60787008. <a href="978-0-7803-7371-6" target="_blank">978-0-7803-7371-6</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>