分布式哈希表路由表更新方法及节点

摘要

本发明公开了一种分布式哈希表路由表更新方法及节点，其中，所述方法包括：叠加网中节点检测到叠加网发生调整时，进行路由表更新，并将触发路由表更新原因信息及更新后路由表哈希值通知叠加网的其他节点；其他节点根据触发路由表更新原因信息进行本地路由表更新，并计算本地更新后路由表的哈希值，确定所计算哈希值与所接收到的路由表哈希值不一致时，与发送触发路由表更新原因信息的节点之间进行路由表交换；其他节点以及发送触发路由表更新原因信息的节点对比所交换的路由表间的差异，对叠加网差异处进行探测，在确定需要修正本地路由表时，进行路由表修正。本发明能自动消除节点间路由表不同步的现象，从而避免了错误的路由表扩散，不会导致叠加网路由性能下降。

说明书

技术领域

本发明涉及分布式哈希表(DHT，Distributed Hash Table)技术，尤其涉及 一种基于DHT技术的分布式哈希表路由表更新方法及节点。

背景技术

分布式哈希表(DHT，Distributed Hash Table)技术是一种广泛应用于对等 (P2P，Peer to Peer)网络中的分布式资源查找技术。DHT叠加网是各节点按 照一定的拓扑结构组成的位于IP网络之上的叠加网，其负责一部分资源的存储 和消息的路由等。DHT在文件交换、分布式计算、服务共享等方面已经充分显 示出了其强大的技术优势。

在DHT叠加网中，各节点以及资源的关键字均具有唯一的标识，其中节点 标识是对节点地址的映射，资源关键字标识是对该资源关键字的映射。当标识 长度为m比特时，标识的取值范围为[0，2^m-1]。由这些标识组成的空间可视 为一个首尾相连的DHT环。常见的DHT算法有Chord、Pastry、Kademlia等， 这些算法规定了DHT环中各节点负责区间的划分方法，以及P2P消息的路由 方法等。以Chord算法为例，各叠加网节点负责存储关键字标识位于本节点标 识与前趋节点标识之间的资源，发送P2P消息的路由跳数一般为O(log N)， 其中N为叠加网中节点的数目。

随着P2P技术的示范效应，DHT技术也被引入到其它技术体制中，以用于 构建高性能、可扩展的分布式数据库系统等，如亚马逊的Dynamo系统等。

在这些分布式数据库系统中，节点(对等体)在计算、存储等方面的性能 均较好，且各节点的加入和退出严格受控，叠加网调整不频繁。但这些系统对 发送P2P消息的路由效率要求较高，要求P2P消息在固定的跳数到达目的节点。 故该类系统适宜采用单跳DHT算法，即各节点均保存完整路由表，掌握叠加网 所有节点负责区间的情况，发送的P2P消息只需一跳即可到达目的节点。然而， 若采用单跳DHT，在叠加网节点多时，则路由表较大。

在异构网络环境下，单跳DHT还可以进一步结合分割标识、虚拟节点等负 载均衡方法，即各节点负责与自身能力相符的分割或虚拟节点数目，以承担合 适的负载。这样，各节点路由表中除存储物理节点信息外，还需存储分割标识 或虚拟节点与物理节点间的映射关系，路由表更为庞大。

采用单跳DHT，要求叠加网中各节点存储的路由表与叠加网实际情况保持 同步或基本同步。

图1为DHT环的示意图，如图1所示，叠加网101是由各类担负不同角色 的对等体(也称为叠加网节点)组成的一张逻辑网络；叠加网中的对等叠加网 节点102为叠加网中的基本组成部分，是能够为同一叠加网中其它叠加网节点 提供存储和传送服务的叠加网节点。对DHT环中的任一叠加网节点，均存在一 个前趋节点和一个后继节点。

图2为节点加入叠加网的流程图，如图2所示，节点加入叠加网具体包括 如下步骤：

步骤201，加入节点获取得到自身节点标识；加入节点可以通过查找自身 配置信息的方式或向服务器请求等方式获取自身节点标识；

步骤202，加入节点向其已知的叠加网任一节点发送附着请求消息；

步骤203，接收到附着请求消息的节点将消息转发给加入节点的负责节点；

步骤204至步骤205，负责节点发送附着响应消息，该附着响应消息被转 发给加入节点；

步骤206，负责节点向加入节点发送路由更新请求消息，该路由更新请求 消息中含有自身存储的当前叠加网完整路由表；

