呂娜，陳坤,*，陳柯帆，朱海峰，潘武

1. 空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安 710077 2. 中國人民解放軍94860部隊(duì)，南京 210000

伴隨著戰(zhàn)爭形態(tài)向信息化、網(wǎng)絡(luò)化和智能化的演變，為提升航空作戰(zhàn)平臺(tái)效能發(fā)揮，航空集群作戰(zhàn)的概念被提出。由一定數(shù)量、能力各異的有人/無人航空平臺(tái)組成航空集群，以網(wǎng)絡(luò)為中心，根據(jù)作戰(zhàn)需求進(jìn)行靈活高效的組織協(xié)同，從而實(shí)現(xiàn)平臺(tái)間優(yōu)勢互補(bǔ)，最大限度提升作戰(zhàn)效能[1]。

機(jī)載網(wǎng)絡(luò)作為各航空集群成員信息傳輸、共享的承載，是進(jìn)行高效協(xié)同作戰(zhàn)的核心前提。而當(dāng)下以各類數(shù)據(jù)鏈為代表的機(jī)載網(wǎng)絡(luò)依然采用傳統(tǒng)的分布式網(wǎng)絡(luò)體系架構(gòu)，網(wǎng)絡(luò)的維護(hù)和管理復(fù)雜僵化[2]。與內(nèi)部協(xié)議緊耦合的網(wǎng)絡(luò)設(shè)備，只能根據(jù)所需網(wǎng)絡(luò)服務(wù)添加越來越多的協(xié)議，難以升級(jí)和拓展功能，嚴(yán)重制約了機(jī)載網(wǎng)絡(luò)的作戰(zhàn)效能發(fā)揮。

軟件定義網(wǎng)絡(luò)(Software-Defined Networking, SDN)為航空集群機(jī)載網(wǎng)絡(luò)的發(fā)展打開了新局面[3]。SDN將控制功能從網(wǎng)絡(luò)設(shè)備中獨(dú)立出來，采用邏輯集中的控制器進(jìn)行統(tǒng)一監(jiān)視與管控，控制平面與數(shù)據(jù)平面的解耦使得對網(wǎng)絡(luò)的集中管控和資源的靈活調(diào)度變得更加簡單[4-6]。文獻(xiàn)[7]將SDN范式與機(jī)載網(wǎng)絡(luò)相融合，提出軟件定義航空集群機(jī)載網(wǎng)絡(luò)(Software-Defined Airborne Network of Aviation Swarm, SDAN-AS)，但機(jī)載網(wǎng)絡(luò)引入SDN帶來諸多好處的同時(shí)也為網(wǎng)絡(luò)的一致性更新帶來了一系列新的挑戰(zhàn)。

在SDN中，為了響應(yīng)流量需求變化、鏈路或節(jié)點(diǎn)故障、安全策略變化等事件，需要頻繁地更新網(wǎng)絡(luò)狀態(tài)[8]。而網(wǎng)絡(luò)狀態(tài)的更新依賴于對交換機(jī)轉(zhuǎn)發(fā)規(guī)則的更改，需要在一系列交換機(jī)上添加、刪除或修改流表規(guī)則。盡管SDN提供了邏輯集中的控制，但本質(zhì)上依然是復(fù)雜的異步分布式系統(tǒng)[9]。由于控制器與交換機(jī)之間存在固有的不可預(yù)測的延遲，且交換機(jī)反應(yīng)和處理時(shí)間存在差異，即使控制器同時(shí)下發(fā)所有的更改指令，更改指令到達(dá)各交換機(jī)的時(shí)間不同，各交換機(jī)成功更改轉(zhuǎn)發(fā)規(guī)則的時(shí)間也不同[10]。這將導(dǎo)致網(wǎng)絡(luò)更新期間可能出現(xiàn)交換機(jī)轉(zhuǎn)發(fā)規(guī)則不一致，繼而產(chǎn)生如轉(zhuǎn)發(fā)循環(huán)、路由黑洞、鏈路擁塞等問題，從而影響業(yè)務(wù)傳輸?shù)挠行院涂煽啃?，?yán)重降低網(wǎng)絡(luò)性能[10-12]。因此，網(wǎng)絡(luò)更新成為亟待解決的挑戰(zhàn)性問題，即如何在滿足網(wǎng)絡(luò)一致性的情況下，將初始網(wǎng)絡(luò)狀態(tài)轉(zhuǎn)變?yōu)樽罱K網(wǎng)絡(luò)狀態(tài)。

近年來，研究人員針對各種不同的一致性要求對網(wǎng)絡(luò)更新問題開展了大量研究。針對無環(huán)一致性，文獻(xiàn)[13]提出依賴林算法，文獻(xiàn)[14]提出反向更新算法，保證了更新期間數(shù)據(jù)包傳輸無環(huán)路。文獻(xiàn)[9]針對數(shù)據(jù)包一致性提出兩階段更新機(jī)制，保證在網(wǎng)絡(luò)更新期間每個(gè)數(shù)據(jù)包只單一按照舊的路徑或者按照新的路徑轉(zhuǎn)發(fā)，而不是兩者的混合。而后,文獻(xiàn)[15]提出增量兩階段更新，將更新過程劃分為多個(gè)輪次，犧牲更新時(shí)間來換取流表規(guī)則開銷的減少。上述2種更新策略只能保證網(wǎng)絡(luò)更新期間數(shù)據(jù)包的一致性，無法滿足擁塞一致性，即在網(wǎng)絡(luò)更新期間不產(chǎn)生擁塞。

