Scheduling Piece Requests Blindly and Randomly for Peer-to-Peer Live Streaming

doi:10.1016/S1005-8885(09)60451-9

中国邮电高校学报(英文) ›› 2010, Vol. 17 ›› Issue (2): 76-84.doi: 10.1016/S1005-8885(09)60451-9

Scheduling Piece Requests Blindly and Randomly for Peer-to-Peer Live Streaming

陈一帅¹,陈常嘉¹,李纯喜²,赵永祥²

1. 北京交通大学
2.

收稿日期:2009-07-06 修回日期:2010-01-21 出版日期:2010-04-30 发布日期:2010-06-01
通讯作者: 陈一帅 E-mail:chenyishuai@gmail.com
基金资助:
国家级.国家自然科学基金

Scheduling Piece Requests Blindly and Randomly for Peer-to-Peer Live Streaming

Received:2009-07-06 Revised:2010-01-21 Online:2010-04-30 Published:2010-06-01

摘要/Abstract

摘要：

The design of piece scheduling algorithm is fundamental in mesh-based Peer-to-Peer (P2P) live streaming systems. This paper regards the piece propagation process in P2P live streaming system as a conflict process, where peers compete to get the piece as soon as possible to meet the tight timing requirement of the live system. In this vision, we reduce the piece scheduling problem as a conflict resolution problem, and propose a blind random scheduling method to resolve it. The algorithm is: 1) pieces are scheduled independently; 2) conflicts are resolved by the random back off algorithm. The theoretical analysis and simulation results prove that the algorithm scales well with the network size, and can obtain near-optimal in-time delivery of pieces. The algorithm is also easy to implement in the real-world system.

关键词:

Peer-to-peer, Live streaming, Conflict Resolution, Exponential Back Off, Piece Scheduling

Abstract:

Key words:

Peer-to-peer, Live streaming, Conflict Resolution, Exponential Back Off, Piece Scheduling

参考文献

1. Padmanabhan V N, Wang H J, Chou P A. Resilient peer-to-peer streaming. Proceedings of the 11st IEEE International Conference on Network Protocol (ICNP’03), Nov 4-7, 2003, Atlanta, GA, USA. Los Alamitos, CA, USA: IEEE Computer Society, 2003: 16-27

2. Castro M, Druschel P, Kermarrec A M, et al. SplitStream: high-bandwidth multicast in a cooperative environment. Proceedings of the 19th ACM SIGOPS Symposium on Operating Systems Principles (SOSP’03), Oct 19-22, 2003, Bolton Landing, NY, USA. New York, NY, USA: ACM, 2003: 298-313

3. Pai V, Kumar K, Tamilmani K, et al. Chainsaw: eliminating trees from overlay multicast. Proceedings of the 4th International Workshop on Peer-to-Peer Systems (IPTPS’05), Feb 24-25, 2005, Ithaca, NY, USA. LNCS 3640. Berlin, Germany: Springer-Verlag, 2005: 127-140

4. Zhang X Y, Liu J C, Li B, et al. CoolStreaming/Donet: a data-driven overlay network for peer-to-peer live media streaming. Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05): Vol 2, Mar 13-17, 2005, Miami, FL, USA. Piscataway, NJ, USA: IEEE, 2005: 2102-2111

5. Magharei N, Rejaie R, Guo Y. Mesh or multiple-tree: a comparative study of live P2P streaming approaches. Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM’07), Mar 6-12, 2007,Anchorage, AK, USA. Piscataway, NJ, USA: IEEE, 2007: 1424-1432

6. Huang Y, Fu T Z J, Chiu D M, et al. Challenges, design and analysis of a large-scale P2P-VoD system. Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM’08), Aug 17-22, 2008, Seattle, WA, USA. New York, NY, USA: ACM, 2008: 375-388

7. Magharei N, Rejaie R. PRIME: peer-to-peer receiver-driven mesh-based streaming. Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM’07), Mar 6-12, 2007,Anchorage, AK,USA. Piscataway, NJ, USA: IEEE 2007: 1415-1423

