基于時延的軟件定義衛(wèi)星網(wǎng)絡(luò)控制域規(guī)劃策略

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

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安，710077)

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

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

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

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

1 軟件定義衛(wèi)星網(wǎng)絡(luò)架構(gòu)

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

整個SDSN網(wǎng)絡(luò)根據(jù)GEO衛(wèi)星數(shù)量及其覆蓋區(qū)域劃分為若干控制域，每個控制域包含一個域控制器、多個從控制器以及許多LEO衛(wèi)星。每個控制域又被劃分為若干個控制子域，每個控制子域內(nèi)由從控制器管理其所屬的LEO。運行過程中，GEO衛(wèi)星接收流建立請求，并通過分發(fā)控制信息改變其控制域內(nèi)的LEO狀態(tài)。NCC/NMC訪問LEO衛(wèi)星，并通過GEO衛(wèi)星管理整個網(wǎng)絡(luò)，GEO衛(wèi)星與NCC/NMC間的連接實現(xiàn)了全球流建立，能夠?qū)γ恳粋€控制動作做出響應(yīng)。從控制器通過星間鏈路(Inter Satellite Links, ISLs)收集狀態(tài)信息或?qū)⒖刂菩畔⒎职l(fā)到所屬子域內(nèi)的LEO衛(wèi)星。這種網(wǎng)絡(luò)架構(gòu)能極大地減少GEO衛(wèi)星廣播引起的干擾、控制器-交換機之間的信令延遲。下一步基于該架構(gòu)對衛(wèi)星網(wǎng)絡(luò)中控制子域劃分問題展開。

2 模型構(gòu)建

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

(1)

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

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

2.1 LEO到從控制器時延

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

(2)

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

(3)

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

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

(4)

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

(5)

(6)

則控制子域內(nèi)LEO到從控制器平均時延：

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

(7)

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

(8)

2.2 網(wǎng)絡(luò)開銷

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

(9)

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

(10)

式中：vS為從控制器狀態(tài)信息的平均傳播速率。網(wǎng)絡(luò)開銷即為轉(zhuǎn)發(fā)開銷與狀態(tài)同步開銷之和。

TL(t)=PT+PS

(11)

2.3 目標函數(shù)

為了合理地配屬從控制器和LEO之間的匹配關(guān)系，盡可能減少從控制器和子域內(nèi)LEO之間的平均時延且控制網(wǎng)絡(luò)開銷。因此，得到如下目標函數(shù)：

目標函數(shù)及約束條件：

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

(12)

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

(13)

(14)

式中：y∈(0,1)，用于調(diào)節(jié)平均時延和網(wǎng)絡(luò)開銷對于控制域規(guī)劃的影響。

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

3 算法設(shè)計

3.1 匹配機制設(shè)計

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

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

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

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

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

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

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

4 仿真與性能評估

4.1 仿真環(huán)境建立

4.1.1 實驗工具

實驗利用STK11.01工具進行衛(wèi)星軌道的相關(guān)仿真并借助Matlab2016b工具對算法進行仿真和分析實驗結(jié)果。

4.1.2 拓撲選擇

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

表2 衛(wèi)星軌道參數(shù)設(shè)定

4.1.3 仿真參數(shù)設(shè)定

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

4.2 仿真結(jié)果分析

4.2.1 算法運算時間

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

圖1 Object值、運算時間與k的關(guān)系

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

圖2 算法運算時間

4.2.2 子域劃分

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

圖3 多域規(guī)劃結(jié)果

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

圖4 網(wǎng)絡(luò)負載對比

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

4.2.3 LEO到控制器平均時延及網(wǎng)絡(luò)開銷

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

圖5 平均時延對比

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

圖6為3種方法的網(wǎng)絡(luò)開銷情況。

圖6 3種方法網(wǎng)絡(luò)開銷對比

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

5 結(jié)語

針對現(xiàn)有控制域劃分算法時延考慮不全面的問題，本文在建立時延模型時加入排隊時延和處理時延，并設(shè)計了MDBPSA算法對網(wǎng)絡(luò)控制域進行規(guī)劃，可得以下結(jié)論：

1)迭代跳出機制能有效縮短算法求解時間，使算法對控制域內(nèi)的子域劃分問題求解時間在0.53 s之內(nèi)，能夠較好地適應(yīng)衛(wèi)星網(wǎng)絡(luò)環(huán)境；

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

3)MDBPSA算法的時延性能明顯優(yōu)于對比算法，且構(gòu)建的網(wǎng)絡(luò)連接關(guān)系較為穩(wěn)定，雖然缺乏對流量抖動的敏感，但節(jié)省了不必要的網(wǎng)絡(luò)開銷。

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

1)從網(wǎng)絡(luò)節(jié)點可靠性和負載等角度加強從控制器部署選址問題的研究；

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