Performance bounds for peer-assisted live streaming

Abstract

Peer-assisted streaming is a promising way for service providers to offer high-quality IPTV to consumers at reasonable cost. In peer-assisted streaming, the peers exchange video chunks with one another, and receive additional data from the central server as needed. In this paper, we analyze how to provision resources for the streaming system, in terms of the server capacity, the video quality, and the depth of the distribution trees that deliver the content. We derive the performance bounds for minimum server load, maximum streaming rate, and minimum tree depth under different peer selection constraints. Furthermore, we show that our performance bounds are actually tight, by presenting algorithms for constructing trees that achieve our bounds.

References

1. S. Ali, A. Mathur, and H. Zhang. Measurement of commercial peer-to-peer live video streaming. In Proceedings of the Workshop in Recent Advances in Peer-to-Peer Streaming (WRAIPS), 2006.
2. S. Assmann. Problems in Discrete Applied Mathematics. In PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1983.
3. S. Assmann, D. Johnson, D. Kleitman, and J. Leung. On a Dual Version of the One-Dimensional Bin Packing Problem. Journal of Algorithms, 5:502--525, 1984.
4. M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. Splitstream: High-bandwidth content distribution in a cooperative environment. In ACM SOSP'03, Lake Bolton, New York, October 2003.
5. M. Chen, M. Ponec, S. Sengupta, J. Li, and P. A. Chou. Utility maximization in peer-to-peer systems. In ACM Sigmetrics, 2008.
6. B. Cohen. Incentives Build Robustness in BitTorrent. In First Workshop on the Economics of Peer-to-Peer Systems, 2003.
7. J. Csirik and J. Frenk. A dual version of bin packing. Technical Report 9029-a, Erasmus University of Rotterdam - Econometric Institute, 1990.
8. J. Csirik, J. B. G. Frenk, M. Labbé, and S. Zhang. Two Simple Algorithms for Bin Covering. Acta Cybern., 14(1):13--25, 1999.
9. J. Csirik and V. Totik. Online Algorithms for a Dual Version of Bin Packing. Discrete Appl. Math., 21(2):163--167, 1988.
10. J. Csirik and G. J. Woeginger. On-line Packing and Covering Problems. In Developments from a June 1996 seminar on Online algorithms, pages 147--177, London, UK, 1998. Springer-Verlag.
11. G. Dan, V. Fodor, and I. Chatzidrossos. On the Performance of Multiple-Tree-Based Peer-to-Peer Live Streaming. IEEE INFOCOM, pages 2556--2560, May 2007.
12. M. R. Garey and D. S. Johnson. "Strong" NP-Completeness Results: Motivation, Examples, and Implications. J. ACM, 25(3):499--508, 1978.
13. X. Hei, C. Liang, J. Liang, Y. Liu, and K. W. Ross. Insights into PPLive: A Measurement Study of a Large-Scale P2P IPTV System. In Proc. of IPTV Workshop, International World Wide Web Conference, 2006.
14. X. Hei, C. Liang, J. Liang, Y. Liu, and K. W. Ross. A Measurement Study of a Large-Scale P2P IPTV System. IEEE Transactions on Multimedia, 2007.
15. C. Huang, J. Li, and K. Ross. Peer-Assisted VoD: Making Internet Video Distribution Cheap. IPTPS'07, Redmond, 2007.
16. C. Huang, J. Li, and K. W. Ross. Can Internet Video-on-Demand be Profitable? In ACM SIGCOMM, pages 133--144, New York, NY, USA, 2007. ACM.
17. R. Kumar, Y. Liu, and K. Ross. Stochastic Fluid Theory for P2P Streaming Systems. In Infocom 2007, Anchorage, Alaska, 2007.
18. J. Li, P. A. Chou, and C. Zhang. Mutualcast: An efficient mechanism for one-to-many content distribution. In ACM SIGCOMM ASIA Workshop, 2005.
19. S. Liu, S. Sengupta, M. Chiang, J. Li, and P. A. Chou. Achieving streaming capacity in P2P. Microsoft Research Technical Report, April 2008.
20. S. Liu, R. Zhang-Shen, W. Jiang, J. Rexford, and M. Chiang. Performance bounds for peer-asssited live streaming. Princeton University Technical Report, March 2008.
21. T. Locher, R. Meier, S. Schmid, and R. Wattenhofer. Push-to-Pull Peer-to-Peer Live Streaming. In 21st International Symposium on Distributed Computing (DISC), September 2007.
22. N. Magharei, R. Rejaie, and Y. Guo. Mesh or multiple-tree: A comparative study of live P2P streaming approaches. In IEEE Infocom, pages 1424--1432, Anchorage, AK, May 2007.
23. V. N. Padmanabhan, H. J. Wang, P. A. Chou, and K. Sripanidkulchai. Distributing streaming media content using cooperative networking. In ACM NOSSDAV, Miami Beach, FL, May 2002.
24. T. Piotrowski, S. Banerjee, S. Bhatnagar, S. Ganguly, and R. Izmailov. Peer-to-Peer Streaming of Stored Media: The Indirect Approach. SIGMETRICS Perform. Eval. Rev., 34(1):371--372, 2006.
25. P. Rodriguez, S.-M. Tan, and C. Gkantsidis. On the Feasibility of Commercial, Legal P2P Content Distribution. ACM SIGCOMM Computer Communication Review, 36(1):75--78, 2006.
26. T. Silverston and O. Fourmaux. Measuring P2P IPTV Systems. In Proceedings of the 17th International workshop on Network and Operating Systems Support for Digital Audio & Video, 2007.
27. T. Small, B. Liang, and B. Li. Scaling laws and tradeoffs in peer-to-peer live multimedia streaming. In MULTIMEDIA '06: Proceedings of the 14th annual ACM international conference on Multimedia, pages 539--548, New York, NY, USA, 2006. ACM.
28. K. Suh, C. Diot, J. Kurose, L. Massoulie, C. Neumann, D. Towsley, and M. Valleo. Push-to-Peer Video-on-Demand system: Design and Evaluation. IEEE Journal on Selected Areas in Communications, special issue on Advances in Peer-to-Peer Streaming Systems, 2007.
29. Y.-C. Tu, J. Sun, M. Hefeeda, and S. Prabhakar. An analytical study of peer-to-peer media streaming systems. ACM Trans. Multimedia Comput. Commun. Appl., 1(4):354--376, 2005.
30. F. Wang, Y. Xiong, and J. Liu. mTreebone: A Hybrid Tree/Mesh Overlay for Application-Layer Live Video Multicast. In the 27th International Conference on Distributed Computing Systems table of contents, 2007.
31. M. Wang and B. Li. R2: Random push with random network coding in live peer-to-peer streaming. IEEE Journal on Selected Areas in Communications, Special Issue on Advances in Peer-to-Peer Streaming Systems, 25(9):1655--1666, December 2007.
32. X. Zhang, J. Liu, B. Li, and T.-S. P. Yum. DONet/CoolStreaming: A data-driven overlay network for live media streaming. In IEEE INFOCOM, Miami, FL, March 2005.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance