本发明涉及通信技术领域， 具体涉及一种重路由顺序规划方法及系统。 背景技术

在传统分布式网络中， 由于网络设备均没有全局业务和路径信息，通 常采 用传统约束最短路径优先（ Constrained Shortest Path First, 筒称 CSPF )算法计 算路由， 但是无法实现全网业务的优化部署和网络利用 率的最大化。

而软件定义网络（Software Defined Networking, 筒称 SDN )技术中， 可 以通过控制器对网络的集中控制以及采用全局 优化算法（Global Optimization Algorithm, 筒称 GOA ) 实现网络业务优化部署， 但是如何实现初始网络状态 到最终网络状态的无缝或无损切换， 需要合理的重路由顺序规划算法。

现有技术一采用试错、 回退为核心思想， 找到从初始网络状态切换到最终 网络状态的合适的调整顺序，但是该算法的时 间性能是指数级的， 无法在网络 中在线应用。

现有技术二要求将初始网络状态直接调整到最 终网络状态，此时对当前网 络利用率有较高要求，只有在网络利用率较低 的网络状态下才可能有较高的成 功率。 但是， 由于多数路由算法， 包括 SDN的 GOA算法， 在计算路径时， 总会优先选择费用最小的路径， 导致大部分业务的路径都集中在部分链路上， 降低了重路由顺序规划的成功率， 对网络利用率也提出更高要求。

发明内容

针对上述缺陷， 本发明实施例提供一种重路由顺序规划方法及 系统， 可以 提高重路由顺序规划算法的时间性能及调整的 成功率。

本发明第一方面提供一种重路由顺序规划方法 ， 包括：

计算待调整标签交换路径 LSP 的参考值， 所述参考值用于表示所述待调 整 LSP被调整的优先级；

从所述待调整 LSP中选择优先级最高的待调整 LSP;

根据所述待调整 LSP参考值的临界值和所述优先级最高的待调整 LSP的 参考值， 判断所述优先级最高的待调整 LSP是否适合调整； 其中， 所述待调 整 LSP参考值的临界值表示待调整 LSP调整到终态 LSP上所需要的最小参考 值；

若所述优先级最高的待调整 LSP适合调整， 则将所述优先级最高的待调 整 LSP调整到相应的终态 LSP上； 若所述优先级最高的待调整 LSP不适合调 整， 则选择至少一条待调整 LSP调整到相应的临时 LSP上。

结合第一方面，在第一种可能的实现方式中， 所述计算待调整标签交换路 径 LSP的参考值， 包括： 计算终态 LSP中与待调整 LSP不重合的链路的剩余 容量； 根据所述剩余容量和所述待调整 LSP的带宽得到链路参考值； 选择最 小的链路参考值作为所述待调整 LSP的参考值。

结合第一方面，在第二种可能的实现方式中， 所述计算待调整标签交换路 径 LSP的参考值， 包括： 计算终态 LSP中与待调整 LSP不重合的链路的预留 容量和总容量； 根据所述待调整 LSP 的带宽、 所述预留容量和所述总容量得 到链路参考值； 计算最大的链路参考值的负值作为所述待调整 LSP的参考值。

结合第一方面， 或第一方面的第一种可能的实现方式， 或第一方面的第二 种可能的实现方式， 在第三种可能的实现方式中， 所述从所述待调整 LSP 中 选择优先级最高的待调整 LSP, 包括： 从所述待调整 LSP 中选择参考值最大 的待调整 LSP; 或从所述待调整 LSP中选择参考值最小的待调整 LSP。

结合第一方面， 或第一方面的第一种可能的实现方式， 或第一方面的第 二种可能的实现方式， 或第一方面的第三种可能的实现方式，在第四 种可能的 实现方式中， 所述选择至少一条待调整 LSP调整到相应的临时 LSP上包括： 从所述待调整 LSP中选择至少一条待调整 LSP; 为所选择的待调整 LSP计算 临时 LSP; 将所述所选择的待调整 LSP调整到所述临时 LSP上。

结合第一方面的第四种可能的实现方式，在第 五种可能的实现方式中， 所 述为所选择的待调整 LSP计算临时 LSP, 包括： 计算网络中链路的剩余容量； 根据所述剩余容量计算所述链路的链路成本； 根据所述链路成本， 计算 LSP 的成本； 选择成本最低的 LSP作为所述所选择的待调整 LSP的临时 LSP。

结合第一方面的第五种可能的实现方式，在第 六种可能的实现方式中， 所 述为所选择的待调整 LSP计算临时 LSP, 包括： 计算每一条所述待调整 LSP 在下一步被调整时， 网络中链路的带宽约束被违背的总次数， 所述总次数作为 所述链路的链路成本； 根据所述链路成本， 计算 LSP 的成本； 选择成本最低 的 LSP作为所述所选择的待调整 LSP的临时 LSP。

结合第一方面， 或第一方面的第一种可能的实现方式， 或第一方面的第二 种可能的实现方式， 或第一方面的第三种可能的实现方式， 或第一方面的第四 种可能的实现方式， 或第一方面的第五种可能的实现方式， 或第一方面的第六 种可能的实现方式，在第七种可能的实现方式 中， 所述重路由顺序规划方法还 包括： 当所述待调整 LSP被调整到对应的终态 LSP或临时 LSP后， 且待后处 理列表中还保存有临时 LSP和调整失败的待调整 LSP时， 将待后处理列表中 的临时 LSP和调整失败的待调整 LSP作为新的待调整 LSP, 并执行计算待调 整标签交换路径 LSP的参考值的。

