Talk:Fair queuing

Name change fiasco

The name of this page needs to be changed to Fair Queuing to reflect the correct spelling, but I can't figure out how to change a page name. —The preceding unsigned comment was added by 192.76.82.90 (talk • contribs) 22:54, 14 August 2006 (UTC).

It's done with a move tab the top of the page. Perhaps you need to create an account and log in to have that ability. I'll do the renaming, and drop the capital Q also. Thanks for catching what everyone else has missed! JonHarder 12:55, 15 August 2006 (UTC)

It turns out there is already an article with that name, which means an administrator will have to perform the operation. I'll make the request. JonHarder 13:02, 15 August 2006 (UTC)

Problem is partly solved. The name is now Fair Queuing, which is the most common spelling on the internet. It harmonizes with the "Weighted Fair Queuing" article. Unfortunatley I did not succeed in removing the capitalization. (I moved the redirecting page "Fair queing" to a temporary address, and then the "Fair queuing" article to "Fair Queuing". I was not allowed to move to "Fair queuing". Finally the redirecting page was moved to "Fair queueing", and a new redirecting page "Fair queuing" was created.) Mange01 21:54, 15 October 2006 (UTC)

The following discussion is an archived debate of the proposal. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the debate was move; fair queueing should suffice. -- tariqabjotu 02:27, 21 August 2006 (UTC)

Requested move

Fair Queueing → Fair queuing – Correct spelling and capitalization. JonHarder 13:11, 15 August 2006 (UTC)

Survey

Add "* Support" or "* Oppose" followed by an optional one-sentence explanation, then sign your opinion with ~~~~

• Support JonHarder 13:12, 15 August 2006 (UTC)
• Rename to Fair queueing with redirect from Fair queuing, as "queu[e]ing" may be spelt either way. David Kernow 10:24, 16 August 2006 (UTC)

Discussion

Add any additional comments

The above discussion is preserved as an archive of the debate. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

A. Demers, S. Keshav, and S. Shenker didn't invent fair queuing.

I generally try not to blow my own horn on Wikipedia, but Demers, Keshav, and Shenker didn't invent fair queuing in 1989. I invented it in 1985. [1][2]. It's one of the classic Internet RFCs, and there's a published paper. I coined the term fair queueing, which first appears in that paper. That paper also introduced congestion collapse and first applied the tragedy of the commons problem to networking. But since it's my own work, I shouldn't edit the article. I'd appreciate it if someone else would do so. Thanks. --John Nagle 22:01, 15 October 2006 (UTC)

Done. It is a pleasure to meet you. Personally, I would not restrain myself from using WikiPedia for publishing terms that I have coined. Mange01 22:22, 15 October 2006 (UTC)

Algorithm

The algorithm description is difficult to understand and may even be wrong. Can someone try to clean this up by defining some variables, adding some equations or pseudo code. Help! --Kvng (talk) 23:44, 5 June 2008 (UTC)

I think the description in the article is confusing, and I invented fair queueing. The original idea was to have one queue for each source IP address, and service them in rotation. That's easy to understand, but doesn't take into account packet length, or allow for weighting some sources or classes of traffic more than others. So there are fancier schemes. Here's a badly written lecture on the subject, [3], and here's a better one.[4]. If the "virtual finishing time" concept is introduced, the explanation here should be at least as good as the one in the second reference, which has some good drawings. I'd suggest explaining the basic approach clearly, and referring readers to references for the more detailed explanation of "virtual finishing time", which is specialist detail for implementors. --John Nagle (talk) 02:28, 6 June 2008 (UTC)

Thank you. The second reference helped a lot. Virtual time is a round number in a a hypothetical bit-by-bit round robin implementation. Virtual times need not be updated when new packets arrive in to the queue(s). Clever. I'll see if I can find time a bit later to improve the algorithm description in the article. --Kvng (talk) 15:18, 6 June 2008 (UTC)

Right. "Virtual time" is a way to implement weighted bit-by-bit round robin. I think the name is confusing, but it was used in some early papers. (There was a tendency in some academic computer science circles in the 1980s to use the terms "virtual" and "abstract" wherever possible.)

