Performance Analysis and Improvement of Overlay Construction for Peer-to-Peer Live Streaming

Abstract

For single-source, single-tree-based peer-to-peer live media streaming, it is generally believed that a short (and wide) tree has a good comprehensive performance in terms of reliability and service delay. While the short tree directly benefits delay optimization, it is unclear whether such a structure maximizes tree reliability, which is sometimes more critical for a streaming Internet service. This article studies several prevalent overlay construction algorithms from the aspects of (1) service reliability, (2) service delay, and (3) protocol overhead. Two types of peer layout, bandwidth-ordered layout and time-ordered layout, are identified, and their performance is evaluated. The analytical results show that, by appropriately placing peers according to their time properties, the tree achieves a much higher degree of reliability than the depth-optimized tree. This finding motivates the design of a heap algorithm, which aims for combining the strengths of both bandwidth ordering and time ordering. It dynamically moves peers between difference layers of the tree according to a simple metric and gradually adjusts the tree toward a layout partially ordered in time and partially ordered in bandwidth. In so doing, the tree has advantages in both service reliability and delay. Extensive simulations show that this new algorithm achieves better comprehensive performance than existing algorithms.

Keywords

Overlay construction peer-to-peer streaming reliability

Get full access to this article

View all access options for this article.

References

Chu, Y. , S. Rao , and H. Zhang 2000. A case for end system multicast . In Proceedings of ACM SIGMETRICS, June.

Pendarakis, D. , S. Shi , D. Verma , and M. Waldvogel . 2001. ALMI: An application level multicast infrastructure . In Proceedings of the 3rd Usenix Symposium on Internet Technologies and Systems, March.

Banerjee, S. , B. Bhattacharjee , and C. Kommareddy . 2002. Scalable application layer multicast . In Proceedings of ACM SIGCOMM 2002, August.

Chawathe, Y. 2000. Scattercast: An architecture for Internet broadcast distribution as an infrastructure service. Ph.D. diss., University of California, Berkeley.

Chu, Y. , A. Ganjam , T. S. E. Ng , S. G. Rao , K. Sripanidkulchai , J. Zhan , and H. Zhang . 2004. Early experience with an Internet broadcast system based on overlay multicast . In Proceedings of USENIX 2004 Annual Technical Conference.

Padmanabhan, V. N. , H. J. Wang , P. A. Chou , and K. Sripanidkulchai . 2002. Distributing streaming media content using cooperative networking . In ACM NOSSDAV, May.

Sripanidkulchai, K. , A. Ganjam , B. Maggs , and H. Zhang . 2004. The feasibility of supporting large-scale live streaming applications with dynamic application end-points . In Proceedings of ACM SIGCOMM, Portland, OR.

Tran, D. A. , K. A. Hua , and T. T. Do . 2004. A peer-to-peer architecture for media streaming . IEEE Journal on Selected Areas in Communications 22 (1): 121-133 .

Guo, M. , and M. Ammar . 2004. Scalable live video streaming to cooperative clients using time shifting and video patching . In Proceedings of INFOCOM 2004.

10.

Veloso, E. , V. Almeida , W. Meira , A. Bestavros , and S. Jin . 2004. A hierarchical characterization of a live streaming media workload . IEEE/ACM Transactions on Networking 14 (1): 133-146 .

11.

Sen, S. , and J. Wang . 2004. Analyzing peer-to-peer traffic across large networks . IEEE/ACM Transactions on Networking 12 (2): 219-232 .

12.

Padmanabhan, V. N. , H. J. Wang , and P. A. Chou . 2003. Resilient peer-to-peer streaming . In 11th IEEE International Conference on Network Protocols (ICNP).

13.

Sripanidkulchai, K. , B. Maggs , and H. Zhang . 2004. An analysis of live streaming workloads on the Internet . In Proceedings of the 4th ACM SIGCOMM IMC, October, Italy.

14.

Kulkarni, V. G. 1996. Modeling and analysis of stochastic systems. London: Chapman & Hall .

15.

David, H. A. , and H. N. Nagaraja . 2003. Order statistics. 3rd ed. New York: Wiley-Interscience .

16.

Saroiu, S. , P. Gummadi , and S. Gribble . 2002. A measurement study of peer-to-peer file sharing systems . In Proceedings of Multimedia Computing and Networking (MMCN).

17.

Tan, G. , S. A. Jarvis , D. P. Spooner , and G. R. Nudd 2005. On efficient and robust overlay construction for large-scale P2P live media streaming. Report TR-2005-02, Department of Computer Science, University of Warwick, UK .

18.

Ooi, W. T. 2005. Dagster: Contributor-aware end-host multicast for media streaming in heterogeneous environment . In Proceedings of Multimedia Computing and Networking (MMCN).

19.

Chu, Y. , S. G. Rao , S. Seshan , and H. Zhang . 2001. Enabling conferencing applications on the Internet using an overlay multicast architecture . In Proceedings of ACM SIGCOMM 2001.

20.

Zegura, E. W. , K. Calvert , and S. Bhattacharjee . 1996. How to model an internetwork . In Proceedings of IEEE INFOCOM'96, San Francisco.