Cooperative content distribution and traffic engineering in an ISP network

ABSTRACT

Traditionally, Internet Service Providers (ISPs) make profit by providing Internet connectivity, while content providers (CPs) play the more lucrative role of delivering content to users. As network connectivity is increasingly a commodity, ISPs have a strong incentive to offer content to their subscribers by deploying their own content distribution infrastructure. Providing content services in an ISP network presents new opportunities for coordination between traffic engineering (to select efficient routes for the traffic) and server selection (to match servers with subscribers). In this work, we develop a mathematical framework that considers three models with an increasing amount of cooperation between the ISP and the CP. We show that separating server selection and traffic engineering leads to sub-optimal equilibria, even when the CP is given accurate and timely information about the ISP's network in a partial cooperation. More surprisingly, extra visibility may result in a less efficient outcome and such performance degradation can be unbounded. Leveraging ideas from cooperative game theory, we propose an architecture based on the concept of Nash bargaining solution. Simulations on realistic backbone topologies are performed to quantify the performance differences among the three models. Our results apply both when a network provider attempts to provide content, and when separate ISP and CP entities wish to cooperate. This study is a step toward a systematic understanding of the interactions between those who provide and operate networks and those who generate and distribute content.

REFERENCES

• 1: W.B. Norton, "Video Internet: The Next Wave of Massive Disruption to the U.S. Peering Ecosystem," Sept 2006. Eqinix white paper.
• 2: AT&T, "U-verse." http://uverse.att.com/.
• 3: Verizon, "FiOS." http://www.Verizon.com/fios/.
• 4: Ao-Jan Su , David R. Choffnes , Aleksandar Kuzmanovic , Fabián E. Bustamante, Drafting behind Akamai (travelocity-based detouring), Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 5: Vinay Aggarwal , Anja Feldmann , Christian Scheideler, Can ISPS and P2P users cooperate for improved performance?, ACM SIGCOMM Computer Communication Review, v.37 n.3, July 2007 [doi>10.1145/1273445.1273449]
• 6: Haiyong Xie , Y. Richard Yang , Arvind Krishnamurthy , Yanbin Grace Liu , Abraham Silberschatz, P4p: provider portal for applications, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 7: David R. Choffnes , Fabián E. Bustamante, Taming the torrent: a practical approach to reducing cross-isp traffic in peer-to-peer systems, ACM SIGCOMM Computer Communication Review, v.38 n.4, October 2008
• 8: D. DiPalantino and R. Johari, "Traffic engineering versus content distribution: A game theoretic perspective," in Proc. IEEE INFOCOM, 2009.
• 9: J.F. Nash, "The bargaining problem," Econometrica, vol. 28, pp. 155--162, 1950.
• 10: D.P. Palomar and M. Chiang, "A tutorial on decomposition methods for network utility maximization," IEEE J. on Selected Areas in Communications, vol. 24, no. 8, pp. 1439--1451, 2006.
• 11: B. Fortz and M. Thorup, "Internet traffic engineering by optimizing OSPF weights," in Proc. IEEE INFOCOM, pp. 519--528, 2000.
• 12: D. Awduche , J. Malcolm , J. Agogbua , M. O'Dell , J. McManus, Requirements for Traffic Engineering Over MPLS, RFC Editor, 1999
• 13: D. Xu, M. Chiang, and J. Rexford, "Like-state routing with hop-by-hop forwarding can achieve optimal traffic engineering," in Proc. IEEE INFOCOM, 2008.
• 14: J. Wardrop, "Some theoretical aspects of road traffic research," the Institute of Civil Engineers, vol. 1, no. 2, pp. 325--378, 1952.
• 15: 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]
• 16: 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]
• 17: Michael Littman , Justin Boyan, A Distributed Reinforcement Learning Scheme for Network Routing, Carnegie Mellon University, Pittsburgh, PA, 1993
• 18: W. Jiang, R. Zhang--Shen, J. Rexford, and M. Chiang, "Cooperative content distribution and traffic engineering in a provider network," Tech. Rep. TR--846--08, Department of Computer Science, Princeton University, 2008.
• 19: M. J. Osborne and A. Rubinstein, A Course in Game Theory. MIT Press, 1999.
• 20: K. Binmore, A. Rubinstein, and A. Wolinsky, "The Nash bargaining solution in economic modelling," RAND Journal of Economics, vol. 17, pp. 176---188, 1986.
• 21: Jiayue He , Rui Zhang-Shen , Ying Li , Cheng-Yen Lee , Jennifer Rexford , Mung Chiang, DaVinci: dynamically adaptive virtual networks for a customized internet, Proceedings of the 2008 ACM CoNEXT Conference, p.1-12, December 09-12, 2008, Madrid, Spain [doi>10.1145/1544012.1544027]
• 22: D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.
• 23: Neil Spring , Ratul Mahajan , David Wetherall , Thomas Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.2-16, February 2004 [doi>10.1109/TNET.2003.822655]
• 24: "Abilene." http://www.internet2.edu.
• 25: Matthew Roughan , Mikkel Thorup , Yin Zhang, Performance of estimated traffic matrices in traffic engineering, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
• 26: Wenjie Jiang , Rui Zhang-Shen , Jennifer Rexford , Mung Chiang, Cooperative content distribution and traffic engineering, Proceedings of the 3rd international workshop on Economics of networked systems, August 22-22, 2008, Seattle, WA, USA [doi>10.1145/1403027.1403030]
• 27: Wenjie Jiang , Dah-Ming Chiu , John C. S. Lui, On the interaction of multiple overlay routing, Performance Evaluation, v.62 n.1-4, p.229-246, October 2005 [doi>10.1016/j.peva.2005.07.005]
• 28: Sam C. M. Lee , Joe W. J. Jiang , Dah-Ming Chiu Chiu , John C. S. Lui, Interaction of ISPs: Distributed Resource Allocation and Revenue Maximization, IEEE Transactions on Parallel and Distributed Systems, v.19 n.2, p.204-218, February 2008 [doi>10.1109/TPDS.2007.70714]
• 29: G. Shrimali, A. Akella, and A. Mutapcic, "Cooperative interdomain traffic engineering using Nash bargaining and decomposition," in Proc. IEEE INFOCOM, 2007.
• 30: M. J. Freedman, C. Aperjis, and R. Johari, "Prices are right: Managing resources and incentives in peer--assisted content distribution," in IPTPS 08, February 2008.
• 31: Y. Liu, H. Zhang, W. Gong, and D. Towsley, "On the interaction between overlay routing and underlay routing," in Proc. IEEE INFOCOM, pp. 2543---2553, 2005.
• 32: Richard T. B. Ma , Dah-ming Chiu , John C. S. Lui , Vishal Misra , Dan Rubenstein, On cooperative settlement between content, transit and eyeball internet service providers, Proceedings of the 2008 ACM CoNEXT Conference, p.1-12, December 09-12, 2008, Madrid, Spain [doi>10.1145/1544012.1544019]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Economics, Performance

Keywords:
content distribution, game, internet, traffic engineering