kademlia原理详细解读资源-CSDN文库

4星 · 超过85%的资源需积分: 20 64 浏览量 2009-06-16 10:52:54 上传评论收藏 296KB PDF 举报

资源推荐

资源详情

资源评论

Kademlia 协议原理简介

MMX，k7mmx@tom.com

2006.2.20

欢迎参观我的宝宝乐园

http://blog.sina.com.cn/u/1227242305

一、前言

Kademlia协议（以下简称Kad）是美国纽约大学的PetarP. Maymounkov和David Mazieres.

在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based on

the XOR metric》。

简单的说，Kad 是一种分布式哈希表（DHT）技术，不过和其他 DHT 实现技术比较，如

Chord、CAN、Pastry 等，Kad 通过独特的以异或算法（XOR）为距离度量基础，建立了一种

全新的 DHT 拓扑结构，相比于其他算法，大大提高了路由查询速度。

在 2005 年 5 月著名的 BiTtorrent 在 4.1.0 版实现基于 Kademlia 协议的 DHT 技术后，

很快国内的 BitComet 和 BitSpirit 也实现了和 BitTorrent 兼容的 DHT 技术，实现

trackerless 下载方式。

另外，emule 中也很早就实现了基于 Kademlia 类似的技术（BT 中叫 DHT，emule 中也叫

Kad，注意和本文简称的 Kad 区别），和 BT 软件使用的 Kad 技术的区别在于 key、value 和

node ID 的计算方法不同。

二、节点状态

Kad 网络中每个节点都有一个 160bit 的 ID 值作为标志符。节点 ID 的生成，各种具体的

应用软件有不同的实现方法，一般是选择一个不重复的值进行 SHA－1 计算，这个值可以是

用户的 IP 地址，或者只是简单的随机生成。

在 Kad 网络中，所有节点都被当作一颗二叉树的叶子，并且每一个节点的位置都由其 ID

值的最短前缀唯一的确定。

对于任意一个节点，都可以把这颗二叉树分解为一系列连续的，不包含自己的子树。最

高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的

一半组成；依此类推，直到分割完整颗树。图 1 就展示了节点 0011 如何进行子树的划分：

图 1：节点 0011 的子树划分

虚线包含的部分就是各子树，由上到下各层的前缀分别为 1，01，000，0010。

Kad 协议确保每个节点知道其各子树的至少一个节点，只要这些子树非空。在这个前提

下，每个节点都可以通过 ID 值来找到任何一个节点。这个路由的过程是通过所谓的 XOR（异

或）距离得到的。

图 2 就演示了节点 0011 如何通过连续查询来找到节点 1110 的。节点 0011 通过在逐步

剩余10页未读，继续阅读

内容反馈

lolivia60

2013-07-02

很详细，非常好~~

hongtonglou

粉丝: 0
资源: 1

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip