On Fair Queueing Algorithms and Core-Stateless Routers

Previously, I commented on the possible unfairness in the congestion avoidance papers specifically when the users are uncooperative. Interestingly, the set of readings for today talk about putting intelligence inside the network for traffic control. Both papers recognize that while end-host control can contribute to congestion avoidance, it is somewhat ineffective when some users are misbehaving. These misbehaving users can either be simply misconfigured or intentionally opportunistic resulting in the unequitable share in bandwidth. These users will grab more bandwidth because TCP-friendly users will graciously throttle back during congestion. Both DKS90 (Demers, Keshav, Shenker, 1990) and SSZ98 (Stoica, Shenker, Zhang 1998) carefully show the interplay between flow controlled sources, uncooperative sources and basic FIFO scheduling. Their results clearly indicate that bandwidth protection is impossible in an environment of mixed users with simple scheduling. With this premise, DKS90 and SSZ98 present fair algorithms and describe the conditions where they work best.

In the DKS90 paper, the authors emulate the bit-by-bit round-robin algorithm and uses the ordering generated from this to schedule packets in a gateway. In this way, the algorithm is fair and also addresses the fixed-packet size constraint of Nagle’s solution. Nagle’s round-robin solution is biased toward flows with large packets. DKS90 also notes that this work is very similar to the work of Zhang. In Zhang’s work, the Virtual Clock (which is similar to the algorithm developed in DKS90), together with an appropriate admission control policy, can be used to establish bounds on delay. This is an important result in terms of assuring end-user service commitments.

While DKS90 shows significant improvement in fairness, the drawback is that the algorithm may be difficult to implement. The premise of DKS90 requires per flow information to be kept at each router which is quite unrealistic. The SSZ98 paper suggests a solution to this problem. They claim that state information is important but should not be placed in all nodes. In their paper, they differentiate the roles of exterior routers and interior routers. They believe that in the core (or interior), no state information except for the labels should be kept. They also assert that maintenance of per-flow state information should be placed as close to the source as possible – in this case the edge routers. This is a classic trade-off scenario wherein you balance complexity and cost (overhead) considerations.

Clearly from these materials and previous readings, it appears that no one algorithm or mechanism would be able to answer the problems of the network. What we may see is that different mechanisms will be working together to achieve a common goal. In the case of these papers, congestion avoidance and bandwidth protection goes hand and hand.