Exploring large-scale peer-to-peer live streaming topologies

ABSTRACT

Real-world live peer-to-peer (P2P) streaming applications have been successfully deployed in the Internet, delivering live multimedia content to millions of users at any given time. With relative simplicity in design with respect to peer selection and topology construction protocols and without much algorithmic sophistication, current-generation live P2P streaming applications are able to provide users with adequately satisfying viewing experiences. That said, little existing research has provided sufficient insights on the time-varying internal characteristics of peer-to-peer topologies in live streaming. This article presents Magellan, our collaborative work with UUSee Inc., Beijing, China, for exploring and charting graph theoretical properties of practical P2P streaming topologies, gaining important insights in their topological dynamics over a long period of time.

With more than 120 GB worth of traces starting September 2006 from a commercially deployed P2P live streaming system that represents UUSee's core product, we have completed a thorough and in-depth investigation of the topological properties in large-scale live P2P streaming, as well as their evolutionary behavior over time, for example, at different times of the day and in flash crowd scenarios. We seek to explore real-world P2P streaming topologies with respect to their graph theoretical metrics, such as the degree, clustering coefficient, and reciprocity. In addition, we compare our findings with results from existing studies on topological properties of P2P file sharing applications, and present new and unique observations specific to streaming. We have observed that live P2P streaming sessions demonstrate excellent scalability, a high level of reciprocity, a clustering phenomenon in each ISP, and a degree distribution that does not follow the power-law distribution.

REFERENCES

• 1: Adamic, L. A., Lukose, R. M., Puniyani, A. R., and Huberman, B. A. 2001. Search in power-law networks. Phys. Rev. E 64(46135).
• 2: Ali, A., Mathur, A., and Zhang, H. 2006. Measurement of commercial peer-to-peer live video streaming. In Proceedings of the Workshop in Recent Advances in Peer-to-Peer Streaming.
• 3: Baset, S. A. and Schulzrinne, H. 2006. An analysis of the Skype peer-to-peer internet telephony protocol. In Proceedings IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA.
• 4: Kuan-Ta Chen , Chun-Ying Huang , Polly Huang , Chin-Laung Lei, Quantifying Skype user satisfaction, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 5: Cheng, B., Liu, X., Zhang, Z., and Jin, H. 2007. A measurement study of a peer-to-peer video-on-demand system. In Proceedings of the 6th International Workshop on Peer-to-Peer Systems (IPTPS '07).
• 6: Garlaschelli, D. and Loffredo, M. I. 2004. Patterns of link reciprocity in directed networks. Phys. Rev. Lett. 93 ,26.
• 7: Guha, S., Daswani, N., and Jain, R. 2006. An experimental study of the Skype peer-to-peer VoIP system. In Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS '06).
• 8: Krishna P. Gummadi , Richard J. Dunn , Stefan Saroiu , Steven D. Gribble , Henry M. Levy , John Zahorjan, Measurement, modeling, and analysis of a peer-to-peer file-sharing workload, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 9: Lei Guo , Songqing Chen , Zhen Xiao , Enhua Tan , Xiaoning Ding , Xiaodong Zhang, Measurements, analysis, and modeling of BitTorrent-like systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.4-4, October 19-21, 2005, Berkeley, CA
• 10: Hei, X., Liang, C., Liang, J., Liu, Y., and Ross, K. W. 2006. Insight into PPLive: Measurement study of a large scale P2P IPTV system. In Workshop on Internet Protocol TV (IPTV) Services over World Wide Web, in conjunction with WWW 2006.
• 11: Hei, X., Liang, C., Liang, J., Liu, Y., and Ross, K. W. 2007. A measurement study of a large-scale P2P IPTV system. IEEE Trans. Multimed 9, 8 (Dec.) 1672--1687.
• 12: Izal, M., Urvoy-Keller, G., Biersack, E., Felber, P., Hamra, A. A., and Garces-Erice, L. 2004. Dissecting BitTorrent: Five months in a torrent's lifetime. In Proceedings of the 5th Passive and Active Measurement Workshop (PAM '04).
• 13: Jovanovic, M., Annexstein, F., and Berman, K. 2001. Modeling peer-to-peer network topologies through small-world models and power laws. In Proceedings of the IX Telecommunications Forum (TELFOR) (Belgrade).
• 14: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 15: Jian Liang , Rakesh Kumar , Keith W. Ross, The FastTrack overlay: a measurement study, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.6, p.842-858, 13 April 2006 [doi>10.1016/j.comnet.2005.07.014]
• 16: Newman, M. E. J. 2002. Assortative mixing in networks. Phys. Rev. Lett. 89(208701).
• 17: Pouwelse, J., Garbacki, P., Epema, D., and Sips, H. 2005. The BitTorrent P2P file sharing system: Measurements and analysis. In Proceedings of the 4th International Workshop on Peer-to-Peer Systems (IPTPS '05).
• 18: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369]
• 19: Thomas Silverston , Olivier Fourmaux, P2P IPTV measurement: a case study of TVants, Proceedings of the 2006 ACM CoNEXT conference, December 04-07, 2006, Lisboa, Portugal [doi>10.1145/1368436.1368490]
• 20: Silverston, T. and Fourmaux, O. 2007. Measuring P2P IPTV systems. In Proceedings of the 17th International Workshop on Network and Operating Systems Support for Digital Audio & Video (NOSSDAV'07) (to appear).
• 21: Steiner, M., Biersack, E. W., and Ennajjary, T. 2007. Actively monitoring peers in KAD. In Proceedings of the 6th International Workshop on Peer-to-Peer Systems (IPTPS '07).
• 22: Daniel Stutzbach , Reza Rejaie, Understanding churn in peer-to-peer networks, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177105]
• 23: Daniel Stutzbach , Reza Rejaie , Subhabrata Sen, Characterizing unstructured overlay topologies in modern P2P file-sharing systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.5-5, October 19-21, 2005, Berkeley, CA
• 24: UUSee Inc. http://www.uusee.com/.
• 25: Long Vu , Indranil Gupta , Jin Liang , Klara Nahrstedt, Measurement of a large-scale overlay for multimedia streaming, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272410]
• 26: Watts, D. J. 2003. Six Degrees: the Science of a Connected Age. ACM, New York.
• 27: Chuan Wu , Baochun Li , Shuqiao Zhao, Magellan: Charting Large-Scale Peer-to-Peer Live Streaming Topologies, Proceedings of the 27th International Conference on Distributed Computing Systems, p.62, June 25-27, 2007 [doi>10.1109/ICDCS.2007.118]
• 28: Zhang, X., Liu, J., Li, B., and Yum, T. P. 2005. CoolStreaming/DONet: A data-driven overlay network for live media streaming. In Proceedings of IEEE INFOCOM 2005. IEEE Computer Society Press, Los Alamitos, CA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Measurement

Keywords:
Peer-to-peer streaming, topology characterization