层次化确定网络中的多约束双路径路由方法

摘要

本发明公开一种层次化确定网络中的多约束双路径路由方法，实现步骤是，将确定网络划分为几个父网络，每个父网络由不同数量的子网络组成，在获取网络拓扑图中各条链路的服务质量参数和可靠性数值的情况下，基于启发式多约束最优路径算法的反向线性标记法和正向标记法，对网络拓扑图进行父网络、子网络和节点这三种简化，获得满足多个约束要求的两条路径。本发明的优点是，获得的多约束双路径不存在重复链路，保证了在第一条路径发生故障的情况下，第二条路径依然可以进行数据通信，同时本发明具有时间复杂度可确定性，且时间复杂度满足工业化设计要求，可用于部署实际的大型互联网络。

说明书

技术领域

本发明属于通信技术领域，更进一步涉及网络通信技术领域中的一种层次化确定网络DetNet(Deterministic Network)中的多约束双路径路由方法。本发明可用于在确定网络中接受多约束参数的路由查找，得出满足多个约束要求的两条路径，为确定网络提供保证服务质量QoS(Quality of Service)的路由服务，有效提升网络的复杂路由查找性能。

背景技术

服务质量QoS(Quality of Service)路由是一种基于网络的可用资源和业务流的QoS要求来选择路径的路由机制，即包含多个QoS参数的动态多约束路由协议。确定网络作为一种新兴的网络，为人们提供了多种网络服务，不同的网络服务有不同的参数约束，而单一的传统网络路由协议无法满足不同服务对不同约束参数的需求，且现有的QoS路由机制无法直接应用于确定网络，如何在确定网络中提供满足多约束的QoS路由成为一个重要的技术问题。

确定网络可以为具有极低数据丢失率和有界延迟的实时应用传送指定的单播或多播数据流。确定网络中提供了拥塞保护CP(Congestion Protection)、显式路由ER(Explicit Routes)和服务保护SP(Service Protection)三种机制来达到此效果。拥塞保护通过沿着确定数据流DF(DetNet Flow)的路径预留资源来操作，例如缓存空间或链路带宽。拥塞保护大大减少甚至完全消除由于网络内的的输出数据包拥塞而导致的数据包丢失问题，但它仅仅给在源端被限制到最大数据包大小和传输速率的确定数据流提供服务。服务保护主要包括数据包的复制和消除。其中，通过数据包的复制使得确定数据流在不同的路径中得以传输，这是一种创新的实现思想。

此机制通过在多条路径传输确定数据流，使得一些路径的丢失不会造成任何数据包的丢失。首先在源端提供确定复合流DCF(DetNet Compound Flow)分组的排序信息,这可以通过添加序列号或时间戳作为确定数据流的一部分来完成，或者可以是分组的固有属性，比如分组被接收的精确时间。然后，将这些分组复制到多个确定成员流DMF(DetNetMember Flow)中，并且沿着至少两条不同的路径将它们发送到目的端，从而保证了在一条路径的某些链路发生故障的情况下，其他路径的数据可以正常传输，这样就大大提高了传输数据的可靠性，同时很大程度上降低了数据丢失率。最后消除重复分组。此操作可以在路径的任何一个阶段进行以节省网络资源。通常情况下，在确定网络的边缘执行此操作，在终端基于序列号对分组进行丢失检测和重新排序。

其中，在实现数据包复制方面，我们可以通过在确定网络中寻找满足多约束参数的两条路径来实现。为了使寻找的两条路径的可靠性达到最高，我们可以把确定网络进行网络规模的分层，比如父网络和子网络两层，然后在网络中寻找满足多约束要求的两条路径，这样做的目的，主要是为了使获得的两条路径“相距的距离尽可能的远”，也就是说，使两条路径不但没有重复链路而且所处的网络层次也尽可能不同，这样的话，一旦一条路径的某些链路发生故障，不会影响第二条路径的数据传输，这样就大大提高了传输数据的可靠性，同时大大降低了数据丢失率。

北京邮电大学申请的专利“实现多约束QoS路由选择的优化方法及装置”(申请号201110129535.5公开号CN 102158417A)公开了一种实现多约束路由选择的优化方法。该方法利用建立路由模型，构造惩罚函数，并运用自然选择和变异操作对初始路径进行迭代求解来实现多约束条件下的最优路由选择。该方法存在的不足是，求解的时间复杂度完全依赖于初始路径的选择，运用自然选择和变异操作使得时间复杂度存在不确定性，无法在实际的大型互联网络中部署使用。

李峰在其论文“多路径QoS路由算法研究”中提出并实现了一种多路径QoS路由算法：KMulpath算法。该算法采用深度优先搜索策略,计算并预存K条满足带宽、时延和跳数约束的QoS路径，通过路径评价函数和对路径带宽利用率的比较,找出最优和次优路径。该方法存在的不足之处是，从源节点到目的节点的两条路径有可能存在重复链路，在重复链路发生故障的情况下，两条路径将同时失效，从而造成数据的丢失。

发明内容

本发明的目的在于针对上述现有技术的不足，提出一种在层次化确定网络中寻找满足多约束参数的两条路径的路由方法。

实现本发明的具体思路是：本发明将确定网络划分为几个父网络，每个父网络由不同数量的子网络组成，在获取网络拓扑图中各条链路的服务质量参数和可靠性数值的情况下，基于启发式多约束最优路径算法的反向线性标记法和正向标记法，对网络拓扑图中进行父网络、子网络和节点这三种简化，获得满足多个约束要求的两条路径，该两条路径不存在重复链路。

