Kademlia网络调研心得

《Kademlia网络调研心得》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、KAD网络调研心得Kademlia网络模拟·课堂报告ShanZifei,PKU大纲调研结果系统功能项目分工代码规范1.调研结果调研目标调研方法主要调研结果研究问题锻炼能力相互了解1.1.调研目标分别阅读·发现问题组长要有清晰了解搜寻并分享资料资料有针对性，避免让组员做无用功集体讨论·统一认识形成思路解决疑问1.2.调研方法Kademlia：分布式哈希表（DHT）技术以异或（XOR）算法为距离度量基础下面从Kad的几个方面谈。1.3.调研结果Kad是P2P的网络，没有服务器(Server)。节点即为Peer/Client。节点信息：IP地址UDP端口节点ID1.3.1节点每一个加入KAD网络的计

2、算机都会被分配一个32位二进制数作为节点ID值。判断两个节点的距离远近是基于数学上的异或的二进制运算，即两个节点距离为其节点ID异或得到的二进制数。异或又称为环和，具有循环特性。采用异或操作作为距离的度量方法，可以将全部ID映射到一个环上（比如，采用格雷码作为映射方法）。1.3.1节点KAD中每个节点维护一个路由表，用以保存如何连接到其他节点的信息。路由表是通过一些称之为K桶的表格构造起来的。对每一个0≦i<32，对应一个K桶，保存着与本节点已知距离介于区间[2^i,2^(i+1)]的若干个节点的信息。K桶中存储的信息有：节点ID、节点IP地址和UDP端口信息（题目的基本要求只保存节点ID）。

3、本题目中要求每个K桶中保存最多10个节点信息，其中信息更新依据Least-recentlySeenEviction原则。1.3.2节点路由表K桶结构示意图进一步分析，每一个K桶实际上都对定位了ID的一个二进制位。根据异或的运算性质分析，可以得到K桶中ID的储存规律。设节点的ID为id，对于该节点第i位的K桶，满足：K桶中的节点ID的第i位与id的第i位不同，第i+1—31位与id的第i+1—31位相同。如下表：（设ID简化为5位，K桶容量简化为5个节点）K桶内节点ID规律示意图由此我们可以看到，低位的K桶定位更加精准，且难以达到桶满状态；高位的K桶低位都是随意的，定位不够精准，且容易达到桶满状

4、态。K桶的信息更新机制如下：每当节点x收到一个远程操作消息（包括下面要提到的四种消息）时，都要用发送者y的节点信息更新自己的K桶。具体步骤为：1．计算自己和发送者的距离：d(x,y)=ID(x)xorID(y)。2．通过距离d选择对应的K桶进行更新操作：3．如果y的IP地址已经存在于这个K桶中，则把对应项移到该K桶的尾部。K桶的更新4．如果y的IP地址没有记录在该K桶中：⑴如果该K桶的记录项小于k个，则直接把y的(IPaddress,UDPport,NodeID)信息插入队列尾部。⑵如果该K桶的记录项大于k个，则选择k桶头部的节点z进行PING操作：如果z没有响应，则从K桶中移除z的信息，并把

5、y的信息插入队列尾部如果z有响应，则把z的信息移到队列尾部，同时忽略y的信息。（这种操作基于“长时间在线的节点，未来长时间在线的可能性更大”的统计规律）K桶的更新KAD协议包括四种远程操作：PING、STORE、FIND_NODE、FIND_VALUE。注意这四种消息都是要即时更新接受者的K桶的。1.3.3.远程操作（分布式版本）PING：探测一个节点是否在线。向这个节点发送一个PING信息，并等待一个回复。如果超时则判断这个节点不在线。STORE：通知一个节点储存一个对。Key值为资源ID，也是32位二进制数，用散列算法得到；value是资源信息（资源被存放在哪个节点）

6、，由这个信息可以获得特定资源的位置。1.3.3.远程操作FIND_NODE(ID,k)：返回节点所知道的更接近目标ID的k个节点的信息。这些节点的信息可以从一个单独的K桶获得，也可以从多个K桶获得（如果最接近目标ID的K桶未满）。FIND_VALUE(key)：返回节点内储存的资源地址或资源值。如果节点内存放了资源地址，则返回资源地址（资源所在节点信息）。如果节点内没有存放ID为key的资源，返回空串。1.3.3.远程操作通过K桶实现路由（查找）操作时，将由远及近，依次定位节点ID，在O(logN)（N为ID空间，此处为232）的时间内完成查询操作。具体步骤如下：（注意使用迭代而不是递归）1.

7、3.4.路由查询（lookup）在节点查询的时候，它先得到它K桶中离所查询的键值最近的K（题目要求为5）个节点，然后向这K个节点发起FIND_NODE消息请求，消息接收者收到这些请求消息后将在他们的K桶中进行查询，如果他们知道离被查键更近的节点，他们就返回这些节点（最多K个）。消息的请求者在收到响应后将使用它所收到的响应结果来更新它的结果列表，这个结果列表总是保持K个最优节点（即离被搜索键更近的K