综述

每个节点都有一个全局唯一的标识符，称为节点 ID。 节点 ID从160bit空间中随机选取，与BitTorrent的infohash值的空间相同。距离度量用来比较两个节点或者节点与infohash之间的远近程度。节点必须维护一个含有少量其他节点联系信息的路由表。ID越靠近自身ID时，路由表越详细。节点知道很多离它很近的节点，只知道少量离它很远地节点。

在Kademlia中，距离度量采用异或计算，结果解释成一个无符号整数。
distance (A,B)=|A ? B|
值越小，距离越近。

当一个节点需要查找一个torrent的peer时，它计算torrent的infohash和本地路由表中的节点 ID的距离。然后向与该torrent最近的一些节点请求该当前正在下载该torrent的peer信息。如果某个节点有这些信息，就直接回复。否则，它必须回复在它的路由表中离这个torrent更近的节点。如此不断重复的搜索更近的节点，直到找不到。当搜索结束之后，peer将自己的联系信息注册到离 torrent最近的节点。

查询peer请求的返回值（包含一个不透明值），称之为令牌。当一个节点通知其他节点它的peer正在下载一个torrent的时候，它必须使用最近向那个节点查询peer请求时，获得的令牌。当一个节点试图公告一个torrent，它所请求过的节点根据这个节点的IP地址检查它的令牌是否有效。这个机制可以防止恶意主机向其他主机注册torrent。由于令牌仅仅由请求节点返回给它所接收到令牌的那个节点，所以并没有规定具体实现。令牌应该在分发出去之后的一段合理时间内被接受。BitTorrent的实现是，用对方的IP地址和一个密码（这个密码每五分钟更换一次），计算SHA1作为令牌，这个令牌的有效时间是十分钟。

路由表

每个节点维护一个路由表，由它所知道的好节点组成。路由表中的节点被用作在DHT中发送请求的起点。当其他节点查询时，就返回路由表中的节点。

并不是我们所知的每个节点都是一样的。一些是好的，而另一些不是。很多使用DHT的节点都可以发送请求和接收应答，但是不能应答其他节点的请求。有一点很重要：每个节点路由表中的节点都应该是好节点。一个节点在过去的15分钟内应答过本节点的的某个请求，它就是一个好节点；如果它曾经应答过本节点的某个请求，并且在过去的15分钟内向本节点发送过请求，它也是一个好节点。如果一个节点15分钟没有活动，它就变成可疑节点。如果它连续多次未能应答请求，它就变成坏节点了。我们所知的好节点被赋予较未知状态的节点更高的优先级。

路由表覆盖整个节点ID空间（从0到2¹⁶⁰）。路由表被细分成“桶”，每个桶覆盖一部分空间。一张空表只有一个桶，它覆盖的空间是min=0，max=2¹⁶⁰ 。当一个ID是N的节点插入路由表中时，它被放进min<=N<max的桶中。一张空表只有一个桶，因此任何一个节点都可以放进去。每个桶在装满之前，最多只能存放K个节点，目前是8个。当一个桶装满了好节点之后，就不能再往里面加入别的节点，除非当前节点的ID落入桶的覆盖范围之内。这样的话，这个桶将被两个新桶替换掉，两个新桶分别覆盖原来一半的空间，并且原来桶里面的节点重新分发到新桶之中。对一张只有一个桶的新表来说，满的桶总是被分割成两个分别覆盖0-2¹⁵⁹和2¹⁵⁹-2¹⁶⁰的桶。

当一个桶装满了好的节点，新的节点将被丢弃。如果桶中的某个节点变坏了，那么它将被一个新节点替换。如果桶中一些可疑节点长达15分钟没有活动，最久不活跃节点将被ping。如果被ping节点响应了，那么将依次ping下一个最久不活跃可疑节点，直到某一个未能响应，或者桶中的所有节点都是好的了。如果桶中的某个节点未能响应ping，建议在丢弃并用新的好节点替换它之前再试一次。这样，路由表中将填满稳定的长期活跃的节点。

