兼顾控制流量的软件定义卫星网络路由策略

费长江， 赵宝康， 虞万荣， 吴纯青

(国防科技大学计算机学院, 长沙 410073)

卫星网络具有覆盖范围广、不受地面条件约束和抗毁性强等显著优势，受到世界各国的广泛重视。然而，现有的卫星网络一般定制专用、各成体系，呈现出“烟囱林立”的特点，难以实现网络统一融合、资源动态管理和功能灵活配置。

软件定义卫星网络(Software Defined Satellite Networks，SDSN)采用一种创新的方式来构建卫星网络，受到了国内外的广泛关注[1-4]。其中，谷歌[5]、休斯[6]等国际巨头对SDSN开展了研究，欧洲进行了相关的VITAL研究项目[7-9]。SDSN采用了软件定义网络(Software Defined Networks,SDN)[10]的主要思想，包括控制平面和数据平面分离，网络视图和控制功能的逻辑集中以及网络可编程控制等。因此，SDSN能够通过统一的控制平面实现卫星网络之间以及与地面网络的融合；根据用户和业务的需求以及网络状态灵活动态地分配资源；通过在应用层进行应用程序更新或添加，简单、快速地更新或扩展网络功能。

与对地静止轨道(Geostationary Earth Orbit，GEO)卫星网络相比，低地球轨道(Low Earth Orbit，LEO)和中地球轨道(Medium Earth Orbit，MEO)卫星网络由于能为多媒体业务提供较低的时延和较高的带宽，已经成为关注的焦点。因此，本文关注基于LEO/MEO的SDSN。

在SDSN中，控制报文和数据报文同时在网络中传输，相互干扰，共同抢占星间链路资源。SDSN中的控制报文主要将网络状态从卫星传输到网络操作控制中心(Network Operation and Control Center，NOCC)，将控制规则从NOCC传输到卫星，对应的控制流量具有以下显著的特点：

1) 高优先级。控制报文实时可靠传输是保证网络稳定高效运行的基础。因此，控制报文通常具有较高优先级，甚至最高优先级。

2) 海量。当前，卫星网络日益与互联网、蜂窝网、物联网(Internet of Things，IoT)等地面网络融合，形成天地一体化的网络。例如，在与IoT融合方面，预计到2025年，仅卫星网络连接的M2M/IoT网络数量就将达到596万个[11]。SDSN为了采集这些网络的状态并进行控制，将产生海量的控制报文。

3) 动态。一方面，为了对网络进行实时动态地控制，SDSN需要频繁地进行网络状态采集和控制规则上注；另一方面，由于卫星网络拓扑动态变化，控制报文的路由需要进行频繁地更新，尤其是当NOCC连接的过顶卫星(以下简称NOCC过顶卫星)切换时，控制报文的路由将进行大范围地更新。这两方面原因导致网络中控制流量的分布呈现出明显的动态性。

高优先级、海量、动态的控制流量将大量抢占星间链路资源，造成链路拥塞，对数据报文传输产生极大的干扰。

为了减少控制流量对数据报文传输的干扰，在保证控制报文实时可靠传输的基础上，优化数据报文传输，本文提出了一种数据流退让路由(Data Flow Retreat Routing，DFRR)策略。DFRR路由策略的主要思路如下：第一，在为数据报文计算路由时，应减少选择控制流量较大的链路。为此，DFRR将链路上控制流量大小作为影响链路代价的一个因素，使得控制流量越大，链路代价也越大。第二，由于NOCC过顶卫星附近会汇聚大量的控制流量，当过顶卫星切换时，新过顶卫星附近将新增大量的控制流量，很可能造成链路拥塞。对此，DFRR在NOCC过顶卫星切换之前，预测可能发生拥塞的链路，并选出这些链路上部分数据流进行重路由，从而避免拥塞。

为了评估DFRR路由策略的性能，本文基于笔者团队开发的SDSN研究平台OpenSatNet[12]，在铱星系统中对DFRR进行了仿真实现。实验结果表明，DFRR能够有效减少网络中的链路拥塞，以及控制报文和数据报文的分组丢失。