為實(shí)現(xiàn)無擁塞網(wǎng)絡(luò)更新，文獻(xiàn)[16]提出了SWAN(Software-driven WAN)更新系統(tǒng)，為網(wǎng)絡(luò)中每條鏈路預(yù)留空閑容量s，通過線性規(guī)劃求解一系列中間狀態(tài)，并證明了至多需要1/s-1次更新即可實(shí)現(xiàn)無擁塞網(wǎng)絡(luò)更新。但SWAN必須始終預(yù)留一部分鏈路容量，犧牲了網(wǎng)絡(luò)帶寬資源利用率。文獻(xiàn)[17]拓展了SWAN中的線性規(guī)劃公式，提出擁塞最小化(Congestion-Minimizing，CM)更新算法，采用隨機(jī)舍入法近似計(jì)算出給定最大瞬時(shí)擁塞情況下的最小化中間階段數(shù)目的更新，用一定的擁塞換取更新速度的提高。文獻(xiàn)[10] 提出Dionysus更新系統(tǒng)，構(gòu)建全局依賴關(guān)系圖并根據(jù)交換機(jī)間的依賴關(guān)系進(jìn)行動(dòng)態(tài)更新，從而提高網(wǎng)絡(luò)更新速度。文獻(xiàn)[18]提出Cupid更新系統(tǒng)，通過關(guān)鍵節(jié)點(diǎn)將全局依賴圖轉(zhuǎn)化為具有潛在擁塞鏈路的局部依賴圖，有效加快更新速度。

上述網(wǎng)絡(luò)更新策略[10,16-18]能夠較好地保證網(wǎng)絡(luò)更新期間的擁塞一致性，但這些策略主要關(guān)注于地面有線網(wǎng)絡(luò)，網(wǎng)絡(luò)拓?fù)涫枪潭ú蛔兊?，未針對無線網(wǎng)絡(luò)的特點(diǎn)進(jìn)行考慮。然而航空集群作戰(zhàn)場景下的網(wǎng)絡(luò)拓?fù)潆S著作戰(zhàn)任務(wù)和需求的變化而變化。拓?fù)渥兓厝粚?dǎo)致部分舊轉(zhuǎn)發(fā)路徑失效，繼續(xù)在其上傳輸業(yè)務(wù)時(shí)將產(chǎn)生嚴(yán)重的數(shù)據(jù)包丟失現(xiàn)象[19]，現(xiàn)有的網(wǎng)絡(luò)更新策略不能適應(yīng)SDAN-AS的需求。本文針對上述問題，提出適應(yīng)拓?fù)渥兓膿砣钚』虏呗?Congestion-Minimizing for Topological Changes，CM-TC)，考慮拓?fù)渥兓挠绊?，對受影響的業(yè)務(wù)流采用重路由機(jī)制進(jìn)行處理，并設(shè)計(jì)貪婪流遷移算法降低產(chǎn)生的網(wǎng)絡(luò)擁塞，最后通過擁塞最小化更新算法完成整個(gè)網(wǎng)絡(luò)更新。

1 問題描述

1.1 網(wǎng)絡(luò)模型

在問題描述之前，首先引入本文的網(wǎng)絡(luò)模型。本文將軟件定義航空集群機(jī)載網(wǎng)絡(luò)抽象為無向圖G=(V,E)。其中V={v1,v2,…,vm}表示網(wǎng)絡(luò)中交換機(jī)的集合，E={e1,e2,…,en}表示鏈路集合。對于?e∈E，Ce表示該鏈路的容量。μ={μe1,μe2,…,μen}表示網(wǎng)絡(luò)鏈路利用率的集合。Go表示初始網(wǎng)絡(luò)狀態(tài)，Gn表示最終網(wǎng)絡(luò)狀態(tài)。F={f1,f2,…,fk}表示網(wǎng)絡(luò)中業(yè)務(wù)流的集合，對于?f∈F，df表示該流的需求，將每條流分別打上不同的VLAN(Virtual Local Area Network)標(biāo)簽將流拆分到多條路徑進(jìn)行傳輸。Po(f)表示Go中的流f的路徑集合，Pn(f)表示Gn中流f的路徑集合，Pa(f)?Po(f)表示Go中流f已失效路徑的集合，F(xiàn)a表示受失效路徑影響的流的集合。

1.2 網(wǎng)絡(luò)更新問題描述

