On cooperative settlement between content, transit and eyeball internet service providers

ABSTRACT

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the "network neutrality" debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the revenue model, selfish ISPs would yield globally optimal routing and interconnecting decisions.

In this paper, we use a more detailed and realistic network model with three classes of ISPs: content, transit, and eyeball. This additional detail enables us to delve much deeper into the implications of a Shapley settlement mechanism. We derive closed-form Shapley values for more structured ISP topologies and develop a dynamic programming procedure to compute the Shapley revenues under more diverse Internet topologies. We also identify the implications on the bilateral compensation between ISPs and the pricing structures for differentiated services. In practice, these results provide guidelines for solving disputes between ISPs and for establishing regulatory protocols for differentiated services and the industry.

REFERENCES

• 1: Joseph P. Bailey, The economics of Internet interconnection agreements, Internet economics, MIT Press, Cambridge, MA, 1997
• 2: Giuseppe Di Battista , Thomas Erlebach , Alexander Hall , Maurizio Patrignani , Maurizio Pizzonia , Thomas Schank, Computing the types of the relationships between autonomous systems, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.267-280, April 2007 [doi>10.1109/TNET.2007.892878]
• 3: Jon Crowcroft, Net neutrality: the technical side of the debate: a white paper, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198263]
• 4: G. Demange and M. Wooders. Group formation in economics: networks, clubs, and coalitions. Cambridge University Press, Cambridge, 2005.
• 5: P. Faratin, D. Clark, P. Gilmore, S. Bauer, A. Berger, and W. Lehr. Complexity of Internet interconnections: Technology, incentives and implications for policy. The 35th Research Conference on Communication, Information and Internet Policy (TPRC), 2007.
• 6: R. Frieden. Without public peer: the potential regulatory and universal service consequences of Internet Balkanization. Virginia Journal of Law and Technology, 3, 1998.
• 7: R. Frieden. Network neutrality or bias? -- handicapping the odds for a tiered and branded Internet, 2006.
• 8: 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]
• 9: Geoff Huston, ISP survival guide: strategies for running a competitive ISP, John Wiley & Sons, Inc., New York, NY, 1998
• 10: M. O. Jackson. Allocation rules for network games. Game Theory and Information from EconWPA, 2003.
• 11: M. Jamison and J. Hauge. Getting what you pay for: Analyzing the net neutrality debate. University of Florida, Department of Economics, PURC Working Paper, 2007.
• 12: Richard T. B. Ma , Dah ming Chiu , John C. S. Lui , Vishal Misra , Dan Rubenstein, Internet economics: the use of Shapley value for ISP settlement, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York [doi>10.1145/1364654.1364662]
• 13: Richard T.B. Ma , Dah-ming Chiu , John C. S. Lui , Vishal Misra , Dan Rubenstein, Interconnecting eyeballs to content: a shapley value perspective on isp peering and settlement, Proceedings of the 3rd international workshop on Economics of networked systems, August 22-22, 2008, Seattle, WA, USA [doi>10.1145/1403027.1403041]
• 14: R. T. B. Ma, D. M. Chiu, J. C. Lui, V. Misra, and D. Rubenstein. The Shapley revenue for content, transit and eyeball ISPs. technical report, Columbia University, EE Department, July 2008. {Online}Available: http://dna-pubs.cs.columbia.edu/citation/paperfile/169/tech08.pdf.
• 15: Richard T. B. Ma , Sam C. M. Lee , John C. S. Lui , David K. Y. Yau, Incentive and service differentiation in P2P networks: a game theoretic approach, IEEE/ACM Transactions on Networking (TON), v.14 n.5, p.978-991, October 2006 [doi>10.1109/TNET.2006.882904]
• 16: P. Mahadevan, D. Krioukov, M. Fomenkov, B. Huffaker, X. Dimitropoulos, kc claffy, and A. Vahdat. Lessons from three views of the Internet topology. CAIDA report, 2005.
• 17: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic theory. Oxford University Press, 1995.
• 18: J. Musacchio, G. Schwartz, and J. Walrand. Network neutrality and provider investment incentives. Asilomar Conference, pages 1437--1444, November 2007.
• 19: M. J. Osborne and A. Rubinstein. A course in game theory. The MIT Press Cambridge, Massachusetts, 1994.
• 20: A. Roth. The Shapley value: Essays in honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, 1988.
• 21: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 22: S. Shakkottai and R. Srikant. Economics of network pricing with multiple ISPs. In Proceedings of IEEE Infocom, 2005.
• 23: L. Shapley. Cores of convex games. International Journal of Game Theory, 1: 11--26, 1971.
• 24: E. Winter. The Shapley Value, in The Handbook of Game Theory. R. J. Aumann and S. Hart, North-Holland, 2002.
• 25: T. Wu. Network neutrality, broadband discrimination. Journal of Telecommunications and High Technology Law, 141, 2005.

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)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

General Terms:
Design, Documentation