基于Chord和Binary Tree混合层次P2P网络结构研究
|
摘要
随着P2P技术的飞速发展,基于它的分布式应用已渗透到很多领域。P2P的分布式应用需要P2P网络结构的支撑,因此P2P网络结构的研究具有非常重要的意义。目前已有的P2P网络结构主要分为非结构化和结构化,非结构化P2P网络组织简单,稳定性好,但查询效率不高且不支持负载平衡;结构化P2P网络查询效率高,支持负载平衡,但并不适用于节点高度动态的网络,为了维护系统逻辑拓扑结构,节点频繁的加入离开以及失效都会造成系统的维护代价急剧加大。
本文在分析了各种P2P网络结构的基础上设计了一种混合层次P2P网络结构(HCBT—Chord and Binary Tree Based Hybrid Hierarchical Network)。在这个网络结构中,上层网络采用Chord结构,引入虚拟节点的概念并用Chord协议进行组织,同时根据需要对现行的Chord协议进行了改进和补充;下层网络采用二叉树结构,引入超级节点。根据节点的能力,把节点组织成二叉树,然后通过堆选举算法选举出超级节点,通过超级节点来组织和管理下层二叉树网络。实验表明,HCBT网络结构具有可扩展性、查询效率高、负载均衡和稳定性好等特点,适用于高动态的网络环境。
P2P存储是P2P技术的应用之一,P2P存储系统中每个节点随时都可能暂时或永久离开系统,系统中的节点均负责存储数据。一旦某节点暂时离开,该节点上存储的数据就将暂时不可访问,而节点的永久离开更会造成数据的丢失。这使得构建P2P存储系统极富挑战性。本文以HCBT网络结构为支撑,设计了一个简单的P2P数据存储模型HCBT-Store,旨在解决高动态P2P环境中的数据持久存储的问题。
Along with the technical and theoretic development of P2P, the distributed applications built on it have been used in many fields. The distributed applications of P2P are supported by structures of P2P network. So research of the structure is very important. Now unstructured and structured network are two typical structures in P2P network. Unstructured P2P network has organized simply. It has high stability, but has low efficiency and unsupported load balance. Structured P2P network has high efficiency and supported load balance, but it isn't suitable for high dynamic network. And when the nodes join and leave frequently, the cost of maintenance is very high.
This paper proposes a hybrid hierarchical P2P network (HCBT- Chord and Binary Tree Hybrid Hierarchical P2P Network) by analyzing many P2P network structures. In the network structure, the upper layer is structured network with chord protocol, which introduces virtual peer notion and improves chord protocol. The lower layer is binary tree network, which introduces super peer notion. Super peers which organize and manage the binary tree network are selected by heap selection algorithm. The experiment indicates that it has scalability and high efficiency and stability and supported load balance, and it is suitable for dynamic network environment.
P2P storage is one of the P2P technical applications. Every node in the P2P storage system which stores some data leaves temporarily or forever, which induces that some data can't be obtained. So it is defiant when P2P storage system is designed. This paper designs a simple P2P storage model (HCBT-Store), which can keep data durability storage.
本文在分析了各种P2P网络结构的基础上设计了一种混合层次P2P网络结构(HCBT—Chord and Binary Tree Based Hybrid Hierarchical Network)。在这个网络结构中,上层网络采用Chord结构,引入虚拟节点的概念并用Chord协议进行组织,同时根据需要对现行的Chord协议进行了改进和补充;下层网络采用二叉树结构,引入超级节点。根据节点的能力,把节点组织成二叉树,然后通过堆选举算法选举出超级节点,通过超级节点来组织和管理下层二叉树网络。实验表明,HCBT网络结构具有可扩展性、查询效率高、负载均衡和稳定性好等特点,适用于高动态的网络环境。
P2P存储是P2P技术的应用之一,P2P存储系统中每个节点随时都可能暂时或永久离开系统,系统中的节点均负责存储数据。一旦某节点暂时离开,该节点上存储的数据就将暂时不可访问,而节点的永久离开更会造成数据的丢失。这使得构建P2P存储系统极富挑战性。本文以HCBT网络结构为支撑,设计了一个简单的P2P数据存储模型HCBT-Store,旨在解决高动态P2P环境中的数据持久存储的问题。
Along with the technical and theoretic development of P2P, the distributed applications built on it have been used in many fields. The distributed applications of P2P are supported by structures of P2P network. So research of the structure is very important. Now unstructured and structured network are two typical structures in P2P network. Unstructured P2P network has organized simply. It has high stability, but has low efficiency and unsupported load balance. Structured P2P network has high efficiency and supported load balance, but it isn't suitable for high dynamic network. And when the nodes join and leave frequently, the cost of maintenance is very high.
This paper proposes a hybrid hierarchical P2P network (HCBT- Chord and Binary Tree Hybrid Hierarchical P2P Network) by analyzing many P2P network structures. In the network structure, the upper layer is structured network with chord protocol, which introduces virtual peer notion and improves chord protocol. The lower layer is binary tree network, which introduces super peer notion. Super peers which organize and manage the binary tree network are selected by heap selection algorithm. The experiment indicates that it has scalability and high efficiency and stability and supported load balance, and it is suitable for dynamic network environment.
P2P storage is one of the P2P technical applications. Every node in the P2P storage system which stores some data leaves temporarily or forever, which induces that some data can't be obtained. So it is defiant when P2P storage system is designed. This paper designs a simple P2P storage model (HCBT-Store), which can keep data durability storage.
引文
[1]杨天路,刘宇宏,张文,原毅强,龙紫薇,魏小康。P2P网络技术原理与系统丌发案例.第1版.北京:人民邮电出版社,2007
[2]陈贵海,李振华.对等网络:结构、应用与设计。第1版。北京:清华大学出版社,2007
[3]严蔚敏,吴伟民.数据结构(C语言版).第1版.北京:清华大学出版社,1997
[4]郑纬民等.对等计算研究概论.清华大学计算机科学与技术系高性能计算研究所,2005
[5]罗杰文.Peer to Peer(P2P)综述.中科院计算技术研究所。2005
[6]Gallaugher J.M,Ramanathan S.C:Choosing a Clie nt/Server Architecture.Information Systems Management,1996,13(2):7-13
[7]W.Litwin,M.A.Neimat,D.A.LH Schneider.A Scaleable,Distributed Data Structure,ACM Transactions on Database Systems(TODS)21,4(1996),480C522,1996
[8]Tian J,Dai YF.Study on durable peer-to-peer storage techniques.Journal of softeware,2007,18(6):1379-1399
[9]Lv E,Duan Z,Qi J,et al.Incorporating clusters into hybrid P2P network.IEEE First International Conference on the Digital Society,Guadeloupe,French Caribbean,Jan.:2007
[10]Li Xiao,Zhuang Z,Liu Y.Dynamic layer management in superpeer architectures.IEEE Proceedings of the 2004 International Conference on Parallel Processing,2004
[11]Yuh-Jzer Joung,Joung,Jiaw-Chang Wang.Chord~2.A two-layer Chord for reducing maintenance overhead via heterogeneity.Computer Networks 51(2007):712-731
[12]Chao Xie,Guihai Chen,Art Vandenberg,Yi Pan.Analysis of hybrid P2P overlay netwok topology.Computer Communication 31(2008):190-200
[13]Berverly Yang,Hector Garcia-Molina.Comparing Hybrid Peer-to-Peer Systems.Stanford University Stanford,CA,USA.2006
[14]Berverly Yang,Hector Garcia-Molina.Designing a Super-Peer Network.Computer Science Department,Stanford University.2005
[15]Napster,http://www.Napster.com
[16]Gnutella,http://www.Gnutella.com
[17]Kazaa,http://www.kazaa.com
[18]唐辉,张国杰,黄建华.一种混合P2P网络模型设计与研究.计算机应用2005,25(3):521-524
[19]田敬,张大为,代亚非,韩华.ESStore:P2P网络的可靠存储协议.全国网络与信息 安全技术研讨会.2005
[20]高乾,杨智,田敬,代亚非.一种分层次的差异型P2P存储体系.软件学报
[21]C.Blake,R.Rodrigues.High availability,scalable storage,dynamic peer networks.In Proc.9~th HotOS,2003
[22]Edith Cohen,Amos Fiat,Haim Kaplan.Associative search in peer to peer network:harness latent semanitcs.Proceedings of INFOCOM'03 Conferernce.2003
[23]Annextein FS.Berman KA,Jovanovic MA,etal.Indexing Techniques for File Sharing in Scalable Peer-to-Peer Networks.Proceedings IEEE ICCCN.2003
[24]周晋,李衍达等.基于Small-World网络的非结构化DHT算法.国家自然科学基金项目(60003004).2005
[25]Freenet,http://freenet.sourceforge.net/
[26]于昊,余风,张忠能.基于Power-Law原则的P2P实现。计算机应用与软件第23卷第6期.2006
[27]Peng Z,Duan Z,Qi J,et al.HP2P:a hybrid hierarchical P2P network.IEEE First International Conference on the Digital Society,Guadeloupe,French Caribbean,Jan:2007
[28]Stoica I,Morris R,Karger D,Kaashoek M,Balakrishnan H.Chord:A scalable peer-to-peer lookup service for internet applications.Annual conference of the special Interest Group on Data Communication(SIGCOMM 2001).August 2001
[29]Zhao B,Kubiatowicz J,Joseph A.Tapestry:An infrastructure for fault-tolerant wide-area location and routing.Technical Report,USB//CSD-01-1141,Berkeley Computer Science Division,University of Calofonia,2001
[30]Ratnasamy,Francis P,Handley M,Karp R,Shenker S.A Scalable Content-Addressable Network.Annual conference of the Special Interest Group on Data Communication(SIGCOMM 2001).August 2001
[31]Rowstron A,Druschel P.Pastry:a scalable,distributed object location and routing for large-scale peer-to-peer systems,ln:Proc,of the Int'l Conf.on Distributed System Platforms(Middleware).2001.329-350
[32]Maymounkov P,Mazieres D.Kademlia:A peer-to-peer information system based on the XOR metric.In:Proc.of the 1~(st)Int'l Workshop on Peer-to-Peer Systems.2002,258-263
[33]Wells C.The oceanstore archive:Goals,structures,and self-repair[MS Thesis].UC Berkeley:University of California.2002
[34]Rhea S,Eaton P,Geels D,Weatherspoon H,Zhao B,Kubiatowicz J.Pond:The OceanStore prototype.In:Proc.of the 2~(nd)USENIX Conf.on File and Storage Technologies.2003,1-14
[35]Bhagwan R,Tati K,Cheng Y,Savage S,Voelker G..Total recall:System support for automated availability management.In:Procoof the 1~(st)ACM/USenix Syrup On Networked Systems Design and Implementation.2004
[36]Zheng W,Hu J,Li M.Granary:Architecture.of object oriented Internet storage service.In:Proc.of the IEEE Int'l Conf.on E-Commerce Technology for Dynamic E-Business.2004.294-297
[37]Hu J,Li M,Zheng W,Wang D,Ning N,Dong H.SmartBoa:Constructing P2P overlay network in the heterogeneous Internet using irregular routing tables,In:Proc.of the 3~(rd)Int'l Workshop on Peer-to-Peer Systems.2004
[38]Upstore.2006.http://upstore.grids.cn
[39]Lunar.2005.http://maze.pku.edu.cn/lunar.htm
[40]Cao Shu-sheng,Yin Wei,Chen Xing-yio A robust cluster-based dynamic-super-node scheme for hybrid peer-to-peer network.The journal of China universities of posts and telecommunications.13(2007)
[41]Hakim weatherspoon,John D.Kubiatowiczo2002.Erasure Coding vs.Replication:A Quantitative Comparison.In:IPTPS'02,LNCS 2429,SpringerVerlag,328-338
[42]田祥宏.基于Chord的P2P网络分层资源定位模型。计算机时代。2008,第一期
[43]徐传富,陈海涛.基于DHT的层次式P2P资源定位模型[J]。计算机工程与应用,2004.18
[44]蔡雄.用Java实现P2P网络模型[J].计算机应用与软件,2006.4
[45]PeerSim:http://peersim.sourceforge.net/
[46]北京大学网络实验室网络系统组:http://net.pku.edu.cn/～p2p
[47]P2PSim:http://pdos.csail.mit.edu/p2psim/
[48]SETI@Home:http://setiathome.ssl.berkeley.edu
[49]Luigi Rizzo.Effective Erasure Codes for Reliable Computer Communication Protocols.ACM Computer Communication Review.1997,27(2):24-36
[50]Rodrigo Rodrigues,Barbara Liskov.High Availability in DHTs:Erasure Coding vs.Replication.In:IPTPS'05,226-239
[51]R.Bhagwan,S Savate,G Voelker.Replication strategies for highly available peer-to-peer storage systems.Technical Report CS2002-0726,UCSD,2002
[52]C Blake and R Rodrigues.High availability,scalable storage,dynamic peer networks:Pick two.In Proceedings of HotOS.2003
[2]陈贵海,李振华.对等网络:结构、应用与设计。第1版。北京:清华大学出版社,2007
[3]严蔚敏,吴伟民.数据结构(C语言版).第1版.北京:清华大学出版社,1997
[4]郑纬民等.对等计算研究概论.清华大学计算机科学与技术系高性能计算研究所,2005
[5]罗杰文.Peer to Peer(P2P)综述.中科院计算技术研究所。2005
[6]Gallaugher J.M,Ramanathan S.C:Choosing a Clie nt/Server Architecture.Information Systems Management,1996,13(2):7-13
[7]W.Litwin,M.A.Neimat,D.A.LH Schneider.A Scaleable,Distributed Data Structure,ACM Transactions on Database Systems(TODS)21,4(1996),480C522,1996
[8]Tian J,Dai YF.Study on durable peer-to-peer storage techniques.Journal of softeware,2007,18(6):1379-1399
[9]Lv E,Duan Z,Qi J,et al.Incorporating clusters into hybrid P2P network.IEEE First International Conference on the Digital Society,Guadeloupe,French Caribbean,Jan.:2007
[10]Li Xiao,Zhuang Z,Liu Y.Dynamic layer management in superpeer architectures.IEEE Proceedings of the 2004 International Conference on Parallel Processing,2004
[11]Yuh-Jzer Joung,Joung,Jiaw-Chang Wang.Chord~2.A two-layer Chord for reducing maintenance overhead via heterogeneity.Computer Networks 51(2007):712-731
[12]Chao Xie,Guihai Chen,Art Vandenberg,Yi Pan.Analysis of hybrid P2P overlay netwok topology.Computer Communication 31(2008):190-200
[13]Berverly Yang,Hector Garcia-Molina.Comparing Hybrid Peer-to-Peer Systems.Stanford University Stanford,CA,USA.2006
[14]Berverly Yang,Hector Garcia-Molina.Designing a Super-Peer Network.Computer Science Department,Stanford University.2005
[15]Napster,http://www.Napster.com
[16]Gnutella,http://www.Gnutella.com
[17]Kazaa,http://www.kazaa.com
[18]唐辉,张国杰,黄建华.一种混合P2P网络模型设计与研究.计算机应用2005,25(3):521-524
[19]田敬,张大为,代亚非,韩华.ESStore:P2P网络的可靠存储协议.全国网络与信息 安全技术研讨会.2005
[20]高乾,杨智,田敬,代亚非.一种分层次的差异型P2P存储体系.软件学报
[21]C.Blake,R.Rodrigues.High availability,scalable storage,dynamic peer networks.In Proc.9~th HotOS,2003
[22]Edith Cohen,Amos Fiat,Haim Kaplan.Associative search in peer to peer network:harness latent semanitcs.Proceedings of INFOCOM'03 Conferernce.2003
[23]Annextein FS.Berman KA,Jovanovic MA,etal.Indexing Techniques for File Sharing in Scalable Peer-to-Peer Networks.Proceedings IEEE ICCCN.2003
[24]周晋,李衍达等.基于Small-World网络的非结构化DHT算法.国家自然科学基金项目(60003004).2005
[25]Freenet,http://freenet.sourceforge.net/
[26]于昊,余风,张忠能.基于Power-Law原则的P2P实现。计算机应用与软件第23卷第6期.2006
[27]Peng Z,Duan Z,Qi J,et al.HP2P:a hybrid hierarchical P2P network.IEEE First International Conference on the Digital Society,Guadeloupe,French Caribbean,Jan:2007
[28]Stoica I,Morris R,Karger D,Kaashoek M,Balakrishnan H.Chord:A scalable peer-to-peer lookup service for internet applications.Annual conference of the special Interest Group on Data Communication(SIGCOMM 2001).August 2001
[29]Zhao B,Kubiatowicz J,Joseph A.Tapestry:An infrastructure for fault-tolerant wide-area location and routing.Technical Report,USB//CSD-01-1141,Berkeley Computer Science Division,University of Calofonia,2001
[30]Ratnasamy,Francis P,Handley M,Karp R,Shenker S.A Scalable Content-Addressable Network.Annual conference of the Special Interest Group on Data Communication(SIGCOMM 2001).August 2001
[31]Rowstron A,Druschel P.Pastry:a scalable,distributed object location and routing for large-scale peer-to-peer systems,ln:Proc,of the Int'l Conf.on Distributed System Platforms(Middleware).2001.329-350
[32]Maymounkov P,Mazieres D.Kademlia:A peer-to-peer information system based on the XOR metric.In:Proc.of the 1~(st)Int'l Workshop on Peer-to-Peer Systems.2002,258-263
[33]Wells C.The oceanstore archive:Goals,structures,and self-repair[MS Thesis].UC Berkeley:University of California.2002
[34]Rhea S,Eaton P,Geels D,Weatherspoon H,Zhao B,Kubiatowicz J.Pond:The OceanStore prototype.In:Proc.of the 2~(nd)USENIX Conf.on File and Storage Technologies.2003,1-14
[35]Bhagwan R,Tati K,Cheng Y,Savage S,Voelker G..Total recall:System support for automated availability management.In:Procoof the 1~(st)ACM/USenix Syrup On Networked Systems Design and Implementation.2004
[36]Zheng W,Hu J,Li M.Granary:Architecture.of object oriented Internet storage service.In:Proc.of the IEEE Int'l Conf.on E-Commerce Technology for Dynamic E-Business.2004.294-297
[37]Hu J,Li M,Zheng W,Wang D,Ning N,Dong H.SmartBoa:Constructing P2P overlay network in the heterogeneous Internet using irregular routing tables,In:Proc.of the 3~(rd)Int'l Workshop on Peer-to-Peer Systems.2004
[38]Upstore.2006.http://upstore.grids.cn
[39]Lunar.2005.http://maze.pku.edu.cn/lunar.htm
[40]Cao Shu-sheng,Yin Wei,Chen Xing-yio A robust cluster-based dynamic-super-node scheme for hybrid peer-to-peer network.The journal of China universities of posts and telecommunications.13(2007)
[41]Hakim weatherspoon,John D.Kubiatowiczo2002.Erasure Coding vs.Replication:A Quantitative Comparison.In:IPTPS'02,LNCS 2429,SpringerVerlag,328-338
[42]田祥宏.基于Chord的P2P网络分层资源定位模型。计算机时代。2008,第一期
[43]徐传富,陈海涛.基于DHT的层次式P2P资源定位模型[J]。计算机工程与应用,2004.18
[44]蔡雄.用Java实现P2P网络模型[J].计算机应用与软件,2006.4
[45]PeerSim:http://peersim.sourceforge.net/
[46]北京大学网络实验室网络系统组:http://net.pku.edu.cn/～p2p
[47]P2PSim:http://pdos.csail.mit.edu/p2psim/
[48]SETI@Home:http://setiathome.ssl.berkeley.edu
[49]Luigi Rizzo.Effective Erasure Codes for Reliable Computer Communication Protocols.ACM Computer Communication Review.1997,27(2):24-36
[50]Rodrigo Rodrigues,Barbara Liskov.High Availability in DHTs:Erasure Coding vs.Replication.In:IPTPS'05,226-239
[51]R.Bhagwan,S Savate,G Voelker.Replication strategies for highly available peer-to-peer storage systems.Technical Report CS2002-0726,UCSD,2002
[52]C Blake and R Rodrigues.High availability,scalable storage,dynamic peer networks:Pick two.In Proceedings of HotOS.2003