Fair Queuing

This paper essentially answers the questions I raised last time about adversarial endpoints who abuse the congestion avoidance schemes to get more bandwidth for themselves. In essence, the paper describes a queuing algorithm that can be used by gateways to do two things: (1) ensure fair use of the bandwidth, and (2) punish misbehaving nodes.

The idea is relatively simple. The gateway considers packets on a source-destination pair basis. This allows it to distribute resources based on individual connections, while minimizing the amount of damage that a malicious user can do (the malicious user can get more than their fair share of bandwidth, but cannot do any useful work). Then, incoming packets are each assigned a number that is the sum of their arrival time and the length of time it will take to send the packet. The packet with the lowest value is transmitted first. There is an additional modification to the algorithm that gives an advantage to connections that have been idle for a while (by subtracting a small nonnegative value delta).

This essentially solves the problem of having adversarial TCP nodes which do not obey congestion avoidance rules and allow their sending windows to grow too large. And by punishing nodes that misbehave, it actually encourages the use of congestion avoidance algorithms, whereas a node attached to a round robin scheduler actually sacrifices some bandwidth by using the congestion avoidance algorithms.

The paper has lots of experimental data, but the data comes from relatively simple network graphs. It would be interesting to see the performance of this algorithm with a very large network with many gateways. One of the issues that is raised in the paper is that the algorithm must be both smart and fast, and this may not be possible for a gateway that has an enormous number of packets going through it.