Analysis and Simulation of a Fair Queueing Algorithm

The authors hypothesize that queueing algorithms play a crucial component in effective network congestion control because: (1) flow control is only helpful for ensuring the presence of free buffer space at a receiver and (2) adaptive routing is only helpful for pushing packets away from network congestion/bottlenecks. Queuing algorithms, they speculate, which are considered only helpful for controlling the order in which packets are sent and the usage of a gateways buffer space, can also affect the way in which different packets from different conversations interact with one another which ultimately will affect the collective behavior of flow control algorithms.

The authors discuss how the most common queuing algorithm, first-come-first-served (FCFS), essentially "relegates congestion control to the sources". They propose Fair Queuing (FQ) as an alternative which allows one to allocate all of bandwidth, promptness, and buffer space fairly. Not only will this allow fair usage of resources, but it also provides a lower delay to lower throughput sources (like Telnet applications). They claim this as one of the prominent features of FQ.

They do some interesting simulations and have some great takeaway points:

• FQ by itself do not provide adequate congestion control; they must be combined with intelligent flow control algorithms to at the sources.
• Ill-behaved hosts get much less than their fair share because they have dropped packets even though they still get charged for their throughput.
• Moreover, FQ protects well behaved sources from their "uncouth brethren", which ultimately rewards good sources.
• FQ provides incentive for sources to implement Jacobson and Karels or some other intelligent flow control, where as FCFS makes using these "sacrificial".

I especially enjoyed their conclusion on how the game-theoretic perspective is important, in fact perhaps even necessary, to achieve their goals. (Again, this is further justification of how a well specified cooperative environment can perform incredibly well!)

This paper was an enjoyable read and I recommend it remain part of the curriculum. If I had any criticism I would have hoped they did more simulations that included more than one gateway (to see how these mechanisms work across larger networks).

I also think this is a prime source of information for anyone interested in looking at how virtual machine monitors do networking since, essentially, they are are gateway/router of sorts.