軟件定義航空集群機(jī)載網(wǎng)絡(luò)自適應(yīng)更新策略

鄒鑫清， 呂 娜， 陳柯帆， 胡詩(shī)駿

(1. 空軍工程大學(xué)信息與導(dǎo)航學(xué)院， 西安， 710077； 2.空軍裝備部上海局駐蕪湖地區(qū)軍代表室， 安徽蕪湖， 241000)

近年來(lái)，隨著現(xiàn)代戰(zhàn)爭(zhēng)逐步趨向信息化和網(wǎng)絡(luò)化，航空作戰(zhàn)平臺(tái)的更新?lián)Q代正向智能化快速發(fā)展。為了更好地協(xié)調(diào)、重組各類航空作戰(zhàn)平臺(tái)，以積極應(yīng)對(duì)未來(lái)未知戰(zhàn)場(chǎng)環(huán)境帶來(lái)的挑戰(zhàn)，衍生于生物集群的航空集群概念被提出[1]。航空集群是由規(guī)模一定、功能多樣的有人/無(wú)人航空平臺(tái)組成，集群成員間通過(guò)簡(jiǎn)單、智能和高效的協(xié)作完成復(fù)雜任務(wù)。

機(jī)載網(wǎng)絡(luò)作為航空平臺(tái)間信息交互的樞紐，是航空集群成員間進(jìn)行靈巧協(xié)同配合的重要基礎(chǔ)。但長(zhǎng)期以來(lái)，機(jī)載網(wǎng)絡(luò)從傳統(tǒng)的“鏈”(航空數(shù)據(jù)鏈)發(fā)展到“網(wǎng)”(航空自組織網(wǎng))，都是針對(duì)特定作戰(zhàn)場(chǎng)景所設(shè)計(jì)，僅能滿足特定作戰(zhàn)任務(wù)的需求，且網(wǎng)絡(luò)自身的靈活性、可擴(kuò)展性及互操作性較差，難以滿足未來(lái)網(wǎng)絡(luò)中心戰(zhàn)作戰(zhàn)環(huán)境中不同系統(tǒng)間的信息交互需求[2]。

軟件定義網(wǎng)絡(luò)(software-defined networking, SDN)作為近幾年發(fā)展迅猛的一種新型網(wǎng)絡(luò)范式[3]，為當(dāng)前機(jī)載網(wǎng)絡(luò)面臨的困境提供了全新的突破方法。SDN將網(wǎng)絡(luò)的控制平面和數(shù)據(jù)平面分離，基于可編程的開(kāi)放接口，通過(guò)邏輯集中的控制器實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)更靈活、細(xì)粒度地管理[4]。由于SDN的優(yōu)勢(shì)恰好可以彌補(bǔ)機(jī)載網(wǎng)絡(luò)的缺陷，文獻(xiàn)[5]將SDN的概念與技術(shù)應(yīng)用于機(jī)載網(wǎng)絡(luò)中，構(gòu)建了新一代面向航空集群的網(wǎng)絡(luò)——軟件定義航空集群機(jī)載網(wǎng)絡(luò)(software-defined airborne network of the aviation swarm, SDAN-AS)，為機(jī)載網(wǎng)絡(luò)未來(lái)的發(fā)展方向提供了重要參考和借鑒，但卻沒(méi)有對(duì)SDAN-AS存在的具體關(guān)鍵技術(shù)問(wèn)題進(jìn)行深入挖掘與研究。

作為SDN網(wǎng)絡(luò)運(yùn)行的基礎(chǔ)，網(wǎng)絡(luò)更新問(wèn)題一直受到相關(guān)研究者的廣泛關(guān)注[6]。為保證業(yè)務(wù)傳輸?shù)倪B續(xù)性，當(dāng)網(wǎng)絡(luò)鏈路、節(jié)點(diǎn)、拓?fù)涞葼顟B(tài)發(fā)生變化時(shí)(如節(jié)點(diǎn)故障、鏈路擁塞等)，需要對(duì)網(wǎng)絡(luò)進(jìn)行適應(yīng)性調(diào)整，如改變傳輸路徑、調(diào)整鏈路負(fù)載等，通常稱為網(wǎng)絡(luò)更新。網(wǎng)絡(luò)更新問(wèn)題是通信網(wǎng)絡(luò)的基礎(chǔ)性問(wèn)題，更是SDN控制平面的核心問(wèn)題，直接關(guān)系到網(wǎng)絡(luò)運(yùn)行效率和業(yè)務(wù)通信質(zhì)量[7]。

