Chord协议

Chord在2001年由麻省理工学院提出(参见0)，其核心思想就是要解决在P2P应用中遇到的基本问题：如何在P2P网络中找到存有特定数据的节点。与前两种协议不同，Chord专门为P2P应用设计，因此考虑了在P2P应用中可能遇到的特殊问题，这些内容将在路由的部分进行讨论。

哈希算法

Chord使用一致性哈希作为哈希算法。在一致性哈希协议中并没有定义具体的算法，在Chord协议中将其规定为SHA-1。

路由算法

Chord在一致性哈希的基础上提供了优化的路由算法：

在Chord中，每个节点同样需要存储m个其他节点的信息，这些信息的集合被称为查询表(Finger Table)。一致性哈希中的节点同样具有这样的表格，但在Chord中，表格中的节点不再是直接相邻的节点，它们的间距(ID间隔)将成2i 的关系排列(i 表示表中的数组下标)。这样形成的节点之间路由关系实际上就是折半查找算法需要的排列关系。

在查询的过程中，查询节点将请求发送到与键值最接近的节点上。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点(这与一致性哈希完全相同)；如果被查询的信息不在本地，就根据查询表将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。不难看出，查询过程实际上就是折半查找的过程。

经过Chord的优化后，查询需要的跳数由O ( N)减少到O(log(N))。这样即使在大规模的P2P网络中(例如N＝100,000,000)，查询的跳数也仅为O(8)，每个节点仅需存储27个(log2100000000)其他节点的信息。

Chord还考虑到多个节点同时加入系统的情况并对节点加入/退出算法作了优化。

讨论

Chord算法本身具有如下优点：

负载平衡

这一优点来自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的节点以同等的概率分担系统负荷，从而可以避免某些节点负载过大的情况。

分布性

Chord是纯分布式系统，节点之间完全平等并完成同样的工作。这使得Chord具有很高的鲁棒性，可以抵御DoS攻击。

可扩展性

Chord协议的开销随着系统规模(结点总数N)的增加而按照O(logN)的比例增加。因此Chord可以用于大规模的系统。

可用性

Chord协议要求节点根据网络的变化动态的更新查询表，因此能够及时恢复路由关系，使得查询可以可靠地进行。

命名的灵活性

Chord并未限制查询内容的结构，因此应用层可以灵活的将内容映射到键值空间而不受协议的限制。

Chord在CFS系统中得到了应用，具体的介绍可参见[8]

内容寻址网络(Content-Addressable Network，CAN)

CAN在2001年由加州大学伯克利分校提出(参见[3])。与Chord一样，CAN也是DHT的一个变种。

哈希算法

CAN的哈希算法与一致性哈希有所不同。Chord中，哈希得到的键值总是一维的，而在CAN中，哈希的结果由d维的笛卡尔空间来表示。d是一个由系统规模决定的常量。

路由算法

CAN的路由查询将在d维笛卡尔空间中进行。

在CAN中，每个节点自身的ID经由哈希后得到的d维向量。经过这样的映射后，整个P2P系统将被映射到一个d维笛卡尔空间中，每个节点的位置由其自身ID决定。CAN对邻居节点的定义并不要求成2i的关系排列，而是改为用在笛卡尔空间上相邻来表示：在d维笛卡尔空间中，2个节点的d维坐标中有d-1维是相等的，剩余的一维是相邻的节点称之为相邻节点。

CAN中的节点仅存储相邻节点表。由于在d维的空间中最多有2d个相邻的节点，因此节点的相邻节点表最多有2d个表项。

在查询的过程中，查询节点首先计算被查询内容的键值(d维向量)，然后在节点列表中查找在笛卡尔空间中与该键值最为接近的相邻节点，找到后向该节点发送查询请求(这一策略被称为贪婪策略)。查询请求中将携带被查询内容的键值。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点(这与一致性哈希完全相同)；如果被查询的信息不在本地，就根据相邻节点表将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。在查询过程中，被查询节点到目标节点的笛卡尔空间距离单调地减少。

如果查询节点或转发节点发现邻居节点表中无法找到可用的下一跳节点，则采用非结构化P2P常用的扩展环搜索(Expanding Ring Search，使用无状态，受控的泛洪算法在重叠网中搜索)以找到合适的(符合贪婪策略)下一节点。

经过CAN的优化后，查询需要的跳数由O ( N)减少到均值为(d/4)(n1/d)的随机制，考虑到d为常数，这一值可以表示为O(n1/d)或O(dn1/d)。

讨论

CAN和Chord的主要区别在于路由算法不同。相比之下，在节点数量非常大时，CAN的平均查询跳数要比Chord增加得更快。而且 CAN查询过程中需要的运算量也要高于Chord。但CAN使用的d为预先设置的常量，因此并不假设系统节点数量。在节点总数动态变化范围很大的系统中， CAN的相邻节点表结构保持稳定，这在P2P的应用中也是很重要的优点。