On Selfish Routing in Internet-Like EnvironmentsLili Qiu Yang Richard Yang∗Yin Zhang Scott Shenker†Microsoft Research Yale University AT&T Labs – Research [email protected] [email protected] [email protected] [email protected] recent trend in routing research is to avoidinefficiencies innetwork-level routing by allowing hosts to either choose routes themselves(e.g., source routing) or use overlay routing networks (e.g., Detouror RON). Such approaches result in selfish routing, because routingdecisions are no longer based on system-wide criteria but are in-stead designed to optimize host-based or overlay-based metrics. Aseries of theoretical results showing that selfish routing can result insuboptimal system behavior have cast doubts on this approach. Inthis paper, we use a game-theoretic approach to investigate the per-formance of selfish routing in Internet-like environments. We focuson intra-domain network environments and use realistic topologiesand traffic demands in our simulations. We show that in contrastto theoretical worst cases, selfish routing achieves close to optimalaverage latency in such environments. However, such performancebenefit comes at the expense of significantly increased congestionon certain links. Moreover, the adaptive nature of selfish overlayscan significantly reduce the effectiveness of traffic engineering bymaking network traffic less predictable.Categories and Subject DescriptorsC.2.5 [Computer-Communication Networks]: Local and Wide-Area Networks—InternetGeneral TermsPerformanceKeywordsSelfish Routing, Overlay, Game Theory, Traffic Equilibrium, TrafficEngineering, Optimization, Relaxation1. INTRODUCTIONFor decades, it has been the responsibility of the network to routetraffic. Recent studies [32, 40] have shown that there is inherent in-efficiency in network-level routing from the user’s perspective. Inresponse to these observations, we have seen an emergent trend toallow end hosts to choose routes themselves by using either source∗Supported in part by NSF grant ANI-0207399.†Supported in part by NSF grants ITR-0205519, ANI-0207399, ITR-0121555, ITR-0081698, ITR-0225660 and ANI-0196514.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGCOMM’03, August 25–29, 2003, Karlsruhe, Germany.Copyright 2003 ACM 1-58113-735-4/03/0008 ...$5.00.routing (e.g., Nimrod [8]) or overlay routing (e.g., Detour [32] orRON [5]). These end-to-end route selection schemes are shown tobe effective in addressing some deficiencies in today’s IP routing.For example, measurements [10, 32, 33] from the Detour projectshow that in the Internet, a large percentage of flows can find betteralternative paths by relaying among overlay nodes, thereby improv-ing their performance. RON [5] also demonstrates the benefit ofoverlay routing using real implementation and deployment.Such end-to-end route selection schemes are selfish by nature inthat they allow end users to greedily select routes to optimize theirown performance without considering the system-wide criteria. Re-cent theoretical results suggest that in the worst case selfish routingcan result in serious performance degradation due to lack of cooper-ation. In particular, Roughgarden and Tardos prove that the price ofanarchy (i.e., the worst-case ratio between the total latency of self-ish routing and that of the global optimal) for selfish routing can beunbounded for general latency functions [31].Despite much theoretical advance, an open question is how self-ish routing performs in Internet-like environments. This is a chal-lenging question, since today’s Internet is unique in the followingrespects.First, topologies and traffic demands of the Internet are not ar-bitrary but have certain structures. The worst-case results may notbe applicable to realistic topologies and traffic demands. A generalopen question is whether selfish routing results in bad performancein Internet-like environments (i.e., under realistic network topolo-gies and traffic demands).Second, users in overlay networks do not have full flexibility inspecifying their end-to-end paths. Due to limited availability ofsource routing support in the routers, the path between any twonetwork nodes is dictated by the Internet routing protocols, suchas OSPF [28], MPLS [26], or BGP [37]. While overlay networksprovide another mechanism to enable users to control their routesby relaying through overlay nodes, the route between two overlaynodes is still governed by the underlying routing protocol. A naturalquestion is how to model such selfish overlay routing and whetherselfish overlay routing results in bad performance.Third, even if selfish overlays (i.e., overlays consisting of selfishtraffic) yield good performance, they can only be deployed gradu-ally. As a result, background traffic and overlay traffic will interactwith each other. We call such interactions horizontal interactions.An important question is how such selfish traffic affects the remain-ing traffic routed using the traditional routing protocols. A relatedquestion is whether multiple overlays result in bad performance.Fourth, the way in which selfish users choose their routes can in-teract with traffic engineering. We call such interactions verticalinteractions, which can be viewed as the following iterative pro-cess. First, ISPs adjust network-level routing according to trafficdemands, using schemes in [6, 14, 15, 42], to minimize networkcost. Then selfish users adapt to changes in the underlying defaultroutes by choosing different overlay paths to optimize their end-151to-end performance. Such adaptation changes traffic demands andtriggers traffic engineering to readjust the default routes, which inturn makes selfish users adapt to new routes. Given the mismatchbetween the objectives of selfish routing and traffic engineering, aninteresting question is whether selfish routing interacts badly withtraffic engineering.In this paper, we seek to answer the above questions through ex-tensive simulations. We take a game-theoretic approach to com-pute the traffic equilibria of various routing schemes and then eval-uate their
View Full Document
Unlocking...