A two-time-scale design for edge-based detection and rectification of uncooperative flows

ABSTRACT

Existing Internet protocols rely on cooperative behavior of end users. We present a control-theoretic algorithm to counteract uncooperative users which change their congestion control schemes to gain larger bandwidth. This algorithm rectifies uncooperative users; that is, forces them to comply with their fair share, by adjusting the prices fed back to them. It is to be implemented at the edge of the network (e.g., by ISPs), and can be used with any congestion notification policy deployed by the network. Our design achieves a separation of time-scales between the network congestion feedback loop and the price-adjustment loop, thus recovering the fair allocation of bandwidth upon a fast transient phase.

REFERENCES

• 1: [1] F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.
• 2: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 3: Aditya Akella , Srinivasan Seshan , Richard Karp , Scott Shenker , Christos Papadimitriou, Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 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: Aleksandar Kuzmanovic , Edward W. Knightly, Low-rate TCP-targeted denial of service attacks: the shrew vs. the mice and elephants, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863966]
• 6: Sergey Gorinsky , Sugat Jain , Harrick Vin , Yongguang Zhang, Robustness to inflated subscription in multicast congestion control, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863967]
• 7: 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
• 8: [8] W. Feng et al., "Stochastic fair blue: a queue management algorithm for enforcing fairness," in Proc. IEEE INFOCOM, Apr. 2001, pp. 1520-1529.
• 9: [9] R. Mahajan and S. Floyd, "Controlling high-bandwidth flows at the congested routers," in Proc. IEEE ICNP, Nov. 2001, pp. 1-12.
• 10: [10] Packeteer Inc. [Online]. Available: http://www.packeteer.com
• 11: 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
• 12: Kartikeya Chandrayana , Shivkumar Kalyanaraman, Uncooperative congestion control, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 13: [13] S. Kunniyur and R. Srikant, "End-to-end congestion control: utility functions, random losses and ECN marks," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, pp. 1323-1332.
• 14: [14] S. H. Low, F. Paganini, and J. C. Doyle, "Internet congestion control," IEEE Contr. Syst. Mag., vol. 22, no. 1, pp. 28-43, Feb. 2002.
• 15: [15] J. Wen and M. Arcak, "A unifying passivity framework for network flow control," IEEE Trans. Autom. Contr., vol. 49, no. 2, pp. 162-174, Feb. 2004.
• 16: Lawrence S. Brakmo , Sean W. O'Malley , Larry L. Peterson, TCP Vegas: new techniques for congestion detection and avoidance, Proceedings of the conference on Communications architectures, protocols and applications, p.24-35, August 31-September 02, 1994, London, United Kingdom
• 17: [17] C. Jin, D. X. Wei, and S. Low, "FAST TCP: motivation, architecture, algorithms, performance," in Proc. IEEE INFOCOM, 2004, pp. 2490-2501.
• 18: Peter V. Kokotovic , John O'Reilly , Hassan K. Khalil, Singular Perturbation Methods in Control: Analysis and Design, Academic Press, Inc., Orlando, FL, 1986
• 19: [19] H. K. Khalil, Nonlinear Systems, 3rd ed. Englewood Cliffs, NJ: Prentice-Hall, 2002.
• 20: [20] F. Paganini, J. Doyle, and S. Low, "Scalable laws for stable network congestion control," in Proc. Conf. Decision and Control, Orlando, FL, Dec. 2001, pp. 185-190.
• 21: [21] F. Paganini, "A global stability result in network flow control," Syst. Contr. Lett., vol. 46, pp. 165-172, 2002.
• 22: [22] S. Deb and R. Srikant, Global stability of congestion controllers for the Internet Univ. Illinois, Urbana, IL, Internal Rep., Feb. 2002.
• 23: [23] On the stability of end-to-end congestion control for the Internet Univ. Cambridge, Cambridge, U.K., Tech. Rep. CUED/F-INFENG/TR.398, Dec. 2000.
• 24: [24] X. Fan, M. Arcak, and J. T. Wen, "Robustness of network flow control against disturbances and time-delay," Syst. Contr. Lett., vol. 53, no. 1, pp. 13-29.
• 25: Rayadurgam Srikant, The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications), SpringerVerlag, 2004
• 26: [26] G. H. Hardy, J. E. Littlewood, and G. Polya, Inequalities, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 1988.
• 27: Sally Floyd , Mark Handley , Jitendra Padhye , Jörg Widmer, Equation-based congestion control for unicast applications, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.43-56, August 28-September 01, 2000, Stockholm, Sweden

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Management

Keywords:
network congestion control, singular-perturbations, uncooperative flow control