8. Vlavianos A, Iliofotou M, Faloutsos M. BiTos: enhancing BitTorrent for supporting streaming applications. Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM’06), Apr 23-29, 2006, Barcelona, Spain. Piscataway, NJ, USA: IEEE, 2006: 6p

9. Zhou Y P, Chiu D M, Lui J C S. A simple model for analyzing P2P streaming protocols. Proceedings of the 15th IEEE International International Conference on Network Protocols (ICNP’07), Oct 16-19, 2007, Beijing, China. Piscataway, NJ, USA: IEEE, 2007: 226-235

10. Zhang M, Zhang Q, Sun L F, et al. Understanding the power of pull-based streaming protocol: can we do better? IEEE Journal on Selected Areas in Communications, 2007, 25(9), 1678-1694

11. Liang C, Guo Y, Liu Y. Is random scheduling sufficient in P2P video streaming?. Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS’08), Jun 17-20, 2008, Beijing, China. Piscataway, NJ, USA: IEEE, 2008: 53-60

12. Cohen B. Incentives build robustness in BitTorrent. Proceedings of the 1st Workshop on Economics of Peer-to-Peer Systems (P2PEcon’03): Vol 6, Jun 5-6, 2003, Berkeley, CA, USA. LNCS 2735. Berlin, Germany: Springer-Verlag, 2003: 102-111

13. Bharambe A R, Herley C, Padmanabhan V N. Analyzing and improving a BitTorrent networks performance mechanisms. Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM’06), Apr 23-29, 2006, Barcelona, Spain. Piscataway, NJ, USA: EEE, 2006: 12p

14. Legout A, Urvoy-Keller G, Michiardi P. Rarest first and choke algorithms are enough. Proceedings of the 6th ACM SIGCOMM on Internet measurement Conference (IMC’06), Oct 25-27, 2006, Rio de Janeiro, Brazil. New York, NY, USA: ACM, 2006: 203-216

15. Mol J D. P2P video streaming with tribler [2008]. http://www.tribler.org/ attachment/wiki/ TriblerCourse/jandavid.pdf

16. Abramson N. The ALOHA system: another alternative for computer communications. Proceedings of Fall Joint Computer Conference Proceedings (AFIPS’70), Nov 17-19, 1970, Houston, TX, USA. Reston, VA, USA: AFIPS Press, 1970: 281-285

17. Yang X, Veciana G D. Service capacity of peer to peer networks. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’04): Vol 4, Mar 7-11, 2004, Hong Kong, China. Piscataway, NJ, USA: IEEE, 2004: 2242-2252

18. Xu D G, Chai H K, Rosenberg C, et al. Analysis of a hybrid architecture for cost-effective streaming media distribution. Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking (MMCN’03), Jan 23-24, 2003, San Jose, CA, USA. 2003

19. Tu Y C, Sun J Z, Prabhakar S. Performance analysis of a hybrid media streaming system. Proceedings of SPIE/ACM Conference on Multimedia Computing and Networking (MMCN’04), Jan 21-22, 2004, San Jose, CA, USA. 2004

20. Lou D F, Mao Y Y, Yeap T H. The production of peer-to-peer video-streaming networks. Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM’2007), Aug 27-31, 2007, Kyoto, Japan. New York, NY, USA: ACM, 2007: 346-351

21. Kumar R, Liu Y, Ross K W. Stochastic fluid theory for P2P streaming systems. Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM’07), Mar 6-12, 2007,Anchorage, AK, USA. Piscataway, NJ, USA: IEEE, 2007: 919-927

22. Hei X J, Liang C, Liang J, et al. A measurement study of a large scale P2P IPTV system, IEEE Transactions on Multimedia, 2007, 9(8): 1672-1687

23. Chen Y S, Chen C J, Li C X. Measure and model P2P streaming system by buffer bitmap. Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications (HPCC’08), Sep 25-27, 2008, Dalian, Beijing. Piscataway, NJ, USA: IEEE, 2008: 242-249

Scheduling Piece Requests Blindly and Randomly for Peer-to-Peer Live Streaming

Scheduling Piece Requests Blindly and Randomly for Peer-to-Peer Live Streaming

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价