一种基于优先级机制的卫星网络重路由方法

摘要

本发明提供一种基于优先级机制的卫星网络重路由方法，包括：当故障发生在关键链路上时，根据最小干扰算法，计算链路重复率，当所述链路重复率小于级别参数时，选择第一优先级的路径，当所述链路重复率大于级别参数时，选择第二优先级的路径，当故障发生在非关键链路上时，当工作路径上的链路存在没有备份路径时，将发生故障的节点或链路前一个节点当作源节点，故障节点或链路的下一个节点作为目的节点，根据最短路径算法，在线直接算出到达目的节点的可行路由，然后重新分发标签，在标签重新分发完成后，实现通信。本发明减少了发生故障时再重新计算路径所耗费的资源，缩短了故障修复时间。

说明书

技术领域

本发明属于网络路由领域，涉及到一种基于优先级机制的卫星网络重路由 方法。

背景技术

在多协议标签交换协议（MPLS）网络中，重路由是用于当标签交换路径(LSP) 链路或节点发生失效时，对发生故障的链路或节点进行保护，以使得数据传输 不至于发生中断的一种技术。目前，按照是否需要预先预留链路资源，针对MPLS 网络的重路由主要分为两大类。第一类为需要预留资源，主要实现形式是链路 或节点保护，具体包括Haskin方法、Makam方法以及相关的改进方法。另一类 是不需要提前预留资源，当有更符合服务质量（QoS）需要的标签交换路径（LSP） 出现时或者当前LSP被其他更高优先级的LSP抢占时发生的重路由，属于该种 重路由。当通信链路或节点发生损坏时，通常采用的是第一类重路由。在卫星 网络中，由于卫星节点之间的距离较远，星上资源有限，当采用第二类重路由 时，卫星重新计算及建立LSP较为耗费星上资源，且造成的延时及延时抖动较 大。因此，应该优先采用第一类重路由。采用第一类重路由，由于需要预留资 源，当所保护的链路或节点发生故障时，可以在较短的时间内实现流量的切换， 实现快速重路由。

发明内容

基于上述问题，本发明提出了一种基于优先级机制的卫星网络重路由方法。

一种基于优先级机制的卫星网络重路由方法，包括：

当故障发生在关键链路上时，根据最小干扰算法，计算链路重复率，当所 述链路重复率小于级别参数时，选择第一优先级的路径，当所述链路重复率大 于级别参数时，选择第二优先级的路径，第一优先级的级别低于第二优先级的 级别；

当故障发生在非关键链路上时，当工作路径的每一条链路都存在的备份路 径，根据最小干扰算法，进行路由，当工作路径上的链路存在没有备份路径时， 将发生故障的节点或链路前一个节点当作源节点，故障节点或链路的下一个节 点作为目的节点，根据最短路径算法，在线直接算出到达目的节点的可行路由， 然后重新分发标签，在标签重新分发完成后，实现通信。

所述最小干扰算法具体包括：

第一步：根据链路权重函数，初始化网络中的所有链路；

第二步：根据链路关键集函数，求出关键集；

第三步：根据所求的链路关键集，对源-目标节点求出K-最短路径；

第四步：按照链路调整函数，调整关键集中的链路权重；

第五步：用最短路径算法，求出最终通信的标签交换路径。

上述当工作路径上的链路存在没有备份路径时，将发生故障的节点或链路 前一个节点当作源节点，故障节点或链路的下一个节点作为目的节点，根据最 短路径算法，在线直接算出到达目的节点的可行路由，然后重新分发标签，在 标签重新分发完成后，实现通信，具体为：当工作路径的条链路存在没有备份 路径时，根据最小干扰算法，进行路由时，当源节点根据最短路径算法计算出 的备份路径上已有另外业务流正在进行传输，确认剩余带宽是否满足工作路径 上的业务流需求，如果剩余带宽满足业务流需求，传输业务流；如果剩余带宽 不满足传输工作路径上的业务流时，确认备份路径上已有的业务流和工作路径 上业务流的优先级；如果备份路径上已有的业务流比工作路径上业务流的优先 级高，那么重路由失败；如果备份路径上已有的业务流比工作路径上业务流的 优先级低，那么工作路径上业务流就抢占备份路径上已有的业务流的带宽，进 行数据流的传输。

本发明的效果和益处是，有效的利用了路由时的计算，减少了发生故障时 再重新计算路径所耗费的资源，缩短了故障修复时间，缓解了星上资源紧张的 情况，实现对工作路径上的所有链路进行保护。

附图说明

附图1为故障发生在关键链路上的重路由方法示意图；

附图2为故障发生在非关键链路上的重路由策略。

具体实施方式

以下结合技术方案和附图详细叙述本发明的具体实施方式。

卫星MPLS网络不同于地面MPLS网络，在卫星MPLS网络中，卫星处于高速 运动中，卫星网络拓扑呈现周期性变化。目前针对卫星网络拓扑变化的解决方 法主要分为三大类，分别为时间拓扑快照方法、散化地理坐标方法和卫星拓扑 相关的方法。

本发明实施例中的卫星网络为低轨星座网络，因此解决卫星网络拓扑变化 可以采用散化地理坐标的方法，将每个卫星节点设置一个唯一的编号，根据该 唯一编号设定网络地址，在路由和重路由实施时，可以采用该网络地址进行。 卫星MPLS网络中，由于卫星之间通信时延大，卫星上资源有限，在进行重路由 时，需要充分考虑到卫星MPLS网络的特殊性。

