Analysis and Simulation of a Fair Queueing Algorithm

This paper considers a fair queuing algorithm for gateways for deciding how to forward incoming packets. The authors claim that queuing attempts to allocate bandwidth, buffer space and promptness, and first-come-first-serve (FCFS) ties all of them together. While the congestion avoidance papers from the previous class consider source/node flow control to vary transmission rate, it was assumed that hosts are cooperative. Another desired property of a queuing algorithm is to allow gateways to control congestion even when certain hosts are non-compliant.

The proposed fair queueing (FQ) algorithm essentially tries to emulate a bitwise round-robin servicing; i.e. each conversation (between host-destination) takes turn sending a bit. For practical reasons, a packet-by-packet transmission is done instead, but the packet arrival time and packet size is used to decide when it is to be sent. A separate parameter is used to regulate promptness, by taking into account when a packet was last transmitted for that conversation. Finally, if a packet arrives when the buffer is full, the latest packet from the conversation using the most buffer space is dropped, BUT the conversation would still be charged for that packet. This essentially punishes out-of-control senders.

The simulations show essentially that FQ works with a range of flow control algorithms to provide fair bandwidth distribution for high-throughput FTP and low delay for Telnet, in contrast to FCFS which could produce "winners" for FTP and high delay for Telnet. It also very nicely shuts down a ill-behaved source, which seemed to me a most desirable outcome.

I liked this paper because it addressed a question I had from the earlier readings, which is how to program gateways to deal with mis-behaving hosts and somewhat control congestion. There are also many questions that the authors posed which could lead to interesting research. For example, it was not clear if a game-theoretic analysis of fair queuing would lead to the conclusion that the best thing hosts could do is to adopt some reasonable flow control, and that they cannot do any better (i.e. cheat to get more bandwidth).