兼顧控制流量的軟件定義衛星網絡路由策略

費長江， 趙寶康， 虞萬榮， 吳純青

(國防科技大學計算機學院, 長沙 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基本的控制過程為：控制層采集基礎設施層的網絡狀態，形成全局網絡視圖；根據應用層中應用程序確定的控制功能進行控制決策；控制決策以控制規則的形式發送給基礎設施層，基礎設施層對相關配置進行更新?？刂茍笪闹饕诨A設施層和控制層，即衛星和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所示?？傮w來說，在不同的數據流平均傳輸速率即不同的網絡負載下，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%?？刂茍笪膩G包率減少的比例比數據報文高，這是因為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減少分組丟失的同時，使得部分原本丟失的報文被納入分組時延統計中，這部分報文的分組時延一般比較大，從而可能增加平均分組時延；③當對數據流進行重路由時，為了繞開擁塞鏈路，通常會選擇較長的路徑，從而增加重路由數據流的分組時延。對于方面③，當網絡中衛星數量和鏈路數量增加時，同一節點對之間有更多代價相近的替代路徑，由此帶來的重路由數據流分組時延增加會減小?？梢姡珼FRR造成分組時延減小或增大取決于方面①和方面②、方面③作用的大小。

圖8 NONE與DFRR分組時延對比Fig.8 Comparison of packet delays between NONE and DFRR

從實驗結果可以看出，當網絡負載較小(數據流平均傳輸速率小于70 Kbit/s)時，2種方法控制報文和數據報文的分組時延相差不大，DFRR的分組時延略大；當網絡負載較大(數據流平均傳輸速率大于70 Kbit/s)時，DFRR的分組時延比NONE更小，方面①起主要作用?？傮w來說，DFRR中控制報文的分組時延減少了1.71%，數據報文的分組時延減少了7.50%。

4 結 論

1) 針對SDSN中海量、動態、高優先級的控制流量對數據報文傳輸產生極大干擾的問題，本文提出了一種DFRR策略。DFRR在計算數據報文路由時，將鏈路上的控制流量大小作為影響鏈路代價的一個因素，減少選擇控制流量較大的鏈路；在NOCC過頂衛星切換導致控制流量分布發生較大變化之前，預測可能發生擁塞的鏈路，并選出鏈路上部分數據流進行重路由，從而避免擁塞。

2) 仿真實驗結果表明：在不同的網絡負載下，與未優化的基本路由策略相比，DFRR的鏈路擁塞次數平均減少了57.63%，控制報文和數據報文的丟包率分別平均減少了46.89%和32.08%，控制報文和數據報文的分組時延分別平均減少了1.71%和7.50%，從而驗證了DFRR策略的有效性。