步骤207，加入节点按路由更新请求消息初始化自身路由表，并向负责节 点回复路由更新响应；

步骤208，加入节点向负责节点发送加入叠加网请求消息；

步骤209，负责节点向加入节点回复加入叠加网响应消息，至此，加入节 点和负责节点完成协商，确定负责节点向加入节点迁移数据的区间；

步骤210，负责节点不断向加入节点发送存储数据请求消息，加入节点在 完成数据存储后回复响应消息；该过程持续到数据迁移过程完成；

步骤211，此时加入节点已完成接管迁移区间部分数据的准备，其负责节 点向叠加网所有其它节点发送路由更新请求消息；该路由更新请求消息可采用 广播或分级广播等形式发送；

步骤212，叠加网各节点按路由更新请求消息更新本地存储的路由表，并 向负责节点回复路由更新响应消息。

若采用分割标识或虚拟节点等负载均衡算法，新加入节点可能需要从多个 在网节点接管负责DHT区间，故加入节点需与多个在网节点交互，分别执行上 述步骤208至步骤212。

若两个或多个节点在相近的时刻请求加入叠加网，由于数据迁移时间较长， 加入过程可存在重叠。图3为两个节点在相近时间加入叠加网的流程图，如图 3所示，本示例假设叠加网在网已有节点仅包括节点A和节点B，且分别为新 加入节点C和节点D为负责节点。图3所示流程具体包括以下步骤：

步骤301，加入节点C已完成向负责节点A的附着过程；

步骤302，负责节点A向节点C发送路由更新请求消息，该路由更新请求 消息内包含完整路由表，路由表中包括节点A、B的相关信息；

步骤303，节点C根据请求初始化本地路由表，并向节点A发送路由更新 响应消息；

步骤304，节点C向节点A发送加入叠加网请求消息；

步骤305，节点A向节点C发送加入叠加网响应消息，至此，加入节点和 负责节点完成协商，确定负责节点向加入节点迁移的数据区间；

步骤306，节点A向节点C发送数据，进行数据迁移；

步骤307，此时加入节点C已完成成为叠加网成员的准备，负责节点A向 叠加网其它所有节点(目前仅有节点B)发送路由更新请求消息，以通知节点 C已加入叠加网；

步骤308，节点B更新本地路由表，并向节点A发送路由更新响应消息；

步骤309，稍晚于节点C，在相近的时刻，加入节点D已完成向负责节点 B的附着过程；

步骤310，负责节点B向节点D发送路由更新请求消息，该路由更新请求 消息内包含完整路由表，路由表中包括节点A、B的相关信息；

步骤311，节点D根据路由更新请求消息初始化本地路由表，并向节点B 发送路由更新响应消息；

步骤312，节点D向节点B发送加入叠加网请求消息；

步骤313，节点B向节点D发送加入叠加网响应消息，至此，加入节点和 负责节点完成协商，确定负责节点向加入节点迁移的数据区间；

步骤314，节点B向节点D发送数据，进行数据迁移；

步骤315，此时加入节点D已完成成为叠加网成员的准备，负责节点B向 节点A发送路由更新请求消息，通知节点D已加入叠加网；

步骤316，节点A更新本地路由表，并向节点B发送路由更新响应消息；

步骤317，此前节点B已获知节点C加入叠加网的信息，故负责节点B向 节点C发送路由更新请求消息，通知节点D已加入叠加网；

步骤318，节点C更新本地路由表，并向节点B发送路由更新响应消息。

以上步骤完成后，新加入节点D因为在其未成为叠加网成员时不会收到关 于加入节点C的路由更新请求消息，其路由表与叠加网实际情况不同步。

路由表不同步的节点会将P2P消息发往错误的目的节点，接收到P2P消息 的节点查询本地存储的路由表获取该目的地址的下一跳，并对该P2P消息进行 转发。这样，P2P消息最终仍可到达正确的目的节点，但增加了路由跳数。后 续，若路由表不同步的节点负责新节点的加入，其保存的路由表会被传递给新 加入节点。不正确路由表会因此扩散，导致叠加网性能不断下降。

发明内容

有鉴于此，本发明的主要目的在于提供一种分布式哈希表路由表更新方法 及节点，能消除节点间路由表不同步的现象，从而避免错误的路由表扩散，避 免叠加网路由性能下降。

为达到上述目的，本发明的技术方案是这样实现的：

一种分布式哈希表路由表更新方法，包括：

叠加网中节点检测到所述叠加网发生调整时，进行路由表更新，并将触发 路由表更新原因信息及更新后路由表哈希值通知所述叠加网的其他节点。