在SDAN-AS場景中，由于作戰(zhàn)任務(wù)、作戰(zhàn)需求的變化，網(wǎng)絡(luò)拓?fù)湓谳^長的時(shí)間跨度上呈現(xiàn)出較大的變化，但在較短的時(shí)間跨度上，網(wǎng)絡(luò)拓?fù)涞淖兓梢砸暈榫植康?、小范圍的變化。網(wǎng)絡(luò)拓?fù)涞淖兓梢允怯捎诠?jié)點(diǎn)/鏈路故障或節(jié)點(diǎn)間相對運(yùn)動(dòng)所導(dǎo)致的。如圖1(a)所示，對于源節(jié)點(diǎn)為1，目的節(jié)點(diǎn)為4的流f，通過打上不同的VLAN標(biāo)簽將流f拆分到多條路徑進(jìn)行傳輸，流f的路徑集合為Po(f)={p1,p2,p3}，p1、p2、p3為圖1(a)中實(shí)線箭頭所指路徑。每條路徑上的節(jié)點(diǎn)根據(jù)標(biāo)簽進(jìn)行相應(yīng)的轉(zhuǎn)發(fā)，在源節(jié)點(diǎn)1處為每條路徑分配權(quán)重實(shí)現(xiàn)流量分配。

圖1 拓?fù)渥兓昂蟮木W(wǎng)絡(luò)狀態(tài)Fig.1 Network state before and after topology change

當(dāng)網(wǎng)絡(luò)拓?fù)溆蓤D1(a)轉(zhuǎn)變?yōu)閳D1(b)時(shí)，節(jié)點(diǎn)2和節(jié)點(diǎn)3之間的鏈路中斷，路徑集合中的p1已經(jīng)失效，然而節(jié)點(diǎn)1～節(jié)點(diǎn)4交換機(jī)中的轉(zhuǎn)發(fā)規(guī)則沒有更改，流f依舊按照p1路徑進(jìn)行傳輸，節(jié)點(diǎn)2 在接收到來自節(jié)點(diǎn)1的數(shù)據(jù)包后，依舊會(huì)按照舊的轉(zhuǎn)發(fā)規(guī)則將數(shù)據(jù)包向節(jié)點(diǎn)3轉(zhuǎn)發(fā)，鏈路e(2,3)的中斷將導(dǎo)致數(shù)據(jù)包無法到達(dá)節(jié)點(diǎn)3，從而導(dǎo)致p1路徑上的數(shù)據(jù)包無法到達(dá)目的節(jié)點(diǎn)4，造成嚴(yán)重的數(shù)據(jù)包丟失。此時(shí)，在流量工程周期內(nèi)，控制器將會(huì)根據(jù)當(dāng)前網(wǎng)絡(luò)拓?fù)浼傲髁啃枨笥?jì)算出全網(wǎng)新的最優(yōu)轉(zhuǎn)發(fā)路徑，如圖1(b)中的虛線所示，計(jì)算出的新轉(zhuǎn)發(fā)路徑集合為Pn(f)={p′1,p′2,p′3}，p′1、p′2、p′3為圖1(b)中虛線箭頭所指路徑。圖1(b)中的實(shí)線部分構(gòu)成初始網(wǎng)絡(luò)狀態(tài)Go，虛線部分構(gòu)成最終網(wǎng)絡(luò)狀態(tài)Gn。

網(wǎng)絡(luò)更新就是將網(wǎng)絡(luò)狀態(tài)從Go轉(zhuǎn)換到Gn的中間過程，即將流量從Go中的舊轉(zhuǎn)發(fā)路徑Po(f)遷移到Gn中的新轉(zhuǎn)發(fā)路徑Pn(f)上的中間過程[20]。

2 更新策略

為解決由于網(wǎng)絡(luò)拓?fù)渥兓瘜?dǎo)致的初始網(wǎng)絡(luò)狀態(tài)中部分可用路徑失效的問題，本文基于CM算法提出CM-TC更新策略。本節(jié)首先描述CM-TC更新策略的流程，再對策略中的相關(guān)算法進(jìn)行詳細(xì)介紹。

2.1 CM-TC更新策略描述

CM-TC更新策略流程如圖2所示。

圖2 CM-TC更新策略流程Fig.2 Process of CM-TC update strategy

階段1控制器根據(jù)收集到的當(dāng)前網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑱z測失效路徑集合Pa，以及受失效路徑影響的流集合Fa。若失效路徑存在，則執(zhí)行階段2，若無失效路徑，則執(zhí)行階段4。

階段2將每條受失效路徑影響的流f*∈Fa重路由到未失效的路徑集合Po(f*)-Pa(f*)上，控制器執(zhí)行重路由機(jī)制計(jì)算未失效路徑上的流量分配，下發(fā)指令修改入口交換機(jī)流表中的路徑流量分配權(quán)重xf,p。同時(shí)在網(wǎng)絡(luò)中添加每條流的新轉(zhuǎn)發(fā)路徑的流表規(guī)則，刪除失效路徑的流表規(guī)則。

階段3在新轉(zhuǎn)發(fā)路徑的流表規(guī)則添加成功之后，若網(wǎng)絡(luò)中存在擁塞，則執(zhí)行貪婪流遷移算法，具體算法細(xì)節(jié)將在2.2節(jié)進(jìn)行詳細(xì)闡述。

階段4執(zhí)行最小化瞬時(shí)擁塞更新算法，通過線性規(guī)劃計(jì)算出給定數(shù)目的中間網(wǎng)絡(luò)狀態(tài)，將網(wǎng)絡(luò)從初始網(wǎng)絡(luò)狀態(tài)逐個(gè)轉(zhuǎn)變?yōu)樽罱K狀態(tài)Gn，完成網(wǎng)絡(luò)更新。

