低轨星座网络中的拥塞避免路由方法

摘要

一种低轨星座网络中的拥塞避免路由方法，包括如下步骤：步骤1：采用数据驱动的路由计算机制，仅在有数据要发送低轨卫星星座网络中的卫星节点上计算可用路径；步骤2：采用主动发现与自动探测相结合的状态通知机制收集链路状态信息，在发出业务报文的同时发出探测报文，并在所述探测报文中携带路径信息，拥塞链路的两端节点向邻居发送状态通知消息；步骤3：源端卫星节点发出业务报文时，通过利用可用路径的状态信息从可用路径集合中选择最佳路径；步骤4：利用所述最佳路径发送业务报文，路径上发生拥塞或故障时进行重路由处理。能够避免潜在的网络级联拥塞，能够解决基于局部网络状态信息选路引发的局部优化问题。

说明书

技术领域

本发明涉及低轨卫星星座网络技术领域，也涉及重路由技术领域，具体涉及一种低轨星座网络中的拥塞避免路由方法。

背景技术

低轨(LEO)卫星星座网络由于卫星轨道高度较低，传输时延和星地链路损耗更小，在天地一体化网络构建中具有重要作用。但由于低轨(LEO)卫星星座中卫星运行速度快，轨道周期短，网络中通过星际链路(ISL)形成的拓扑结构具有高度的动态性，这对网络路由方法带来极大挑战。随着网络中业务量的大幅增加，卫星星座网络中卫星部署的均匀性与地面用户的业务需求非均匀性之间的矛盾越来越突出。

传统最短路径的路由方法由于仅考虑链路时延或跳数，不考虑流量分布，因此会加剧上述矛盾。致使卫星星座网络在为用户提供服务时，星际链路之间的数据负载量存在很大差异，有些链路负载很大，甚至出现拥塞，而有些链路上却少有数据传输，严重影响了用户的服务质量。因此需要使流量在不同链路上均衡分布，并随着卫星星座网络流量变化及时调整路径，即需要提出能够避免链路拥塞、使流量负载均衡分布的路由方法。

现有卫星星座网络的负载均衡路由方法为了减小路径选择开销，通常采用分布式方法，并以卫星节点附近的局部链路状态信息为依据确定最佳路径，容易引发卫星星座网络中的级联拥塞，而且可能使卫星星座网络趋于不稳定，严重影响卫星星座网络性能。

发明内容

为解决上述问题，本发明提供了一种低轨星座网络中的拥塞避免路由方法，通过利用卫星星座网络中的路径状态信息从可用路径集合中选择最佳路径，避免潜在的网络级联拥塞，能够解决基于局部网络状态信息选路引发的局部优化问题。同时，结合卫星星座网络拓扑的可预见性计算可用路径集合，利用主被动相结合的状态通知机制，能够减小路径计算开销，兼顾链路状态获取的及时性。

为了克服现有技术中的不足，本发明提供了一种低轨星座网络中的拥塞避免路由方法的解决方案，具体如下：

一种低轨星座网络中的拥塞避免路由方法，包括如下步骤：

步骤1：采用数据驱动的路由计算机制，仅在有数据要发送低轨卫星星座网络中的卫星节点上计算可用路径；

步骤2：采用主动发现与自动探测相结合的状态通知机制收集链路状态信息，在发出业务报文的同时发出探测报文，并在所述探测报文中携带路径信息，拥塞链路的两端节点向邻居发送状态通知消息；

步骤3：源端卫星节点发出业务报文时，通过利用可用路径的状态信息从可用路径集合中选择最佳路径，即要求最佳路径上的所有链路上的卫星节点中的报文队列的长度均不大于拥塞门限；步骤4：利用所述最佳路径发送业务报文，路径上发生拥塞或故障时进行重路由处理。

进一步的，所述利用所述最佳路径发送报文的方法，包括：

步骤5-1：利用所述最佳路径发送报文，如探测发现最佳路径上的链路发生拥塞或故障，则为报文重新选路；

步骤5-2：重新选路的过程与所述最佳路径的选择过程相同。

进一步的，所述重新选路过程与最佳路径的选择过程相同。

进一步的，所述卫星星座中的链路状态，包括拥塞、正常和故障三种状态：

初始运行时所有链路处于正常状态，当某报文队列的长度大于拥塞门限时，该链路进入拥塞状态；当某报文队列的长度小于恢复门限时，链路返回正常状态；且拥塞门限大于恢复门限；当链路出现故障时，进入故障状态；故障恢复时，返回正常状态；

所述链路拥塞状态表记录网络中发生拥塞或故障的链路信息，初始状态时该表为空，当收到状态通知时根据通知信息增加或删除该表对应的表项。

