Inefficiency in provisioning interconnected communication networks

ABSTRACT

We model the Internet as a collection of Internet Service Providers (ISPs) that transit and peer to meet an exogenous demand for the transport of IP traffic among an arbitrary set of cities. The prices of bandwidth and of transit are also exogenous. ISPs are assumed to behave rationally and selfishly and therefore they provision the network that maximizes their own profit regardless of how expensive the overall network becomes. We call optimal to a network that ISPs would build if they cooperated to reduce overall provisioning costs; and we call inefficiency cost the additional cost to provision a network at Nash equilibrium relative to the provisioning cost of an optimal network. We show that inefficiency cost is primarily related to transit agreements. In fact, in a world where only peering agreements exist there is no inefficiency cost. However, networks with only peering agreements forgo the efficiencies of traffic aggregation. Transit agreements help reduce provisioning costs by realizing benefits from economies of scale. We show, by example, that there exist Nash networks that are strictly more expensive than optimal networks even when ISPs choose transit prices and therefore the market to provision communication networks with interconnection agreements designed they way the are today is inefficient. We show that inefficiency cost may be reduced, for example, by enforcing side payments between ISPs. We conclude with an analysis of the difficulties a regulator would face in endeavoring to move a market from am inefficient Nash equilibrium to optimality.

REFERENCES

• 1: T. Bates, E. Gerich, L. Joncheray, J. Jouanigot, D. Karrengerg, M. Terpstra, and J. Yu. Representation of IP Routing Policies in a Routing Registry. RFC 1786, 1995.
• 2: M. Beckmann, C. McGuire, and C. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
• 3: D. Braess. Uber ein Paradoxon der Verkehrsplanung. Unternehmensforschung, 12:258--268, 1968. available from http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/.
• 4: R. Coase. The Problem of Social Cost. Journal of Law and Economics, 1:1--44, 1960.
• 5: G. Cook. Peering, Transit and IXs: Economics and Policy. available at www.cookreport.com, November 2002.
• 6: J. Correa, A. Schulz, and N. Stier. Selfish Routing in Capacitated Networks. In INFORMS Annual Meeting, October 2003. Atlanta, Georgia.
• 7: P. Ferreira. Interconnected Communication Networks Provisioned Selfishly. Phd dissertation, Carnegie Mellon University, 2004.
• 8: P. Ferreira, J. Mindel, and L. McKnight. Why Bandwidth Trading Markets Have not Matured? Analysis of Technological and Market Issues. International Journal of Technology, Management and Policy, 2, 2004.
• 9: P. Ferreira and M. Sirbu. The Inefficiency of Markets for Provisioning Communication Networks. In 32nd Annual Telecommunication Policy Research Conference, October 1-3, Arlington, VA 2004. School of Law, George Mason University.
• 10: P. Ferreira and M. Sirbu. The Price of Anarchy for Interconnected Communication Networks Provisioned Selfishly. In Conference on Competition in Networks: Wired and Wireless, May 2004. London Business School, London, UK.
• 11: E. Friedman. A Generic Analysis of Selfish Routing. Working Paper, available at http://www.orie.cornell.edu/ friedman/papers.htm, 2001.
• 12: Sam Halabi , Danny McPherson, Internet Routing Architectures, Second Edition, Cisco Systems, 2000
• 13: A. Haurie and P. Marcotte. On the relationship between Nash-Cournot and Wardrop equilibria. Networks, 15:295--308, 1985.
• 14: A. Haurie and P. Marcotte. A Game-theoretic Approach to Network Equilibrium. Mathematical Programming Study, 26:252--255, 1986.
• 15: J. Hawkison and T. Bates. Guidelines for Creation, Selection and Registration of an Autonomous System (AS). RFC 1930, 1996.
• 16: Geoff Huston, ISP survival guide: strategies for running a competitive ISP, John Wiley & Sons, Inc., New York, NY, 1998
• 17: Ramesh Johari , John N. Tsitsiklis, Efficiency loss in market mechanisms for resource allocation, 2004
• 18: Ramesh Johari , John N. Tsitsiklis, Efficiency Loss in a Network Resource Allocation Game, Mathematics of Operations Research, v.29 n.3, p.407-435, August 2004 [doi>10.1287/moor.1040.0091]
• 19: M. Kende. The Digital Handshake: Connecting Internet Backbones. Working Paper 32, Office of Plans and Policy, Federal Communications Commission, FCC, September 2000.
• 20: E. Koutsoupias and C. Papadimitriou. Worst-case Equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, 1999.
• 21: J. Marcus. Global Traffic Exchange Among Internet Service Providers (ISPs). In OECD - Internet Traffic Exchange, June 2001. Berlin, Germany.
• 22: A. Mas-Colell, M. Whiston, and J. Green. Microeconomic Theory. Oxford University Press, 1995.
• 23: T. McGarty. Peering, Transit and Interconnection: Internet Access in Central Europe. MIT Internet Telephony Consortium, Working Paper, January 2002.
• 24: J. Nash. Non-cooperative Games. Annals of Mathematics, 54(2):286--295, 1951.
• 25: W. Norton. Interconnection Strategies for ISPs. White Paper, Equinix, 1999.
• 26: W. Norton. Internet Service Providers and Peering. White Paper, Equinix, 1999.
• 27: M. O'Kelly and T. Grubesic. Backbone Topology, Access and the Commercial Internet: 1997-2000. Environmental and Planning B, 29:533--552, 2002.
• 28: C. Pigou. The Economics of Welfare. Macmillan, 1920.
• 29: J. Postel. The Transport Control Protocol(TCP). RFC 793, 1985.
• 30: 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]
• 31: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001
• 32: Tim Roughgarden, The Price of Anarchy with Polynomial Edge Latency, Cornell University, Ithaca, NY, 2001
• 33: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, 2002
• 34: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 35: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 36: Telegeography. Light Reading, September 2004.
• 37: Telegeography. Light Reading, August 2004.
• 38: Telegeography. Annual Traffic Report., 2004.
• 39: J. Wardrop. Some Theoretical Aspects of Road Traffic Research. In Institute of Civil Engineers, volume 1, pages 325--378, 1952. Part II.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Economics, Theory

Keywords:
Cost of Anarchy, peering, provisioning networks, transit