本发明涉及通信技术领域，具体是涉及一种路径计算方法及系统。
背景技术：
传统的路由计算领域，业务路由通常是按顺序单条进行最短路径计算；但在密集波分复用(dense-wavelengthdivisionmultiplexing，dwdm)网络中，由于频谱、可用波道等限制，对于多条业务同时进行优化，往往无法获取总体最短的传输长度，单条业务在当时的资源情况下的最短，组合起来并不是最优的解，达不到全局最短路径的要求。
技术实现要素：
针对现有技术中存在的缺陷，本发明的目的在于提供一种路径计算方法及系统，在资源受限的情况下，尽可能缩短业务的当前工作路径的总长度，提高全网整体运行效率。
本发明提供一种路径计算方法，其包括：
计算每个业务的k短路径和所有业务的当前工作路径的总长度；
比较每个业务的当前工作路径与最短路径的偏离程度，从偏离程度最大的业务开始，释放最短路径中的资源以替换当前工作路径，并为被释放的资源所属的业务重新分配当前工作路径，使得调整后当前工作路径的总长度减小；
其中，最短路径以及重新分配的当前工作路径都属于k短路径。
在上述技术方案的基础上，对于第i个业务，所述偏离程度pi为：
其中，ri表示第i个业务的所述当前工作路径的长度，ri0表示第i个业务的所述最短路径的长度，1≤i≤n。
在上述技术方案的基础上，在所述最短路径的每条链路上，释放所述偏离程度最小的业务占用的资源，以释放资源后得到的路径替换所述当前工作路径。
在上述技术方案的基础上，所述方法还包括：
当所述当前工作路径的总长度与所有业务的所述最短路径的总长度的偏差值低于设定阈值时，停止调整所述当前工作路径。
在上述技术方案的基础上，在计算每个业务的k短路径之前，获取所有业务的所述当前工作路径的信息；或者，从所述k短路径中确定所述当前工作路径。
本发明还提供一种路径计算系统，其包括：
计算模块，其用于计算每个业务的k短路径和所有业务的当前工作路径的总长度；
调整模块，其用于比较每个业务的当前工作路径与最短路径的偏离程度，从偏离程度最大的业务开始，释放最短路径中的资源以替换当前工作路径，并为被释放的资源所属的业务重新分配当前工作路径，使得调整后当前工作路径的总长度减小；其中，最短路径以及重新分配的当前工作路径都属于k短路径。
在上述技术方案的基础上，对于第i个业务，所述偏离程度p为：
其中，ri表示第i个业务的所述当前工作路径的长度，ri0表示第i个业务的所述最短路径的长度，1≤i≤n。
在上述技术方案的基础上，所述调整模块用于在所述最短路径的每条链路上，释放所述偏离程度最小的业务占用的资源，以释放资源后得到的路径替换所述当前工作路径。
在上述技术方案的基础上，所述调整模块还用于当所述当前工作路径的总长度与所有业务的所述最短路径的总长度的偏差值低于设定阈值时，停止调整所述当前工作路径；
所述计算模块还用于从所述k短路径中确定所述当前工作路径。
在上述技术方案的基础上，所述系统还包括：
获取模块，其用于获取所有业务的所述当前工作路径的信息。
与现有技术相比，本发明实施例路径计算方法包括：计算每个业务的k短路径(kshortestpath，ksp)和所有业务的当前工作路径的总长度；比较每个业务的当前工作路径与最短路径的偏离程度，从偏离程度最大的业务开始，释放最短路径中的资源以替换当前工作路径，并为被释放的资源所属的业务重新分配当前工作路径，使得调整后当前工作路径的总长度减小；其中，最短路径以及重新分配的当前工作路径都属于k短路径。本发明实施例在资源受限的情况下，尽可能缩短业务的当前工作路径的总长度，提高全网整体运行效率。
附图说明
为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是本发明实施例路径计算方法流程图；
图2是应用本发明实施例路径计算方法的网络拓扑示意图；
图3是本发明实施例路径计算系统示意图。
具体实施方式
下面结合附图及具体实施例对本发明作进一步的详细描述。
参见图1所示，本发明实施例提供一种路径计算方法，路径计算方法包括：
s110计算每个业务的k短路径和所有业务的当前工作路径的总长度。
s120比较每个业务的当前工作路径与最短路径的偏离程度，从偏离程度最大的业务开始，释放最短路径中的资源以替换当前工作路径，并为被释放的资源所属的业务重新分配当前工作路径，使得调整后当前工作路径的总长度减小；其中，最短路径以及重新分配的当前工作路径都属于k短路径。
本发明实施例具有的特点包括：降低了全局的路由长度，提升了资源利用率；基于全局进行调整，部分解决了局部最优不等于全局最优的问题；提高了全网整体运行效率。
相比于传统的路由计算模式，本发明实施例可以解决网格(mesh)网络的由于资源受限原因导致全局路由无法最优问题，能够较大幅度地降低全局的路由长度。
本发明实施例的路径计算方法，在优先保证满足频谱和可用波道受限的情况下，尽可能缩短业务工作路径的总长度，适用于对于工作路径的总长度要求较高的国家干线网络和国际干线网络。
作为一个可选的实施方式，对于第i个业务，偏离程度pi为：
其中，ri表示第i个业务的当前工作路径的长度，ri0表示第i个业务的最短路径的长度，1≤i≤n，n为全网中业务的总数量，n为正整数，通常情况下，n>1。
作为一个可选的实施方式，在最短路径的每条链路上，释放偏离程度最小的业务占用的资源，以释放资源后得到的路径替换当前工作路径。
具体的，最短路径包括m条链路，m为正整数，通常情况下，m≥1。
作为一个可选的实施方式，路径计算方法还包括：
当当前工作路径的总长度与所有业务的最短路径的总长度的偏差值低于设定阈值时，停止调整当前工作路径。
作为一个可选的实施方式，在步骤s110之前，路径计算方法还包括：
s100获取所有业务的当前工作路径的信息。
作为一个可选的实施方式，在步骤s110中，从k短路径中确定当前工作路径。
具体的，可以根据现有的路径资源分配算法从k短路径中确定当前工作路径。
在一个示例中，本发明实施例路径计算方法包括：
s201计算每个业务的k短路径，计算k短路径与最短路径的偏差值。
对于第i个业务(c_i)，计算第k短路径与最短路径的偏离值p(c_ik)，即p(c_ik)＝r(c_ik)-r(c_i0)，其中，r(c_ik)为第k短路径的长度，r(c_i0)为最短路径的长度。
s202根据路径资源分配算法计算出所有业务的路径、波长以及中继资源分配，并标记出每个业务的当前工作路径p，0≤p≤k-1，0表示最短路径，当前工作路径p是k短路径中的一条路径，r(c_ip)表示业务c_i的第p短路径的长度，并记录所有业务的当前工作路径的总长度。
s203计算业务c_i的当前偏离程度：p(c_ip)-paver，其中，p(c_ip)为当前工作路径与最短路径的偏离值，即p(c_ip)＝r(c_ip)-r(c_i0)，paver为所有业务的当前工作路径与最短路径的偏差值的平均值，
s204对所有业务按当前偏离程度从大到小排序。
s205调整偏离程度最大的业务c_j的路径和资源。
例如：业务c_j的最短路径的长度为r(c_j0)，最短路径经过三条链路，每条链路上的业务集合分别为(c_j1,c_j2,c_j3)，(c_j4,c_j5,c_j6,c_j7)和(c_j2,c_j5,c_j8)。
s206对每条链路上的业务集合按偏离程度从大到小排序。
s207删除所有的偏离程度最小的业务的路径和资源。
s208当删除完所有的链路上偏离程度最小的业务，即能够释放出一条路径供偏离程度最大的业务使用。
s209再依次计算所有链路上被释放路径和资源所属的业务的当前工作路径。
s210对比调整后的当前工作路径的总长度和调整前当前工作路径的总长度，如果有降低，即进入步骤s211；否则，不作调整，结束流程。
s211进行调整，并将本次调整的偏离程度最大的业务放入不变集合中，下次循环时不进行调整。
s212判断是否满足退出条件，若是，结束；若否，返回步骤s204。
退出条件包括两个：所有业务的当前工作路径的总长度与所有业务的最短路径的总长度的偏差值低于设定阈值，或者，受到资源限制而无法继续调整。
本发明实施例基于k短路径算法，利用冒泡算法的思路进行路由计算以及路径长度调整分析，重点需要解决网络mesh程度较高时，需要得到全网最短路由路径的问题。
以下通过一个具体示例说明本发明实施例路径计算方法。
参见图2所示的网络拓扑示意图，包括节点node1、node2、node3、node4和node5，其中，node1→node2、node1→node3、node1→node4、node2→node3、node3→node4均只存在一个可用波道，node1→node2的长度为200公里(km)、node1→node3的长度为80km、node1→node4的长度为100km、node2→node3的长度为100km、node3→node4的长度为120km，任意两节点之间均可以不做中继完成；存在业务a(node1→node2)和业务b(node1→node3)。
本发明实施例路径计算方法包括：
s310计算两条业务的k短路径，并确定当前工作路径。
首先计算业务a的k短路径，例如k＝3，一共有三条可通路径(node1→node2：长度为200km，node1→node3→node2：长度为180km；node1→node4→node3→node2：长度为320km)，从最短路径出发选择node1→node3→node2作为业务a的当前工作路径。
然后计算业务b的k短路径，一共三条可通路径(node1→node2→node3：长度为300km；node1→node3：长度为80km；node1→node4→node3：长度为220km)，node1→node3最短，但资源被业务a占用，因此选择node1→node4→node3作为业务b的当前工作路径。
业务a和业务b的当前工作路径的总长度为180 220＝400km。
s320计算上述业务的k短路径相对于最短路径的偏差值：
业务a：
node1→node2：偏差值为20km，11％；
node1→node3→node2(当前工作路径)：基准值；
node1→node4→node3→node2：偏差值为140km，78％。
业务b：
node1→node2→node3：偏差值为220km，2.75；
node1→node3：基准值；
node1→node4→node3(当前工作路径)：偏差值为220km，2.75。
s330按偏离程度对业务排序
按偏离程度排序后，调整顺序为：首先业务b，然后业务a。
s340调整业务的当前工作路径
业务b的最短路径为node1→node3，业务b的最短路径上存在业务a，释放业务a占据的资源；
得到业务b的调整后的路由：node1→node3；
从业务a的k短路径中得到调整后的路由：node1→node2。
s350判断调整前、后当前工作路径的总长度
调整后所有业务的当前工作路径的总长度200km 80km＝280km，调整前所有业务的当前工作路径的总长度180km 220km＝400km。比较后，调整后当前工作路径的总长度低于调整前当前工作路径的长度，判定调整业务a和业务b的路由，将调整后业务b的当前工作路径加入到不变列表。
s360判断业务a，业务a无法调整，流程终止。
参见图3所示，本发明实施例还提供一种路径计算系统，用于实现前述实施例路径计算方法，路径计算系统包括计算模块和调整模块。
计算模块用于计算每个业务的k短路径和所有业务的当前工作路径的总长度。
调整模块用于比较每个业务的当前工作路径与最短路径的偏离程度，从偏离程度最大的业务开始，释放最短路径中的资源以替换当前工作路径，并为被释放的资源所属的业务重新分配当前工作路径，使得调整后当前工作路径的总长度减小；其中，最短路径以及重新分配的当前工作路径都属于k短路径。
作为一个可选的实施方式，对于第i个业务，偏离程度pi为：
其中，ri表示第i个业务的当前工作路径的长度，ri0表示第i个业务的最短路径的长度，1≤i≤n，n为全网中业务的总数量，n为正整数，通常情况下，n>1。
作为一个可选的实施方式，调整模块用于在最短路径的每条链路上，释放偏离程度最小的业务占用的资源，以释放资源后得到的路径替换当前工作路径。
具体的，最短路径包括m条链路，m为正整数，通常情况下，m≥1。
作为一个可选的实施方式，调整模块还用于当当前工作路径的总长度与所有业务的最短路径的总长度的偏差值低于设定阈值时，停止调整当前工作路径。
计算模块还用于从k短路径中确定当前工作路径。
作为一个可选的实施方式，路径计算系统还包括获取模块，获取模块用于获取所有业务的当前工作路径的信息。
本发明不局限于上述实施方式，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也视为本发明的保护范围之内。本说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。
1.一种路径计算方法，其特征在于，其包括：
计算每个业务的k短路径和所有业务的当前工作路径的总长度；
比较每个业务的当前工作路径与最短路径的偏离程度，从偏离程度最大的业务开始，释放最短路径中的资源以替换当前工作路径，并为被释放的资源所属的业务重新分配当前工作路径，使得调整后当前工作路径的总长度减小；
其中，最短路径以及重新分配的当前工作路径都属于k短路径。
2.如权利要求1所述的路径计算方法，其特征在于：
对于第i个业务，所述偏离程度pi为：
其中，ri表示第i个业务的所述当前工作路径的长度，ri0表示第i个业务的所述最短路径的长度，1≤i≤n。
3.如权利要求1所述的路径计算方法，其特征在于：
在所述最短路径的每条链路上，释放所述偏离程度最小的业务占用的资源，以释放资源后得到的路径替换所述当前工作路径。
4.如权利要求1所述的路径计算方法，其特征在于，所述方法还包括：
当所述当前工作路径的总长度与所有业务的所述最短路径的总长度的偏差值低于设定阈值时，停止调整所述当前工作路径。
5.如权利要求1所述的路径计算方法，其特征在于：
在计算每个业务的k短路径之前，获取所有业务的所述当前工作路径的信息；或者，从所述k短路径中确定所述当前工作路径。
6.一种路径计算系统，其特征在于，其包括：
计算模块，其用于计算每个业务的k短路径和所有业务的当前工作路径的总长度；
调整模块，其用于比较每个业务的当前工作路径与最短路径的偏离程度，从偏离程度最大的业务开始，释放最短路径中的资源以替换当前工作路径，并为被释放的资源所属的业务重新分配当前工作路径，使得调整后当前工作路径的总长度减小；其中，最短路径以及重新分配的当前工作路径都属于k短路径。
7.如权利要求6所述的路径计算系统，其特征在于：
对于第i个业务，所述偏离程度pi为：
其中，ri表示第i个业务的所述当前工作路径的长度，ri0表示第i个业务的所述最短路径的长度，1≤i≤n。
8.如权利要求6所述的路径计算系统，其特征在于：
所述调整模块用于在所述最短路径的每条链路上，释放所述偏离程度最小的业务占用的资源，以释放资源后得到的路径替换所述当前工作路径。
9.如权利要求6所述的路径计算系统，其特征在于：
所述调整模块还用于当所述当前工作路径的总长度与所有业务的所述最短路径的总长度的偏差值低于设定阈值时，停止调整所述当前工作路径；
所述计算模块还用于从所述k短路径中确定所述当前工作路径。
10.如权利要求6所述的路径计算系统，其特征在于，所述系统还包括：
获取模块，其用于获取所有业务的所述当前工作路径的信息。
技术总结