结合第一方面的第七种可能的实现方式，在第 八种可能的实现方式中， 所 述将待后处理列表中的临时 LSP 和调整失败的待调整 LSP作为新的待调整 LSP之后， 包括： 当调整所述待调整 LSP的迭代次数达到预设的最大值时， 则停止调整； 当调整所述待调整 LSP 的迭代次数未达到预设的最大值时， 执 行计算待调整标签交换路径 LSP的参考值的。

本发明第二方面提供一种重路由顺序规划系统 ， 包括：

计算单元， 用于计算待调整标签交换路径 LSP 的参考值， 所述参考值用 于指示所述待调整 LSP被调整的优先级；

选择单元， 用于从所述待调整 LSP中选择优先级最高的待调整 LSP; 判断单元， 用于根据所述待调整 LSP参考值的临界值和所述优先级最高 的待调整 LSP的参考值， 判断所述优先级最高的待调整 LSP是否适合调整； 其中， 所述待调整 LSP参考值的临界值表示待调整 LSP调整到终态 LSP上所 需要的最小参考值；

调整单元， 用于在所述优先级最高的待调整 LSP适合调整时， 将所述优 先级最高的待调整 LSP调整到相应的终态 LSP上； 在所述优先级最高的待调 整 LSP不适合调整时， 选择至少一条待调整 LSP调整到相应的临时 LSP上。

结合第一方面， 在第一种可能的实现方式中， 所述参考值计算单元包括： 第一计算单元，用于计算终态 LSP中与待调整 LSP不重合的链路的剩余容量； 第二计算单元， 用于根据所述剩余容量和所述待调整 LSP的带宽得到链路参 考值； 第一选择单元， 用于选择最小的链路参考值作为所述待调整 LSP的参 考值。

结合第二方面， 在第三种可能的实现方式中， 所述计算单元包括： 第三计 算单元， 用于计算终态 LSP中与待调整 LSP不重合的链路的预留容量和总容 量； 第四计算单元， 用于根据所述待调整 LSP的带宽、 所述预留容量和所述 总容量得到链路参考值； 第二选择单元， 用于计算最大的链路参考值的负值作 为所述待调整 LSP的参考值。

结合第二方面， 或第二方面的第一种可能的实现方式， 或第二方面的第二 种可能的实现方式， 在第三种可能的实现方式中， 所述调整单元具体包括： 第 一调整单元和第二调整单元； 其中， 第一调整单元， 用于在所述优先级最高的 待调整 LSP适合调整时， 将所述优先级最高的待调整 LSP调整到相应的终态 LSP上； 第二调整单元包括： 第一选择单元， 用于从所述待调整 LSP中选择 至少一条待调整 LSP; 第二选择单元， 用于为所选择的待调整 LSP计算临时 LSP; 临时 LSP调整单元， 用于将所述所选择的待调整 LSP调整到所述临时 LSP上。

结合第二方面的第三种可能的实现方式，在第 四种可能的实现方式中， 所 述第二选择单元包括： 第一容量计算单元， 用于计算网络中链路的剩余容量； 第一链路成本计算单元， 用于根据所述剩余容量计算所述链路的链路成 本； 第 一成本计算单元， 用于根据所述链路成本， 计算 LSP的成本； 第一临时 LSP 选择单元， 用于选择成本最低的 LSP作为所述所选择的待调整 LSP 的临时 LSP。

结合第二方面的第三种可能的实现方式，在第 五种可能的实现方式中， 所 述第二选择单元包括： 第二链路成本计算单元， 用于计算每一条所述待调整 LSP在下一步被调整时， 网络中链路的带宽约束被违背的总次数， 所述总次数 作为所述链路的链路成本； 第二成本计算单元， 用于根据所述链路成本， 计算 LSP的成本； 第二临时 LSP选择单元， 用于选选择成本最低的 LSP作为所述 所选择的待调整 LSP的临时 LSP。

结合第二方面的第一种可能的实现方式至第五 种可能的实现方式中任意 一种可能的实现方式，在第六种可能的实现方 式中， 所述重路由顺序规划系统 还包括： 循环单元， 用于当所述待调整 LSP被调整到对应的终态 LSP或临时 LSP后， 且待后处理列表中还保存有临时 LSP和调整失败的待调整 LSP时， 将待后处理列表中的临时 LSP和调整失败的待调整 LSP作为新的待调整 LSP。

本发明实施例中， 计算所有待调整 LSP的参考值， 其中， 所述参考值用 于表示每一条待调整 LSP被调整的优先级； 从待调整 LSP中选择优先级最高 的待调整 LSP,根据待调整 LSP的参考值的临界值和优先级最高的待调整 LSP 的参考值， 判断优先级最高的待调整 LSP是否适合调整， 若所述优先级最高 的待调整 LSP适合调整，则将优先级最高的待调整 LSP调整到对应的终态 LSP 上； 若所述优先级最高的待调整 LSP不适合调整， 则从待调整 LSP中选择至 少一条待调整 LSP调整到临时 LSP上。 与现有技术相比， 本发明实施例通过 计算所有待调整 LSP的参考值， 并根据待调整 LSP的参考值的临界值， 判断 优先级最高的待调整 LSP是否适合调整， 从而提高重路由顺序规划算法的时 间性能， 同时， 当优先级最高的待调整 LSP不适合调整时， 通过选择至少一 条待调整 LSP先调整到临时 LSP上， 转而处理其它待调整 LSP, 以便提高重 路由顺序规划调整的成功率。

附图说明

为了更清楚地说明本发明实施例的技术方案， 下面将对本发明实施例中所 需要使用的附图作筒单地介绍，显而易见地， 下面描述中的附图仅仅是本发明 的一些实施例，对于本领域普通技术人员来讲 ，在不付出创造性劳动的前提下， 还可以根据这些附图获得其他的附图。

图 1为本发明一实施例提供的重路由顺序规划方� �的基本流程示意图； 图 2-a为本发明一实施例提供的参考值计算方式流 程图；

