卫星网络具有覆盖范围广、不受地面条件约束和抗毁性强等显著优势，受到世界各国的广泛重视。然而，现有的卫星网络一般定制专用、各成体系，呈现出“烟囱林立”的特点，难以实现网络统一融合、资源动态管理和功能灵活配置。
软件定义卫星网络(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，通过网络状态收集，同时结合卫星轨道数据计算等形成全局网络视图，完成卫星网络路由计算、网络协议配置等各项控制任务；应用层是位于控制层之上的一个抽象层次，通过在应用层开发不同功能的应用程序，可以实现负载均衡、服务质量等不同的控制功能。

图 1 SDSN架构 Fig. 1 SDSN architecture

图选项

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

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

图选项

1.2 软件定义卫星网络路由 目前，SDSN的研究兴起不久，在路由方面开展了少量初步的研究。传统卫星网络的路由算法主要分为静态路由算法^[14-16]和动态路由算法两类^[17-20]。静态路由算法利用卫星网络拓扑可预测性和周期性的特点静态计算路由，但不能应对不可预测拓扑变化(如卫星节点或星间链路失效等)；动态路由算法根据网络状态动态、分布式地计算路由，但由于卫星网络大尺度和拓扑动态变化的特点，存在收敛时间长和信令开销大的问题。
****们从服务质量^[21-22]、流量工程^[23]、多路径路由^[24-25]和动态响应路由^[25-26]等方面对SDSN的路由进行了研究。与传统卫星网络路由算法相比，SDSN在路由方面具有明显的优势，能够很好地实现动态路由^[8]。SDSN采用动态、集中式路由的方式，路由在NOCC集中计算，然后通过相应的控制规则上注到卫星。由于NOCC拥有实时的全局网络视图，路由计算能够综合各种因素进行优化，实现细粒度路由，在保证业务服务质量的同时，最大化网络资源利用率。
2 数据流退让路由策略 2.1 兼顾控制流量的链路代价 为了保证控制报文实时可靠地传输，本文设置控制报文的优先级高于数据报文。控制报文优先级较高，会优先抢占星间链路资源。当一条链路上控制流量较大时，数据报文传输会受到一定程度的影响，尤其是链路负载较大时。而反过来，虽然设置为高优先级能在很大程度上保证控制报文的传输，但对于控制流量较大的链路，如果链路负载较大，控制报文的传输仍然会受到一定的影响。因此，本文通过设计兼顾控制流量的链路代价，在计算数据报文路由时，减少选择控制流量较大的链路。
SDSN空间段t时刻的拓扑可以表示为无向图G(t)=(V, E(t))，其中V={v₁, v₂, …, v_N}为节点集合，即所有的卫星，下标N为网络中卫星的数目，E(t)为t时刻网络中链路(v_i, v_j)(i, j=1, 2, …, N，i≠j)的集合。链路是无向的，即(v_i, v_j)= (v_j, v_i)。根据一定的代价标准，每条链路有相应的链路代价c_{i, j}(t)。
设t时刻链路(v_i, v_j)上的控制流量大小为b_{i, j}^C(t)。在不同时刻，网络中控制流量的分布如图 3所示，图中链路上的蓝色线条表示控制流量，蓝色线条的宽度表示控制流量的大小。因为所有的控制报文都要经过NOCC过顶卫星，所以过顶卫星附近的链路将汇聚大量的控制流量。

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

图选项

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

(1)

式中：b_{i, j}^R(t)和d_{i, j}(t)分别为链路(v_i, v_j)在t时刻的剩余带宽和时延；α₁>0、α₂>0、β>0和γ>0为对应的调节参数，α₂为一个很小的正数，以避免b_{i, j}^R(t)=0时计算出错。
可见，b_{i, j}^R(t)越小，d_{i, j}(t)越大，b_{i, j}^C(t)越大，链路代价越大，链路被选中的可能性越小。
2.2 链路拥塞避免算法 由于NOCC过顶卫星附近的链路汇聚了大量的控制流量，当过顶卫星切换时，控制报文路由更新，新过顶卫星附近链路上的控制流量会急剧增加(见图 3)，很可能出现链路拥塞。因此，本文在NOCC过顶卫星切换之前，预测切换后可能发生拥塞的链路，对这些链路上的部分数据流进行重路由，从而避免链路拥塞。

2.2.1 假定条件 在描述链路拥塞避免算法之前，先给出算法的假定条件，它们是算法正确运行的前提。
假定1)：控制报文路由采用静态路由。
动态路由算法需要动态获取网络状态，通常分布式地计算路由。一方面，网络状态本身需要通过控制报文传输；另一方面，动态路由算法收敛时间长，不能保证控制报文路由及时更新。而静态路由不需要动态获取网络状态，通常采用离线的方式计算路由，更加适用于控制报文路由。因此，假定1)是合理的。
假定2)：控制报文路由切换的时间可以忽略不计。
由于静态路由计算的路由通常提前存储在卫星节点或者在路由切换前提前发送给卫星节点，路由切换只需要对转发规则进行更新。同时，未来星载交换机将具有强大的处理能力。因此，假定2)也是合理的。根据假定2)，可以认为控制报文路由切换前后，每颗卫星和NOCC之间的控制流量大小不变，所有数据流量大小和路由均不变，空间段网络拓扑不变，各链路的时延不变。

