A BGP-based Mechanism for Lowest-Cost Routing∗Joan Feigenbaum†Yale UniversityComputer Science DepartmentNew Haven, CT 06520 [email protected] Papadimitriou‡University of California at BerkeleyComputer Science DivisionBerkeley, CA 94720 [email protected] Sami§Yale UniversityComputer Science DepartmentNew Haven, CT 06520 [email protected] Shenker¶ICSI1947 Center StreetBerkeley, CA 94704 [email protected] routing of traffic between Internet domains or Autonom-ous Systems (ASs), a task known as interdomain routing, iscurrently handled by the Border Gateway Protocol (BGP).In this paper, we address the problem of interdomain routingfrom a mechanism-design point of view. The application ofmechanism-design principles to the study of routing is thesubject of earlier work by Nisan and Ronen [14] and Hersh-berger and Suri [10]. In this paper, we formulate and solvea version of the routing-mechanism design problem that isdifferent from the previously studied version in three waysthat make it more accurately reflective of real-world inter-domain routing: (1) we treat the nodes as strategic agents,rather than the links; (2) our mechanism computes lowest-cost routes for all source-destination pairs and payments fortransit nodes on all of the routes (rather than computingroutes and payments for only one source-destination pair ata time, as is done in [14, 10]); (3) we show how to com-pute our mechanism with a distributed algorithm that is astraightforward extension to BGP and causes only modest∗This work was supported by the DoD University ResearchInitiative (URI) program administered by the Office of NavalResearch under Grant N00014-01-1-0795.†Supported in part by ONR grants N00014-01-1-0795 andN00014-01-1-0447 and NSF grant CCR-0105337.‡Supported in part by NSF grants ITR-0081698 and ITR-0121555 and by an IBM Faculty Development Award.§Supported by ONR grant N00014-01-1-0795.¶Supported in part by NSF grants ITR-0081698 and ITR-0121555.increases in routing-table size and convergence time (in con-trast with the centralized algorithms used in [14, 10]). Thisapproach of using an existing protocol as a substrate for dis-tributed computation may prove useful in future developmentof Internet algorithms generally, not only for routing or pric-ing problems. Our design and analysis of a strategyproof,BGP-based routing mechanism provides a new, promising di-rection in distributed algorithmic mechanism design, whichhas heretofore been focused mainly on multicast cost shar-ing.1. INTRODUCTIONThe Internet is comprised of many separate administrativedomains or Autonomous Systems (ASs). Routing occurs ontwo levels, intradomain and interdomain, implemented bytwo different sets of protocols. Intradomain-routing proto-cols, such as OSPF, route packets within a single AS. Inter-domain routing, currently handled by the Border GatewayProtocol (BGP), routes packets between ASs. Althoughrouting is a very well-studied problem, it has been app-roached by computer scientists primarily from an engineer-ing or “protocol-design” perspective.In their seminal paper on algorithmic mechanism design,Nisan and Ronen [14] advocate combining an economic, “inc-entive-compatibility” approach with the more traditionalprotocol-design approach to the problem. Internet rout-ing is an extremely natural problem in which to considerincentives, because ownership, operation, and use by nu-merous independent, self-interested parties give the Internetthe characteristics of an economy as well as those of a com-puter. In this paper, we continue the study of routing froma mechanism-design perspective, concentrating specificallyon interdomain routing, for reasons explained below.In our formulation of the routing-mechanism design prob-lem, each AS incurs a per-packet cost for carrying traffic,where the cost represents the additional load imposed onthe internal AS network by this traffic. To compensate forthese incurred costs, each AS is paid a price for carryingtransit traffic, which is traffic neither originating from nordestined for that AS. It is through these costs and prices thatconsideration of “incentive compatibility” is introduced tothe interdomain-routing framework, which, as currently im-plemented, does not consider incentives. We are followingprevious work on mechanism design for routing [14, 10] byintroducing incentives in this way. Our goal is to maximizenetwork efficiency by routing packets along the lowest-costpaths (LCPs). Standard routing protocols (such as BGP)can compute LCPs given a set of AS costs. However, undermany pricing schemes, an AS could be better off lying aboutits costs;1such lying would cause traffic to take nonoptimalroutes and thereby interfere with overall network efficiency.To prevent this, we first ask how one can set the prices sothat ASs have no incentive to lie about their costs; as wediscuss in Section 2, such pricing schemes are called “strat-egyproof.” We also require that ASs that carry no tran-sit traffic receive no payment. We prove that there is onlyone strategyproof pricing scheme with this property; it is amember of the Vickrey-Clarke-Groves (VCG) class of mech-anisms [21, 2, 9]. We next ask how the VCG prices shouldbe computed, and we provide a “BGP-based” distributedalgorithm that accomplishes this.Our results contribute in several ways to the understand-ing of how incentives and computation affect each other inrouting-protocol design. Nisan and Ronen [14] and Hersh-berger and Suri [10] considered the LCP mechanism-designproblem, motivated in part by the desire to include incen-tive issues in Internet-route selection. The LCP mechanismstudied in [14, 10] takes as input a biconnected graph, a sin-gle source, a single destination, and a (claimed) transmissioncost for each link; the strategic agents are the links, and themechanism computes, in a strategyproof manner, both anLCP for this single routing instance and a set of paymentsto the links on the LCP. This mechanism is a member of theVCG family and forms the point of departure for our work.However, our formulation of the problem differs in three re-spects, each of which makes the problem more representativeof real-world routing:• First, in our formulation, it is the nodes that are thestrategic agents, not the links as in [14, 10]. We makethis choice, because we are trying to model interdo-main routing. ASs actually are independent economicactors
View Full Document
Unlocking...