Using Repeated Games to Design Incentive-Based Routing Systems

  • Michael Afergan
  • Published 2006 in Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications

Abstract

Incorporating pricing information in routing systems has been explored in various contexts and fashions. In this paper we examine certain fundamental properties important in the design of such a routing protocol. The importance of these properties is derived from the underlying economic factors governing the behavior of the autonomous players. We view the exchange of pricing information at an interconnect as a repeated game between the relevant players. For example, multiple ISPs competing for the business of a CDN. With this model, we see that various protocol parameters—such as protocol period, minimum bid size, and unit of measure— have a significant and important impact on the equilibrium outcome. We show how these parameters can be used to address the problem of the repeated dynamic and further that these conclusions are robust to a variety of practical assumptions including asynchronous play and heterogeneous networks. These often surprising results enable protocol designers to appreciate and leverage these seemingly benign parameters, a result that has direct practical importance.

Topics

7 Figures and Tables

Download Full PDF Version (Non-Commercial Use)