2.2.2 拥塞链路预测 设链路(v_i, v_j)的带宽为B_{i, j}，t时刻链路上控制流量和数据流量需要的带宽分别为b_{i, j}^C(t)和b_{i, j}^D(t)，则判定链路拥塞的条件为

(2)

即当链路上流量(包括控制流量和数据流量)需要的带宽大于s_{i, j}B_{i, j}时(s_{i, j}为安全系数)，则认为该链路将会出现拥塞。由于链路上的流量大小存在一定的波动性，增加了安全系数0 < s_{i, j}≤1。
设某一次NOCC过顶卫星切换导致控制报文路由切换的时刻为t₀，记切换前的瞬间为t₀^-，切换后的瞬间为t₀⁺。在t₀^-时刻，设卫星v_n(n=1, 2, …, N)和NOCC之间控制流量的大小为b^C_n(t₀^-)，链路(v_i, v_j)上的数据流量大小为b_{i, j}^D(t₀^-)。
在t₀⁺时刻，控制报文路由切换后，根据假定1)，可以知道控制报文的路由路径，设卫星v_n和NOCC之间在空间段的路由路径包含的链路集合为E_n^C(t₀⁺)。根据假定2)，v_n和NOCC之间控制流量的大小为b_n^C(t₀⁺)=b_n^C(t₀^-)。因此，t₀⁺时刻链路(v_i, v_j)上控制流量需要的带宽为

(3)

式中：x_n^{C_{i, j}}(t₀⁺)∈{0, 1}表示t₀⁺时刻v_n和NOCC之间的路由路径是否经过链路(v_i, v_j)，即E_n^C(t₀⁺)是否包含(v_i, v_j)。若包含，x_n^{C_{i, j}}(t₀⁺)=1，否则x_n^{C_{i, j}}(t₀⁺)=0。根据假定2)，t₀⁺时刻链路(v_i, v_j)上数据流量需要的带宽为b_{i, j}^D(t₀⁺)=b_{i, j}^D(t₀^-)。
因此，根据链路拥塞判定条件，如果满足

(4)

即

(5)

则认为链路(v_i, v_j)在NOCC过顶卫星切换导致控制报文路由切换后会发生拥塞。
图 4为一个拥塞链路预测的示例。为了简化起见，这里只考虑4个卫星节点，分别为v₁、v₂、v₃和v₄，设所有链路的带宽为50 Kbit/s，安全系数为0.9。星间链路上的流量由控制流量和数据流量组成，分别用蓝色数字和黑色数字标注在链路上，单位均为Kbit/s。在t₀^-时刻，NOCC过顶卫星为v₃，v₁、v₂和v₄到v₃的路由路径分别为v₁→v₃，v₂→v₁→v₃和v₄→v₃(图 4(b))。所有卫星节点和NOCC之间的控制流量大小均为10 Kbit/s。

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

图选项

