@Article{feigenbaum05a,
  author =	 {Joan Feigenbaum and Christos Papadimitriou and Rahul
                  Sami and Scott Shenker},
  title =	 {A {BGP}-based mechanism for lowest-cost routing},
  journal =	 {Distributed Computing},
  year =	 2005,
  doi =		 {10.1007/s00446-005-0122-y},
  abstract =	 {The routing of traffic 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
                  [16] and Hershberger and Suri [12]. In this paper,
                  we formulate and solve a version of the
                  routing-mechanism design problem that is different
                  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 lowest-cost routes for
                  all soure-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 [12, 16]); (3) we show
                  how to compute our mechanism with a distributed
                  algorithm that is a straightforward extension to BGP
                  and causes only modest increases in routing-table
                  size and convergence time (in contrast with the
                  centralized algorithms used in [12, 16]). This
                  approach of using an existing protocol as a
                  substrate for distributed computation may prove
                  useful in future development of Internet algorithms
                  generally, not only for routing or pricing
                  problems. Our design and analysis of a
                  strategyproof, BGP-based routing mechanism provides
                  a new, promising direction in distributed
                  algorithmic mechanism design, which has heretofore
                  been focused mainly on multicast cost sharing},
  keywords =     {networks routing},
  url = 	 {http://jmvidal.cse.sc.edu/library/feigenbaum05a.pdf},
  googleid = 	 {Y8fsoNlk1S8J:scholar.google.com/},
  cluster = 	 {3446771975692535651}
}