On Selfish Routing in Internet-Like Environments
Title | On Selfish Routing in Internet-Like Environments |
Publication Type | Conference Paper |
Year of Publication | 2003 |
Authors | Qiu, L., Yang Y. Richard, Zhang Y., & Shenker S. J. |
Published in | Proceedings of ACM Special Interest Group on Data Communications Conference (SIGCOMM) |
Page(s) | 151-162 |
Other Numbers | 198 |
Abstract | A recent trend in routing research is to avoid inefficiencies in network-level routing by allowing hosts to either choose routes themselves (e.g., source routing) or use overlay routing networks (e.g., Detour or RON). Such approaches result in selfish routing, because routing decisions are no longer based on system-wide criteria but are instead designed to optimize host-based or overlay-based metrics. A series of theoretical results showing that selfish routing can result in suboptimal system behavior have cast doubts on this approach. In this paper, we use a game-theoretic approach to investigate the performance of selfish routing in Internet-like environments. We focus on intra-domain network environments and use realistic topologies and traffic demands in our simulations. We show that in contrast to theoretical worst cases, selfish routing achieves close to optimal average latency in such environments. However, such performance benefit comes at the expense of significantly increased congestion on certain links. Moreover, the adaptive nature of selfish overlays can significantly reduce the effectiveness of traffic engineering by making network traffic less predictable. |
Acknowledgment | This work was partially supported by funding provided to ICSI and its researchers through National Science Foundation grants ANI: 0196514 (originally 9730162, "Learning and the Design of the Internet"); CNS: 0081698 ("Analysis of Internet Algorithms: Optimization, Game Theory, and Competitive Analysis"); CCF: 0121555 ("Discrete Models and Algorithms in the Sciences"); CNS: 0207399 ("Incentive-Compatible Designs for Distributed Systems"); CNS: 0205519 ("Addressing Fundamental Issues for Robust Internet Performance"); and CNS: 0225660 ("Robust Large-Scale Distributed Systems"). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation. |
URL | http://www.icsi.berkeley.edu/pubs/networking/selfishrouting03.pdf |
Bibliographic Notes | Proceedings of ACM Special Interest Group on Data Communications Conference (SIGCOMM), pp. 151-162, Karlsruhe, Germany |
Abbreviated Authors | L. Qiu, Y.R. Yang, Yin Zhang, and S. Shenker |
ICSI Research Group | Networking and Security |
ICSI Publication Type | Article in conference proceedings |