IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 9, NO. 6, DECEMBER 2001 681Stable Internet Routing Without Global CoordinationLixin Gao, Member, IEEE, and Jennifer Rexford, Senior Member, IEEEAbstract—The Border Gateway Protocol (BGP) allows an au-tonomous system (AS) to apply diverse local policies for selectingroutes and propagating reachability information to other domains.However, BGP permits ASs to have conflicting policies that canlead to routing instability. This paper proposes a set of guidelinesfor an AS to follow in setting its routing policies, without requiringcoordination with other ASs. Our approach exploits the Internet’shierarchical structure and the commercial relationships betweenASs to impose a partial order on the set of routes to each desti-nation. The guidelines conform to conventional traffic-engineeringpractices of ISPs, and provideeachASwithsignificantflexibilityinselectingitslocalpolicies.Furthermore,theguidelines ensurerouteconvergence even under changes in the topology and routing poli-cies. Drawing on a formal model of BGP, we prove that followingour proposed policy guidelines guarantees route convergence. Wealso describe how our methodology can be applied to new types ofrelationships between ASs, how to verify the hierarchical AS rela-tionships, and how to realize our policy guidelines. Our approachhas significant practical value since it preserves the ability of eachAS to apply complex local policies without divulging its BGP con-figurations to others.Index Terms—Border Gateway Protocol (BGP), convergence,Internet, protocols, routing.I. INTRODUCTIONTHE INTERNET connects thousands of AutonomousSystems (ASs) operated by different institutions, such asInternet Service Providers (ISPs), companies, and universities.Routing within an AS is controlled by intradomain protocolssuch as OSPF, IS–IS, and RIP [1]. ASs interconnect viadedicated links and public network access points, and exchangereachability information using the Border Gateway Protocol(BGP) [2], [3]. BGP is an interdomain routing protocol thatallows ASs to apply local policies for selecting routes andpropagating routing information, without revealing their poli-cies or internal topology to others. However, recent studieshave shown that a collection of ASs may have conflicting BGPpolicies that lead to route divergence [4], [5]. Route divergencecan result in route oscillation, which can significantly degradethe end-to-end performance of the Internet. Avoiding theseconflicting BGP policies is crucial for the stability of the In-ternet routing infrastructure. Yet, to be practical, any techniqueManuscript received September 14, 2000; revised July 1, 2001; recommendedby IEEE/ACM TRANSACTIONS ON NETWORKING Editor K. Calvert. The workof L. Gao was supported in part by the National Science Foundation underGrants ANI-9977555 and ANI-0085848, and NSF CAREER Award Grant ANI-9875513.L. Gao is with the Department of Electrical and Computer Engineering, Uni-versity of Massachusetts, Amherst, MA 01003 USA (e-mail: [email protected]).J.RexfordiswiththeInternetandNetworking SystemsCenter, AT&T Labs—Research, Florham Park, NJ 07932 USA (e-mail: [email protected]).Publisher Item Identifier S 1063-6692(01)10544-3.for ensuring convergence should not sacrifice the ability ofeach AS to apply complex local policies.A natural approach to the route convergence problem involvesthe use of the Internet Routing Registry, a repository of routingpolicies specified in a standard language [6]. A complete andup-to-date registry could check if the set of routing policies hasany potential convergence problems. However, this global coor-dination effort faces several impediments. First, many ISPs maybe unwilling to reveal their local policies to others, and may notkeep the registry up-to-date. Second, and perhaps more impor-tantly, even if ISPs decide to reveal their local polices, recentwork has shown that statically checking for convergence prop-erties is an NP-complete problem [4]. Third, even if the registrycould ensure convergent routes under a given topology, BGPstill might not converge under router or link failures, or a policychange. Hence, rather than requiring global coordination, webelieve that convergence should be achieved by restricting theset of policies that each AS can apply. In this paper, we pro-pose a set of guidelines for an AS to follow in setting its routingpolicies, without requiring coordination with other ASs [7]. Inaddition, the guidelines ensure routing convergence even underchanges in the underlying topology (e.g., router or link failure)or the routing policies.Our approach capitalizes on the Internet’s hierarchical struc-ture and the commercial relationships between ASs. These rela-tionships include customer–provider, peer-to-peer, and backup[8], [9]. A customer pays its provider for connectivity to therest of the Internet, whereas peers agree to exchange traffic be-tween their respective customers free of charge; an AS may alsoprovide backup connectivity to the Internet in the event of afailure. To ensure route convergence, we impose a partial orderon the set of routes to each destination. Under our guidelines,routing via a peer or a provider is never preferable to routingvia a customer link; furthermore, routes via backup links havethe lowest preference. An AS is free to apply any local poli-cies to the routes learned from neighbors within each prefer-ence class. These guidelines conform to conventional traffic-en-gineering practices of ISPs, and this might well explain why In-ternet routing divergence has not occurred yet. However, it iscrucial to make these guidelines explicit since BGP itself doesnot constrain routing policies to ensure convergence. Based onour results, we propose a simple routing registry that stores onlytherelationship between each AS pair, rather than the entire setof routing policies. These relationships can be explicitly regis-tered by the ASs or inferred from the BGP routing tables avail-able throughout the Internet [10], [11].The remainder of the paper is structured as follows. Sec-tion II presents an overview of interdomain routing and dis-cusses previous work on BGP protocol dynamics. Then, Sec-tion III presents a formal model of BGP that includes ASs with1063–6692/01$10.00 © 2001 IEEE682 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 9, NO. 6, DECEMBER 2001multiple BGP speakers, both interior BGP (iBGP) and exte-rior BGP (eBGP), and additional BGP attributes.