论文部分内容阅读
对等网应用所面临的一个关键问题是如何有效定位存储特定资源的结点。不同的对等网查找算法采用不同的策略,其查询效率也有所不同。本文分析了一种分布式查找算法Chord。Chord作为第二代对等网算法,以分布式散列表为查找策略。Chord算法是可改进的,并且每个结点只需维持对数级的Chord环上结点数的结点,便可完成通信任务,而且需要传递的信息量也是对数级的。Chord算法具有负载平衡、可靠性、可扩展性等优点,但是它的查询效率比较低。针对Chord算法的不足,本文提出了Full-Chord算法。Full-Chord算法主要改进了Chord算法的指针表,将原来计算指针表的公式扩展为两个,这样可以在顺时针和逆时针两个方向上同时进行。Full-Chord算法在查询开始时,就能将查询限制在半个Chord环上,这样便能更接近目标结点,提高查询效率。通过理论分析,Full-Chord算法的查询效率明显优于Chord算法。对等网中结点加入和离开是很平常的,因此必需考虑对等网的自适应性。关于这个方面,本文做了大量研究,提出了为每个结点再建立一张拥有r个后继结点的后继列表的设想,很好地解决了这个问题。本文还借鉴了small-world领域的研究成果,扩展了Chord算法。通过对结点度数的分析,提出“超级结点”的概念。并且参考Google的网页搜索技术PageRank,给出了计算结点级别的公式noderange,从而能很好地确定超级结点。通过超级结点,可以更加有效地定位资源,提高查询效率。最后,通过仿真测试表明,Full-Chord算法在平均查找路径长度和平均查询时间这两个方面的性能明显优于原始Chord算法。