进一步的，所述采用数据驱动的路由计算机制，仅在有数据要发送的低轨卫星星座网络中的卫星节点上计算可用路径的方法，包括：

在所述低轨卫星星座运行的一个时间片内星座网络拓扑结构不发生变化，根据预先可知的星座网络拓扑计算出K条可用路径组成可用路径集合，该路径集合中的路径满足路径时延小于预设的时延门限的约束条件，计算得到的路径集合存储于所述卫星节点的路由表中，并在该时间片内无需再次计算路径集合，其中，K为正整数。

进一步的，所述采用自动探测与主动发现相结合的状态通知机制收集链路状态信息的方法，包括：

自动探测；

主动发现。

进一步的，所述主动发现的方法，包括：

步骤3-1：源端卫星节点在发送业务报文的同时，沿最佳可用路径向目的端卫星节点发送探测报文；

步骤3-2：一旦在可用路径上得知某链路已经处于拥塞状态，则立即返回源端卫星节点告知状态，使其重新选择路径，同时通知该可用路径上所经过的各沿途的卫星节点；

步骤3-3：并把拥塞的路径状态信息存储于源端节点和被通知的中间节点的预设的链路拥塞状态表中。

进一步的，所述自动探测的方法，包括：

步骤1-1：初始的时候所述卫星星座网络中的卫星节点把链路状态设置为正常状态；

步骤1-2：接着所述卫星星座网络中的卫星节点就检测其内部设置的报文队列的长度；

步骤1-3：所述卫星星座网络中的卫星节点当监测到报文队列的长度大于拥塞门限时，把链路状态设置为拥塞状态，并仅向除该拥塞链路另一端节点之外的其它相邻的卫星节点发送拥塞通知消息；

步骤1-4：所述卫星星座网络中的卫星节点又监测到报文队列的长度不大于拥塞门限时，即恢复可用状态时，把链路状态恢复为正常状态，并仅向除该拥塞链路另一端节点的其它相邻的卫星节点发送恢复正常状态的通知消息。

进一步的，所述自动探测的方法，还包括：

步骤2-1：所述卫星星座网络中的相邻卫星节点通过互相发送周期性的心跳报文来维持连接状态；

步骤2-2：一旦某个卫星节点发送的心跳报文的响应时间超过预设的门限时间，则判断其相邻的卫星节点故障，把链路状态设置为故障状态，并仅向其相邻的卫星节点发送故障通知消息；

步骤2-3：一旦某个卫星节点发送的心跳报文的响应时间又未超过预设的门限时间，则判断其相邻的卫星节点恢复正常，即恢复可用状态时，把链路状态恢复为正常状态，并仅向其相邻的卫星节点发送恢复正常状态的消息。

进一步的，所述最佳路径的选择过程为：

步骤4-1：对可用路径集合中的可用路径按照路径时延升序排序；

步骤4-2：按照所述排序的序列依次对各个可用路径通过查询链路拥塞状态表来检查可用路径上的链路状态是否为拥塞或故障，如果存在这样的链路，则该可用路径不满足条件，不能被选为最佳路径；

步骤4-3：直至检查到可用路径上的链路状态未出现拥塞和故障，就把该可用路径作为最佳路径；

步骤4-4：若所有可用路径上的链路状态都出现拥塞或故障，就选择作为最短路径的所述排序在最前的那个可用路径作为最佳路径。

本发明的有益效果为：

通过利用路径上的拥塞状态信息从可用路径集合中选择最佳路径，可避免潜在的网络级联拥塞，解决基于局部网络状态信息选路引发的局部优化问题，并可使流量负载均衡分布于卫星星座网络中，减小卫星星座网络的丢包率和报文排队时延，提高网络传输吞吐量；结合卫星星座网络拓扑的可预见性计算可用路径集合，充分利用卫星星座网络拓扑特点，可减小路径计算开销；通过自动探测与主动发现相结合的状态通知机制，能够减小路径选择开销，兼顾链路状态获取的及时性。

附图说明

图1为本发明的低轨卫星星座网络的整体拓扑示意图。

图2是本发明的链路拥塞状态表结构示意图；

图3是本发明的链路状态信息表的结构示意图；

图4是本发明的低轨星座网络中的拥塞避免路由方法的规划方法的整体流程图。

图5是本发明的所述利用所述最佳路径发送报文的方法的流程图。

图6是本发明的所述主动发现的方法的流程图。

图7是本发明的所述自动探测的方法的部分流程图。

图8是本发明的所述自动探测的方法的另一部分流程图。

图9是本发明的所述最佳路径的选择过程的流程图。

具体实施方式

