新型结构化P2P覆盖网络研究
|
摘要
近年来,P2P技术成为了计算机界研究的热点,而P2P覆盖网络作为作为P2P系统的骨架,对P2P系统的性能有着至关重要的作用。现有的P2P覆盖网络可分为非结构化和结构化两类,非结构化网络具有大簇系数和大平均网络距离的特性,而在结构化网络中,簇系数和平均网络距离均较小。同时,在现有的P2P网络构建中,下层的网络拓扑结构并没有得到考虑,因此在端到端的通信中,尽管覆盖网上所反映出路径跳数很少,但实际的延迟却会很大。
首先,针对P2P覆盖网络目前存在的问题,本文结合小世界理论和底层拓扑信息探测的思想提出了一种新的P2P覆盖网络(NSWO网络),并对该覆盖网络的构建算法做了详细描述,该网络同时具有网络敏感和小世界网络大簇系数小平均网络距离的特性。
然后,我们利用上述特性在所提出的NSWO网络的基础上构建了一套高效的资源搜索算法,该算法采用先簇内搜索,再簇间搜索的原则,通过仿真实验与现有的经典P2P覆盖网络资源搜索算法比较,验证了该算法在平均网络延迟和平均搜索路径长度上均有优势。
最后,我们同样是利用NSWO网络的特性,提出了一套NSWO网络上的拥塞控制算法,以解决网络中由于热点资源的出现而引发的网络突然拥塞问题,实验表明,该算法具有较好的拥塞控制能力。
In recent years, P2P technology has become the hot spot in computer research. And the P2P overlay network, as P2P system's skeleton, has played a very important role in the P2P system's performance. The existing P2P overlay network can be divided into two types of unstructured one and structured one. The unstructured overlay network has characteristics of big cluster coefficient and great average network distance. And in structured overlay network, the cluster coefficient and average network distance are both small. At the same time, in the existing P2P network construction, the underlying network topology hasn't been take into account. Thus, in peer-to-peer correspondence, the actual latency can actually be very large although the hops of path are just few.
First, in view of existing problems of P2P overlay network, this article applies the small world theory and the idea of network topology information collection to propose a new P2P overlay network (NSWO network). and this new overlay network's construction algorithm has been given a detailed description in the paper. This overlay network has all Characteristics of network-aware, big cluster coefficient and small average network distance.
Then, taking advantage of NSWO network's characteristics, we developed a highly efficient algorithm for object searching. This algorithm is designed with principle that it first do searching in cluster, and then do searching between clusters. Through the simulation experiment, it has been confirmed that, comparing with the existing classic P2P overlay network, our algorithm has superiority in average network latency and average searching path's length.
Finally, we have also used NSWO network's characteristics to proposed a set of algorithm for congestion control, in order to handle the flash crowd caused by popular object's appearance in network. The simulation experiment has indicated that this algorithm has a good congestion control ability.
首先,针对P2P覆盖网络目前存在的问题,本文结合小世界理论和底层拓扑信息探测的思想提出了一种新的P2P覆盖网络(NSWO网络),并对该覆盖网络的构建算法做了详细描述,该网络同时具有网络敏感和小世界网络大簇系数小平均网络距离的特性。
然后,我们利用上述特性在所提出的NSWO网络的基础上构建了一套高效的资源搜索算法,该算法采用先簇内搜索,再簇间搜索的原则,通过仿真实验与现有的经典P2P覆盖网络资源搜索算法比较,验证了该算法在平均网络延迟和平均搜索路径长度上均有优势。
最后,我们同样是利用NSWO网络的特性,提出了一套NSWO网络上的拥塞控制算法,以解决网络中由于热点资源的出现而引发的网络突然拥塞问题,实验表明,该算法具有较好的拥塞控制能力。
In recent years, P2P technology has become the hot spot in computer research. And the P2P overlay network, as P2P system's skeleton, has played a very important role in the P2P system's performance. The existing P2P overlay network can be divided into two types of unstructured one and structured one. The unstructured overlay network has characteristics of big cluster coefficient and great average network distance. And in structured overlay network, the cluster coefficient and average network distance are both small. At the same time, in the existing P2P network construction, the underlying network topology hasn't been take into account. Thus, in peer-to-peer correspondence, the actual latency can actually be very large although the hops of path are just few.
First, in view of existing problems of P2P overlay network, this article applies the small world theory and the idea of network topology information collection to propose a new P2P overlay network (NSWO network). and this new overlay network's construction algorithm has been given a detailed description in the paper. This overlay network has all Characteristics of network-aware, big cluster coefficient and small average network distance.
Then, taking advantage of NSWO network's characteristics, we developed a highly efficient algorithm for object searching. This algorithm is designed with principle that it first do searching in cluster, and then do searching between clusters. Through the simulation experiment, it has been confirmed that, comparing with the existing classic P2P overlay network, our algorithm has superiority in average network latency and average searching path's length.
Finally, we have also used NSWO network's characteristics to proposed a set of algorithm for congestion control, in order to handle the flash crowd caused by popular object's appearance in network. The simulation experiment has indicated that this algorithm has a good congestion control ability.
引文
[1]John Risson, Tim Moors. Survey of Research towards Robust Peer-to-Peer Networks. In:Computer Networks, December 2006.
[2]余颜峰.P2P网络监控与拓扑发现的关键技术研究.北京工业大学博士学位论文.2007.
[3]Hyojin Park, Jinhong Yang, Juyoung Park.A Survey on Peer-to-Peer Overlay Network Schemes. In:Advanced Communication Technology,Feb 2008.
[4]Napster:http://free.napster.com/
[5]罗杰文.Peer-to-Peer计算综述.中科院计算技术研究所.http://www.intsci.ac.cn/users/luojw/papers/p2p_review.pdf.2005.4.25
[6]Gnutella:http://www.gnutella.com/
[7]RFC3261.http://www.rfc.net.
[8]Sameh El-Ansary, Seif Haridi.An Overview of Structured P2P Overlay Networks. In:http://eprints.sics.se/237/01/elansary-singlespaced.pdf, July 2004.
[9]Secure Hash Standard. In:Federal Information Processing Standards Publication 180-2,2002 August 1.
[10]Ion Stoica, R Morris, D Karger, F Kaashoek etal. Chord:A scalable peer-topeer lookup service for Internet applications. In:Proceedings of ACM SIGCOMM 2001, August 2001. [online]:http://www.pdos.lcs.mit.edu/chord/#pubs
[11]Supriya Krishnamurthy, Sameh El-Ansary, Erik Aurell,Seif Haridi. A Statistical Theory of Chord under Churn. In:The 4th Annual International Workshop on Peer-To-Peer Systems(IPTPS05),Ithaca,NY,USA.2005.
[12]S Ratnasamy, P Francis, M Handley etal. A scalable content addressable network. In:Proceedings of ACM SIGCOMM 2001, August 2001.
[13]A Rowstron,P Druschel. Pastry:Scalable, decentralized object location and routing for large-scale peer-to-peer systems. In:Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany, November 2001.
[14]B Y Zhao, J Kubiatowicz, A Joseph. Tapestry:An infrastructure for fault-tolerant wide-area location and routing. In:Technical Report UCB/CSD-01-1141, University of California at Berkeley, Computer Science Department,2001.
[15]C.G.Plaxton,R.Rajaraman,A.W.Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. In:Theory of Computing Systems, Vol.32 No.3.1999.
[16]Sean Rhea,Chris Wells,Patrick Eaton etal. Maintenance-Free Global Data Storage. In:IEEE Internet Computing, Vol.5,No.5, PP.40-49, September/October, 2001.
[17]RFC文档[EB/OL]. (1993-01) [2006-06-12]. http://oss org.cn/man/develop/rfc /RFC1393.txt.
[18]Junghee Han, David Watson, Farnam Jahanian. Topology Aware Overlay Networks. In:INFOCOM 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies,2005.
[19]Peng Y,Yang M,Dai Y F. Analyze the Impact of User Search Behavior on DHT-based P2P File Sharing System. In:Proceedings of International Workshop on NGI and P2P Systems,October,2006.
[20]Thomas Locher, Stefan Schmid, Roger Wattenhofer. eQuus:A Provably Robust and Locality-Aware Peer-to-Peer System. In:Peer-to-Peer Computing,2006. P2P 2006. Sixth IEEE International Conference.
[21]Le Hai Dao, Jong Won Kim. AChord:Topology-Aware Chord in Anycast-Enabled Networks. In:2006 International Conference on Hybrid Information Technology.
[22]Marcel Waldvogel, Roberto Rinaldi. Efficient TopologyAware Overlay Network. In:ACM SIGCOMM Computer Communication Review,2003.
[23]S.Ratnasamy,S.Shenker,I.Stoica. Routing Algorithms for DHTs:Some
Open Questions. In:Proc.of First International Workshop on Peer-to-Peer Systems(IPTPS'02), Cambridge, USA,2002.
[24]Zhang H,Goel A,Govindan R. Using the Small-world Model to Improve
Freenet Performance. In:Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies,2003.
[25]Duncan J. Watts, Steven H. Strogatz. Colective Dynamics of "Small-world" Networks. In:Nature393,1998:440-042.
[26]Mei Li, Wang-Chien Lee, Anand Sivasubramaniam. Semantic Small World:An Overlay Network for Peer-to-Peer Search. In:Network Protocols,2004.
[27]冯国富,毛莺池,陆桑璐,陈道蓄.SWAPS:一种基于Small World的文件搜索算法.计算机研究与发展,2006,40(3)：33-39.
[28]Xiaoping Sun. SCAN:a small-world structured p2p overlay for multi-dimensional queries. In:WWW 2007:1191-1192.
[29]Ken Y K. Hui,John C S.Lui, David K Y Yau. Small World Overlay P2P Networks. In:Quality of Service,2004. IWQOS 2004. Twelfth IEEE International Workshop.
[30]周晋,陆海明,李衍达.用Small-World设计无组织P2P系统的路由算法.软件学报,2004,15(6)：25-27.
[31]魏文红,李晋聪.一种基于Small+World的P2P覆盖网络的研究.计算机工程与应用,2008,44(3)：19-21
[32]谈杰,李星.网络测量综述.计算机应用研究,2006,23(2)：5-7.
[33]THOMPSON W, KELVIN L. Popular lectures and addresses [M]. In:Bartlett's Familiar Quotations.14th ed. Boston:Little Brown&lo,1968:723.
[34]Kleinberg J. The small-world phenomenon:an algorithmic perspective. In: Cornell Computer Science Technical Report,99-1776,2000.
[35]Matei Ripeanu, Ian Foster. Mapping the Gnutella Network:Macroscopic Properties of Large-Scale Peer-to-Peer Systems. In:IPTPS.Cambridge,MA,USA, 2002.
[36]B.Y.Zhao, L.Huang, J.Stribling, S.C.Rhea etal. Tapestry:A resilient global-scale overlay for service deployment. In:IEEE Journal on Selected Areas in Communications.2004,22(1):41-53.
[37]朱超.P2P网络系统搜索算法研究.哈尔滨工业大学工学硕士学位论文.2007.
[38]Girish Suryanarayana, Richard N. Taylor. A Survey of Trust Management and
Resource Discovery Technologies in Peer-to-Peer Applications. In:ISR Technical Report # UCI-ISR-04-6, July 2004.
[39]曹静霞,杨静,顾君忠.基于推荐策略的P2P资源搜索算法研究与实现.计算机应用,2005,25(8).
[40]郭方方,杨永田.一种非结构化P2P系统搜索算法的研究.哈尔滨工程大学学报,2006,27(1).
[41]Gkantsidis C,Mihail M,Saberi A.Random Walks in Peer-to-Peer Networks. In:IEEE Infocom,2004.
[42]李建春,庄雷,赵宗渠.反馈机制在P2P网络资源搜索中的应用研究.计算机工程与应用,2005,41(4)：26-28.
[43]沈洁,胡金初.P2P搜索新技术：智能搜索技术,微机发展.2005,15(11)：19-22.
[44]陈海涛,龚正虎,黄遵国.一种基于学习的P2P搜索算法.计算机研究与发展,2005,42(9)：16-18.
[45]谢夏,金海,黄瑾,张琴.一种基于网络跳数的网格信息服务机制.小型微型计算机系统,2007,28(3)：20-22.
[46]王东泉,张刚.利用路由索引技术提高Gnutella的性能.微处理机,2006,35(5)：14-17.
[47]M.Mitzenmacher.Compressed bloom filters. In:IEEE/ACM Trans. on Networking,2002,10(5):604-612.
[48]黄道颖,黄建华,庄雷,李祖鹏等.基于主动网络的分布式P2P网络模型.软件学报,2004,15(7)：1081-1089.
[49]黄民肃,向东.无线自组网络中的基于多个支配集的路由协议.计算机应用研究.2007,24(5)：33-36.
[50]Miguel Castro, Peter Druschel, Ayalvadi Ganesh etal. Secure routing for structured peer-to-peer overlay networks. In:Proc. of the 5th Usenix Symposium on Operating Systems Design and Implementation, Boston, MA, December 2002.
[51]Sylvia Ratnasamy,Paul Francis,Mark Handley etal. A scalable content-addressable network. In:Proc.ACM SIGCOMM,2001.
[52]张震.对等网中Chord资源查找算法的研究.计算机工程与应用,2006,40(8)：147-152.
[53]胡志刚等,一种基于Chord的资源定位方法,中南大学学报,2005,36(3)：30-32.
[54]Yang B,Garcia M H. Improving Search in Peer-to-Peer Networks. In: Proceedings of the 22nd IEEE International Conference on Distributed Computing,2002.
[55]P2PSim,http://pdos.csail.mit.edu/p2psim.
[56]张宇,张宏莉.Internet拓扑建模综述.软件学报,2004,15(08)：P1221一1222.
[57]Zegura EW,Calvert KL,Bhattacharjee S. How to model an Internetwork. In: Proc.of the IEEE INFOCOM'96,New York:IEEE Press,1996:594-602.
[58]D. Rubenstein and S. Sahu. An analysis of a simple p2p protocol for flash crowd document retrieval. In:Columbia University, Technical report EE011109-1,November,2001.
[59]A. Stavrou, D. Rubenstein, and S. Sahu. A lightweight, robust p2p system to handle flash crowds. In:IEEE ICNP, November,2002.
[60]Arturo Crespo, Hector Garcia-Molina. Semantic Overlay Networks for P2P Systems. In:Technical Report. Stanford,2003.
[2]余颜峰.P2P网络监控与拓扑发现的关键技术研究.北京工业大学博士学位论文.2007.
[3]Hyojin Park, Jinhong Yang, Juyoung Park.A Survey on Peer-to-Peer Overlay Network Schemes. In:Advanced Communication Technology,Feb 2008.
[4]Napster:http://free.napster.com/
[5]罗杰文.Peer-to-Peer计算综述.中科院计算技术研究所.http://www.intsci.ac.cn/users/luojw/papers/p2p_review.pdf.2005.4.25
[6]Gnutella:http://www.gnutella.com/
[7]RFC3261.http://www.rfc.net.
[8]Sameh El-Ansary, Seif Haridi.An Overview of Structured P2P Overlay Networks. In:http://eprints.sics.se/237/01/elansary-singlespaced.pdf, July 2004.
[9]Secure Hash Standard. In:Federal Information Processing Standards Publication 180-2,2002 August 1.
[10]Ion Stoica, R Morris, D Karger, F Kaashoek etal. Chord:A scalable peer-topeer lookup service for Internet applications. In:Proceedings of ACM SIGCOMM 2001, August 2001. [online]:http://www.pdos.lcs.mit.edu/chord/#pubs
[11]Supriya Krishnamurthy, Sameh El-Ansary, Erik Aurell,Seif Haridi. A Statistical Theory of Chord under Churn. In:The 4th Annual International Workshop on Peer-To-Peer Systems(IPTPS05),Ithaca,NY,USA.2005.
[12]S Ratnasamy, P Francis, M Handley etal. A scalable content addressable network. In:Proceedings of ACM SIGCOMM 2001, August 2001.
[13]A Rowstron,P Druschel. Pastry:Scalable, decentralized object location and routing for large-scale peer-to-peer systems. In:Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany, November 2001.
[14]B Y Zhao, J Kubiatowicz, A Joseph. Tapestry:An infrastructure for fault-tolerant wide-area location and routing. In:Technical Report UCB/CSD-01-1141, University of California at Berkeley, Computer Science Department,2001.
[15]C.G.Plaxton,R.Rajaraman,A.W.Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. In:Theory of Computing Systems, Vol.32 No.3.1999.
[16]Sean Rhea,Chris Wells,Patrick Eaton etal. Maintenance-Free Global Data Storage. In:IEEE Internet Computing, Vol.5,No.5, PP.40-49, September/October, 2001.
[17]RFC文档[EB/OL]. (1993-01) [2006-06-12]. http://oss org.cn/man/develop/rfc /RFC1393.txt.
[18]Junghee Han, David Watson, Farnam Jahanian. Topology Aware Overlay Networks. In:INFOCOM 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies,2005.
[19]Peng Y,Yang M,Dai Y F. Analyze the Impact of User Search Behavior on DHT-based P2P File Sharing System. In:Proceedings of International Workshop on NGI and P2P Systems,October,2006.
[20]Thomas Locher, Stefan Schmid, Roger Wattenhofer. eQuus:A Provably Robust and Locality-Aware Peer-to-Peer System. In:Peer-to-Peer Computing,2006. P2P 2006. Sixth IEEE International Conference.
[21]Le Hai Dao, Jong Won Kim. AChord:Topology-Aware Chord in Anycast-Enabled Networks. In:2006 International Conference on Hybrid Information Technology.
[22]Marcel Waldvogel, Roberto Rinaldi. Efficient TopologyAware Overlay Network. In:ACM SIGCOMM Computer Communication Review,2003.
[23]S.Ratnasamy,S.Shenker,I.Stoica. Routing Algorithms for DHTs:Some
Open Questions. In:Proc.of First International Workshop on Peer-to-Peer Systems(IPTPS'02), Cambridge, USA,2002.
[24]Zhang H,Goel A,Govindan R. Using the Small-world Model to Improve
Freenet Performance. In:Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies,2003.
[25]Duncan J. Watts, Steven H. Strogatz. Colective Dynamics of "Small-world" Networks. In:Nature393,1998:440-042.
[26]Mei Li, Wang-Chien Lee, Anand Sivasubramaniam. Semantic Small World:An Overlay Network for Peer-to-Peer Search. In:Network Protocols,2004.
[27]冯国富,毛莺池,陆桑璐,陈道蓄.SWAPS:一种基于Small World的文件搜索算法.计算机研究与发展,2006,40(3)：33-39.
[28]Xiaoping Sun. SCAN:a small-world structured p2p overlay for multi-dimensional queries. In:WWW 2007:1191-1192.
[29]Ken Y K. Hui,John C S.Lui, David K Y Yau. Small World Overlay P2P Networks. In:Quality of Service,2004. IWQOS 2004. Twelfth IEEE International Workshop.
[30]周晋,陆海明,李衍达.用Small-World设计无组织P2P系统的路由算法.软件学报,2004,15(6)：25-27.
[31]魏文红,李晋聪.一种基于Small+World的P2P覆盖网络的研究.计算机工程与应用,2008,44(3)：19-21
[32]谈杰,李星.网络测量综述.计算机应用研究,2006,23(2)：5-7.
[33]THOMPSON W, KELVIN L. Popular lectures and addresses [M]. In:Bartlett's Familiar Quotations.14th ed. Boston:Little Brown&lo,1968:723.
[34]Kleinberg J. The small-world phenomenon:an algorithmic perspective. In: Cornell Computer Science Technical Report,99-1776,2000.
[35]Matei Ripeanu, Ian Foster. Mapping the Gnutella Network:Macroscopic Properties of Large-Scale Peer-to-Peer Systems. In:IPTPS.Cambridge,MA,USA, 2002.
[36]B.Y.Zhao, L.Huang, J.Stribling, S.C.Rhea etal. Tapestry:A resilient global-scale overlay for service deployment. In:IEEE Journal on Selected Areas in Communications.2004,22(1):41-53.
[37]朱超.P2P网络系统搜索算法研究.哈尔滨工业大学工学硕士学位论文.2007.
[38]Girish Suryanarayana, Richard N. Taylor. A Survey of Trust Management and
Resource Discovery Technologies in Peer-to-Peer Applications. In:ISR Technical Report # UCI-ISR-04-6, July 2004.
[39]曹静霞,杨静,顾君忠.基于推荐策略的P2P资源搜索算法研究与实现.计算机应用,2005,25(8).
[40]郭方方,杨永田.一种非结构化P2P系统搜索算法的研究.哈尔滨工程大学学报,2006,27(1).
[41]Gkantsidis C,Mihail M,Saberi A.Random Walks in Peer-to-Peer Networks. In:IEEE Infocom,2004.
[42]李建春,庄雷,赵宗渠.反馈机制在P2P网络资源搜索中的应用研究.计算机工程与应用,2005,41(4)：26-28.
[43]沈洁,胡金初.P2P搜索新技术：智能搜索技术,微机发展.2005,15(11)：19-22.
[44]陈海涛,龚正虎,黄遵国.一种基于学习的P2P搜索算法.计算机研究与发展,2005,42(9)：16-18.
[45]谢夏,金海,黄瑾,张琴.一种基于网络跳数的网格信息服务机制.小型微型计算机系统,2007,28(3)：20-22.
[46]王东泉,张刚.利用路由索引技术提高Gnutella的性能.微处理机,2006,35(5)：14-17.
[47]M.Mitzenmacher.Compressed bloom filters. In:IEEE/ACM Trans. on Networking,2002,10(5):604-612.
[48]黄道颖,黄建华,庄雷,李祖鹏等.基于主动网络的分布式P2P网络模型.软件学报,2004,15(7)：1081-1089.
[49]黄民肃,向东.无线自组网络中的基于多个支配集的路由协议.计算机应用研究.2007,24(5)：33-36.
[50]Miguel Castro, Peter Druschel, Ayalvadi Ganesh etal. Secure routing for structured peer-to-peer overlay networks. In:Proc. of the 5th Usenix Symposium on Operating Systems Design and Implementation, Boston, MA, December 2002.
[51]Sylvia Ratnasamy,Paul Francis,Mark Handley etal. A scalable content-addressable network. In:Proc.ACM SIGCOMM,2001.
[52]张震.对等网中Chord资源查找算法的研究.计算机工程与应用,2006,40(8)：147-152.
[53]胡志刚等,一种基于Chord的资源定位方法,中南大学学报,2005,36(3)：30-32.
[54]Yang B,Garcia M H. Improving Search in Peer-to-Peer Networks. In: Proceedings of the 22nd IEEE International Conference on Distributed Computing,2002.
[55]P2PSim,http://pdos.csail.mit.edu/p2psim.
[56]张宇,张宏莉.Internet拓扑建模综述.软件学报,2004,15(08)：P1221一1222.
[57]Zegura EW,Calvert KL,Bhattacharjee S. How to model an Internetwork. In: Proc.of the IEEE INFOCOM'96,New York:IEEE Press,1996:594-602.
[58]D. Rubenstein and S. Sahu. An analysis of a simple p2p protocol for flash crowd document retrieval. In:Columbia University, Technical report EE011109-1,November,2001.
[59]A. Stavrou, D. Rubenstein, and S. Sahu. A lightweight, robust p2p system to handle flash crowds. In:IEEE ICNP, November,2002.
[60]Arturo Crespo, Hector Garcia-Molina. Semantic Overlay Networks for P2P Systems. In:Technical Report. Stanford,2003.