控制器周期性地執(zhí)行網(wǎng)絡(luò)更新策略，首先執(zhí)行階段1進(jìn)行失效路徑檢測，當(dāng)檢測到舊轉(zhuǎn)發(fā)路徑中存在部分路徑失效時(shí)，即按照策略階段順序執(zhí)行。若無路徑失效，即無需執(zhí)行階段1和階段2，直接執(zhí)行階段4的最小化瞬時(shí)擁塞更新算法。

2.2 算法描述

本節(jié)配合圖3和圖4對CM-TC更新策略中的相應(yīng)算法進(jìn)行描述。

圖3 階段2中的網(wǎng)絡(luò)狀態(tài)Fig.3 Network state in the second stage

圖4 階段3中的網(wǎng)絡(luò)狀態(tài)Fig.4 Network state in the third stage

2.2.1 重路由機(jī)制

當(dāng)舊轉(zhuǎn)發(fā)路徑中存在失效路徑時(shí)，更新策略進(jìn)入階段2。此時(shí)新轉(zhuǎn)發(fā)路徑的流表規(guī)則還沒有添加，由于每條業(yè)務(wù)流新轉(zhuǎn)發(fā)路徑的流表規(guī)則添加需要在該路徑上的所有交換機(jī)上添加新的流表規(guī)則，同時(shí)受影響的流數(shù)目較多，因此流表規(guī)則的添加需要一定時(shí)間，在該段時(shí)間內(nèi)網(wǎng)絡(luò)只能按照舊轉(zhuǎn)發(fā)路徑傳輸?？紤]到繼續(xù)在失效路徑上傳輸業(yè)務(wù)會(huì)導(dǎo)致嚴(yán)重的數(shù)據(jù)包丟失，首先要將受影響的流在失效路徑上的流量轉(zhuǎn)移到未失效路徑上，即使這可能產(chǎn)生一定的擁塞，但仍優(yōu)于在失效路徑上繼續(xù)傳輸帶來的直接數(shù)據(jù)包丟失。同時(shí)為了盡可能地減少擁塞，從全局出發(fā)重新計(jì)算受影響的流在未失效路徑上的流量分配權(quán)重，從而最大限度地最小化網(wǎng)絡(luò)最大鏈路擁塞。因此，問題形式化為

s.t.

(1)

線性規(guī)劃式(1)的目標(biāo)函數(shù)，即最小化網(wǎng)絡(luò)最大鏈路利用率。約束條件第1條表示網(wǎng)絡(luò)流量需求守恒；第2條表示受路徑失效影響的流f∈Fa在失效路徑p∈Pa(f)上的權(quán)重為0，其中xf,p表示重路由后流f分配到路徑p上的流量權(quán)重。第3條表示流的多路徑路由約束，由于重路由機(jī)制只將受影響流在失效路徑上的流量進(jìn)行重路由，未失效路徑上的并不變動(dòng)，因此受影響流重路由之后的流量分配權(quán)重將大于等于其舊的網(wǎng)絡(luò)狀態(tài)中的流量分配權(quán)重，其中xf,p表示舊的網(wǎng)絡(luò)狀態(tài)中的流f分配到路徑p上的流量權(quán)重；第4條表示未受影響的流的流量分配權(quán)重保持不變。通過標(biāo)準(zhǔn)線性規(guī)劃求解器對線性規(guī)劃式(1)進(jìn)行求解即可計(jì)算出重路由之后轉(zhuǎn)發(fā)路徑上的流量分配，即重路由之后的網(wǎng)絡(luò)配置。

如圖3(a)中，每條鏈路的容量為1，節(jié)點(diǎn)1～節(jié)點(diǎn)7的流f1通過紅色的3條路徑進(jìn)行傳輸，節(jié)點(diǎn)2～節(jié)點(diǎn)7的業(yè)務(wù)流f2通過藍(lán)色的3條路徑進(jìn)行傳輸。2條業(yè)務(wù)流的需求都為2，路徑上的流量劃分見圖中標(biāo)注。當(dāng)節(jié)點(diǎn)4～節(jié)點(diǎn)7之間的鏈路故障時(shí)，檢測到p2和p4這2條路徑失效后，執(zhí)行重路由機(jī)制，將其上的流量重路由到未失效的其他路徑上，通過線性規(guī)劃計(jì)算出的流量劃分如圖3(b) 所示。在圖3(c)中，虛線表示的p7和p8為添加的新路徑，p2和p4這2條失效路徑已被刪除。

2.2.2 貪婪流遷移算法

