InstantLeap: fast neighbor discovery in P2P VoD streaming

ABSTRACT

A fundamental challenge in peer-to-peer (P2P) Video-on-Demand (VoD) streaming is to quickly locate new supplying peers whenever a VCR command is issued, in order to achieve smooth viewing experiences. For most existing commercial systems which resort to tracking servers for such neighbor discovery, the increasing scale of P2P VoD systems has brought heavy load onto the dedicated servers. To avoid overloading the servers and achieve instant neighbor discovery over the self-organizing P2P overlay, we design a novel method of organizing peers watching the same video, that constitutes a light-weighted indexing structure to support efficient streaming and fast neighbor discovery at the same time. InstantLeap achieves an O(1) neighbor discovery efficiency upon any playback "leaps" across the media stream in streaming overlays of any sizes, with a low messaging cost for the overlay maintenance. We support our design with rigorous analysis and extensive simulations.

REFERENCES

• 1: PPLive, http://www.pplive.com/.
• 2: UUSee, http://www.uusee.com/.
• 3: PPStream, http://www.ppstream.com/.
• 4: B. Cheng, X. Liu, Z. Zhang, and H. Jin. A Measurement Study of a Peer-to-Peer Video-on-Demand System. In Proc. of the 6th International Workshop on Peer-to-Peer Systems (IPTPS 2007), February 2007.
• 5: B. Cheng, H. Jin, and X. Liao. Supporting VCR Functions in P2P VoD Services Using Ring-Assisted Overlays. In Proc. of the IEEE International Conference on Communications (ICC 2007), June 2007.
• 6: H. Chi, Q. Zhang, J. Jia, and X. Shen. Efficient Search and Scheduling in P2P-based Media-on-Demand Streaming Service. IEEE Journal on Selected Areas in Communications, 25(1):119--130, January 2007.
• 7: Yung Ryn Choe , Derek L. Schuff , Jagadeesh M. Dyaberi , Vijay S. Pai, Improving VoD server efficiency with bittorrent, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany [doi>10.1145/1291233.1291258]
• 8: Yan Huang , Tom Z.J. Fu , Dah-Ming Chiu , John C.S. Lui , Cheng Huang, Challenges, design and analysis of a large-scale p2p-vod system, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 9: S. Naicken , B. Livingston , A. Basu , S. Rodhetbhai , I. Wakeman , D. Chalmers, The state of peer-to-peer simulators and simulations, ACM SIGCOMM Computer Communication Review, v.37 n.2, April 2007 [doi>10.1145/1232919.1232932]
• 10: Nevena Vratonjić , Priya Gupta , Nikola Knežević , Dejan Kostić , Antony Rowstron, Enabling DVD-like features in P2P video-on-demand systems, Proceedings of the 2007 workshop on Peer-to-peer streaming and IP-TV, August 27-31, 2007, Kyoto, Japan [doi>10.1145/1326320.1326326]
• 11: Dan Wang , Jiangchuan Liu, A Dynamic Skip List-Based Overlay for On-Demand Media Streaming with VCR Interactions, IEEE Transactions on Parallel and Distributed Systems, v.19 n.4, p.503-514, April 2008 [doi>10.1109/TPDS.2007.70748]
• 12: Z. Yin and H. Jin. DHT Based Collaborative Multimedia Streaming and Caching Service. In Proc. of the IEEE International Region 10 Conference (TENCON 2005), November 2005.
• 13: W.-P. Yiu, X. Jin, and S.-H. Chan. VMesh: Distributed Segment Storage for Peer-to-Peer Interactive Video Streaming. IEEE Journal on Selected Areas in Communications, Special Issue on Advances in Peer-to-Peer Streaming Systems, 25(9):1717 -- 1731, December 2007.
• 14: X. Zhang, J. Liu, B. Li, and T.P. Yum. CoolStreaming/DONet: A Data-Driven Overlay Network for Live Media Streaming. In Proc. of IEEE INFOCOM, March 2005.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
indexing overlay, neighbor discovery, peer-to-peer network, video-on-demand