Analysis and Simulation of a Fair Queueing Algorithm

Summary

This paper talks about a fair queueing algorithm that is based on Nagle's fair queueing (FQ) algorithm. The authors set forth 3 quantities that they want to be able to measure and optimize: bandwidth, promptness and buffer space. The main requirement they want to meet is fair bandwidth and buffer space allocation. They use the max-min criterion to define fairness. They also define what a user could be and decide that a user will be a source-destination pair.

They describe the algorithm in detail, which is trying to simulate the bit-by-bit round-robin algorithm. They claim the algorithm they describe asymptotically approaches the fair bandwidth allocation of the bit-by-bit round-robin algorithm. They also describe an addition to the algorithm that gives users who use less than their share of the bandwidth more promptness. And, when the queue becomes full, the last packet of the user with the highest amount of buffer space is dropped, which essentially penalizes ill-behaved hosts.

Finally, the authors run several simulations to compare FQ to FCFS using various flow control algorithms. When running the simulations, they looked at 4 performance criterion: total throughput, average rtt of the packets, number of packet retransmissions and number of dropped packets. The results showed that FQ works the best when paired with the JK flow control algorithm, giving end-hosts an incentive to implement more intelligent flow control algorithms.

Criticism & Questions

When choosing their definition of user, they mention the drawback that comes from an ill-behaved host opening up multiple connections with different destinations in order to congest the network. However, they didn't try this scenario out in the simulations - that would have been interesting to see.

They also put forth several alternative definitions to user and mention that the definition can be easily changed in their algorithm. Their algorithm would be more compelling if they could run their simulations with all the types of users to show that it works equally well for all of them or how it works better or worse for some definitions of user.