优选地，将触发路由表更新原因信息及更新后路由表哈希值通知所述叠加 网的其他节点之后，所述方法还包括：

所述其他节点根据所述触发路由表更新原因信息进行本地路由表更新，并 计算本地更新后路由表的哈希值，确定所计算哈希值与所接收到的路由表哈希 值不一致时，与发送触发路由表更新原因信息的节点之间进行路由表交换；

所述其他节点以及所述发送触发路由表更新原因信息的节点根据所交换的 路由表确定是否需要修正本地路由表，需要时进行路由表修正。

优选地，所述其他节点以及所述发送触发路由表更新原因信息的节点根据 所交换的路由表确定是否需要修正本地路由表，需要时进行路由表修正，为：

所述其他节点以及所述发送触发路由表更新原因信息的节点分别根据从对 方获取的路由表对比出与自身路由表之间的差异，对导致路由表差异的节点进 行探测，根据探测结果在确定需要自身修正路由表时，进行本地路由表修正。

优选地，所述叠加网发生调整，为：新节点加入所述叠加网和/或有节点退 出所述叠加网。

优选地，所述触发路由表更新原因信息包括以下信息的至少一种：

新节点加入所述叠加网、节点退出所述叠加网、节点负责区间变化；

所述路由表哈希值为节点中完整的路由表哈希值或节点中各路由表分段的 哈希值。

优选地，所述方法还包括：

为路由表或路由表分段设置计数器；

所述其他节点确定所计算哈希值与所接收到的路由表或路由表分段哈希值 不一致时，将所述计数器加一；确定所述计数器的计数值达到设定阈值时，与 所述发送触发路由表更新原因信息的节点之间进行路由表交换。

优选地，所述路由表哈希值为节点中各路由表分段的哈希值时，所述方法 还包括：

所述其他节点根据所述触发路由表更新原因信息进行本地路由表更新，确 定更新后某路由表分段的哈希值与所接收的某路由表分段的哈希值不一致时， 与所述发送触发路由表更新原因信息的节点之间仅进行不一致的路由表分段交 换。

一种叠加网节点，包括检测单元、更新单元和通知单元；其中：

检测单元，用于检测所述叠加网是否发生调整，发生时触发更新单元；

更新单元，用于进行路由表更新；

通知单元，用于将触发路由表更新原因信息及更新后路由表哈希值通知所 述叠加网的其他节点。

上述节点还包括交换单元和修正单元，其中：

交换单元，用于与所述其他节点进行路由表交换；

修正单元，用于根据从所述其他节点获取的路由表对比出与所述节点自身 路由表之间的差异，对导致路由表差异的节点进行探测，在确定需要所述节点 自身修正路由表时，进行本地路由表修正。

其中，所述叠加网发生调整，为：新节点加入所述叠加网和/或有节点退出 所述叠加网；

所述触发路由表更新原因信息包括以下信息的至少一种：

新节点加入所述叠加网、节点退出所述叠加网、节点负责区间变化；

所述路由表哈希值为节点中完整的路由表哈希值或节点中各路由表分段的 哈希值。

一种叠加网节点，包括接收单元、更新单元、计算单元和确定单元；其中：

接收单元，用于接收其他节点发送的触发路由表更新原因信息及更新后路 由表哈希值；

更新单元，用于根据所述触发路由表更新原因信息进行本地路由表更新；

计算单元，用于计算所述节点本地更新后路由表的哈希值；

确定单元，用于确定所计算哈希值是否与所接收到的路由表哈希值一致。

上述节点还包括交换单元和修正单元，其中：

所述确定单元确定所计算哈希值与所接收到的路由表哈希值不一致时，触 发交换单元；

交换单元，用于与所述其他节点进行路由表交换；

修正单元，用于根据从所述其他节点获取的路由表对比出与所述节点自身 路由表之间的差异，对导致路由表差异的节点进行探测，在确定需要所述节点 自身修正路由表时，进行本地路由表修正。

其中，所述触发路由表更新原因信息包括以下信息的至少一种：

新节点加入所述叠加网、节点退出所述叠加网、节点负责区间变化；

所述路由表哈希值为节点中完整的路由表哈希值或节点中各路由表分段的 哈希值。

