基于時延的軟件定義衛星網絡控制域規劃策略

郭子楨, 梁 俊, 肖 楠, 陳威龍, 陳金濤, 謝寶華

(空軍工程大學信息與導航學院，西安，710077)

將軟件定義網絡架構引入衛星網絡，能夠使數據平面的衛星僅需承擔轉發和硬件配置功能，就實現路由策略的靈活部署、網絡配置簡化及網絡成本降低[1]。隨著衛星網絡承載的業務越來越多，單個控制器顯然無法滿足網絡的控制需求[2]，多控制器雖然能克服單控制器帶來的單點失效和可擴展性差的缺點，卻也帶來了一個新問題：對于給定數量的控制器和交換機，如何合理規劃交換機與控制器的配屬關系。

現有SDN多域規劃的研究已經較為成熟，能夠為衛星網絡相關研究提供一定的借鑒。WANG[3]等提出基于K-means的控制器部署方法，通過對網絡中節點進行聚類，在聚類中心處部署控制器并按照跳數最少原則劃分控制域，這能夠有效降低控制器通信時延。文獻[4]提出的K-Critical算法通過預測機制和多分類集網絡拓撲構建，可以有效實現系統的負載均衡。文獻[5]提出了一種自適應多域劃分算法(Adaptive Multi-Domain Approach，AMDA)，通過考慮時延和控制器負載，采用譜聚類方法劃分控制域。文獻[6]提出了一種基于雙向匹配的控制域劃分策略，同時從控制器和交換機2個角度考慮，以實現控制器間的負載均衡。然而這些算法大多適用于拓撲固定且網絡尺度較小的地面網絡，將其直接應用于衛星網絡會導致網絡性能不理想。

目前，已經有許多研究者開始關注SDSN網絡控制器部署問題：楊力[7]等提出一種基于雙門限的控制器動態部署策略，通過定義控制器的負載狀態以期實現控制器負載的動態調整，然而仿真實驗卻并未直接與衛星網絡拓撲相結合。WU[8]等提出一種低開銷的網絡擴展方法，以控制器與交換機的最短距離為優化指標。XU[9]等借助STK工具對SDSN網絡的時延進行了分析，將低軌衛星(Low Earth Orbit, LEO)按照軌道分組并從每組選出最靠近赤道且運動方向相反的2顆衛星部署控制器，共部署12個控制器，但這種部署方案要求星座中所有節點均安裝控制器模塊且動態調整其開閉狀態，網絡狀態變化時的重規劃開銷過大。HU[10]等設計了一種SoftLEO架構，將LEO衛星按照軌道分為6組，選擇6個緯度相近的節點作為每組衛星的控制器部署位置以減小控制器間的通信開銷，然而網絡的可靠性和負載均衡性能不夠理想。WU[11]等設計了一種APSO算法全面的分析了控制器的狀態同步開銷、信息收集開銷、流建立開銷、網絡重規劃開銷等并以此確定控制器部署位置。文獻[12]通過線性規劃優化流建立時延完成控制器部署及劃域。文獻[13]在部署控制器時將網絡端到端時延和負載均衡指數作為優化目標。這些研究大多僅考慮傳播時延，忽略了排隊時延與處理時延，同時衛星網絡中節點轉發、處理能力有限，不同的負載將帶來排隊時延與處理時延的巨大差異進而影響劃域結果，簡單地忽略這些影響或者認為所有控制器都有相同的排隊時延與處理時延的做法顯然是不合理的，這將導致網絡性能的下降。

本文針對現有算法時延描述不夠全面的問題，綜合考慮排隊時延、處理時延、傳播時延構建了軟件定義衛星網絡時延分析模型，并設計了基于模擬退火的多控制域均衡劃分算法(Multi-Domain Balanced Partition Algorithm Based on Simulated Annealing, MDBPSA)，通過構建控制器匹配列表的方法尋找近似最優的劃域結果，提升網絡時延性能、實現網絡負載均衡。同時由于衛星網絡拓撲快速動態變化，時間片持續時間短，要求算法有較快的運算速度，本文特別設計了迭代跳出機制以加快模擬退火算法的求解速度，仿真結果表明改進后的算法求解時間遠小于時間片持續時間且性能良好，能夠滿足衛星網絡需求。

1 軟件定義衛星網絡架構

