Gnutella网络的路由搜索算法研究
摘要
随着网络计算机系统的飞速发展,信息量越来越庞大,用户对海量信息存储和数据交换、查询、检索等技术和方式的选择越来越重要。为了满足人们对各种类型敏感信息的需求,P2P(Peer–to-Peer)技术应运而生。P2P在对等计算、协同工作、搜索引擎、文件交换等领域有很好的应用前景。在目前的P2P应用模型中,非结构化p2p系统得到了非常广泛的应用。Gnutella是非结构化P2P的网络通信协议,基于Gnutella通信协议的网络叫做Gnutella网络。近年来Cnutella网络发展的非常迅速。但是由于Gnutella网络的资源查询机制采用洪泛策略,从而导致了查询速度慢与查询效果不佳等缺点,限制了P2P网络的进一步发展。如何管理网络连接、实施高效的搜索算法、减少冗余消息、增加搜索的查准率、解决Gnutella网络的可扩展性对该网络的进一步发展至关重要。
Gnutella协议洪泛机制的最大问题是导致冗余消息的产生。节点将查询消息向其所有邻居节点转发,从而造成搜索消息被迅速复制,网络负载过重,查准率和查找效率不高。在以往改进的算法中,虽然在一定程度上减少了查询消息的转发量,但是在资源查准率和查找消息可达性方面仍有不足。本文在总结以往改进算法的基础上,对其不足进行改进,引入了一种基于索引机制的资源搜索改进算法。
本文首先介绍了P2P的产生背景、主要应用领域及其目前的发展状况,重点分析了非结构化P2P代表协议Gnutella的搜索策略及其改进算法RWRI(Random Walk with Routing Index),并分析RWRI算法存在的不足。其次针对RWRI算法的不足提出了如下改进:通过在路由索引表中增加记录查询信息和当前节点到达资源目标节点的最小跳数信息来指导查询,从而弥补了原算法在指引查询时不能保证查询消息可达性的缺点;引入返回路径表与路由索引表互相呼应,采用缓存查询返回消息的策略来提高重复查询的效率。最后在NS2+Cygwin平台下对本文提出的改进算法进行了验证,将改进算法和改进前算法进行了比较。实验结果表明:改进后的算法在一定程度上提高了资源搜索的查准率,减少了资源搜索的盲目性。
With the rapid development of network,the amout of data became larger.It’s more and more important to choose a good method for data query and exchange.P2P technical is just appear to meet this demand.P2P technical has a good future in the area of search engine,cooperation and data exchange.Gnutella is a protocol of unstructured p2p system.The flood query method of gnutella lead to a bad query result which restrict the development of p2p network.how to manage the network,how to execure a search method with a high efficiency and how to solve the extention problem is important to the development of network.
The problem of the Gnutella flood protocol is that,it will cause redundant messages.the redundant message will lead to the over burden of the network.the optimized algorithm before reduced the burden of the network,but the query hit rate is not improved.this paper will introduce a new optimized algorithm based on index.
First,this paper will introduce the history of p2p network and its development.we will pay more attention to the shortage of RWRI algorithm of Gnutella protocol.Second, this paper put forward a improved algorithm of gnutella: record the minimum distance between the node and the query target node to guard the query message; use both route index table and return path table to record the return path of the query hit message to guard the same query, the improvement above will optimized the query hit rate and the query result.Last, this paper compared the optimized algorithm and the old algorithm on ns2 and cygwin platform.the result indicate that under the optimized algorithm ,the query hit rate and the objective of query are improved.
Gnutella协议洪泛机制的最大问题是导致冗余消息的产生。节点将查询消息向其所有邻居节点转发,从而造成搜索消息被迅速复制,网络负载过重,查准率和查找效率不高。在以往改进的算法中,虽然在一定程度上减少了查询消息的转发量,但是在资源查准率和查找消息可达性方面仍有不足。本文在总结以往改进算法的基础上,对其不足进行改进,引入了一种基于索引机制的资源搜索改进算法。
本文首先介绍了P2P的产生背景、主要应用领域及其目前的发展状况,重点分析了非结构化P2P代表协议Gnutella的搜索策略及其改进算法RWRI(Random Walk with Routing Index),并分析RWRI算法存在的不足。其次针对RWRI算法的不足提出了如下改进:通过在路由索引表中增加记录查询信息和当前节点到达资源目标节点的最小跳数信息来指导查询,从而弥补了原算法在指引查询时不能保证查询消息可达性的缺点;引入返回路径表与路由索引表互相呼应,采用缓存查询返回消息的策略来提高重复查询的效率。最后在NS2+Cygwin平台下对本文提出的改进算法进行了验证,将改进算法和改进前算法进行了比较。实验结果表明:改进后的算法在一定程度上提高了资源搜索的查准率,减少了资源搜索的盲目性。
With the rapid development of network,the amout of data became larger.It’s more and more important to choose a good method for data query and exchange.P2P technical is just appear to meet this demand.P2P technical has a good future in the area of search engine,cooperation and data exchange.Gnutella is a protocol of unstructured p2p system.The flood query method of gnutella lead to a bad query result which restrict the development of p2p network.how to manage the network,how to execure a search method with a high efficiency and how to solve the extention problem is important to the development of network.
The problem of the Gnutella flood protocol is that,it will cause redundant messages.the redundant message will lead to the over burden of the network.the optimized algorithm before reduced the burden of the network,but the query hit rate is not improved.this paper will introduce a new optimized algorithm based on index.
First,this paper will introduce the history of p2p network and its development.we will pay more attention to the shortage of RWRI algorithm of Gnutella protocol.Second, this paper put forward a improved algorithm of gnutella: record the minimum distance between the node and the query target node to guard the query message; use both route index table and return path table to record the return path of the query hit message to guard the same query, the improvement above will optimized the query hit rate and the query result.Last, this paper compared the optimized algorithm and the old algorithm on ns2 and cygwin platform.the result indicate that under the optimized algorithm ,the query hit rate and the objective of query are improved.
引文
[1] 戴建强. P2P 基础技术初探[J]. 厦门科技,2006,(06): 34-37
[2] 王先兵,张荣,胡建光.Gnutella 协议的研究[J].计算机工程, 2001,27(11):56-57,158
[3] Anoymous, The Gnutella Protocol Specification v0.4[EB/OL], http://www.securitytechnet.com/resource/hot-topic/p2p/gnutellaprotocol04.pdf, 2005.4.5
[4] peer-to-peer 综述.http://www.intsci.ac.cn/users/luojw/papers/p2p.htm,2005
[5] Ng C H, Sia K C. Peer clustering and firework query model[C]. In Proc. of 11th World Wide Web Conference, Hawaii,USA, 2002
[6] S.H.Kwok,K.Y.Chan.An Enhanced Gnutella P2P Protocol:A Search Perspective[C].In Proc. Of Proceedings of the 18th international Conference on Advanceed information Networking and Application(AINA’04),2004
[7] Yang B, Garcia-Molina H. Efficient search in peer-to-peer networks[C]. In Proc. of ICDCS'02, Vienna, Austria, 2002
[8] Christos Gkantsidis,Milena Mihail,Admin Saberi.Random Walks in Peer-to-Peer Networks[J].2004 IEEE
[9] Hongbo Jiang,Shudong Jin.Exploiting Dynamic Querying like Flooding Techniques in Ustructurted Peer-to-Peer Networks[C].In Proc. Of Proceedings of the 13th IEEE international Conference on Network Protocols(ICNP’05),2005
[10] Christos Gkantsidis,Milena Mihail,Admin Saberi.Hybrid Search Schemes for Unstructured Peer-to-Peer Networks[J].2005 IEEE
[11] Sweeney J, Hayward S, Drakos N,et al. COM-12-4447:The Five Peer-to-Peer Models: Toward the New Web. 2001-02-05
[12] 薛广涛等.使用兴趣子网划分机制对 Gnutella 资源划分机制的改进(J).上海交通大学学报.vol 38 no12.Dec 2004
[13] 庄雷 等.消除 R- TTL 环: Gnutella 网络中减少冗余消息的解决方法(J).微计算机应用.Vol 25 No 4.jun 2004.
[14] 张联峰,刘乃安,钱秀槟,张玉清.综述对等网(P2P)技术[J].计算机工程与应用, 2003,12:142-145
[15] P2P 面临困惑[J].每周电脑报,2001,(12):43
[16] 伍班权. P2P 应用三部曲[J]. 互联网周刊,2002,(25):56-57
[17] Kert. P2P Introduction. http://wwv.ppcn.net/技术文摘,2003-04-14
[18] 汤韦,吴朝晖.P2P_对等网络的未来[J].计算机应用研究,2004,(1):13-16
[19] 严晗,王典洪,张建辉. 有关 P2P 的应用及其发展方向[J]. 现代计算机,2003,(05):36-39
[20] AssetMetrixTM Research Labs. Corporate P2P Usage&Risk Analysis. AssertMetrix, Inc.,2003-07:1-18
[21] 李振武,杨舰,白英彩.对等网络研究及其挑战[J].计算机应用与软件, 2004,21(2):54-57
[22] Q. Lv, Y. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In 16th international conference on Supercomputiug, 2002.6
[23] 丁一.新词 Gnutella[J]. 知识就是力量,2003,(5):13
[24] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker.Making Gnutella-like P2P Systems Scalable
[25] The Gnutella Protocol Specification V0.4:C1ip2 Distributed Search Solutions. http://dss.clin2.com, 1999
[26] Gnutella Protocol. http://www.capnbry.net/gnutclla/protocol.php
[27] Gnutella Forums. http://www.gnutcllaforums.com/
[28] Use of the Gnutella Protocol in B2B Info-exchange Network. http://www.infoanarchy.org/story/2002/4/10/112223/265
[29] 刘宝旭,孙笑庆,崔石,陆建强. Gnutella 协议及数据包结构分析[J]. 计算机工程, 2004,30(02):P8-10
[30] 黄通颖,李祖鹏,庄雷等.分布式 Peer-to-Peer 网络 Cnutella 模型研究[J].计算机工程与应用,2003,39(5):60-63
[31] 黄通颖,李祖鹏,张尧等.Active Distributed Peer-to-Peer Network Architecture[C].In: International Conference on Communication Technology (ICCT2003) Proceedings, 2003
[32] Evangelos P.Markatos.Tracing a larger-scale Peer to Peer System:An hour in the life of Gnutella[C].In Proc of Proceedings of the 2nd IEEE/ACM International Sysposium on Cluster Computing and the Grid(CCGRID’02)
[33] 黄道颖,陈新,张安琳等. P2P 网络 Gnutella 模型中搜索消息的路由机制及改进研究[J]. 计算机工程与应用,2003,(25):13-15,37
[34] 郭大江,陈闳中.Gnutella 网络搜索算法的改进.计算机工程与应用[J], 2005,(36):123-124
[35] 黄道颖,刘刚等.利用 Gnutella 网络的拓扑特性改进可扩展性[J].计算机工程与应用, 2003,39(26):58-60
[36] 张维凤,张代远. P2P 网络中基于文件路由模型搜索方法的改进[J]. 计算机技术与发展,2006,16(12):111-113
[37] 刘涛,张志明.一种基于 P2P 网络 Gnutella 模型的查询策略[J]. 计算机应用与软件,2006,23(6):53-55
[38] 邓泓,周莉,周定康. Gnutella 网络中树结构搜索机制的研究[J]. 江西师范大学学报(自然科学版),2006,30(3):282-284
[39] 王东泉,张刚. 利用路由索引技术提高 Gnutellar 的性能[J]. 微处理机, 2006,(5):42-43
[40] http://gnutella.com
[41] B.Yang and H.Garcia-Molina. Comparing hybrid peer-to-peer systems. In Proc of the 27th IntI. Conf:on Very Large Databases, September 2001
[42] Mihajlo A .Jovanovi'cB S .Modeling Large-scale Peer-to-Peer Networks and a Case Study of Gnutella. University of Cincinnati, 2000
[43] Vana Kalogeraki Dimitrios Gunopulos D.Zeinalipour-Yazti. A local Search Mechanism for Peer-to-Peer Networks CIKM 02, November 4-9,2002, Mc1ean,Virginia, USA
[44] S. Brin. The anatomy of a large-scale hyper textual web search engine. In 7th WWW Conference, 1998
[45] A.Crespo and H.Garcia-Molina. Routing indices for peer-to-peer systems. In Proc. of ICDCS 2002, July 2002
[46] E.Cohen and S.Shenker. Optimal replication in random search networks. Preprint, Optional 2001
[47] L.Adamic, R.Lukose, A.Puniyani, and B.Huberman. Search in power-law networks. Available at http://www.-part.xerox.tom/istl/groups/iea/papers/plsearch/, 2001
[48] Subhabrata Sen, Jia Wang, Analyzing Peer-To-Peer Traffic Across Large Networks, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 2, APRIL 2004
[49] 乐光学. 基于 Gnutella 协议的 P2P 网络路由搜索算法:Light-Flooding[J]. 计算机工程, 2005,31(11):112-114
[50] Jose S. Emergence of Distributed Content Management and Peer-to-Peer Content Networks. Gartner Group Inc., 2001
[51] Kleinberg J M, Kumar R, Achaean P. The Web a Graph: Measurements, Models, and Methods. In 5th Annual International Conference on Computing and Combinatorics, 1999, 1627:1-7
[52] 李建春 等.反馈机制在 p2p 网络资源搜索中的应用研究.计算机工程与应用(J). 2005 .4
[53] 侯孟书 等.非结构化 P2P 系统的路由算法.电子科技大学学报(J). 2005 .2
[2] 王先兵,张荣,胡建光.Gnutella 协议的研究[J].计算机工程, 2001,27(11):56-57,158
[3] Anoymous, The Gnutella Protocol Specification v0.4[EB/OL], http://www.securitytechnet.com/resource/hot-topic/p2p/gnutellaprotocol04.pdf, 2005.4.5
[4] peer-to-peer 综述.http://www.intsci.ac.cn/users/luojw/papers/p2p.htm,2005
[5] Ng C H, Sia K C. Peer clustering and firework query model[C]. In Proc. of 11th World Wide Web Conference, Hawaii,USA, 2002
[6] S.H.Kwok,K.Y.Chan.An Enhanced Gnutella P2P Protocol:A Search Perspective[C].In Proc. Of Proceedings of the 18th international Conference on Advanceed information Networking and Application(AINA’04),2004
[7] Yang B, Garcia-Molina H. Efficient search in peer-to-peer networks[C]. In Proc. of ICDCS'02, Vienna, Austria, 2002
[8] Christos Gkantsidis,Milena Mihail,Admin Saberi.Random Walks in Peer-to-Peer Networks[J].2004 IEEE
[9] Hongbo Jiang,Shudong Jin.Exploiting Dynamic Querying like Flooding Techniques in Ustructurted Peer-to-Peer Networks[C].In Proc. Of Proceedings of the 13th IEEE international Conference on Network Protocols(ICNP’05),2005
[10] Christos Gkantsidis,Milena Mihail,Admin Saberi.Hybrid Search Schemes for Unstructured Peer-to-Peer Networks[J].2005 IEEE
[11] Sweeney J, Hayward S, Drakos N,et al. COM-12-4447:The Five Peer-to-Peer Models: Toward the New Web. 2001-02-05
[12] 薛广涛等.使用兴趣子网划分机制对 Gnutella 资源划分机制的改进(J).上海交通大学学报.vol 38 no12.Dec 2004
[13] 庄雷 等.消除 R- TTL 环: Gnutella 网络中减少冗余消息的解决方法(J).微计算机应用.Vol 25 No 4.jun 2004.
[14] 张联峰,刘乃安,钱秀槟,张玉清.综述对等网(P2P)技术[J].计算机工程与应用, 2003,12:142-145
[15] P2P 面临困惑[J].每周电脑报,2001,(12):43
[16] 伍班权. P2P 应用三部曲[J]. 互联网周刊,2002,(25):56-57
[17] Kert. P2P Introduction. http://wwv.ppcn.net/技术文摘,2003-04-14
[18] 汤韦,吴朝晖.P2P_对等网络的未来[J].计算机应用研究,2004,(1):13-16
[19] 严晗,王典洪,张建辉. 有关 P2P 的应用及其发展方向[J]. 现代计算机,2003,(05):36-39
[20] AssetMetrixTM Research Labs. Corporate P2P Usage&Risk Analysis. AssertMetrix, Inc.,2003-07:1-18
[21] 李振武,杨舰,白英彩.对等网络研究及其挑战[J].计算机应用与软件, 2004,21(2):54-57
[22] Q. Lv, Y. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In 16th international conference on Supercomputiug, 2002.6
[23] 丁一.新词 Gnutella[J]. 知识就是力量,2003,(5):13
[24] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker.Making Gnutella-like P2P Systems Scalable
[25] The Gnutella Protocol Specification V0.4:C1ip2 Distributed Search Solutions. http://dss.clin2.com, 1999
[26] Gnutella Protocol. http://www.capnbry.net/gnutclla/protocol.php
[27] Gnutella Forums. http://www.gnutcllaforums.com/
[28] Use of the Gnutella Protocol in B2B Info-exchange Network. http://www.infoanarchy.org/story/2002/4/10/112223/265
[29] 刘宝旭,孙笑庆,崔石,陆建强. Gnutella 协议及数据包结构分析[J]. 计算机工程, 2004,30(02):P8-10
[30] 黄通颖,李祖鹏,庄雷等.分布式 Peer-to-Peer 网络 Cnutella 模型研究[J].计算机工程与应用,2003,39(5):60-63
[31] 黄通颖,李祖鹏,张尧等.Active Distributed Peer-to-Peer Network Architecture[C].In: International Conference on Communication Technology (ICCT2003) Proceedings, 2003
[32] Evangelos P.Markatos.Tracing a larger-scale Peer to Peer System:An hour in the life of Gnutella[C].In Proc of Proceedings of the 2nd IEEE/ACM International Sysposium on Cluster Computing and the Grid(CCGRID’02)
[33] 黄道颖,陈新,张安琳等. P2P 网络 Gnutella 模型中搜索消息的路由机制及改进研究[J]. 计算机工程与应用,2003,(25):13-15,37
[34] 郭大江,陈闳中.Gnutella 网络搜索算法的改进.计算机工程与应用[J], 2005,(36):123-124
[35] 黄道颖,刘刚等.利用 Gnutella 网络的拓扑特性改进可扩展性[J].计算机工程与应用, 2003,39(26):58-60
[36] 张维凤,张代远. P2P 网络中基于文件路由模型搜索方法的改进[J]. 计算机技术与发展,2006,16(12):111-113
[37] 刘涛,张志明.一种基于 P2P 网络 Gnutella 模型的查询策略[J]. 计算机应用与软件,2006,23(6):53-55
[38] 邓泓,周莉,周定康. Gnutella 网络中树结构搜索机制的研究[J]. 江西师范大学学报(自然科学版),2006,30(3):282-284
[39] 王东泉,张刚. 利用路由索引技术提高 Gnutellar 的性能[J]. 微处理机, 2006,(5):42-43
[40] http://gnutella.com
[41] B.Yang and H.Garcia-Molina. Comparing hybrid peer-to-peer systems. In Proc of the 27th IntI. Conf:on Very Large Databases, September 2001
[42] Mihajlo A .Jovanovi'cB S .Modeling Large-scale Peer-to-Peer Networks and a Case Study of Gnutella. University of Cincinnati, 2000
[43] Vana Kalogeraki Dimitrios Gunopulos D.Zeinalipour-Yazti. A local Search Mechanism for Peer-to-Peer Networks CIKM 02, November 4-9,2002, Mc1ean,Virginia, USA
[44] S. Brin. The anatomy of a large-scale hyper textual web search engine. In 7th WWW Conference, 1998
[45] A.Crespo and H.Garcia-Molina. Routing indices for peer-to-peer systems. In Proc. of ICDCS 2002, July 2002
[46] E.Cohen and S.Shenker. Optimal replication in random search networks. Preprint, Optional 2001
[47] L.Adamic, R.Lukose, A.Puniyani, and B.Huberman. Search in power-law networks. Available at http://www.-part.xerox.tom/istl/groups/iea/papers/plsearch/, 2001
[48] Subhabrata Sen, Jia Wang, Analyzing Peer-To-Peer Traffic Across Large Networks, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 12, NO. 2, APRIL 2004
[49] 乐光学. 基于 Gnutella 协议的 P2P 网络路由搜索算法:Light-Flooding[J]. 计算机工程, 2005,31(11):112-114
[50] Jose S. Emergence of Distributed Content Management and Peer-to-Peer Content Networks. Gartner Group Inc., 2001
[51] Kleinberg J M, Kumar R, Achaean P. The Web a Graph: Measurements, Models, and Methods. In 5th Annual International Conference on Computing and Combinatorics, 1999, 1627:1-7
[52] 李建春 等.反馈机制在 p2p 网络资源搜索中的应用研究.计算机工程与应用(J). 2005 .4
[53] 侯孟书 等.非结构化 P2P 系统的路由算法.电子科技大学学报(J). 2005 .2