On large-scale peer-to-peer streaming systems with network coding

ABSTRACT

Live peer-to-peer (P2P) streaming has recently received much research attention, with successful commercial systems showing its viability in the Internet. Nevertheless, existing analytical studies of P2P streaming systems have failed to mathematically investigate and understand their critical properties, especially with a large scale and under extreme dynamics such as a flash crowd scenario. Even more importantly, there exists no prior analytical work that focuses on an entirely new way of designing streaming protocols, with the help of network coding. In this paper, we seek to show an in-depth analytical understanding of fundamental properties of P2P streaming systems, with a particular spotlight on the benefits of network coding. We show that, if network coding is used according to certain design principles, provably good performance can be guaranteed, with respect to high playback qualities, short initial buffering delays, resilience to peer dynamics, as well as minimal bandwidth costs on dedicated streaming servers. Our results are obtained with mathematical rigor, but without sacrificing realistic assumptions of system scale, peer dynamics, and upload capacities. For further insights, streaming systems using network coding are compared with traditional pull-based streaming in large-scale simulations, with a focus on fundamentals, rather than protocol details. The scale of our simulations throughout this paper exceeds 200,000 peers at times, which is in sharp contrast with existing empirical studies, typically with a few hundred peers involved.

REFERENCES

• 1: Siddhartha Annapureddy , Saikat Guha , Christos Gkantsidis , Dinan Gunawardena , Pablo Rodriguez Rodriguez, Is high-quality vod feasible using P2P swarming?, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242694]
• 2: Thomas Bonald , Laurent Massoulié , Fabien Mathieu , Diego Perino , Andrew Twigg, Epidemic live streaming: optimal performance trade-offs, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 3: H.-C. Chi and Q. Zhang. Deadline-aware network coding for video on demand service over P2P networks. J. of Zhejiang Univ. Science A, 2006.
• 4: Supratim Deb , Muriel Médard , Clifford Choute, Algebraic gossip: a network coding approach to optimal multiple rumor mongering, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2486-2507, June 2006 [doi>10.1109/TIT.2006.874532]
• 5: S. N. Ethier and T. G. Kurtz. Markov Processes: Characterization and Convergence. Wiley, New York, 1986.
• 6: 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
• 7: T. Ho and R. Koetter and M. Medard and M. Effros and J. Shi and D. Karger. A Random Linear Network Coding Approach to Multicast. IEEE Transactions on Information Theory, October 2006.
• 8: R. Kumar and Y. Liu and K. W. Ross. Stochastic Fluid Theory for P2P Streaming Systems. In Proc. of IEEE INFOCOM, 2007.
• 9: T. G. Kurtz. Approximation of Population Processes. CBMS-NSF Regional Conf. Series in Applied Math, 1981.
• 10: T. Lindvall. Lectures on the Coupling Method. Wiley, New York, 1992.
• 11: Shao Liu , Rui Zhang-Shen , Wenjie Jiang , Jennifer Rexford , Mung Chiang, Performance bounds for peer-assisted live streaming, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 12: Yong Liu, On the minimum delay peer-to-peer video streaming: how realtime can it be?, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291259]
• 13: L. Massoulie and A. Twigg and C. Gkantsidis and P. Rodriguez. Randomized Decentralized Broadcasting Algorithms. In Proc. of IEEE INFOCOM, 2007.
• 14: Vidhyashankar Venkataraman , Kaouru Yoshida , Paul Francis, Chunkyspread: Heterogeneous Unstructured Tree-Based Peer-to-Peer Multicast, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.2-11, November 12-15, 2006 [doi>10.1109/ICNP.2006.320193]
• 15: M. Wang and B. Li. Lava: A Reality Check of Network Coding in Peer-to-Peer Live Streaming. In Proc. of IEEE INFOCOM, 2007.
• 16: M. Wang and B. Li. R2: Random Push with Random Network Coding in Live Peer-to-Peer Streaming. IEEE J. on Sel. Areas in Communications, December 2007.
• 17: M. Zhang and Q. Zhang and L. Sun and S. Yang. Understanding the Power of Pull-based Streaming Protocol: Can We Do Better? IEEE J. on Sel. Areas in Communications, December 2007.
• 18: X. Zhang and J. Liu and B. Li and T.-S. P. Yum. CoolStreaming/DONet: A Data-Driven Overlay Network for Efficient Live Media Streaming. In Proc. of IEEE INFOCOM, 2005.
• 19: Y. Zhou and D. M. Chiu and J. C. S. Lui. A Simple Model for Analyzing P2P Streaming Protocols. In Proc. of IEEE International Conference on Network Protocols (ICNP), 2007.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Design, Performance

Keywords:
network coding, peer-to-peer streaming, performance analysis