图 2-b为本发明另一实施例提供的参考值计算方式 流程图；

图 3-a为本发明另一实施例提供的重路由顺序规划 方法的流程示意图； 图 3-b为本发明一实施例提供的计算临时 LSP的流程示意图；

图 3-c为本发明另一实施例提供的计算临时 LSP的流程示意图；

图 4为本发明另一实施例提供的重路由顺序规划� �法的流程示意图； 图 5为本发明另一实施例提供的重路由顺序规划� �法的流程示意图； 图 6为本发明一实施例提供的重路由顺序规划系� �的结构示意图； 图 7-a为本发明另一实施例提供的重路由顺序规划 系统的结构示意图； 图 7-b为本发明另一实施例提供的重路由顺序规划 系统的结构示意图； 图 7-c为本发明另一实施例提供的重路由顺序规划 系统的结构示意图； 图 8-a为本发明另一实施例提供的重路由顺序规划 系统的结构示意图； 图 8-b为本发明另一实施例提供的重路由顺序规划 系统的结构示意图； 图 9为本发明另一实施例提供的重路由顺序规划� �统的结构示意图； 图 10为本发明实施例所提供的重路由设备的结构� ��意图。

具体实施方式

下面将结合本发明实施例的附图， 对本发明实施例中的技术方案进行清 楚、 完整地描述， 显然， 所描述的实施例仅仅是本发明一部分实施例， 而不是 全部的实施例。基于本发明中的实施例， 本领域普通技术人员在没有做出创造 性劳动前提下所获得的所有其他实施例， 都属于本发明保护的范围。

本发明实施例提供一种重路由顺序规划方法及 系统，用于提高重路由顺序 规划算法的时间性能和调整的成功率。

如图 1所示， 一种重路由顺序规划方法， 可包括：

S110、 计算待调整标签交换路径 LSP的参考值， 所述参考值用于表示所 述待调整 LSP被调整的优先级；

可以理解的是， 待调整标签交换路径（Label Switched Path, 筒称 LSP ) 是还未被调整到终态 LSP的 LSP组，本发明实施例在调整所有待调整 LSP时， 通过按照待调整 LSP被调整的优先顺序进行调整， 而本发明实施例所提供的 参考值（ Reference Value , 筒称 RV )在直接反映待调整 LSP是否可被调整外， 特別表示了待调整 LSP可被调整的优先级。

S120、 从所述待调整 LSP中选择优先级最高的待调整 LSP;

按照上述 S110计算得到 RV,根据 RV从所有待调整 LSP中选择优先级最 高的待调整 LSP。

其中， RV表示待调整 LSP可以调整的优先级， 可以以 RV越大表示优先 级越高，或者以 RV越小表示优先级越高，进而可以选择 RV最大的待调整 LSP 或者选择 RV最小的待调整 LSP。

S130、 根据所述待调整 LSP参考值的临界值和所述优先级最高的待调整 LSP的参考值， 判断所述优先级最高的待调整 LSP是否适合调整， 其中， 所 述待调整 LSP参考值的临界值表示待调整 LSP调整到终态 LSP上所需要的最 小参考值； 若所述优先级最高的待调整 LSP适合调整， 执行 S140; 若所述优 先级最高的待调整 LSP不适合调整， 执行 S150;

可以理解的是， RV表示待调整 LSP的优先级， 同时， RV值也直接反映 了待调整 LSP是否可调整， 若任何一路待调整 LSP的 RV指示其刚好能够调 整时， 那么刚好能够调整时所要满足的最小 RV为所述待调整 LSP的临界值， 也就是说， 临界值是一个用来划分待调整 LSP可调或不可调的分界值， 如果 待调整 LSP的 RV等于临界值或大于临界值， 那么表示该待调整 LSP可以调 整， 如果待调整 LSP的 RV小于临界值， 那么表示该待调整 LSP不可以调整。 当然， 如果在上述中所选择的优先级最高的待调整 LSP的 RV值小于临界值， 那么表示所有待调整 LSP均不可调整。

S140、 将所述优先级最高的待调整 LSP调整到相应的终态 LSP上； 可以理解的是，根据待调整 LSP的 RV的临界值，确定优先级最高的待调 整 LSP可以调整时， 将优先级最高的待调整 LSP调整到相应的终态 LSP上。

S150、 选择至少一条待调整 LSP调整到相应的临时 LSP上。

其中， 根据调整 LSP的 RV的临界值， 确定优先级最高的待调整 LSP不 可以调整时， 本发明实施例采用暂时从待调整 LSP选择至少一条待调整 LSP, 为所选择的待调整 LSP计算相应的临时 LSP, 然后将所选择的待调整 LSP分 別调整到临时 LSP上。

本发明实施例中，计算待调整 LSP的 RV,其中， RV用于表示待调整 LSP 被调整的优先级， 从待调整 LSP中选择优先级最高的待调整 LSP, 如果根据 待调整 LSP的 RV的临界值， 判断优先级最高的待调整 LSP是否适合调整， 在适合调整时， 将其调整到相应的终态 LSP上， 而在不适合调整时， 说明其 它待调整 LSP也不适合调整， 从待调整 LSP中选择至少一个待调整 LSP调整 到临时 LSP上， 以便下次可以先行调整其它待调整 LSP, 可以提高调整的成 功率和算法的时间性能。

作为一个可选的实施例， 如图 2-a所示， 上述 S110具体可以包括： S2110、 计算终态 LSP中与待调整 LSP不重合的链路的剩余容量； S2120、 根据所述剩余容量和所述待调整 LSP的带宽得到链路参考值；

S2130、 选择最小的链路参考值作为所述待调整 LSP的参考值。