Did you see the hydraulic analogy in the second reference? Weighted fair queuing works like a series of tubes going into a junction, with conservation of liquid flow, more flow from the bigger tubes, and the rule that you can't switch inputs in the middle of a packet. Cute. --John Nagle (talk) 16:42, 6 June 2008 (UTC)

The hydraulics analogy was a good start but didn't get me all the way there. Hydraulics don't map directly to network behavior (e.g. increased pressure increases flow in hydraulics but not in networks). --Kvng (talk) 19:13, 7 June 2008 (UTC)

Algorithm section has been reworked. Let me know if I munged anything. I probably should add some citations of the references John Nagle provided above.--Kvng (talk) 05:19, 3 August 2008 (UTC)

The algorithm described as fair queuing is not the one provided by John Nagle in reference [5]. This reference defines the algorithm as follows:

  "   We introduce the concept of fairness.  We would like to make our
  packet switches fair; in other words, each source host should be able
  to obtain an equal fraction of the resources of each packet switch.
  We can do this by replacing the single first in, first out queue
  associated with each outgoing link with multiple queues, one for each
  source host in the entire network. We service these queues in a
  round- robin fashion, taking one packet from each non-empty queue in
  turn and transmitting the packets with positive time to live values
  on the associated outgoing link, while dropping the expired packets.
  Empty queues are skipped over and lose their turn.
  
     This mechanism is fair; outgoing link bandwidth is parcelled out
  equally amongst source hosts.  Each source host with packets queued
  in the switch for the specified outgoing link gets exactly one packet
  sent on the outgoing link each time the round robin algorithm cycles.
  So we have implemented a form of load-balancing."

Also, the algorithm described as fair queuing (above) does not have the properties described in the article and its introduction. Specifically, fair queuing as described by Nagle *does not* take into account packet sizes. This can lead to unfair bandwidth allocation of a bandwidth ratio up to max/min, where max and min are maximum and minimum packet sizes supported by the network.

Nagle first used the term fair queuing, but did not actually proposed a fair packet scheduling algorithm. A. Demers, S. Keshav, and S. Shenker, in "Analysis and simulation of a fair queueing algorithm," present "a fair queuing algorithm" explicitly inspired by Nagle's algorithm, but explain that under their criteria of fairness (max-min fairness) Nagle's algorithm is not fair. Thus, though the term is coined and the concept inspired by Nagle, the original fair queuing algorithm is weighted, requiring amounts of a resource requested by "users," as needed by the definition of max-min fairness. Their algorithm represents weighted fair queuing, where the resource is policed according to preassigned weights to "users," instead of user requests of resource amounts.

Stamatis Kavvadias

Family of Algorithms

It is not quite correct to say that Fair Queueing is "a scheduling algorithm". A family of scheduling algorithms would be more precise. A modification by A. Demers, S. Keshav and S. Shenker of Nagle's initial proposal was the first Fair Queueing algorithm to be extensively studied and proven in practice. This is where the confusion as to the origin comes from. Since most modern usage of the term "Fair Queueing" refers to the later variant a reference to this paper might be aproppriate:

Demers, A., Keshav, S., and Shenker, S. 1989. Analysis and simulation of a fair queueing algorithm. In Symposium Proceedings on Communications Architectures & Protocols (Austin, Texas, United States, September 25 - 27, 1989). SIGCOMM '89. ACM, New York, NY, 1-12. DOI= http://doi.acm.org/10.1145/75246.75248 —Preceding unsigned comment added by 129.97.169.179 (talk) 17:20, 30 November 2009 (UTC)

Can you address this issue in the article? Feel free to change.

Actually Nagle himself (in a message above) asked us to change the name of the originator of the algorithm to his name.Mange01 (talk) 16:01, 17 September 2014 (UTC)

In fact, the term "Fair Queueing' has two meanings

1. A principle, a family of scheduling algorithms, the idea to share the bandwidth based on a round-robin way, by Nagle, 1985
2. The packet-based implementation of the ideal bit-by-bit round robin by Demers, Keshav, and Shenker, 1989

