Feedback control for router congestion resolution

ABSTRACT

Queueing is a crucial component in effective router congestion control. If packets are dropped indiscriminately by the queueing system, in some cases, the effect can be to encourage senders to actually increase their transmission rates, worsening the congestion and destabilizing the system.We approach this congestion problem from the point of view of the elementary concepts of game theory and control theory. We provide a queueing mechanism with feedback-control. Our analysis shows that the protocol achieves high throughput as well as fairness in allocating capacity among sources, while maintaining bounded queue lengths and responding dynamically to changes in network flow conditions. Perhaps most importantly, the new protocol is shown in network simulations to have superior ability (compared with previous solutions) to protect responsive flows (specifically TCP) against router flooding by multiple high-volume unresponsive (e.g., UDP) flows.

REFERENCES

• 1: S. Athuraliya, V. H. Li, S. H. Low, and Q. Yin. REM: Active queue management. IEEE Network, 15(3):48 -- 53, May/June 2001.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: R. Braden. Requirements for internet hosts -- communication layers. STD 3, RFC 1122, October 1989.
• 4: 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
• 5: 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]
• 6: S. Floyd, R. Gummadi, and S. Shenker. Adaptive red: An algorithm for increasing the robustness of red, 2001.
• 7: 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]
• 8: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 9: Xiaojie Gao , Kamal Jain , Leonard J. Schulman, Fair and efficient router congestion control, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: Y. Gao and J. Hou. A state feedback control approach to stabilizing queues for ecn-enabled tcp connections, 2003.
• 11: Rahul Garg , Abhinav Kamra , Varun Khurana, A game-theoretic approach towards congestion control in communication networks, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.47-61, July 2002 [doi>10.1145/571697.571723]
• 12: C. V. Hollot, V. Misra, D. F. Towsley, and W. Gong. On designing improved controllers for AQM routers supporting TCP flows. In INFOCOM, pages 1726--1734, 2001.
• 13: V. Jacobson, Congestion avoidance and control, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.314-329, August 1988
• 14: 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
• 15: Controlling High-Bandwidth Flows at the Congested Router, Proceedings of the Ninth International Conference on Network Protocols, p.192, November 11-14, 2001
• 16: R. Pan, B. Prabhakar, and K. Psounis. CHOKe: a stateless active queue management scheme for approximating fair bandwidth allocation. In Proc. IEEE INFOCOM, 2000.
• 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: Ao Tang , Jiantao Wang , Steven H. Low, Understanding CHOKe: throughput and spatial characteristics, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.694-707, August 2004 [doi>10.1109/TNET.2004.833162]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design

Keywords:
Nash equilibrium, congestion control, feedback control, game theory, max-min-fairness