適應拓撲變化的擁塞最小化網(wǎng)絡更新策略

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

1. 空軍工程大學 信息與導航學院，西安 710077 2. 中國人民解放軍94860部隊，南京 210000

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

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

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

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

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

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

上述網(wǎng)絡更新策略[10,16-18]能夠較好地保證網(wǎng)絡更新期間的擁塞一致性，但這些策略主要關注于地面有線網(wǎng)絡，網(wǎng)絡拓撲是固定不變的，未針對無線網(wǎng)絡的特點進行考慮。然而航空集群作戰(zhàn)場景下的網(wǎng)絡拓撲隨著作戰(zhàn)任務和需求的變化而變化。拓撲變化必然導致部分舊轉(zhuǎn)發(fā)路徑失效，繼續(xù)在其上傳輸業(yè)務時將產(chǎn)生嚴重的數(shù)據(jù)包丟失現(xiàn)象[19]，現(xiàn)有的網(wǎng)絡更新策略不能適應SDAN-AS的需求。本文針對上述問題，提出適應拓撲變化的擁塞最小化更新策略(Congestion-Minimizing for Topological Changes，CM-TC)，考慮拓撲變化的影響，對受影響的業(yè)務流采用重路由機制進行處理，并設計貪婪流遷移算法降低產(chǎn)生的網(wǎng)絡擁塞，最后通過擁塞最小化更新算法完成整個網(wǎng)絡更新。

1 問題描述

1.1 網(wǎng)絡模型

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

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

在SDAN-AS場景中，由于作戰(zhàn)任務、作戰(zhàn)需求的變化，網(wǎng)絡拓撲在較長的時間跨度上呈現(xiàn)出較大的變化，但在較短的時間跨度上，網(wǎng)絡拓撲的變化可以視為局部的、小范圍的變化。網(wǎng)絡拓撲的變化可以是由于節(jié)點/鏈路故障或節(jié)點間相對運動所導致的。如圖1(a)所示，對于源節(jié)點為1，目的節(jié)點為4的流f，通過打上不同的VLAN標簽將流f拆分到多條路徑進行傳輸，流f的路徑集合為Po(f)={p1,p2,p3}，p1、p2、p3為圖1(a)中實線箭頭所指路徑。每條路徑上的節(jié)點根據(jù)標簽進行相應的轉(zhuǎn)發(fā)，在源節(jié)點1處為每條路徑分配權重實現(xiàn)流量分配。

圖1 拓撲變化前后的網(wǎng)絡狀態(tài)Fig.1 Network state before and after topology change

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

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

2 更新策略

為解決由于網(wǎng)絡拓撲變化導致的初始網(wǎng)絡狀態(tài)中部分可用路徑失效的問題，本文基于CM算法提出CM-TC更新策略。本節(jié)首先描述CM-TC更新策略的流程，再對策略中的相關算法進行詳細介紹。

2.1 CM-TC更新策略描述

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

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

階段1控制器根據(jù)收集到的當前網(wǎng)絡拓撲信息，檢測失效路徑集合Pa，以及受失效路徑影響的流集合Fa。若失效路徑存在，則執(zhí)行階段2，若無失效路徑，則執(zhí)行階段4。

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

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

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

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

2.2 算法描述

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

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

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

2.2.1 重路由機制

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

s.t.

(1)

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

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

2.2.2 貪婪流遷移算法

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

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

對應圖3(c)中，首先找出擁塞最大的鏈路e(5,7)，經(jīng)過該鏈路的流為f1和f2，剩余容量Cr(f1,p7)=Cr(f2,p8)=1，因此任選其一進行遷移即可。選擇將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)所示。此時網(wǎng)絡無擁塞，算法終止。

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

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

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

2.2.3 最小化瞬時擁塞更新算法

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

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

定義1最小化瞬時擁塞更新

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

定義2瞬時擁塞

(2)

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

(3)

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

3 仿真結果及分析

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

3.1 仿真參數(shù)設置

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

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

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

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

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

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

3.2 仿真結果分析

圖5為網(wǎng)絡更新期間丟失數(shù)據(jù)包數(shù)目的比較，可以看出One Shot、SWAN、CM這3種算法的丟包率遠遠高于CM-TC。由于該場景中網(wǎng)絡節(jié)點隨機移動，網(wǎng)絡拓撲動態(tài)變化，當網(wǎng)絡拓撲發(fā)生變化時，初始網(wǎng)絡狀態(tài)中的部分路徑將會失效，繼續(xù)在其上傳輸業(yè)務將會丟失大量數(shù)據(jù)包。而One Shot、SWAN、CM并沒有考慮到網(wǎng)絡拓撲的變化，3種算法隨著業(yè)務流速率的增大將會丟失大量數(shù)據(jù)包。其中，由于One Shot直接從初始網(wǎng)絡狀態(tài)同時更新所有交換機到最終網(wǎng)絡狀態(tài)，導致網(wǎng)絡過度擁塞，因此丟失了大量數(shù)據(jù)包。CM和SWAN都采用了中間狀態(tài)進行過渡，CM中擁塞較小、SWAN中無擁塞，但由于需要相對較長的更新時間而導致失效路徑上的數(shù)據(jù)包丟失較多。而CM-TC采用了重路由機制，將受影響的業(yè)務流分配到失效路徑上的流量，線性規(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)絡更新過程中擁塞鏈路的瞬時鏈路利用率比較，SWAN為無擁塞更新算法，因此這里不做比較。CM算法和CM-TC算法中，設定中間狀態(tài)數(shù)目為3。從仿真結果可以看出，One Shot算法的最大瞬時鏈路利用率達到了將近200%，正是由于One Shot直接同時更新網(wǎng)絡中所有交換機所導致的嚴重網(wǎng)絡擁塞。而CM和CM-TC算法都大大降低了網(wǎng)絡更新中出現(xiàn)的瞬時擁塞，最大瞬時鏈路利用率只有大約130%，與One Shot算法相比，最大瞬時擁塞降低了約30.73%。在實際運行的網(wǎng)絡中，對彈性流量和優(yōu)先級較低的業(yè)務流而言，短暫的速率降低或流量擁塞是可以忍受的，因此CM和CM-TC算法帶來的瞬時鏈路擁塞是可以接受的。CM-TC相比于CM算法效果稍稍有所降低，這是由于CM-TC采用的重路由機制在大大減少數(shù)據(jù)包丟失的情況下也帶來了一定的網(wǎng)絡擁塞，但兩者基本處于同一水平，CM-TC算法在降低網(wǎng)絡更新期間的瞬時擁塞方面仍然表現(xiàn)出較好的水平。

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

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

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

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

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

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

4 結 論

1) 提出的CM-TC算法對拓撲變化進行考慮，在更新之前采用重路由機制進行處理，與其他擁塞一致性更新算法相比，大大降低了丟包率，減少了拓撲變化導致的網(wǎng)絡更新期間的嚴重數(shù)據(jù)包丟失。

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

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