本发明的步骤包括如下：

(1)获取网络拓扑图中各条链路的服务质量参数和可靠性数值：

(1a)子网络中的每个节点向与其相邻的节点发送查询信息，将相邻节点接收信息后的应答，作为该两个相邻节点之间链路的服务质量参数和可靠性数值；

(1b)利用迪杰斯特拉算法，查找子网络中每两个边界节点之间的最短路径，将最短路径的服务质量参数和可靠性数值，作为该两个边界节点之间链路的服务质量参数和可靠性数值；

(1c)在每个子网络中保留边界节点，隐藏除了边界节点之外的其他节点；

(1d)子网络的边界节点向与其相邻的子网络的边界节点发送查询信息，将与其相邻的子网络的边界节点接收信息之后的应答，作为该两个相邻边界节点之间链路的服务质量参数和可靠性数值；

(2)确定源边界节点和目的边界节点：

(2a)在网络拓扑图中随机选取一个节点，作为源节点；

(2b)在网络拓扑图中除所选的节点外，随机选取一个节点，作为目的节点；

(2c)利用迪杰斯特拉算法，计算从源节点到源节点所处的子网络内的每个边界节点的路径，在所有的路径中选择服务质量参数中的跳数值最小的边界节点，作为源边界节点；

(2d)利用迪杰斯特拉算法，计算从目的节点到目的节点所处的子网络内的每个边界节点的路径，在所有路径中选择服务质量参数中的跳数值最小的边界节点，作为目的边界节点；

(3)获得源边界节点的反向线性标记值：

利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值；

(4)判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤(5)；否则，执行步骤(18)；

(5)计算网络拓扑图中的第一条路径：

(5a)利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记；

