CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Designing Networking Protocols Using Repeated Games

Michael Afergan

Overview

Consideration of the participants' incentives is vital to building robust networked systems. To do so, application and protocol designers require tools and frameworks that allow them to understand how the decisions made will impact the system. In our research, we use repeated games, a well-understood tool from Game Theory, to provide novel and practical insight for a variety of problems, including inter-domain routing and application overlay networks. These results are not only useful within each problem domain but suggest that repeated games may be an interesting, practical, and important tool for network application and protocol design.

Repeated Games

There are three key reasons why we believe that repeated games are an important tool for networking design.

  • Repetition is an inherent aspect of almost all networked problems. Examples include repeated interactions between commercial networks seeking to obtain more traffic, repeated interactions between users and a given network, or repeated interactions between users and each other in peer-to-peer environment. In most of these applications, users are interested in optimizing their results over a longer horizon. Indeed, many networking protocols seek to optimize performance over longer timescales.
  • Repeated games are a well-understood area of Game Theory. As such, the literature provides us with many of the framework and tools necessary to perform insightful and effective analysis of a variety of these problems. This enables us to use repeated games as an effective descriptive tool -- and to derive practical prescriptive results.
  • The equilibria of repeated games can significantly differ from the equilibria of the particular stage-game. One of the key key conclusions of repeated game theory is that the repeated setting can provide very different, and indeed opposite results from the one-shot game. Therefore, for many networked applications, it is vital that any game theoretic analysis consider the repeated case.

Networking problems not only strongly motivate the consideration of the repeated case, but also have several properties that cause repeated game analysis to be insightful. For example, another conclusion of repeated game theory is that the granularity of the action space can significantly impact the result of the system. Networked applications, by virtue of being wire-based protocols, inherently have a discrete representation space. Further, the distributed nature of most networked applications implies that degree to which players can adapt a protocol in real-time is limited. Dynamically selecting and coordinating an alternative behavior is likely impossible.

Sample Results

With this motivation, our research considers several relevant networking problems using the tools of repeated games. Considering a diverse set of problems, we see that the repeated framework is qualatively more descriptive and insightful that prior models. Further, we see that given an appropriate model, the tools of repeated games are able to provide novel and practical insight into a diverse set of problems.

Inter-domain Routing

There variety of reasons why one might consider more tightly coupling the expression of prices into the routing protocols that are used on the Internet. Although economic considerations dominate the routing decisions made by the profit-maximizing ISPs, prices are not explicit in BGP. The resulting inexact tools create significant manual overhead and increase the chance for error. Further, user-directed routing, such as overlays or multihoming, shifts the balance of power, creating tension between the users and the ASes. This may be best resolved by making the incentives more explicit in the routing system.

Given this motivation, we ask the question. ``How should one design a protocol to convey pricing information for routes?'' Here the customer could be an enterprise, a Content Delivery Network (CDN), or an access ISP. The customer connects to multiple networks via which it may reach its destinations. Our model considers this problem as a repeated game, and as such differs starkly from prior models and thus results in the space, most notably the seminal Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS) model. [1] Examination of our model reveals that unavoidable yet seemingly minor design choices have significant practical effects. For example.

  • A longer protocol period (a slower protocol) can lead to a lower price.
  • Using a more granular format (e.g., megabits instead of megabytes) can lead to a higher price.
  • A wider price field in the protocol can lead to a lower price.

These conclusions have clear, direct, and previously unrecognized practical significance for protocol designers. Further, this understanding helps to resolve the uncertainty and problems presented by the repeated game.

Results in Multicast Application Overlay Trees

Application overlays have been proposed as a way of achieving the benefits of IP multicast, and various protocols exist for creating efficient trees. [2] In practice, the quality experienced by a node decreases as it moves away from the source and also as it supports more children. [3] This poses a challenge for the robustness and in turn the efficiency of these trees.

Repeated games provide an appealing -- and perhaps unique -- framework for analyzing this problem. In a practical environment where we do not have a micro-payment architecture nor an effective identity scheme (as is the case on the Internet), the one-shot game results in the degenerate unicast tree. In our repeated model, users' greed is tempered by their desire for the network to continue to exist. With this model we solve for the equilibrium conditions and simulate the interactions on a network topology. This allows us to determine the relationship of system parameters and protocol behaviors on the network efficiency and maximum size. In turn we are again able to make recommendations for system design.

References

[1] J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker. A BGP-Based Mechanism for Lowest-Cost Routing. In The Proceedings on PODC, Monterey, California, 2002.

[2] S. Banerjee, B. Bhattacharjee, and C. Kommareddy. Scalable Application Layer Multicast. In The Proceedings of ACM SIGCOMM, Pittsburgh, Pennsylvania, 2002.

[3] L. Mathy, N. Blundell, V. Roca, and A. El-Sayed. Impact of Simple Cheating in Application-Level Multicast. In The Proceedings of IEEE Infocom, 2004.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)