From: Ethan Katz-Bassett (ethan@cs.washington.edu)
Date: Sun Oct 24 2004 - 17:46:50 PDT
In this paper, the authors address the problem of network gateway queuing
disciplines and present their fair queuing algorithm. When the paper was
written, first-come first-serve (FCFS) was the dominate discipline. They
explain queuing disciplines as addressing three concerns: bandwidth
allocation, buffer space allocation, and promptness. With FCFS, the order
of arrival of packets completely decides all three, an unfair system open to
abuse. The fair queuing algorithm attempts to address all three concerns
separately and fairly, is not abusable in the ways that FCFS is, and seems
to offer no disadvantages vs FCFS, other than being more complex.
The authors present bit-by-bit round-robin as a fair scheme, then give their
fair queuing algorithm as a workable approximation. This approach reminded
me somewhat of how the digital fountain was presented. By simulating
bit-by-bit round-robin, this algorithm achieves fairer bandwidth allocation
than ones that use packet-by-packet round-robin. I enjoyed the authors'
explanations of the advantages and disadvantages of the different choices of
what represents a user; I wish they had gone into this more.
One great advantage of the fair queuing scheme is that it encourages hosts
to employ effective flow control algorithms, and it penalizes hosts that do
not attempt to. Fair queuing works no matter the flow control at the hosts,
yet gives an incentive for hosts to play fair.
I wish the paper had described more the reason for giving faster service to
newly active flows. While it makes sense in their FTP/Telnet example, I am
not yet convinced that this is always the proper behavior.
The fair queuing algorithm provides obvious benefits over FCFS and provides
some necessary fairness. I wish that the paper had dealt more with weighted
fair queuing; the authors mention it briefly in the conclusion, but without
any real analysis. More complicated schemes are necessary to provide truly
differentiated service. Among other things, simply dropping from whichever
queue fills does not properly weight "important" flows, and dropping only
when buffers fill does not seem sufficient to fulfill low-latency
guarantees.
This archive was generated by hypermail 2.1.6 : Sun Oct 24 2004 - 17:46:55 PDT