本文首先介绍了SDSN及其路由，其次提出了数据流退让路由策略DFRR，包括兼顾控制流量的链路代价设计，以及在NOCC过顶卫星切换时的链路拥塞避免算法，最后对DFRR进行了性能评估。

1 软件定义卫星网络及其路由

1.1 软件定义卫星网络

SDSN是指基于软件定义思想构造卫星网络，通过设计开放、标准的数据平面接口支撑数据与控制平面解耦，实现网络态势与控制的逻辑集中，进而支持网络业务定制与应用创新。与SDN架构[13]类似，SDSN的架构如图1所示，包括基础设施层、控制层和应用层。基础设施层主要由卫星构成，除了进行数据转发外，还需要负责用户接入、波束调整以及软件定义无线电(Software Defined Radio，SDR)相关的配置；控制层位于NOCC，通过网络状态收集，同时结合卫星轨道数据计算等形成全局网络视图，完成卫星网络路由计算、网络协议配置等各项控制任务；应用层是位于控制层之上的一个抽象层次，通过在应用层开发不同功能的应用程序，可以实现负载均衡、服务质量等不同的控制功能。

SDSN基本的控制过程为：控制层采集基础设施层的网络状态，形成全局网络视图；根据应用层中应用程序确定的控制功能进行控制决策；控制决策以控制规则的形式发送给基础设施层，基础设施层对相关配置进行更新。控制报文主要在基础设施层和控制层，即卫星和NOCC之间传递网络状态和控制规则，如图2所示。

图1 SDSN架构Fig.1 SDSN architecture

1.2 软件定义卫星网络路由

目前，SDSN的研究兴起不久，在路由方面开展了少量初步的研究。传统卫星网络的路由算法主要分为静态路由算法[14-16]和动态路由算法两类[17-20]。静态路由算法利用卫星网络拓扑可预测性和周期性的特点静态计算路由，但不能应对不可预测拓扑变化(如卫星节点或星间链路失效等)；动态路由算法根据网络状态动态、分布式地计算路由，但由于卫星网络大尺度和拓扑动态变化的特点，存在收敛时间长和信令开销大的问题。

图2 SDSN控制报文传输Fig.2 Control message transmission in SDSN

学者们从服务质量[21-22]、流量工程[23]、多路径路由[24-25]和动态响应路由[25-26]等方面对SDSN的路由进行了研究。与传统卫星网络路由算法相比，SDSN在路由方面具有明显的优势，能够很好地实现动态路由[8]。SDSN采用动态、集中式路由的方式，路由在NOCC集中计算，然后通过相应的控制规则上注到卫星。由于NOCC拥有实时的全局网络视图，路由计算能够综合各种因素进行优化，实现细粒度路由，在保证业务服务质量的同时，最大化网络资源利用率。

2 数据流退让路由策略

2.1 兼顾控制流量的链路代价

为了保证控制报文实时可靠地传输，本文设置控制报文的优先级高于数据报文。控制报文优先级较高，会优先抢占星间链路资源。当一条链路上控制流量较大时，数据报文传输会受到一定程度的影响，尤其是链路负载较大时。而反过来，虽然设置为高优先级能在很大程度上保证控制报文的传输，但对于控制流量较大的链路，如果链路负载较大，控制报文的传输仍然会受到一定的影响。因此，本文通过设计兼顾控制流量的链路代价，在计算数据报文路由时，减少选择控制流量较大的链路。

SDSN空间段t时刻的拓扑可以表示为无向图G(t)=(V,E(t))，其中V={v1,v2,…,vN}为节点集合，即所有的卫星，下标N为网络中卫星的数目，E(t)为t时刻网络中链路(vi,vj)(i,j=1,2,…,N，i≠j)的集合。链路是无向的，即(vi,vj)=(vj,vi)。根据一定的代价标准，每条链路有相应的链路代价ci,j(t)。

通常情况下，链路代价主要考虑链路的时延和剩余带宽，时延越小，剩余带宽越大，链路代价越小。笔者在链路代价计算时同时考虑链路上控制流量的大小，构建兼顾控制流量的链路代价，计算公式为

