基于混合双层模型的DHT网络路由表快照算法

计算机科学 ›› 2015, Vol. 42 ›› Issue (Z6): 263-265.

基于混合双层模型的DHT网络路由表快照算法

余杰,李强,李莎莎,马俊,李舟军

国防科学技术大学计算机学院长沙410073,北京航空航天大学计算机学院北京100000,国防科学技术大学计算机学院长沙410073;北京航空航天大学计算机学院北京100000,国防科学技术大学计算机学院长沙410073,北京航空航天大学计算机学院北京100000

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金项目(61103015,0,61303191)资助

Hybrid Method for Capturing Snapshot of Routing Table of DHT Networks

YU Jie, LI Qiang, LI Sha-sha, MA Jun and LI Zhou-jun

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： DHT网络是目前应用最广泛的P2P协议,路由表是其进行自组织的关键组件。由于DHT网络的完全分布特点,对其全局路由表快照进行测量是一个研究难点和热点。提出了基于混合双层模型的DHT路由表快照算法:首先通过引入路由查询重复度这一重要概念来定义DHT网络快照和路由表快照采集的效率；然后提出了先宽度优先搜索后深度优先搜索的全局快照混合搜索策略；最后基于路由表的不均匀特性提出了路由表快照自适应搜索策略。在Kad网络上的真实实现表明,全局快照混合搜索策略的平均效率比Blizzard高91.2%,比宽度优先搜索高64.5%,比深度优先搜索高27.4%；路由表快照自适应搜索策略在g=5时具有最佳的路由表快照采集效率,比随机搜索策略高187.4%,比g=7时高38.9%。

Abstract: DHT network is the most widely used P2P protocol in the world and routing table is the key component for its self-organization.It’s difficult to measure the global routing table of a DHT network due to its feature of totally distributed architecture.In this paper,we propose a hybrid method to capture the snapshot of the routing table of DHT network.We first introduce a repetition degree to define the efficiency when crawling the snapshot.Then,we propose a DHT snapshot method that uses breadth-first search first and then changes to depth-first search.Finnally,we propose a self-adaptive method to crawl the routing tables based on the un-even feature of routing table.The experiment on Kad network shows that,the DHT snapshot method is 91.2% better than Blizzard,64.5% better than breadth-first and 27.4% better than depth-first.Routing table snapshot method reaches the best when g=5 and it is 187.4% better than the random method and 38.9% better than g＝7.

Key words: DHT,Routing table,Two layer model,Hybrid strategy,Self-adaptive strategy

余杰,李强,李莎莎,马俊,李舟军. 基于混合双层模型的DHT网络路由表快照算法[J]. 计算机科学, 2015, 42(Z6): 263-265. https://doi.org/

YU Jie, LI Qiang, LI Sha-sha, MA Jun and LI Zhou-jun. Hybrid Method for Capturing Snapshot of Routing Table of DHT Networks[J]. Computer Science, 2015, 42(Z6): 263-265. https://doi.org/

参考文献

[1] Stoica I,Morris R,Karger D,et al.Chord:A scalable peer-to-peer lookup service for Internet applications[C]∥Proceedings of SIGCOMM’01.2001:149-160
[2] Han J,Liu Y.Rumor Riding:Anonymizing Unstructured Peer-to-Peer Systems[M].IEEE ICNP,Santa Barbara,California,USA,November,2006
[3] 刘琼,徐鹏,杨海涛,等.Peer-to-Peer文件共享系统的测量研究[J].软件学报,2006,17(10):2131-2140
[4] Maymounkov P,Mazières D.Kademlia:A Peer-to-Peer Information System Based on the XOR Metric[C]∥Proceedings of the 1st International Workshop on Peer-to-Peer Systems(IPTPS’02).2002:53-65
[5] Bhagwan R,Savage S,Voelker G.Understanding availability[C]∥Proceedings of the 2nd International Workshop on Peer-to-Peer Systems(IPTPS’03).2003:256-267
[6] Brunner R.A performance evaluation of the Kad-protocol[M].Master Thesis,2006
[7] Steiner M,Biersack E W,Ennajjary T.Actively monitoringpeers in KAD[C]∥Proceedings of the 6th International Workshop on Peer-to-Peer Systems(IPTPS’07).2007
[8] Guo L,Chen S,Xiao Z,et al.Measurement,analysis,and mode-ling of BitTorrent-like systems[C]∥Proceedings of IMC’05.2005
[9] Neglia G,Reina G,Zhang H.Availability in BitTorrent Systems[C]∥Proceedings of INFOCOM’07.2007
[10] Jimenez R,Osmani F,Knutsson B.Connectivity Properties ofMainline BitTorrent DHT Nodes[C]∥Proceedings of P2P’09.2009
[11] Yu J,Fang C,Xu J,et al.ID repetition in Kad[C]∥Proceedings of IEEE P2P’09.2009
[12] Yu J,Lu L,Li Z,et al.A simple effective scheme to enhance the capability of web servers using P2P networks[C]∥Proceedings of ICPP’10.2010
[13] 李强,李舟军,周长斌,等.Kad网络中Sybil攻击团体检测技术研究[J].计算机研究与发展,2014,51(7):1614-1624
[14] Steiner M,Carra D,Biersack E W.Long term study of peer behavior in the KAD DHT[C]∥IEEE/ACM Trans.Networking.2009

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed