Analysis and Simulation of a Fair Queueing Algorithm

A. Demers, S. Keshave, and S. Shenker, “Analysis and simulations of a fair queueing algorithm,” in Proc. ACM SIGCOMM‘89, Austin, TX, 1989, pp. 1–12.

As it is not possible to ensure an ethical and fair usage of network resources by only trusting the end nodes, the network gateways need to support fair resource allocation when it is desired. In other words, a fair and proper congestion avoidance algorithm needs the involvement of network and end users simultaneously and otherwise it is not possible.

The authors of this paper, propose a modification to the first fair queuing algorithm proposed by Nagle (1987) which further satisfies the design requirements they had envisioned for any such fair scheme (fair bandwidth, fair buffer space and continuity of service). Nagle proposed servicing distinct queues (one queue per flow) by a round-robin scheduler per packet basis which fails to allocate BW fairly when packet sizes can be different. The modified FQ algorithm tries to emulate a bit-by-bit round-robin scheduler (BR) by computing the end service time of each packet as it arrives similar to BR but servicing them per packet basis instead of per bit basis (servicing the packet with the earliest service time first).

It is interesting to know that in many of today's high speed routers, packets are divided into equal size cells at the input, processed internally and then reassembled at the output. This might mean that enforcing fairness and priorities over variable packet sizes is still hard to implement after 20 years. Even though the papers result is nice, the single size cell approach is still the dominant method in high speed routers. It would be interesting to better understand why after 20 years (from the publication of this paper) still it is preferred to work with single size packets?

Another very interesting point in this paper is that the proposed FQ algorithm discourages the ill-behaved sources by dropping their packets while counting them towards their BW usage! I find this very interesting and effective from game theoretic point of view. In overall I found this paper to be a great mixture of intuition, analysis, simulation and effective results and therefore I would suggest it to be kept in the syllabus.

ANALYSIS OF THE INCREASE AND DECREASE ALGORITHMS FOR CONGESTION AVOIDANCE IN COMPUTER NETWORKS

D. Chiu and R. Jain, "Analysis of the increase and decrease algorithms for congestion avoidance in computer networks," Comput. Networks ISDN Syst., vol. 17, pp. 1-14, 1989.

This paper is mainly concerned with analytic comparison of linear congestion avoidance control algorithms over a synchronous binary feedback model. In other words, there are n identical end-hosts trying to share a link and the system provides them with a single bit feedback indicating overload/underload status of the link at each time stamp. Even though the assumptions of the model such as synchronicity of end-users may not hold in many scenarios, this result can be considered to be the basis of current TCP congestion control/avoidance algorithm.

To be able to have a solid comparison of algorithms, one needs to define the desired performance metrics. The authors choose efficiency (closeness of l0ad to "knee"), fairness, distributedness and convergence time (responsiveness and smoothness) as the key criteria. The paper (both analytically and pictorially) proves that within the class of linear CA algorithms, the decrease needs to be only multiplicative while increase needs to be additive with possible multiplicative part. They further show that Within this class of algorithms the Additive Increase Multiplicative Decrease (AIMD) has the fastest convergence time and therefore is the most optimal algorithm within this model and set of criteria.

The authors argue against the non-linear control algorithms as they are concerned with sensitivity of the system to parameters. It is interesting that today's TCP congestion control algorithm is a mixture of linear (congestion avoidance) and non-linear (slowstart, fast retransmit, fast recovery, ...) parts and therefore is not linear. If one only considers the result of this paper he/she can not conclude weather further investigations of the non-linear algorithms is meaningful or not!

I found this paper quite interesting since it elegantly shows the advantages of AIMD congestion avoidance algorithms within its model. It would still be interesting to analyze and discuss the model and criteria which was used by the authors. For example the result which was proved for synchronous models, how much it will hold for asynchronous models? Furthermore, distributedness was considered as a required criteria of CA algorithms. Is it correct to discard all non-distributed algorithms at once with the excuse that they will be hard to implement? Can there be semi-coordinated algorithms which have much better performances and can possibly worth the extra coordination efforts?