摘录


Kademlia 协议(以下简称 Kad)是美国纽约大学的 P. Maymounkov 和 D. 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 的计算方法不同。

点评

算法的魅力

原文

点击这里查看原文

其它

本帖内容由21QA云收藏工具自动生成,欢迎使用。

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055

提问于 04 六月, 14:38

%E8%B7%AF%E4%BA%BA%E7%94%B2's gravatar image

路人甲
131266457557


参考1

原作者论文

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
永久链接

回答于 04 六月, 14:39

%E8%B7%AF%E4%BA%BA%E7%94%B2's gravatar image

路人甲
131266457557

编辑于 13 六月, 14:27


I'm assuming you've read the Kademlia paper. Here's an excerpt from my article An Introduction to Kademlia DHT & How It Works

Some background information:

When you have a Kademlia network running, there should always be a node that every other node knows about in order for them to join the network; lets call this the Bootstrap node BN.

K is a Kademlia constant that determines the size of the Buckets in a node's routing table as well as the amount of nodes a piece of Data should be stored on.

Joining Process:

A new Node NN is created with a NodeId (assigned by some method) and an IP Address (the IP of the computer it's hosted on).

NN sends a LookupRequest(A.NodeId) to BN. A Lookup Request basically asks the receiving node for the K-Closest nodes it knows to a given NodeId. In this case, BN will return the K-Closest nodes it knows to NN.

BN will now add NN to it's routing table, so NN is now in the network.

NN receives the list of K-Closest nodes to itself from BN. NN adds BN to it's routing table.

NN now pings these K nodes received from BN, and the ones that reply are added to it's Routing Table in the necessary buckets based on distance. By pinging these nodes, they also learn of NN existence and add NN to their Routing tables.

NN is now connected to the network and is known by nodes on the network.

NN now loops through each of it's K-Buckets

foreach(K-Buckets as KB)         
    1. NN generates a random NodeId `RNID` // A NodeId that will be in KB 
    2. NN sends LookupRequest(RNID) to the K-Closest nodes it knows to RNID. 
    3. The response will be K nodes closest to RNID.
    4. NN now fills KB. 
NN does this for each of it's buckets to fill these buckets. After this operation, NN has a better idea of the nodes on the network at different distances away from itself.

Note: This step is not mandatory, however I did it in My Implementation of Kademlia so that each node will have better knowledge of the network when they join.

I wrote a full introduction to Kademlia at An Introduction to Kademlia DHT & How It Works

reference

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055
永久链接

回答于 13 六月, 14:54

%E8%B7%AF%E4%BA%BA%E7%94%B2's gravatar image

路人甲
131266457557

编辑于 13 六月, 14:56

你的回答
切换预览

你可以使用订阅来关注这个问题

使用邮箱订阅:

登录后可以订阅更新

使用RSS订阅:

回答

回答与评论

文字标记基础知识

  • *斜体文字* 或者 _斜体文字_
  • **黑体文字** 或者 __黑体文字__
  • 插入超链接: [链接文字](http://url.com/ "标题")
  • 插入图片: ![alt](/path/img.jpg "标题")
  • 编号排列: 1. Foo 2. Bar
  • 输入换行符前请输入两个空格(即:空空回车),仅敲回车无效。
  • 支持基本的HTML标签的使用

问题的标签:

×576
×33

问题发表于: 04 六月, 14:38

问题被查看: 115 次

最近更新: 13 六月, 14:56

powered by O*S*Q*A

粤ICP备14040061号-1