Dynamics of Hot-Potato Routing in IP Networks

Tuesday, January 13, 2004 - 3:00pm - 3:50pm
Keller 3-180
Jennifer Rexford (AT&T Laboratories - Research)
The separation of intradomain and interdomain routing is a key feature of the Internet routing architecture. However, intradomain routing protocols such as OSPF and IS-IS do have a (sometimes significant) influence on the path-selection process in the Border Gateway Protocol (BGP). This talk presents an analysis of the influence of OSPF on BGP routing a large tier-1 ISP network. We propose a general methodology for associating BGP update messages with events visible in OSPF. Then, we apply our methodology to streams of OSPF link-state advertisements and BGP update messages from AT&T's domestic IP backbone. Our analysis shows that (i) hot potato routing is sometimes a significant source of BGP updates, (ii) BGP updates can lag 60 seconds behind the related OSPF event, which can cause delays in forwarding-plane convergence, (iii) OSPF-triggered BGP updates have a nearly uniform distribution across destination prefixes, and (iv) the fraction of BGP messages triggered by OSPF varies significantly across time and router locations, with important implications on external monitoring of BGP. We also describe how certain network designs and operational practices increase the impact that internal OSPF events have on BGP routing.

This is a joint work with Renata Teixeira, Aman Shaikh, and Tim Griffin.