本发明中，当节点确定有新节点加入或有节点退出叠加网时，所述节点进 行本地路由更新后，会将触发路由表更新原因信息及更新后路由表哈希值通知 所述叠加网的其他节点；所述其他节点根据所述触发路由表更新原因信息进行 本地路由表更新，并计算本地更新后路由表的哈希值，确定与自身所接收到的 路由表哈希值不一致时，所述其他节点以及所述发送触发路由表更新原因信息 的节点之间进行路由表交换；所述其他节点以及所述发送触发路由表更新原因 信息的节点分别根据所获取的路由表信息与本地存储路由表间的差异对叠加网 进行探测，确定需要自身修正路由表时，进行本地路由表修正。这样，本发明 的技术方案可以在有节点进行路由表更新时自动消除节点间路由表不同步的现 象，从而避免了错误的路由表扩散，不会导致叠加网路由性能下降；本发明中 仅采用哈希值进行路由表的校验，当发现校验值不一致时节点之间才进行路由 表交换，消除路由表不同步现象的开销较小。

附图说明

图1为DHT环的示意图；

图2为节点加入叠加网的流程图；

图3为两个节点在相近时间加入叠加网的流程图；

图4为本发明实施例中节点进行路由更新并进行路由表校验及修正的第一 流程图；

图5为本发明实施例中节点进行路由更新并进行路由表校验及修正的第二 流程图；

图6为本发明实施例中节点进行路由更新并进行路由表校验及修正的第三 流程图；

图7为本发明实施例中节点进行路由更新并进行路由表校验及修正的第四 流程图；

图8为本发明实施例叠加网节点的一种组成结构示意图；

图9为本发明实施例叠加网节点的另一种组成结构示意图。

具体实施方式

本发明的基本思想为：当节点确定有新节点加入或有节点退出叠加网时， 所述节点进行本地路由更新后，会将触发路由表更新原因信息及更新后路由表 哈希值通知所述叠加网的其他节点；所述其他节点根据所述触发路由表更新原 因信息进行本地路由表更新，并计算本地更新后路由表的哈希值，确定与自身 所接收到的路由表哈希值不一致时，所述其他节点以及所述发送触发路由表更 新原因信息的节点之间进行路由表交换；所述其他节点以及所述发送触发路由 表更新原因信息的节点分别根据所获取的路由表信息与本地存储路由表间的差 异对叠加网进行探测，确定需要自身修正路由表时，进行本地路由表修正。

为使本发明的目的，技术方案和优点更加清楚明白，以下举实施例并参照 附图，对本发明进一步详细说明。

图4为本发明实施例中节点进行路由更新并进行路由表校验及修正的第一 流程图。叠加网采用类似Chord算法的资源负责分布形式，即各节点负责本节 点标识与前趋节点标识之间的哈希空间。本示例中，假设节点D保存的路由表 信息不完整，其不知晓节点C的存在；节点D的负责节点为节点B。如图4所 示，本示例的节点进行路由更新并进行路由表校验及修正的流程具体包括以下 步骤：

步骤401，节点B收到节点X退出叠加网请求消息，或通过连通性检测发 现节点X已失效，其需要将节点X已失效的信息广播到整个叠加网；

步骤402，节点B向节点D发送路由更新请求消息，其中含有节点X离开 的信息及更新后完整路由表的哈希值；

步骤403，节点D根据请求更新路由表，计算更新后完整路由表的哈希值， 向节点B发送路由表更新响应消息，并包含上述计算所得哈希值；

步骤404，节点B比较接收到的响应消息中的哈希值与本地存储计算值， 发现二者不符；

步骤405，节点B向节点D发送完整路由表，并请求节点D返回完整路由 表；

步骤406，节点D向节点B发送完整路由表；

步骤407，节点B对比接收到的和本地存储的路由表，发现接收到的路由 表中缺少节点C；

步骤408，节点B向节点C发送连通性探测请求；

步骤409，节点C向节点B发送连通性探测响应消息，节点B确认节点C 在网，无需修正本地路由表；

步骤410，节点D对比接收到的路由表和本地存储的路由表，发现接收到 的路由表中多出节点C；

步骤411，节点D向节点C发送连通性探测请求消息；

步骤412，节点C向节点D发送连通性探测响应消息；

步骤413，节点D确认节点C在网，对本地路由表进行修正。

图5为本发明实施例中节点进行路由更新并进行路由表校验及修正的第二 流程图。本示例中，叠加网采用基于分割的负载均衡算法、哈希空间等分为若 干分割，各节点负责与自身能力相符的分割数目。本示例中，假设节点D保存 关于节点C的负责区间情况与当前网络情况不同步。节点D为节点Y的负责 节点，叠加网中还包括节点B。如图5所示，本示例的节点进行路由更新并进 行路由表校验及修正的流程具体包括以下步骤：

