基于小世界模型的DHT路由-上海交通大学P2P研究与开发网.PDFVIP

申请上海交通大学博士学位论文 第3章 基于小世界模型的DHT路由 第3章 基于小世界模型的 DHT 路由 3.1 引言 路由是 P2P 系统的基础，提高路由性能是 P2P 系统的一个极关键问题，因 而非常受到重视。现存的使用 DHT-P2P 系统诸如 CAN/Chord/Tapestry/Pastry 路 CAN 的路由效率相对比较糟糕，特别是在低 由性能各有它们的优点和局限性。 维的情况下，但它能使用低度的路由表来保持相对较低的维护开销。 Chord/Tapestry/Pastry 有着较优的路由效率却不得不忍受较高的维护开销。在负 载较重的动态环境下，它甚至导致路由颠簸问题[XU 2003a]。 本章研究了 DHT 路由的一种改进策略，并由此展示了 DHT-P2P 系统中以较 低的维护开销实现有效的资源定位的可行途径。研究工作是以 CAN 为基础，但 略加变换后同样适用于其它的 DHT 路由算法。我们的主要创新是在结构化路由 层上构造了小世界模式，并由此改进路由性能。 本章工作主要受 Kleinberg 最近研究成果的启发[KLEI 2000]。Kleinberg 提出 如果将n ×n 个节点放入一个二维网格中并且每个节点都有一些短链和仅一条长 链，采用贪婪路由能够以平均O(log2 n) 跳在任何一对节点间传送消息。Kleinberg 的理论对建立和改进低度P2P 系统非常有用。目前已有一系列 Kleinberg 式的网 络构造诸如[MANK 2003a,DAHL 2002]。在CAN 中构建小世界是一个非常直觉 的想法。因为 CAN 有着和 Kleinberg 模型相似的拓扑结构。然而，Kleinberg 模 型是一个静态模型，它使用所有节点的全局信息来构建小世界现象。反过来， P2P 系统中节点的加入和离开是自由的并且每个节点只拥有整个系统的一小部分信 息。例如，CAN 节点是自由地加入和离开的，并且每个节点只知道它的 2d 个邻 居节点。因此，我们尝试概率缓存节点代替 Kleinberg 模型中的静态结构来模型 小世界现象。这种方法的潜在收益是能够以一种极低廉的代价来改进路由性能。 因为概率缓存技术在我们改进 CAN 的设计中非常重要，所以我们将此改进的 CAN 命名为 PCCAN （Probabilistic Cache-based CAN ）。 本章其余部分组织如下：3.2 节介绍小世界模型；3.3 节介绍基于小世界模型 构造的 PCCAN 设计原理和方法；3.4 节对于 PCCAN 性能进行分析；3.5 节讨论 了性能影响多方面的问题；3.6 节给出了实验结果；3.7 节和 3.8 节分别对比相关 - 37 - 申请上海交通大学博士学位论文 基于分布式哈希表的对等系统关键技术研究 工作并总结本章内容。 3.2 小世界模型 小世界现象，即大多数人都被许多条由熟人构成的短链连接着的理论，是由 Stanley Milgram [MILG 1967]在六十年代作为社会学问题首次提出的。我们可以 用 Milgram 实验中一个典型的例子来具体描述一下社会学中的小世界现象。1976 年，当时的哈佛大学教授 Milgram 作了这样一个试验，在内布拉斯加州的奥马哈 随机选出 160 个当地居民，让他们每人设法将一封信传递到麻省的波士顿中作 的一个零售店主手中。这些人将信交给他认为最接近目标的一位朋友手中，接下 来由这位朋友以同样的方式传递到下一位朋友手中，直到最后信送达目标人手 中。实验结果是，最后有42 封信到达了目标人手中，而且这些信的平均中间传 递人数为 5.5 人。相比较 2 亿美国人口，这个数字显得非常低。这就是非常著 名的“小世界”现象。大量的试验表明，一条成功链的平均中间步数是在 5 步到 6 步之间，因而它也被称为“6 度分离”现象。在通信网络中，如果网络中的任何 两个节点都能以短跳距相连，即可以通过少量的链路往返在