|
if mylist.find(key) or copylist .find(key) //找到所查询的信息或复制 then result . done <-- true //查询完成 result.info <-- getinfo(key) 取得key 对应的信息 doRCP(lasthopinfo , result.info) //将节点信息复制到上一跳节点以改善热点查询 155 else result . done <-- false // 查询未完成 result . next <-- getnexthop (key) //返回自身finger 中最靠近key 的节点信息 end if return result 可以看到，CH-Chord 在节点加入时使用原有RCP 返回复制信息，仅查询到结果时进行 160 一次额外RCP 调用，同时由于复制信息而使得原本的查询跳数减少，由此产生的RCP 数也 减少，因此该算法并没有产生更多的网络消耗。对于网络中的各个节点，只有节点上的储存 被查询信息的储存空间增加了数倍。 2.4 并行查询 并行查询的优势在于可以通过同时访问不同的节点，降低访问高延迟节点的概率，因此 165 可以降低平均路由时间。将CH-Chord 算法与并行的查询方式相结合，不仅可以降低平均延 迟时间，而且由于并行增加了对各个节点的访问，也增加了访问拥有复制信息的节点的可能 性，因此还能一定程度上降低平均查询跳数。在查询的并行路数上，文献[5]结果显示随着 并行数目的增大，其降低查询时间的效果随之降低，并行路数在5 之后的效果不在明显，因 此本论文中采用并行路数为5 进行实验。 170 3 仿真实验结果分析 实验选取在ubuntu10.0 系统上的p2psim-0.3 作为仿真平台。仿真实验中节点由随机网络 拓扑生成，模拟网络环境的平均网络延迟为110ms，生成拓扑节点数为2000，4000，6000， 8000，10000 时的状态,，实验结果如图4——图6 所示。 3.1 路由跳数与查询时间分析 175 图4 节点与平均跳数 图4 为在不同数量的节点中路由查询的平均跳数，其中参数p 代表查询并行路数，从图 中可以看出，基于节点信息复制的算法CH-Chord 的查询平均跳数少于标准Chord 算法以及 180 改进路由表结构的F-Chord 算法，并与并行查询的方法在跳数上接近。但是CH-Chord 与并 行查询算法结合后平均查询跳数再次降低。CH-Chord 能够降低平均查询跳数的原因：Chord 查询不仅仅是一个查询节点通过访问finger 逐渐接近key 所在节点的过程，同时也是一个对 被查询节点逐渐精确定位的过程。Chord 查询的每一跳，都将Chord 查询发起节点与被访问 节点之间的Chord 空间分为两个部分，即排除被查询节点的部分和被查询节点所在的部分， 185 然后再对被查询节点所在的部分进行下一跳，重复这样的方法直到最终定位到一个点。 CH-Chord 方法将所要查询的信息复制到之前数个节点（数量等于节点后继数），使得该定 位过程不再精确到最后一个节点，降低了定位的精度，因此减少平均路由跳数。 图5 节点与平均查询时间 190 图5 为在不同节点时的平均查询时间，由结果可以看出，最大路由跳数的降低，同时降 低了平均查询时间。与标准的Chord 相比，结合了并行查询的CH-Chord 在平均查询时间上 减少了约40%到50%，使得Chord 查询更加高效。 3.2 网络带宽占用分析 195 图6 节点平均网络带宽占用 图6 为Chord 在稳定查询时的带宽占用情况，其中带宽单位为（Byte/node/s）。图中 CH-Chord 算法与标准的Chord 相比，在稳定状态并没有占用额外的带宽。虽然在查询过程 200 中对查询数据进行复制需要额外使用额外的RCP 调用，但是由于CH-Chord 减少了平均跳 数使得查询时的RCP 减少，因此总体上并没有增加带宽占用。与此相比通过改变路由表结 构的方法的F-Chord 则比其他算法占用更多的带宽，因为F-Chord 需要维护更长的路由表项。 这也证明了Chord 中节点的主要带宽消耗是在路由表的维护而非在查询上。 4 结论 205 本文分析了Chord 查询时被查询节点之前的节点会被频繁访问的路由特点，提出了一种 基于节点信息复制与查询热点的路由表改进算法CH-Chord，该算法通过将节点信息复制到 自身的前驱节点，使得路由查询提前结束从而降低平均查询跳数与查询时间。通过分析与实 验证明了该算法能在有效减少平均查询时间与跳数同时不增加Chord 维护的消耗。下一步的 研究方向是CH-Chord 在实际的系统中如何维护复制后的信息。 210 [参考文献] (References) [1] David Karger, Eric Lehman1 Tom Leighton, Matthew Levine1,Daniel Lewin,Rina Panigrahy.Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web[OL].[1997]http://theory.lcs.mit.edu/ 215 [2] Giovanni Chiola, Gennaro Cordasco, Luisa Gargano, Alberto Negro, and Vittorio Scarano. Optimizing the ¯nger table in Chord-like DHTs[OL].[2008] http://web-minds.consorzio-cini.it/ [3] G. Cordasco, L. Gargano, A. Negro, and V. Scarano F-Chord: Improved Uniform Routing on Chord[OL].[2004] http://onlinelibrary.wiley.com/ [4] Frank Dabek, Jinyang Li, Emil Sit, James Robertson, M. Frans Kaashoek, Robert Morris. Designing a DHT for 220 low latency and high throughput[J].ACM,2004 [5] 徐春丹.基于DHT 的结构化P2P 路由协议Chord 的研究[D]. 北京:北京邮电大学,2010 [6] 祁玉, 张新有chord 路由表结构的分析与改进[J] .计算机工程与设计. 2010-03-28 [7] 肖永刚.Chord 网络模型的研究和改进[D].北京:北京邮电大学. 2010-03-01 学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表 |