(1)

图3 不同时刻控制流量分布示意图Fig.3 Sketch map of control traffic distributions at different time points

2.2 链路拥塞避免算法

由于NOCC过顶卫星附近的链路汇聚了大量的控制流量，当过顶卫星切换时，控制报文路由更新，新过顶卫星附近链路上的控制流量会急剧增加(见图3)，很可能出现链路拥塞。因此，本文在NOCC过顶卫星切换之前，预测切换后可能发生拥塞的链路，对这些链路上的部分数据流进行重路由，从而避免链路拥塞。

2.2.1 假定条件

在描述链路拥塞避免算法之前，先给出算法的假定条件，它们是算法正确运行的前提。

假定1)：控制报文路由采用静态路由。

动态路由算法需要动态获取网络状态，通常分布式地计算路由。一方面，网络状态本身需要通过控制报文传输；另一方面，动态路由算法收敛时间长，不能保证控制报文路由及时更新。而静态路由不需要动态获取网络状态，通常采用离线的方式计算路由，更加适用于控制报文路由。因此，假定1)是合理的。

假定2)：控制报文路由切换的时间可以忽略不计。

由于静态路由计算的路由通常提前存储在卫星节点或者在路由切换前提前发送给卫星节点，路由切换只需要对转发规则进行更新。同时，未来星载交换机将具有强大的处理能力。因此，假定2)也是合理的。根据假定2)，可以认为控制报文路由切换前后，每颗卫星和NOCC之间的控制流量大小不变，所有数据流量大小和路由均不变，空间段网络拓扑不变，各链路的时延不变。

2.2.2 拥塞链路预测

(2)

即当链路上流量(包括控制流量和数据流量)需要的带宽大于si,jBi,j时(si,j为安全系数)，则认为该链路将会出现拥塞。由于链路上的流量大小存在一定的波动性，增加了安全系数0

(3)

因此，根据链路拥塞判定条件，如果满足

(4)

即

(5)

则认为链路(vi,vj)在NOCC过顶卫星切换导致控制报文路由切换后会发生拥塞。

图4 拥塞链路预测示例Fig.4 An example of congestion link prediction

2.2.3 重路由数据流选择

对于可能发生拥塞的链路，需要提前选择部分数据流进行重路由。为了合理地选择需要重路由的数据流，首先定义数据流的速率-满意度函数。

从用户体验角度，对于每条数据流，都存在数据流传输速率到用户体验的服务满意度之间的映射关系。笔者将这种映射关系量化，定义为速率-满意度函数。

定义1速率-满意度函数。假设网络中有M种业务，数据流l属于其中一种业务m(m=1,2,…,M)，其传输速率bl与用户体验的服务满意度Sl之间存在某种确定的映射关系，即

Sl=fm(bl)

(6)

将这种映射关系称为数据流l的速率-满意度函数，函数值Sl称为数据流l的服务满意度。

同一种业务的不同数据流具有相同的速率-满意度函数，而不同业务的数据流具有不同的速率-满意度函数。

下面证明重路由数据流选择问题是NP完全问题。

定理1重路由数据流选择问题是NP完全问题。

证明已知均分问题为NP完全问题。均分问题可以描述为：已知A={1,2,…,L}，对∀l∈A，Sl>0，求是否存在A′⊆A，使得

(7)

(8)

(9)

直到求得S*最小值为止。

当限制对∀l∈C

(10)

(11)

(12)

(13)

(14)

即

(15)

重路由数据流选择问题变为均分问题。因此重路由数据流选择问题是NP完全问题。

证毕

为了求解重路由数据流选择问题，进一步分析其最优解的特性。

证明如果上述最优子结构特性不成立，设(z2,z3,…,zLi,j)(zl∈{0,1})是该子问题的一个最优解，而(y2,y3,…,yLi,j)不是该子问题的最优解。由此可知

(16)

(17)

因此

(18)

(19)

证毕

因此，重路由数据流选择问题可以采用动态规划法进行求解，算法的伪代码如下：

算法1重路由数据流选择