在執(zhí)行完重路由機(jī)制且新轉(zhuǎn)發(fā)路徑的流表規(guī)則已添加成功后，更新策略進(jìn)入階段3。盡管階段2中的重路由機(jī)制減少了數(shù)據(jù)包的直接丟失，但可能會(huì)使網(wǎng)絡(luò)產(chǎn)生一定程度的擁塞。CM算法利用短暫的網(wǎng)絡(luò)瞬時(shí)擁塞換取網(wǎng)絡(luò)更新時(shí)間的減少，在更新期間會(huì)產(chǎn)生瞬時(shí)擁塞，而執(zhí)行完重路由機(jī)制后的網(wǎng)絡(luò)是存在一定擁塞的，若直接執(zhí)行CM算法將網(wǎng)絡(luò)轉(zhuǎn)變到最終網(wǎng)絡(luò)狀態(tài)，難以達(dá)到CM算法原有的效果，與CM算法在常規(guī)網(wǎng)絡(luò)更新中達(dá)到的效果相比，將會(huì)在網(wǎng)絡(luò)更新期間產(chǎn)生更大程度的擁塞。因此需要在執(zhí)行CM算法之前盡可能地通過流量遷移降低網(wǎng)絡(luò)擁塞。

針對重路由機(jī)制帶來的網(wǎng)絡(luò)擁塞問題，在階段3中設(shè)計(jì)貪婪流遷移算法以降低網(wǎng)絡(luò)擁塞程度，如算法1所示。首先找出鏈路利用率最大的鏈路e*，若該鏈路存在擁塞，則將經(jīng)過該鏈路的所有業(yè)務(wù)流添加到集合F*中；然后對于集合F*中的每一條業(yè)務(wù)流f，計(jì)算其轉(zhuǎn)發(fā)路徑中的剩余容量Cr(f,p)；之后找出剩余容量最大的流f*以及對應(yīng)的剩余容量最大的路徑p*；再將流f*經(jīng)過鏈路e*的路徑上的流量遷移到具有最大剩余容量的路徑p*上；循環(huán)上述過程，直至控制器檢測到網(wǎng)絡(luò)無擁塞或無法找到具有剩余容量的路徑時(shí)終止算法。

對應(yīng)圖3(c)中，首先找出擁塞最大的鏈路e(5,7)，經(jīng)過該鏈路的流為f1和f2，剩余容量Cr(f1,p7)=Cr(f2,p8)=1，因此任選其一進(jìn)行遷移即可。選擇將f1在p3上的流量部分遷移到p7上，流量劃分如圖4(a)所示。然后找出圖4(a)中擁塞最大的鏈路e(3,7)，經(jīng)過該鏈路的流為f1，剩余容量Cr(f1,p7)=2/3，因此將f1在p1上的部分流量遷移到p7上，流量劃分如圖4(b)所示。再找出圖4(b)中擁塞最大的鏈路e(6,7)，經(jīng)過該鏈路的流為f2，剩余容量Cr(f2,p8)=1/3，因此將f2在p6上的部分流量遷移到p8上，流量劃分如圖4(c)所示。此時(shí)網(wǎng)絡(luò)無擁塞，算法終止。

算法1:貪婪流遷移算法輸入:鏈路集合E;流集合F;鏈路容量C;路徑集合P;流需求集合df;當(dāng)前網(wǎng)絡(luò)配置xf,p;鏈路利用率集合μ輸出:貪婪流遷移后的網(wǎng)絡(luò)流量配置xf,p1. Whileμmax>1do;網(wǎng)絡(luò)存在擁塞開始循環(huán)2. F*=Φ, Cr=Φ, e* = argmax (μ)進(jìn)行變量初始化3. for eachf∈Fdo4. if 流f的轉(zhuǎn)發(fā)路徑p經(jīng)過鏈路e*then5. 將流f添加到集合F*中6. 標(biāo)記流f經(jīng)過e*的路徑pc(f)=p7. end if8. end for9. for eachf∈F*do10. for eachp∈P(f)do11. if?e∈p都滿足μe<1then12. 計(jì)算流f在路徑p上的剩余容量Cr(f,p)13. end if14. end for15. end for16. ifCr==Φthen17. break18. end if19. (f*,p*)=argmax Cr(f,p) ;找出空閑容量最大的流f*以及對應(yīng)的路徑p*20. T=min(df*·(xf*,pc(f*)-1),Cr(f*,p*));計(jì)算待遷移的流量值T21. xf*,p*=xf*,p*+T/df*;增加流f*在路徑p*上的流量權(quán)重22. xf*,pc(f*)=xf*,pc(f*)-T/df*;減少流f*在路徑pc(f*)上的流量權(quán)重23. 執(zhí)行算法1更新集合μ24. end while

貪婪流遷移算法每次對擁塞最大的鏈路上的流量進(jìn)行遷移，貪婪地占用具有最大剩余容量的路徑，從而減少遷移次數(shù)，在較短的時(shí)間內(nèi)盡可能地降低擁塞流的數(shù)目、降低最大鏈路擁塞。擁塞流遷移的實(shí)現(xiàn)，通過控制器向該流的入口交換機(jī)下發(fā)指令修改流表中轉(zhuǎn)發(fā)路徑上流量分配權(quán)重完成。

