R. Johari and J. Tsitsiklis, "Routing and Peering in a Competitive Internet" January 2003.
|Routing and Peering in a Competitive Internet|
|Abstract:||Today's Internet is a loose federation of independent network providers, each acting in their own self interest. In this paper, we consider some implications of this economic reality. Specifically, we consider how the incentives of the providers might determine where they choose to interconnect with each other; we show that for any given provider, determining an optimal placement of interconnection links is generally NP-complete. However, we present simple solutions for some special cases of this placement problem. We also consider the phenomenon of nearest-exit, or "hot-potato," routing, where outgoing traffic exits a provider's network as quickly as possible. If each link in a network is assessed a linear cost per unit flow through the link, we show that the total cost of nearest exit routing is no worse than three times the optimal cost. In the general case, with nonlinear cost functions, we consider allowing providers to charge each other for flow on their links. We study the efficiency of such a scheme, and arrive at bounds on the worst possible efficiency loss.|