输出：y1,y2,…,yLi,j。

1H0={(0,0)}

2 for eachl∈{1,2,…,Li,j-1} do

5 end for

6 (B1,Q1)= the last step point inHLi,j-1

8Q=max{Q1,Q2}

9 ifQ2>Q1then

10yLi,j=0

11 else

12yLi,j=1

13 end if

14 Backtrack to calculateyLi,j-1,yLi,j-2,…,y1

2.2.4 数据流重路由

(20)

(21)

(22)

(23)

链路拥塞避免算法的伪代码如下：

算法2链路拥塞避免算法

输出：F。

初始化：F=∅，G=∅。

1/*拥塞链路预测*/

6 else

8 end if

9 end for

12G=G∪(vi,vj)

13 end if

14 end for

15 /*重路由数据流选择*/

16 whileG≠∅ do

17 for each data flowlon the first link (vi,vj) inGdo

18m=DetectType(l)

20 end for

23G=G{(vi,vj)}

24 UpdateG(F)

25 end while

26 returnF

函数UpdateG()更新G的具体操作是：G中的链路如果包含F中的数据流，则判断删除这些数据流后链路是否仍然拥塞。如果不拥塞，则从G中删除该链路。

3 实验评估

3.1 实验场景与参数设置

为了分析DFRR路由策略对网络性能的影响，在笔者团队开发的SDSN研究平台OpenSatNet上对DFRR进行了仿真实现。OpenSatNet是一个轻量级的平台，可以在个人电脑上模拟整个卫星网络。实验中OpenSatNet运行在笔记本电脑(Core i7处理器，8 GB内存)Ubuntu 14.04 LTS虚拟机中。实验场景由典型的LEO卫星网络铱星系统、1个地面站和1个NOCC组成。仿真界面如图5所示。

实验参数设置如表1所示。星间链路带宽为1 Mbit/s，星地链路带宽为10 Mbit/s。地面站和NOCC均位于北京。每颗卫星与NOCC之间存在一条大小为20 Kbit/s的恒定速率控制流；卫星之间随机分布100条数据流，数据流传输速率随机产生。数据流平均传输速率的不同反映了网络负载的不同。由于主要从控制报文和数据报文总体的传输性能方面进行评估，而不是具体控制流和数据流的传输性能。因此，为了简化起见，设置所有数据流类型相同，具有相同的速率-满意度函数。

图5 仿真界面Fig.5 Emulation interface

表1 实验参数设置Table 1 Experiment parameter setting

与DFRR对比的基本路由策略在计算数据报文路由时，其链路代价仅考虑链路的剩余带宽和时延，不考虑链路上控制流量的大小；在NOCC过顶卫星切换时，不做任何操作。该基本路由策略记为NONE。NONE的链路代价计算公式为

链路代价参数对应的剩余带宽、时延和控制流量大小的单位分别为Kbit/s、ms和Kbit/s。控制报文路由采用快照路由算法[15]，快照路由算法是一种典型的静态路由。仿真时间为一个轨道周期。

3.2 实验结果与分析

DFRR路由策略尽量减少控制流量对数据报文传输的干扰，对网络中的链路拥塞进行了优化，在保证控制报文传输的基础上，优化数据报文传输。因此，主要从链路拥塞次数、丢包率和分组时延3个方面对DFRR的性能进行评估。其中，在丢包率和分组时延方面，同时对控制报文和数据报文进行了分析。

3.2.1 链路拥塞次数

链路拥塞次数统计仿真过程中，拥塞链路出现的次数，如图6所示。总体来说，在不同的数据流平均传输速率即不同的网络负载下，DFRR显著减少了网络中的链路拥塞次数，平均减少了57.63%。此外，还可以看出，随着网络负载的增大，NONE和DFRR的链路拥塞次数均大幅增加，但DFRR减少链路拥塞次数的数量变化不大(有少量增加)，减少的比例逐渐下降。例如，当数据流平均传输速率为50 Kbit/s时，链路拥塞减少111次，减少的比例为94.07%；而当数据流平均传输速率为100 Kbit/s时，链路拥塞减少287次，减少的比例为30.34%。这是由于：一方面，当网络负载较小时，链路拥塞主要是由控制报文路由切换引起，当网络负载较大时，链路拥塞在全网范围出现，而DFRR主要避免控制报文路由切换造成的链路拥塞；另一方面，当网络负载较小时，DFRR可以将拥塞链路上部分数据流重路由到剩余带宽较大的链路，而当网络负载较大时，总体上链路的剩余带宽减少，数据流重路由后仍然出现链路拥塞的概率增加。

