P2P环境下的内容分发机制研究
|
摘要
随着网络技术的进步,Internet己经发展成为信息社会中最重要的内容发布系统,但Internet中传统的以应用服务器为中心的内容分发网络(Content Distribution Network,CDN)存在着性能瓶颈,不利于网络扩大和维护费用高等问题。与此同时,一种新的分布式资源利用模式——对等网络(Peer-to-Peer,P2P)计算产生了。与传统的C/S计算不同的是,P2P计算一般不需要中心服务器。网络中每个节点既是客户端,又是服务器。P2P允许计算节点之间的直接交流和协作。P2P计算可以充分利用Internet边缘日益丰富的闲置资源,包括计算、存储、带宽等资源。内容发布和共享是P2P计算的一个主要应用领域,基于P2P的内容发布系统的特点是能够充分利用大量的客户端资源,减轻或者抛却应用服务器的负载。
P2P内容分发机制的核心是负载均衡算法以及文件分块选择算法。其中负载均衡算法的目的是选择更接近的、性能更好的节点作为分发服务器。为适应P2P网络的各个节点随时变化的状态以及性能,内容分发机制采用动态的基于优先级的负载均衡算法——根据节点CPU和内存的状况、两节点之间的逻辑距离以及网络状况进行优先级计算并排序,然后顺序选择节点发出资源请求。文件分块选择算法依据文件两层分块的原理划分为两部分:部分选择算法以及块选择算法。前者采用基于优先级的原则:通过该部分在各节点的分布情况、完成度等因素计算出优先级,选择优先级最大的部分进行分发。后者采用顺序选择以及节点反馈相结合的方法:正常情况下,按照块的顺序进行选择;否则,跳跃到下载点所反馈回来的下一块进行顺序选择。
负载均衡算法使得下载者趋向于向更接近的、性能更好的上传者发出资源请求,以获得更好的分发速度;文件分块选择算法有助于增大网络中文件分块在各个下载者之间的差异性,以便加快下载者之间的分发速度。以此为核心的内容分发机制可以更快的速度从更接近、性能更好的节点处获得资源。
With the development of network technology, Internet has become the most important content distribution system in the information society, but the traditional server-centric content distribution mode is also confronted with performance bottle neck. At the same time, P2P computing as a new mode of utilizing distributed computing resources comes into being. It is different from Client/Server computing, commonly there is no special server in P2P network and nodes can communicate and collaborate directly with each other. P2P computing can utilize increasingly unused resources in the edge of the Internet. Content distribution and sharing is one of the main applications of P2P computing, P2P-based content distribution system can fully utilize resources of vast clients and lighten the load of application server.
The core of the P2P-based content distribution mechanism is the load balance arithmetic and the file’s part choosing arithmetic. The purpose of the load balance arithmetic is to choose the node which is nearer or has a better performance as the distribution server. To adapt to the momentarily changing of the state and the performance of the nodes, the priority-based load balance arithmetic is used, whose principle is: calculating and sorting the priority by the states of the CPU and memory, the logic distance of the nodes and the states of network, then send a resource request to the node that has the highest priority. Like the principle of the file’s partition, the file’s part choosing arithmetic is divided into two: the Part-choosing arithmetic and the Block-choosing arithmetic. The Part-choosing arithmetic is priority-based: calculating and sorting every Part’s priority by the situation of the Part in the nodes and the finish percentage, then sending the Part that has biggest priority. The Block-choosing arithmetic’s principle is choosing in the order and the node’s feedback: In the normal condition choosing the Block in the order; otherwise, choosing the Block beginning with the feedback.
The load-balance arithmetic could make the download-node to send the resource request to the upload-node which is nearer and has better performance; the file’s part choosing arithmetic is good for making the difference of the file’s Part in the download-nodes bigger, and making the speed of the distribution faster. The content distribution mechanism whose core is the two arithmetics can make the node to get the resource faster from the nearer and better performance nodes.
P2P内容分发机制的核心是负载均衡算法以及文件分块选择算法。其中负载均衡算法的目的是选择更接近的、性能更好的节点作为分发服务器。为适应P2P网络的各个节点随时变化的状态以及性能,内容分发机制采用动态的基于优先级的负载均衡算法——根据节点CPU和内存的状况、两节点之间的逻辑距离以及网络状况进行优先级计算并排序,然后顺序选择节点发出资源请求。文件分块选择算法依据文件两层分块的原理划分为两部分:部分选择算法以及块选择算法。前者采用基于优先级的原则:通过该部分在各节点的分布情况、完成度等因素计算出优先级,选择优先级最大的部分进行分发。后者采用顺序选择以及节点反馈相结合的方法:正常情况下,按照块的顺序进行选择;否则,跳跃到下载点所反馈回来的下一块进行顺序选择。
负载均衡算法使得下载者趋向于向更接近的、性能更好的上传者发出资源请求,以获得更好的分发速度;文件分块选择算法有助于增大网络中文件分块在各个下载者之间的差异性,以便加快下载者之间的分发速度。以此为核心的内容分发机制可以更快的速度从更接近、性能更好的节点处获得资源。
With the development of network technology, Internet has become the most important content distribution system in the information society, but the traditional server-centric content distribution mode is also confronted with performance bottle neck. At the same time, P2P computing as a new mode of utilizing distributed computing resources comes into being. It is different from Client/Server computing, commonly there is no special server in P2P network and nodes can communicate and collaborate directly with each other. P2P computing can utilize increasingly unused resources in the edge of the Internet. Content distribution and sharing is one of the main applications of P2P computing, P2P-based content distribution system can fully utilize resources of vast clients and lighten the load of application server.
The core of the P2P-based content distribution mechanism is the load balance arithmetic and the file’s part choosing arithmetic. The purpose of the load balance arithmetic is to choose the node which is nearer or has a better performance as the distribution server. To adapt to the momentarily changing of the state and the performance of the nodes, the priority-based load balance arithmetic is used, whose principle is: calculating and sorting the priority by the states of the CPU and memory, the logic distance of the nodes and the states of network, then send a resource request to the node that has the highest priority. Like the principle of the file’s partition, the file’s part choosing arithmetic is divided into two: the Part-choosing arithmetic and the Block-choosing arithmetic. The Part-choosing arithmetic is priority-based: calculating and sorting every Part’s priority by the situation of the Part in the nodes and the finish percentage, then sending the Part that has biggest priority. The Block-choosing arithmetic’s principle is choosing in the order and the node’s feedback: In the normal condition choosing the Block in the order; otherwise, choosing the Block beginning with the feedback.
The load-balance arithmetic could make the download-node to send the resource request to the upload-node which is nearer and has better performance; the file’s part choosing arithmetic is good for making the difference of the file’s Part in the download-nodes bigger, and making the speed of the distribution faster. The content distribution mechanism whose core is the two arithmetics can make the node to get the resource faster from the nearer and better performance nodes.
引文
[1] Stefan Saroiu, Krishna P. Gummadi, et al. An Analysis of Internet Content Delivery Systems. In Proc. of OSDI '02, 2002
[2] Tyron Stading, Petros Maniatis, Mary Baker. Peer-to-Peer Caching Schemes to Address Flash Crowds. IPTPS 2002,LNCS2 429. 203～213
[3] Stephen Adler. The Slashdot Effect: an Analysis of Three Internet Publications. Linux Gazette 38,1999
[4] Guillaume Pierre, Maarten van Steen. Globule: a platform for self-replicating Web documents. Proceedings of the 6th International Conference on Protocols for Multimedia Systems,2001,10. 1～11
[5]谢智文.互联网P2P应用技术探讨.武汉市第二届学术年会、通信学会2006年学术年会论文集.2006. 236~237
[6]梁毅,王忠. P2P技术的发展与应用.四川省通信学会2005年学术年会论文集,2005. 440~443
[7] Li ZP, Huang JH, Huang DY, Zhuang L. Introduction to Peer-to-Peer networking technology and development. Telecommunications Science, 2003, 19(3). 1-4
[8]李之棠. P2P原理与技术[J].华中科技大学计算机学院. CERNET第十一届学术会议
[9]李珊. P2P技术:互联网发展的新惊喜.电子商务,Electronic Science & Technology Review,2005,02期. 72~74
[10] Dejan S. Milojicic, Vana Kalogeraki, et al. Peer-to-Peer Computing. HP Laboratories Palo Alto, HPL-2002-57
[11]李阳明,王丽芬,郭慧. P2P对等网络的关键技术及应用.现代计算机(专业版),2005年08期
[12] Balachander Krishnamurthy, Craig Wills, Yin Zhang. On the Use and Performance of Content Distribution Networks. In ACM SIGCOMM INTERNETM EASUREMENT WORKSHOP 2001
[13] Lazar I, Terrill W. Exploring Content Delivery Networking[J],IT Professional, Volume 3, Issue 4, July-Aug. 2001. 47~49
[14] Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, In Proc.ACM, SIGCOMM, San Diego, CA, August 2001. 149~160
[15] John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski. Oceanstore: An architecture for Global-Scale Persistent Storage. In Proc. ASPLOS’2000, Cambridge, MA, November 2000. 190~201
[16] Ben Y. 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
[17] Thomas Karagiannis, Andre Broido, Nevil Brownlee, et al. File-sharing in the Internet: A characterization of P2P traffic in the backbone. CAIDA,SDSC,UCSD
[18] M. Ripeanu. Peer-to-peer Architecture Case Study: Gnutella. In Proceedings of International Conference on P2P Computing, 2001
[19] S. Saroiu, P.K. Gummadi, et al. A measurement Study of Peer-to-Peer File Sharing Systems. Proceedings of Multimedia Computing and Networking (MMCN),2002
[20] Nicol D M. Communication load balancing in distributed systems[C]. Proc of Scalable High Performance Computing Conf, 1992. 292~299
[21]张联峰,刘乃安等.综述:对等网(P2P)技术,计算机工程与应用,2003
[22] P.Backx, T. Wauters,B. Dhoedt,P. Demeester. A Comparison of Peer-to-Peer Architectures [J], Eurescom Summit 2002. 67~75
[23] David Liben-Nowell, Hari Balakrishnan, David Karger. Observations on the dynamic evolution of peer-to-peer networks[J], In Proceedings of the First International, Workshop on Peer-to-Peer Systems, Cambridge, MA, 2002.3. 25~68
[24] Jaime Woret. Interconnecting Unstructured P2P File Sharing Networks.P2P Journal. January, 2005
[25]乐光学.基于Gnutella协议的P2P网络路由搜索算法:Light-Flooding[J],计算机工程, 2005年11期. 121~123
[26] Jain S, Mahajan R, Wetherall D. A study of the performance potential of DHT-basedoverlays. In: Proc. of the 4th USENIX Symposium on Internet Technologies and Systems (USITS 2003). 2003. 256~261
[27] A Fiat, J Saia. Censorship resistant peer-to-peer content addressable networks. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms.2002. 94~103
[28] S Ratnasamy. A Scalable Content-Addressable Network. [Ph.D. Thesis]. University of California, Berkeley. October 2002
[29] Lua E. Keong, Crowcroft Jon, Pias Marcelo. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE Communications Surveys & Tutorials, Second Quarter 2005
[30] A. Rowstron , P. Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-peer Systems. Proc. Middleware, 2001
[31] Petar Maymounkov, David Mazieres. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. In: Proc. of the 1st Int'l Workshop on Peer-to-Peer Systems (IPTPS 2002). 2002. 153~161
[32] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Technical Information Service, Springfield, VA, Apr.1995
[33] M. Harchol Balter, T. Leighton, D. Lewin. Resource discovery in distributed networks, ACM Symposium on Principles of Distributed Computing, May 1999. 229~237
[34] D.Tsoumakos, N. Roussopoulos. A Comparison of Peer-to-Peer Search Methods. Proceedings of the Sixth WebDB Workshop, CA, USA, 2003,6. 61~66
[35]江早,王浩.基于P2P的多媒体数据分发技术的研究及在3i-DSN系统的应用.中国学位论文全文库,2005
[36] Wu M Y, Shu W. A load-balancing algorithm for n-cubes[C].Proc of the 1996 Int'l Conf on Parallel Processing, 1996. 148~155
[37]杨兵强,仇建伟.网格环境下负载平衡研究.计算机工程与设计,2005年,11期
[38]周健,洪佩琳,李津生. DHT网络中一种基于树型结构的负载均衡方案.小型微型计算机系统,2006年,11期
[39] Liu Xin, Chien Andrew A.. Traffic-based Load Balance for Scalable NetworkEmulation. Proceedings of the ACM/IEEE SC2003 Conference(SC’03)
[40] Keslassy Isaac, Chang Cheng-Shang, McKeown Nick, et al. Optimal load-balancing. IEEE, 2005. 1712~1722
[2] Tyron Stading, Petros Maniatis, Mary Baker. Peer-to-Peer Caching Schemes to Address Flash Crowds. IPTPS 2002,LNCS2 429. 203～213
[3] Stephen Adler. The Slashdot Effect: an Analysis of Three Internet Publications. Linux Gazette 38,1999
[4] Guillaume Pierre, Maarten van Steen. Globule: a platform for self-replicating Web documents. Proceedings of the 6th International Conference on Protocols for Multimedia Systems,2001,10. 1～11
[5]谢智文.互联网P2P应用技术探讨.武汉市第二届学术年会、通信学会2006年学术年会论文集.2006. 236~237
[6]梁毅,王忠. P2P技术的发展与应用.四川省通信学会2005年学术年会论文集,2005. 440~443
[7] Li ZP, Huang JH, Huang DY, Zhuang L. Introduction to Peer-to-Peer networking technology and development. Telecommunications Science, 2003, 19(3). 1-4
[8]李之棠. P2P原理与技术[J].华中科技大学计算机学院. CERNET第十一届学术会议
[9]李珊. P2P技术:互联网发展的新惊喜.电子商务,Electronic Science & Technology Review,2005,02期. 72~74
[10] Dejan S. Milojicic, Vana Kalogeraki, et al. Peer-to-Peer Computing. HP Laboratories Palo Alto, HPL-2002-57
[11]李阳明,王丽芬,郭慧. P2P对等网络的关键技术及应用.现代计算机(专业版),2005年08期
[12] Balachander Krishnamurthy, Craig Wills, Yin Zhang. On the Use and Performance of Content Distribution Networks. In ACM SIGCOMM INTERNETM EASUREMENT WORKSHOP 2001
[13] Lazar I, Terrill W. Exploring Content Delivery Networking[J],IT Professional, Volume 3, Issue 4, July-Aug. 2001. 47~49
[14] Ion Stoica, Robert Morris, David Karger, M.Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, In Proc.ACM, SIGCOMM, San Diego, CA, August 2001. 149~160
[15] John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski. Oceanstore: An architecture for Global-Scale Persistent Storage. In Proc. ASPLOS’2000, Cambridge, MA, November 2000. 190~201
[16] Ben Y. 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
[17] Thomas Karagiannis, Andre Broido, Nevil Brownlee, et al. File-sharing in the Internet: A characterization of P2P traffic in the backbone. CAIDA,SDSC,UCSD
[18] M. Ripeanu. Peer-to-peer Architecture Case Study: Gnutella. In Proceedings of International Conference on P2P Computing, 2001
[19] S. Saroiu, P.K. Gummadi, et al. A measurement Study of Peer-to-Peer File Sharing Systems. Proceedings of Multimedia Computing and Networking (MMCN),2002
[20] Nicol D M. Communication load balancing in distributed systems[C]. Proc of Scalable High Performance Computing Conf, 1992. 292~299
[21]张联峰,刘乃安等.综述:对等网(P2P)技术,计算机工程与应用,2003
[22] P.Backx, T. Wauters,B. Dhoedt,P. Demeester. A Comparison of Peer-to-Peer Architectures [J], Eurescom Summit 2002. 67~75
[23] David Liben-Nowell, Hari Balakrishnan, David Karger. Observations on the dynamic evolution of peer-to-peer networks[J], In Proceedings of the First International, Workshop on Peer-to-Peer Systems, Cambridge, MA, 2002.3. 25~68
[24] Jaime Woret. Interconnecting Unstructured P2P File Sharing Networks.P2P Journal. January, 2005
[25]乐光学.基于Gnutella协议的P2P网络路由搜索算法:Light-Flooding[J],计算机工程, 2005年11期. 121~123
[26] Jain S, Mahajan R, Wetherall D. A study of the performance potential of DHT-basedoverlays. In: Proc. of the 4th USENIX Symposium on Internet Technologies and Systems (USITS 2003). 2003. 256~261
[27] A Fiat, J Saia. Censorship resistant peer-to-peer content addressable networks. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms.2002. 94~103
[28] S Ratnasamy. A Scalable Content-Addressable Network. [Ph.D. Thesis]. University of California, Berkeley. October 2002
[29] Lua E. Keong, Crowcroft Jon, Pias Marcelo. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE Communications Surveys & Tutorials, Second Quarter 2005
[30] A. Rowstron , P. Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-peer Systems. Proc. Middleware, 2001
[31] Petar Maymounkov, David Mazieres. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. In: Proc. of the 1st Int'l Workshop on Peer-to-Peer Systems (IPTPS 2002). 2002. 153~161
[32] FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/NIST, National Technical Information Service, Springfield, VA, Apr.1995
[33] M. Harchol Balter, T. Leighton, D. Lewin. Resource discovery in distributed networks, ACM Symposium on Principles of Distributed Computing, May 1999. 229~237
[34] D.Tsoumakos, N. Roussopoulos. A Comparison of Peer-to-Peer Search Methods. Proceedings of the Sixth WebDB Workshop, CA, USA, 2003,6. 61~66
[35]江早,王浩.基于P2P的多媒体数据分发技术的研究及在3i-DSN系统的应用.中国学位论文全文库,2005
[36] Wu M Y, Shu W. A load-balancing algorithm for n-cubes[C].Proc of the 1996 Int'l Conf on Parallel Processing, 1996. 148~155
[37]杨兵强,仇建伟.网格环境下负载平衡研究.计算机工程与设计,2005年,11期
[38]周健,洪佩琳,李津生. DHT网络中一种基于树型结构的负载均衡方案.小型微型计算机系统,2006年,11期
[39] Liu Xin, Chien Andrew A.. Traffic-based Load Balance for Scalable NetworkEmulation. Proceedings of the ACM/IEEE SC2003 Conference(SC’03)
[40] Keslassy Isaac, Chang Cheng-Shang, McKeown Nick, et al. Optimal load-balancing. IEEE, 2005. 1712~1722