Stable Internet Routing Without Global Coordination

Monday, February 9, 2009 -
4:00pm to 6:00pm
Global Internet connectivity results from a competitive cooperation of tens of thousands of independently-administered networks (called Autonomous Systems), each with their own preferences for how traffic should flow. The responsibility for reconciling these preferences falls to interdomain routing, realized today by the Border Gateway Protocol (BGP). However, BGP allows ASes to express conflicting local policies that can lead to global routing instability. This talk proposes a set of guidelines for an AS to follow in setting its routing policies, without requiring coordination with other ASes. Our approach exploits the Internet's hierarchical structure and the commercial relationships between ASes to impose a partial order on the set of routes to each destination. The guidelines conform to conventional traffic-engineering practices of ISPs, and provide each AS with significant flexibility in selecting its local policies. Furthermore, the guidelines ensure route convergence even under changes in the topology and routing policies. Drawing on a formal model of BGP, we prove that following our proposed policy guidelines guarantees route convergence. We also describe how our methodology can be applied to new types of relationships between ASes, how to verify the hierarchical AS relationships, and how to realize our policy guidelines. Our approach has significant practical value since it preserves the ability of each AS to apply complex local policies without divulging its BGP configurations to others.
Jennifer Rexford
Princeton University
Event Location: 
Fine Hall 214