每个桶都要维护一个最后变化属性来标志它的新旧程度。当桶中的一个节点被ping而且回复了，或者一个节点加入桶中，或者一个节点被另一个节点替换，桶的最后变化属性将被更新。桶如果15分钟没有变化，就应该刷新——从它覆盖的ID空间中随机选择一个ID，在上面执行一个 find_nodes搜索。可以接收其他节点请求的节点通常不需要经常刷新桶。不能接收其他节点请求的节点则需要定期刷新所有桶，保证在DHT需要的时候路由表中的都是好节点。
启动时，节点在它的路由表中插入第一个节点，然后应该尝试查找DHT中最近邻的其他节点——向邻近节点发送find_node命令，再向更近的节点发送该命令，直到不能找到更近邻的节点。在客户端软件每次调用路由表时，应该保存路由表。

BitTorrent协议扩展

BitTorrent协议被扩展了，以便让tracker所告知的peer相互之间可以交换UDP端口号。这样，客户端就可以获得常规torrent下载时自动生成的路由表。新安装的客户端第一次试图下载一个无法track的torrent时，路由表中没有任何节点，需要torrent中的联系信息。

支持DHT的peer设置在BitTorrent协议握手交换的保留标志位8字节的最后一位。peer接收到远程节点的握手消息，如果标志支持DHT，那么应该回复一个PORT消息。它以0x09开始，然后是两字节的UDP端口，采用网络字节顺序。peer接收到这个消息应该试图ping远程peer上对应IP和端口的那个节点。如果收到ping的响应，这个节点应该尝试按照通常规则，把这个新的联系信息插入路由表中。

Torrent文件扩展

一个无法track的torrent字典中不包括"announce"这个键，而是有一个"nodes"键。这个键应该设置成离生成torrent的节点路由表中最近的K个节点。或者，由生成torrent的人把这个键设置成已知的好节点。请不要把"router.bittorrent.com"自动加入 torrent文件中，也不要把它加入到客户端的路由表中。

DE<nodes = [["<host>", <port>], ["<host>", <port>], ...] nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]]DE<

KRPC协议

KRPC协议是一个简单的RPC机制，由在UDP上发送的bencode字典组成。发送一个请求包，回复一个响应包，没有重试。有三种消息类型： query, response, error。对于DHT协议，有四种query ：ping, find_node, get_peers, announce_peer。

一个KRPC消息是一个字典，包括两个通用键和多个依消息类型而定的其他键。每个消息都有一个"t"键和一个字符串值，代表transaction ID。这个transaction ID由请求节点生成，在回复的时候回显。这样回复可以关联同一个节点的多个请求。KRPC中的另一个通用键是"y"，也是一个字符串作为值，表示消息的类型。"y"的值有："q"（query，请求），"r"（response，回复，响应），"e"（error，错误）。

联系编码

peer的联系信息编码成一个6字节的串，也叫"紧密的IP地址/端口信息"，4字节的IP地址紧接2字节端口号，都是采用网络字节顺序。

节点的联系信息编码成一个26字节的串，也叫"紧密的节点信息"，20字节的节点ID紧接紧密的IP地址/端口信息，同样采用网络字节顺序。

请求

请求，即"y"的值是"q"的KRPC消息，包括两个附加键"q"和"a"。"q"的值是请求的方法名，"a"的值是请求的参数。

响应

响应，即"y"的值是"r"的KRPC消息，包括一个附加键"r"。"r"的值是请求的返回值。当成功完成一个请求时，发送响应消息。

错误

错误，即"y"的值是"e"的KRPC消息，包括一个附加键"e"。"e"的值是一个列表，其中的第一个元素是一个整数，表示错误代码。第二个元素是一个错误消息的字符串。当请求无法完成时，发送错误。下表是可能出现的错误：

错误包示例

DE<generic error = {'t':0, 'y':'e', 'e':[201, "A Generic Error Ocurred"]} bencoded = d1:eli201e23:A Generic Error Ocurrede1:ti0e1:y1:eeDE<

DHT请求

所有的请求都有一个id的键，值是请求节点的ID。所有的响应都有一个id的键，值是响应节点的ID。