考慮到衛星地面站全球布站困難且成本高昂、同步軌道衛星(Geosynchronous Earth Orbit，GEO)處理轉發能力無法適應LEO衛星數量和業務的快速增長、GEO衛星對地通信時延較大等問題[14-17]，本文采用在地面網絡控制/監測中心(Network Control Center/Network Management Center, NCC/NMC)部署主控制器，在GEO衛星上部署區域控制器，并從基于OpenFlow的LEO衛星中挑選從屬控制器的多層部署方案。該架構利用地面強大的計算能力和充足的存儲空間控制整個網絡，GEO衛星與地面站保持穩定連接，并選取從控制器作為GEO的補充。

整個SDSN網絡根據GEO衛星數量及其覆蓋區域劃分為若干控制域，每個控制域包含一個域控制器、多個從控制器以及許多LEO衛星。每個控制域又被劃分為若干個控制子域，每個控制子域內由從控制器管理其所屬的LEO。運行過程中，GEO衛星接收流建立請求，并通過分發控制信息改變其控制域內的LEO狀態。NCC/NMC訪問LEO衛星，并通過GEO衛星管理整個網絡，GEO衛星與NCC/NMC間的連接實現了全球流建立，能夠對每一個控制動作做出響應。從控制器通過星間鏈路(Inter Satellite Links, ISLs)收集狀態信息或將控制信息分發到所屬子域內的LEO衛星。這種網絡架構能極大地減少GEO衛星廣播引起的干擾、控制器-交換機之間的信令延遲。下一步基于該架構對衛星網絡中控制子域劃分問題展開。

2 模型構建

SDSN控制子域劃分問題可以運用圖論相關知識進行描述。SDSN網絡可以表示為G=(V,E)，其中V表示節點集合，E表示節點間鏈路集合。假設網絡中所有LEO衛星均可承擔交換機功能，其中的一部分部署了從控制器，LEO衛星數量為N，從控制器數量為M。從控制器集合用C={C1,C2,…,CM}表示，其處理能力為Ω={Ω1,Ω2,…,ΩM}，對控制器設置相應冗余因子βm∈(0,1)以預留部分處理能力預防過載[13]。LEO集合表示為S={S1,S2,…,SN}。兩節點間最短路徑表示為dmn。在衛星網絡中網絡流量可以表示為時間的函數，Sn在時間t內的流請求速率可以表示為λ(t)n。矩陣X描述SDSN控制域中從控制器和LEO的控制關系，其中元素取值見式(1)。

(1)

每個LEO僅與一個從控制器建立控制關系。因此整個控制域可劃分為M個控制子域: Domainm1～DomainmM。

現有OpenFlow交換機均為多核交換機，且OpenDaylight、Ryu等控制器均采用多線程處理方式，因此，可將LEO與從控制器間的通信過程近似為G/M/k排隊模型，即消息到達為一般過程、控制器對于流請求的處理為馬爾科夫過程、從控制器線程數為k。在此基礎上，可計算相關參數。

2.1 LEO到從控制器時延

所有與Cm相連的LEO的流請求速率之和即為Cm在時間t內需要處理的流請求，記為L(t)m，見式(2)，其中各LEO交換機之間的流請求相互獨立。

(2)

由Little原理可得流請求排隊時延Q(t)m，見式(3)。

(3)

式中：Ω(t)m表示時間t內從控制器Cm的可用處理能力，且0<Ω(t)m<Ωm；λ(t)mn表示Sn在時間t內對Cm的流請求速率。

Cm的平均處理時間為P(t)m，滿足：

(4)

衛星網絡覆蓋范圍大，路徑傳播時延也是控制子域規劃的重要指標。傳播時延T(t)m滿足式(5)：

(5)

(6)

則控制子域內LEO到從控制器平均時延：

AT(t)m=Q(t)m+P(t)m+T(t)m

(7)

控制域平均時延為AT(t)：

(8)

2.2 網絡開銷

SDN架構下無法匹配流表的數據包需上交從控制器處理，且從控制器需要進行周期性通信以更新控制邏輯，保持控制域內網絡視圖。因此網絡開銷主要可分為轉發開銷和狀態同步開銷2個主要部分。轉發開銷PT主要為從控制器處理LEO的Packet-in包并下發流表所帶來的網絡開銷，見式(9)。狀態同步開銷PS見式(10)。

(9)

式中：vR為從控制器輪詢LEO的平均速率。

(10)

式中：vS為從控制器狀態信息的平均傳播速率。網絡開銷即為轉發開銷與狀態同步開銷之和。

TL(t)=PT+PS

(11)

2.3 目標函數

為了合理地配屬從控制器和LEO之間的匹配關系，盡可能減少從控制器和子域內LEO之間的平均時延且控制網絡開銷。因此，得到如下目標函數：