I understand the wish of J. Nagle to establish the truth, but now, one can not ignore the overloading of the expression.

I suggest to explain it in the first paragraph. MarcBoyerONERA (talk) 21:03, 10 March 2015 (UTC).

Before proceeding further with edits reflecting your point of view that there are two meanings, please produce a citation or two so that other editors and readers can verify this. ~Kvng (talk) 19:26, 15 April 2015 (UTC)

The "two meanings" concept is new to me. The abstract to Demers' paper says "A fair queuing algorithm, based on an earlier suggestion by Nagle, is proposed", so Demers didn't see two meanings. The key concept is recognizing traffic flows and queuing by flow, not FIFO, across all packets. Early routers were pure FIFO, and many routers still are. Fair queuing was the first approach to datagram switches which considered flows. Once you start recognizing flows, a large number of options open up. There are lots of variations on this theme, such as weighted fair queuing. This leads to the more general concept of traffic shaping, where you start manipulating queuing by flow to achieve quality of service goals or preferentially accelerate some flows (see net neutrality.) If you use dumb FIFO and have lots of memory at a choke point (more bandwidth in than out), you get bufferbloat problems. So "See Also" should include traffic shaping and bufferbloat, and they should link back here. That set of articles should show how all those concepts are connected. (Personal note: many home routers still lack fair queuing in the uplink direction, which is why, when doing a large upload on a link with limited upload bandwidth, download operations stall even when download bandwidth is available. The ACKs are stuck behind the uplink data. It's sad to see this three decades later.) John Nagle (talk) 05:02, 16 April 2015 (UTC)

Thank you once again for your contributions to Wikipedia. To comment on this page is a wize approach. I tried to implement some of your comments. Please tell me if I have introduced some errors.

Would it be correct to say that non-waited fair queuing is not implemented in today's routers and switches, while WFQ is available in today's most advanced network nodes, and typically activated in mobile GPRS nodes but seldom in the wired infrastructure by the ISP:s?

(Off topic: I once wrote this and this paper and I am considering to resume that work. I would like to relate my algorithms to traditional fair queueing/scheduling disciplines but I have not found a good source for such categorization.) Mange01 (talk) 17:38, 16 April 2015 (UTC)

As background, bear in mind that the Internet was the successor to the ARPAnet. The ARPAnet was packet switched, but it had guaranteed delivery (no packet dropping), true flow control (hosts couldn't send unless there were buffers available), and a rigid structure (all nodes were centrally administered from BBN HQ in Boston.) In the ARPAnet, packet loss was not a problem, but buffer shortages were. A big problem with the ARPAnet was limited memory in the IMPs. The Internet was intended to allow interconnection of diverse networks without central administration. No guaranteed delivery, and no flow control at the packet level. So packets would sometimes be dropped. Excessive packet drop in the Internet was originally thought to be a problem which more and cheaper memory would solve. That's why my RFC 970 was entitled "On Packet Switches with Infinite Storage". That paper argues that more memory would not solve the problem, and it was going to be necessary to get serious about re-ordering packets in some useful way. I'd also written RFC 896, which described how a network could get into a stable state of congestion collapse where everybody was frantically retransmitting and almost nothing was getting through. In those days, we weren't trying to squeeze out a little more performance; we were trying to avoid situations where almost nothing got through the network at all. There were failures where the Internet effectively stopped working at some nodes but no component was broken. The early Internet had major problems scaling up. It wasn't clear at the time that a big, diverse, pure datagram network could ever work reliably. (Some telephony people argued early on that it would never work.[6]) Papers of the early 1980s were addressing issues at that level. John Nagle (talk) 21:05, 16 April 2015 (UTC)

I just added mentioning of RR, FQ, WFQ, WRR, DRR and GPS in the fairness page. Any suggestions on how to improve those articles? I am not sure on which of these schemes that are only for data packet scheduling and which are only for operational system process scheduling.

Of course It is very interesting to read contributions by a person who actually were there when it all happened. When I teach, I normally compare today's TCP/IP with the principles of x.25, Frame relay, ATM, MPLS, GPRS, etc, but apparantly ARPAnet is also worth mentioning.

The things you mention should be discussed somewhere at Wikipedia, but I am not sure on what Wikipedia articles that are the best place for mentioning what you write. ARPAnet? Mange01 (talk) 17:27, 19 April 2015 (UTC)

Network scheduler seems to be Wikipedia's overview topic on this subject. That could use some work; some links there are to the raw source code of algorithms, with no explanation. There are lots of approaches, but the general idea is to keep the sender that's sending the most from hogging the channel. Any form of fairness beats FIFO for that case. John Nagle (talk) 21:19, 19 April 2015 (UTC)

I am not a native english speaker, so I may not use the exact words to speak about this overloading of terms. But the words "Fair queuing" are commonly used to speak about the Demers' algorithm. I can give several examples:

1. the paper "How Fair Is Fair Queuing?" only mention the Demers' algorithm
2. in the paper "Efficient fair queuing using deficit round-robin", the authors wrote "we will use capitalized Fair Queuing (FQ) to refer to the implementation and the uncapitalized "fair queuing" to refer to the generic idea.
3. in "Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks", the paper from Nagle is even not cited, only the Demers' one is.

I guess that at least one paper out of two makes the confusion. One can be sorry about that, but in my opinion, the Wikipedia page must mention both interpretations, and clearly warn the reader about this semantics overloading, at the start of the article. MarcBoyerONERA (talk) 09:03, 20 April 2015 (UTC)

Here's a slide set on the history of fair queuing from Simon Frazier University.[7]. That's part of a presentation on a gigabit Ethernet switch. There's a good overview of the tradeoffs between different approaches to fair queuing. In the wireless world, here's another overview.[8] That one lists 9 variations on fair queuing and has a comparison table. The approaches that are the fairest have higher compute or hardware requirements, which is why there are so many variations on this basic theme. John Nagle (talk) 19:24, 20 April 2015 (UTC)

I know that fair sharing of bandwidth is a huge area of network scheduling, and that there is no magic solution but always some tradeoff between fairness, latency and implementation costs/complexity. My claim is on another point: there are commonly two semantics for the words "fair queuing". The user @Kvng: asked me some references to illustrate this meaning confusion. Some use it as it was originally defined, a "principle", and others as the name of the Demers' algorithm. In my opinion, as already said, the Wikipedia page must must mention both interpretations, and clearly warn the reader about this semantics overloading, at the start of the article. MarcBoyerONERA (talk) 05:02, 21 April 2015 (UTC)

Does anyone else see the "two meanings" as described above? For a modern, but not citeable, discussion of the subject, see "New Fair Queuing option in Linux 3.12+" [9] on Reddit, which goes over the history and practice in that area. Not a WP:RS reliable source itself, but has references to other documents which are. Basic conclusion there: fair queuing, in any form, is much better than FIFO, and the new Linux implementation is quite good. John Nagle (talk) 06:19, 21 April 2015 (UTC)

@Kvng:, @Mange01: John Nagle and myself disagree on some semantics points (see above). Could you help us? Do we have to contact the Wikipedia:WikiProject Computing/Computer networking task force? And how to manage this talk page? I am quite new in Wikipedia, and this end-less discussion in unreadable... — Preceding unsigned comment added by MarcBoyerONERA (talk • contribs)

@MarcBoyerONERA: thank you for the citations. #2 may be useful as it explicitly states that there are two meanings for fair queuing (but I fear this distinction is being made for the purposes of readability within the paper only). You're making inferences with the other two and this is original research which many new editors are surprised to learn is discouraged on Wikipedia. John Nagle provides primary sources which are also not held in high esteem.

I'm not sure how to resolve this yet. My feeling is that recent edits by MarcBoyerONERA have not been improving the article. If we all manage to agree that there's "fair queueing" (concept) and a separate "Fair Queueing" (algorithm first proposed by John Nagle and improved upon by others) then this article should become a disambiguation page. If, on the other hand, we decide to revert some recent changes and move back in the direction we came, I think we can cover the concept of queueing with fairness in Network scheduler and Generalized processor sharing and dedicate this article to coverage of Nagel's idea at the improvements to it. ~Kvng (talk) 14:38, 21 April 2015 (UTC)

@Kvng: As far as I understand Wikipedia citation policy, the reference #3 is secondary source, making a global overview of the domain (in 1995). I just had a look on a few papers published the last 5 years mentioning "fair queuing" (thanks to Google scholar), and one out of two uses the term "fair queuing" to mention the algorithm of Demers. This confusion is a pity, but it exists. Even on wikipedia (in the Deficit round robin page, it is written that the FQ scheduler has complexity O(log(n), making a confusion between the family and the Demers' algorithm). One source of confusion is that Weighted fair queuing is an algorithm, not a family of algorithms :-(. Another is that the Demers' algorithm have no official name. Whatever, what about a single sentence in the introduction like "It is a common mistake to make a confusion between the family of algorithms and its Demers' implementation."?

More globally, after work done on FQ and WFQ, I was working on GPS (see my User:MarcBoyerONERA/sandbox). Perhaps a global approach is needed. Where to discuss it? — Preceding unsigned comment added by MarcBoyerONERA (talk • contribs)

It is actually encouraging to see confusion in the field mirrored on Wikipedia. It is not our job as editors to straighten inherently crooked things. The best we can do in an environment like this is describe the confusion. We probably need to think about reverting some of your changes while we sort through this. If you want to start a broader discussion, I suggest that can be done at one of the following (in order of increasing broadness) Talk:Network scheduler, Wikipedia talk:WikiProject Computing/Computer networking task force or Wikipedia talk:WikiProject Computing. ~Kvng (talk) 16:15, 21 April 2015 (UTC)

Network scheduler probably should be the top article of a tree. It's a short article now. If I were writing it (which I won't, as a COI issue), I'd start out by describing FIFO queuing, the dumbest network scheduling algorithm. Then discuss its limitations, describing what happens when a heavy sender and a light sender are both trying to use the same link. (That's what all this is really about - keeping heavy senders from hogging links.) Mention that a network scheduler works in cooperation with (or, in bad cases, against) the transport level TCP congestion-avoidance algorithm and its counterparts for other transport protocols. Point out that there are two things a network scheduler can do - reorder packets, and drop them. Show both lines of development, with RFC 970 at the beginning of the "reorder" approach, and Random Early Drop at the beginning of the "drop" approach. Drawings would be helpful. Briefly cover and link to traffic shaping, bufferbloat, and net neutrality. Mark all the related articles with "Main article: Network scheduler". This would be helpful to people coming to the subject who need to learn about it. John Nagle (talk) 20:34, 21 April 2015 (UTC)

