Methodological frameworks for large-scale network analysis and design

ABSTRACT

This paper emphasizes the need for methodological frameworks for analysis and design of large scale networks which are independent of specific design innovations and their advocacy, with the aim of making networking a more systematic engineering discipline. Networking problems have largely confounded existing theory, and innovation based on intuition has dominated design. This paper will illustrate potential pitfalls of this practice. The general aim is to illustrate universal aspects of theoretical and methodological research that can be applied to network design and verification. The issues focused on will include the choice of models, including the relationship between flow and packet level descriptions, the need to account for uncertainty generated by modelling abstractions, and the challenges of dealing with network scale. The rigorous comparison of proposed schemes will be illustrated using various abstractions. While standard tools from robust control theory have been applied in this area, we will also illustrate how network-specific challenges can drive the development of new mathematics that expand their range of applicability, and how many enormous challenges remain.

REFERENCES

• 1: H. Choe and S. H. Low. Stabilized Vegas. In Proc. of IEEE Infocom, 2003.
• 2: G. E. Dullerud and F. Paganini. A Course in Robust Control Theory: A Convex Approach. Springer-Verlag, 2000.
• 3: X. Fan, M. Arcak, and J. Wen. Robustness of network flow control against disturbances and time-delay. To appear in System and Control Letters, 2004.
• 4: J. K. Hale and S. M. V. Lunel. Introduction to Functional Differential Equations. Applied Mathematical Sciences (99). Springer-Verlag, 1993.
• 5: Zhang Heying , Liu Baohong , Dou Wenhua, Design of a robust active queue management algorithm based on feedback compensation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863987]
• 6: C. V. Hollot, V. Misra, D. Towsley, and W. Gong. A control theoretic analysis of red. In Proc. of IEEE Infocom, 2001.
• 7: R. Jain. Congestion control in computer networks: Issues and trends. IEEE Network Magazine, pages 24--30, May 1990.
• 8: F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.
• 9: Srinivasan Keshav, A control-theoretic approach to flow control, Proceedings of the conference on Communications architecture & protocols, p.3-15, September 03-06, 1991, Zurich, Switzerland
• 10: H. K. Khalil. Nonlinear Systems. Prentice Hall, Inc., second edition, 1996.
• 11: S. Kunniyur and R. Srikant. A time-scale decomposition approach to adaptive ECN marking. IEEE Transactions on Automatic Control, 47(6):882--894, 2002.
• 12: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 13: 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]
• 14: S. H. Low, F. Paganini, and J. C. Doyle. Internet congestion control. IEEE Control Systems Magazine, 2002.
• 15: Steven H. Low , Fernando Paganini , Jiantao Wang , John C. Doyle, Linear stability of TCP/RED and a scalable control, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.5, p.633-647, 5 December 2003 [doi>10.1016/S1389-1286(03)00304-9]
• 16: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 17: A. Megretski and A. Rantzer. System analysis via integral quadratic constraints. IEEE Transactions on Automatic Control, 42(6):819--830, 1997.
• 18: Vishal Misra , Wei-Bo Gong , Don Towsley, Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.151-160, August 28-September 01, 2000, Stockholm, Sweden
• 19: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 20: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 21: F. Paganini, J. Doyle, and S. Low. Scalable laws for stable network congestion control. In Proceedings of the 40th IEEE Conf. on Decision and Control, Orlando, FL, 2001.
• 22: F. Paganini, J. C. Doyle, and S. H. Low. Scalable laws for stable network congestion control. In Proc. of the 40th Conference on Decision and Control, 2001.
• 23: Fernando Paganini , Zhikui Wang , John C. Doyle , Steven H. Low, Congestion control for high performance, stability, and fairness in general networks, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.43-56, February 2005 [doi>10.1109/TNET.2004.842216]
• 24: A. Papachristodoulou. Analysis of nonlinear time delay systems using the sum of squares decomposition. In Proc. of the American Control Conference, 2004.
• 25: A. Papachristodoulou and S. Prajna. On the construction of Lyapunov functions using the sum of squares decomposition. In Proc. of the 41st IEEE Conference on Decision and Control, 2002.
• 26: S. Prajna, A. Papachristodoulou, and P. Parrilo. Introducing SOSTOOLS: A general purpose sum of squares programming solver. In Proc. of the 41st IEEE Conference on Decision and Control, 2002.
• 27: S. Shenker, A theoretical analysis of feedback flow control, Proceedings of the ACM symposium on Communications architectures & protocols, p.156-165, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 28: Rayadurgam Srikant, The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications), SpringerVerlag, 2004
• 29: G. Vinnicombe. Robust congestion control for the Internet, submitted for publication.
• 30: G. Vinnicombe. On the stability of networks operating TCP-like congestion control. In Proc. of IFAC World Congress, 2002.