目標函數及約束條件：

minObject=[yAT(t)+(1-y)TL(t)]

(12)

?m,L(t)m≤βm·Ω(t)m

(13)

(14)

式中：y∈(0,1)，用于調節平均時延和網絡開銷對于控制域規劃的影響。

上述約束條件中，式(13)表示網絡中沒有控制器過載的情況發生。式(14)表示所有LEO都只能連接到唯一一個從控制器。

3 算法設計

3.1 匹配機制設計

定義1匹配。即LEO與從控制器建立控制關系。例如Sn若受Cm控制，則LEO與Cm完成匹配。記為(Cm，Sn)。

定義2從控制器匹配列表。從控制器將控制域內所有LEO按照dmnλ(t)n升序排列，并構造匹配列表Γ(Cm)={Sn,…}，在從控制器未過載的情況下優先與匹配列表中排序靠前的LEO建立匹配。

定義3優選。若Sn在從控制器匹配列表Γ(Cm)={Sn,…}中排在首位，則Sn是Cm的優選LEO，記為Sn←Γ(Cm)。

3.2 基于模擬退火的多控制域均衡劃分算法

MDBPSA算法的基本流程為：首先收集網絡歷史狀態信息，由于衛星軌道的周期性，我們能夠獲得所需信息作為劃域依據。匹配過程中從控制器在處理能力允許的情況下，優先與優選LEO進行匹配。針對柵格化的衛星網絡使用魯棒性強的模擬退火算法對從控制器與LEO的匹配進行優化，尋求使目標函數最小的匹配方式。不斷重復該過程，直至網絡中不存在未得到匹配的LEO，得到SDSN多域劃分。

表1 基于模擬退火的多域均衡規劃算法

建立匹配時，LEO向所有從控制器提交匹配申請，各從控制器匹配列表中元素相同，只有排序的差異。在匹配過程中若存在從控制器不滿足L(t)m>βmΩ(t)m|Ω(t)m≤0，則采用模擬退火算法為不滿足條件的從控制器建立匹配，并將建立了匹配的LEO從匹配列表中剔除。若所有從控制器均滿足L(t)m>βmΩ(t)m|Ω(t)m≤0，則放寬匹配條件，為仍未得到匹配的LEO選擇可用處理能力最大或過載程度最輕的從控制器建立匹配，直至匹配列表為空集。綜上，在整個匹配過程中不會遺漏任何LEO，能夠為每個LEO選取合適的從控制器建立匹配關系。

4 仿真與性能評估

4.1 仿真環境建立

4.1.1 實驗工具

實驗利用STK11.01工具進行衛星軌道的相關仿真并借助Matlab2016b工具對算法進行仿真和分析實驗結果。

4.1.2 拓撲選擇

實驗拓撲以IRIDIUM[18]進行調整得到，如表2所示。這樣可使得時間片劃分個數少于644個，最短持續時間大于8 s，平均持續時間大于133.17 s[19]，為控制域規劃留出了充足的時間。

表2 衛星軌道參數設定

4.1.3 仿真參數設定

本文仿真參數設定如下：差異化的選取LEO流請求速率λ(t)n的值，將取值范圍設定為100～500 kB/s以模擬衛星網絡控制流量特征。從控制器處理能力均為8 MB。設定從控制器冗余因子為0.9，輪詢LEO的平均速率為vR=10 kB/s，進行狀態同步的傳播速率vS=1 kB/s。y值設定為0.5。

4.2 仿真結果分析

4.2.1 算法運算時間

為了縮短模擬退火算法運算時長以適應衛星網絡拓撲變化，MDBPSA算法設計了迭代跳出機制以縮短算法運行時間。模擬退火算法的特點是能夠依概率接受較差的解，避免陷入局部最優。因此設置計數器記錄新解被拒絕的次數，若連續k次被拒絕，則提前結束本次迭代。k與目標函數值及算法運算時間的關系如圖1所示，將相同條件下重復實驗50次的最優值作為最終結果。圖中紅色虛線為不設置迭代跳出機制時Object極限值，此時的運算時間為10.27 s。

圖1 Object值、運算時間與k的關系

由圖1可以看出，k=11時能夠在保證求解結果良好的情況下盡可能縮短算法運算時間。此時算法運算時間的累積分布函數如圖2所示，可知運算時間基本保持在0.56 s之內，較時間片最短持續時間小很多。迭代跳出機制能夠明顯加快算法運算速度，使得算法能夠適應衛星網絡拓撲的快速動態變化。