步骤501，节点D为节点Y加入叠加网的负责节点，且向节点Y的数据 迁移过程已完成，其需要将该负责区间变化消息广播到整个叠加网；

步骤502，节点D向节点B发送路由更新请求消息，该路由更新请求消息 中包含有节点Y负责区间变化的信息及更新后完整路由表的哈希值；

步骤503，节点B根据路由更新请求消息更新路由表，计算更新后完整路 由表的哈希值，向节点D发送路由表更新响应消息，并包含上述计算所得哈希 值；

步骤504，节点D比较接收到响应中的哈希值与本地存储计算值，发现二 者不符；

步骤505，节点D向节点B发送完整路由表，并请求节点B返回完整路由 表；

步骤506，节点B向节点D发送完整路由表；

步骤507，节点B对比接收到的和本地存储的路由表，发现接收到的路由 表中C负责区间与本地记录不符；

步骤508，节点B向节点C发送负责区间探测请求消息；

步骤509，节点C向节点B发送负责区间探测响应消息，该负责区间探测 响应消息中包含本节点负责区间的情况，节点B确认本地存储路由表关于节点 C负责区间的记录正确，无需修正路由表；

步骤510，节点D对比接收到的和本地存储的路由表，发现收到的路由表 中C负责区间与本地记录不符；

步骤511，节点D向节点C发送负责区间探测请求消息；

步骤512，节点C向节点D发送负责区间探测响应消息，该负责区间探测 响应消息中包含本节点负责区间情况；

步骤513，节点D确认本地关于节点C负责区间记录有误，对路由表进行 修正。

为加快路由表差异的发现，减小节点间交换路由表的开销，可对路由表进 行分段，在路由更新请求及响应消息中附带各分段的哈希值。路由表的分段应 按约定进行，以保证对相同的路由表计算将得到相同的分段哈希值用于校验。 图6为本发明实施例中节点进行路由更新并进行路由表校验及修正的第三流程 图。叠加网采用类似Chord算法的资源负责区间分布形式，即各节点负责本节 点标识与前趋节点标识之间的哈希空间。本示例中，节点M所保存的路由表信 息不完整，其不知晓节点P已离开叠加网，叠加网中还包括节点N。如图6所 示，本示例的节点进行路由更新并进行路由表校验及修正的流程具体包括以下 步骤：

步骤601，节点M遇有需广播路由表更新的情形；

步骤602，节点M向节点N发送路由表更新请求消息，该路由表更新请求 消息中含有关于叠加网调整情况的信息及各路由表分段的哈希值；

步骤603，节点N根据以上请求更新路由表，并计算更新后各路由表分段 的哈希值，向节点M发送路由表更新响应消息，该路由表更新响应消息中包含 上述所计算的哈希值；

步骤604，节点M比较接收到响应消息中的哈希值与本地存储计算值，发 现某段哈希值不符；

步骤605，节点M向节点N发送哈希值不符部分的路由表，并请求节点N 返回该段路由表；

步骤606，节点N向节点M发送哈希值不符部分的路由表；

步骤607，节点N对比接收到的和本地存储的路由表，发现接收到的路由 表中缺少节点P；

步骤608，节点N向节点P发送连通性探测请求消息；

步骤609，节点M对比接收到的路由表和本地存储的路由表，发现接收到 的路由表中多出节点P；

步骤610，节点M向节点P发送连通性探测请求消息；

步骤611，节点N请求定时器到时未接收到节点P的探测响应消息，探测 请求超时，确认节点P已失效，无需修正路由表；

步骤612，节点M请求定时器到时未接收到节点P的探测响应消息，探测 请求超时，确认节点P已失效，对路由表进行修正。

为避免单点过载等情况，节点发现路由更新请求及响应消息中所含哈希值 不符后，可并不立即交换路由表，而是将相应的计数器加1，待计数器达到设 定阈值后，再与其它节点进行路由表交换并进一步处理。本示例中，叠加网中 包括节点Q、节点M和节点N。图7为本发明实施例中节点进行路由更新并进 行路由表校验及修正的第四流程图，如图7所示，本示例的节点进行路由更新 并进行路由表校验及修正的流程具体包括以下步骤：

步骤701，节点Q遇有需更新路由表的情形；

步骤702，节点Q向节点M发送路由更新请求消息，并附带路由表分段哈 希值；