目前SDN網(wǎng)絡(luò)更新問(wèn)題的研究普遍基于拓?fù)湎鄬?duì)穩(wěn)定、鏈路質(zhì)量相對(duì)可靠的有線網(wǎng)絡(luò)環(huán)境，針對(duì)多樣性業(yè)務(wù)傳輸下的網(wǎng)絡(luò)擁塞問(wèn)題研究相應(yīng)的網(wǎng)絡(luò)更新策略。對(duì)于航空集群，由于其OODA的閉環(huán)作戰(zhàn)需求，SDAN-AS的業(yè)務(wù)具有與SDN有線網(wǎng)絡(luò)具有相同的多樣性特點(diǎn)；但是航空集群成員移動(dòng)速度較快、成員相對(duì)位置變化頻繁，且存在敵方干擾的情況，導(dǎo)致SDAN-AS的鏈路狀態(tài)高度不穩(wěn)定，從而加劇了鏈路擁塞和業(yè)務(wù)傳輸?shù)牟贿B續(xù)，嚴(yán)重影響SDAN-AS的業(yè)務(wù)轉(zhuǎn)發(fā)效率。

針對(duì)上述問(wèn)題，從解決SDAN-AS鏈路擁塞、提升業(yè)務(wù)轉(zhuǎn)發(fā)效率的角度，首先通過(guò)FLIP混合更新算法對(duì)各業(yè)務(wù)流的更新順序進(jìn)行規(guī)范，得到表示更新順序的操作序列；在此基礎(chǔ)上，設(shè)計(jì)鏈路擁塞的感知算法，并在混合更新算法中加入鏈路擁塞的感知，對(duì)操作序列加以約束條件，進(jìn)一步改進(jìn)混合更新算法提出基于擁塞避免的網(wǎng)絡(luò)更新算法(congestion avoidance based algorithm of update, CA-AU)，以增加鏈路感知能力，減少鏈路擁塞的發(fā)生，從而提高SDAN-AS的業(yè)務(wù)轉(zhuǎn)發(fā)效率及網(wǎng)絡(luò)更新可靠性。

1 相關(guān)理論與模型構(gòu)建

1.1 理論介紹

現(xiàn)有針對(duì)SDN網(wǎng)絡(luò)的更新算法主要分為3類，分別為：次序更新[8]、兩階段提交更新[9]以及混合更新[10]。其中，次序更新通過(guò)計(jì)算交換機(jī)轉(zhuǎn)發(fā)規(guī)則的替換順序來(lái)保證網(wǎng)絡(luò)更新的準(zhǔn)確和可靠，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)該方法具有較高的可靠性且更新速度較快、效率較高；兩階段提交更新通過(guò)在交換機(jī)上同時(shí)保留業(yè)務(wù)流的新、舊轉(zhuǎn)發(fā)規(guī)則，并在網(wǎng)絡(luò)入口給業(yè)務(wù)流打標(biāo)簽，決定業(yè)務(wù)流的轉(zhuǎn)發(fā)規(guī)則來(lái)保證網(wǎng)絡(luò)更新的準(zhǔn)確和可靠。但研究發(fā)現(xiàn)，當(dāng)網(wǎng)絡(luò)規(guī)模較大、交換機(jī)數(shù)量較多時(shí)，使用次序更新方法可能無(wú)法保證網(wǎng)絡(luò)更新過(guò)程的準(zhǔn)確和可靠；而當(dāng)存在交換機(jī)的內(nèi)存不足以額外存儲(chǔ)一套新的轉(zhuǎn)發(fā)規(guī)則時(shí)，無(wú)法使用兩階段提交更新方法?？梢钥闯?，當(dāng)航空集群規(guī)模較大時(shí)，次序更新方法不適用；當(dāng)集群成員存在內(nèi)存不足的情況時(shí)，兩階段提交方法不適用。因此，本文后續(xù)基于混合更新方法，加入對(duì)鏈路擁塞的感知，提出適用于航空集群機(jī)載網(wǎng)絡(luò)的更新策略。下面對(duì)混合更新算法——FLIP(fast lightweight policy)進(jìn)行介紹。

算法首先將更新問(wèn)題分解至每一條業(yè)務(wù)流，并對(duì)每條業(yè)務(wù)流獨(dú)立計(jì)算各自的操作序列。算法以一個(gè)網(wǎng)絡(luò)更新問(wèn)題作為輸入，具體內(nèi)容包括：網(wǎng)絡(luò)初始狀態(tài)(拓?fù)?、?jié)點(diǎn)和鏈路的相關(guān)信息)、最終狀態(tài)下的路由以及需要維護(hù)的給定策略。算法輸出為所有業(yè)務(wù)流子操作序列混合所得的操作序列。其中，后一個(gè)子序列中的任何操作需在前一個(gè)子序列中的所有操作完成后執(zhí)行。

