６１
２２
６
６
７０
４
５
１
２
３
Ｓｕｃｃｅｓｓｏｒ（６）＝０Ｓｕｃｃｅｓｓｏｒ（１）＝１
Ｓｕｃｃｅｓｓｏｒ（２）＝３
图１Ｃｈｏｒｄ环结构
１引言
在规模庞大的对等网络结构中，如何快速准确地到目标
资源是目前对等网络研究中的热点问题。目前在这个方面的研究中，基于ＤＨＴ的分布式查算法具有扩展性好、效率高和自适应强等特点，其中有代表性的算法有：Ｃｈｏｒｄ ［１，１２］
，Ｐａｓｔｒｙ［２］
，ＣＡＮ［３］
，
Ｔａｐｅｓｔｒｙ［４］，Ｓｙｍｐｈｏｎｙ［１５］，Ｋｅｌｉｐｓ［１６］，Ｓｋｉｐｎｅｔ［１７］，Ｓｔｒｕｃｔｕｒｅｄｓｕｐｅｒｐｅｅｒｓ［１８］
等。Ｃｈｏｒｄ作为典型的ＤＨＴ查算法具有结构简单、查速度机器码注册码
快和负载平衡等特点。在Ｃｈｏｒｄ的基础之上，ＭＩＴ相继进行了
Ｏｎｅ－Ｈｏｐ
［５，６］
，Ｋｏｏｒｄｅ［７］
和ＥｐｉＣｈｏｒｄ
［８，９］
外置电源等跟进式的研究，这些算法
在速度和稳定性上有了更大的提高。本文在介绍Ｃｈｏｒｄ结构的基础之上，对最新的Ｏｎｅ－Ｈｏｐ和ＥｐｉＣｈｏｒｄ进行介绍，分析算法的性能。
２Ｃｈｏｒｄ
２．１Ｃｈｏｒｄ的构造
Ｃｈｏｒｄ是基于相容散列（ＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇ）［１０］的一种资源
定位及查算法。与传统的散列相比，相容散列具有更好的稳定性和负载平衡。相容散列使用Ｈａｓｈ函数，如ＳＨＡ－１［１１］，作用于网络中每个节点的ＩＰ，从而得到每个节点的标识；同样，使用ＳＨＡ－１作用于网络资源的“关键字”，从而得到每个网络资源的标识ｉｄ。 相容散列按如下规则将资源指定给节点：网络节点标识以
２ｍ为模构成环（ｍ为资源和节点标识的位数，即满足２ｍ－１≤节
点数量≤２ｍ）。资源ｋ被指定到环中等于ｋ的节点或者紧跟着
ｋ的节点，这个节点被称为ｋ的Ｓｕｃｃｅｓｓｏｒ节点，可以表示为
Ｓｕｃｃｅｓｓｏｒ（ｋ）。如果节点被表示为一个从０到２ｍ－１的环，那么Ｓｕｃｃｅｓｓｏｒ（ｋ）就是在环上从ｋ出发顺时针方向第一个遇到的节点。如图１，节点０、１、３；关键字１、２、６在节点环上的存储情况。
相容散列使节点加入和离开只会引起网络一小部分的变化。当一个节点ｎ加入时，一些先前指定到ｎ的Ｓｕｃｃｅｓｓｏｒ上的资源，现在要指定到ｎ；当ｎ节点离开环，那么原来存储在ｎ中的资源将自动转存于ｎ的Ｓｕｃｃｅｓｓｏｒ节点上。
２．２Ｃｈｏｒｄ查算法
２．２．１
简单查
Ｃｈｏｒｄ中的每个节点仅存储其Ｓｕｃｃｅｓｓｏｒ节点的地址，查
过程沿着Ｓｕｃｃｅｓｓｏｒ进行。算法如下：
ｎ．ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ（ｉｄ）ｉｆ（ｉｄ∈（ｎ，ｓｕｃｃｅｓｓｏｒ））
ｒｅｔｕｒｎｓｕｃｃｅｓｓｏｒ；ｅｌｓｅ
对等网中Ｃｈｏｒｄ资源查算法研究
张
震
王晓明
（暨南大学计算机科学系，广州５１０６３２）
Ｅ－ｍａｉｌ：ｚｈａｎｇ２００３１７４＠ｙａｈｏｏ．ｃｏｍ．ｃｎ
摘
要
在大规模的对等网络结构中，如何快速准确地确定资源的位置是一个比较突出的问题，基于ＤＨＴ（Ｄｉｓｔｒｉｂｕｔｅｄ
ＨａｓｈＴａｂｌｅ）资源定位及查算法是目前比较流行的算法之一，文章介绍了其中具有代表性的Ｃｈｏｒｄ算法以及基于Ｃｈｏｒｄ
的两种改进算法，对其进行了分析比较。关键词
对等网查算法
ＣｈｏｒｄＯｎｅ－ＨｏｐＥｐｉＣｈｏｒｄ
文章编号１００２－８３３１－（２００６）１１－０１４７－０６
文献标识码Ａ
中图分类号ＴＰ３０９
ＲｅｓｅａｒｃｈｏｎＣｈｏｒｄＬｏｏｋｕｐＡｌｇｏｒｉｔｈｍｆｏｒＰｅｅｒ－ｔｏ－ＰｅｅｒＮｅｔｗｏｒｋ
ＺｈａｎｇＺｈｅｎＷａｎｇＸｉａｏｍｉｎｇ
（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＪｉｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ５１０６３２）
Ａｂｓｔｒａｃｔ：ＡｎｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍｔｈａｔｃｏｎｆｒｏｎｔｓＰｅｅｒ－ｔｏ－ＰｅｅｒＮｅｔｗｏｒｋｉｓｔｈｅｅｆｆｉｃｉｅｎｔｌｏｃａｔｉｏｎｏｆｔｈｅｎｏｄｅｔｈａｔｓｔｏｒｅｓａｄｅｓｉｒｅｄｄａｔａｉｔｅｍ．ＴｈｅｒｅｓｅａｒｃｈｆｏｃｕｓｅｓｏｎｔｈｅＤＨＴ（ＤｉｓｔｒｉｂｕｔｅｄＨａｓｈＴａｂｌｅ），ｂｅｃａｕｓｅＤＨＴｌｏｏｋｕｐａｌｇｏｒｉｔｈｍｓｏｆｆｅｒａｓｃａｌａｂｌｅａｎｄｅｆｆｉｃｉｅｎｔｒｏｕｔｉｎｇａｎｄｏｂｊｅｃｔｌｏｃａｔｉｏｎｐｌａｔｆｏｒｍｆｏｒＰｅｅｒ－ｔｏ－Ｐｅｅｒｎｅｔｗｏｒｋｓ．ＷｅｉｎｔｒｏｄｕｃｅＣｈｏｒｄ，ｔｈｅｍｏｓｔｒｅｐｒｅｓｅｎｔａ
ｔｉｖｅＤＨＴｌｏｏｋｕｐａｌｇｏｒｉｔｈｍ．ＴｈｅｎｗｅｉｎｔｒｏｄｕｃｅｔｗｏｕｐｄａｔｅａｌｇｏｒｉｔｈｍｓｏｆＣｈｏｒｄ．Ｋｅｙｗｏｒｄｓ：Ｐｅｅｒ－ｔｏ－ＰｅｅｒＬｏｏｋｕｐａｌｇｏｒｉｔｈｍ，Ｃｈｏｒｄ，Ｏｎｅ－Ｈｏｐ，ＥｐｉＣｈｏｒｄ
基金项目：暨南大学自然科学基金资助项目
作者简介：张震（１９７５－），男，助教，主要研究方向：网络体系结构，路由算法，网络安全。王晓明（１９６０－），女，博士，教授，主要研究方向：网络体系结
５４５６
５１４８
４２
３８
３２
２１
１４
１
８
查５４
图２简单查过程
ＦｉｎｇｅｒＴａｂｌｅＦｉｎｇｅｒ［０］１４Ｆｉｎｇｅｒ［１］１４
Ｆｉｎｇｅｒ［２］１４Ｆｉｎｇｅｒ［３］２１Ｆｉｎｇｅｒ［４］３２Ｆｉｎｇｅｒ［５］４２ＦｉｎｇｅｒＴａｂｌｅＦｉｎｇｅｒ［０］４８Ｆｉｎｇｅｒ［１］４８Ｆｉｎｇｅｒ［２］４８Ｆｉｎｇｅｒ［３］５１Ｆｉｎｇｅｒ［４］
１
Ｆｉｎｇｅｒ［５］１４
５４
５６
５１４８
４２
３８
３２
２１
１４
１
８
图４升级查过程
ｒｅｔｕｒｎｓｕｃｃｅｓｓｏｒ．ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ（ｉｄ）；其查复杂度为Ｏ（ｎ）。
图２中描述了节点８查ｉｄ５４的过程：
２．２．２升级查
每个节点ｎ要维护一个包含ｍ个表项的ｆｉｎｇｅｒ表，ｍ为资
源和节点标识的位数，第ｉ个表项包含的是在节点环中存放（ｎ＋２ｉ－１）ｍｏｄ２ｍ的点ｓ，即ｓ＝Ｓｕｃｃｅｓｓｏｒ（（ｎ＋２ｉ－１）ｍｏｄ２ｍ），１≤ｉ≤
ｍ。称ｓ是ｎ的第ｉ个ｆｉｎｇｅｒ，表示为ｎ．ｆｉｎｇｅｒ［ｉ］。
定义１
ｆｉｎｇｅｒ［ｉ］：环中存储（ｎ＋２ｉ－１）ｍｏｄ２ｍ的点。
Ｓｕｃｃｅｓｓｏｒ：节点在环上的下一个节点，即ｎ．ｆｉｎｇｅｒ［１］。Ｐｒｅｄｅｃｅｓｓｏｒ：节点在环上的前一个节点。
图１中节点０，１，３的ＦｉｎｇｅｒＴａｂｌｅ，如图３所示。
特征
（１）每个节点保存部分其他点的信息，并且保存在环路上临近节点的信息量比远端节点的信息量大。
（２）每个节点只包含Ｏ（ｌｏｇＮ）个表项，造成一个节点通常没有足够的信息来直接到任何一个关键字。
算法如下：
ｎ．ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ（ｉｄ）ｉｆ（ｉｄ∈（ｎ，ｓｕｃｃｅｓｓｏｒ］）ｒｅｔｕｒｎｓｕｃｃｅｓｓｏｒ；ｅｌｓｅ
ｎ′＝ｃｌｏｓｅｓｔ．ｐｒｅｃｅｄｉｎｇ＿ｎｏｄｅ（ｉｄ）；ｒｅｔｕｒｎｎ′．ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ（ｉｄ）；ｎ．ｃｌｏｓｅｓｔ＿ｐｒｅｃｅｄｉｎｇ＿ｎｏｄｅ（ｉｄ）
ｆｏｒｉ＝ｍｄｏｗｎｔｏ１ｉｆ（ｆｉｎｇｅｒ［ｉ］∈（ｎ，ｉｄ］）ｒｅｔｕｒｎｆｉｎｇｅｒ［Ｉ］；ｒｅｔｕｒｎｎ；
如果ｉｄ在节点ｎ与其Ｓｕｃｃｅｓｓｏｒ之间，则ｉｄ一定存储在ｎ的Ｓｕｃｃｅｓｓｏｒ中；否则执行ｎ．ｃｌｏｓｅｓｔ＿ｐｒｅｃｅｄｉｎｇ＿ｎｏｄｅ过程查ｆｉｎｇｅｒ表，到与ｉｄ最近的节点ｎ′
；ｎ′再次调用ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ。这是因为越接近ｉｄ就会了解到更多的关于ｉｄ的信息，可以尽快地定位ｉｄ。图４显示对于图２中的查任务使用升级查算法以后的查过程。
节点８在其ｆｉｎｇｅｒ表中到最接近５４的节点４２，将请求发送给节点４２，同样４２在其ｆｉｎｇｅｒ表中到节点５１，节点４２将请求发送给５１，节点５１发现目标５４位于它与其Ｓｕｃｃｅｓｓｏｒ（即５６）之间，查成功，发送请求给节点５６，节点５６响应请求。查是一个递归的过程。
定理在ｎ个节点的网络中，升级算法的查复杂度为
Ｏ（ｌｏｇｎ）。
证明：假设节点ｎ要查存储资源ｋ的节点，假定ｐ是所求节点紧前面的一个节点，如果ｎ≠ｐ，则调用ｃｌｏｓｅｓｔ＿
ｐｒｅｃｅｄｉｎｇ＿ｎｏｄｅ（ｋ）在ｎ的ｆｉｎｇｅｒ中到最接近ｋ的节点。设ｐ
点在由ｉ确定的区域［ｎ＋２ｉ－１，ｎ＋２ｉ］，由于这个区域非空（包含ｐ），
节点ｎ会联系它的第ｉ个ｆｉｎｇｅｒｆ，ｎ与ｆ的距离至少是２ｉ－１；ｆ和
ｐ也在这个区域内，也就是说他们的距离至少是２ｉ－１，由于ｆ与ｐ
都在［ｎ＋２ｉ－１，ｎ＋２ｉ］区域内，它们的距离至多为２ｉ－１，这说明每一次节点的查过程都使得到的节点与目标节点的距离至少缩短一半。由于节点和ｉｄ的分布随机，那么查节点的数量就会为Ｏ（ｌｏｇｎ）。
２．３稳定性问题
Ｃｈｏｒｄ节点的频繁加入、失效或离开可能造成路由错误。
如果节点ｎ的加入是单一的，ｎ可以通过已知点ｎ′
进行ｍ＋１次ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ查过程到ｎ的Ｓｕｃｃｅｓｓｏｒ、Ｐｒｅｄｅｃｅｓｓｏｒ，并构
成其ｆｉｎｇｅｒｔａｂｌｅ。由于ｎ的加入一定会影响到某些节点的
ｆｉｎｇｅｒ，所以，随后要更新其他节点的ｆｉｎｇｅｒｔａｂｌｅ。这个过程是
完备的，但是，在网络环境中，节点的加入是随机的，如果每有一个节点加入就要进行一次全面的更新，系统消耗大，影响查速度。为此，Ｃｈｏｒｄ采用定期更新的方法。
Ｓｔａｂｉｌｉｚａｔｉｏｎ过程：
ＦｉｎｇｅｒＴａｂｌｅＦｉｎｇｅｒ［０］１Ｆｉｎｇｅｒ［１］３Ｆｉｎｇｅｒ［２］
０
Ｆｉｎｇｅｒ［０］３Ｆｉｎｇｅｒ［１］３Ｆｉｎｇｅｒ［２］
０
ＦｉｎｇｅｒＴａｂｌｅ
Ｆｉｎｇｅｒ［０］
０Ｆｉｎｇｅｒ［１］０Ｆｉｎｇｅｒ［２］
０ＦｉｎｇｅｒＴａｂｌｅ０
１
２
３
４
５
６
７
图３ＦｉｎｇｅｒＴａｂｌｅ
２
２
２
３
３
３
４５
１
４
４
ＳｌｉｃｅＬｅａｄｅｒＵｎｉｔＬｅａｄｅｒ
ＯｒｄｉｎａｒｙＮｏｄｅ
图５Ｏｎｅ－Ｈｏｐ的信息流程
ｎ．ｃｒｅａｔｅ（）ｐｒｅｄｅｃｅｓｓｏｒ＝ｎｉｌ；ｓｕｃｃｅｓｓｏｒ＝ｎ；ｎ．ｊｏｉｎ（ｎ′
）ｐｒｅｄｅｃｅｓｓｏｒ＝ｎｉｌ；
ｓｕｃｃｅｓｓｏｒ＝ｎ′＿ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ（ｎ）ｎ．ｓｔａｂｉｌｉｚｅ（）
ｘ＝ｓｕｃｃｅｓｓｏｒ．ｐｒｅｄｅｃｅｓｓｏｒ．ｉｆ（ｘ∈（ｎ，ｓｕｃｃｅｓｓｏｒ］）ｓｕｃｃｅｓｓｏｒ＝ｘ；ｓｕｃｃｅｓｓｏｒ．ｎｏｔｉｆｙ（ｎ）；
ｎ．ｎｏｔｉｆｙ（ｎ′
）ｉｆ（ｐｒｅｄｅｃｅｓｓｏｒｉｓｎｉｌｏｒｎ′∈（ｐｒｅｄｅｃｅｓｓｏｒ，ｎ））
ｐｒｅｄｅｃｅｓｓｏｒ＝ｎ′ｎ．ｆｉｘ＿ｆｉｎｇｅｒｓ（）ｎｅｘｔ＝ｎｅｘｔ＋１；ｉｆ（ｎｅｘｔ＞ｍ）ｎｅｘｔ＝１；
ｆｉｎｇｅｒ［ｎｅｘｔ］＝ｆｉｎｄ＿ｓｕｃｃｅｓｓｏｒ（ｎ＋２ｎｅｘｔ－１）；ｎ．ｃｈｅｃｋ＿ｐｒｅｄｅｃｅｓｓｒｏｒ（）ｉｆ（ｐｒｅｄｅｃｅｓｓｏｒｈａｓｆａｉｌｅｄ）ｐｒｅｄｅｃｅｓｓｏｒ＝ｎｉｌ；
ｎ．ｃｒｅａｔｅ（）：建立一个节点。
ｎ．ｊｏｉｎ（）：通过已知节点ｎ′
将ｎ加入到环中，ｎ只是考虑Ｓｕｃｃｅｓｓｏｒ的正确性，Ｐｒｅｄｅｃｅｓｓｏｒ初始为ｎｉｌ。
ｎ．ｓｔａｂｉｌｉｚｅ（）：节点定期执行，确认每个节点的Ｓｕｃｃｅｓｓｏｒ是
否正确。令ｘ＝Ｐｒｅｄｅｃｅｓｓｏｒ（Ｓｕｃｃｅｓｓｏｒ（ｎ）），如果ｘ∈（ｎ，ｎ．ｓｕｃ－
ｃｅｓｓｏｒ），说明ｘ是新近加入到ｎ后面的节点，调整ｎ的Ｓｕｃｃｅｓ－ｓｏｒ为ｘ，随后通过ｎｏｔｉｆｙ（）过程指定ｘ节点的Ｐｒｅｄｅｃｅｓｓｏｒ。
ｆｉｘ＿ｆｉｎｇｅｒｓ（）：使每个节点的ｆｉｎｇｅｒｔａｂｌｅ保持更新。ｃｈｅｃｋ＿ｐｒｅｄｅｃｅｓｓｏｒ（）：每个节点定期执行确定节点的Ｐｒｅ－ｄｅｃｅｓｓｏｒ是否有效，如果失效，就置为ｎｉｌ，在后面的ｓｔａｂｉｌｉｚｅ（）
中，通过ｎｏｔｉｆｙ（）加以更新。
Ｃｈｏｒｄ中，起码要保持节点Ｓｕｃｃｅｓｓｏｒ的正确性。这样查
至少是按着Ｓｕｃｃｅｓｓｏｒ逐步进行的，保证最终会到目标点。对于所有节点的ｆｉｎｇｅｒｔａｂｌｅ尽量保持更新，提高查效率（达到
Ｏ（ｌｏｇｎ））。
３Ｏｎｅ－Ｈｏｐ
对Ｇｎｕｔｅｌｌａ网络
［１３］
的研究
［１４］
表明：规模为１０００００个节点
的系统，平均每秒钟发生１９次成员变化事件，节点变化并不是非常频繁。可见Ｃｈｏｒｄ的稳定过程并没有占据过多的带宽，反而是递归查过程占用大量的带宽。基于上述分析开发了
Ｏｎｅ－Ｈｏｐ算法，尝试扩大节点路由信息，加快查速度。
３．１Ｏｎｅ－Ｈｏｐ
Ｏｎｅ－Ｈｏｐ将Ｃｈｏｒｄ环分割成ｋ个Ｓｌｉｃｅ（分片），每个Ｓｌｉｃｅ
都有一个ＳｌｉｃｅＬｅａｄｅｒ。Ｓｌｉｃｅ再次被分为ｕ个同样大小的分片，称为Ｕｎｉｔ，每个Ｕｎｉｔ选取Ｕｎｉｔ中间的节点作为ＵｎｉｔＬｅａｄｅｒ。
Ｏｎｅ－Ｈｏｐ的信息流程如图５。
（１）节点定时发送ｋｅｅｐ－ａｌｉｖｅ信息检查其Ｐｒｅｄｅｃｅｓｓｏｒ和
Ｓｕｃｃｅｓｓｏｒ的状况，如发现变化，将这个变化信息发送给它的ＳｌｉｃｅＬｅａｄｅｒ。
（２）ＳｌｉｃｅＬｅａｄｅｒ将成员节点的变化信息收集在一起，等待
ｔｂｉｇ时间，将这些信息发送给其他的ＳｌｉｃｅＬｅａｄｅｒ。ＳｌｉｃｅＬｅａｄｅｒ
之间的信息交换是异步的，这样可以节约带宽。
（３）ＳｌｉｃｅＬｅａｄｅｒ将成员节点的变化信息收集在一起，等待一小段时间ｔｗａｉｔ，将这个信息发送给这个Ｓｌｉｃｅ中的所有Ｕｎｉｔ
Ｌｅａｄｅｒ成员。
（４）每个ＵｎｉｔＬｅａｄｅｒ将ＳｌｉｃｅＬｅａｄｅｒ发送来的信息综合，加入到ｋｅｅｐ－
ａｌｉｖｅ信息中，发送给其Ｓｕｃｃｅｓｓｏｒ和Ｐｒｅｄｅｃｅｓｓｏｒ
节点。
（５）普通节点将接收到的ｋｅｅｐ－ａｌｉｖｅ信息沿着一个方向进行传播：如果从Ｐｒｅｄｅｃｅｓｓｏｒ接收到信息，那么就将信息传送给它的Ｓｕｃｃｅｓｓｏｒ；如果是从Ｓｕｃｃｅｓｓｏｒ接收到的信息，那么将信息传送给它的Ｐｒｅｄｅｃｅｓｓｏｒ。当信息传送到Ｕｎｉｔ的边界时，信息消亡。
３．２Ｏｎｅ－Ｈｏｐ算法分析
３．２．１
Ｏｎｅ－Ｈｏｐ中的时间设定
Ｏｎｅ－Ｈｏｐ的基本构想就是在节点中存储全部节点的路由
信息，算法效率和节点中存储信息的实时性关系密切。规定：当一个节点发现其Ｓｕｃｃｅｓｓｏｒ或者Ｐｒｅｄｅｃｅｓｓｏｒ发生变化后，在ｔｔｏｔ时间后，系统中所有节点都要知道这个变化。
定义２
ｔｗａｉｔ：ＳｌｉｃｅＬｅａｄｅｒ把信息传送给成员ＵｎｉｔＬｅａｄｅｒ的时间间隔；
ｔｓｍａｌｌ：ＵｎｉｔＬｅａｄｅｒ把信息传送给成员节点的时间间隔；
ｔｂｉｇ：ＳｌｉｃｅＬｅａｄｅｒ把信息传送给其他的ＳｌｉｃｅＬｅａｄｅｒ的时间
间隔；
ｔｄｅｔｅｃｔ：从发生变化到ＳｌｉｃｅＬｅａｄｅｒ发现变化的时间间隔。
当ＳｌｉｃｅＬｅａｄｅｒ收集完成员节点的变化信息后，在ｔｗａｉｔ＋ｔｓｍａｌｌ
后，Ｓｌｉｃｅ的所有成员节点会知道发生在本Ｓｌｉｃｅ中的所有变化。再经过ｔｂｉｇ，ＳｌｉｃｅＬｅａｄｅｒ将变化信息发送给其他ｋ－１个
ＳｌｉｃｅＬｅａｄｅｒ。再经过ｔｗａｉｔ＋ｔｓｍａｌｌ，系统所有的节点将了解发生的所有变化。那么ｔｔｏｔ＝ｔｄｅｔｅｃｔ＋ｔｗａｉｔ＋ｔｓｍａｌｌ＋ｔｂｉｇ。
定义３
ｆ：可接受的首次查失败比例；ｎ：系统中节点的数量；
ｒ：系统中成员节点变化比率。
假设节点均匀分布在环上，则失败请求比例应小于或者等于节点变化率，即：
ｒ≤ｆ×ｎｔｔｏｔ
，可以得到：ｔｔｏｔ≤
ｆ×ｎ
ｒ３．２．２
ｋ和ｕ的确定
筛底使用ｍ个字节来描述一个变化事件，ｖ个字节是构造数据
表１节点带宽表
ＳｌｉｃｅＬｅａｄｅｒ
ＵｎｉｔＬｅａｄｅｒＯｔｈｅｒｎｏｄｅｓ
上游带宽
ｒｍ（ｕ＋２）＋
２ｖｋ
ｔ
ｂｉｇ
２×ｒ×ｍ＋３ｖ
ｒ×ｍ＋２ｖ
下游带宽
ｒｍ＋
２ｖｋ
ｔ
ｂｉｇ
路网ｒ×ｍ＋２ｖ
ｒ×ｍ＋２ｖ
ｉｄ２
６２
５７
５１
４９
４７
４０
３５
３０
２０
２５
１７
１５
１０
６
０
Ｌｏｏｋｕｐ２
图６ＥｐｉＣｈｏｒｄ查示例
节点
３０
５１
６２
１０
０
节点路由信息
…，６２，５１，１０，２０，…
…，５７，６２，０，１０，…
…，５７，０，６，１０，…
…，６２，０，６，１５，…
…，５７，６２，６，１７，…
表２节点路由表
ｔ
０
１
２
３
４
５
６
７
操作
向１０，５１，６２发送请求
５１回复（５７，６２，０，１０）
向０发送请求
６２回复（０，６）
向６发送请求
１０回复（６２，０，６）
０回复（６）
６回复
等待回复
的请求
１０，５１，６２
１０，６２
０，１０，６２
０，１０
０，６，１０
０，６
６
最好的
Ｐｒｅｄｅｃｅｓｓｏｒ
６２
０
０
０
０
０
０
最好的
Ｓｕｃｃｅｓｓｏｒ
１０
１０
１０
６
６
６
６
查成功
表３ＥｐｉＣｈｏｒｄ搜索过程
包的额外消耗。考察下面四种通信：
（１）ｋｅｅｐ－ａｌｉｖｅ信息：ｋｅｅｐ－ａｌｉｖｅ信息构成了系统底层通信。假定ｋｅｅｐ－ａｌｉｖｅ信息是每秒钟发送的，每个信息中包含ｒ个事件信息，则ｋｅｅｐ－ａｌｉｖｅ信息的大小为ｒ×ｍ＋ｖ；每个节点接收到这个信息以后要发送确认信息，大小为ｖ。因此，上、下游带宽均为：ｒ×ｍ＋２ｖ。
（２）普通节点通知ＳｌｉｃｅＬｅａｄｅｒ的信息：每个Ｓｌｉｃｅ中每秒
发生ｒ
ｋ
个变化，因此ＳｌｉｃｅＬｅａｄｅｒ的下游带宽为
ｒ×（ｍ＋ｖ）
ｋ
；每
个信息都要做回复，即上游带宽为ｒ×ｖ
ｋ
。
（３）ＳｌｉｃｅＬｅａｄｅｒ之间的交换信息：每个ＳｌｉｃｅＬｅａｄｅｒ收集ｔｂｉｇ时间内成员的变化信息，信息的大小为ｒ
ｋ
×ｔｂｉｇ×ｍ＋ｖ，ＳｌｉｃｅＬｅａｄｅｒ将这个信息发送给其他ｋ－１个ＳｌｉｃｅＬｅａｄｅｒ，随后收到他们的回复信息，显然，所有的ＳｌｉｃｅＬｅａｄｅｒ的上游和下游带
宽是对称的：（ｒ×ｍ
ｋ
＋２ｖ
ｔｂｉｇ
）（ｋ－１）。
（４）ＳｌｉｃｅＬｅａｄｅｒ与ＵｎｉｔＬｅａｄｅｒ之间的信息：ＳｌｉｃｅＬｅａｄｅｒ将过去ｔｗａｉｔ＝１ｓ中收集到的信息构成一个批次发送，这个批次中包含ｒ个变化信息，信息的大小为（ｒ×ｍ＋ｖ）×ｕ。去除可忽略的信息，系统中每个节点的带宽使用情况见表１。
可以看出，ＳｌｉｃｅＬｅａｄｅｒ上游带宽使用量很大，系统需要通过调整ｋ、ｕ减少这个带宽。ｋ和ｕ决定了每个ｕｎｉｔ的大小，由于ＵｎｉｔＬｅａｄｅｒ在ｕｎｉｔ的中间并且ｋｅｅｐ－ａｌｉｖｅ信息是每秒钟发
送的，那么ｔｓｍａｌｌ的大小就是ｕｎｉｔ大小的一半，即：ｔｓｍａｌｌ＝
ｎ
２ｋｕ
。给
定了ｔｗａｉｔ和ｔｄｅｔｅｃｔ以后，通过ｔｓｍａｌｌ和ｔｔｏｔ能够确定ｔｂｉｇ的大小。为了分析简单，假定ｔｄｅｔｅｃｔ＝３ｓ，ｔｗａｉｔ＝１ｓ；给定ｎ，ｒ和ｆ值以后，分析ｋ和ｕ。将上面的假定带入到ＳｌｉｃｅＬｅａｄｅｒ的上游带宽公式中，经过证明我们得到如下结论：当
ｋ＝ｒ×ｍ×ｎ
４ｖ
!
ｕ＝４ｖｎ
ｒ×ｍ×（ｔｔｏｔ－ｔｗａｉｔ－ｔｄｅｔｅｃｔ）２
!
翻罐笼时，ＳｌｉｃｅＬｅａｄｅｒ的上游带宽最小。
由ｎ＝２ｋｕ×ｔｓｍａｌｌ，得到ｔｓｍａｌｌ＝ｔｂｉｇ。
４ＥｐｉＣｈｏｒｄ
大多数的ＤＨＴｓ查算法是通过节点主动发送探测信息来不断更新保存在本地的路由信息；ＥｐｉＣｈｏｒｄ引入了反应式路由维护策略：节点在查询的时候，通过其他节点的回复信息更新本地的路由信息。这种反应式策略不能保持路由的及时更新，为此，在ＥｐｉＣｈｏｒｄ中采用并行查，通过加快查速度缓解这个问题。
４．１并行查算法
节点根据本地路由信息产生ｐ个并行查询：其中１个发给和目标值最接近的后继节点，其余的发给和目标值最近的ｐ－１个前驱节点。请求发送是异步的，目的是节约带宽。系统采用两种方法来发现新的路由信息：
（１）当一个节点第一次加入网络，它从临近的节点（Ｓｕｃ－ｃｅｓｓｏｒ、Ｐｒｅｄｅｃｅｓｓｏｒ）中获得完整的路由信息的拷贝。
（２）节点通过查询的回复信息更新本地路由。
当节点ｎ收到查询后做出如下三种回复：
①ｎ包含目标，则返回目标，查成功；
②如果ｎ是目标的前驱节点，ｎ会从本地路由信息中提供其Ｓｕｃｃｅｓｓｏｒ信息以及通往目标的ｌ个最好的下一跳节点信息；
③如果ｎ是目标的后继节点，ｎ会从本地路由信息中提供其Ｐｒｅｄｅｃｅｓｓｏｒ信息以及通往目标的ｌ个最好的下一跳节点信息。
ｌ个最好的下一跳：根据本地路由信息到紧跟在目标后面的一个节点以及ｌ－１个目标最近的前驱节点。
可以得出这样的结论，当ｐ增大时，系统性能提高，查速度更快、延时更小。实验也验证了这一点［８］，但当ｐ≥３时，随着ｐ增大，系统性能提高就不是很明显了，为了节约节点资源，设定ｐ＝３。
图６中点３０寻ｉｄ２，表２为每个节点已有的路由信息，表３为ＥｐｉＣｈｏｒｄ查过程，其中ｐ＝３，ｌ＝３。控制器设计
ＥｐｉＣｈｏｒｄ采用反复式查方式而不是递归式的，即：节点并行发送ｐ个请求，等待请求回复信息；这个查询将更加接近目标。ＥｐｉＣｈｏｒｄ的反复式查询方式避免了发送多余的信息：如
ｎｑ－１
ｎｑ－２
ｎｑ
ｎｘ
ｎ１
ｎ２
２１
ｑ
ｑ－１
ｑ－２
３图９ＥｐｉＣｈｏｒｄ强稳定算法
ｎ
图７ＥｐｉＣｈｏｒｄ节点路由信息分片
ｎ
ｍ
图８
全局错误示意图
果使用ｐ个并行的递归查，当一个查线程到目标时，其他递归查线程还会继续下去，浪费很大的带宽。
４．２反应式路由维护
反应式路由维护主要内容有三个方面：
（１）ＥｐｉＣｈｏｒｄ系统中，每条路由信息都有固定的生存时间。
当节点接收到信息（无论是请求还是回复）时，如果节点的路由中没有发送点的信息，则添加发送点的路由信息，并将加入时间设定为本地时间；如果已含有发送点的信息，那么重新设置加入时间为本地时间。请求响应中的每条路由信息包含生存时间（发送点发送信息时的时间减去路由信息的加入时间），生存时间信息用于设置或者重新设置接受节点各路由信息的生存时间。路由信息在以下两种情况下被清除：它映射的节点不响应请求达到一定的数量；或者生存时间超过了指定门限ｔ。
（２）为了保证ＥｐｉＣｈｏｒｄ至少也具有Ｃｈｏｒｄ的效率Ｏ（ｌｏｇｎ），对ＥｐｉＣｈｏｒｄ节点中的路由信息分片。每个节点路由表分割为两个对称的指数级（如２）大小的分片Ｓｌｉｃｅ，如图７。随着查逐渐接近目标，每个Ｓｌｉｃｅ中的路由信息成指数增长，这样的分片机制提供了查路径Ｏ（ｌｏｇｎ）的保证。
（３）为了保证系统效率，ＥｐｉＣｈｏｒｄ规定每个Ｓｌｉｃｅ中必须包含一定数量的有效路由信息。如果某个分片中没有足够多的有效路由信息，那么节点将向这个分片中的中间节点发送查询信息，通过查询获取补充路由信息。
４．３稳定性算法
当有大量节点同时加入到环上同一位置时，会引起地址错误；另外，当节点未作宣布就离开会造成出现孤儿节点，即环路上的节点不知道这些节点的存在。ＥｐｉＣｈｏｒｄ采用两种稳定算法：弱稳定
算法和强稳定算法。
４．３．１弱稳定算法
弱稳定算法为保持局部节点稳定的算法。节点定期检查它的Ｓｕｃｃｅｓｓｏｒ和Ｐｒｅｄｅｃｅｓｓｏｒ是否有效，如果发现了新的
Ｓｕｃｃｅｓｓｏｒ和Ｐｒｅｄｅｃｅｓｓｏｒ就作路由更新，也就是说节点只维护局
部信息的正确。
弱稳定算法无法修复全局错误，如图８所示，对于这样的错误只能通过强稳定算法修复。
４．３．２强稳定算法
强稳定算法为保持全局节点稳定的算法。强稳定算法的设计是基于一个简单的思想：回路。图８中，ｎ节点发送一个包含本身标识的探测包，探测包沿着Ｓｕｃｃｅｓｓｏｒ发送，当探测包到达节点ｍ，ｍ通过其Ｓｕｃｃｅｓｓｏｒ以及探测包中ｎ的标识发现路由错误；在ｍ节点执行弱稳定算法修正这个错误。探测包经历整个
环路，效率低；有效的方法是将环路分段，向各段并行发送探测包，探测包沿着Ｓｕｃｃｅｓｓｏｒ指针传送，通过传送路径发现错误。
算法如下：
（１）节点ｘ根据其路由信息在环路上选取ｑ个均匀分布的节点：ｎ１，ｎ２，ｎ３，…，ｎｑ，满足ｎｘ＜ｎ１＜ｎ２＜ｎ３＜…＜ｎｑ；
（２）ｘ发送一个以ｘ为目标的探测包给ｎｑ；
（３）ｘ继续发送给ｎｉ一个以ｎｉ＋１为目标的探测包，其中ｉ＝ｑ－
１，…，１，如果ｎｊ失效了，那么就用它的Ｓｕｃｃｅｓｓｏｒ代替；
（４）ｘ生成一个以ｎ１为目标的探测包，发送给ｘ的Ｓｕｃｃｅｓｓｏｒ节点。算法如图９所示。
当探测包到达标识大于或者等于目标的节点时，探测包消亡。探测包消亡时有如下两种情况出现：
（１）探测包经过的网络段不存在错误：如果探测包在它的目标节点消亡，或者在目标节点的Ｓｕｃｃｅｓｓｏｒ节点消亡。
（２）探测包经过的网络段存在错误：如果探测包没有在（１）中指定的节点消亡，即探测包节点越过了目标到达了另外的一个段中的节点，但这个点却不是目标节点的Ｓｕｃｃｅｓｓｏｒ，这说明出现全局错误，ＥｐｉＣｈｏｒｄ利用这两个段交接部分的节点信息纠正错误。
如果系统的规模庞大，即ｎ／ｑ也比较大，这样每一段中的探测包传递非常耗时。对于这种情况，系统通过对分段进行再分段来解决，如节点ｙ接收到探测包其目标地址为ｎｚ，那么在ｎｙ和ｎｚ节点之间再次选取ｑ个节点，ｎｙ＜ｎ１＜ｎ２＜…＜ｎｑ＜ｎｚ，重复上面描述的算法。可见，强稳定算法的算法复杂性为Ｏ（ｎ２）。
５总结
Ｃｈｏｒｄ算法是结构简单，容易实现的一种ＤＨＴ算法。节点中保存Ｏ（ｌｏｇｎ）个局部路由信息，使用递归搜索算法把这些分散的路由信息结合成一个整体，充分体现了对等网络分布式的特
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议