步骤703，节点M按路由更新请求消息对路由表进行更新，计算更新后路 由表的哈希值，向节点Q发送路由更新响应消息，并附带上述计算所得哈希值；

步骤704，节点M发现路由表某段哈希值与本地记录不符，将该段计数器 值加1，并将计数器结果与设定阈值比较，未达到设定阈值；

叠加网继续运行一段时间；

步骤705，节点M遇有需要更新路由表的情形；

步骤706，节点M向节点N发送路由更新请求消息，并附带路由表分段哈 希值；

步骤707，节点N按路由更新请求消息对路由表进行更新，计算更新后路 由表的哈希值，向节点M发送路由更新响应消息，并附带上述哈希值；

步骤708，节点M发现路由表某段哈希值与本地记录不符，将该段计数器 值加1，并将计数器结果与设定阈值比较，未达到设定阈值；

步骤709，节点M向节点P发送路由更新请求消息，并附带路由表分段哈 希值；

步骤710，节点P按路由更新请求消息对路由表进行更新，计算更新后路 由表的哈希值，向节点M发送路由更新响应消息，并附带上述哈希值；

步骤711，节点M发现路由表某段哈希值与本地记录不符，将该段计数器 值加1，并将计数器结果与设定阈值比较，未达到设定阈值；

叠加网继续运行一段时间；

步骤712，节点M在与某节点进行路由更新请求/响应消息交互后，某段计 数器值加1后达到设定阈值。节点M与该节点交换该段路由表，对差异所在进 行探测，并进行相应处理，重置该段计数器为0。

图8为本发明实施例叠加网节点的一种组成结构示意图，如图8所示，本 示例的叠加网节点包括检测单元80、更新单元81和通知单元82；其中：

检测单元80，用于检测所述叠加网是否发生调整，发生时触发更新单元81；

更新单元81，用于进行路由表更新；

通知单元82，用于将触发路由表更新原因信息及更新后路由表哈希值通知 所述叠加网的其他节点。

在图8所示叠加网节点的基础上，本示例的叠加网节点还包括交换单元(图 8中未图示)和修正单元(图8中未图示)，其中：

交换单元，用于与所述其他节点进行路由表交换；

修正单元，用于根据从所述其他节点获取的路由表对比出与所述节点自身 路由表之间的差异，对导致路由表差异的节点进行探测，在确定需要所述节点 自身修正路由表时，进行本地路由表修正。

所述叠加网发生调整，为：新节点加入所述叠加网和/或有节点退出所述叠 加网；

上述触发路由表更新原因信息包括以下信息的至少一种：

新节点加入所述叠加网、节点退出所述叠加网、节点负责区间变化。

上述路由表哈希值为节点中完整的路由表哈希值或节点中各路由表分段的 哈希值。

图9为本发明实施例叠加网节点的另一种组成结构示意图，如图9所示， 本示例的叠加网节点包括接收单元90、更新单元91、计算单元92和确定单元 93；其中：

接收单元90，用于接收其他节点发送的触发路由表更新原因信息及更新后 路由表哈希值；

更新单元91，用于根据所述触发路由表更新原因信息进行本地路由表更 新；

计算单元92，用于计算所述节点本地更新后路由表的哈希值；

确定单元93，用于确定所计算哈希值是否与所接收到的路由表哈希值一 致。

在图9所示叠加网节点的基础上，本示例的叠加网节点还包括交换单元(图 9中未图示)和修正单元(图9中未图示)，其中：

交换单元，用于与所述其他节点进行路由表交换；

修正单元，用于根据从所述其他节点获取的路由表对比出与所述节点自身 路由表之间的差异，对导致路由表差异的节点进行探测，在确定需要所述节点 自身修正路由表时，进行本地路由表修正。

所述叠加网发生调整，为：新节点加入所述叠加网和/或有节点退出所述叠 加网。

上述触发路由表更新原因信息包括以下信息的至少一种：

新节点加入所述叠加网、节点退出所述叠加网、节点负责区间变化。

上述路由表哈希值为节点中完整的路由表哈希值或节点中各路由表分段的 哈希值。

本领域技术人员应当理解，图8及图9中所示的叠加网节点中的各处理单 元的实现功能可参照前述图4至图7的分布式哈希表路由表更新方法的相关描 述而理解。本领域技术人员应当理解，图8及图9所示的叠加网节点中各处理 单元的功能可通过运行于处理器上的程序而实现，也可通过具体的逻辑电路而 实现。

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范 围。