现有卫星星座网络负载均衡路由方法为了减小路径选择开销，通常采用分布式方法，并以卫星节点附近的局部链路状态信息为依据确定最佳路径，容易引发网络中的级联拥塞，而且可能使卫星星座网络趋于不稳定，严重影响网络性能。因此，需要一种能够充分考虑全局链路状态和负载分布的、开销小、运行稳定、网络性能有保障的负载均衡卫星星座网络路由方法。

下面将结合附图和实施例对本发明做进一步地说明。

如图1-图9所示，低轨星座网络中的拥塞避免路由方法的规划方法，包括如下步骤：

步骤1：采用数据驱动的路由计算机制，仅在有数据要发送低轨卫星星座网络中的卫星节点上计算可用路径；

所述采用数据驱动的路由计算机制，仅在有数据要发送的低轨卫星星座网络中的卫星节点上计算可用路径的方法，包括：

在所述低轨卫星星座运行的一个时间片内假设星座网络拓扑结构中的卫星节点之间的相对位置不发生变化，根据预先可知的星座网络拓扑计算出K条可用路径组成可用路径集合，该路径集合中的路径满足路径时延小于预设的时延门限的约束条件，计算得到的路径集合存储于所述卫星节点的路由表中，并在该时间片内无需再次计算路径集合，其中，K为正整数。如图1所示，星座网络拓扑结构中包括沿着不同的极轨道运转的卫星节点，两个卫星节点之间的数据传输路径可能由多条卫星间链路组成，同一轨道上的卫星节点之间的链路就是轨道内链路，不同轨道上的卫星节点之间的链路就是轨道间链路，虚线箭头代表卫星在轨道上的轨道运行方向，星座中卫星运行方向相反的两个轨道之间的间隔就是缝隙，缝隙两边的卫星之间的链路较难维持。划分时间片的方式是星座网络拓扑控制的常用方法，用来屏蔽星座网络的动态性，典型方法为快照方法，每个快照内假设星座拓扑固定不变。

星座网络拓扑虽然具有动态性，但卫星之间的相对位置固定，且拓扑变化具有规律性，因此可以利用星座的运行时间，以及预先可知的节点之间的连接关系，利用地面网络常用的K-最短路径方法计算出K条可用路径。

其中每条路径的时延即为组成该路径的所有链路的时延总和，为了对数据传输的路径长度进行限制，以满足业务需求，同时节省信道资源的使用，要求路径时延小于预设的时延门限，比如国际标准中通常要求话音业务端到端时延远小于1s，如果网络中传输有话音业务，就可以设置该时延门限为200ms。

采用数据驱动的路由计算机制是一种按需的路由计算方式，且每个时间片仅计算一次，这种方法可大幅降低星上节点的计算量，降低星上能量消耗，延长星座系统寿命。

步骤2：采用主动发现与自动探测相结合的状态通知机制收集链路状态信息，在发出业务报文的同时发出探测报文，并在所述探测报文中携带路径信息，拥塞链路的两端节点向邻居发送状态通知消息；链路状态信息通常设置在链路状态信息表内。

所述采用主动发现与自动探测相结合的状态通知机制收集链路状态信息的方法，包括：

自动探测；

所述自动探测的方法，包括：

步骤1-1：初始的时候所述卫星星座网络中的卫星节点把链路状态设置为正常状态；

步骤1-2：接着所述卫星星座网络中的卫星节点就检测其内部设置的报文队列的长度；

步骤1-3：所述卫星星座网络中的卫星节点当监测到报文队列的长度大于拥塞门限时，把链路状态设置为拥塞状态，并仅向除该拥塞链路另一端节点之外的其它相邻的卫星节点发送拥塞通知消息；

步骤1-4：所述卫星星座网络中的卫星节点又监测到报文队列的长度不大于拥塞门限时，即恢复可用状态时，把链路状态恢复为正常状态，并仅向除该拥塞链路另一端节点的其它相邻的卫星节点发送恢复正常状态的通知消息。

所述自动探测的方法，还包括：

步骤2-1：所述卫星星座网络中的相邻卫星节点通过互相发送周期性的心跳报文来维持连接状态；

步骤2-2：一旦某个卫星节点发送的心跳报文的响应时间超过预设的门限时间，则判断其相邻的卫星节点故障，把链路状态设置为故障状态，仍仅向其相邻的卫星节点发送故障通知消息；

步骤2-3：一旦某个卫星节点发送的心跳报文的响应时间又未超过预设的门限时间，则判断其相邻的卫星节点恢复正常，即恢复可用状态时，把链路状态恢复为正常状态，并仅向其相邻的卫星节点发送恢复正常状态的消息。

主动发现；

所述主动发现的方法，包括：

