基于多环的Chord改进算法 (2010年)
需积分: 5 197 浏览量
2021-05-22
03:53:38
上传
评论
收藏 257KB PDF 举报
一一
ι
一
第
36
卷第
2
期
1
仿
1.36
No.2
计算机工程
Computer
Engineering
2010
年
1
月
January
2010
·网络与通信·
文章编号
100
←
-3428(2010)0
2-0
11
6-{)③
文献标识码
A
中图分类号
TP30
1.
6
基于多坏的
Chord
改进算法
李建军熊选东谭酶贞
2
(1.解放军信息工程大学电子技术学院，郑州
450004;
2.
海军司令部航空管制处，北京
100071)
摘
要:通过分析
Chord
协议，提出基于多环的
Chord
改进算法
MR-Chordo
MR-Chord
采用多环和组相结合的结构，在组内每个节点记录
全组的路由，组与组之间以递归算法相连成多个环。通过理论分析和仿真实验对
Chord
和
MR-Chord
进行比较，结果表明，
MR-Chord
使
系统的性能和适应性更好，路由表中的冗余很少。
关键词
Chord
协议P2
P
网络;多环;性能分析
Improved Chord Algorithm ßased on Multi-ring
Ll
Jian
气
jun
l，
XIONG
Xuan-dong
l,
TAN
Xiao-zhen
2
(1.
Institute
of
Electronic Technology, PLA Information
Engin
巳
ering
University,
Zh
巳
ngzhou
450004;
2.
N avy Command Air Traffic Control Department, Beijing 10007
1)
(Abstract]
By analyzing Chord protocol, this paper proposes
an
improved Chord algorithm called MR-Chord(Chord Based on the Combination of
Ri
ng
and Group), which is based on multi-ring. MR-Chord uses the structure combining multi-ring and group. Each node in the group records the
whole
routing
of
the group and the groups link into multi-ring with recursive algorithm. Analysis on theory and simulation results show that
MR-Chord has better
p
巳
rformance
and adaptability of
th
巳
system
，
and the routing tables have few redundancy.
(Key
words]
Chord protocol; P2P network; multi-ring;
p
巳
rformanc
巳
analysis
1
概述
P2P
表示网络节点对等互联。它平行于网络上流行的客
户端/服务器的主从互联模式，实现了分布式资源利用与共
享，每个节点均可进行对等通信，具备同时对信息内容进行
接收、发送、存储、搜索等功能，各节点对等协同完成任务。
网络中的每个节点具有相同的地位，既可以请求服务又可以
提供服务，同时扮演客户端和服务器
2
种角色，还具有路由
器和高速缓冲存储器的功能。
P2P
网络按照网络中节点和资源的关系可以分为非结构
化
P2P
网络和结构化
P2P
网络。非结构
P2P
网络是基于泛洪
搜索的，搜索较慢而且消耗大量的资源。结构化
P2P
网络是
利用分布式哈希表(Di
stributed
Hash
Table,
DHT)
实现的，搜索
速度快，产生的查询消息少。
Chord
协议
[1]
是
2001
年麻省理
工学院
(Massachusetts
Institute
of
Technology,
MIT)
专门为结
构化
P2P
应用设计的。它虽然具有算法简单、查找速度快等
特点，但仍存在以下不足，从而影响了效率:
(1)对网络拓扑
的实际结构欠缺考虑，使得逻辑上相邻的一跳在物理网络中
可能经过很多跳数，造成了相当大的网络延迟。
(2)Chord
的
路由表中存在严重的冗余。为了减少不必要的网络延迟、提
高路由的效率，许多学者对
Chord
做了进一步的研究。其中，
Echord[2],
TCS-Chord[
剖，
Achord
f4
]
等都通过不同的方式对
Chord
进行了改进，但是这些改进局限性较大、实用性较差，
而且都无法消除
Chord
路由表中大量的冗余。另一些研究只
是简单地在路由表存在冗余时以其他节点来替换，或者引入
超级节点。
本文提出了一种结合多环和组的算法
MR-Chord(Chord
Based
on the
Combination
of
Ring
and Group) ,
MR-Chord
利用
组构成环，由于组在线时
l
肖远大于节点，因此可以大幅减少
一
116
一
路由表的冗余。同时通过调节组的大小来适应网络的动态变
化，提高查找效率。而且可以在其上应用任意减少网络延迟
的改进方法。
2
相关工作
2.1
Chord
协议
Chord
协议通过相容哈希函数把指定的关键字
Key
映射
到对应的节点
Node
上。在
Chord
中，节点及所有的关键字都
被同一个哈希算法映射到一个
m
位的标识符(一个节点的标
识符是它的
IP
地址或其他信息经过哈希映射得到的)。其中，
m
的取值必须足够大，才能使
2
个节点或
2
个关键字的哈希
值相同的可能性忽略不计。
在
Chord
系统中，每个节点按照其标识符大小依次顺序
连接，最后首尾相接形成一个环。对节点的
IP
地址或其他信
息进行哈希得到节点的标识符
Node
Key
，
用同样的方法，哈
希资源的关键字可以得到资源的标识符
key
。每个资源根据自
己的
key
值被分派到某个节点上，这个节点叫作
key
的
successor
节点，用
successor(key)
表示，它是
Chord
环上沿
}I
顶
时针方向第
1
个标识符大于等于
key
的节点。
2.2
Chord
的路由分析
根据
Chord
的原理，现假设
Chord
环的节点数为
2
m
，
而
网络中的实际节点数为
2
n
(m>>
时，并且所有节点均匀分布
在
Chord
环上。于是任意相邻节点间的间距为L1
=
2
"，
-n
。若其
中一个节点为
N
o
，
则之后的
γ-1
个节点可以表示为
N
o
+L1,
N
o
+2
L1
, … ,
N
o
+2"-I
L1
其路由表为
(N
o
+i-
l
)mod2"'
作者筒介:李建军(1
980
一)
，男，硕士研究生，主研方向:网络安全，
P2P
网络;熊选东，研究员;谭晓贞，工程师
收稿日期
2009-05-20
E-mail: lijianjun2006@gmail.com
资源评论
weixin_38673548
- 粉丝: 4
- 资源: 948
最新资源
- 疯狂吃月饼游戏小程序前端源码
- 开源光谱分析仪博客的代码
- 基于深度学习的工业缺陷检测（续篇）
- 大创项目编程示例开发案列优质学习资料资源工具与案列应用场景开发文档教程资料.txt
- 树莓派智能车编程实例开发案列优质学习资料资源工具与案列应用场景开发文档教程资料.txt
- 电子设计竞赛（Electronic Design Contest） 开发案列优质学习资料资源工具与案列应用场景开发文档教程资料
- Cpu-Z 是一款计算机的CPU检测软件
- 美国大学生数学建模竞赛 开发案列优质学习资料资源工具与案列应用场景开发文档教程资料.txt
- 最新版点微同城源码34.7+全套插件+小程序前后端附图片
- 计算机二级 开发案列优质学习资料资源工具与案列应用场景开发文档教程资料.txt
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