具体地，本发明实施例提供的计算 RV地方法可以计算终态 LSP与待调整

LSP中不重合的链路的剩余容量，然后分別计 算每一条不重合链路的剩余容量 和该待调整 LSP的带宽的差值， 则差值作为每一条不重合链路的链路参考值， 从计算所得到的链路参考值中选择最小的链路 参考值作为待调整 LSP的 RV。

假设 Q表示终态 LSP, P表示待调整 LSP, e表示终态 LSP与待调整 LSP 的不重合链路， RC ( e )表示终态 LSP与待调整 LSP不重合链路的剩余容量，

BW表示待调整 LSP的带宽， 那么由上述描述可以得到待调整 LSP的 RV的 计算公式如下：

( e ) -BW} 公式 1

或者， 计算终态 LSP中与待调整 LSP不重合的链路的剩余容量， 然后选 择剩余容量最小的链路， 计算该链路的剩余容量与待调整 LSP的带宽的差值， 则得到待调整 LSP的 RV。

同样， 假设 Q表示终态 LSP, P表示待调整 LSP, e表示终态 LSP与待调 整 LSP的不重合链路， RC ( e )表示终态 LSP与待调整 LSP不重合链路的剩 余容量， BW表示待调整 LSP的带宽， 那么由上述描述可以得到待调整 LSP 的 RV的计算公式如下：

( e ) -BW 公式 2

可以理解的是， 终态 LSP中与待调整 LSP不重合的链路， 即是终态 LSP 中具有而待调整 LSP 中不具有的链路， 如果不重合链路中剩余容量最小的链 路的剩余容量都等于或大于待调整 LSP的带宽， 说明终态 LSP中各链路有能 力接收待调整 LSP, 那么该条链路与待调整 LSP的带宽的差值等于或大于 0, 也就是待调整 LSP的 RV等于或大于 0。

举例来说， 有待调整 LSP1 和对应的终态 LSP2 , LSP1 链路为

AB-BC-CD-DF, LSP2的链路为 AB-BD-DE-EF, 那么终态 LSP2 中与待调整 LSP1不重合的链路分別有 BD、 DE、 EF, 其中， BD的剩余容量为 80M, DE 的剩余容量为 100M, EF的剩余容量为 90M, 而待调整 LSP1的带宽为 100M, 那么根据上述公式 1 , 可以得到 3个链路参考值， 分別为 -20M、 0、 -10M, 进 而待调整 LSP的 RV为 -20M。 根据上述公式 2, 3条不重合链路的最小剩余容 量为 80M, 那么 80M与待调整 LSP的带宽 100M的差值为 -20M, 进而待调整 LSP的 RV为 -20M。

作为另一个可选的实施例， 如图 2-b所示， 上述 S110具体可以包括： S2210、计算终态 LSP中与待调整 LSP不重合的链路的预留容量和总容量；

S2220, 根据所述待调整 LSP的带宽、 所述预留容量和所述总容量得到链 路参考值；

S2230, 计算最大的链路参考值的负值作为所述待调整 LSP的参考值。 具体地， 本发明实施例提供的计算 RV 另一可选方法中， 计算终态 LSP 中与待调整 LSP中不重合的链路的预留容量和总容量， 然后计算待调整 LSP 与不重合链路的预留容量的总和，再减去该链 路的总容量得到一个差值， 则该 差值作为不重合链路的链路参考值，从计算所 得到的链路参考值中选择最大的 链路参考值， 并对该链路参考值取负值得到待调整 LSP的 RV。

假设 Q表示终态 LSP, P表示待调整 LSP, e表示终态 LSP与待调整 LSP 的不重合链路， R ( e )表示终态 LSP中与待调整 LSP不重合链路的预留容量， C ( e )表示终态 LSP中与待调整 LSP不重合链路的总容量， BW表示待调整 LSP的带宽， 那么由上述描述可以得到待调整 LSP的 RV的计算公式如下： BW+R ( e ) -C ( e ) } 公式 3

或者，计算终态 LSP中与待调整 LSP不重合的链路的预留容量和总容量， 然后计算每一条不重合链路的预留容量与总容 量的差值，该差值与待调整 LSP 的带宽的总和作为不重合链路的链路参考值， 然后取最大的参考值的负值作为 待调整 LSP的 RV。

同样， 假设 Q表示终态 LSP, P表示待调整 LSP, e表示终态 LSP与待调 整 LSP的不重合链路， R ( e )表示终态 LSP中与待调整 LSP不重合链路的预 留容量， C ( e )表示终态 LSP中与待调整 LSP不重合链路的总容量， BW表 示待调整 LSP的带宽， 那么由上述描述可以得到待调整 LSP的 RV的计算公 式如下：

BW + ( R ( e ) -C ( e ) ) } 公式 4

举例来说， 有待调整 LSP1 和对应的终态 LSP2 , LSP1 链路为 AB-BC-CD-DF, LSP2的链路为 AB-BD-DE-EF, 那么终态 LSP2 中与待调整 LSP1不重合的链路分別有 BD、 DE、 EF, 其中， BD的预留容量为 10M和总 容量为 120M, DE的预留容量为 15M和总容量为 110M, EF的预留容量为 10M 和总容量为 100M,而待调整 LSP1的带宽为 100M,那么根据上述公式 3或 4, 可以得到 3个链路参考值， 分別为 -10M、 5M、 10M, 则从 3个链路参考值中 选择最大的链路参考值 10M,而最大的链路参考值 10M的负值作为待调整 LSP 的 RV。