(5b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第一条路径；

(6)对网络拓扑图进行第一次简化：

(6a)判断第一条路径上从源边界节点到目的边界节点之间的每个节点与源边界节点是否属于同一个父网络，若是，则执行步骤(6b)；否则，执行步骤(6c)；

(6b)删去网络拓扑图中与源边界节点属于同一个父网络的节点；

(6c)判断不属于源边界节点所在父网络的节点与目的边界节点是否属于同一个父网络，若是，则执行步骤(6d)；否则，执行步骤(6e)；

(6d)删去网络拓扑图中与目的边界节点属于同一个父网络中的节点；

(6e)删去网络拓扑图中既不属于源边界节点所在父网络，又不属于目的边界节点所在父网络的节点所在的父网络后，得到第一次简化后的网络拓扑图；

(7)获得源边界节点的反向线性标记值：

在第一次简化后的网络拓扑图中，利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值；

(8)判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤(9)；否则，执行步骤(10)；

(9)计算第二条路径：

(9a)在第一次简化后的网络拓扑图中,利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记；

(9b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第二条路径后执行步骤(19)；

(10)对第一次简化前的网络拓扑图进行第二次简化：

(10a)判断第一条路径上从源边界节点到目的边界节点之间的每个节点与源边界节点是否属于同一个子网络，若是，则执行步骤(10b)；否则，执行步骤(10c)；

(10b)删去网络拓扑图中与源边界节点属于同一个子网络的节点；

(10c)判断不属于源边界节点所在子网络的节点与目的边界节点是否属于同一个子网络，若是，则执行步骤(10d)；否则，执行步骤(10e)；

(10d)删去网络拓扑图中与目的边界节点属于同一个子网络中的节点；

(10e)删去网络拓扑图中，既不属于源边界节点所在子网络，又不属于目的边界节点所在子网络的节点所在的子网络后，得到第二次简化后的网络拓扑图；

(11)获得源边界节点的反向线性标记值：

在第二次简化后的网络拓扑图中，利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值；

(12)判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤(13)；否则，执行步骤(14)；

(13)计算第二条路径：

(13a)在第二次简化后的网络拓扑图中,利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记；

(13b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第二条路径后执行步骤(19)；

(14)对第一次简化前的网络拓扑图进行第三次简化：

删去网络拓扑图中第一条路径上从源边界节点到目的边界节点之间的所有节点，得到第三次简化后的网络拓扑图；

(15)获得源边界节点的反向线性标记值：

在第三次简化后的网络拓扑图中，利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值；

(16)判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤(17)；否则，执行步骤(19)；

(17)计算第二条路径：

(17a)在第三次简化后的网络拓扑图中,利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记；

(17b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第二条路径后执行步骤(19)；

(18)查找失败；

(19)完成多约束双路径路由。

本发明与现有技术相比具有以下优点：

第一，由于本发明采用对网络拓扑图进行第一次简化，对第一次简化前的网络拓扑图进行第二次简化和对第一次简化前的网络拓扑图进行第三次简化的方法，使两条路径所处的网络层次尽可能不同，不同网络层次的两条路径不存在重复链路，克服了现有技术中从源节点到目的节点的两条路径有可能存在重复链路，在重复链路发生故障的情况下，两条路径将同时失效，从而造成数据丢失的问题，使得本发明在层次化确定网络中可以获得满足多个约束要求的不存在重复链路的两条路径，该两条路径保证了在第一条路径发生故障的情况下，第二条路径依然可以进行数据通信。

第二，由于本发明采用启发式多约束最优路径算法的反向线性标记法和正向标记法，而启发式多约束最优路径算法和迪杰斯特拉算法的时间复杂度是相同的，克服了现有技术中由于依赖初始路径的选取而造成的时间复杂度不确定性的问题，使得本发明具有了时间复杂度可确定性，且时间复杂度满足工业化设计要求，可用于部署实际的大型互联网络的优点。

附图说明

图1是本发明的流程图；

图2是本发明实施例中的简化前的网络拓扑图；

图3是本发明实施例中的第一次简化后的网络拓扑图。

具体实施方式

下面结合附图对本发明作进一步的详细描述。

参照附图1，对本发明的具体步骤作进一步的详细描述。

步骤1，获取网络拓扑图中各条链路的服务质量参数和可靠性数值。

子网络中的每个节点向与其相邻的节点发送查询信息，将相邻节点接收信息后的应答，作为该两个相邻节点之间链路的服务质量参数和可靠性数值。

利用迪杰斯特拉算法，查找子网络中每两个边界节点之间的最短路径，将最短路径的服务质量参数和可靠性数值，作为该两个边界节点之间链路的服务质量参数和可靠性数值。

在每个子网络中保留边界节点，隐藏除了边界节点之外的其他节点。

子网络的边界节点向与其相邻的子网络的边界节点发送查询信息，将与其相邻的子网络的边界节点接收信息之后的应答，作为该两个相邻边界节点之间链路的服务质量参数和可靠性数值。

步骤2，确定源边界节点和目的边界节点。

在网络拓扑图中随机选取一个节点，作为源节点。

在网络拓扑图中除所选的节点外，随机选取一个节点，作为目的节点。

利用迪杰斯特拉算法，计算从源节点到源节点所处的子网络内的每个边界节点的路径，在所有的路径中选择服务质量参数中的跳数值最小的边界节点，作为源边界节点。

利用迪杰斯特拉算法，计算从目的节点到目的节点所处的子网络内的每个边界节点的路径，在所有路径中选择服务质量参数中的跳数值最小的边界节点，作为目的边界节点。

步骤3，获得源边界节点的反向线性标记值。

利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值。

所述的启发式多约束最优路径算法的反向线性标记法的具体步骤如下。

第1步，将网络拓扑图中的目的边界节点加入第一个节点集合中,并将加入第一个节点集合中的目的边界节点作为工作节点，网络拓扑图中的其余节点均加入第二个节点集合中。

第2步，找出第二个节点集合中与工作节点所有相邻的节点。

第3步，从所有相邻节点中任选一个节点。

第4步，所选节点保存工作节点作为它的前一跳节点。

第5步，将工作节点到所选节点的连接链路的各个服务质量参数的值作为所选节点的各个服务质量参数的值，并保存到所选节点中。

第6步，计算所选节点的每一个服务质量参数的值和相应的约束值的比值。

第7步，对所有比值求和，将求和结果作为所选节点的反向线性标记值。

第8步，判断所有相邻节点是否选完，若是，则执行第9步；否则，执行第3步。

第9步，将除第二个集合中工作节点相邻的节点之外的其他节点的反向线性标记值记为无穷大。

第10步，从第二个集合中提取反向线性标记值最小的节点，将该节点加入到第一个节点集合中，组成新的工作节点。

第11步，找出第二个节点集合中与新工作节点所有相邻的节点。

第12步，判断所有相邻节点中的每一个节点是否满足节点标记更新条件，若是，则执行第13步；否则，执行第17步。

所述节点标记更新条件如下。

其中，r(v)表示所有相邻节点中的节点v的反向线性标记值，∑表示求和操作，K表示约束值的个数，K的取值是大于等于1的的整数，r_k(u)表示从工作节点到新工作节点u之间的连接链路的第k个服务质量参数的值，w_k(u,v)表示从新工作节点u到所有相邻节点中的节点v之间的连接链路的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值。

第13步，所选节点保存新工作节点作为它的新的前一跳节点。

第14步，对新工作节点的各个服务质量参数的值与新工作节点到所选节点的连接链路的相应服务质量参数的值求和，将每个服务质量参数对应的求和结果作为所选节点的各个新的服务质量参数值，并保存到所选节点中。

第15步，计算所选节点保存的每一个新的服务质量参数值与相应的约束值的比值。

第16步，对所有比值求和，将求和结果作为所选节点的新的反向线性标记值。

第17步，删去第二个节点集合中的新工作节点。

第18步，判断第二个节点集合是否为空，若是，则执行第19步，否则，执行第10步。

第19步，返回源边界节点的反向线性标记值。

第20步，结束启发式多约束最优路径算法的反向线性标记。

步骤4，判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤5；否则，执行步骤18。

所述的多约束服务质量参数条件如下。

r(s)≤K

其中，r(s)表示源边界节点s的反向线性标记值，K表示约束值的个数，K的取值是大于等于1的的整数。

步骤5，计算网络拓扑图中的第一条路径。

(5a)利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记。

所述的启发式多约束最优路径算法的正向标记法具体步骤如下。

第1步，将网络拓扑图中的源边界节点加入第一个节点集合中,并将加入第一个节点集合中的源边界节点作为工作节点，网络拓扑图中的其余节点均加入第二个节点集合中。

第2步，找出第二个节点集合中与工作节点所有相邻的节点。

第3步，从所有相邻节点中任选一个节点。

第4步，对工作节点的可靠性数值与工作节点到所选节点的连接链路的可靠性数值求和，将求和结果作为所选节点的可靠性数值。

第5步，所选节点保存工作节点作为它的前一跳节点。

第6步，将工作节点到所选节点的连接链路的各个服务质量参数的值作为所选节点的各个服务质量参数的值，并保存到所选节点中。

第7步，对所选节点在正向标记法与反向线性标记法中保存的同一个服务质量参数值累加，计算每个服务质量参数的求和结果同相应约束值的比值。

第8步，提取最大的比值，将该值作为所选节点的正向标记值。

第9步，判断所有相邻节点是否选完，若是，则执行第10步；否则，执行第3步。

第10步，将除第二个集合中工作节点相邻的节点之外的其他节点的正向标记值和可靠性数值记为无穷大。

第11步，在第二个集合中，任选两个节点，比较所选节点的可靠性数值的大小，选取可靠性数值较小的节点，判断是否满足以下条件，若是，则返回满足以下条件的节点；否则，返回正向标记值较小的节点，从第二个集合的未选择节点中选取一个节点，与返回节点再次比较，直至选完第二个集合中的所有节点。

所述以下条件如下。

g_k(u)+r_k(u)≤c_k

其中，g_k(u)表示节点u在正向标记法中保存的第k个服务质量参数的值，r_k(u)表示节点u在反向线性标记法中保存的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值。

第12步，将最终返回的节点加入第一个节点集合中，组成新的工作节点。

第13步，在第二个节点集合中找出与新工作节点相邻的所有节点。

第14步，从所有相邻节点中任选一个节点。

第15步，对新工作节点的可靠性数值与新工作节点到所选节点的连接链路的可靠性数值求和，将求和结果作为临时节点的可靠性数值。

第16步，对新工作节点到所选节点的连接链路的各个服务质量参数和新工作节点在正向标记法中保存的同一个服务质量参数值求和，将每个服务质量参数的求和结果作为临时节点的各个服务质量参数值。

第17步，将所选节点在反向线性标记法中保存的各个服务质量参数值作为临时节点在反向线性标记法中保存的各个服务质量参数值。

第18步，对临时节点的各个服务质量参数值与临时节点在反向线性标记法中保存的同一个服务质量参数值求和，计算每个服务质量参数的求和结果同相应约束值的比值。

第19步，提取最大的比值，将该值作为临时节点的正向标记值。

第20步，比较所选节点和临时节点的可靠性数值的大小，选取可靠性数值较小的节点，判断是否满足以下条件，若是，则返回满足以下条件的节点；否则，返回正向标记值较小的节点。

所述以下条件如下。

g_k(u)+r_k(u)≤c_k

其中，g_k(u)表示节点u在正向标记法中保存的第k个服务质量参数的值，r_k(u)表示节点u在反向线性标记法中保存的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值。

第21步，若返回的节点为临时节点，则执行第22步；否则，执行第26步。

第22步，所选节点将临时节点的可靠性数值作为新的可靠性数值。

第23步，所选节点保存新工作节点作为它的前一跳节点。

第24步，所选节点将临时节点的各个服务质量参数值作为各个新的服务质量参数值，并保存到所选节点中。

第25步，所选节点将临时节点的正向标记值作为所选节点的新的正向标记值。

第26步，判断所有相邻节点是否选完，若是，则执行第27步；否则，执行第14步。

第27步，删去第二个节点集合中的新工作节点。

第28步，判断第二个节点集合是否为空，若是，则执行第29步，否则，执行第11步。

第29步，结束启发式多约束最优路径算法的正向标记。

(5b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第一条路径。

步骤6，对网络拓扑图进行第一次简化。

第1步，判断第一条路径上从源边界节点到目的边界节点之间的每个节点与源边界节点是否属于同一个父网络，若是，则执行第2步；否则，执行第3步。

第2步，删去网络拓扑图中与源边界节点属于同一个父网络的节点。

第3步，判断不属于源边界节点所在父网络的节点与目的边界节点是否属于同一个父网络，若是，则执行第4步；否则，执行第5步。

第4步，删去网络拓扑图中与目的边界节点属于同一个父网络中的节点。

第5步，删去网络拓扑图中既不属于源边界节点所在父网络，又不属于目的边界节点所在父网络的节点所在的父网络后，得到第一次简化后的网络拓扑图。

步骤7，获得源边界节点的反向线性标记值。

在第一次简化后的网络拓扑图中，利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值。

步骤8，判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤9；否则，执行步骤10。

所述的多约束服务质量参数条件如下。

r(s)≤K

其中，r(s)表示源边界节点s的反向线性标记值，K表示约束值的个数，K的取值是大于等于1的的整数。

步骤9，计算第二条路径。

(9a)在第一次简化后的网络拓扑图中,利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记。

(9b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第二条路径后执行步骤19。

步骤10，对第一次简化前的网络拓扑图进行第二次简化。

第1步，判断第一条路径上从源边界节点到目的边界节点之间的每个节点与源边界节点是否属于同一个子网络，若是，则执行第2步；否则，执行第3步。

第2步，删去网络拓扑图中与源边界节点属于同一个子网络的节点。

第3步，判断不属于源边界节点所在子网络的节点与目的边界节点是否属于同一个子网络，若是，则执行第4步；否则，执行第5步。

第4步，删去网络拓扑图中与目的边界节点属于同一个子网络中的节点。

第5步，删去网络拓扑图中，既不属于源边界节点所在子网络，又不属于目的边界节点所在子网络的节点所在的子网络后，得到第二次简化后的网络拓扑图。

步骤11，获得源边界节点的反向线性标记值。

在第二次简化后的网络拓扑图中，利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值。

步骤12，判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤13；否则，执行步骤14。

所述的多约束服务质量参数条件如下。

r(s)≤K

其中，r(s)表示源边界节点s的反向线性标记值，K表示约束值的个数，K的取值是大于等于1的的整数。

步骤13，计算第二条路径。

(13a)在第二次简化后的网络拓扑图中,利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记。

(13b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第二条路径后执行步骤19。

步骤14，对第一次简化前的网络拓扑图进行第三次简化。

删去网络拓扑图中第一条路径上从源边界节点到目的边界节点之间的所有节点，得到第三次简化后的网络拓扑图。

步骤15，获得源边界节点的反向线性标记值。

在第三次简化后的网络拓扑图中，利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值。

步骤16，判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤17；否则，执行步骤19。

所述的多约束服务质量参数条件如下。

r(s)≤K

其中，r(s)表示源边界节点s的反向线性标记值，K表示约束值的个数，K的取值是大于等于1的的整数。

步骤17，计算第二条路径。

(17a)在第三次简化后的网络拓扑图中,利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记。

(17b)将标记后的目的边界节点作为第一个节点，将第一个节点作为工具节点，将工具节点的前一跳节点作为第一个节点的下一个节点，依次类推，直到工具节点为源边界节点为止，从第一个节点开始，将依次得到的下一个节点进行连接，得到第二条路径后执行步骤19。

步骤18，查找失败。

步骤19，完成多约束双路径路由。

下面结合实施例对本发明的计算第一条路径的步骤和从第一次简化后的网络拓扑图中计算第二条路径的步骤进行详细说明。

图2是本发明实施例中的简化前的网络拓扑图，图3是本发明实施例中的第一次简化后的网络拓扑图。在图2中：S1、S2、S3、S4、S5和S6分别表示子网络1、子网络2、子网络3、子网络4、子网络5和子网络6，L1、L2、L3和L4分别表示父网络1、父网络2、父网络3和父网络4，父网络1由子网络1构成，父网络2由子网络2和子网络3构成，父网络3由子网络4和子网络5构成，父网络4由子网络6构成，11、12和13表示子网络1的边界节点，21和22表示子网络2的边界节点，31、32和33表示子网络3的边界节点，41和42表示子网络4的边界节点，51、52和33表示子网络5的边界节点，61、62和63表示子网络6的边界节点。点之间的连线表示两节点之间的连接链路，其上标注的值为连接链路的两个服务质量参数，连接链路的可靠性数值未在图上标注，路由求解的两个约束值分别为14和13。

步骤1，获取网络拓扑图中各条链路的服务质量参数和可靠性数值。

对于节点11、12，利用迪杰斯特拉算法，查找到节点11到节点12之间的最短路径，其参数(2，2)和-lg0.99分别为节点11到节点12之间链路的两个服务质量参数和可靠性数值。同理，对于节点11、13，其参数(1，3)和-lg0.98分别为节点11到节点13之间链路的两个服务质量参数和可靠性数值。对于节点21、22，其参数(1，1)和-lg0.95分别为节点21到节点22之间链路的两个服务质量参数和可靠性数值。对于节点31、32，其参数(3，5)和-lg0.97分别为节点31到节点32之间链路的两个服务质量参数和可靠性数值。对于节点31、33，其参数(4，3)和-lg0.98分别为节点31到节点33之间链路的两个服务质量参数和可靠性数值。对于节点32、33，其参数(2，4)和-lg0.93分别为节点32到节点33之间链路的两个服务质量参数和可靠性数值。对于节点41、42，其参数(3，2)和-lg0.95分别为节点41到节点42之间链路的两个服务质量参数和可靠性数值。对于节点51、52，其参数(3，4)和-lg0.95分别为节点51到节点52之间链路的两个服务质量参数和可靠性数值。对于节点51、53，其参数(6，2)和-lg0.97分别为节点51到节点53之间链路的两个服务质量参数和可靠性数值。对于节点52、53，其参数(5，6)和-lg0.96分别为节点52到节点53之间链路的两个服务质量参数和可靠性数值。对于节点61、63，其参数(3，2)和-lg0.98分别为节点61到节点63之间链路的两个服务质量参数和可靠性数值。对于节点62、63，其参数(1，2)和-lg0.98分别为节点62到节点63之间链路的两个服务质量参数和可靠性数值。

子网络S1的边界节点12向子网络S2的边界节点21发送查询信息，得到边界节点12与边界节点21的连接链路的服务质量参数值(5，7)和可靠性数值-lg0.96。同理，对于节点12、32，其参数(1，5)和-lg0.95分别为节点12到节点32之间链路的两个服务质量参数和可靠性数值。对于节点12、51，其参数(2，4)和-lg0.98分别为节点12到节点51之间链路的两个服务质量参数和可靠性数值。对于节点12、41，其参数(2，4)和-lg0.93分别为节点12到节点41之间链路的两个服务质量参数和可靠性数值。对于节点13、21，其参数(2，3)和-lg0.99分别为节点13到节点21之间链路的两个服务质量参数和可靠性数值。对于节点13、31，其参数(2，2)和-lg0.94分别为节点13到节点31之间链路的两个服务质量参数和可靠性数值。对于节点13、52，其参数(3，2)和-lg0.95分别为节点13到节点52之间链路的两个服务质量参数和可靠性数值。对于节点13、41，其参数(4，6)和-lg0.94分别为节点13到节点41之间链路的两个服务质量参数和可靠性数值。对于节点22、61，其参数(3，2)和-lg0.98分别为节点22到节点61之间链路的两个服务质量参数和可靠性数值。对于节点33、61，其参数(1，4)和-lg0.97分别为节点33到节点61之间链路的两个服务质量参数和可靠性数值。对于节点53、62，其参数(2，2)和-lg0.99分别为节点53到节点62之间链路的两个服务质量参数和可靠性数值。对于节点42、62，其参数(1，3)和-lg0.96分别为节点42到节点62之间链路的两个服务质量参数和可靠性数值。

步骤2，确定源边界节点和目的边界节点。

源节点为子网络S1中的一个节点，利用迪杰斯特拉算法，计算从源节点到边界节点11和边界节点12的路径，选择跳数值最小的边界节点11作为源边界节点，源节点到源边界节点11的最小跳数路径的两个服务质量参数值为(1,1)。

目的节点为子网络S6中的一个节点，利用迪杰斯特拉算法，计算从目的节点到边界节点61、边界节点62和边界节点63的路径，选择跳数值最小的边界节点63作为目的边界节点，目的节点到目的边界节点63的最小跳数路径的两个服务质量参数值为(1,1)。

转化为求边界节点11到边界节点63之间满足约束值：C1＝13，C2＝12的多约束双路径求解问题。

步骤3，获得源边界节点的反向线性标记值。

将目的边界节点63加入第一个节点集合中，并将目的边界节点63作为工作节点，其余节点均加入第二个节点集合中。对第二个节点集合中目的边界节点63的每一个相邻节点，按照下式，进行标记。

r_k(u)＝w_k(t,u)

π_r(u)＝t

其中，t为工作节点，r(u)表示所有相邻节点中的节点u的反向线性标记值，∑表示求和操作，K表示约束值的个数，K的取值是大于等于1的的整数，w_k(t,u)表示从工作节点t到所有相邻节点中的节点u的连接链路的第k个服务质量参数的值，π_r(u)表示所有相邻节点中的节点u的前一跳节点，r_k(u)表示所有相邻节点中的节点u的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值。

如节点62，进行标记。

r₁(62)＝w₁(63,62)＝1，r₂(62)＝w₂(63,62)＝2，π_r(62)＝63。

同理，标记节点61。

r₁(61)＝w₁(63,61)＝3，r₂(61)＝w₂(63,61)＝2，π_r(61)＝63。

对第二个集合中除工作节点63相邻的节点之外的其他节点11、12、13、21、22、31、32、33、41、42、51、52、53的反向线性标记值都记为无穷大。

第一步，从第二个集合中提取反向线性标记值最小的节点，将该节点加入到第一个节点集合中，组成新的工作节点，根据上步的计算可知节点62的反向线性标记值最小，所以将节点62加入第一个节点集合中，组成新的工作节点。

第二步，对于第二个节点集合中与新工作节点相邻的每一个节点v，判断是否满足节点标记更新条件，若是，则对节点进行节点标记更新操作；否则，执行下一步。

所述节点标记更新条件如下。

所述节点标记更新操作如下。

r_k(v)＝r_k(u)+w_k(u,v)

π_r(v)＝u

其中，r(v)表示所有相邻节点中的节点v的反向线性标记值，∑表示求和操作，K表示约束值的个数，K的取值是大于等于1的的整数，r_k(u)表示从工作节点到新工作节点u之间的连接链路的第k个服务质量参数的值，w_k(u,v)表示从新工作节点u到所有相邻节点中的节点v之间的连接链路的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值，π_r(v)表示所有相邻节点中的节点v的前一跳节点，r_k(v)表示所有相邻节点中的节点v的第k个服务质量参数的值。

新工作节点为62，第二个节点集合中与新工作节点62相邻的节点有节点53和42，对于节点53：r(53)＝∞，所以对节点53进行节点标记更新操作：r₁(53)＝3，r₂(53)＝4，π_r(53)＝62。同理，对节点42进行节点标记更新操作：r₁(42)＝2，r₂(42)＝5，π_r(42)＝62。

第三步，删去第二个节点集合中的新工作节点，第二个节点集合变更为包含节点11、12、13、21、22、31、32、33、41、42、51、52、53、61。

第四步，判断第二个节点集合是否为空，若是，返回源边界节点的反向线性标记值；否则，返回执行第一步。

判断可知，第二个节点集合不为空，返回执行第一步，根据上述计算的反向线性标记值，选择新工作节点为61，然后按照上述的步骤，第二个节点集合中与新工作节点61相邻的节点22和33进行节点标记更新操作：r₁(22)＝6，r₂(22)＝4，π_r(22)＝61，r₁(33)＝4，r₂(33)＝6，π_r(33)＝61。第二个节点集合变更为包含节点11、12、13、21、22、31、32、33、41、42、51、52、53。

同理，重复执行以上步骤，直至第二个节点集合变更为空集，返回源边界节点的反向线性标记值，启发式多约束最优路径算法的反向线性标记结束。

步骤4，判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，执行步骤5，否则，执行步骤18。

源边界节点的反向线性标记值满足多约束服务质量参数条件。

步骤5，计算网络拓扑图中的第一条路径。

利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记。

将源边界节点11加入第一个节点集合中，并将源边界节点11作为工作节点，其余节点均加入第二个节点集合中。对第二个节点集合中源边界节点11的每一个相邻节点，按照下式，进行标记。

c(u)＝c(s)+c(s,u)

g_k(u)＝w_k(s,u)

π_g(u)＝s

其中，s为工作节点，c(s)表示工作节点的可靠性数值，c(s,u)表示工作节点到所有相邻节点中的节点u的连接链路的可靠性数值，c(u)表示所有相邻节点中的节点u的可靠性数值，w_k(s,u)表示工作节点s到所有相邻节点中的节点u的连接链路的第k个服务质量参数的值，g_k(u)表示所有相邻节点中的节点u的第k个服务质量参数的值，r_k(u)表示所有相邻节点中的节点u在反向线性标记法中保存的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值，g(u)表示所有相邻节点中的节点u的正向标记值，K表示约束值的个数，K的取值是大于等于1的的整数，π_g(u)表示所有相邻节点中的节点u的前一跳节点。

如节点12，进行标记。

c(12)＝c(11)+c(11,12)＝-lg1-lg0.99＝-lg0.99，

g₁(12)＝w₁(11,12)＝2，g₂(12)＝w₂(11,12)＝2，π_g(12)＝11。

同理，对节点13进行标记。

c(13)＝c(11)+c(11,13)＝-lg1-lg0.98＝-lg0.98，

g₁(13)＝w₁(11,13)＝1，g₂(13)＝w₂(11,13)＝3，π_g(13)＝11。

将除第二个集合中工作节点相邻的节点之外的其他节点21、22、31、32、33、41、42、51、52、53、61、62和63的正向标记值和可靠性数值记为无穷大。

第一步，在第二个集合中，任选两个节点，比较所选节点的可靠性数值的大小，选取可靠性数值较小的节点，判断是否满足以下条件，若是，则返回满足以下条件的节点；否则，返回正向标记值较小的节点，从第二个集合的未选择节点中选取一个节点，与返回节点再次比较，直至选完第二个集合中的所有节点，将最终返回的节点加入第一个节点集合中，组成新的工作节点。

所述以下条件如下。

g_k(u)+r_k(u)≤c_k

其中，g_k(u)表示节点u在正向标记法中保存的第k个服务质量参数的值，r_k(u)表示节点u在反向线性标记法中保存的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值。

对于节点12和13：c(12)＜c(13)，g₁(12)+g₁(12)＜13，g₂(12)+g₂(12)＞12，g(12)＞g(13)，因此返回节点13。将返回的节点13加入第一个集合中，组成新的工作节点。

第二步，对于第二个节点集合中与新工作节点相邻的每一个节点v，根据计算临时节点的式子计算临时节点的各项数值，比较节点v和临时节点的可靠性数值的大小，选取可靠性数值较小的节点，判断是否满足以下条件，若是，则返回满足以下条件的节点；否则，返回正向标记值较小的节点，若返回的节点为临时节点，对节点进行节点标记更新操作。

所述计算临时节点的式子如下。

c(temp)＝c(u)+c(u,v)

g_k(temp)＝g_k(u)+w_k(u,v)

r_k(temp)＝r_k(v)

其中，c(temp)表示临时节点的可靠性数值，c(u)表示新工作节点的可靠性数值，c(u,v)表示新工作节点到所有相邻节点中的节点u的连接链路的可靠性数值，g_k(temp)表示临时节点的第k个服务质量参数的值，w_k(u,v)表示新工作节点到所有相邻节点中的节点u的连接链路的第k个服务质量参数的值，g_k(u)表示新工作节点在正向标记法中保存的第k个服务质量参数的值，r_k(v)表示所有相邻节点中的节点u在反向线性标记法中保存的第k个服务质量参数的值，r_k(temp)表示临时节点在反向线性标记法中保存的第k个服务质量参数的值，c_k表示第k个服务质量参数的约束值，g(temp)表示临时节点的正向标记值。

所述以下条件如下。

g_k(u)+r_k(u)≤c_k

其中，g_k(u)表示节点u在正向标记法中保存的第k个服务质量参数的值，r_k(u)表示节点u在反向线性标记法中保存的第k个服务质量参数的值，

所述节点标记更新操作如下。

c(v):＝c(temp)

g(v):＝g(temp)

g_k(v):＝g_k(temp)

π_g(v):＝u

其中，c(temp)表示临时节点的可靠性数值，c(v)表示所有相邻节点中的节点v的新的可靠性数值，g(temp)表示临时节点的正向标记值，g(v)表示所有相邻节点中的节点v的新的正向标记值，g_k(temp)表示临时节点的第k个服务质量参数的值，g_k(v)表示所有相邻节点中的节点v的各个新的服务质量参数值，π_g(v)表示所有相邻节点中的节点v的的前一跳节点。

新工作节点为13，第二个节点集合中与新工作节点相邻的所有节点为21、31、41和52。

对于节点21：c(temp)＝c(13)+c(13,12)＝-lg0.9702，

g₁(temp)＝g₁(13)+w₁(13,21)＝3,g₂(temp)＝g₂(13)+w₂(13,21)＝6,

r₁(temp)＝r₁(21)＝7，r₂(temp)＝r₂(21)＝5，由于c(21)＝∞，c(temp)＜c(21)，g₁(temp)+r₁(temp)＜13，g₂(temp)+r₂(temp)＜12，因此返回临时节点temp，所以对节点21进行节点标记更新操作：c(21)＝-lg0.9702，g₁(21)＝3，g₂(21)＝6，π_g(21)＝13。

同理，对于节点31：c(31)＝-lg0.9212，g₁(31)＝3，g₂(31)＝5，π_g(31)＝13。对于节点41：c(41)＝-lg0.9212，g₁(41)＝5，g₂(41)＝9，π_g(41)＝13。对于节点52：c(52)＝-lg0.931，g₁(52)＝4，g₂(52)＝5，π_g(52)＝13。

第三步，删去第二个节点集合中的新工作节点，第二个节点集合变更为包含节点12,21,22,31,32,33,41,42,51,52,53,61,62和63。

第四步，判断第二个节点集合是否为空，若是，启发式多约束最优路径算法的正向标记结束；否则，返回执行第一步。

判断可知，第二个节点集合不为空，返回执行第一步。

对于节点12和21：c(12)＜c(21)，g₁(12)+g₁(12)＜13，g₂(12)+g₂(12)＞12，g(12)＞g(21)，因此在节点12和21中返回节点21。

对于节点21和31：c(21)＜c(31)，g₁(21)+g₁(21)＜13，g₂(21)+g₂(21)＜12，因此在节点21和31中返回节点21。

对于节点21和41：c(21)＜c(41)，g₁(21)+g₁(21)＜13，g₂(21)+g₂(21)＜12，因此在节点21和41中返回节点21。

对于节点21和52：c(21)＜c(52)，g₁(21)+g₁(21)＜13，g₂(21)+g₂(21)＜12，因此在节点21和52中返回节点21。

最终返回节点21，将节点21加入第一个节点集合，并作为新工作节点。

第二个节点集合中与节点21相邻的所有节点为节点12和22。

对于节点12：

c(temp)＝c(21)+c(21,12)＝-lg0.931392，

g₁(temp)＝g₁(21)+w₁(21，12)＝8,g₂(temp)＝g₂(21)+w₂(21，12)＝13,

r₁(temp)＝r₁(12)＝7，r₂(temp)＝r₂(12)＝11，

由于c(21)＝-lg0.99，c(temp)＞c(12)，g₁(12)+r₁(12)＜13，g₂(12)+r₂(12)＞12，g(temp)＞g(12)，因此返回节点12，节点12的标记不变。

对于节点22：

c(temp)＝c(21)+c(21,22)＝-lg0.92169，

g₁(temp)＝g₁(21)+w₁(21，22)＝4,g₂(temp)＝g₂(21)+w₂(21，22)＝7,

r₁(temp)＝r₁(22)＝6，r₂(temp)＝r₂(22)＝4，

由于c(22)＝∞，c(temp)＜c(22)，g₁(temp)+r₁(temp)＜13，g₂(temp)+r₂(temp)＜12，因此返回临时节点temp,所以对节点22进行节点标记更新操作：c(22)＝-lg0.92169，g₁(22)＝4，g₂(22)＝7，π_g(22)＝21。

新节点集N变更为包含节点12,22,31,32,33,41,42,51,52,53,61,62和63。同理，重复执行以上步骤，直至第二个节点集合变更为空集，启发式多约束最优路径算法的正向标记结束。

至此，可以得出第一条路径P1为：11→13→21→22→61→63。路径P1的两个服务质量参数分别为w₁(p1)＝10，w₂(p1)＝11，满足给出的约束值。

步骤6，对网络拓扑图进行第一次简化。

节点13与源边界节点11属于同一个父网络L1，因此在父网络L1中删去节点13。节点21与源边界节点11不属于同一个父网络，与目的边界节点63也不属于同一个父网络，因此删去节点21所在的网络L2。节点22与源边界节点11不属于同一个父网络，与目的边界节点63也不属于同一个父网络，因此删去节点22所在的网络L2。节点61与目的边界节点63属于同一个父网络L4，因此在父网络L4中删去节点61，对网络拓扑图进行第一次简化后得到图3。

步骤7，获得源边界节点的反向线性标记值。

在第一次简化后的网络拓扑图中，利用启发式多约束最优路径算法的反向线性标记法，得到源边界节点的反向线性标记值，

步骤8，判断源边界节点的反向线性标记值是否满足多约束服务质量参数条件，若是，则执行步骤9；否则，执行步骤10。

满足多约束服务质量参数条件。

步骤9，计算第二条路径。

在第一次简化后的网络拓扑图中,利用启发式多约束最优路径算法的正向标记法，对网络拓扑图中的每个节点进行标记。

至此，可以得出第二条路径P2为：11→12→51→53→62→63。路径P2的两个服务质量参数分别为w₁(p2)＝13，w₂(p2)＝12，满足给出的约束值。由于本实例的特殊性，在步骤9已经得出路由结果，不再执行步骤10到步骤19。从上述实施例的实现过程中可以发现，本发明实现了层次化确定网络中的多约束双路径路由方法。