算法首先提取各操作之間的順序來(lái)保證更新過(guò)程中的轉(zhuǎn)發(fā)正確性，不出現(xiàn)更新過(guò)程中的中間狀態(tài)無(wú)可匹配的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，或數(shù)據(jù)包在有限節(jié)點(diǎn)間相互轉(zhuǎn)發(fā)的情況。其次，提取保留給定策略的約束條件，以保證更新過(guò)程中不違背給定的轉(zhuǎn)發(fā)規(guī)則。當(dāng)保留給定策略約束條件與部分轉(zhuǎn)發(fā)正確性約束條件之間存在矛盾時(shí)，需要求解線性規(guī)劃以確定一組更新開(kāi)銷最低的更新操作序列。

1.2 場(chǎng)景及架構(gòu)描述

圖1直觀地展示了SDAN-AS的基本架構(gòu)。與SDN相同，SDAN-AS將整個(gè)網(wǎng)絡(luò)在邏輯上由南到北分割成3個(gè)平面，分別為數(shù)據(jù)平面、控制平面和應(yīng)用平面[9]。其中，數(shù)據(jù)平面由負(fù)責(zé)數(shù)據(jù)存儲(chǔ)與轉(zhuǎn)發(fā)的網(wǎng)元設(shè)備組成(簡(jiǎn)稱為數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)備)。這些數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)備的通信系統(tǒng)通常搭載于航空集群成員中的中小型空中平臺(tái)(例如戰(zhàn)斗機(jī)、偵察機(jī)、電子干擾機(jī)、無(wú)人機(jī)等)之上?？刂破矫嬗韶?fù)責(zé)邏輯集中地掌控網(wǎng)絡(luò)全局的網(wǎng)絡(luò)控制器組成。這些網(wǎng)絡(luò)控制器的通信系統(tǒng)通常搭載于航空集群成員中的大型空中平臺(tái)(例如預(yù)警機(jī)和指通機(jī))之上[11]。通過(guò)南向接口，網(wǎng)絡(luò)控制器可以及時(shí)地掌握全局網(wǎng)絡(luò)視圖并向底層的數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)備下發(fā)相關(guān)指令消息。通過(guò)北向接口，網(wǎng)絡(luò)控制器能夠向上層實(shí)時(shí)地反饋底層網(wǎng)絡(luò)狀態(tài)信息，以便網(wǎng)絡(luò)應(yīng)用根據(jù)網(wǎng)絡(luò)的實(shí)際情況進(jìn)行動(dòng)態(tài)調(diào)整，達(dá)到全網(wǎng)最優(yōu)。應(yīng)用平面由網(wǎng)絡(luò)需要的、用戶定義的各種業(yè)務(wù)與應(yīng)用組成[12]。

圖1 SDAN-AS網(wǎng)絡(luò)架構(gòu)

為了更加直觀地對(duì)SDAN-AS網(wǎng)絡(luò)更新問(wèn)題進(jìn)行描述，本文將SDAN-AS網(wǎng)絡(luò)建模為一個(gè)無(wú)向圖Ω=(V,E,C)，其中V={v1,v2,…,vM}表示網(wǎng)絡(luò)拓?fù)鋬?nèi)的全體節(jié)點(diǎn)的集合，M表示拓?fù)鋬?nèi)節(jié)點(diǎn)的數(shù)量。E={(vs,vd)|vs,vd∈V}表示網(wǎng)絡(luò)拓?fù)渲墟溌返募?；C表示全體控制器集合，其構(gòu)成SDAN-AS網(wǎng)絡(luò)的控制平面。顯然有C?V。接下來(lái)針對(duì)SDAN-AS網(wǎng)絡(luò)更新中的相關(guān)變量進(jìn)行定義：W={w1,w2,…,wm}表示當(dāng)前網(wǎng)絡(luò)更新過(guò)程中的待更新節(jié)點(diǎn)集合，顯然有W?V，m表示待更新節(jié)點(diǎn)數(shù)量；Λ={f1,f2,…,fn}表示待更新業(yè)務(wù)流集合，n表示待更新業(yè)務(wù)流數(shù)量。

2 基于擁塞避免的SDAN-AS自適應(yīng)更新策略

2.1 總體策略

圖2為策略流程，包括更新問(wèn)題收集階段(上半部分)和更新操作約束求解階段(下半部分)。

圖2 基于擁塞避免的SDAN-AS自適應(yīng)更新策略流程圖

