本发明涉及分布式哈希表（ DHT, Distributed Hash Table )技术， 尤其

背景技术

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

在 DHT叠加网中， 各节点以及资源的关键字均具有唯一的标识， 其中 节点标识是对节点地址的映射， 资源关键字标识是对该资源关键字的映射。 当标识长度为 m比特时， 标识的取值范围为 [0, 2 ^Λ ιη-1]。 由这些标识组成 的空间可视为一个首尾相连的 DHT环。常见的 DHT算法有 Chord、 Pastry、 Kademlia等， 这些算法规定了 DHT环中各节点负责区间的划分方法， 以及 Ρ2Ρ消息的路由方法等。 以 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的路由更新请求消息， 其路由表与叠加网实际情况不同 步。

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

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

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

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

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

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

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

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

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

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

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

优选地， 所述触发路由表更新原因信息包括以下信息的 至少一种： 新节点加入所述叠加网、 节点退出所述叠加网、 节点负责区间变化； 所述路由表哈希值为节点中完整的路由表哈希 值或节点中各路由表分 段的哈希值。

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

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

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

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

一种叠加网节点， 包括检测单元、 更新单元和通知单元； 其中： 检测单元， 用于检测所述叠加网是否发生调整， 发生时触发更新单元； 更新单元， 用于进行路由表更新；

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

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

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

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

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

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

新节点加入所述叠加网、 节点退出所述叠加网、 节点负责区间变化； 所述路由表哈希值为节点中完整的路由表哈希 值或节点中各路由表分 段的哈希值。

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

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

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

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

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

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

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

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

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

其中， 所述触发路由表更新原因信息包括以下信息的 至少一种： 新节点加入所述叠加网、 节点退出所述叠加网、 节点负责区间变化； 所述路由表哈希值为节点中完整的路由表哈希 值或节点中各路由表分 段的哈希值。

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

图 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所示的叠加网 节点中各处理单元的功能可通过运行于处理器 上的程序而实现， 也可通过 具体的逻辑电路而实现。

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

工业实用性

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