通信工程师互联网技术Chord协议

　　　在线辅导　面授招生　考试大纲　指定教材　试题汇总

1.Chord协议
Chord在2001年由麻省理工学院提出，其核心思想就是要解决在P2P应用中遇到的基本问题：如何在P2P网络中找到存有特定数据的节点。与前两种协议不同，Chord专门为P2P应用设计，因此考虑了在P2P应用中可能遇到的特殊问题。
　　①哈希算法
Chord使用相容哈希作为哈希算法。在相容哈希协议中并没有定义具体的箅法，在Chord协议中将其规定为SHA-1。
　　②路由算法
Chord在相容哈希的基础上提供了优化的路由算法，每个节点维护少量的路由信息，通过这些路由信息，可以提高査询的效率。

这一方案有两个重要的特征：首先,每个节点都需要知道一部分节点的信息，而且离它最近的节点，它就知道越多的信息。其次，每个节点的指针表通常并不包括足够多的信息可以确定任意一个关键字的位置。当节点n不知道关键字1的后继节点时，如果n能够找到一个节点，这个节点的标识符更接近，那么这个节点就知道该关键字的更多信息。根据这一特征，n将查找它的指针表，找到节点标识符大于k的第一个节点，并询问节点,看是否知道哪个节点更接近匕通过重复这个过程,最终将会知道A的后继节点。
在查询的过程中查询节点将请求发送到与键值最接近的节点上。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点(这与相容哈希完全相同）；如果被查询的信息不在本地就根据查询表将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。不难看出，查询过程实际上就是折半査找的过程。经过Chord的优化后，查询需要的跳数由O(N)减少到OdogCN))这样即使在大规模的P2P网络中（例如N=100000000),查询的跳数也仅为0(8)，每个节点仅需存储27个（log2100000000)其他节点的信息。
Chord还考虑到多个节点同时加人系统的情况并对节点加人/退出算法作了优化。
新节点n的加人分为3个阶段：
a.初始化新节点的指针表。假设节点《在加人网络之前通过某种机制知道网络中的某个节点n。这时，为了初始化n的指针表，n将要求节点：为它查找指针表中的其他表项。
b.更新现有其他节点的指针表。节点加人网络后将调用其他节点的更新函数，让其他节点更新其指针表。
c.从后继节点把关键字传递到节点这一步是把所有后继节点是的关键字转移到上。整个加人操作的时间复杂度是0(log2JV),如果采用更复杂的算法，可以把复杂度降低到CKlogN。
在对等网络中，某个对等节点随时可能退出系统或者发生失效，因此，处理节点失效是一个重要的问题。在Chord中，当节点n失效时,所有在指针表中包括n的节点都必须把n替换成的后继节点。另外，节点n的失效不能影响系统中正在进行的査询过程。
在失效处理中最关键的步骤是维护正确的后继指针。为丁保证这一点，每个Chord节点都维护一张包括一个最近后继的后继列表。如果节点注意到它的后继节点失效了，它就用后继列表中第一个正常节点替换失效节点。
③优缺点分析
Chord算法本身具有如下优点：
负载平衡。这一优点来自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的节点以同等的概率分担系统负荷，从而可以避免某些节点负载过大的情况。
分布性。Chord是纯分布式系统，节点之间完全平等并完成同样的工作。这使得Chord具有很高的鲁棒性,可以抵御DOS攻击。
可扩展性。Chord协议的开销随着系统规模（结点总数/V)的增加而按照O(logN)的比例增加。因此Chord可以用于大规模的系统。
可用性。Chord协议要求节点根据网络的变化动态的更新查询表，因此，能够及时恢复路由关系，使得查询可以可靠地进行。
命名的灵活性。Chord并未限制查询内容的结构，因此应用层可以灵活的将内容映射到键值空间而不受协议的限制。

返回目录： 通信工程师互联网技术新型网络体系结构汇总

编辑推荐：

中级通信专业实务 互联网技术教程汇总

中级通信专业实务传输与接入教程汇总

通信专业实务考试设备与环境教程汇总

通信专业实务考试交换技术教程汇总