其中，更新問(wèn)題收集階段實(shí)現(xiàn)了SDAN-AS當(dāng)前網(wǎng)絡(luò)狀態(tài)的采集以及更新問(wèn)題的初步解析。具體包括①當(dāng)前網(wǎng)絡(luò)狀態(tài)信息的采集。SDAN-AS網(wǎng)絡(luò)控制器對(duì)當(dāng)前網(wǎng)絡(luò)狀態(tài)信息進(jìn)行采集，采集的信息包括：網(wǎng)絡(luò)拓?fù)洹⒐?jié)點(diǎn)和鏈路的相關(guān)信息(包括節(jié)點(diǎn)間鏈路的鏈路容量、網(wǎng)絡(luò)中處于傳輸狀態(tài)的業(yè)務(wù)流的優(yōu)先級(jí)以及占用的鏈路容量等)。②業(yè)務(wù)流轉(zhuǎn)發(fā)路徑的采集?？刂破魍ㄟ^(guò)北向接口，從應(yīng)用平面獲取高層次網(wǎng)絡(luò)控制邏輯以及網(wǎng)絡(luò)管控需求，包括網(wǎng)絡(luò)更新完成后需實(shí)現(xiàn)的業(yè)務(wù)流的轉(zhuǎn)發(fā)路徑以及更新過(guò)程中需保留的給定策略。

更新操作序列求解階段生成網(wǎng)絡(luò)更新操作序列，實(shí)現(xiàn)SDAN-AS網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)策略的更新，并保證更新過(guò)程中的一致性。該階段包括：

1)網(wǎng)絡(luò)更新問(wèn)題的分解。根據(jù)更新問(wèn)題收集階段輸入的網(wǎng)絡(luò)初始轉(zhuǎn)發(fā)策略、規(guī)劃的轉(zhuǎn)發(fā)策略、保留的給定策略以及預(yù)測(cè)的鏈路狀態(tài)，提取出每條業(yè)務(wù)流需要保留的轉(zhuǎn)發(fā)規(guī)則以及轉(zhuǎn)發(fā)正確性需求，作為FLIP算法的輸入。此外將鏈路狀態(tài)信息作為基于擁塞避免的SDAN-AS更新算法的輸入，具體算法細(xì)節(jié)將在2.2節(jié)闡述。

2)連接一致性與策略一致性約束條件計(jì)算。FLIP算法中的基本操作類型包括：①規(guī)則替換操作rep(s,f)，在節(jié)點(diǎn)s上對(duì)業(yè)務(wù)流f執(zhí)行的以最終規(guī)則替換當(dāng)前規(guī)則的操作；②標(biāo)簽操作tag(s,f,θ)，在節(jié)點(diǎn)s上對(duì)業(yè)務(wù)流f執(zhí)行對(duì)其所有數(shù)據(jù)包打上標(biāo)簽θ的操作；③匹配操作match(s,f,θi,θf(wàn))。在節(jié)點(diǎn)s上執(zhí)行安裝初始和最終規(guī)則，并對(duì)業(yè)務(wù)流f中的新數(shù)據(jù)包打上標(biāo)簽θf(wàn)、舊數(shù)據(jù)包打上標(biāo)簽θi的操作。當(dāng)保證連接一致性與策略一致性的約束條件存在矛盾時(shí)，需迭代求解線性規(guī)劃問(wèn)題：

(1)

該線性規(guī)劃問(wèn)題的目標(biāo)為尋找一組更新操作序列，使更新開(kāi)銷最低。其中，constrains onrep(i,f)表示全體替換操作的次序約束，當(dāng)該線性規(guī)劃問(wèn)題無(wú)解時(shí)，通過(guò)標(biāo)簽-匹配操作取代更新序列中部分節(jié)點(diǎn)替換操作，從而化解約束矛盾，最終計(jì)算得到該線性規(guī)劃問(wèn)題最優(yōu)解更新序列作為算法輸出。

因此，根據(jù)網(wǎng)絡(luò)更新的連接一致性與策略一致性需求，基于FLIP算法分別計(jì)算每條業(yè)務(wù)流的更新操作序列。首先通過(guò)線性函數(shù)求解該條業(yè)務(wù)流的規(guī)則切換操作序列rep(s,f)。若該線性函數(shù)無(wú)實(shí)解，則通過(guò)基于兩階段提交機(jī)制的標(biāo)簽-匹配操作tag(s,f,θ)-match(s,f,θi,θf(wàn))，代替部分節(jié)點(diǎn)的rep(s,f)操作，生成新的操作序列。

3)容量一致性約束條件計(jì)算：基于FLIP計(jì)算得到的業(yè)務(wù)流操作序列，根據(jù)網(wǎng)絡(luò)更新的容量一致性需求，通過(guò)基于擁塞避免的自適應(yīng)更新算法以及排隊(duì)退避算法對(duì)網(wǎng)絡(luò)更新的容量一致性約束進(jìn)行計(jì)算，提取新的業(yè)務(wù)流更新操作次序約束。若現(xiàn)有更新操作無(wú)法避免更新過(guò)程中產(chǎn)生的擁塞，則進(jìn)一步通過(guò)排隊(duì)退避算法，將部分低優(yōu)先級(jí)業(yè)務(wù)流加入擁塞鏈路前序節(jié)點(diǎn)的緩存隊(duì)列中，待高優(yōu)先級(jí)業(yè)務(wù)流完成更新后釋放緩存恢復(fù)轉(zhuǎn)發(fā)。