圖2 算法運算時間

4.2.2 子域劃分

為了展示MDBPSA算法的控制器負載均衡性能，后續實驗將地面網絡中較為成熟的AMDA方法[5]及文獻[12]劃域思想(下文簡稱為ILP方法)作為對比。AMDA算法按照負載自適應方式為控制器動態分配交換機完成多域構建；ILP方法力求使網絡流建立時延最小。以控制域網絡拓撲為仿真對象，其中共包含25個LEO節點及40條星間鏈路。假設網絡中所有節點間統計相互獨立且都具備部署從控制器的能力，將其中4個節點設置為從控制器節點，使用不同方法對上述網絡拓撲進行子域劃分，結果如圖3所示。圖中以不同形狀區分LEO節點及從控制器節點，C1～C4所管理的控制子域Domainm1～Domainm4分別以白色、淺綠色、深綠色、黑色表示。

圖3 多域規劃結果

3種劃域方式控制子域負載對比見圖4。

圖4 網絡負載對比

從圖4可以看出ILP方法從控制器負載差異最大，這是由于該方法將流建立時延作為優化目標，僅考慮傳播時延而忽略了控制器處理能力限制，這也說明了在衛星網絡中部署控制器時不考慮處理時延和排隊時延的做法不夠合理。AMDA方法和MDBPSA均實現了LEO與從控制器的均衡連接。相較而言，MDBPSA加入了對處理時延的考慮，且網絡時延由各控制子域時延按負載加權得到，加強了對網絡負載的限制，故能取得更好的負載均衡性能。以從控制器負標準差作為衡量劃域均衡性的指標，可得到如下結果：AMDA方法297.039、MDBPSA算法168.158、ILP方法492.446，可以看出MDBPSA算法負載均衡性明顯優于其他算法，較AMDA方法提升43.39%，較ILP方法提升65.85%。

4.2.3 LEO到控制器平均時延及網絡開銷

在實驗2所得子域劃分的基礎上，本實驗對3種方法LEO到從控制器時延進行對比。實驗中假設數據包在星間鏈路傳播時速率穩定可靠且丟包率為零。圖5為3種算法的控制域平均時延情況。

圖5 平均時延對比

從圖5可以看出，MDBPSA算法各子域的平均時延相差不大，而AMDA方法中Domain4和ILP算法Domain2的平均時延很大。這是因為AMDA作為一種彈性規劃方式，雖然能夠快速的均衡從控制器負載，但從控制器與LEO之間的連接關系并不穩定，不穩定的網絡關系導致部分從控制器平均時延增大。在更為復雜的網絡環境下這種現象更加明顯，甚至可能引起跨域通信問題使網絡時延急劇增加。而ILP算法缺乏對控制器處理時延、排隊時延的考慮，導致時延性能不夠理想。綜合來看，MDBPSA 算法將排隊時延和處理時延納入考慮范圍后能夠明顯平衡各控制子域時延，使網絡平均時延低于AMDA方法且較ILP方法降低約10%。

圖6為3種方法的網絡開銷情況。

圖6 3種方法網絡開銷對比

由圖6可以看出MDBPSA算法在具有較好性能的同時，網絡開銷也低于對比算法。這是由于AMDA方法、ILP方法分別注重負載和流建立時延而對控制器到交換機距離缺乏關注故而性能并不理想。通過對算法的分析可知，MDBPSA算法在進行劃域時對節點間距離與流量負載情況均進行了考慮，而網絡開銷主要與節點間距離及流量負載情況有關，故而MDBPSA算法能夠使網絡開銷較ILP方法下降12.52%。

5 結語

針對現有控制域劃分算法時延考慮不全面的問題，本文在建立時延模型時加入排隊時延和處理時延，并設計了MDBPSA算法對網絡控制域進行規劃，可得以下結論：

1)迭代跳出機制能有效縮短算法求解時間，使算法對控制域內的子域劃分問題求解時間在0.53 s之內，能夠較好地適應衛星網絡環境；

2)算法具有良好的負載均衡性能，較AMDA方法提升43.39%，較ILP方法提升65.85%；

3)MDBPSA算法的時延性能明顯優于對比算法，且構建的網絡連接關系較為穩定，雖然缺乏對流量抖動的敏感，但節省了不必要的網絡開銷。

未來將在下列方面作進一步改進：

1)從網絡節點可靠性和負載等角度加強從控制器部署選址問題的研究；

2)將時間片變化時交換機遷移所產生的開銷納入考慮范圍。