图6 NONE与DFRR链路拥塞次数对比Fig.6 Comparison of link congestion times between NONE and DFRR

3.2.2 丢 包 率

DFRR在减少链路拥塞的同时直接减少了拥塞链路上的分组丢失。NONE和DFRR中控制报文和数据报文的丢包率对比如图7所示。控制报文的丢包率平均减少了46.89%，数据报文的丢包率平均减少了32.08%。控制报文丢包率减少的比例比数据报文高，这是因为DFRR避免的链路拥塞大多位于NOCC过顶卫星附近，所有的控制报文均要通过NOCC过顶卫星转发，而数据报文只有一部分会经过NOCC过顶卫星附近的拥塞链路。当DFRR重路由部分数据流减少链路拥塞时，几乎所有控制流的分组丢失都会减少，而只有部分数据流的分组丢失会减少。

图7 NONE与DFRR丢包率对比Fig.7 Comparison of packet loss rates between NONE and DFRR

此外，在DFRR中，仍有一定比例的分组丢失，这些分组丢失主要由3方面的原因造成：①除了控制报文路由切换导致NOCC过顶卫星附近出现链路拥塞外，在网络其余部分也可能出现链路拥塞；②数据流重路由后仍然可能出现链路拥塞；③网络拓扑动态变化会导致控制流和数据流重路由，在重路由过程中会出现分组丢失。

3.2.3 分组时延

NONE与DFRR中控制报文和数据报文的分组时延对比如图8所示。DFRR对分组时延的影响主要有3个方面：①DFRR减少链路拥塞，从而降低了NONE中经过拥塞链路分组的排队时延；②DFRR减少分组丢失的同时，使得部分原本丢失的报文被纳入分组时延统计中，这部分报文的分组时延一般比较大，从而可能增加平均分组时延；③当对数据流进行重路由时，为了绕开拥塞链路，通常会选择较长的路径，从而增加重路由数据流的分组时延。对于方面③，当网络中卫星数量和链路数量增加时，同一节点对之间有更多代价相近的替代路径，由此带来的重路由数据流分组时延增加会减小。可见，DFRR造成分组时延减小或增大取决于方面①和方面②、方面③作用的大小。

图8 NONE与DFRR分组时延对比Fig.8 Comparison of packet delays between NONE and DFRR

从实验结果可以看出，当网络负载较小(数据流平均传输速率小于70 Kbit/s)时，2种方法控制报文和数据报文的分组时延相差不大，DFRR的分组时延略大；当网络负载较大(数据流平均传输速率大于70 Kbit/s)时，DFRR的分组时延比NONE更小，方面①起主要作用。总体来说，DFRR中控制报文的分组时延减少了1.71%，数据报文的分组时延减少了7.50%。

4 结 论

1) 针对SDSN中海量、动态、高优先级的控制流量对数据报文传输产生极大干扰的问题，本文提出了一种DFRR策略。DFRR在计算数据报文路由时，将链路上的控制流量大小作为影响链路代价的一个因素，减少选择控制流量较大的链路；在NOCC过顶卫星切换导致控制流量分布发生较大变化之前，预测可能发生拥塞的链路，并选出链路上部分数据流进行重路由，从而避免拥塞。

2) 仿真实验结果表明：在不同的网络负载下，与未优化的基本路由策略相比，DFRR的链路拥塞次数平均减少了57.63%，控制报文和数据报文的丢包率分别平均减少了46.89%和32.08%，控制报文和数据报文的分组时延分别平均减少了1.71%和7.50%，从而验证了DFRR策略的有效性。