本发明针对卫星MPLS网络中，由于卫星之间通信时延大，星上资源有限， 在进行重路由时，本发明在基于最小干扰算法的路由算法基础上，根据路由计 算时所得到的路由信息，按照业务流的不同性质，对不同业务流划分不同的优 先级，进行不同的重路由策略。

本发明实施例中业务种类和负担的增加要求卫星网络提供更可靠更快捷的 服务，而增加的业务中许多是有QoS需求的。这些QoS需求来自用户业务的服务 需要，比如实时性很强的业务对时延的要求比较高，有些通信业务对时延抖动 比较敏感，有一些业务对带宽要求比较高，还有一些业务则同时对这时延、时 延抖动和带宽都有要求。如何满足不同用户的不同QoS需求是一个具有挑战性的 问题。现在假设对这几种不同的QoS需求，设定不同的参数，从而得到不同权重 所组成一个综合函数。例如：可以将由时延和带宽组成的函数称为优先级函数， 其优先级函数，其公式表示为：

其中，f代表优先级，α₁表示时延的权重，D表示为链路的传输时延，D_min为当前卫星网络中所有链路的最小时延，α₂表示带宽权重，为链路的剩余带 宽，为当前卫星网络中所有链路剩余容量的最大值，考虑现在大多数业务 的QoS需求，对时延的要求和对带宽的要求差不多，因此假设α₁=0.5，α₂=0.5。

本发明最小干扰算法一般分为两个阶段进行处理，分别为初始链路权重计 算和链路动态调整。初始权重计算依赖于链路权重定义，链路动态调整依赖于 链路关键集。其中，在链路调整阶段，依据当前请求的源-目标节点对以及链路 关键集，通过K最短路径调整链路权重。最小干扰算法的基本步骤如下：

第一步：根据链路权重函数，初始化网络中的所有链路；

第二步：根据链路关键集函数，求出关键集；

第三步：根据所求的链路关键集，对源-目标节点求出K-最短路径；

第四步：按照链路调整函数，调整关键集中的链路权重；

第五步：用最短路径算法，求出最终通信的LSP。

由上面的步骤看出，对于最小干扰算法，其中一个较为明显的劣势在于其 计算K-最短路径时的复杂计算。为了充分利用K-最短路径时计算的结果，本发 明提出的重路由策略，可以使得这些计算更有价值。

由于最小干扰算法算出来的备份路径只是针对关键链路进行保护的，并未 对工作路径上非关键链路进行保护，所以本发明的重路由算法在结合最小干扰 算法的同时分两种情况进行考虑：

第一种情况：当故障发生在关键链路上，如图1所示。

图1是故障发生在关键链路上的重路由策略示意图。设定链路重复率β，定 义链路重复率β为两次求得的LSP中，相同链路与总路径的比值。用公式表示为

β=∑Link_i/max(∑Link1,∑Link2)

其中，Link_i为Link1和Link2中相同的链路，Link1和Link2为两次最短路径所 求得的链路，∑Link_i、∑Link1和∑Link2分别为两次所求相同链路的数目和两次 所求的最短路径数之和。故障发生时，根据业务流的优先级，按照表1选择重路 由保护路径，其中λ为级别参数，当0≤β<λ，则表示低优先级，当β≥λ，则 表示高优先级。

表1

第二种情况：当故障发生在非关键链路上，如图2所示。

图2是故障发生在非关键链路上的重路由策略示意图。由于网络条件限制， 在求得K最短路径时，常常无法得到对工作路径的每一条链路的备份路径，这时 在进行第一类重路由时，由于不存在备份路径，就会表现为重路由失败。为了 提高重路由能力，将出现重路由失败时，进行第二类重路由，即在线计算。具 体方法是，当工作路径上非关键路径发生故障时且没有备份路径，那么把发生 故障的节点或链路前一个节点当作源节点，即Source点，故障节点或链路的下一 个节点作为目的节点，即C点，计算时不再使用最小干扰算法，而是直接根据最 短路径算法，在线直接算出到达目的节点的可行路由，然后采用RSVP-TE或者 LDP-CR协议进行重新分发标签。完成之后，就可以继续通信。通过第二类重路 由，可以解决当采用第一类重路由策略时，对于未备份的链路无法进行重路由 的问题。

本发明定义了优先级函数，所以当发生第二种情况时，当源节点根据最短 路径算法计算出的备份路径上已有另外业务流正在进行传输，这时就需要查看 剩余带宽是否满足工作路径上的业务流需求，如果满足剩余带宽需求，那就直 接切换过去，进行传输；如果剩余带宽不满足传输工作路径上的业务流，那么 这时看备份路径上已有的业务流和工作路径上业务流的优先级，如果备份路径 上已有的业务流比工作路径上业务流的优先级高，那么宣布重路由失败；如果 备份路径上已有的业务流比工作路径上业务流的优先级低，那么工作路径上业 务流就抢占备份路径上已有的业务流的带宽，进行传输，等传输完成或者工作 路径上的故障恢复了，再继续传输备份路径上原有有的业务流。这样对高优先 级数据流传输起到了较好的保护作用，获得了更好的QoS保证。

在具体实施时，可将此策略放在卫星节点上，在数据发送的过程中，通过 路由与星历信息获取卫星所经过节点信息，并进行上述计算，完成卫星MPLS网 络的重路由。

本发明针对以上卫星通信中出现的问题提出基于优先级机制的快速重路由 策略，有效的利用了路由时的计算，避免了重路由时的重新计算，缩短故障修 复时间，缓解了星上资源紧张的情况，实现对工作路径上的所有链路进行保护。

以上所述，此为本发明较佳的具体实施方式，但本发明的保护范围并不局 限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本 发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护 范围之内。