The University of Massachusetts Amherst
University of Massachusetts Amherst

Search Google Appliance

Links

Gao Wins Test of Time Award

Professor Lixin Gao of the Electrical and Computer Engineering Department has won the "SIGMETRICS Test of Time Award," which recognizes an influential performance evaluation paper whose impact is still felt 10-12 years after its initial publication. In 2000, Gao collaborated with Jennifer Rexford to write the winning paper: "Stable Internet Routing without Global Coordination."

During the Proceedings of ACM SIGMETRICS 2000, this paper provided a formal analysis of Border Gateway Protocol (BGP) routing policies and showed how to ensure convergence to stable Internet routes without requiring routers to divulge their BGP configurations. See http://www.sigmetrics.org/awards.shtml for details. SIGMETRICS is the ACM Special Interest Group for the computer systems performance evaluation community

Professor Gao, who became an IEEE Fellow in 2009, was one of the eight “nationally acclaimed faculty members” presented with the Award for Outstanding Accomplishments in Research and Creative Activity at the most recent Annual Faculty Convocation at UMass Amherst.

As Gao’s 2000 paper explained: “The Border Gateway Protocol (BGP) allows an autonomous system (AS) to apply diverse local policies for selecting routes and propagating reachability information to other domains. However, BGP permits ASes to have conflicting policies that can lead to routing instability. This paper 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.” (June 2011)