2.2 基于擁塞避免的SDAN-AS更新算法

2.2.1 SDAN-AS網(wǎng)絡(luò)更新?lián)砣兄?/p>

算法1 鏈路擁塞感知算法

輸入：F,VOL,CAP

輸出：C，Ψ

1)C=?

2)fori=1→ndo

4)endfor

5)forekinEdo

6)volek=0,Ψek=?,i=1

7)whileek∈Traceido

8)volek=volek+voli

9)Ψek=Ψek∪f(wàn)i

10)i=i+1

11)endwhile

12)ifvolek>capek

13)C=C∪ek

14)endif

15)endfor

設(shè)計(jì)SDAN-AS網(wǎng)絡(luò)更新?lián)砣兄惴ㄈ缦?。算法輸入包括全體待更新業(yè)務(wù)流路徑集合F={Fi|1≤i≤n}、占用的鏈路容量VOL={voli|1≤i≤n}、當(dāng)前網(wǎng)絡(luò)中全體鏈路的容量CAP={capek|ek∈E}，其中E表示網(wǎng)絡(luò)中全體鏈路集合。算法輸出為潛在擁塞鏈路集合C以及各鏈路經(jīng)過(guò)的業(yè)務(wù)流集合Ψ。此外，Tracei表示業(yè)務(wù)流在更新過(guò)程中所有轉(zhuǎn)發(fā)路徑遍歷的鏈路集合。

算法1第1行對(duì)鏈路擁塞感知集合進(jìn)行初始化；第2～4行計(jì)算得到全體業(yè)務(wù)流在更新過(guò)程中所遍歷的鏈路；第5～15行計(jì)算鏈路擁塞狀態(tài)，其中第7～11行計(jì)算每條鏈路上可能經(jīng)過(guò)的業(yè)務(wù)流量，若超出該條鏈路的容量，該條鏈路在更新過(guò)程中可能出現(xiàn)擁塞情況，將被加入集合C，同時(shí)將該條鏈路上可能經(jīng)過(guò)的業(yè)務(wù)流加入集合Ψ中。

2.2.2 基于擁塞避免的自適應(yīng)更新算法

根據(jù)總體更新策略，在獲取網(wǎng)絡(luò)更新過(guò)程中的鏈路擁塞狀態(tài)后，通過(guò)基于擁塞避免的自適應(yīng)更新算法計(jì)算混合更新操作序列約束。

算法2 基于擁塞避免的自適應(yīng)更新算法(CA-AU)

輸入：網(wǎng)絡(luò)更新流相關(guān)信息I=(PRI,SEQ,VOI,F)

擁塞狀態(tài)信息L=(C,Ψ,CAP)

輸出：混合更新操作序列約束集合Cons

1)Cons=?

3)forfiinΨekdo

5)m=j

6)else

7)continue

8)endif

9)Ωi=?,Γi={fx∈Ψek|prix

10)forfjinΓido

12)Ωi=Ωi∪f(wàn)j

14)endif

16)break

17)endif

18)endfor

20)QueueRetreat()

21)endif

22)endfor

算法2第1行首先對(duì)混合更新操作序列約束集合Cons進(jìn)行初始化，之后通過(guò)第2～24行，逐鏈路添加混合更新操作序列約束。其中，第4～9行判斷流在更新后的轉(zhuǎn)發(fā)路徑是否經(jīng)過(guò)當(dāng)前潛在的擁塞鏈路，若經(jīng)過(guò)則記錄造成擁塞的更新操作序號(hào)，否則，繼續(xù)分析更低一級(jí)優(yōu)先級(jí)的業(yè)務(wù)流更新操作子序列。第10～19行依次在優(yōu)先級(jí)低于fi的業(yè)務(wù)流更新操作子序列中搜索可釋放鏈路容量的更新操作，并添加進(jìn)混合更新操作序列約束集合Cons中。若在Ψek中搜索完畢后，ek的鏈路容量仍無(wú)法保證無(wú)擁塞更新，此時(shí)調(diào)用排隊(duì)退避算法QueueRetreat()，對(duì)ek上的部分低處理優(yōu)先級(jí)業(yè)務(wù)流添加排隊(duì)退避以及恢復(fù)轉(zhuǎn)發(fā)更新操作約束。本文對(duì)排隊(duì)退避操作以及恢復(fù)轉(zhuǎn)發(fā)操作定義如下：

