Routing and peering in a competitive Internet

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.