在t₀⁺时刻，NOCC过顶卫星将切换为v₄，v₁、v₂和v₃到v₄的路由路径分别为v₁→v₃→v₄，v₂→v₄和v₃→v₄(图 4(e))。根据假定2)，所有卫星和NOCC之间的控制流量大小仍为10 Kbit/s。预测t₀⁺时刻各链路上控制流量需要的带宽如图 4(e)所示。同时，根据假定2)，预测t₀⁺时刻各链路上数据流量需要的带宽如图 4(f)所示。因此，预测t₀⁺时刻各链路上控制流量和数据流量需要的带宽如图 4(d)所示。
由于链路(v₃, v₄)满足链路拥塞判定条件，即20+30>0.9×50。因此，预测链路(v₃, v₄)为t₀⁺时刻的拥塞链路，而其余链路均不满足条件。

2.2.3 重路由数据流选择 对于可能发生拥塞的链路，需要提前选择部分数据流进行重路由。为了合理地选择需要重路由的数据流，首先定义数据流的速率-满意度函数。
从用户体验角度，对于每条数据流，都存在数据流传输速率到用户体验的服务满意度之间的映射关系。笔者将这种映射关系量化，定义为速率-满意度函数。
定义1??速率-满意度函数。假设网络中有M种业务，数据流l属于其中一种业务m(m=1, 2, …, M)，其传输速率b_l与用户体验的服务满意度S_l之间存在某种确定的映射关系，即

(6)

将这种映射关系称为数据流l的速率-满意度函数，函数值S_l称为数据流l的服务满意度。
同一种业务的不同数据流具有相同的速率-满意度函数，而不同业务的数据流具有不同的速率-满意度函数。
在定义速率-满意度函数之后，就可以确定重路由数据流了。笔者希望在避免链路拥塞的前提下，重路由数据流总的服务满意度尽可能小。因此，重路由数据流选择问题描述如下：已知一条带宽为B_{i, j}，安全系数为s_{i, j}的链路(v_i, v_j)。在NOCC过顶卫星切换之前(即t₀^-时刻)，链路上的控制流量大小为b_{i, j}^C(t₀^-)，链路上有L_{i, j}条数据流，第l(l=1, 2, …, L_{i, j})条数据流的传输速率为b_l^{i, j}，服务满意度为S_l^{i, j}，服务满意度的权重为w_l^{i, j}(w_l^{i, j}与数据流的优先级等有关)。预测在NOCC过顶卫星切换之后(即t₀⁺时刻)，链路上控制流量需要的带宽为b_{i, j}^C(t₀⁺)。为了避免NOCC过顶卫星切换之后链路(v_i, v_j)拥塞，需要选出部分数据流进行重路由。求一种最佳的选择方案，使得重路由数据流总的服务满意度最小，且去除重路由数据流后链路(v_i, v_j)不拥塞。
重路由数据流选择问题可形式化描述为：给定B_{i, j}>0，0 < s_{i, j}≤1，b_{i, j}^C(t₀⁺)≤s_{i, j}B_{i, j}，b_l^{i, j}>0，S_l^{i, j}>0，w_l^{i, j}>0(l=1, 2, …, L_{i, j})，求一个L_{i, j}元向量Y=(y₁, y₂, …, y_{Li, j}), y_l∈{0, 1}，使得最小，且≤s_{i, j}B_{i, j}。
下面证明重路由数据流选择问题是NP完全问题。
定理1??重路由数据流选择问题是NP完全问题。
证明??已知均分问题为NP完全问题。均分问题可以描述为：已知A={1, 2, …, L}，对?l∈A，S_l>0，求是否存在A′?A，使得

(7)

重路由数据流选择问题可以进一步表述为：已知C={1, 2, …, L_{i, j}}，对?l∈C，b_l^{i, j}>0，w_l^{i, j}S_l^{i, j}>0，s_{i, j}B_{i, j}-b_{i, j}^C(t₀⁺)≥0，重路由数据流满意度之和为S^*>0，求是否存在C′?C，使得

(8)

(9)

直到求得S^*最小值为止。
首先，重路由数据流选择问题是NP完全问题。这是因为重路由数据流的选择以及验证过程为计算和，可以在多项式时间内完成。
当限制对?l∈C

(10)

(11)

(12)

时，重路由数据流选择问题变为：已知C={1, 2, …, L_{i, j}}，对?l∈C，w_l^{i, j}S_l^{i, j}>0，求是否存在C′?C，使得

