A. Demers, S. Keshav, S. Shenker, “Analysis and Simulation of a Fair Queueing Algorithm,” Internetworking: Research and Experience, 1 (1990), pp. 3-26.

Summary

Congestion control in communication networks can be implemented at the source, where flow control algorithms vary the sending rate, or at the gateway through routing and queueing algorithms. However, implementations at the source must rely on the benevolence of the users; hence, they are susceptible to malicious behavior. The authors argue that queueing algorithms can be more effective in congestion control since they control how packets from different sources interact and, in turn, affect the collective behavior of flow control algorithms. They consider bandwidth, promptness, and buffer space as the three control axes, effective allocation of which can ensure efficient and fair congestion control.

This paper presents a modified Fair Queueing (FQ) algorithm, based on the original proposal by Nagle, with an aim to provide fair allocation of bandwidth, lower delay for benevolent sources, and isolation of malicious ones in heterogeneous networking environment. Major changes to Nagle’s algorithm in this paper include the use of variable length packets, control over the promptness/delay of packet dispatching, and dynamic packet scheduling instead of static round-robin ordering. An allocation is considered fair if it satisfies the max-min criteria:

1. No user receives more than its request,
2. No other allocation scheme satisfying condition 1 has higher minimum allocation, and
3. Condition 2 remains recursively true as minimal user is removed and total resource is reduced accordingly.

Several possible definitions of the term user is provided: the source, the destination, the source-destination pair etc. Eventually, they settle on using the source-destination pair as user citing a tradeoff between security and efficiency (without any clear explanation!)

The algorithm itself is a packet-level approximation of a bit-by-bit (fluid) round-robin transmission model using the following rule: “whenever a packet finishes transmission, next one selected is the one with the earliest finish time“. A preemptive version of the algorithm is also presented, which additionally supports a tolerance parameter to allow users using less than fair share bandwidth to have lower delay. Packet dropping policy used in FQ is: “when the queue is full and a new packet arrives, the last packet from the user using the most buffer is dropped”, which provides a small incentive for the users to implement better flow controls.

Finally, through mathematical derivation and simulation, the authors establish the performance and fairness gain of modified FQ working in conjunction with different congestion control schemes.

Thoughts

The use of source-destination pair as user is not properly justified in the paper. The authors do mention the possible security concerns arising from it (malicious source hogging resources by creating many source-destination pairs), but ignore it completely.

Also, the memory requirement for keeping states (too many of them in case of source-destination pairs), price, deployability of FQ in gateways are not discussed.