Jennifer Rexford:
Stable Internet Routing Without Global Coordination

CITP Lecture Series

Date: Thursday, December 10, 2009
Time: 4:30 PM – 6:00 PM
Location: 101 Sherrerd Hall
Reception immediately following in 3rd floor atrium

Slides of Jennifer Rexford’s lecture

The Internet is the interconnection of tens of thousands of independently-administered networks, each acting in their own self-interest. Yet, these networks must cooperate to compute the paths that traffic traverses from one end of the Internet to the other. Responsibility for stitching the disparate parts of the Internet together falls to interdomain routing—embodied for the past twenty years in the Border Gateway Protocol (BGP). BGP allows each network, or “Autonomous system” (AS), to apply diverse local policies for selecting paths and deciding who else can direct traffic over these paths. In fact, BGP permits ASes to have conflicting policies that can lead to global routing instability, where ASes keep changing their routing decision indefinitely. Yet, in practice, we know that the Internet (mostly) “works.” In this talk, we prove that each AS acting in its own self-interest ensures a stable global system. Our results capitalize on the bilateral business relationships between neighboring ASes and the hierarchical structure of the Internet’s AS-level topology. We also propose an incrementally-deployable extension to BGP that enables ASes to have more flexible routing policies—including offering customized route selection as a service to their customers—without sacrificing global stability.


Jennifer Rexford is a Professor in the Computer Science department at Princeton University. From 1996-2004, she was a member of the Network Management and Performance department at AT&T Labs–Research. Jennifer is co-author of the book “Web Protocols and Practice” (Addison-Wesley, May 2001). She served as the chair of ACM SIGCOMM from 2003 to 2007. Jennifer received her BSE degree in electrical engineering from Princeton University in 1991, and her MSE and PhD degrees in computer science and electrical engineering from the University of Michigan in 1993 and 1996, respectively. She was the 2004 winner of ACM’s Grace Murray Hopper Award for outstanding young computer professional.

Sponsored by Microsoft