本发明公开了一种多域域间路由维护方法和系统，此方法包括：节点加入时，在该新加入节点所在域外的其它域中查找到其对应的域外路由节点，建立所述节点到所述域外路由节点的域间路由路径，所述域外路由节点是指该域外路由节点所在域中节点标识与所述新加入节点的节点标识之间满足预设的域间路由建立原则的节点；所述其它域中的相关节点根据域间路由建立原则，建立或调整到该新加入节点所在域的域间路由路径。本发明所述多域域间路由维护方法，可以减少域间路由维护开销。
节点加入时，在该新加入节点所在域外的其它域中查找到其对应的域外路由节点，建立所述节点到所述域外路由节点的域间路由路径，所述域外路由节点是指该域外路由节点所在域中节点标识与所述新加入节点的节点标识之间满足预设的域间路由建立原则的节点；所述其它域中的相关节点根据域间路由建立原则，建立或调整到该新加入节点所在域的域间路由路径。
2.如权利要求1所述的方法，其特征在于，节点加入时，该节点称为第一节点，该节点的加入的域称为第一域，与其它域中的一个域，该域称为第二域，建立域间路由路径具体包括：第一节点加入第一域，向第二域的第二节点发送请求消息；
第二节点根据域间路由建立原则在第二域查找到域外路由节点，域外路由节点返回响应消息给所述第一节点；
所述第一节点建立到所述域外路由节点的域间路由路径。
3.如权利要求2所述的方法，其特征在于，第一节点为加入所述第一域的第一个节点时，还包括：所述第一节点收到所述响应消息后，发送更新通知消息给所述域外路由节点，所述域外路由节点转发所述更新通知消息至其所在域中的所有其他节点，其他节点建立到所述第一节点的域间路由路径。
4.如权利要求2所述的方法，其特征在于，第一节点为加入所述第一域的非第一个节点时，还包括：所述第一节点发送更新请求至所述域外路由节点，所述域外路由节点收到所述请求后，根据域间路由建立原则进行逆向查找，在第二域中查找到更新节点，所述更新节点建立与所述第一节点的域间路由路径，其中，所述第一节点是第一域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点。
5.如权利要求1所述的方法，所述节点对应一负责节点，所述负责节点与所述节点在同一个域中，其特征在于，负责节点检测到节点离开时，该节点称为离开节点，负责节点向负责节点所在域外的其它域的节点发送更新通知消息；
其它域的节点收到该更新通知消息后，根据域间路由建立原则进行逆向查找，在其它域中查找到更新节点；其中，所述离开节点是离开节点所在域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点；
所述更新节点建立与离开节点所在域的新域外路由节点之间的域间路由路径，其中，所述新域外路由节点是离开节点所在域中节点标识与所述更新节点的节点标识之间满足所述域间路由建立原则的节点。
6.如权利要求5所述的方法，其特征在于，所述更新通知消息中携带所述新域外路由节点的信息，所述更新节点从所述更新通知消息中获取新域外路由节点的信息。
7.如权利要求4或5或6所述的方法，其特征在于，域间路由路径的两个节点分别称为首节点和尾节点，路径方向是从首节点到尾节点，所述域间路由建立原则是指，尾节点与尾节点所在域中的所有节点相比，其节点标识大于且最接近首节点的节点标识，或者其节点标识小于且最接近首节点的节点标识，或者其节点标识与首节点的节点标识之差的绝对值最小。
8.如权利要求7所述的方法，其特征在于，所述根据域间路由建立原则进行逆向查找，查找到更新节点具体是指：路由建立原则为尾节点节点标识大于且最接近首节点的节点标识时，查找节点标识小于且最接近所述新加入节点或离开节点的节点作为更新节点；
路由建立原则为尾节点节点标识小于且最接近首节点的节点标识时，查找节点标识大于且最接近所述加入节点或离开节点的节点作为更新节点；
路由建立原则为尾节点节点标识与首节点的节点标识之差的绝对值最小时，查找节点标识与所述新加入节点或离开节点的节点标识之差的绝对值最小的节点作为更新节点。
9.一种多域域间路由维护系统，其特征在于，包括若干个域，域中包括若干个节点，其中：所述节点，用于加入时，在该节点所在域外的其它域中查找到域外路由节点，建立所述节点到所述域外路由节点的域间路由路径，所述域外路由节点是指该域外路由节点所在域中节点标识与所述节点的节点标识之间满足预设的域间路由建立原则的节点；还用于在其它域中的相关节点加入时，调整到其它域的域间路由路径。
10.如权利要求9所述的系统，其特征在于，所述系统至少包括第一域和第二域，第一节点加入所述第一域，所述第二域至少包括第二节点，其中：所述第一节点，用于加入第一域时，向第二域的第二节点发送请求消息；还用于收到域外路由节点返回的响应消息时，建立到所述域外路由节点的域间路由路径；
所述第二节点，用于收到该请求消息后，根据域间路由建立原则在第二域查找到域外路由节点；
所述域外路由节点，用于返回响应消息给所述第一节点。
所述第一节点，还用于在第一个加入所述第一域时，在收到所述域外路由节点返回的响应消息后，发送更新通知消息给所述域外路由节点；
所述域外路由节点，用于转发所述更新通知消息至其所在域中的所有其他节点；其他节点建立到所述第一节点的域间路由路径。
第一节点，还用于非第一个加入所述第一域时，发送更新请求至所述域外路由节点；
所述域外路由节点，用于收到所述更新请求后，根据域间路由建立原则进行逆向查找，在第二域中查找到更新节点；其中，所述第一节点是第一域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点；
所述更新节点，用于建立与所述第一节点的域间路由路径。
13.如权利要求9所述的系统，其特征在于，所述节点还对应一负责节点，所述负责节点与所述节点属于同一个域，其中：所述负责节点，用于检测到节点离开时，向其所在域外的其他域的节点发送更新通知消息；
其他域的节点，用于收到该更新通知消息后，根据域间路由建立原则进行逆向查找，在其他域中查找到更新节点；其中，所述离开节点是离开节点所在域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点；
更新节点，用于建立与离开节点所在域中新域外路由节点之间的域间路由路径，其中，所述新域外路由节点是离开节点所在域中节点标识与所述更新节点的节点标识之间满足预设的域间路由建立原则的节点。
14.如权利要求13所述的系统，其特征在于，所述负责节点，还用于在所述更新通知消息中携带所述新域外路由节点的信息，所述更新节点，用于从所述更新通知消息中获取新域外路由节点的信息。
15.如权利要求12或13或14所述的系统，其特征在于，域间路由路径的两个节点分别称为首节点和尾节点，路径方向是从首节点到尾节点，所述域间路由建立原则是指，尾节点与尾节点所在域中的所有节点相比，其节点标识大于且最接近首节点的节点标识，或者其节点标识小于且最接近首节点的节点标识，或者其节点标识与首节点的节点标识之差的绝对值最小。
所述域外路由节点或其他域的节点用于按如下方式查找更新节点：
路由建立原则为尾节点节点标识大于且最接近首节点的节点标识时，查找节点标识小于且最接近所述新加入节点或离开节点的节点作为更新节点；
路由建立原则为尾节点节点标识小于且最接近首节点的节点标识时，查找节点标识大于且最接近所述新加入节点或离开节点的节点作为更新节点；
路由建立原则为尾节点节点标识与首节点的节点标识之差的绝对值最小时，查找节点标识与所述新加入节点或离开节点的节点标识之差的绝对值最小的节点作为更新节点。
一种多域域间路由维护方法和系统
技术领域
[0001] 本发明涉及对等网(Peer-to-Peer，P2P)技术领域，尤其是涉及一种多域的结构化对等网络域间路由维护方法和系统。
背景技术
[0002] P2P网络是分布式网络和计算机技术相结合的产物，是采用对等模式工作的计算机网络。P2P网络允许节点自由加入叠加网，所有节点功能对等、分布式地自组织成一个整体网络，能够极大程度地提高网络效率，充分利用网络带宽，开发每个网络节点的潜力。特别是基于分布式哈希表(DistributedHash Table，简称DHT)和覆盖网络(Overlay Network)的全分布式结构化P2P网络(即DHT网络)得到业界的广泛重视。
[0003] DHT网络主要是采用分布式散列表技术来组织网络中的节点(即加入到P2P网络中的用户主机或服务器)。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。只要目的节点存在于网络中，DHT总能发现它，发现的准确性得到了保证，最经典的案例是Tapestry、Pastry、Chord和CAN。
[0004] 这些典型的DHT网络的路由查找的复杂度一般随网络节点数目增多而增大，一般为O(log N)，N为网络中最大节点数。在DHT网络中还有一类基于常数路由复杂度的路由算法O(1)DHT，这类DHT算法的路由复杂度是不随网络最大节点数的变化而变化的，它对应的路由复杂度是一个常数，也就是查找需要的跳数是一个常数。现在一些结构化覆盖网的研究者提出一些在一跳或两跳之内即可完成消息路由的结构化覆盖网协议，其中典型有Kelips算法、多域One-hop(单跳)算法等。
[0005] 多域One-hop算法将整个P2P网络划分为若干域，域的划分按照地域位置来进行，对于每个域有唯一的域标识(简称域ID)与之对应；地域划分所依据的地域位置信息可以是节点或用户所在的行政区域划分，或运营商区域划分等。整个P2P网络中的域划分以及域的数目可以根据实际情况来定。
[0006] 下面简单介绍一下多域One-hop算法中的域间路由方法。整个叠加网中分N个域，每个域中的任何一个节点都有一个域外路由表，表中记录其它域中的部分节点的路由信息。域外路由表中节点是随机选取，动态更新的。如图1所示，为在某一时间间隔内，域2中的节点和其它域部分节点路由连接情况。
[0007] 图2示意了一个域的某个节点(如节点A)和域2中的节点的域外路由动态更新的过程。步骤如下：
[0008] S101，节点A在加入叠加网时，随机选取其它域中的某个节点(如节点P)做为其域外路由连接节点，节点A和节点P建立信任连接，同时定时向其发送heartbeat(心跳)请求消息。
[0009] S102，节点P随机选取域2中的一个节点(如节点Q)，返回heartbeat响应给节点P时带上节点Q信息。
[0010] S103，节点A更改域外路由表中域2表项，把原先节点P信息，改为节点Q信息，同时节点A和节点Q建立信任连接，向节点Q发送heartbeat请求消息。
[0011] S104，节点Q随机选取域2中的一个节点(如节点S)，返回heartbeat响应给节点P时带上节点S信息。
[0012] 这样节点A不断地更新到域2中的路由节点信息。节点A随着心跳不断地更新信任连接。整个叠加网中几百万个节点都在不断地更新信任连接，对系统来说是一个很大的开销。
发明内容
[0013] 本发明要解决的技术问题是提供一种多域域间路由维护方法和系统，以提高叠加网中的节点性能，减少域间路由维护开销。
[0014] 为了解决上述问题，本发明提供了一种多域域间路由维护方法，包括：节点加入时，在该新加入节点所在域外的其它域中查找到其对应的域外路由节点，建立所述节点到所述域外路由节点的域间路由路径，所述域外路由节点是指该域外路由节点所在域中节点标识与所述新加入节点的节点标识之间满足预设的域间路由建立原则的节点；所述其它域中的相关节点根据域间路由建立原则，建立或调整到该新加入节点所在域的域间路由路径。
[0015] 进一步地，上述方法还具有以下特点：
[0016] 节点加入时，该节点称为第一节点，该节点的加入的域称为第一域，与其它域中的一个域，该域称为第二域，建立域间路由路径具体包括：第一节点加入第一域，向第二域的第二节点发送请求消息；第二节点根据域间路由建立原则在第二域查找到域外路由节点，域外路由节点返回响应消息给所述第一节点；所述第一节点建立到所述域外路由节点的域间路由路径。
[0017] 进一步地，上述方法还具有以下特点：
[0018] 第一节点为加入所述第一域的第一个节点时，还包括：所述第一节点收到所述响应消息后，发送更新通知消息给所述域外路由节点，所述域外路由节点转发所述更新通知消息至其所在域中的所有其他节点，其他节点建立到所述第一节点的域间路由路径。
[0019] 进一步地，上述方法还具有以下特点：
[0020] 第一节点为加入所述第一域的非第一个节点时，还包括：所述第一节点发送更新请求至所述域外路由节点，所述域外路由节点收到所述请求后，根据域间路由建立原则进行逆向查找，在第二域中查找到更新节点，所述更新节点建立与所述第一节点的域间路由路径，其中，所述第一节点是第一域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点。
[0021] 进一步地，上述方法还具有以下特点：
[0022] 所述节点对应一负责节点，所述负责节点与所述节点在同一个域中，负责节点检测到节点离开时，该节点称为离开节点，负责节点向负责节点所在域外的其它域的节点发送更新通知消息；其它域的节点收到该更新通知消息后，根据域间路由建立原则进行逆向查找，在其它域中查找到更新节点；其中，所述离开节点是离开节点所在域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点；所述更新节点建立与离开节点所在域的新域外路由节点之间的域间路由路径，其中，所述新域外路由节点是离开节点所在域中节点标识与所述更新节点的节点标识之间满足所述域间路由建立原则的节点。
[0023] 进一步地，上述方法还具有以下特点：
[0024] 所述更新通知消息中携带所述新域外路由节点的信息，所述更新节点从所述更新通知消息中获取新域外路由节点的信息。
[0025] 进一步地，上述方法还具有以下特点：
[0026] 域间路由路径的两个节点分别称为首节点和尾节点，路径方向是从首节点到尾节点，所述域间路由建立原则是指，尾节点与尾节点所在域中的所有节点相比，其节点标识大于且最接近首节点的节点标识，或者其节点标识小于且最接近首节点的节点标识，或者其节点标识与首节点的节点标识之差的绝对值最小。
[0027] 进一步地，上述方法还具有以下特点：
[0028] 所述根据域间路由建立原则进行逆向查找，查找到更新节点具体是指：路由建立原则为尾节点节点标识大于且最接近首节点的节点标识时，查找节点标识小于且最接近所述新加入节点或离开节点的节点作为更新节点；路由建立原则为尾节点节点标识小于且最接近首节点的节点标识时，查找节点标识大于且最接近所述加入节点或离开节点的节点作为更新节点；路由建立原则为尾节点节点标识与首节点的节点标识之差的绝对值最小时，查找节点标识与所述新加入节点或离开节点的节点标识之差的绝对值最小的节点作为更新节点。
[0029] 为了解决上述技术问题，本发明还提供了一种多域域间路由维护系统，包括若干个域，域中包括若干个节点，其中：所述节点，用于加入时，在该节点所在域外的其它域中查找到域外路由节点，建立所述节点到所述域外路由节点的域间路由路径，所述域外路由节点是指该域外路由节点所在域中节点标识与所述节点的节点标识之间满足预设的域间路由建立原则的节点；还用于在其它域中的相关节点加入时，调整到其它域的域间路由路径。
[0030] 进一步地，上述系统还具有以下特点：
[0031] 所述系统至少包括第一域和第二域，第一节点加入所述第一域，所述第二域至少包括第二节点，其中：所述第一节点，用于加入第一域时，向第二域的第二节点发送请求消息；还用于收到域外路由节点返回的响应消息时，建立到所述域外路由节点的域间路由路径；所述第二节点，用于收到该请求消息后，根据域间路由建立原则在第二域查找到域外路由节点；所述域外路由节点，用于返回响应消息给所述第一节点。
[0032] 进一步地，上述系统还具有以下特点：
[0033] 所述第一节点，还用于在第一个加入所述第一域时，在收到所述域外路由节点返回的响应消息后，发送更新通知消息给所述域外路由节点；所述域外路由节点，用于转发所述更新通知消息至其所在域中的所有其他节点；其他节点建立到所述第一节点的域间路由路径。
[0034] 进一步地，上述系统还具有以下特点：
[0035] 第一节点，还用于非第一个加入所述第一域时，发送更新请求至所述域外路由节点；所述域外路由节点，用于收到所述更新请求后，根据域间路由建立原则进行逆向查找，在第二域中查找到更新节点；其中，所述第一节点是第一域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点；所述更新节点，用于建立与所述第一节点的域间路由路径。
[0036] 进一步地，上述系统还具有以下特点：
[0037] 所述节点还对应一负责节点，所述负责节点与所述节点属于同一个域，其中：所述负责节点，用于检测到节点离开时，向其所在域外的其他域的节点发送更新通知消息；其他域的节点，用于收到该更新通知消息后，根据域间路由建立原则进行逆向查找，在其他域中查找到更新节点；其中，所述离开节点是离开节点所在域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点；更新节点，用于建立与离开节点所在域中新域外路由节点之间的域间路由路径，其中，所述新域外路由节点是离开节点所在域中节点标识与所述更新节点的节点标识之间满足预设的域间路由建立原则的节点。
[0038] 进一步地，上述系统还具有以下特点：
[0039] 所述负责节点，还用于在所述更新通知消息中携带所述新域外路由节点的信息，所述更新节点，用于从所述更新通知消息中获取新域外路由节点的信息。
[0040] 进一步地，上述系统还具有以下特点：
[0041] 域间路由路径的两个节点分别称为首节点和尾节点，路径方向是从首节点到尾节点，所述域间路由建立原则是指，尾节点与尾节点所在域中的所有节点相比，其节点标识大于且最接近首节点的节点标识，或者其节点标识小于且最接近首节点的节点标识，或者其节点标识与首节点的节点标识之差的绝对值最小。
[0042] 进一步地，上述系统还具有以下特点：
[0043] 所述域外路由节点或其他域的节点用于按如下方式查找更新节点：路由建立原则为尾节点节点标识大于且最接近首节点的节点标识时，查找节点标识小于且最接近所述新加入节点或离开节点的节点作为更新节点；路由建立原则为尾节点节点标识小于且最接近首节点的节点标识时，查找节点标识大于且最接近所述新加入节点或离开节点的节点作为更新节点；路由建立原则为尾节点节点标识与首节点的节点标识之差的绝对值最小时，查找节点标识与所述新加入节点或离开节点的节点标识之差的绝对值最小的节点作为更新节点。
[0044] 本发明所述多域域间路由维护方法，可以减少域间路由维护开销。
附图说明
[0045] 图1是现有技术中某个时间间隔内一个域到其它域连接情况示意图；
[0046] 图2是现有技术中一个域的某个节点动态更新其到另一个域连接节点示意图；
[0047] 图3是本发明新域第一个节点加入，域外路由表更新流程图；
[0048] 图4是本发明新域第一个节点加入后，两域之间相互路由示意图；
[0049] 图5是本发明域内非第一个节点加入，域外路由表更新流程图；
[0050] 图6(a)、图6(b)是本发明域内非第一个节点加入之前，两域之间相互路由示意图；
[0051] 图7(a)、图7(b)是本发明域内非第一个节点加入之后，两域之间相互路由示意图；
[0052] 图8是本发明域内节点宕机，其它域节点更新路由连接示意图。
具体实施方式
[0053] 下面结合附图和实施例对本发明进行进一步说明。
[0054] 本发明中，每个域包括若干个节点，每个节点都有一个节点标识信息，它作为全网中每个节点的唯一标识。节点标识信息可由域ID(标识)和节点ID组成，即节点标识信息＝域ID+节点ID。每个域中节点根据节点ID从小到大按顺时针顺序组成一个环，对环上任一节点，其节点ID小于其后向节点的节点ID，大于其前向节点的节点ID，其中，前向节点是指该节点顺时针方向的上一个节点，后向节点是指该节点顺时针方向的下一个节点。本发明不限于顺时针方向环路，节点也可按节点ID从小到大按逆时针顺序组成一个环，本发明对此不作限定。
[0055] 每个节点的后向节点为该节点的负责节点，负责节点用于当一个节点加入或离开时，负责处理并且通知域外其它节点，还用于检测节点是否失效，在节点失效时，向域外其它节点发送通知。域中第一个节点加入时，因不存在对应的负责节点，其路由建立方法具体见后续说明。
[0056] 本发明所述的多域域间路由维护方法包括：
[0057] 节点加入时，在该新加入节点所在域外的其他域中查找到其对应的域外路由节点，建立所述节点到该域外路由节点的域间路由路径，该域外路由节点是指该域外路由节点所在域中节点标识与所述第一节点的节点标识之间满足预设的域间路由建立原则的节点；其它域中的相关节点根据域间路由建立原则调整到该新加入节点所在域的域间路由路径；
[0058] 节点离开时，其它域中的相关节点根据域间路由建立原则，调整到该离开节点所在域的域间路由路径。
[0059] 其中，所述域间路由建立原则为节点ID最近原则等可逆向原则，可逆向原则是指，根据次原则可使域1中的节点映射到域2中的特定节点，并且域2中的节点可以知道是域1中哪个节点映射过来的，其中：
[0060] 域间路由路径的两个节点分别称为首节点和尾节点，路径方向是从首节点到尾节点，所述域间路由建立原则是指，尾节点与尾节点所在域中的所有节点相比，其节点ID大于且最接近首节点的节点ID，或者其节点ID小于且最接近首节点的节点ID，或者其节点ID与首节点的节点ID之差的绝对值最小。
[0061] 比如，第一域中的节点A要建立和第二域的路由，即首节点为节点A，选择尾节点时，选择第二域中节点ID大于且最接近节点A的节点ID的节点，比如为节点P，节点A与节点P建立域间路由路径，节点A路由到第二域时，路由到节点P。
[0062] 1)节点加入时，该节点称为第一节点，该节点的加入的域称为第一域，与其它域中的一个域，该域称为第二域，当节点为加入第一域的第一个节点时，建立域间路由路径具体包括：
[0063] 步骤a1，第一节点加入第一域，向第二域的第二节点发送请求消息；
[0064] 该第二节点是第一节点从服务器获取的第二节点中任一节点；
[0065] 步骤a2，第二节点收到该请求消息后，根据域间路由建立原则查找到域外路由节点，如果第二节点是第一节点对应的域外路由节点，则执行步骤a3，如果不是，则第二节点直接转发或通过域中其他节点转发该请求消息至域外路由节点；
[0066] 步骤a3，域外路由节点返回响应消息给所述第一节点；
[0067] 步骤a4，所述第一节点建立到所述域外路由节点的域间路由路径，在其域外路由表中保存域外路由节点的信息；
[0068] 步骤a5，所述第一节点发送更新通知消息给所述域外路由节点，所述域外路由节点转发所述更新通知消息至其所在域中的所有其他节点，其他节点建立到所述第一节点的域间路由路径，其他节点在其域外路由表中保存第一节点的信息。
[0069] 2)节点加入时，该节点称为第一节点，该节点的加入的域称为第一域，与其它域中的一个域，该域称为第二域，当节点为加入第一域的非第一个节点时，建立域间路由路径具体包括：
[0070] 步骤b1，第一节点加入第一域，向第二域的第二节点发送请求消息；
[0071] 其中，第一节点从其负责节点获取负责节点对应的域外路由节点信息，即第二节点信息，然后向第二节点发送请求消息；
[0072] 步骤b2，第二节点收到该请求消息后，根据域间路由建立原则在第二域中查找到第一节点对应的域外路由节点，如果第二节点是第一节点对应的域外路由节点，则不用转发该请求消息，执行步骤b3，如果不是，则第二节点直接转发或通过域中其他节点转发该请求消息至域外路由节点；
[0073] 步骤b3，域外路由节点返回响应消息给所述第一节点；
[0074] 步骤b4，第一节点建立到所述域外路由节点的域间路由路径，在其域外路由表中保存域外路由节点的信息；
[0075] 步骤b5，第一节点发送更新请求至所述域外路由节点，所述域外路由节点根据域间路由建立原则进行逆向查找，在第二域中查找到更新节点，所述更新节点建立与所述第一节点的域间路由路径，其中，所述第一节点是第一域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点。
[0076] 3)节点离开时，假设离开节点为第一节点，具体包括：
[0077] 步骤c1，负责节点检测到节点离开时，该节点称为离开节点，负责节点向负责节点所在域外的其它域的节点发送更新通知消息；
[0078] 具体是指，负责节点向其域外路由节点发送更新通知消息；
[0079] 步骤c2，其它域的节点收到该更新通知消息后，根据域间路由建立原则进行逆向查找，在其它域中查找到更新节点；其中，所述离开节点是离开节点所在域中节点标识与所述更新节点的节点标识满足预设的域间路由建立原则的节点；
[0080] 步骤c3，所述更新节点建立与离开节点所在域的新域外路由节点之间的域间路由路径，其中，所述新域外路由节点是离开节点所在域中节点标识与所述更新节点的节点标识之间满足所述域间路由建立原则的节点。
[0081] 其中，步骤c1中，所述更新通知消息中携带所述新域外路由节点的信息，步骤c3中，所述更新节点从所述更新通知消息中获取新域外路由节点的信息。
[0082] 上述步骤b5，c2中所述根据域间路由建立原则进行逆向查找，查找到更新节点具体是指：
[0083] 路由建立原则为尾节点节点ID大于且最接近首节点的节点ID时，查找节点ID小于且最接近所述加入或离开的节点的节点作为更新节点；
[0084] 路由建立原则为尾节点节点ID小于且最接近首节点的节点ID时，查找节点ID大于且最接近所述加入或离开的节点的节点作为更新节点；
[0085] 路由建立原则为尾节点节点ID与首节点的节点ID之差的绝对值最小时，查找节点ID与所述加入或离开的节点的节点ID之差的绝对值最小的节点作为更新节点。
[0086] 下面通过两个域间建立路由进行说明，但是，需要指出的是，本发明不限于两个域间路由维护，当存在多个域时，比如域1、域2和域3，各域两两之间建立和维护路由的方法类似只存在两个域的情况。
[0087] 结合图2，域2中已经有四个节点(P、Q、R、S)，域1中的第一个节点A加入叠加网时，域间路由更新流程如图3所示，本实施例中，域间路由建立原则为节点ID大于且最接近待建立路由的节点的节点ID，具体步骤如下：
[0088] 步骤S301，节点A从服务器获取任意节点Q信息，向节点Q发请求消息，消息中包含节点A的信息；
[0089] 步骤S302～S304，节点Q根据大于且最接近节点A的节点ID的原则判定域2中与节点A建立路由的节点，该节点称为节点A的域外路由节点或者称为最终节点，如果节点Q为最终节点，则节点Q直接返回响应消息给节点A，否则，节点Q向下一个节点转发节点A的请求消息，在该消息中包含最终节点的信息；
[0090] 下一个节点收到该请求消息时，判断自己是否为最终节点，如果不是，继续向下一个节点转发请求消息，如果是，则返回响应消息给节点A；
[0091] 本实施中，下一个节点为节点P，且节点P发现自己是最终节点时，通过节点Q返回响应消息给节点A，响应消息中包含节点P的信息。
[0092] 步骤S305，节点A收到响应消息后，保存节点P信息，并且向节点P发送update(更新)通知消息，通知节点P新域的第一个节点A加入叠加网，并要求节点P将此消息转发到节点P所在域中的其他所有节点；
[0093] 步骤S306～S308，节点P收到通知消息后，保存节点A信息，同时利用分组广播的方式向域内所有节点转发该通知消息；其它节点收到消息后，保存节点A信息。
[0094] 这样，域1和域2之间相互路由关系建立，如图4所示。域1中节点A域外路由到域2中时，选择节点P；域2中的所有节点路由到域1中时，选择节点A。
[0095] 下面介绍域内非第一个节点加入，域间路由更新流程。图6为节点C加入之前的域间路由连接示意图。图6(a)是域1所有节点路由到域2的连接示意图；图6(b)是域2所有节点路由到域1的连接示意图。图7为节点C加入之后的域间路由连接示意图。图7(a)是域1所有节点路由到域2的连接示意图；图7(b)是域2所有节点路由到域1的连接示意图。
[0096] 如图5所示，节点C加入叠加网时，域外路由更新的具体步骤包括：
[0097] 步骤S501，域1内非第一个节点C向其负责节点D发请求消息；
[0098] 负责节点的节点ID大于且最接近节点C的节点ID。
[0099] 步骤S502，节点D返回其域外路由表，其中包括节点Q信息；
[0100] 步骤S503，节点C向节点Q发送请求消息；
[0101] 步骤S504～S505，节点Q根据大于且最接近节点C的节点ID的原则，判定与节点C建立路由的节点，该节点为节点C的域外路由节点或称为最终节点；如果节点Q为最终节点，则节点Q直接返回响应消息给节点A；否则，节点Q向下一个节点转发节点C的请求消息，在该消息中包含最终节点的信息；下一个节点收到该请求消息时，判断自己是否为最终节点，如果不是，继续向下一个节点转发请求消息，如果是，则返回响应给节点A；
[0102] 本实施例中，节点Q发现自己就是最终节点，返回响应消息给节点C，响应消息中包含节点Q的信息；
[0103] 步骤S506，节点C在其域外路由表保存节点Q的信息后，向节点Q发送更新请求；
[0104] 步骤S507～S508，节点Q根据大于且最接近原则进行逆向查找，即在域2中查找节点ID小于且最接近节点C的节点，该节点称为更新节点，转发更新请求消息给更新节点，该更新节点的域外路由节点由更改为节点C。
[0105] 本实施例中，查找到的更新节点为节点P，则节点P的域外路由由节点D改为节点C，即节点P在其域外路由表中将节点D的信息删除，增加节点C的信息；节点P再原路返回响应消息给节点C。
[0106] 这样，C加入之前，节点P路由到域1是选择节点D，加点C加入后，节点P路由到域1是选择节点C了。
[0107] 下面介绍域内节点失效，域间路由更新流程。如图8所示，具体步骤如下：
[0108] 步骤S801，节点C的负责节点D定时向节点C发保活请求；
[0109] 步骤S802，如果节点D在一定时间内收到节点C返回的保活响应，则返回步骤S801；如果节点D在一定的时间内都没有收到节点C的保活响应，则执行步骤S803；
[0110] 步骤S803，节点D向节点Q发更新通知消息，通知节点Q节点C失效；
[0111] 该更新通知消息中可以携带域1中节点ID大于且最接近节点C的域外路由节点(即节点P)的节点ID的节点信息，本实施例中，域1中，节点D的节点ID大于且最接近节点P的节点ID，所以，在该更新通知消息中携带节点D的信息。
[0112] 步骤S804～S8067，节点Q根据大于且最接近的原则进行逆向查找，即在域2中查找小于节点C且最接近节点C的节点，该节点称为更新节点，向更新节点转发通知消息；更新节点收到该通知消息后，将其域外路由表中的节点C信息改为域1中节点ID大于且最接近节点P的节点，可从通知消息中获得该信息；更新节点原路返回响应消息给节点D；
[0113] 本实施例中，该更新节点为节点P，节点P收到通知消息后，将其域外路由表中的相应项中节点C信息改为节点D；原路返回响应给节点D。
[0114] 节点失效后，两个域的域间路由情况如图6所示。