算法1第1行表示，當(dāng)網(wǎng)絡(luò)最大鏈路利用率μmax>1時(shí)開始循環(huán)；第2行進(jìn)行變量初始化和賦值，其中，e*表示網(wǎng)絡(luò)鏈路利用率最大的鏈路，F(xiàn)*表示經(jīng)過鏈路e*的流的集合，Cr表示剩余容量。第3～8行將經(jīng)過擁塞最高的鏈路e*的流f加入到集合F*中，并標(biāo)記出每條流f∈F*經(jīng)過鏈路e*的路徑pc(f)=p；第9～15行計(jì)算出每一條流f∈F*的每一條路徑p∈P(f)的剩余容量Cr(f,p)；第16～18行表示，若任何一條流的任何一條路徑都沒有剩余容量則終止算法；第19行找出剩余容量最大的流f*及其對應(yīng)的路徑p*；第20～22行將流f*在擁塞路徑pc(f*)上的流量部分遷移到存在剩余容量的路徑p*上；第23行執(zhí)行算法1更新鏈路利用率集合μ；之后進(jìn)行循環(huán)，直至μmax<1或在經(jīng)過e*的流中無法找到存在剩余容量的路徑，則結(jié)束算法循環(huán)。

2.2.3 最小化瞬時(shí)擁塞更新算法

在更新策略進(jìn)入階段4之后，網(wǎng)絡(luò)擁塞已經(jīng)得到較好的緩解，此時(shí)采用最小化瞬時(shí)擁塞更新算法，計(jì)算出給定數(shù)目中間狀態(tài)的網(wǎng)絡(luò)配置。

假設(shè)給定網(wǎng)絡(luò)更新期間中間狀態(tài)數(shù)目為n，則網(wǎng)絡(luò)狀態(tài)集合為S={S0,S1,…,Sn+1}，其中S0表示初始網(wǎng)絡(luò)狀態(tài)，Sn+1表示最終網(wǎng)絡(luò)狀態(tài)，Si(i∈{1,2,…,n})表示第i個(gè)中間狀態(tài)，Si→Si+1表示網(wǎng)絡(luò)從第i個(gè)狀態(tài)轉(zhuǎn)變?yōu)榈趇+1個(gè)狀態(tài)的更新過程。

定義1最小化瞬時(shí)擁塞更新

已知S0和Sn+1狀態(tài)下的網(wǎng)絡(luò)配置，計(jì)算n個(gè)中間狀態(tài)的網(wǎng)絡(luò)配置，從而最小化網(wǎng)絡(luò)更新期間的瞬時(shí)擁塞。

定義2瞬時(shí)擁塞

(2)

因此最小化瞬時(shí)擁塞更新算法可以形式化為

(3)

線性規(guī)劃式(3)的目標(biāo)函數(shù)，即最小化網(wǎng)絡(luò)最大瞬時(shí)鏈路利用率。約束條件的第1條表示在任意的Si→Si+1期間，任意鏈路e在最嚴(yán)重的情況下的擁塞程度不超過μ，即鏈路e上待減少的流量還沒有減少，但待增加的流量已經(jīng)增加了；第2條表示網(wǎng)絡(luò)流量需求守恒；第3條表示受路徑失效影響的流f∈Fa在失效路徑p∈Pa(f)上的權(quán)重為0，約束第4條表示流的多路徑路由約束。通過求解線性規(guī)劃式(2)即可計(jì)算出最小化網(wǎng)絡(luò)擁塞更新期間n個(gè)中間狀態(tài)對應(yīng)的網(wǎng)絡(luò)配置。

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

本文的仿真實(shí)驗(yàn)運(yùn)行在CPU為Intel Xeon，主頻為3.2 GHz，內(nèi)存16 GB的商用服務(wù)器上。本文采用的仿真軟件為Exata 5.1網(wǎng)絡(luò)仿真軟件。EXata是針對新型無線通信技術(shù)而設(shè)計(jì)的半實(shí)物網(wǎng)絡(luò)仿真平臺(tái)，精確程度與真實(shí)網(wǎng)絡(luò)相媲美，采用先進(jìn)的并行算法，能夠仿真上千個(gè)節(jié)點(diǎn)的大型無線網(wǎng)絡(luò)，特別適合集群式計(jì)算系統(tǒng)的復(fù)雜仿真項(xiàng)目。本節(jié)基于EXata網(wǎng)絡(luò)仿真平臺(tái)對本文提出的CM-TC網(wǎng)絡(luò)更新策略進(jìn)行仿真分析。同時(shí)與One Shot、SWAN、CM等網(wǎng)絡(luò)更新算法進(jìn)行比較，從而驗(yàn)證分析其性能。

3.1 仿真參數(shù)設(shè)置

仿真參數(shù)設(shè)置如表1所示。在仿真區(qū)域內(nèi)隨機(jī)生成網(wǎng)絡(luò)節(jié)點(diǎn)，仿真場景區(qū)域根據(jù)航空集群作戰(zhàn)范圍設(shè)定為1 000 km×1 000 km，節(jié)點(diǎn)數(shù)目由小規(guī)模到大規(guī)模集群在20～100范圍內(nèi)變化，根據(jù)節(jié)點(diǎn)通信半徑生成網(wǎng)絡(luò)拓?fù)鋱D，節(jié)點(diǎn)通信半徑為當(dāng)前航空數(shù)據(jù)鏈系統(tǒng)的穩(wěn)定傳輸距離200 km每個(gè)節(jié)點(diǎn)隨機(jī)移動(dòng)，節(jié)點(diǎn)移動(dòng)速率按照作戰(zhàn)飛機(jī)巡航速度從低速到高速在200～1 200 km·h-1的范圍內(nèi)變化。然后在節(jié)點(diǎn)間隨機(jī)生成業(yè)務(wù)流，其需求服從均值為5、方差為1的正態(tài)分布?？刂破鞲鶕?jù)全網(wǎng)視圖從全局出發(fā)為每條業(yè)務(wù)流計(jì)算出多條邊不相交的路徑，將每條業(yè)務(wù)流拆分到多條路徑進(jìn)行傳輸，通過線性規(guī)劃計(jì)算流量劃分，并將轉(zhuǎn)發(fā)規(guī)則下發(fā)到每個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)根據(jù)轉(zhuǎn)發(fā)規(guī)則進(jìn)行流量轉(zhuǎn)發(fā)、處理。而后在每一個(gè)流量工程周期內(nèi)根據(jù)當(dāng)前網(wǎng)絡(luò)拓?fù)渲匦掠?jì)算新轉(zhuǎn)發(fā)路徑，執(zhí)行網(wǎng)絡(luò)更新策略。

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameter setting

