非对称双向Base-k Chord

doi:10.3969/j.issn.1000-0801.2010.10.019

电信科学 ›› 2010, Vol. 26 ›› Issue (10): 71-79.doi: 10.3969/j.issn.1000-0801.2010.10.019

非对称双向Base-k Chord

严华云^1,²,关估红²,詹卫华²,蒋云良¹

¹ 湖州师范学院信息与工程学院湖州313000
² 同济大学电子与信息工程学院上海201804

出版日期:2010-10-15 发布日期:2010-10-15
基金资助:
国家自然科学基金资助项目;浙江省自然科学基金资助杰出青年团队项目;浙江省自然科学基金资助项目;湖州市科技攻关项目

An Asymmetrically Bidirectional Base-k Chord

Huayun Yan^1,²,Jihong Guan²,Weihua Zhan²,Yunliang Jiang¹

¹ School of Information＆Engineering，Huzhou Teachers College，Huzhou 313000，China
² College of Electronics＆Information Engineering，Tongji University，Shanghai 201804，China

Online:2010-10-15 Published:2010-10-15

摘要/Abstract

摘要：

针对Base-k Chord 的路由效率问题，本文对其finger 表做出了非对称双向调整，即将其finger 表奇数项保留为正向finger，偶数项finger对折到反向作为反向finger，调整后的finger表的大小不变。在此基础上提出了改进的路由算法，该算法每次选择离目标节点最近的finger进行路由。为了证明本文方法比2-Chord的对称双向finger方法更好，将2-Chord 扩展成对称双向Base-k Chord，并与之进行了性能比较。实验分析发现，对称双向Base-k Chord 的路由效率提升极小，非对称双向Base-k Chord有效地降低了平均路由跳数。

关键词: peer-to-peer, chord；finger表, 路由算法

Abstract:

To improve the routing efficiency of Base-k Chord，this paper proposes a new finger table for Base-k Chord by using an asymmetrically bidirectional structure. Concretely，keeping the odd items in the finger table unchanged，while re-directing the even items，which does not change the size of the finger table. A routing algorithm for this new Chord structure is developed， which can always chooses the next finger for routing that is nearest to the destination node. For performance comparison，the 2-Chord is extended to symmetrically bidirectional Chord. Experimental results show that the routing efficiency of symmetrically bidirectional Chord archives no much improvement in performance，while the proposed asymmetrically bidirectional Base-k Chord outperforms its counterparts.

Key words: peer-to-peer, Chord，finger table, routing algorithm

严华云,关估红,詹卫华,蒋云良. 非对称双向Base-k Chord[J]. 电信科学, 2010, 26(10): 71-79.

Huayun Yan,Jihong Guan,Weihua Zhan,Yunliang Jiang. An Asymmetrically Bidirectional Base-k Chord[J]. Telecommunications Science, 2010, 26(10): 71-79.

图/表 11

图1

图2

图3

图4

图5

图6

图7

表1

图8

图9

图10

参考文献 11

1	Napster.
2	Gnutella.
3	Stoica I ， Morris R ， Karger D ， et al. Chord：a scalable peer-to-peer lookup service for internet applications. In：Proceedings of the ACM SIGCOMM 2001 Conference on Applications， Technologies， Architectures and Protocols for Computer Communication， SanDiego，California，USA，August 2001.
4	Bharambe A ， Agrawal M ， Seshan S . Mercury：Supporting scalable multi-attribute range queries. In：Proceedings of the ACM SIGCOMM 2004 Conference on Applications， Technologies，Architectures，and Protocols for Computer Communication， Portland Oregon，USA，August 30—September 3 2004.
5	Cordasco G ， Gargano L ， Negro A ， et al. F-Chord：improved uniform routing on chord. Networks， 2008，52（4）： 325～332
6	郑彦，陈宏伟，王汝传等. 新型分布式散列表-Bchord. 通信学报， 2008，29（2）： 22～28
7	Cordasco G ， Sala A . 2-Chord halved. In：Proceedings of the 2nd International Workshop on Hot Topics in Peer-to-Peer Systems， San Diego California，USA，July 2005.
8	Ganesan P ， Manku G S . Optimal routing in Chord. In：Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms， New Orleans，Louisiana，USA，January 2004.
9	Chiola G ， Cordasco G ， Gargano L ， et al. Optimizing the finger table in Chord-like DHTs. Concurrency and Computation：Practice and experience， 2008，20（6）： 643～657
10	peersim.
11	Zipf G K . nd the principle of least effort. New York：Addion-Wesley， 1949.

K			节点空间大小
K	10³	10⁴	10⁵	10⁶	10⁷	10⁸	2¹²⁸
K=3	14	18	22	26	30	34	162
K=4	15	21	27	30	36	42	192
K=5	20	24	32	36	44	48	224

[1]	桂飞,程阳,李丹,洪思虹. 互联网智能路由架构及算法[J]. 电信科学, 2020, 36(10): 12-20.
[2]	任智,王坤龙,李秀峰. 基于兴趣社区的高效路由与缓存管理算法[J]. 电信科学, 2018, 34(6): 43-52.
[3]	宋朝,郑迎凤,赵文彬. 一种有效的稀疏无线传感器网络路由方案[J]. 电信科学, 2016, 32(4): 59-64.
[4]	樊自甫,伍春玲,王金红. 基于SDN架构的数据中心网络路由算法需求分析[J]. 电信科学, 2015, 31(2): 36-45.
[5]	吴吉义,张启飞,王桐,陈德人,章剑林. 一种P2P文件共享系统的QoS评价模型[J]. 电信科学, 2012, 28(12): 135-141.
[6]	刘礼建,张广明,唐桂忠,王祥华. 智能家居ZigBee网络的构建与路由优化[J]. 电信科学, 2011, 27(9): 106-110.
[7]	韩国栋,谢同飞,肖庆辉. 2D-Mesh片上网络中通信密集点优化方法[J]. 电信科学, 2011, 27(2): 81-86.
[8]	欧阳一鸣,丁同柱,梁华国,谢涛. 一种基于2D-mesh的低延迟NoC路由算法设计[J]. 电信科学, 2011, 27(10): 98-102.
[9]	欧阳一鸣,屠强,梁华国,郭凯. 基于重构的片上网络容错机制[J]. 电信科学, 2010, 26(8): 76-81.
[10]	欧阳一鸣,郭凯,梁华国. 基于片上网络的容错通信方法[J]. 电信科学, 2010, 26(7): 55-60.
[11]	吴启武,王建萍,周贤伟. WDM光网络中的组播路由算法研究[J]. 电信科学, 2009, 25(9): 51-57.
[12]	欧阳一鸣,朱兵,梁华国,王伟. 针对片上网络组播通信模型的设计与仿真[J]. 电信科学, 2009, 25(4): 56-61.
[13]	欧阳一鸣,朱兵,梁华国,王伟. 针对片上网络组播通信模型的设计与仿真[J]. 电信科学, 2009, 25(3): 56-61.

非对称双向Base-k Chord

An Asymmetrically Bidirectional Base-k Chord

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 11

相关文章 13

Metrics

推荐阅读 0