定義1 排隊(duì)等待操作queue(f,v,e)：在節(jié)點(diǎn)v上將業(yè)務(wù)流f中通過(guò)鏈路e轉(zhuǎn)發(fā)的數(shù)據(jù)包加入緩存隊(duì)列中，此時(shí)業(yè)務(wù)流f暫停在鏈路e上的傳輸，但不影響流f在該節(jié)點(diǎn)上的更新。

定義2 恢復(fù)轉(zhuǎn)發(fā)操作recov(f,v,e)：在節(jié)點(diǎn)v的緩存隊(duì)列中，將屬于業(yè)務(wù)流f的數(shù)據(jù)包通過(guò)鏈路e轉(zhuǎn)發(fā)。顯然，對(duì)于一條業(yè)務(wù)流f，存在約束：queue(f,v,e)

算法3QuecueRetreat( )

輸入：網(wǎng)絡(luò)更新流相關(guān)信息I=(PRI,SEQ,VOI,F)

擁塞狀態(tài)信息L=(C,Ψ,CAP)

fi的更新退避業(yè)務(wù)流集合Ω

Ψek中優(yōu)先級(jí)低于fi的業(yè)務(wù)流集合Γi

輸出：排隊(duì)退避約束集合Cons_QRi

1)Cons_QRi=?,Φi=?

2)whileΓi≠?

6)endif

8)break

9)endif

10)endwhile

11)whileΦi≠?

12)l=1

16)l=l+1

17)endwhile

算法3輸入包括待更新流相關(guān)信息I=(PRI,SEQ,VOI,F)；擁塞狀態(tài)信息L=(C,Ψ,CAP)；流fi的更新退避業(yè)務(wù)流集合Ωi；Ψek中優(yōu)先級(jí)低于fi的業(yè)務(wù)流集合Γi。輸出為業(yè)務(wù)流fi的排隊(duì)退避約束集合Cons_ORi。算法中Φi表示流fi的排隊(duì)退避業(yè)務(wù)流集合，數(shù)組quei與reci分別保存了排隊(duì)退避操作與恢復(fù)轉(zhuǎn)發(fā)操作，若有j

圖3給出一個(gè)基于擁塞避免的自適應(yīng)更新算法示例。圖中共有fi、f2與f33條待更新業(yè)務(wù)流,優(yōu)先級(jí)pri1[B],E,H,G,D]，所需保留的轉(zhuǎn)發(fā)策略為P(f2)={[G,H],[H,G]}；f3的初始轉(zhuǎn)發(fā)路徑與最終轉(zhuǎn)發(fā)路徑分別為與F3=[A,B,F,C,H]與∑Ψ[E,G]vol-volf2≤capek，即在執(zhí)行操作rep(E,f2)后鏈路上不再產(chǎn)生擁塞。因此，添加混合更新操作序列約束rep(E,f2)

同理，對(duì)于潛在擁塞鏈路[F,C]，為保證f1的無(wú)擁塞更新，在Ψ[F,C]={f1,f3}中搜索f3的更新操作子序列。不同的是，f3在更新前后均經(jīng)過(guò)了鏈路[F,C]，無(wú)法通過(guò)更新退避約束實(shí)現(xiàn)f1的無(wú)擁塞更新。此時(shí)調(diào)用QueueRetreat()算法，并添加排隊(duì)退避約束條件queue(f3,F,[F,C])

經(jīng)過(guò)鏈路擁塞感知算法可以計(jì)算得到潛在的擁塞鏈路為:C={[E,G],[F,C]},兩條鏈路上經(jīng)過(guò)的業(yè)務(wù)流集合分別為:Ψ[E,G]={f1,f2}和Ψ[F,C]={f1,f3},然后通過(guò)基于擁塞避免的自適應(yīng)更新算法計(jì)算混合更新操作序列的約束'對(duì)于潛在擁塞鏈路[E,G],首先計(jì)算保證高優(yōu)先級(jí)業(yè)務(wù)流f1的無(wú)擁塞更新的約束條件,在Ψ[E,G]={f1,f2}中搜索低優(yōu)先級(jí)業(yè)務(wù)流f2的更新操作子序列。其中,操作可以在使f2的轉(zhuǎn)發(fā)路徑從鏈路[E,G]切 換為[E,H]從而釋放鏈路[E,G]上的容量,且此時(shí)滿足∑Ψ[E,G]vol-volf2≤capek，即在執(zhí)行操作rep(E,f2)后鏈路上不再產(chǎn)生擁塞。因此，添加混合更新操作序列約束rep(E,f2)