图 2-a和图 2-b所对应的技术方案为本发明实施例提供计算 RV的可选方 法， 本领域技术人员可以理解， 除了上述计算 RV的方法外， 其它可以实现本 发明技术目的的计算方法均属于本发明保护范 围， 例如， 通过上述公式 3和 4 求得每一条不重合链路的链路参考值后， 再计算链路参考值与待调整 LSP所 传送的业务的优先级的乘积，选择最大的乘积 计算其负值作为所述待调整 LSP 的 RV, 具体计算方式如下：

BW+R ( e ) -C ( e ) }*P _pnonty

其中， Q表示终态 LSP, P表示待调整 LSP, e表示终态 LSP与待调整 LSP 的不重合链路， R ( e )表示终态 LSP中与待调整 LSP不重合链路的预留容量， C ( e )表示终态 LSP中与待调整 LSP不重合链路的总容量， BW表示待调整 LSP的带宽， P _pn 。 _nty 表示待调整 LSP的业务的优先级。

作为一个可选的实施例， 如图 3-a所示， 上述 S140可以包括：

S310、 从所述待调整 LSP中选择至少一条待调整 LSP;

S320、 为所选择的待调整 LSP计算临时 LSP;

S330、 将所述所选择的待调整 LSP调整到所述临时 LSP上。

其中， 当优先级最高的待调整 LSP不适合调整时，则说明其它待调整 LSP 在当前链路情况下不适合调整， 则从待调整 LSP 中选择至少一条待调整 LSP 调整到临时 LSP上， 以便可以通过调整开一些待调整 LSP, 从而先行调整其 它待调整 LSP。

可选地， 可以根据所传送的业务的重要性，选择传送不 重要的业务的待调 整 LSP先行调整到临时 LSP上。

可选地， 还可以将带宽比较大的待调整 LSP先行调整到临时 LSP上。 其中， 可以采用约束最短路径优先算法（ Constrained Shortest Path First, 筒称 CSPF ) 为选择的调整到临时 LSP上的待调整 LSP计算对应的临时 LSP。

作为一个可选的实施方式， 如图 3-b所示， 上述 S320具体包括：

S3211、 计算网络中链路的剩余容量；

S3212、 根据所述剩余容量计算所述链路的链路成本；

53213 , 根据所述链路成本， 计算 LSP的成本；

53214、 选择成本最低的 LSP作为所述所选择的待调整 LSP的临时 LSP。 其中，计算网络中每一条链路的剩余容量， 然后根据剩余容量计算每一条 链路的链路成本 Link Cost,根据 LSP中每一条链路的链路成本 Link Cost则可 以获得 LSP的成本， 之后选择成本最低的 LSP作为待调整 LSP的临时 LSP。

具体地， 链路成本可以通过公式计算： Link Cost=l/R ( L )

其中， R ( L ) 为链路的剩余容量。

作为另一个可选的实施方式， 如图 3-c, 上述 S320具体包括：

53221 , 计算每一条所述待调整 LSP在下一步被调整时， 网络中链路的带 宽约束被违背的总次数， 所述总次数作为所述链路的链路成本；

53222, 根据所述链路成本， 计算 LSP的成本；

53223 , 选择成本最低的 LSP作为所述所选择的待调整 LSP的临时 LSP。 其中， 通过计算待调整 LSP在下一步被调整时， 网络中链路的带宽约束 被违背的总次数， 该总次数作为该条链路的链路成本， 计算公式为：

Link C。St=N _{Link Ti} g _ht Degree

其中， NL _{lnk Tl} ght Degree为链路的带宽约束被违背的总次数。 后选择成本最低的 LSP作为待调整 LSP的临时 LSP。

当然， 临时 LSP除了上述所例举的两种计算方法， 还可以采用其它方法， 例如链路成本为 Link Cost, 那么用来计算 LSP成本的每一条链路的链路成本 为 Link Cost=l/Link Cost,然后再根据每一条链路的 1/Link Cost计算 LSP成本， 选择最低成本的 LSP作为待调整 LSP的临时 LSP, 因此， 在此对临时 LSP的 计算方法不作限定。

如图 4所示， 为基于图 1所提供的重路由顺序规划方法的另一实施例� � 包 括：

5401、 计算待调整列表中待调整 LSP的 RV, 所述 RV用于表示所述待调 整 LSP被调整的优先级；

可以理解的是， 待调整列表中存放还未被调整的待调整 LSP,待调整 LSP 是还未被调整到终态 LSP的 LSP组。本发明实施例在调整所有待调整 LSP时， 通过按照待调整 LSP被调整的优先级顺序进行调整， 而本发明实施例所提供 的 RV在直接反映待调整 LSP是否可被调整外， 特別表示了待调整 LSP可被 调整的优先级。

5402、根据所述待调整 LSP的 RV,计算所述待调整 LSP的 RV的临界值， 所述临界值为待调整 LSP调整到终态 LSP时所需要的最小 RV;

可以理解的是， RV表示待调整 LSP的优先级， 同时， RV值也直接反映 了待调整 LSP是否可调整， 若任何一路待调整 LSP的 RV指示其刚好能够调 整时， 那么刚好能够调整时所要满足的最小 RV为所述待调整 LSP的临界值， 也就是说， 临界值是一个用来划分待调整 LSP可调或不可调的分界值， 如果 待调整 LSP的 RV等于临界值或大于临界值， 那么表示该待调整 LSP可以调 整， 如果待调整 LSP的 RV小于临界值， 那么表示该待调整 LSP不可以调整。 当然， 如果在上述中所选择的优先级最高的待调整 LSP的 RV值小于临界值， 那么表示所有待调整 LSP均不可调整。

5403、 从所述待调整 LSP中选择优先级最高的待调整 LSP;

按照上述 S110计算得到 RV,根据 RV从所有待调整 LSP中选择优先级最 高的待调整 LSP。

