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 based on 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 benefits come 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: 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
• 2: [2] E. Altman, T. Boulogne, R. E. Azouzi, and T. Jimenez, "A survey on networking games," Telecommun. Syst., Nov. 2000.
• 3: 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
• 4: [4] D. O. Awduche, "MPLS and traffic engineering in IP networks," IEEE Commun. Mag., vol. 37, no. 12, pp. 42-47, Dec. 1999.
• 5: I. Castineyra , N. Chiappa , M. Steenstrup, The Nimrod Routing Architecture, RFC Editor, 1996
• 6: 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 ]
• 7: [7] R. Cole, Y. Dodis, and T. Roughgarden, "Pricing networks with selfish routing," presented at the 2nd Workshop on Economics of Peer-to-Peer Systems, Cambridge, MA, Jun. 2004.
• 8: Pradeep Dubey, Inefficiency of Nash equilibria, Mathematics of Operations Research, v.11 n.1, p.1-8, Feb. 1986
• 9: 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
• 10: 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]
• 11: [11] L. Fleischer, K. Jain, and M. Mahdian, "Taxes for heterogeneous selfish users in a multicommodity network," presented at the Foundations of Computer Science (FOCS), Rome, Italy, Oct. 2004.
• 12: [12] M. Florian and D. Hearn, "Network equilibrium models and algorithms," in Network Routing. New York: Elsevier Science, 1995.
• 13: [13] B. Fortz, J. Rexford, and M. Thorup, "Traffic engineering with traditional IP routing protocols," IEEE Commun. Mag., vol. 40, no. 10, pp. 118-124, Oct. 2002.
• 14: [14] B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, Mar. 2000, pp. 519-528.
• 15: [15] E. Friedman, " Genericity and congestion control in selfish routing," in Proc. 43rd IEEE Conf. Decision and Control, 2004, pp. 4667-4672.
• 16: 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]
• 17: Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
• 18: 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]
• 19: [19] S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot, "An approach to alleviate link overload as observed on an IP backbone," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 406-416.
• 20: George Karakostas , Stavros G. Kolliopoulos, Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.268-276, October 17-19, 2004 [doi>10.1109/FOCS.2004.26]
• 21: [21] R. Keralapura, N. Taft, C. Chuah, and G. Iannaconne, "Can ISPs take the heat from overlay networks?," presented at the ACM HotNets-III Workshop, San Diego, CA, Nov. 2004.
• 22: [22] Y. A. Korilis, A. A. Lazar, and A. Orda, "Architecting noncooperative networks," IEEE J. Sel. Areas Commun., vol. 13, no. 7, pp. 1241-1251, Sep. 1995.
• 23: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 24: [24] E. Koutsoupias and C. Papadimitriou, "Worst-case equilibria," in Proc. 16th Annu. Symp. Theoretical Aspects of Computer Science, 1999, pp. 404-413.
• 25: [25] J. B. Krawczyk and S. Berridge, "Relaxation algorithms in finding Nash equilibria," Computational Economics from Economics Working Paper Archive at WUSTL, Jul. 1997.
• 26: V. S. Anil Kumar , Madhav V. Marathe, Improved Results for Stackelberg Scheduling Strategies, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.776-787, July 08-13, 2002
• 27: [27] Y. Liu, H. Zhang, W. Gong, and D. Towsley, " On the interaction between overlay routing and underlay routing," in Proc. IEEE INFOCOM , Mar. 2005, pp. 2543-2553.
• 28: Z. Morley Mao , Lili Qiu , Jia Wang , Yin Zhang, On AS-level path inference, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 29: [29] A. Medina, A. Lakhina, I. Matta, and J. Byers, BRITE: Boston University Representative Internet Topology Generator. [Online]. Available: http://www.cs.bu.edu/brite
• 30: [30] The Network Simulator: ns-2. [Online]. Available: http://www.isi.edu/ nsnam/ns/
• 31: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 32: [32] Rocketfuel. Pop-Level ISP Maps. [Online]. Available: http://www.cs. washington.edu/research/networking/rocketfuel/maps/policy-dist. tar.gz
• 33: Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece [doi>10.1145/380752.380783]
• 34: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, 2002
• 35: 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]
• 36: 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
• 37: [37] Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Englewood Cliffs, NJ: Prentice-Hall, 1985.
• 38: 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
• 39: [39] L. Subrmanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, New York, NY, Jun. 2002, pp. 618-627.
• 40: 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
• 41: [41] H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin, "The impact of routing policy on Internet paths," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 736-742.
• 42: [42] S. Uryas'ev and R. Y. Rubinstein, "On relaxation algorithms in computation of noncooperative equilibria," IEEE Trans. Autom. Contr., vol. 39, no. 6, pp. 1263-1267, Jun. 1995.
• 43: [43] X. Xiao, A. Hannan, B. Bailey, and L. Ni, "Traffic engineering with MPLS in the Internet," IEEE Network Mag., vol. 14, no. 2, pp. 28-33, Mar.-Apr. 2000.
• 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.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Management, Performance

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