同理，對(duì)于潛在擁塞鏈路[F,C]，為保證f1的無(wú)擁塞更新，在Ψ[F,C]={f1,f3}中搜索f3的更新操作子序列。不同的是，f3在更新前后均經(jīng)過(guò)了鏈路[F,C]，無(wú)法通過(guò)更新退避約束實(shí)現(xiàn)f1的無(wú)擁塞更新。此時(shí)調(diào)用QueueRetreat()算法，并添加排隊(duì)退避約束條件queue(f3,F,[F,C])

3 仿真結(jié)果與分析

本節(jié)將CA-AU更新策略與幾種典型的SDN更新算法在SDAN-AS網(wǎng)絡(luò)環(huán)境下進(jìn)行仿真分析，并對(duì)幾類關(guān)鍵性能指標(biāo)進(jìn)行比較，驗(yàn)證CA-AU的性能。選取的對(duì)比更新算法包括次序更新算法、FLIP混合更新算法以及zUpdate更新算法[13]。選取的性能評(píng)價(jià)指標(biāo)為更新平均排隊(duì)時(shí)延和平均更新成功率。仿真參數(shù)設(shè)置如表1所示，其中，網(wǎng)絡(luò)中各業(yè)務(wù)流所占用的鏈路容量服從均值為5，方差為1的正態(tài)分布；各業(yè)務(wù)流優(yōu)先級(jí)服從最小值為1，最大值為10的均勻分布。仿真實(shí)驗(yàn)參照Rocketfuel拓?fù)鋄14]，實(shí)驗(yàn)過(guò)程中可對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行增減。當(dāng)對(duì)指定自變量參數(shù)進(jìn)行仿真分析時(shí)，其他自變量參數(shù)設(shè)置為平均值。

表1 仿真參數(shù)

圖4為一次成功的網(wǎng)絡(luò)更新過(guò)程中，各待更新業(yè)務(wù)流的平均排隊(duì)時(shí)延隨網(wǎng)絡(luò)規(guī)模變化的趨勢(shì)。

圖4 排隊(duì)時(shí)延與網(wǎng)絡(luò)規(guī)模關(guān)系

參與對(duì)比的更新策略分別為CA-AU策略與FLIP混合更新算法，通過(guò)對(duì)比可以發(fā)現(xiàn)，隨網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的提升，F(xiàn)LIP與CA-AU的排隊(duì)時(shí)延均呈現(xiàn)指數(shù)式上升的趨勢(shì)。而FLIP的平均排隊(duì)時(shí)延始終遠(yuǎn)高于CA-AU。在網(wǎng)絡(luò)規(guī)模為20個(gè)節(jié)點(diǎn)時(shí)，平均時(shí)延已接近100s，其原因在于FLIP算法雖然充分考慮了單條業(yè)務(wù)流的轉(zhuǎn)發(fā)正確性需求與給定策略需求，但沒(méi)有考慮鏈路擁塞對(duì)網(wǎng)絡(luò)更新的影響。擁塞現(xiàn)象易造成網(wǎng)絡(luò)需要通過(guò)多次序列計(jì)算以及指令下發(fā)過(guò)程才能最終成功完成更新；相比之下，CA-AU的更新平均時(shí)延顯著降低，隨網(wǎng)絡(luò)規(guī)模增至120個(gè)節(jié)點(diǎn)，其平均時(shí)延始終保持在10s以下。CA-AU的平均更新排隊(duì)時(shí)延主要來(lái)源于低優(yōu)先級(jí)業(yè)務(wù)流的主動(dòng)排隊(duì)退避。

圖5為一次成功的網(wǎng)絡(luò)更新過(guò)程中，各待更新業(yè)務(wù)流的平均排隊(duì)時(shí)延隨待更新業(yè)務(wù)流變化的趨勢(shì)。在該組實(shí)驗(yàn)中，網(wǎng)絡(luò)規(guī)模設(shè)置為70個(gè)節(jié)點(diǎn)。仿真結(jié)果表明，隨業(yè)務(wù)流的增長(zhǎng)，各流平均更新排隊(duì)時(shí)延呈現(xiàn)更加急劇的指數(shù)增長(zhǎng)，原因在于業(yè)務(wù)流數(shù)量的增長(zhǎng)直接造成網(wǎng)絡(luò)中鏈路擁塞現(xiàn)象的加劇，從而導(dǎo)致FLIP算法執(zhí)行時(shí)，需要更多次的更新周期完成一次成功的網(wǎng)絡(luò)更新；而對(duì)于CA-AU算法，擁塞鏈路的增加也造成低優(yōu)先級(jí)業(yè)務(wù)流需要在更多的擁塞鏈路的前序節(jié)點(diǎn)上進(jìn)行排隊(duì)退避。但排隊(duì)退避所引起的平均排隊(duì)時(shí)延相較于FLIP算法仍顯著降低。