其中， RV表示待调整 LSP可以调整的优先级， 可以以 RV越大表示优先 级越高，或者以 RV越小表示优先级越高，进而可以选择 RV最大的待调整 LSP 或者选择 RV最小的待调整 LSP。

S404、判断所述优先级最高的待调整 LSP的 RV是否小于所述临界值，若 所述优先级最高的待调整 LSP的 RV小于所述临界值， 执行 S405; 若所述优 先级最高的待调整 LSP的 RV不小于所述临界值， 执行 S409;

可以理解是， 临界值为待调整 LSP能够被调整到终态 LSP时需要的最小 值， 在待调整 LSP小于临界值时， 说明该待调整 LSP不可以调整。 S405、从所述待调整 LSP中选择至少一条待调整 LSP,并调用 CSPF算法 为所选择的待调整 LSP计算对应的临时 LSP;

如果根据所选择的优先级最高的待调整 LSP的 RV和临界值，确定优先级 最高的待调整 LSP不可以调整后， 将从所有待调整 LSP中选择至少一条待调 整 LSP, 并调用 CSRF算法为所选择的每一条待调整 LSP计算临时 LSP, 通 过将至少一条待调整 LSP调整到临时 LSP上， 从而可以转而调整其它待调整 LSP。

可选地， 可以根据所传送的业务的重要性，选择传送不 重要的业务的待调 整 LSP先行调整到临时 LSP上。

可选地， 还可以将带宽比较大的待调整 LSP先行调整到临时 LSP上。 其中， 可以采用约束最短路径优先算法（ Constrained Shortest Path First, 筒称 CSPF ) 为选择的调整到临时 LSP上的待调整 LSP计算对应的临时 LSP。

作为可选的一个实施方式，计算网络中每一条 链路的剩余容量， 然后根据 剩余容量计算每一条链路的链路成本 Link Cost, 然后计算 LSP所有链路的链 路成本 Link Cost的总和作为该 LSP的成本，之后选择成本最低的 LSP作为待 调整 LSP的临时 LSP。

具体地， 链路成本可以通过公式计算： Link Cost=l/R ( L )

其中， R ( L ) 为链路的剩余容量。

作为另一个可选的实施方式， 通过计算待调整 LSP在下一步被调整时， 网络中链路的带宽约束被违背的总次数， 该总次数作为该条链路的链路成本， 计算公式为：

Link C。St=NLink Tight Degree

其中， NL _{lnk Tl} ght Degree为链路的带宽约束被违背的总次数。

然后计算 LSP所有链路的链路成本 Link Cost的总和作为该 LSP的成本， 之后选择成本最低的 LSP作为待调整 LSP的临时 LSP。

当然， 临时 LSP除了上述所例举的两种计算方法， 还可以采用其它方法， 例如链路成本为 Link Cost, 那么用来计算 LSP成本的每一条链路的链路成本 为 Link Cost=l/Link Cost,然后计算 LSP所有链路的链路成本 1/Link Cost的总 和作为该 LSP的成本， 选择最低成本的 LSP作为待调整 LSP的临时 LSP , 因 此， 本发明实施例中对临时 LSP的计算方法不作限定。

5406、 判断是否计算临时 LSP成功， 若计算临时 LSP成功， 执行 S407; 若计算临时 LSP不成功， 执行 S410;

5407、 将所选择的待调整 LSP调整到计算的临时 LSP上；

如果为所选择的待调整 LSP计算临时 LSP成功后，将所选择的待调整 LSP 调整到临时 LSP。

5408、 将临时 LSP增加至待后处理列表；

可以理解的是， 待调整 LSP调整到临时 LSP上， 之后将该临时 LSP增加 至待后处理列表。

S409、 将优先级最高的待调整 LSP调整到对应的终态 LSP上；

S410、将计算临时 LSP失败的所选择的待调整 LSP增加至待后处理列表。 如果为待调整 LSP计算临时 LSP失败， 那么将该待调整 LSP增加至待后 处理列表。

本发明实施例中通过计算待调整列表中的待调 整 LSP的 RV, 以及待调整 LSP的 RV的临界值。 其中， RV用于表示待调整 LSP被调整的优先级， 从待 调整 LSP中选择优先级最高的待调整 LSP,如果确定优先级最高的待调整 LSP 的 RV小于临界值， 那么从待调整 LSP中选择至少一条待调整 LSP调整到为 其计算的临时 LSP上， 以便可以转而调整一些可以调整的待调整 LSP, 能够 提高重路由顺序规划算法调整的成功率。 如果确定优先级最高的待调整 LSP 的 RV大于或等于临界值，那么直接将该优先级最� ��的待调整 LSP调整到相应 的终态 LSP。

进一步， 如图 5所示， 一种重路由顺序规划方法， 包括：

5501、 判断待调整列表中是否还有待调整 LSP, 若否， 执行 S502;

在图 4所提供的重路由顺序规划方法中， 将调整失败的待调整 LSP和临 时 LSP增加至待后处理列表， 该待后处理列表中的 LSP为在处理完待调整列 表中的待调整 LSP后进行调整的 LSP, 因此，如果待调整列表中的待调整 LSP 在重复执行上述之后， 或调整到终态 LSP上， 或放至待后处理列表中， 那么 将待后处理列表中的 LSP增加至待调整列表， 重复执行上述图 4所提供的。

5502、 判断待后处理列表是否还有 LSP, 若待后处理列表还有 LSP, 执行 S503; 若待后处理列表没有 LSP, 则调整成功；

S503、 将待后处理列表中的 LSP增加至待调整列表中， 作为新的待调整

LSP;

其中， 如果待后处理列表中还有 LSP, 那么将其增加至待调整 LSP 中作 为新的待调整 LSP, 以便重新对新加进待调整列表的待调整 LSP进行计算调