There are also related articles Leaky bucket and Token Bucket. These are variations on the "drop" approach. John Nagle (talk) 22:53, 21 April 2015 (UTC)

Dave TahtTo further confuse matters, we call the DRR++-like fair-queuing algorithm used in fq_codel as "flow queuing" as (usually) as we treat flows that build a queue (e.g. bulk flows) differently from those that don't. https://tools.ietf.org/id/draft-ietf-aqm-fq-codel-00.txt

We are further improving the fairness by adopting an 8 way set associative hash in fq_codel´s successor, cake: http://www.bufferbloat.net/projects/codel/wiki/Cake

I (and others) are confused about how to think about or describe "htb", when talking about packet scheduling, and hfsc blends together multiple things also.

lastly, in https://tools.ietf.org/html/draft-ietf-aqm-recommendation-11

we say that " In short, scheduling algorithms and queue management should be seen as complementary, not as replacements for each other."

There are schools that think AQM can solve everything, others that think FQ can solve everything, and the school jim gettys and I belong to says that fq + aqm + ecn are the trifecta (in rough order of importance) that will speed up and make more reliable the whole internet, by a lot.

Getting the ietf to pay attention to FQ is something many despaired of (since the very first ietf meeting!! see page 88: https://www.ietf.org/proceedings/01.pdf ) and that is why we spent so much time discussing aqm here, before moving onto fq:

I had no idea that document still existed. Thanks. John Nagle (talk) 18:56, 22 April 2015 (UTC)

https://gettys.wordpress.com/2013/07/10/low-latency-requires-smart-queuing-traditional-aqm-is-not-enough/ — Preceding unsigned comment added by Dtaht (talk • contribs) 18:40, 22 April 2015 (UTC)

"A byte-weighted fair queuing algorithm"

That approach and code need to be cited.

In practice, few implementations work that way. Many, such as "fq-codel", hash the flow information and put the packet on some limited number of queues.[10]. Also, the uncited code snippet given is full of bugs. SelectQueue() returns "it", which will always be N. The intent was probably to return QueueNum. But that, too, would be wrong, because there's an off-by-one error in that loop. The queues are numbered 1..N, but the loop only tests queues 1 through N-1. Also, QueueNum is undefined if all queues are empty. Is this WP:OR, or did that code come from some published source? John Nagle (talk) 00:38, 29 April 2015 (UTC)

@Nagle: Thanks for the bug detection. It should be fixed, and some precisions listed.

1. The pseudo-code is a translation of the Demers' description in natural langage (referenced in the introduction, it is usefull to re-cite it?), not of a specific implementation.
2. The way packets are set into queues in delegated to the choseQueue() function. But more globaly, I do not know how to name the "selection of queue" process. In the introduction of the article, it is written "a packet queue (or job queue) for each traffic flow", and in the traffic flow page, several definitions are given, but if my memory is good (but its is years ago), in CISCO routers with QoS, they are a lot of parameters than can be used by network admin to set some packet in a queue or another.
3. The corrected selectQueue() function returns queueNum and goes up to N (I have done too many C code, going from 0 to N-1...)
4. And queueNum() must be called by the send() function, that itself must be called only if some queue is not empty.

The goal was to gives the general idea without going into too many details. Some details on some specific implementations can be added (but I won't, since I do not know much about it).

MarcBoyerONERA (talk) 08:39, 29 April 2015 (UTC)

I see an anon just changed the pseudo-code. If that code is WP:OR, it probably should be removed. Wikipedia isn't set up to debug code. This isn't Github. Try drawing pictures instead. Thanks. John Nagle (talk) 06:08, 5 May 2015 (UTC)

Finding something that is not WP:OR seems difficult, since this algorithm has been generalised into Weighted fair queueing, and as far as I known, the implementation effort was done on WFQ. Nevertheless, I guess that it is more readable to present first the byte-weighted fair queuing algorithm pseudo-code, and the one of WFQ as a small modification of this one. MarcBoyerONERA (talk) 08:42, 11 May 2015 (UTC)

Complexity

It says that the complexity is log(n), however, the pseudo code seems to have complexity n (Presumably because it is a naive version of the algorithm). In case I'm not mistaken, one should clarify this. --Muxamilian (talk) 16:10, 19 September 2018 (UTC)

Yes, the pseudo-code has complexity O(n). But for example, a Red–black_tree has complexity O(log(n)) at search/insert/delete. One can also consider a sorted array, and since one always pick the smallest one, search is done at O(1) whereas insert/delete is O(n)... MarcBoyerONERA (talk) 16:10, 21 September 2018 (UTC)

Is now() a virtual time ?

@Mspreitz: I do not understand why you have changed the text such that now() represents a virtual time. MarcBoyerONERA (talk) 09:42, 23 April 2019 (UTC)

@MarcBoyerONERA: I think now() must mean reading the virtual clock. Look in the pseudo code, at this line in updateTime: virStart = max( now(), lastVirFinish[queueNum] ). That is clearly intended to correspond to the equation in the Demers et al paper S^α_i = MAX(F^α_i-1, R(t^α_i)), which means that the virtual start time of packet i is the later of (1) the finish time of the previous packet in the same flow and (2) the virtual time of the arrival of packet i. Mspreitz 21:30, 17 May 2019 (UTC)

selectQueue vs choseQueue

@Wblackie: selectQueue and choseQueue are different functions. As marked into the comments

• choseQueue(): selects the queue where the packet is enqueued
• selectQueue(): selects the queue with the minimal virtual finish time

So, this is not a typo.