(13)

(14)

即

(15)

重路由数据流选择问题变为均分问题。因此重路由数据流选择问题是NP完全问题。??????证毕
为了求解重路由数据流选择问题，进一步分析其最优解的特性。
定理2 ??重路由数据流选择问题的最优解具有最优子结构特性。假设(y₁, y₂, …, y_{Li, j})(y_l∈{0, 1}, l=1, 2, …, L_{i, j})是重路由数据流选择问题的最优解，(y₂, y₃, …, y_{Li, j})必然是重路由数据流选择子问题的最优解：B_{i, j}>0，0 < s_{i, j}≤1，b_{i, j}^C(t₀⁺)≤ s_{i, j}B_{i, j}-y₁b₁^{i, j}(当y₁=0时，y₁=1；当y₁=1时，y₁=0)，b_l^{i, j}>0，w_l^{i, j}S_l^{i, j}>0(l=2, 3, …, L_{i, j})。
证明??如果上述最优子结构特性不成立，设(z₂, z₃, …, z_{Li, j})(z_l∈{0, 1})是该子问题的一个最优解，而(y₂, y₃, …, y_{Li, j})不是该子问题的最优解。由此可知

(16)

(17)

因此

(18)

(19)

注意到1-y₁=y₁，因此(y₁, z₂, z₃, …, z_{Li, j})是比(y₁, y₂, …, y_{Li, j})更优的解，(y₁, y₂, …, y_{Li, j})不是重路由数据流选择问题的最优解。这与假设矛盾。因此，(y₂, y₃, …, y_{Li, j})必然是相应子问题的最优解。??????证毕
因此，重路由数据流选择问题可以采用动态规划法进行求解，算法的伪代码如下：
算法1??重路由数据流选择
输入：B_{i, j}，s_{i, j}，b_{i, j}^C(t₀⁺)，L_{i, j}，b_l^{i, j}，S_l^{i, j}，w_l^{i, j}(l=1, 2, …, L_{i, j})。
输出：y₁, y₂, …, y_{Li, j}。
1 H⁰={(0, 0)}
2 for each l∈{1, 2, …, L_{i, j}-1} do
3????H₁^l={(B, Q)|(B-b_l^{i, j}, Q-w_l^{i, j}S_l^{i, j})∈H^l-1 and B≤s_{i, j}B_{i, j}-b_{i, j}^C(t₀⁺)}
4????H^l=MergePurge(H^l-1, H₁^l)
5 end for
6 (B₁, Q₁)= the last step point in H^{L_{i, j}-1}
7 (B₂, Q₂)=(B+b^{i, j}_{Li, j}, Q+w^{i, j}_{Li, j}S^{i, j}_{Li, j})
8 Q=max{Q₁, Q₂}
9 if Q₂>Q₁ then
10??y_{Li, j}=0
11 else
12 y_{Li, j}=1
13 end if
14 Backtrack to calculate y_{Li, j}-1, y_{Li, j}-2, …, y₁
设g(l, B)为s_{i, j}B_{i, j}-b_{i, j}^C(t₀⁺)=B，可供选择的数据流为{1, 2, …, l+1}时的最优解值，H^l(l=0, 1, …, L_{i, j})表示函数曲线的全部阶跃点的集合，其中H⁰={(0, 0)}。H₁^l(l= 1, 2, …, L_{i, j})表示函数曲线-g(l-1, B-b_l^{i, j})的全部阶跃点的集合。MergePurge()函数合并2个阶跃点集合，并从中舍弃应去除的阶跃点。(B, Q)为H^{L_{i, j}}中使得B+b_{Li, j}≤s_{i, j}B_{i, j}-b_{i, j}^C(t₀⁺)的最大阶跃点。Q为最优解值。

