Decentralized control of large-scale networks as a game with local interactions: cross-layer TCP/IP optimization

ABSTRACT

Developing optimized distributed protocols for large-scale networks is a challenging problem due to scalability and stability concerns. Scalability concerns can be naturally addressed by interpreting distributed protocols as a non-cooperative game of local protocol components attempting to maximize their individual utilities. One of the difficulties in implementing this approach is developing adaptive algorithms capable of learning of the expected utilities and adjusting the corresponding control actions for the purpose of approaching the solution to the corresponding game, and thus optimization of the global system performance. It is known that the best response by each component to its expected utility may result in unstable behavior and deterioration of the overall performance. On an example of cross-layer optimization of a TCP/IP network, this paper discusses the possibility of avoiding these undesirable effects by allowing the control actions occasionally deviate from their best response values. Using simulations, the paper suggests that (a) sufficient level of randomness in route selection improves the network performance by eliminating the route flapping instability, (b) the optimal level of randomness keeps the network within the stability region in close proximity to the border of this region, and (c) it may be possible to optimize the network performance by adjusting the level of randomness.

References

1. A. G. Ganek and T. A. Corbi, "The dawning of the autonomic computing era," IBM Systems J., Vol. 42, No 1, 2003, pp.5--18.
2. D. Fudenberg and D. K. Levine, The theory of learning in games, The MIT Press, 1999.
3. C. Huitema, Routing in the Internet, Prentice Hall, 2000.
4. D. Bertsekas and R. Gallager, Data Networks, Prentice-Hall, New Jersey, 1992.
5. J. Wang, L. Li, S. H. Low, and J. C. Doyle, "Cross-layer optimization in TCP/IP networks," IEEE/ACM Trans. on Networking, to appear, available at http://netlab.caltech.edu/.
6. A. Elwalid, C. Jin, S. Low and J. Widjaja, "MATE: MPLS Adaptive Traffic Engineering," in Proceedings of Infocom'2001, Anchorage, Alaska, April 2001.
7. D. P. Bertsekas, "Dynamic behavior of shortest path routing algorithm for communication networks," IEEE Trans. On Automatic Control, pp. 60--74, Feb. 1982.
8. S. H. Low and P. Varaiya, "Dynamic behavior of a class of adaptive routing protocols (IGRP)," Proc. Of Infocom'93, pp. 610--616, March 1993.
9. Z. Wang, Y. Wang, and L. Zhang, "Internet traffic engineering without full mesh overlaying," in Proceedings of Infocom'2001, Anchorage, Alaska, April 2001.
10. A. Sridharan, R. Guerin, and Cristophe Diot, "Achieving Near Optimal Traffic Engineering Solution for Current OSPF/IS-IS Networks," in Proceedings of Infocom'2003.
11. F. P. Kelly, A. K. Maulloo, and D. H. K. Tan, "The rate control for communication networks: shadow prices, proportional fairness and stability," Journal of the Operational Research Society, pp. 237--252, vol. 409, 1998.
12. T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 1991.
13. V. Marbukh, "Network provisioning as a game against nature," IEEE International Communications Conference (ICC 2003), Anchorage, AK, 2003.
14. V. Marbukh, "On Shortest random walks under adversarial uncertainty", Fortieth Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, 2002.
15. O. Borchert and R. Rouil, "The GMPLS lightwave agile switching simulator -- an overview," http://www.antd.nist.gov/glass.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

    • Availability

    • Maintainability and maintenance

    • Reliability

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• General and reference

  • Cross-computing tools and techniques

    • Performance

    • Reliability