圖5 排隊(duì)時(shí)延與業(yè)務(wù)流量關(guān)系

圖6為一次成功的網(wǎng)絡(luò)更新過(guò)程中，待更新業(yè)務(wù)流的平均排隊(duì)時(shí)延隨平均飛行速度之間的關(guān)系。為驗(yàn)證CA-AU在SDAN-AS高度動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境下的適應(yīng)性，在該組實(shí)驗(yàn)中選取了zUpdate無(wú)擁塞更新策略作為對(duì)比。zUpdate是一種數(shù)據(jù)中心網(wǎng)絡(luò)環(huán)境下的無(wú)擁塞更新方案，通過(guò)對(duì)比可以發(fā)現(xiàn)，隨著飛行速度的提升，zUpdate與CA-AU的平均更新排隊(duì)時(shí)延均明顯上升，表明隨著網(wǎng)絡(luò)動(dòng)態(tài)性的提升，zUpdate與CA-AU的適應(yīng)性均有一定程度的下降。其中，zUpdate的平均排隊(duì)時(shí)延在飛行速度較低時(shí)低于CA-AU，這是因?yàn)閦Update可提供無(wú)擁塞的更新方案，而CA-AU則需要對(duì)部分低優(yōu)先級(jí)的業(yè)務(wù)流進(jìn)行主動(dòng)的排隊(duì)退避。然而隨平均飛行速度的提升，zUpdate的平均排隊(duì)時(shí)延急劇上升，并在飛行速度達(dá)到500km/h時(shí)開(kāi)始高于CA-AU。這是因?yàn)镃A-AU策略通過(guò)鏈路擁塞感知，對(duì)潛在的擁塞鏈路進(jìn)行了更新約束的計(jì)算，相比于適用于靜態(tài)網(wǎng)絡(luò)環(huán)境的zUpdate，在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下具有更高的容錯(cuò)與適應(yīng)性能。

圖6 排隊(duì)時(shí)延與飛行速度關(guān)系

圖7為網(wǎng)絡(luò)更新成功率隨網(wǎng)絡(luò)規(guī)模的變化趨勢(shì)，該組仿真實(shí)驗(yàn)選取次序更新作為對(duì)照，在不同規(guī)模下的網(wǎng)絡(luò)中，采用相同的網(wǎng)絡(luò)拓?fù)涓鲌?zhí)行100次重復(fù)實(shí)驗(yàn)?？梢园l(fā)現(xiàn)，隨網(wǎng)絡(luò)規(guī)模的提升，次序更新的更新成功率均呈指數(shù)式下降，隨網(wǎng)絡(luò)規(guī)模的提升，次序更新與CA-AU更新成功率的差距持續(xù)增大，當(dāng)網(wǎng)絡(luò)規(guī)模達(dá)到120個(gè)節(jié)點(diǎn)時(shí)，更新成功率降至20%以下。而CA-AU的更新成功率雖也隨著網(wǎng)絡(luò)規(guī)模的提升而下降，但在網(wǎng)絡(luò)規(guī)模提升至120個(gè)節(jié)點(diǎn)的過(guò)程中始終保持在90%以上。該實(shí)驗(yàn)結(jié)果表明，在鏈路狀態(tài)不穩(wěn)定的機(jī)載網(wǎng)絡(luò)環(huán)境下，基于混合更新的CA-AU相比于次序更新的可靠性有了大幅提升，同時(shí)也表明相比于次序更新，CA-AU具有更強(qiáng)的魯棒性，可在更加復(fù)雜的網(wǎng)絡(luò)環(huán)境下獲取理想的更新效率。

圖7 更新成功率與網(wǎng)絡(luò)規(guī)模關(guān)系

4 結(jié)語(yǔ)

本文面向軟件定義航空集群機(jī)載網(wǎng)絡(luò)的特殊復(fù)雜環(huán)境，研究適用于該網(wǎng)絡(luò)的更新策略。首先，基于混合更新算法計(jì)算理想鏈路狀態(tài)下業(yè)務(wù)流的更新操作序列，隨后針對(duì)每條業(yè)務(wù)流做擁塞鏈路的感知，并根據(jù)鏈路擁塞情況提出擁塞避免算法，基于業(yè)務(wù)流優(yōu)先級(jí)生成無(wú)擁塞的更新操作約束，以實(shí)現(xiàn)網(wǎng)絡(luò)更新的準(zhǔn)確、可靠性。仿真結(jié)果表明，本文提出的更新策略在更新過(guò)程中降低排隊(duì)時(shí)延的同時(shí)，提高了更新的成功率。