2.2.4 数据流重路由 为了避免重路由数据流后仍然出现链路拥塞，对数据流重路由时，链路代价应该根据t₀⁺时刻的网络状态进行计算。式(3)给出了t₀⁺时刻链路(v_i, v_j)∈E(t₀⁺)上的控制流量大小。
设t₀^-时刻重路由数据流集合F中的一条数据流r(r=1, 2, …, R)在空间段的路由路径包含的链路集合为E_r^RD(t₀^-)，传输速率为b_r^RD(t₀^-)。其中，R为集合F中元素的个数。由假定2)，在t₀⁺时刻，数据流r的传输速率为b_r^RD(t₀⁺)=b_r^RD(t₀^-)，若不重路由，数据流r在空间段的路由路径包含的链路集合为E_r^RD(t₀⁺)=E_r^RD(t₀^-)。因此，除去需要重路由的数据流，预测t₀⁺时刻链路(v_i, v_j)上的数据流量大小为

(20)

式中：x_r^{RD_{i, j}}(t₀⁺)∈{0, 1}和x_r^{RD_{i, j}}(t₀^-)∈{0, 1}分别表示t₀⁺时刻和t₀^-时刻数据流r的路由路径是否经过(v_i, v_j)，即E_r^RD(t₀⁺)和E_r^RD(t₀^-)是否包含(v_i, v_j)。若包含，则取值为1，否则取值为0。根据假定2)，b_{i, j}^D(t₀⁺)=b_{i, j}^D(t₀^-)，x_r^{RD_{i, j}}(t₀⁺)=x_r^{RD_{i, j}}(t₀^-)。
因此，除去需要重路由的数据流，预测t₀⁺时刻链路(v_i, v_j)上的流量大小为

(21)

预测t₀⁺时刻链路(v_i, v_j)的剩余带宽为

(22)

根据假定2)，d_{i, j}(t₀⁺)=d_{i, j}(t₀^-)。因此，重路由数据流时，链路(v_i, v_j)的代价为

(23)

链路拥塞避免算法的伪代码如下：
算法2??链路拥塞避免算法
输入：G(t₀^-)=(V, E(t₀^-))，B_{i, j}，s_{i, j}，b_{i, j}^D(t₀^-)((v_i, v_j)∈E(t₀^-))，E_n^C(t₀⁺)，b_n^C(t₀^-)(n=1, 2, …, N)，L_{i, j}，b_l^{i, j}，w_l^{i, j}(l=1, 2, …, L_{i, j})，f_m(m=1, 2, …, M)。
输出：F。
初始化：F=?，G=?。
1/*拥塞链路预测*/
2 for each (v_i, v_j)∈E(t₀^-) do
3??for each E_n^C(t₀⁺)∈{E₁^C(t₀⁺), …, E_N^C(t₀⁺)} do
4????if (v_i, v_j)∈E_n^C(t₀⁺) then
5??????????x_n^{C_{i, j}}(t₀⁺)=1
6????else
7??????????x_n^{C_{i, j}}(t₀⁺)=0
8????end if
9??end for
10??
11??if b_{i, j}^C(t₀⁺)+b_{i, j}^D(t₀^-)>s_{i, j}B_{i, j} then
12??????G=G∪(v_i, v_j)
13??end if
14 end for
15 /*重路由数据流选择*/
16 while G≠? do
17????for each data flow l on the first link (v_i, v_j) in G do
18??????m=DetectType(l)
19??????S_l^{i, j}=f_m(b_l^{i, j})
20????end for
21????{r₁^{i, j}, r₂^{i, j}, …, r^{i, j}_{Ri, j}}=SelectReroute(B_{i, j}, s_{i, j}, b_{i, j}^C(t₀⁺), L_{i, j}, b₁^{i, j}, b₂^{i, j}, …, b^{i, j}_{Li, j}, S₁^{i, j}, S₂^{i, j}, …, S^{i, j}_{Li, j}, w₁^{i, j}, w₂^{i, j}, …, w^{i, j}_{Li, j})
22??????F=F∪{r₁^{i, j}, r₂^{i, j}, …, r^{i, j}_{Ri, j}}
23??????G=G\{(v_i, v_j)}
24??????UpdateG(F)
25 end while
26 return F
算法首先进行拥塞链路预测，将可能发生拥塞的链路存入集合G。对于每条链路(v_i, v_j)依次判断是否可能拥塞(line 2)：首先判断在t₀⁺时刻各条控制流是否经过(v_i, v_j)(line 3~9)，计算t₀⁺时刻链路(v_i, v_j)上的控制流量大小。然后根据已知的链路上数据流量大小、带宽和安全系数，预测链路(v_i, v_j)是否拥塞(line 11)。
在得到拥塞链路集合G后，确定重路由数据流，将需要重路由的数据流存入集合F。同一条数据流可能经过多条拥塞链路。由于NOCC过顶卫星切换导致的拥塞链路很可能集中在新过顶卫星附近，一条数据流经过多条拥塞链路的情况更可能发生。因此，每次选取G中的第1条链路(v_i, v_j)计算需要重路由的数据流。首先判断链路(v_i, v_j)上每条数据流的类型(line 18)，计算服务满意度(line 19)，然后通过求解重路由数据流选择问题得到链路(v_i, v_j)上需要重路由的数据流集合{r₁^{i, j}, r₂^{i, j}, …, r^{i, j}_{Ri, j}}(line 21)，添加到集合F(line 22)。将链路(v_i, v_j)从G中删除(line 23)，然后对G进行更新(line 24)。更新G之后，选取G中的第一条链路重复上述过程，直到G=?为止，得到重路由数据流集合F(line 26)。
函数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所示。

