Program at a glance   Tutorial program   Technical program   Abstracts   Papers


Routing Stability and Convergence
Full Paper
Routing Stability in Congested Networks: Experimentation and Analysis
Aman Shaikh (University of California, Santa Cruz)
Lampros Kalampoukas (Bell Labs, Lucent Technologies)
Rohit Dube (Bell Labs, Lucent Technologies)
Anujan Varma (University of California, Santa Cruz)
Loss of the routing protocol messages due to network congestion can cause peering session failures in routers, leading to route flapping and routing instabilities. We study the effects of traffic overload on routing protocols by quantifying the stability and robustness properties of two common Internet routing protocols, OSPF and BGP, when the routing control traffic is not isolated from data traffic. We develop analytical models to quantify the effect of congestion on the robustness of OSPF and BGP as a function of the traffic overload factor, queueing delays, and packet sizes. We perform extensive measurements in an experimental network of routers to validate the analytical results. We subsequently use the analytical framework to investigate the effect of factors that are difficult to incorporate into an experimental setup, such as a wide range of link propagation delays and packet dropping policies. Our results show that increased queuing and propagation delays adversely affect BGP's resillience to congestion, in spite of its use of a reliable transport protocol. Our findings demonstrate the importance of selective treatment of routing protocol messages from other traffic, by scheduling and buffer management policies in the routers, to achieve stable and robust network operation.