步骤3-1：源端卫星节点在发送业务报文的同时，沿前两条可用路径向目的端卫星节点发送探测报文；源端卫星节点是路径中首个发送报文的卫星节点，而目的端卫星节点是最末一个发送报文的卫星节点。

步骤3-2：一旦在可用路径上得知某链路已经处于拥塞状态(到达拥塞链路两端节点的相邻节点时即可得知该状态)，则立刻实时返回源端卫星节点告知状态，同时通知该可用路径上所经过的各沿途的卫星节点；

步骤3-3：并把拥塞的路径状态信息存储于源端节点和被通知的中间节点的预设的链路拥塞状态表中。

如果所探测的两条可用路径存在拥塞状态，则启动新一条可用路径的探测，同时维持对原有的两条可用路径的探测，一旦原有的两条可用路径中有恢复可用状态的路径，则取消对新的可用路径的探测，以收缩探测范围维持较低的开销。

在星座网络中，由于星间链路带宽有限，时延较长，类似地面的链路状态交互机制会带来很大开销，而且状态信息的时滞，会使路由更新收敛更慢，容易导致路由环路等故障。本方法采用自动探测与主动发现相结合的状态通知机制，一方面，主动发现是一种按需的状态交换机制，而且当探测报文发现拥塞后立即返回源端节点，可以避免因探测报文本身丢失或在节点长时间排队而导致状态收集失败或不及时；另一方面，自动探测能够使算法及时获知链路状态，对突发的拥塞或故障做出及时响应，且探测到拥塞后仅向相邻节点发送状态信息，该机制与常用的链路状态广播机制相比可以大幅降低状态交互产生的信令开销，因此，该方法能够克服地面链路状态交互机制在星座网络中存在的问题，

步骤3：源端卫星节点发出业务报文时，通过利用可用路径的状态信息从可用路径集合中选择最佳路径，即要求最佳路径上的所有链路上的卫星节点中的报文队列的长度均不大于拥塞门限；

所述最佳路径的选择过程为：

步骤4-1：对可用路径集合中的可用路径按照路径时延升序排序；

步骤4-2：按照所述排序的序列依次对各个可用路径通过查询链路拥塞状态表来检查可用路径上的链路状态是否为拥塞或故障，如果存在这样的链路，则该可用路径不满足条件，不能被选为最佳路径；

步骤4-3：直至检查到可用路径上的链路状态未出现拥塞和故障，就把该可用路径作为最佳路径；

步骤4-4：若所有可用路径上的链路状态都出现拥塞或故障，就选择作为最短路径的所述排序在最前的那个可用路径作为最佳路径。

步骤4：利用所述最佳路径发送报文，路径上发生拥塞或故障时进行重路由处理。

所述利用所述最佳路径发送报文的方法，包括：

步骤5-1：利用所述最佳路径发送报文，如探测发现最佳路径上的链路发生拥塞或故障，则为报文重新选路；

步骤5-2：重新选路的过程与所述最佳路径的选择过程相同。

最佳路径选择过程中，要求最佳路径上的所有链路上的卫星节点中的报文队列占比均不大于拥塞门限，这比仅使用本地链路状态的星座网络分布式路由方法更具全局性，使得选出的路径更接近全局最优路径，降低了网络中发生级联拥塞的可能。

所述重新选路过程与最佳路径的选择过程相同。

所述卫星星座中的链路状态，包括拥塞、正常和故障三种状态：

初始运行时所有链路处于正常状态，当某报文队列的长度大于拥塞门限时，该链路进入拥塞状态；当某报文队列的长度小于恢复门限时，链路返回正常状态；且拥塞门限大于恢复门限，两个门限值可根据链路流量负载自适应调整；当链路出现故障时，进入故障状态；故障恢复时，返回正常状态。

所述链路拥塞状态表记录网络中发生拥塞或故障的链路信息，初始状态时该表为空，当收到状态通知时根据通知信息增加或删除该表对应的表项。

以下对门限值的设置做出说明：

假设链路的最大队列长度为Q

L

δ＝0:这意味着在卫星w处，q(t)＝Q

D/δ>1:在节点w处的队列在收到来自s的报文之前就已经溢出了。因此拥塞概率也是1。

D/δ<1:节点w处的队列在收到来自s的报文之前溢出，此时，拥塞概率为D/δ。

因此，拥塞概率p可以设置如下：

p＝min(1,D/δ)

而拥塞门限Q

Q

也就是说，当路径上的拥塞概率比较小时，拥塞门限Q

以上以用实施例说明的方式对本发明作了描述，本领域的技术人员应当理解，本公开不限于以上描述的实施例，在不偏离本发明的范围的情况下，可以做出各种变化、改变和替换。