仿真選擇對比的算法描述如下：

1) SWAN。該算法為無擁塞更新算法，將初始網(wǎng)絡(luò)狀態(tài)和最終網(wǎng)絡(luò)狀態(tài)作為輸入，通過線性規(guī)劃，計(jì)算出一系列的中間狀態(tài)，從而實(shí)現(xiàn)無擁塞網(wǎng)絡(luò)更新。由于該算法需要為每條鏈路預(yù)留一定的帶寬，不會(huì)產(chǎn)生擁塞，在本場景中只進(jìn)行流表規(guī)則數(shù)目和丟失數(shù)據(jù)包數(shù)目的比較。

2) One Shot。該算法是指直接由控制器向網(wǎng)絡(luò)中的所有交換機(jī)節(jié)點(diǎn)下發(fā)所有的流表，所有交換機(jī)同時(shí)更新，沒有中間狀態(tài)過渡，直接由初始網(wǎng)絡(luò)狀態(tài)更新到最終網(wǎng)絡(luò)狀態(tài)。

3) CM。該算法以給定的中間狀態(tài)數(shù)以及網(wǎng)絡(luò)的初始和最終狀態(tài)作為輸入，通過線性規(guī)劃，求解出一系列中間網(wǎng)絡(luò)狀態(tài)，從而實(shí)現(xiàn)給定中間狀態(tài)數(shù)情況下的最小擁塞更新。

3.2 仿真結(jié)果分析

圖5為網(wǎng)絡(luò)更新期間丟失數(shù)據(jù)包數(shù)目的比較，可以看出One Shot、SWAN、CM這3種算法的丟包率遠(yuǎn)遠(yuǎn)高于CM-TC。由于該場景中網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)移動(dòng)，網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化，當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，初始網(wǎng)絡(luò)狀態(tài)中的部分路徑將會(huì)失效，繼續(xù)在其上傳輸業(yè)務(wù)將會(huì)丟失大量數(shù)據(jù)包。而One Shot、SWAN、CM并沒有考慮到網(wǎng)絡(luò)拓?fù)涞淖兓?種算法隨著業(yè)務(wù)流速率的增大將會(huì)丟失大量數(shù)據(jù)包。其中，由于One Shot直接從初始網(wǎng)絡(luò)狀態(tài)同時(shí)更新所有交換機(jī)到最終網(wǎng)絡(luò)狀態(tài)，導(dǎo)致網(wǎng)絡(luò)過度擁塞，因此丟失了大量數(shù)據(jù)包。CM和SWAN都采用了中間狀態(tài)進(jìn)行過渡，CM中擁塞較小、SWAN中無擁塞，但由于需要相對較長的更新時(shí)間而導(dǎo)致失效路徑上的數(shù)據(jù)包丟失較多。而CM-TC采用了重路由機(jī)制，將受影響的業(yè)務(wù)流分配到失效路徑上的流量，線性規(guī)劃后重路由到其他的可用路徑上，大大減少了更新數(shù)據(jù)包的丟失。相比于SWAN和CM算法，CM-TC降低了約81.32%的數(shù)據(jù)包丟失。

圖5 丟失數(shù)據(jù)包數(shù)目比較Fig.5 Comparison of number of lost packets

圖6為網(wǎng)絡(luò)更新過程中擁塞鏈路的瞬時(shí)鏈路利用率比較，SWAN為無擁塞更新算法，因此這里不做比較。CM算法和CM-TC算法中，設(shè)定中間狀態(tài)數(shù)目為3。從仿真結(jié)果可以看出，One Shot算法的最大瞬時(shí)鏈路利用率達(dá)到了將近200%，正是由于One Shot直接同時(shí)更新網(wǎng)絡(luò)中所有交換機(jī)所導(dǎo)致的嚴(yán)重網(wǎng)絡(luò)擁塞。而CM和CM-TC算法都大大降低了網(wǎng)絡(luò)更新中出現(xiàn)的瞬時(shí)擁塞，最大瞬時(shí)鏈路利用率只有大約130%，與One Shot算法相比，最大瞬時(shí)擁塞降低了約30.73%。在實(shí)際運(yùn)行的網(wǎng)絡(luò)中，對彈性流量和優(yōu)先級(jí)較低的業(yè)務(wù)流而言，短暫的速率降低或流量擁塞是可以忍受的，因此CM和CM-TC算法帶來的瞬時(shí)鏈路擁塞是可以接受的。CM-TC相比于CM算法效果稍稍有所降低，這是由于CM-TC采用的重路由機(jī)制在大大減少數(shù)據(jù)包丟失的情況下也帶來了一定的網(wǎng)絡(luò)擁塞，但兩者基本處于同一水平，CM-TC算法在降低網(wǎng)絡(luò)更新期間的瞬時(shí)擁塞方面仍然表現(xiàn)出較好的水平。