ping

最基本的请求是ping, "q"="ping"。 ping请求只有一个参数"id"，值是发送者的节点ID，20字节的，网络字节顺序。相应的响应也只有一个id键，值是响应结点的ID 。

DE<arguments: {"id" : "<querying nodes id>"} response: {"id" : "<queried nodes id>"}DE<

示例包

DE<ping Query = {"t":"0", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}} bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t1:01:y1:qeDE<

DE<Response = {"t":"0", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}} bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t1:01:y1:reDE<

find_node

find_node用来查找一个给定ID的节点联系信息，"q"=="find_node"。 find_node请求有两个参数，"id"包含请求结点的ID；"target"包含请求节点要查找的目标节点ID。当一个节点接收到一个 find_node请求后，它的响应应该包含一个"node"键，值是这个目标节点，或者它路由表中K(8)个离目标节点最近的好节点的紧密的节点信息。

DE<arguments: {"id" : "<querying nodes id>", "target" : "<id of target node>"} response: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"}DE<

示例包

DE<find_node Query = {'t':0, 'y':'q', 'q':'find_node', 'a': {'id':'abcdefghij0123456789', 'target':'mnopqrstuvwxyz123456'}} bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:ti0e1:y1:qeDE<

DE<Response = {'t':0, 'y':'r', 'r': {'id':'0123456789abcdefghij', 'nodes': 'def456...'}} bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:ti0e1:y1:reDE<

get_peers

get_peers与一个torrent的infohash关联，"q"="get_peers"。get_peers请求有两个参数："id"包含请求结点的ID；"info_hash"包含torrent的infohash。如果接收请求的节点知道infohash的peer，它把这些peer 的紧密的IP地址/端口信息连接成一个串列表，以"value"作为键，回复给请求节点。如果接收请求的节点没有infohash的 peer ，它回复路由表中离infohash最近的K个节点，以"nodes"作为键。任何一种情况，"token"键都包含在返回值中。在将来发送 announce_peer请求的时候，token值也是必须的。

DE<arguments: {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>"} response: {"id" : "<queried nodes id>", "values" : ["<compact peer info string>"]} or: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"}DE<

示例包

DE<get_peers Query = {'t':0, 'y':'q', 'q':'get_peers', 'a': {'id':'abcdefghij0123456789', 'info_hash':'mnopqrstuvwxyz123456'}} bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:ti0e1:y1:qeDE<

DE<Response with peers = {'t':0, 'y':'r', 'r': {'id':'abcdefghij0123456789', 'token':'aoeusnth', 'values': ['axje.uidhtnmbrl']}} bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl15:axje.uidhtnmbrlee1:ti0e1:y1:reDE<

DE<Response with closest nodes = {'t':0, 'y':'r', 'r': {'id':'abcdefghij0123456789', 'token':'aoeusnth', 'nodes': 'def456...'}} bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:ti0e1:y1:reDE<

announce_peer

声明请求节点的peer正在一个端口上下载一个torrent。announce_peer有四个参数："id"是请求节点ID； "info_hash"是torrent的infohash；"port"是正在下载的端口号，整数；"token"是上次接收get_peers请求响应时获得的。接收announce请求的节点必须根据IP地址检查令牌（token），即上次它作为请求节点时发给它的令牌与现在提供的令牌相同。然后接收请求的节点应该存储请求节点的IP地址和提供的与infohash关联的端口到本地peer联系信息存储池中。

DE<arguments: {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>", "port" : <port number>, "token" : "<opaque token>"} response: {"id" : "<queried nodes id>"}DE<

示例包

DE<announce_peers Query = {'t':0, 'y':'q', 'q':'announce_peers', 'a': {'id':'abcdefghij0123456789', 'info_hash':'mnopqrstuvwxyz123456', 'port' : 6881, 'token' : 'aoeusnth'}} bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:
mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q14:announce_peers1:ti0e1:y1:qeDE<

DE<Response = {"t":"0", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}} bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t1:01:y1:reDE<

脚注

原文地址：http://www.bittorrent.org/Draft_DHT_protocol.html