数字视频中的p2p网络拓扑结构研究与应用.doc
约60页DOC格式手机打开展开
数字视频中的p2p网络拓扑结构研究与应用,60页共计32869字摘要p2p（peer to peer）技术在分布式系统和资源共享应用领域中得到迅速的发展，在视频应用领域，近几年国内外涌现出大量的使用p2p技术的产品。当前非结构化p2p网络主要使用集中式查找、洪泛式查找和混合式查找，随着网络规模的扩大，非结构化p2p网络暴露出扩展性能较差的问题。本文针对p2p视...
内容介绍
此文档由会员 bfxqt 发布
60页共计32869字
摘要
P2P（Peer to Peer）技术在分布式系统和资源共享应用领域中得到迅速的发展，在视频应用领域，近几年国内外涌现出大量的使用P2P技术的产品。当前非结构化P2P网络主要使用集中式查找、洪泛式查找和混合式查找，随着网络规模的扩大，非结构化P2P网络暴露出扩展性能较差的问题。本文针对P2P视频系统中的一些基本问题进行了研究和实验，包括：节点的路由和查找算法、数据调度和节点选择策略、网络通讯等。本文的主要研究工作和贡献如下：
（1）节点的路由和查找算法。查找的效率一直是分布式Hash表一个备受关注的指标，在分布式哈希表中，比较著名的协议包括Chord、Pastry、Tapestry和CAN（Content Addressable Network）等。本文结合具体的应用系统的特点和需要修改或者精简了路由查找算法，使它更适合P2P视频点播的应用。
（2）数据调度和节点选择策略。提出了节点学习历史经验的数据调度方法和超时数据的紧急调度方法。为了充分利用节点的资源能力、最大程度地减小中心服务器的压力，设计并实现了节点学习历史经验的自适应的数据调度和节点选择算法；另一方面，为了保证数据在规定的时间内到达，设计并实现了一种超时数据的紧急时刻调度算法。
（3）网络通讯。用户的网络环境多种多样，有些位于公网，有些位于各种各样的网关之后，为了使所有用户平等地使用系统的服务，设计并实现了UDP（User Datagram Protocol）打洞方案解决了部分网关之后的用户的通讯问题，使它们达到和公网上的用户平等的地位。
实验证明，本文提出的数据调度策略和网络通讯方法都是有效的，DHT在较小规模的实验环境中可行，目前还没有推广到大规模的网络环境中。
目 录
第一章 绪论 1
1.1 P2P技术简介 1
1.2 P2P在视频点播中的应用 3
1.3 国内P2P视频发展现状 6
1.4 国外P2P视频发展情况 8
1.5 P2P视频以何制胜 9
1.6 面临的挑战 9
1.7 本文的主要工作和文章结构 10
第二章 P2P查找算法及改进 12
2.1 P2P网络模型 12
2.2 分布式哈希搜索算法 16
2.2.1 Chord协议 16
2.2.2内容访问网络（Content-Addressable Network，CAN） 24
2.2.3 Pastry系统 29
第三章 关键技术的研究和运用 35
3.1 项目简介 35
3.2 基于划分区域的查找 38
3.3 数据调度策略 40
3.4 复杂网络环境中的通讯 46
3.4.1 基本概念 46
3.4.2 面临的困难及其解决的方法 48
3.4.3 实验 51
第四章 总结和展望 53
参考文献 54
致谢 56
关键词：非结构化，结构化，分布式哈希，数据调度，穿越网关
参考文献
[1] Napster, http://www.napster.com
[2] Gnutella, http://gnutella.wego.com
[3] KaZaA, http://kazaa.com
[4] BitTorrent, http://bitconjurer.org/BitTorrent/
[5] Skype, http://www.skype.com.
[6] Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, Hari Balakrishnan, Chord A Scalable Peer-to-peer Lookup Service for Internet Applications, In Proceeding of ACM SIGCOMM 2001, San Diego, California, USA
[7] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, A Scalable Content-Addressable Network, In Proceedings of ACM SIGCOMM2001, San Diego, California, USA
[8] Antony Rowstron and Peter Druschel, Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001).
[9] BenY Zhao, John Kubiatowicz and Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley.
[10] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy, Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, In Proceedings of the 29th Annual ACM Symposium on Theory of Computing
[11] Cox R, Muthitacharoen A, Morris R T. Serving dns using a peer-to-peer lookup service. In: Proceedings of First International Workshop on Peer-to-Peer Systems, Cambridge, March 2002
[12] Jacky Chu, Kevin Labonte, George Bissiasetal, A trace-driven evaluation of chord, Technical report June 2004
[13] RATNASAMY S, HANDLEY M, KARP R, Application-level Multicast using Content-Addressable Networks, Proceedings of NGC, 2001
[14] Yang B, Garcia-Molina H, Improving search in peer-to-peer networks, Distributed Computing Systems, IEEE Computer Society, 2002.5.14
[15] Balakrishnan H, Kaashoek M F, Karger D, Looking up data in p2p systems, Communications of the ACM, 2003
[16] Hefeeda M, Habib A, Botev B, PROMISE: a peer-to-peer media streaming using collect cast, Proceedings of the ACM Multimedia, New York, ACM Press, 2003
[17] Guo Y, Suh K, Kurose J, P2Cast: P2P patching scheme for Vod service, Proceeding of the WWW 2003, New York, ACM Press, 2003
[18] Do T, Hua K, Tantaoui M, P2Vod: Providing fault tolerant video-on-demand streaming in peer-to-peer environment, Proceedings of the IEEE, Paris, IEEE Communications Society, 2004
[19] J. Rosenberg , J. Weinberger , et. STUN - Simple Traversal of User Datagram Protocol (UDP) Through Network Address Translators (NATs), rfc 3489
[20] Microsoft IPv6,
http://www.microsoft.com/china/technet/prodtechnol/winxppro/maintain/Teredo.mspx
[21] 董海韬， 基于对等网络流媒体传输系统技术的研究，清华大学， 2005.5
[22] 马凌霄，基于p2p网络的流媒体技术研究，浙江大学， 2005年
[23] Chao Zhang, Hai Jin, Dafu Deng, Sirui Yang, Quan Yuan and Zuoning Yin, Cluster and Grid Computing Lab. Anysee: Multicast-based Peer-to-Peer Media Streaming Service System, 2005 Asia-Pacific Conference on Communications, Perth, Western Australia, 3 - 5 October 2005.
[24] Xinyan Zhang, Jiangchuan Liu, Bo Li, and Tak-Shing Peter Yum, CoolStreaming/DONet: A Data-driven Overlay Network for Peer-to-Peer Live Media Streaming, 2004
[25] Venkat Padmanabhan, Microsoft Research, Resilient Peer-to-Peer Streaming, 2003.3
[26] Kai Hwang, Internet Security and Cyber Trust for Integrated Web Services and P2P Grid Computing, 2005.12
[27] Meng Zhang, Jian-Guang Luo, Li Zhao, and Shi-Qiang Yang, A Peer-to-Peer Network for Live Media Streaming – Using a Push-Pull Approach, Tsinghua University, 2005
[28] Xiaojun Hei, Chao Liang, Jian Liang, Yong Liu and Keith W. Ross, Insights into PPLive: A Measurement Study of a Large Scale P2P IPTV System.
[29] M.Ripeanu. Peer-to-peer Architecture Case Study: Gnutella. In Proceedings of International Conference on P2P Computing, 2001.
[30] C-NET NEWS, Napster among fastest-growing Net technologies, Oct. 2000, http://news.com.com/2100-1023-246648.html
[31] S. Deering and D. Cheriton, Multicast Routing in Datagram Internetworks and Extended LANs, ACM Transactions on Computer Systems, May 1990
[32] S. E. Deering, Multicast Routing in a Datagram Internetwork, Ph.D. thesis, Stanford University, Dec 1991
[33] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L.Wei, The PIM Architecture for Wide-Area Multicast Routing, IEEE/ACM Transactions on Networking, April 1996
[34] S. Floyd, V. Jacobson, C.G. liu, S. McCanne, and L. Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transaction on networking, Dec. 1997
[35] J.C. Lin and S. Paul, A reliable multicast transport protocol, in Proceedings Of IEEE INFOCOM, 1996
[36] J. H. Saltzer, D. P. Reed, and D. D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems, Nov. 1984
[37] S. Saroiu, P. Gummadi, and S. Gribble, A Measurement Study of Peer-to-Peer File Sharing Systems, Proceedings of SPIE/ACM MMCN 2002, Jan. 2002
摘要
P2P（Peer to Peer）技术在分布式系统和资源共享应用领域中得到迅速的发展，在视频应用领域，近几年国内外涌现出大量的使用P2P技术的产品。当前非结构化P2P网络主要使用集中式查找、洪泛式查找和混合式查找，随着网络规模的扩大，非结构化P2P网络暴露出扩展性能较差的问题。本文针对P2P视频系统中的一些基本问题进行了研究和实验，包括：节点的路由和查找算法、数据调度和节点选择策略、网络通讯等。本文的主要研究工作和贡献如下：
（1）节点的路由和查找算法。查找的效率一直是分布式Hash表一个备受关注的指标，在分布式哈希表中，比较著名的协议包括Chord、Pastry、Tapestry和CAN（Content Addressable Network）等。本文结合具体的应用系统的特点和需要修改或者精简了路由查找算法，使它更适合P2P视频点播的应用。
（2）数据调度和节点选择策略。提出了节点学习历史经验的数据调度方法和超时数据的紧急调度方法。为了充分利用节点的资源能力、最大程度地减小中心服务器的压力，设计并实现了节点学习历史经验的自适应的数据调度和节点选择算法；另一方面，为了保证数据在规定的时间内到达，设计并实现了一种超时数据的紧急时刻调度算法。
（3）网络通讯。用户的网络环境多种多样，有些位于公网，有些位于各种各样的网关之后，为了使所有用户平等地使用系统的服务，设计并实现了UDP（User Datagram Protocol）打洞方案解决了部分网关之后的用户的通讯问题，使它们达到和公网上的用户平等的地位。
实验证明，本文提出的数据调度策略和网络通讯方法都是有效的，DHT在较小规模的实验环境中可行，目前还没有推广到大规模的网络环境中。
目 录
第一章 绪论 1
1.1 P2P技术简介 1
1.2 P2P在视频点播中的应用 3
1.3 国内P2P视频发展现状 6
1.4 国外P2P视频发展情况 8
1.5 P2P视频以何制胜 9
1.6 面临的挑战 9
1.7 本文的主要工作和文章结构 10
第二章 P2P查找算法及改进 12
2.1 P2P网络模型 12
2.2 分布式哈希搜索算法 16
2.2.1 Chord协议 16
2.2.2内容访问网络（Content-Addressable Network，CAN） 24
2.2.3 Pastry系统 29
第三章 关键技术的研究和运用 35
3.1 项目简介 35
3.2 基于划分区域的查找 38
3.3 数据调度策略 40
3.4 复杂网络环境中的通讯 46
3.4.1 基本概念 46
3.4.2 面临的困难及其解决的方法 48
3.4.3 实验 51
第四章 总结和展望 53
参考文献 54
致谢 56
关键词：非结构化，结构化，分布式哈希，数据调度，穿越网关
参考文献
[1] Napster, http://www.napster.com
[2] Gnutella, http://gnutella.wego.com
[3] KaZaA, http://kazaa.com
[4] BitTorrent, http://bitconjurer.org/BitTorrent/
[5] Skype, http://www.skype.com.
[6] Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, Hari Balakrishnan, Chord A Scalable Peer-to-peer Lookup Service for Internet Applications, In Proceeding of ACM SIGCOMM 2001, San Diego, California, USA
[7] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, A Scalable Content-Addressable Network, In Proceedings of ACM SIGCOMM2001, San Diego, California, USA
[8] Antony Rowstron and Peter Druschel, Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, IFIP/ACM International Conference on Distributed Systems Platforms(Middleware 2001).
[9] BenY Zhao, John Kubiatowicz and Anthony D. Joseph. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Technical Report No. UCB/CSD-01-1141, University of California Berkeley.
[10] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy, Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, In Proceedings of the 29th Annual ACM Symposium on Theory of Computing
[11] Cox R, Muthitacharoen A, Morris R T. Serving dns using a peer-to-peer lookup service. In: Proceedings of First International Workshop on Peer-to-Peer Systems, Cambridge, March 2002
[12] Jacky Chu, Kevin Labonte, George Bissiasetal, A trace-driven evaluation of chord, Technical report June 2004
[13] RATNASAMY S, HANDLEY M, KARP R, Application-level Multicast using Content-Addressable Networks, Proceedings of NGC, 2001
[14] Yang B, Garcia-Molina H, Improving search in peer-to-peer networks, Distributed Computing Systems, IEEE Computer Society, 2002.5.14
[15] Balakrishnan H, Kaashoek M F, Karger D, Looking up data in p2p systems, Communications of the ACM, 2003
[16] Hefeeda M, Habib A, Botev B, PROMISE: a peer-to-peer media streaming using collect cast, Proceedings of the ACM Multimedia, New York, ACM Press, 2003
[17] Guo Y, Suh K, Kurose J, P2Cast: P2P patching scheme for Vod service, Proceeding of the WWW 2003, New York, ACM Press, 2003
[18] Do T, Hua K, Tantaoui M, P2Vod: Providing fault tolerant video-on-demand streaming in peer-to-peer environment, Proceedings of the IEEE, Paris, IEEE Communications Society, 2004
[19] J. Rosenberg , J. Weinberger , et. STUN - Simple Traversal of User Datagram Protocol (UDP) Through Network Address Translators (NATs), rfc 3489
[20] Microsoft IPv6,
http://www.microsoft.com/china/technet/prodtechnol/winxppro/maintain/Teredo.mspx
[21] 董海韬， 基于对等网络流媒体传输系统技术的研究，清华大学， 2005.5
[22] 马凌霄，基于p2p网络的流媒体技术研究，浙江大学， 2005年
[23] Chao Zhang, Hai Jin, Dafu Deng, Sirui Yang, Quan Yuan and Zuoning Yin, Cluster and Grid Computing Lab. Anysee: Multicast-based Peer-to-Peer Media Streaming Service System, 2005 Asia-Pacific Conference on Communications, Perth, Western Australia, 3 - 5 October 2005.
[24] Xinyan Zhang, Jiangchuan Liu, Bo Li, and Tak-Shing Peter Yum, CoolStreaming/DONet: A Data-driven Overlay Network for Peer-to-Peer Live Media Streaming, 2004
[25] Venkat Padmanabhan, Microsoft Research, Resilient Peer-to-Peer Streaming, 2003.3
[26] Kai Hwang, Internet Security and Cyber Trust for Integrated Web Services and P2P Grid Computing, 2005.12
[27] Meng Zhang, Jian-Guang Luo, Li Zhao, and Shi-Qiang Yang, A Peer-to-Peer Network for Live Media Streaming – Using a Push-Pull Approach, Tsinghua University, 2005
[28] Xiaojun Hei, Chao Liang, Jian Liang, Yong Liu and Keith W. Ross, Insights into PPLive: A Measurement Study of a Large Scale P2P IPTV System.
[29] M.Ripeanu. Peer-to-peer Architecture Case Study: Gnutella. In Proceedings of International Conference on P2P Computing, 2001.
[30] C-NET NEWS, Napster among fastest-growing Net technologies, Oct. 2000, http://news.com.com/2100-1023-246648.html
[31] S. Deering and D. Cheriton, Multicast Routing in Datagram Internetworks and Extended LANs, ACM Transactions on Computer Systems, May 1990
[32] S. E. Deering, Multicast Routing in a Datagram Internetwork, Ph.D. thesis, Stanford University, Dec 1991
[33] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L.Wei, The PIM Architecture for Wide-Area Multicast Routing, IEEE/ACM Transactions on Networking, April 1996
[34] S. Floyd, V. Jacobson, C.G. liu, S. McCanne, and L. Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transaction on networking, Dec. 1997
[35] J.C. Lin and S. Paul, A reliable multicast transport protocol, in Proceedings Of IEEE INFOCOM, 1996
[36] J. H. Saltzer, D. P. Reed, and D. D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems, Nov. 1984
[37] S. Saroiu, P. Gummadi, and S. Gribble, A Measurement Study of Peer-to-Peer File Sharing Systems, Proceedings of SPIE/ACM MMCN 2002, Jan. 2002
