|
Abstract : |
The routing of tra#c between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address the problem of interdomain routing from a mechanism-design point of view. The application of mechanism-design principles to the study of routing is the subject of earlier work by Nisan and Ronen [14] and Hershberger and Suri [10]. In this paper, we formulate and solve a version of the routing-mechanism design problem that is di#erent from the previously studied version in three ways that make it more accurately reflective of real-world interdomain routing: (1) we treat the nodes as strategic agents, rather than the links; (2) our mechanism computes lowestcost routes for all source-destination pairs and payments for transit nodes on all of the routes (rather than computing routes and payments for only one source-destination pair at a time, as is done in [14, 10]); (3) we show how to compute our mechanism with a distributed algorithm that is a straightforward extension to BGP and causes only modest, |