图 5 仿真界面 Fig. 5 Emulation interface

图选项

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

参数		数值
卫星系统参数	卫星轨道面数目	6
	每个轨道内卫星数目	11
	卫星轨道高度/km	780
	极区边界纬度值/(°)	60
	星间链路带宽/(Mbit·s-1)	1
	星地链路带宽/(Mbit·s-1)	10
	地面站与NOCC位置	北京
流量相关参数	每条控制流传输 速率/(Kbit·s-1)	20
	数据流数目	100
	数据流平均传输 速率/(Kbit·s-1)	50，60，70， 80，90，100
DFRR与NONE 相关参数	链路代价参数α1，α2，β，γ	2 000，1，1，0.01
	安全系数	1
	速率-满意度函数	Sl=100 th bl(bl>0)
	仿真时间/s	6 034.7

表选项






与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策略的有效性。

参考文献

[1]	BAO J, ZHAO B, YU W, et al. OpenSAN:A software-defined satellite network architecture[J]. ACM Sigcomm Computer Communication Review, 2014, 44(4): 347-348. DOI:10.1145/2740070
[2]	TANG Z, ZHAO B, YU W, et al.Software defined satellite networks: Benefits and challenges[C]//Computing, Communications and IT Applications Conference (ComComAp).Piscataway, NJ: IEEE Press, 2014: 127-132.
[3]	YUAN D M, REN R W. Research on the SDN-based architecture of space-sky information network[J]. Applied Mechanics & Materials, 2014, 644.
[4]	LI T, ZHOU H, LUO H, et al.Using SDN and NFV to implement satellite communication networks[C]//2016 International Conference on Networking and Network Applications.Piscataway, NJ: IEEE Press, 2016: 131-134.
[5]	BARRITT B J, EDDY W.SDN enhancements for LEO satellite networks: AIAA-2016-5755[R].Reston: AIAA, 2016.
[6]	GOPAL R, RAVISHANKAR C.Software defined satellite networks: AIAA-2014-4480[R].Reston: AIAA, 2014.
[7]	BERTAUX L, MEDJIAH S, BERTHOU P, et al. Software defined networking and virtualization for broadband satellite networks[J]. IEEE Communications Magazine, 2015, 53(3): 54-60. DOI:10.1109/MCOM.2015.7060482
[8]	FERRúS R, KOUMARAS H, SALLENT O, et al. SDN/NFV-enabled satellite communications networks:Opportunities, scenarios and challenges[J]. Physical Communication, 2015, 18(2): 95-112.
[9]	FERRúS R, SALLENT O, RASHEED T, et al. Enhancing satellite & terrestrial networks integration through NFV/SDN technologies[J]. IEEE Communications Society E-Letter, 2015, 10(4): 17-21.
[10]	MCKEOWN N. Software-defined networking[J]. INFOCOM Keynote Talk, 2009, 17(2): 30-32.
[11]	M2M and IoT via satellite, 7th Edition[EB/OL].(2016-11-21)[2017-02-28].http://www.nsr.com/research-reports/satellite-communications-1/m2m-and-iot-via-satellite-7th-edition/.
[12]	FEI C, ZHAO B, YU W, et al.A research platform for software defined satellite networks[C]//201716th International Conference on Optical Communications and Networks.Piscataway, NJ: IEEE Press, 2017: 1-2.
[13]	左青云, 陈鸣, 赵广松, 等. 基于OpenFlow的SDN技术研究[J]. 软件学报, 2013, 24(5): 1078-1097. ZUO Q Y, CHEN M, ZHAO G S, et al. Research on OpenFlow-based SDN technologies[J]. Journal of Software, 2013, 24(5): 1078-1097. (in Chinese)
[14]	WERNER M. A dynamic routing concept for ATM-based satellite personal communication networks[J]. IEEE Journal on Selected Areas in Communications, 1997, 15(8): 1636-1648. DOI:10.1109/49.634801
[15]	GOUNDER V V, PRAKASH R, ABU-AMARA H.Routing in LEO-based satellite networks[C]//Procceedings of 1999 Emerging Technologies Symposium on Wireless Communications and Systems.Piscataway, NJ: IEEE Press, 1999: 22.1-22.6.
[16]	EVANS J V. Satellite systems for personal communications[J]. Proceedings of the IEEE, 1998, 86(7): 1325-1341. DOI:10.1109/5.681367
[17]	TSAI K, MA R P.DARTING: A cost-effective routing alternative for large space-based dynamic-topology networks[C]//Military Communications Conference, 1995.Piscataway, NJ: IEEE Press, 1995: 682-686.
[18]	MIHAEL M, MARKUS W, ALE? ?, et al. Alternate link routing for traffic engineering in packet-oriented ISL networks[J]. International Journal of Satellite Communications, 2001, 19(5): 463-480. DOI:10.1002/(ISSN)1099-1247
[19]	TALEB T, MASHIMO D, JAMALIPOUR A, et al. Explicit load balancing technique for NGEO satellite IP networks with on-board processing capabilities[J]. IEEE/ACM Transactions on Networking, 2009, 17(1): 281-293. DOI:10.1109/TNET.2008.918084
[20]	KOR?AK ?, ALAG?Z F, JAMALIPOUR A. Priority-based adaptive routing in NGEO satellite networks[J]. International Journal of Communication Systems, 2007, 20(3): 313-333. DOI:10.1002/(ISSN)1099-1131
[21]	赵杰.基于SDN的VDES卫星网络路由关键技术研究[D].成都: 电子科技大学, 2017: 33-45. ZHAO J.Research on key technologies of VDES satellite network routing based on SDN[D].Chengdu: University of Electronic Science and Technology of China, 2017: 33-45(in Chinese). http://cdmd.cnki.com.cn/Article/CDMD-10614-1017077899.htm
[22]	袁梦珠.基于SDN的卫星网络关键技术研究[D].成都: 电子科技大学, 2017: 42-57. YUAN M Z.Research on key technologies of SDN based satellite network[D].Chengdu: University of Electronic Science and Technology of China, 2017: 42-57(in Chinese). http://cdmd.cnki.com.cn/Article/CDMD-10614-1017078401.htm
[23]	YU X, LEI W M, SONG L, et al. A routing algorithm based on sdn for on-board switching networks[J]. Journal of Information Science & Engineering, 2017, 33(5): 1255-1266.
[24]	田睿, 郁小松, 赵永利, 等. 基于SDN的空间信息网络多路径承载策略[J]. 无线电工程, 2016, 46(12): 1-4. TIAN R, YU X S, ZHAO Y L, et al. Multi-path carrying strategy in SDN-based space information networks[J]. Radio Engineering, 2016, 46(12): 1-4. DOI:10.3969/j.issn.1003-3106.2016.12.01 (in Chinese)
[25]	朱小茹, 王兴伟, 张爽, 等. 基于SDN和接触图的空间信息网络路由机制[J]. 计算机科学与探索, 2018, 12(6): 918-927. ZHU X R, WANG X W, ZHANG S, et al. Routing mechanism for space information network based on SDN and contact graph[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(6): 918-927. (in Chinese)
[26]	JIANG L, FENG J, SHEN Y, et al. Fast recovery routing algorithm for software defined network based operationally responsive space satellite networks[J]. KSⅡ Transactions on Internet & Information Systems, 2016, 10(6): 2936-2951.