A Theory of Stability for Communication Networks

PI: David Starobinski

Research supported by the Office of Science at the U.S. Department of Energy

High-performance networks, such as ESnet, rely on advanced control-plane protocols such as RIP, OSPF, BGP, RSVP, and MPLS, to support efficient data packet forwarding over the network. Despite their extreme importance, these control-plane protocols are vulnerable to various forms of instability, such as delayed convergence, persistent route oscillations, thrashing, and deadlocks. The goal of this project is to develop a unified theoretical framework to understand and address these stability issues. Accordingly, a program of research will be developed, centering on the following objectives: (i) identify the different forms of instability that control-plane protocols may exhibit; (ii) determine the fundamental, theoretical causes of instability; (iii) estimate, using analysis and simulation, the likelihood of occurrence of instability phenomena in control-plane protocols as a function of network and protocol parameters; (iv) prevent instability in control-plane protocols, through the development of new algorithmic and graph-theoretic methodologies. The results of this research will have direct bearing on the design of robust and reliable control-plane protocols for UltraScience Net and other next-generation DOE networks.

Links:

Bandwidth Allocation GUI for UltraScience Net

References:

1. Francesco de Pellegrini, David Starobinski, Mark Karpovsky and Lev Levitin, ``Scalable Cycle-Breaking Algorithms for Gigabit Ethernet Backbones,'' IEEE INFOCOM 2004, Hong Kong, March 2004. pdf
2. David Starobinski, Mark Karpovsky, and Lev Zakrevski, ``Application of Network Calculus to General Topologies using Turn-Prohibition,'' IEEE/ACM Transactions on Networking, Vol. 11, No. 3, pp. 411-421, June 2003. pdf
3. David Starobinski and Moshe Sidi, ``Stochastically Bounded Burstiness for Communication Networks,'' IEEE Transactions on Information Theory, Vol. 46, No. 1, pp.206-212, January 2000. Gzipped PostScript