Computer Science Department
School of Computer Science, Carnegie Mellon University


Mechanisms for Internet Routing: A Study

Aditya Akella, Shuchi Chawla, Srini Seshan

July 2002

Keywords: Game theory, mechanism design, load-sensitive routing

In this paper, we address the issue of Routing in the Internet from a Game Theoretic perspective. We adopt a two-pronged strategy: firstly, we revisit two `classic' models of the Nash equilibria of a network of selfish flows in the Internet and extend their results for Nash equilibria to what we believe are more realistic settings (for example, we present results for non-linear latency functions). Secondly, we apply our results as well as the "classic" results for Nash equilibria to designing Routing schemes for networks. The goal of such schemes is not to price network usage but rather to ensure sound overall network performance in the presence of greedy behavior of the participating flows. Finally we show how our results can be employed to build a Wide-Area routing scheme.

12 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by