On selfish routing in internet-like environments

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.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Aditya Akella , Srinivasan Seshan , Richard Karp , Scott Shenker , Christos Papadimitriou, Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 3: E. Altman, R. E. Azouzi, and A. Vyacheslav. Non-cooperative routing in loss networks. In Proceedings of Performance '02, Rome, Italy, Sept. 2002.
• 4: E. Altman, T. Boulogne, R. E. Azouzi, and T. Jimenez. A survey on networking games. Telecommunication Systems, Nov. 2000.
• 5: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 6: D. O. Awduche. MPLS and traffic engineering in IP networks. IEEE Communication Magazine, pages 42--47, Dec. 1999.
• 7: T. Boulogne, E. Altman, O. Pourtallier, and H. Kameda. Mixed equilibrium for multiclass routing games. IEEE Transactions on Automatic Control, 47(6):903--916, Jun. 2002.
• 8: I. Castineyra, N. Chiappa, and M. Steenstrup. The Nimrod Routing Architecture, RFC 1992, Aug. 1996.
• 9: Anthony Chen , Der-Horng Lee , R. Jayakrishnan, Computational study of state-of-the-art path-based traffic assignment algorithms, Mathematics and Computers in Simulation, v.59 n.6, p.509-518, July 2002 [doi>10.1016/S0378-4754(01)00437-2]
• 10: A. Collins. The Detour framework for packet rerouting. PhD Qualifying Examination, Nov. 1998.
• 11: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 13: M. Florian and D. Hearn. Network Routing, chapter 6, Network equilibrium models and algorithms. Elsevier Science, 1995.
• 14: B. Fortz, J. Rexford, and M. Thorup. Traffic engineering with traditional IP routing protocols. IEEE Comm. Magazine, Oct. 2002.
• 15: B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proceedings of IEEE INFOCOM '00, Tel Aviv, Israel, Mar. 2000.
• 16: E. Friedman. Selfish routing on data networks isn't too bad: Genericity, TCP, and OSPF. Working paper. Available from http://www.orie.cornell.edu/~friedman/papers.html, Oct. 2002.
• 17: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 18: Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
• 19: Carl M. Harris , Percy H. Brill , Martin J. Fischer, Internet-Type Queues with Power-Tailed Interarrival Times and Computational Methods for Their Analysis, INFORMS Journal on Computing, v.12 n.4, p.261-271, October 2000 [doi>10.1287/ijoc.12.4.261.11882]
• 20: S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot. An approach to alleviate link overload as observed on an IP backbone. In Proccedings of IEEE INFOCOM '03, San Francisco, CA, Apr. 2003.
• 21: Y. A. Korilis, A. A. Lazar, and A. Orda. Architecting noncooperative networks. IEEE Journal of Selected Areas in Communications, 13(7):1241--1251, Sept. 1995.
• 22: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, 1999.
• 23: J. B. Krawczyk and S. Berridge. Relaxation algorithms in finding Nash equilibria. In Computational Economics from Economics Working Paper Archive at WUSTL, Jul. 1997.
• 24: lp_solve. ftp://ftp.ics.ele.tue.nl/pub/lp_solve/.
• 25: A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: Boston University representative Internet topology generator. Available from http://www.cs.bu.edu/brite.
• 26: Multiprotocol label switching (MPLS). http://www.ietf.org/html.charters/mpls-charter.html.
• 27: The network simulator: ns-2. http://www.isi.edu/nsnam/ns/.
• 28: Open shortest path first (OSPF). http://www.ietf.org/html.charters/ospf-charter.html.
• 29: M. Patriksson. Algorithms for computing traffic equilibria. In Networks and Spatial Economics. 2003. http://www.cs.chalmers.se/~mipat/LATEX/NSE.ps.
• 30: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, 2002
• 31: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 32: Stefan Savage , Thomas Anderson , Amit Aggarwal , David Becker , Neal Cardwell , Andy Collins , Eric Hoffman , John Snell , Amin Vahdat , Geoff Voelker , John Zahorjan, Detour: Informed Internet Routing and Transport, IEEE Micro, v.19 n.1, p.50-59, January 1999 [doi>10.1109/40.748796]
• 33: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 34: Y. Sheffi. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, 1985.
• 35: Scott J. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.819-831, Dec. 1995 [doi>10.1109/90.477727]
• 36: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 37: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 38: L. Subrmanian, S. Agarwal, J. Rexford, and R. Katz. Characterizing the Internet hierarchy from multiple vantage points. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002.
• 39: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 40: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin. The impact of routing policy on Internet paths. In Proceedings of IEEE INFOCOM '01, Anchorage, AK, Apr. 2001.
• 41: S. Uryas'ev and R. Y. Rubinstein. On relaxation algorithms in computation of noncooperative equilibria. IEEE Transactions on Automatic Control, 39(6):1263--1267, Jun. 1995.
• 42: X. Xiao, A. Hannan, B. Bailey, and L. Ni. Traffic engineering with MPLS in the Internet. IEEE Network Magazine, Mar. 2000.
• 43: Ellen W. Zegura , Mostafa H. Ammar , Zongming Fei , Samrat Bhattacharjee, Application-layer anycasting: a server selection architecture and use in a replicated Web service, IEEE/ACM Transactions on Networking (TON), v.8 n.4, p.455-466, Aug. 2000 [doi>10.1109/90.865074]
• 44: Yin Zhang , Matthew Roughan , Nick Duffield , Albert Greenberg, Fast accurate computation of large-scale IP traffic matrices from link loads, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Performance

Keywords:
game theory, optimization, overlay, relaxation, selfish routing, traffic engineering, traffic equilibrium