Designing Networking Protocols Using Repeated GamesMichael AferganOverviewConsideration 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 GamesThere are three key reasons why we believe that repeated games are an important tool for networking design.
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 ResultsWith 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 RoutingThere 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.
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 TreesApplication 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. |
||
|