S503、 判断调整待调整 LSP的迭代次数是否达到预设的最大值， 若调整 待调整 LSP的迭代次数达到预设的最大值， 则调整失败； 若调整待调整 LSP 的迭代次数未达到预设的最大值， 则继续调整。

当然， 在对待调整 LSP的调整过程中， 有可能某些待调整 LSP—直无法 调整， 导致调整算法进入死循环， 因此， 可以通过预设调整算法迭代次数的最 大值， 一旦调整的迭代次数达到预设的最大值， 将停止调整， 以免造成系统崩 本发明实施例中在待调整列表中的待调整 LSP被调整到临时 LSP或终态 LSP后， 如果待后处理列表中还保存有 LSP, 那么将待后处理列表中的 LSP 增加至待调整列表中，作为新的待调整 LSP, 并重复执行以上实施例所提供的 方案对待调整列表中的待调整 LSP进行调整， 若在确定调整的迭代次数达到 预设的最大值时， 则停止调整， 调整失败。 在反复执行以上实施例所提供的调 整步骤之后， 调整迭代次数未达到预设的最大值， 且待后处理列表没有 LSP, 则说明已经调整成功。

如图 6所示，本发明实施例还提供一种重路由顺序� �划系统 600,可包括： 计算单元 610, 用于计算待调整标签交换路径 LSP的参考值， 所述参考值 用于指示所述待调整 LSP被调整的优先级；

选择单元 620, 用于从所述待调整 LSP中选择优先级最高的待调整 LSP; 判断单元 630,用于根据所述待调整 LSP参考值的临界值和所述优先级最 高的待调整 LSP的参考值，判断所述优先级最高的待调整 LSP是否适合调整； 其中， 所述待调整 LSP参考值的临界值表示待调整 LSP调整到终态 LSP上所 需要的最小参考值；

调整单元 640, 用于在所述优先级最高的待调整 LSP适合调整时，将所述 优先级最高的待调整 LSP调整到相应的终态 LSP上； 在所述优先级最高的待 调整 LSP不适合调整时，选择至少一条待调整 LSP调整到相应的临时 LSP上。

其中， 计算单元 610计算所有待调整 LSP的参考值， 其中， 所述参考值 用于指示所述待调整 LSP被调整的优先级； 之后， 选择单元 620从所有待调 整 LSP中选择优先级最高的待调整 LSP, 判断单元 630根据该优先级最高的 待调整 LSP的参考值和待调整 LSP的参考值的临界值， 判断该优先级最高的 待调整 LSP是否适合调整， 在确定优先级最高的待调整 LSP适合调整时， 调 整单元 640将该优先级最高的待调整 LSP调整到对应的终态 LSP上， 在确定 优先级最高的待调整 LSP不适合调整时， 调整单元 640从待调整 LSP中选择 至少一条待调整 LSP调整到对应的临时 LSP上， 从而能够有效地提高重路由 顺序规划算法的时间性能和调整的成功率。

可选地， 上述选择单元 620从所述待调整 LSP中选择参考值最大的待调 整 LSP; 或从所述待调整 LSP中选择参考值最小的待调整 LSP。

作为一个可选的实施方式， 如图 7-a所示， 上述计算单元 610可包括： 第一计算单元 7110, 用于计算终态 LSP中与待调整 LSP不重合的链路的 剩余容量；

第二计算单元 7120, 用于根据所述剩余容量和所述待调整 LSP的带宽得 到链路参考值；

第一选择单元 7130, 用于选择最小的链路参考值作为所述待调整 LSP的 参考值。

具体地， 计算终态 LSP与待调整 LSP中不重合的链路的剩余容量， 然后 分別计算每一条不重合链路的剩余容量和该待 调整 LSP的带宽的差值， 则差 值作为每一条不重合链路的链路参考值，从计 算所得到的链路参考值中选择最 小的链路参考值作为待调整 LSP的 RV。

作为一个可选的实施方式， 如图 7-b所示， 所述计算单元 610可包括： 第三计算单元 7210, 用于计算终态 LSP中与待调整 LSP不重合的链路的 预留容量和总容量；

第四计算单元 7220, 用于根据所述待调整 LSP的带宽、 所述预留容量和 所述总容量得到链路参考值； 第二选择单元 7230, 用于计算最大的链路参考值的负值作为所述待 调整 LSP的参考值。

具体地， 本发明实施例提供的计算 RV 另一可选方法中， 计算终态 LSP 中与待调整 LSP中不重合的链路的预留容量和总容量， 然后计算待调整 LSP 与不重合链路的预留容量的总和，再减去该链 路的总容量得到一个差值， 则该 差值作为不重合链路的链路参考值，从计算所 得到的链路参考值中选择最大的 链路参考值， 并对该链路参考值取负值得到待调整 LSP的 RV。

作为一个可选的实施方式， 如图 7-c所示， 所述调整单元 640具体包括： 第一调整单元 7310和第二调整单元 7320;

其中， 第一调整单元 7310, 用于在所述优先级最高的待调整 LSP适合调 整时， 将所述优先级最高的待调整 LSP调整到相应的终态 LSP上；

第二调整单元 7320可包括：

第一选择单元 7321 ,用于从所述待调整 LSP中选择至少一条待调整 LSP; 第二选择单元 7322, 用于为所选择的待调整 LSP计算临时 LSP;

临时 LSP调整单元 7323, 用于将所述所选择的待调整 LSP调整到所述临 时 LSP上。

可选地， 如图 8-a所示， 所述第二选择单元 7322可包括：

第一容量计算单元 8110, 用于计算网络中链路的剩余容量；

第一链路成本计算单元 8120、 用于根据所述剩余容量计算所述链路的链 路成本；