圖6 瞬時(shí)鏈路利用率比較Fig.6 Comparison of instantaneous link utilization

圖7為網(wǎng)絡(luò)更新過程中產(chǎn)生擁塞的業(yè)務(wù)流數(shù)目，擁塞業(yè)務(wù)流的數(shù)目隨著業(yè)務(wù)流總數(shù)目的增加基本呈現(xiàn)線性增加。由于One Shot算法沒有中間過渡狀態(tài)，同時(shí)更新網(wǎng)絡(luò)中的所有交換機(jī)，導(dǎo)致網(wǎng)絡(luò)中將近85%的業(yè)務(wù)流產(chǎn)生擁塞。與之相比，CM和CM-TC算法避免了網(wǎng)絡(luò)更新期間大部分業(yè)務(wù)流的擁塞，只有接近30%的業(yè)務(wù)流受到影響。CM-TC相較于CM算法，擁塞業(yè)務(wù)流數(shù)目有所上升，但差距并不明顯，說明由重路由機(jī)制帶來的網(wǎng)絡(luò)擁塞經(jīng)過貪婪流遷移算法的處理后有了較大的改善，效果較好。

圖7 擁塞業(yè)務(wù)流數(shù)目比較Fig.7 Comparison of congested flow numbers

圖8為網(wǎng)絡(luò)更新期間產(chǎn)生的流表規(guī)則開銷，即添加、修改和刪除的流表規(guī)則數(shù)目。可以看出，One Shot算法對應(yīng)的流表規(guī)則開銷最低，SWAN算法對應(yīng)的流表規(guī)則開銷遠(yuǎn)遠(yuǎn)高于CM與CM-TC。One Shot算法沒有中間狀態(tài)過渡，只需要添加、修改和刪除必要的流表，因此具有最低的流表規(guī)則開銷。與之相反，SWAN算法為了實(shí)現(xiàn)無擁塞的更新需要更多數(shù)目的中間狀態(tài)進(jìn)行過渡，帶來了最多的流表規(guī)則開銷。CM與CM-TC不追求無擁塞更新，旨在實(shí)現(xiàn)限定中間狀態(tài)數(shù)目情況下的最小擁塞更新，只需要較少數(shù)目的中間狀態(tài)即可完成網(wǎng)絡(luò)更新，從而實(shí)現(xiàn)了較小的流表規(guī)則開銷。與SWAN算法相比，CM-TC降低了約41%的流表規(guī)則開銷；與CM算法相比，僅僅增加了5%左右的流表規(guī)則開銷。

圖8 流表規(guī)則開銷比較Fig.8 Comparison of overhead of rules

根據(jù)以上仿真結(jié)果，可以看出，CM和CM-TC算法能夠有效簡化網(wǎng)絡(luò)更新問題，犧牲較少的網(wǎng)絡(luò)性能換取更新速度提高的同時(shí)，減少了流表規(guī)則開銷。本文提出的CM-TC算法在網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化的航空集群場景中，與傳統(tǒng)擁塞一致性更新算法相比，顯著減少了網(wǎng)絡(luò)更新期間的數(shù)據(jù)包丟失。雖然采用了重路由機(jī)制可能產(chǎn)生一定的擁塞，但本文進(jìn)一步設(shè)計(jì)的貪婪流遷移算法有效降低了網(wǎng)絡(luò)更新期間的瞬時(shí)擁塞，減少了擁塞流數(shù)目。與CM算法相比，在規(guī)則開銷、網(wǎng)絡(luò)擁塞方面仍然表現(xiàn)較好，同時(shí)顯著降低了網(wǎng)絡(luò)更新期間的數(shù)據(jù)包丟失。

4 結(jié) 論

1) 提出的CM-TC算法對拓?fù)渥兓M(jìn)行考慮，在更新之前采用重路由機(jī)制進(jìn)行處理，與其他擁塞一致性更新算法相比，大大降低了丟包率，減少了拓?fù)渥兓瘜?dǎo)致的網(wǎng)絡(luò)更新期間的嚴(yán)重?cái)?shù)據(jù)包丟失。

2) 針對重路由機(jī)制導(dǎo)致的擁塞上升進(jìn)一步設(shè)計(jì)了貪婪流遷移算法，有效地降低了網(wǎng)絡(luò)更新期間的瞬時(shí)擁塞。

3) CM-TC用規(guī)則開銷、網(wǎng)絡(luò)擁塞方面的少量提高換取了網(wǎng)絡(luò)更新期間數(shù)據(jù)包丟失的顯著降低，適應(yīng)航空集群場景的網(wǎng)絡(luò)更新需求。