March 1, 2005
Jennifer Rexford has been awarded the 2004 Grace Murray Hopper Award by the Association for Computing Machinery (ACM) for her work on assuring stable and efficient Internet routing. The Hopper Award recognizes the outstanding young computer professional of the year.
"The Border Gateway Protocol (BGP) is the glue that holds the disparate parts of the Internet together. However, the rapid commercialization of the Internet in the last decade has put a significant strain on the interdomain-routing system. Unlike traditional routing protocols, BGP allows the operators of each domain to design policies for selecting paths to reach the Internet's many destinations and deciding which other networks may use these paths.
"BGP offers significant flexibility in selecting policies, but these policies have (at best) an indirect influence on where the traffic goes. Jennifer Rexford's work has addressed these problems through deep understanding and innovation across Computer Science theory, networking protocols, Internet economics, and ISPs' operational practices.
"Rexford's work with Lixin Gao was the first to recognize that economic relationships in the Internet have a profound influence on the behavior of the underlying protocols. This work formulated and analyzed policy-design guidelines that, if followed by each domain, would ensure that the interdomain-routing system always converges to a unique and stable solution. The guidelines are simple and motivated by the economic incentives that drive how BGP policies are configured in practice. Domains typically have either a customer-provider relationship (in which the provider ensures that the customer can send traffic to and from the rest of the Internet) or a peer-peer relationship (in which two peers agree to exchange traffic directed to their respective customers). Rexford and Gao proved that the global routing system would converge as long as (i) a domain does not allow traffic from one peer/provider to route through another peer/provider, (ii) a domain prefers to direct traffic through a customer when multiple paths exist, and (iii) the provider-customer relation is acyclic. These guidelines are consistent with common business practices, because a domain accrues revenue by directing traffic through customers but not by sending traffic through peers and providers.
"Although these guidelines constrain local routing policies, operators still have significant latitude in selecting local policies that satisfy their network-engineering goals. Translating these high-level goals into specific policies for each router is challenging. Rexford's work with Nick Feamster on modeling BGP path selection captures the network-wide effects of changes in routing policies on the flow of traffic through a network. The model considers the routing information learned from neighboring domains, the local BGP policies, the intradomain topology and routing configuration, and the offered traffic and determines the load on each link in the network. Because the model arrives at the convergent state with minimal computational overhead, it can be used as an "inner loop" in exploring different candidate routing policies to identify one that satisfies the operators' goals.
"Thus, the essential importance and impact of Rexford's work on interdomain routing is that it provided (i) the essential rules that a local domain needs to play by in order to meet the overarching goal of stability of the Internet and (ii) the concrete methods that a local domain can reliably apply to achieve both stability and its own engineering goals."
See the ACM press release.