Analysis and Simulation of a Fair Queueing Algorithm

This paper discusses the role of gateway queueing algorithms in congestion control and proceeds to present the many advantages of a proposed fair queueing algorithm. Unlike the previous papers that detailed source-based congestion control schemes, this one focuses on the effect of gateway-based queueing algorithms on congestion control. The authors argue that standard FCFS queuing algorithms place the burden of congestion control completely on hosts, thereby leaving the network bandwidth vulnerable to ill-behaved hosts that do not comply with standard TCP congestion control schemes. In this light, Nagle's round-robin-based fair queueing (FQ) algorithm aims to provide protection against "antisocial" behavior by employing gateway queueing-based congestion control. Unfortunately, Nagle's proposal does not ensure fairness for several reasons - for one, it does not account for packet lengths. Before diving into their own proposal, the authors clarify the motivation behind a fair queueing algorithm.

The fair allocation of bandwidth, promptness and buffer space among users is complicated by the question of what defines a user. Rather than defining the user as the source, the destination or a process running on the source host, the best trade-off is achieved by allocating by conversations (source-destination pairs). The proposed algorithm uses a packetized queueing mechanism based on the end times of packets; this successfully accounts for packet lengths. Moreover, newly arriving packets are accommodated in the queue by dropping the last packet from the dominant conversation. In effect, this punishes ill-behaved hosts by charging them for poor congestion control on their end. Finally, the authors compare the performance of the FQ scheme to that of the FCFS-based standard congestion control. In conclusion, the authors assert that achieving low delay or avoiding dropped packets is very difficult with congestion control only at hosts, especially in a non-cooperative environment. Two objections have been raised to FQ algorithm-based congestion control. The first objection is that some conversations need more bandwidth than would be deemed "fair" (file server pairs, for example) - one solution to this is to utilize bandwidth priorities in the queueing algorithm. The second objection is that such a FQ algorithm requires advanced gateways, which may not be technologically or economically feasible.

This paper was very intriguing because it provided a new angle to congestion control, one which I'd never seen before. I'm surprised that this aspect of congestion control is rarely covered in undergraduate networking. The authors did a fairly good job of covering the caveats involved, such as applications that require "unfair" bandwidth allocation, but elaboration on assigning bandwidth priorities would have been interesting indeed. Definitely one to keep in the syllabus.