Fair and efficient router congestion control

ABSTRACT

Congestion is a natural phenomenon in any network queuing system, and is unavoidable if the queuing system is operated near capacity. In this paper we study how to set the rules of a queuing system so that all the users have a self-interest in controlling congestion when it happens.Routers in the internet respond to local congestion by dropping packets. But if packets are dropped indiscriminately, the effect can be to encourage senders to actually increase their transmission rates, worsening the congestion and destabilizing the system. Alternatively, and only slightly more preferably, the effect can be to arbitrarily let a few insistent senders take over most of the router capacity.We approach this problem from first principles: a router packet-dropping protocol is a mechanism that sets up a game between the senders, who are in turn competing for link capacity. Our task is to design this mechanism so that the game equilibrium is desirable: high total rate is achieved and is shared widely among all senders. In addition, equilibrium should be reestablished quickly in response to changes in transmission rates. Our solution is based upon auction theory: in principle, although not always in practice, we drop packets of the highest-rate sender, in case of congestion. We will prove the game-theoretic merits of our method. We'll also describe a variant of the method with some further advantages that will be supported by network simulations.

REFERENCES

• 1: A. Albanese, J. Blomer, J. Edmonds, M. Luby, and M. Sudan. Priority encoded transmission. IEEE Trans. Information Theory, 42(6):1737--1744, 1996.
• 2: J.C.R. Bennett and H. Zhang. WF2 Q: Worstcase fair weighted fair queueing. In Proc. IEEE INFOCOM, pages 120--128, 1996.
• 3: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 4: Sally Floyd , Kevin Fall, Promoting the use of end-to-end congestion control in the Internet, IEEE/ACM Transactions on Networking (TON), v.7 n.4, p.458-472, Aug. 1999 [doi>10.1109/90.793002]
• 5: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 6: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 7: S. Golestani. A selfclocked fair queueing scheme for broadband applications. In Proc. IEEE INFOCOM, pages 636--646, 1994.
• 8: E. Hashem. Analysis of random drop for gateway congestion control. MIT LCS Technical Report 465, 1989.
• 9: J. M. Jaffe. Bottleneck flow control. IEEE Trans. on Comm., COM-29(7):954--962.
• 10: R. M. Karp, C. H. Papadimitriou, and S. Shenker. A simple algorithm for finding frequent elements in streams and bags. Manuscript.
• 11: Dong Lin , Robert Morris, Dynamics of random early detection, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.127-137, September 14-18, 1997, Cannes, France
• 12: P. McKenny. Stochastic fairness queueing. In Proc. IEEE INFOCOM, pages 733--740, 1990.
• 13: T. Ott, T. Lakshman, and L. Wong. SRED: Stabilized RED. In Proc. INFOCOM, pages 1346--1355, 1999.
• 14: R. Pan, B. Prabhakar, and K. Psounis. CHOKe: a stateless active queue management scheme for approximating fair bandwidth allocation. In Proc. IEEE IN-FOCOM, 2000.
• 15: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks—the single node case, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 2), p.915-924, May 1992, Florence, Italy
• 16: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 17: Ion Stoica , Scott Shenker , Hui Zhang, Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.118-130, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 18: A. Tang, J. Wang, and S. H. Low. Understanding CHOKe. In Proc. IEEE INFOCOM, 2003.