第一成本计算单元 8130, 用于根据所述链路成本， 计算 LSP的成本； 第一临时 LSP选择单元 8140, 用于选择成本最低的 LSP作为所述所选择 的待调整 LSP的临时 LSP。

可选地， 如图 8-b所示， 所述第二选择单元 7322可包括：

第二链路成本计算单元 8210, 用于计算每一条所述待调整 LSP在下一步 被调整时， 网络中链路的带宽约束被违背的总次数， 所述总次数作为所述链路 的链路成本；

第二成本计算单元 8220、 用于根据所述链路成本， 计算 LSP的成本； 第二临时 LSP选择单元 8230, 用于选择成本最低的 LSP作为所述所选择 的待调整 LSP的临时 LSP。

如图 9所示， 所述重路由顺序规划系统 600还可以包括：

循环单元 900, 用于当所述待调整 LSP被调整到对应的终态 LSP或临时 LSP后， 且待后处理列表中还保存有临时 LSP和调整失败的待调整 LSP时， 将待后处理列表中的临时 LSP和调整失败的待调整 LSP作为新的待调整 LSP。

具体地， 当调整所述待调整 LSP 的迭代次数达到预设的最大值时， 则停 止调整； 当调整所述待调整 LSP的迭代次数未达到预设的最大值时， 执行计 算待调整标签交换路径 LSP的参考值的步骤。

参阅图 10, 本发明实施例还提供一种重路由顺序规划设备 ， 可包括： 存 储器 1010和至少一个处理器 1020 (图 10中以一个处理器为例）。 本发明实施 例的一些实施例中， 存储器 1010和处理器 1020可通过总线或其它方式连接， 其中， 图 10以通过总线连接为例。

其中， 处理器 1020执行以下步骤： 计算待调整标签交换路径 LSP的参考 值，所述参考值用于表示所述待调整 LSP被调整的优先级；从所述待调整 LSP 中选择优先级最高的待调整 LSP; 根据所述待调整 LSP参考值的临界值和所 述优先级最高的待调整 LSP的参考值， 判断所述优先级最高的待调整 LSP是 否适合调整； 其中， 所述待调整 LSP参考值的临界值表示待调整 LSP调整到 终态 LSP上所需要的最小参考值；若所述优先级最高 的待调整 LSP适合调整， 则将所述优先级最高的待调整 LSP调整到相应的终态 LSP上； 若所述优先级 最高的待调整 LSP不适合调整， 则选择至少一条待调整 LSP调整到相应的临 时 LSP上。

在本发明一些实施例中，处理器 1020还可以执行以下步骤：计算终态 LSP 中与待调整 LSP不重合的链路的剩余容量； 根据所述剩余容量和所述待调整 LSP的带宽得到链路参考值； 选择最小的链路参考值作为所述待调整 LSP的 参考值。

在本发明一些实施例中，处理器 1020还可以执行以下步骤：计算终态 LSP 中与待调整 LSP不重合的链路的预留容量和总容量； 根据所述待调整 LSP的 带宽、所述预留容量和所述总容量得到链路参 考值； 计算最大的链路参考值的 负值作为所述待调整 LSP的参考值。 在本发明一些实施例中， 处理器 1020还可以执行以下步骤： 从所述待调 整 LSP中选择参考值最大的待调整 LSP; 或从所述待调整 LSP中选择参考值 最小的待调整 LSP。

在本发明一些实施例中， 处理器 1020还可以执行以下步骤： 从所述待调 整 LSP中选择至少一条待调整 LSP; 为所选择的待调整 LSP计算临时 LSP; 将所述所选择的待调整 LSP调整到所述临时 LSP上。

在本发明一些实施例中， 处理器 1020还可以执行以下步骤： 计算网络中 链路的剩余容量； 根据所述剩余容量计算所述链路的链路成本； 根据所述链路 成本， 计算 LSP的成本； 选择成本最低的 LSP作为所述所选择的待调整 LSP 的临时 LSP。

在本发明一些实施例中， 处理器 1020还可以执行以下步骤： 计算每一条 所述待调整 LSP在下一步被调整时， 网络中链路的带宽约束被违背的总次数， 所述总次数作为所述链路的链路成本； 根据所述链路成本， 计算 LSP的成本； 选择成本最低的 LSP作为所述所选择的待调整 LSP的临时 LSP。

在本发明一些实施例中， 处理器 1020还可以执行以下步骤： 当所述待调 整 LSP被调整到对应的终态 LSP或临时 LSP后， 且待后处理列表中还保存有 临时 LSP和调整失败的待调整 LSP时， 将待后处理列表中的临时 LSP和调整 失败的待调整 LSP作为新的待调整 LSP,并执行计算待调整标签交换路径 LSP 的参考值的步骤。

在本发明一些实施例中， 处理器 1020还可以执行以下步骤： 当调整所述 待调整 LSP的迭代次数达到预设的最大值时， 则停止调整； 当调整所述待调 整 LSP的迭代次数未达到预设的最大值时，执行计 算待调整标签交换路径 LSP 的参考值的步骤。

在本发明一些实施例中， 存储器 1010可以用来存储待调整 LSP和临时 LSP。

在本发明一些实施例中， 存储器 1010还可以用来存储待调整 LSP的参考 值和所述待调整 LSP的参考值的临界值。

本领域普通技术人员可以理解实现上述实施例 方法中的全部或部分步骤 是可以通过程序来指令相关的硬件完成，所述 的程序可以存储于一种计算机可 读存储介质中， 上述提到的存储介质可以是只读存储器， 磁盘或光盘等。 以上对本发明所提供的一种重路由顺序规划方 法及系统进行了详细介绍， 对于本领域的一般技术人员，依据本发明实施 例的思想，在具体实施方式及应 用范围上均会有改变之处， 综上所述， 本说明书内容不应理解为对本发明的限