基于SkipNet的副本框架模型研究
摘要
近年来,云计算受到了很多关注,但是云计算本身的复杂性给资源的副本管理带来了巨大的挑战。目前很多研究者对P2P底层覆盖网络进行了研究,将结点和资源进行有效的管理和分配,取得了很好的效果。因此,在未来,云计算技术与P2P的某些技术结合起来将成为一种可能。
在网络应用对响应速度要求越来越高的背景下,本文研究的问题主要是在原有的P2P底层覆盖网络上将资源进行合理分配和管理,对查询请求作出快速响应,使其能用到云环境中。具体工作为：首先,结合P2P中的SkipNet覆盖网络和康奈尔大学提出的Beehive模型的优势,提出了一个基于SkipNet的副本框架模型,根据资源的流行度,计算出应该复制的副本数量,并将副本放置到恰当的结点上。当资源的流行度发生变化时,能对资源副本的数量和位置进行有效的调整,同时,能根据用户的查询选用不同的查询算法做出快速响应。其次,对基于SkipNet的副本框架结构进行了合理设计,详细阐述了基于SkipNet的拓扑结构和副本框架结构,在此基础上,提出了一套基于SkipNet的副本框架模型运行机制,对资源的调整、加入、查询、更新、删除和结点的加入、离开流程等进行了具体阐述。最后,使用PeerSim对该副本框架进行了仿真、验证和分析。
据统计,当前的大多数查询遵行幂律分布,实验结果表明,该副本框架能够对查询做出快速响应,查询平均时间复杂度由O(logN)降至O(1),即使当幂律分布中的齐夫参数发生变化时,使用该副本框架进行查询也能达到很好的效果。该模型为云计算中进行副本管理提供了有效的解决方案。
In recent years, cloud computing is a very hot topic. But the complexity of it brings us a big challenge to manage the replicas of the objects. Researchers have also been dedicated to the research of P2P overlay network, and have succeeded in managing nodes and distributing objects. So, in the future, it's possible to combine cloud computing and some of the P2P techniques to provide a better service for users.
Many network applications nowadays need quicker and quicker response speed, and this thesis is aimed at distributing and managing objects effectively on existed P2P overlay network, by which we can get good lookup performance for applications. We hope it can be used in cloud environment. Detailed work is:Firstly, by taking full advantage of SkipNet overlay network and Beehive model proposed by Cornell University, we proposed a SkipNet-based replicas framework model. In this model, we can calculate the number of replicas we should replicate and distribute the replicas on proper nodes according to the popularity of the object. When the popularity changes, the model can adjust the number and position of the replicas. It can also choose different lookup algorithm according to user's query. Secondly, we designed the SkipNet-based replication framework model reasonably and elaborated the topology of SkipNet and the structure of replication framework. We also proposed the operation mechanism of the model, for example, the adjustment, join, query, update and deletion of the replicas, the join and departure of node and so on. Thirdly, we use PeerSim to simulate, test and analyze the replication framework.
According to statistics, most of the queries obey power-law distribution. The results show that in average case, this replication framework achieves O(1)lookup performance even when the Zipf-parameter changes, which provides an effective solution to manage replicas in cloud environment.
在网络应用对响应速度要求越来越高的背景下,本文研究的问题主要是在原有的P2P底层覆盖网络上将资源进行合理分配和管理,对查询请求作出快速响应,使其能用到云环境中。具体工作为：首先,结合P2P中的SkipNet覆盖网络和康奈尔大学提出的Beehive模型的优势,提出了一个基于SkipNet的副本框架模型,根据资源的流行度,计算出应该复制的副本数量,并将副本放置到恰当的结点上。当资源的流行度发生变化时,能对资源副本的数量和位置进行有效的调整,同时,能根据用户的查询选用不同的查询算法做出快速响应。其次,对基于SkipNet的副本框架结构进行了合理设计,详细阐述了基于SkipNet的拓扑结构和副本框架结构,在此基础上,提出了一套基于SkipNet的副本框架模型运行机制,对资源的调整、加入、查询、更新、删除和结点的加入、离开流程等进行了具体阐述。最后,使用PeerSim对该副本框架进行了仿真、验证和分析。
据统计,当前的大多数查询遵行幂律分布,实验结果表明,该副本框架能够对查询做出快速响应,查询平均时间复杂度由O(logN)降至O(1),即使当幂律分布中的齐夫参数发生变化时,使用该副本框架进行查询也能达到很好的效果。该模型为云计算中进行副本管理提供了有效的解决方案。
In recent years, cloud computing is a very hot topic. But the complexity of it brings us a big challenge to manage the replicas of the objects. Researchers have also been dedicated to the research of P2P overlay network, and have succeeded in managing nodes and distributing objects. So, in the future, it's possible to combine cloud computing and some of the P2P techniques to provide a better service for users.
Many network applications nowadays need quicker and quicker response speed, and this thesis is aimed at distributing and managing objects effectively on existed P2P overlay network, by which we can get good lookup performance for applications. We hope it can be used in cloud environment. Detailed work is:Firstly, by taking full advantage of SkipNet overlay network and Beehive model proposed by Cornell University, we proposed a SkipNet-based replicas framework model. In this model, we can calculate the number of replicas we should replicate and distribute the replicas on proper nodes according to the popularity of the object. When the popularity changes, the model can adjust the number and position of the replicas. It can also choose different lookup algorithm according to user's query. Secondly, we designed the SkipNet-based replication framework model reasonably and elaborated the topology of SkipNet and the structure of replication framework. We also proposed the operation mechanism of the model, for example, the adjustment, join, query, update and deletion of the replicas, the join and departure of node and so on. Thirdly, we use PeerSim to simulate, test and analyze the replication framework.
According to statistics, most of the queries obey power-law distribution. The results show that in average case, this replication framework achieves O(1)lookup performance even when the Zipf-parameter changes, which provides an effective solution to manage replicas in cloud environment.
引文
[1]刘鹏.云计算(第二版).北京：电子工业出版社,2011.
[2]朱近之.智慧的云计算---物联网的平台(第二版).北京：电子工业出版社,2011.
[3]George Coulouris, Jean Dollimore, Tim Kindberg著,金蓓弘,曹冬磊等译.分布式系统概念与设计[M].北京：机械工业出版社,2008.
[4]Nicholas J.A. Harvey,John Dunagan. SkipNet:A Scalable Overlay Network with Practical Locality Properties[C]. USITS'03 Proceedings of the 4th conference on USENIX Sysposium on Internet Technologies and Systems,2003,4.
[5]Benugopalan Ramasubramanian, Emin Gun Sirer. Beehive:O(1)Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays[C]. NSDI'04 Proceedings of the 1 st conference on Symposium on Networked Systems Design and Implementation,2004,1.
[6]William Pugh. Skip Lists:A Probabilistic Alternative to Balanced Trees[M]. Communications of the ACM,1990,33.
[7]leeing.PeerSim中文教程[EB/01.].http://leeing.org/peersim-turtorial-analyse-of-cycle-based-model/,2010-06-30.
[8]Adina Crainiceanu, Prakash Linga, Ashwin Machanavajjhala. Load Balancing and Range Queries in P2P Systems Using P-Ring[J]. ACM Transactions on Internet Technology(TOIT),2011.
[9]Gyorgy Dan, Niklas Carlsson. Power-law revisited:large scale measurement study of P2P content popularity[J]. In Proceedings of IPTPS.2010,12-21.
[10]Weixiong Rao. Optimal Resource Placement in Structured Peer-to-Peer Networks[C].IEEE Transaction on Parallel and Distributed System,2010.
[11]段鹏.跨频道P2P流媒体模型研究[D].云南,云南大学,2010.
[12]丁天亮.基于声誉的P2P信任模型研究[D].云南,云南大学,2009.
[13]朴冬临.基于SkipNet的P2P-SIP系统研究与设计[D].北京,北京邮电大学,2008.
[14]TingjianGe, Stan Zdonik. A Skip-list Approach for Efficiently Processing Forecasting Queries[J]. Proceedings of the VLDB Endowment,2008,1.
[15]James Aspnes, Gauri Shah. Skip graphs[J]. ACM Transactions on Algorithms(TALG),2007,3.
[16]Lars Arge, David Eppstein, Michael T. Goodrich. Skip-Webs:Efficient Distributed Data Structures for Multi-Dimensional Data Sets[C]. Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing,2005.
[17]ArvindKrisnamuthy. Structured and Unstructured Overlays for Distributed Data[EB/01]. http://wenku.baidu.com/view/4ecce83710661ed9ad51f3e1.html,2011-02-24.
[18]Les Houches. Distributed Indexing[M].Britain:Cambridge University Press,2010.
[19]Shinji Tsuboi, Tomoteru Oku, Masaaki Ohnishi, Shinichi Ueshima. Generating Skip Delaunay Network for P2P Geocasting[C].the Sixth International Conference on Creating, Connecting and Collaborating through Computer,2008.
[20]M.Ripeanu.Peer-to-peer Architecture Case Study:Gnutella. Proceeding of International Conference on P2P Computing,2001.
[21]A.Rowstorn, P.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),2001.
[22]I.Stoica, R.Morris, D.Karger, etc. Chord:A Scalable Peer-to-peer Lookup Service for Internet Applications. Proceeding of ACM SIGCOMM 2001, San Diego, California, USA,2001.
[23]Fay Chang, Jeffrey Dean. Bigtable:A Distributed Storage System for Structured Data[J]. ACM TOCS,2008,26.
[24]Jeffrey Dean, SanayGhemawat.MapReduce:simplified data processing on large clusters[M]. Communications of the ACM-50th anniversary issue:1958-2008,2008,51.
[25]Sanjay Ghemawat, Howard Gobioff. The Google file system[J]. ACM SIGOPS Operating Systems Review-SOSP'03,2003,37.
[26]Masanori Bando, H. Jonathan Chao. FlashTrie:Hash-based Prefix-CompreesedTrie for IP Route Lookup Beyond 100Gbps[C].29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 2010.
[27]Michael J. Freedman, RadekVingralek. Efficient Peer-to-Peer Lookup Based on a Distributed Trie[J]. In Proceedings of IPTPS.2002,66-75.
[28]SriramRamabhadran, Sylvia Ratnasamy. Prefix Hash Tree:An Indexing Data Structure over Distributed Hash Table[EB/01]. http://citeseerx.ist.psu.edu,2004.
[29]Jiannan Wang, JianhuaFeng, Guoliang Li. Trie-Join:Efficient Trie-based String Similarity Joins with Edit-Distance Constraints[J]. the VLDB Endowment,2010,3.
[30]StrahilRistov. LZ trie and dictionary compression[J].Software-Practice&Experience,2005,35.
[31]Florin Dragan, Georges Gardarin, Laurent Yeh. Routing XQuery in A P2P Network Using Adaptable Trie-Indexes[EB/01]. http://citeseerx.ist.psu.edu,2004.
[32]Sebastian Kniesburges, Christian Scheideler. Hashed Patricia Trie:Efficient Longest Prefix Matching in Peer-to-Peer System[C].the 5th international conference on WALCOM:algorithms and computation,2011.
[2]朱近之.智慧的云计算---物联网的平台(第二版).北京：电子工业出版社,2011.
[3]George Coulouris, Jean Dollimore, Tim Kindberg著,金蓓弘,曹冬磊等译.分布式系统概念与设计[M].北京：机械工业出版社,2008.
[4]Nicholas J.A. Harvey,John Dunagan. SkipNet:A Scalable Overlay Network with Practical Locality Properties[C]. USITS'03 Proceedings of the 4th conference on USENIX Sysposium on Internet Technologies and Systems,2003,4.
[5]Benugopalan Ramasubramanian, Emin Gun Sirer. Beehive:O(1)Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays[C]. NSDI'04 Proceedings of the 1 st conference on Symposium on Networked Systems Design and Implementation,2004,1.
[6]William Pugh. Skip Lists:A Probabilistic Alternative to Balanced Trees[M]. Communications of the ACM,1990,33.
[7]leeing.PeerSim中文教程[EB/01.].http://leeing.org/peersim-turtorial-analyse-of-cycle-based-model/,2010-06-30.
[8]Adina Crainiceanu, Prakash Linga, Ashwin Machanavajjhala. Load Balancing and Range Queries in P2P Systems Using P-Ring[J]. ACM Transactions on Internet Technology(TOIT),2011.
[9]Gyorgy Dan, Niklas Carlsson. Power-law revisited:large scale measurement study of P2P content popularity[J]. In Proceedings of IPTPS.2010,12-21.
[10]Weixiong Rao. Optimal Resource Placement in Structured Peer-to-Peer Networks[C].IEEE Transaction on Parallel and Distributed System,2010.
[11]段鹏.跨频道P2P流媒体模型研究[D].云南,云南大学,2010.
[12]丁天亮.基于声誉的P2P信任模型研究[D].云南,云南大学,2009.
[13]朴冬临.基于SkipNet的P2P-SIP系统研究与设计[D].北京,北京邮电大学,2008.
[14]TingjianGe, Stan Zdonik. A Skip-list Approach for Efficiently Processing Forecasting Queries[J]. Proceedings of the VLDB Endowment,2008,1.
[15]James Aspnes, Gauri Shah. Skip graphs[J]. ACM Transactions on Algorithms(TALG),2007,3.
[16]Lars Arge, David Eppstein, Michael T. Goodrich. Skip-Webs:Efficient Distributed Data Structures for Multi-Dimensional Data Sets[C]. Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing,2005.
[17]ArvindKrisnamuthy. Structured and Unstructured Overlays for Distributed Data[EB/01]. http://wenku.baidu.com/view/4ecce83710661ed9ad51f3e1.html,2011-02-24.
[18]Les Houches. Distributed Indexing[M].Britain:Cambridge University Press,2010.
[19]Shinji Tsuboi, Tomoteru Oku, Masaaki Ohnishi, Shinichi Ueshima. Generating Skip Delaunay Network for P2P Geocasting[C].the Sixth International Conference on Creating, Connecting and Collaborating through Computer,2008.
[20]M.Ripeanu.Peer-to-peer Architecture Case Study:Gnutella. Proceeding of International Conference on P2P Computing,2001.
[21]A.Rowstorn, P.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),2001.
[22]I.Stoica, R.Morris, D.Karger, etc. Chord:A Scalable Peer-to-peer Lookup Service for Internet Applications. Proceeding of ACM SIGCOMM 2001, San Diego, California, USA,2001.
[23]Fay Chang, Jeffrey Dean. Bigtable:A Distributed Storage System for Structured Data[J]. ACM TOCS,2008,26.
[24]Jeffrey Dean, SanayGhemawat.MapReduce:simplified data processing on large clusters[M]. Communications of the ACM-50th anniversary issue:1958-2008,2008,51.
[25]Sanjay Ghemawat, Howard Gobioff. The Google file system[J]. ACM SIGOPS Operating Systems Review-SOSP'03,2003,37.
[26]Masanori Bando, H. Jonathan Chao. FlashTrie:Hash-based Prefix-CompreesedTrie for IP Route Lookup Beyond 100Gbps[C].29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 2010.
[27]Michael J. Freedman, RadekVingralek. Efficient Peer-to-Peer Lookup Based on a Distributed Trie[J]. In Proceedings of IPTPS.2002,66-75.
[28]SriramRamabhadran, Sylvia Ratnasamy. Prefix Hash Tree:An Indexing Data Structure over Distributed Hash Table[EB/01]. http://citeseerx.ist.psu.edu,2004.
[29]Jiannan Wang, JianhuaFeng, Guoliang Li. Trie-Join:Efficient Trie-based String Similarity Joins with Edit-Distance Constraints[J]. the VLDB Endowment,2010,3.
[30]StrahilRistov. LZ trie and dictionary compression[J].Software-Practice&Experience,2005,35.
[31]Florin Dragan, Georges Gardarin, Laurent Yeh. Routing XQuery in A P2P Network Using Adaptable Trie-Indexes[EB/01]. http://citeseerx.ist.psu.edu,2004.
[32]Sebastian Kniesburges, Christian Scheideler. Hashed Patricia Trie:Efficient Longest Prefix Matching in Peer-to-Peer System[C].the 5th international conference on WALCOM:algorithms and computation,2011.