基于定時(shí)的航空集群機(jī)載網(wǎng)絡(luò)更新方法

陳 坤,呂 娜,朱海峰,方 宇

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

0 引 言

航空集群作戰(zhàn)作為未來(lái)空中作戰(zhàn)的主要樣式,已被廣泛研究和深入發(fā)展。受生物集群?jiǎn)l(fā),在多航空平臺(tái)間形成高效信息共享,實(shí)現(xiàn)平臺(tái)間靈活協(xié)作,突破單一平臺(tái)的弱勢(shì)短板,繼而涌現(xiàn)出遠(yuǎn)超個(gè)體的強(qiáng)大體系作戰(zhàn)能力[1]。

機(jī)載網(wǎng)絡(luò)是集群成員間信息交互的基礎(chǔ)承載,機(jī)載網(wǎng)絡(luò)的信息交互能力是保證航空集群作戰(zhàn)效能發(fā)揮的關(guān)鍵[2]。當(dāng)前的機(jī)載網(wǎng)絡(luò)組網(wǎng)方式固定,網(wǎng)絡(luò)設(shè)備與內(nèi)部協(xié)議緊耦合,難以實(shí)現(xiàn)互操作,無(wú)法滿足航空集群作戰(zhàn)的信息交互需求,制約了平臺(tái)的效能發(fā)揮和體系作戰(zhàn)能力的全面提升。

為向機(jī)載網(wǎng)絡(luò)提供與多任務(wù)靈活耦合的網(wǎng)絡(luò)服務(wù),實(shí)現(xiàn)簡(jiǎn)單高效的網(wǎng)絡(luò)管控,軟件定義航空集群機(jī)載網(wǎng)絡(luò)[3](software-defined airborne network of aviation swarm,SDAN-AS)應(yīng)運(yùn)而生。SDAN-AS吸收了軟件定義網(wǎng)絡(luò)[4](software-defined networking,SDN)中的諸多好處,如控制與轉(zhuǎn)發(fā)分離、邏輯集中的網(wǎng)絡(luò)控制以及自動(dòng)化業(yè)務(wù)部署等[5-6],為機(jī)載網(wǎng)絡(luò)的發(fā)展帶來(lái)新思路的同時(shí)也伴隨著新的挑戰(zhàn)[7]。

在SDAN-AS中,依然避免不了SDN固有的網(wǎng)絡(luò)一致性更新問(wèn)題。與傳統(tǒng)網(wǎng)絡(luò)不同,SDN將數(shù)據(jù)平面與控制平面解耦,通過(guò)邏輯集中的控制器提供集中統(tǒng)一的全局網(wǎng)絡(luò)視圖,從而實(shí)現(xiàn)更加靈活的網(wǎng)絡(luò)控制,快速適應(yīng)如路由更新、流量工程等變化。同時(shí)這也為快速的網(wǎng)絡(luò)一致性更新帶來(lái)了挑戰(zhàn)。

研究人員針對(duì)網(wǎng)絡(luò)一致性更新問(wèn)題開(kāi)展了大量研究。主要可劃分為兩階段更新和次序更新兩種方法[8]。文獻(xiàn)[9]首先提出SDN的一致性更新問(wèn)題,定義了數(shù)據(jù)包一致性,并提出兩階段更新協(xié)議(two-phase update protocol,TPP)。該方法采用不同的版本號(hào)標(biāo)記新舊兩套轉(zhuǎn)發(fā)規(guī)則,在第1個(gè)階段,將帶有新版本號(hào)的新轉(zhuǎn)發(fā)規(guī)則安裝到所有的內(nèi)部交換機(jī);在第2個(gè)階段,在入口交換機(jī)將數(shù)據(jù)包打上新版本號(hào)。從而實(shí)現(xiàn)網(wǎng)絡(luò)轉(zhuǎn)發(fā)規(guī)則的更改,并保證數(shù)據(jù)包一致性,即每個(gè)數(shù)據(jù)包只會(huì)按照新或舊轉(zhuǎn)發(fā)規(guī)則進(jìn)行處理,而不會(huì)是兩者的混合。該方法需要同時(shí)保存新舊兩套轉(zhuǎn)發(fā)規(guī)則,流表規(guī)則開(kāi)銷較大[10]。

次序更新[11-15]將更新劃分為一系列更新階段,在每個(gè)階段,控制器發(fā)送更新指令到一部分交換機(jī),在控制器接收到該階段所有的交換機(jī)完成更新的確認(rèn)消息后,進(jìn)入下一階段。通過(guò)謹(jǐn)慎地計(jì)算更新順序,實(shí)現(xiàn)網(wǎng)絡(luò)的一致更新。

上述兩種方法都屬于異步網(wǎng)絡(luò)更新。SDN采用的集中控制僅僅是在邏輯上集中,其物理上是分散的[16]?？刂破髋c數(shù)據(jù)平面的網(wǎng)絡(luò)設(shè)備之間存在著固有延遲,難以實(shí)現(xiàn)同步的更新,只能通過(guò)控制器與數(shù)據(jù)平面的交互來(lái)協(xié)調(diào)更新順序,大大增加了更新時(shí)間。且對(duì)于流交換場(chǎng)景,無(wú)法解決流交換帶來(lái)的更新死鎖問(wèn)題,難以實(shí)現(xiàn)網(wǎng)絡(luò)的一致性更新。

過(guò)去十多年間,時(shí)鐘同步技術(shù)在計(jì)算機(jī)網(wǎng)絡(luò)中得到充分發(fā)展,如精準(zhǔn)網(wǎng)絡(luò)時(shí)間協(xié)議(precision time protocol,PTP)等時(shí)鐘同步協(xié)議已成為商用網(wǎng)絡(luò)設(shè)備的普遍特性,在實(shí)際應(yīng)用中能夠達(dá)到亞微秒級(jí)精度。隨著SDN的發(fā)展和演進(jìn),用于SDN的時(shí)鐘同步協(xié)議如ReversePTP等被提出,已被納入Openflow協(xié)議,SDN的時(shí)鐘同步機(jī)制逐步完善,基于時(shí)鐘同步的網(wǎng)絡(luò)更新被提出[17-18]。文獻(xiàn)[17]證明了流交換場(chǎng)景的存在是不可避免的,并提出了一種定時(shí)更新系統(tǒng)——TIME4,利用精準(zhǔn)到微秒級(jí)的時(shí)鐘同步進(jìn)行網(wǎng)絡(luò)中更新操作的執(zhí)行,但沒(méi)有涉及到具體的更新調(diào)度。文獻(xiàn)[18]進(jìn)一步提出Chronus定時(shí)更新系統(tǒng),針對(duì)最小化更新時(shí)間優(yōu)化問(wèn)題,采用時(shí)間拓展網(wǎng)絡(luò)進(jìn)行一致性的約束分析,但在時(shí)間拓展網(wǎng)絡(luò)中只能假定鏈路時(shí)延為單位時(shí)間的整數(shù)倍,無(wú)法采用真實(shí)的鏈路時(shí)延。

本文針對(duì)上述異步分布式系統(tǒng)的問(wèn)題,在航空集群背景下,提出一種基于定時(shí)的更新(time-based update,TBU)方法。將時(shí)間參數(shù)與更新依賴圖相結(jié)合,設(shè)計(jì)基于時(shí)間的更新依賴關(guān)系圖,并針對(duì)最小化更新時(shí)間的優(yōu)化問(wèn)題提出貪婪依賴圖更新調(diào)度算法,根據(jù)真實(shí)鏈路時(shí)延為更新操作分配更新時(shí)間,從而按照預(yù)定計(jì)劃進(jìn)行定時(shí)網(wǎng)絡(luò)更新。網(wǎng)絡(luò)設(shè)備在預(yù)定的時(shí)間點(diǎn)執(zhí)行相應(yīng)更新操作,控制器下發(fā)更新指令后無(wú)需進(jìn)行更新順序的協(xié)調(diào),避免了節(jié)點(diǎn)間的頻繁交互。

1 問(wèn)題描述

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

1.2 定時(shí)更新問(wèn)題

NS表示網(wǎng)絡(luò)狀態(tài),是網(wǎng)絡(luò)中的節(jié)點(diǎn)、鏈路以及業(yè)務(wù)流轉(zhuǎn)發(fā)規(guī)則的合集。為優(yōu)化網(wǎng)絡(luò)傳輸,通常需要根據(jù)流量變化計(jì)算出當(dāng)前最優(yōu)路由轉(zhuǎn)發(fā)規(guī)則,并更改網(wǎng)絡(luò)的路由轉(zhuǎn)發(fā)規(guī)則,該過(guò)程即為網(wǎng)絡(luò)更新,要求在滿足網(wǎng)絡(luò)一致屬性的同時(shí),將網(wǎng)絡(luò)從初始網(wǎng)絡(luò)狀態(tài)NSi轉(zhuǎn)變至目標(biāo)網(wǎng)絡(luò)狀態(tài)NSt。

一般的網(wǎng)絡(luò)更新方法主要針對(duì)無(wú)路由黑洞、無(wú)轉(zhuǎn)發(fā)循環(huán)和無(wú)鏈路擁塞3種一致屬性進(jìn)行研究。本文采用基于隧道的轉(zhuǎn)發(fā),業(yè)務(wù)流以整體的形式遷移,不會(huì)出現(xiàn)路由黑洞和循環(huán)轉(zhuǎn)發(fā)問(wèn)題。因此,只需關(guān)注無(wú)鏈路擁塞一致性,即更新期間任意時(shí)刻網(wǎng)絡(luò)中任意鏈路上可能經(jīng)過(guò)的流量總和都不能大于鏈路容量。

如圖1所示,網(wǎng)絡(luò)中每條鏈路的鏈路容量為10個(gè)單位,存在f1與f2兩條業(yè)務(wù)流,分別用藍(lán)色和紅色標(biāo)注,每條業(yè)務(wù)流的傳輸速率都為10個(gè)單位。NSi由圖1中實(shí)線部分構(gòu)成,NSt則由虛線部分構(gòu)成。此時(shí),兩條業(yè)務(wù)流需要交換路徑進(jìn)行傳輸,在異步更新中,無(wú)法實(shí)現(xiàn)同時(shí)完成更新,無(wú)論哪一條流先完成更新,都會(huì)造成鏈路的擁塞。而在定時(shí)更新方法中,能夠?qū)崿F(xiàn)微秒級(jí)的時(shí)間同步,同時(shí)更新兩條流,避免網(wǎng)絡(luò)擁塞的產(chǎn)生。

圖1 流交換更新場(chǎng)景示意圖Fig.1 Flow exchange update scenario diagram

對(duì)于定時(shí)的一致更新,由于能夠?qū)崿F(xiàn)定時(shí)的多條流同時(shí)更新,因此可以將更新劃分為k個(gè)階段,對(duì)于第i個(gè)階段(1≤i≤k),定義一個(gè)更新時(shí)間ti。在ti時(shí)刻,階段i中所有的操作同時(shí)完成更新。在任意時(shí)間,都不會(huì)破壞網(wǎng)絡(luò)的一致屬性。

2 TBU方法

通過(guò)PTP能夠?qū)崿F(xiàn)精準(zhǔn)到微秒級(jí)的時(shí)鐘同步[19]。本節(jié)以TIME4系統(tǒng)為基礎(chǔ),提出TBU方法,將時(shí)間參數(shù)與依賴圖相結(jié)合,設(shè)計(jì)基于定時(shí)的更新依賴圖(time-based dependency graph,TBDG),并提出貪婪調(diào)度算法計(jì)算更新調(diào)度。

2.1 TBU方法流程描述

階段 1控制器根據(jù)從數(shù)據(jù)平面收集到的網(wǎng)絡(luò)拓?fù)湫畔?將網(wǎng)絡(luò)更新分解為一系列的更新操作。

階段 2控制器根據(jù)網(wǎng)絡(luò)狀態(tài)信息將一系列更新操作生成TBDG。再執(zhí)行TBDG調(diào)度算法,為每個(gè)更新操作分配一個(gè)更新時(shí)間。將包含更新時(shí)間的更新消息下發(fā)到數(shù)據(jù)平面中對(duì)應(yīng)的交換機(jī)。

階段 3每個(gè)接收到更新消息的交換機(jī)提取出更新消息中的更新時(shí)間,并在其相應(yīng)的更新時(shí)間點(diǎn)完成更新操作的執(zhí)行,直至所有交換機(jī)完成更新,最終完成整個(gè)網(wǎng)絡(luò)更新。

TBU方法流程如圖2所示。

圖2 TBU方法流程圖Fig.2 TBU method flow chart

2.2 TBDG設(shè)計(jì)

TBDG采用有向線段將更新操作、鏈路資源、時(shí)間標(biāo)記、資源標(biāo)記等元素相互連接起來(lái),用于展現(xiàn)更新操作執(zhí)行之間復(fù)雜的相互依賴關(guān)系。

在TBDG中,存在更新操作和鏈路資源兩種節(jié)點(diǎn),分別以圓形和矩形表示。更新操作節(jié)點(diǎn)用集合O表示,鏈路資源節(jié)點(diǎn)用集合R表示。每一個(gè)更新操作節(jié)點(diǎn)o∈O表示添加、修改或刪除流表規(guī)則。每一個(gè)鏈路資源節(jié)點(diǎn)r∈R表示該鏈路上的可用鏈路帶寬資源。從一個(gè)更新操作節(jié)點(diǎn)o1指向另一個(gè)更新操作節(jié)點(diǎn)o2的有向邊,表示o2依賴于o1,即o2必須在o1被執(zhí)行后才能執(zhí)行;從一個(gè)更新操作節(jié)點(diǎn)o指向一個(gè)鏈路資源節(jié)點(diǎn)r的有向邊,附加時(shí)間標(biāo)記tmark和鏈路資源標(biāo)記rmark,表示r依賴于o,即o被執(zhí)行tmark個(gè)時(shí)間單位后將會(huì)釋放rmark個(gè)單位的鏈路資源到r上;從一個(gè)鏈路資源節(jié)點(diǎn)r指向一個(gè)更新操作節(jié)點(diǎn)o的有向邊,附加時(shí)間標(biāo)記tmark和鏈路資源標(biāo)記rmark,表示o依賴于rmark,即o被執(zhí)行tmark個(gè)時(shí)間單位后將會(huì)占用r上rmark個(gè)單位的鏈路資源。

如圖3所示,圖3(a)中每條鏈路的容量都為10個(gè)單位,存在f1與f2兩條業(yè)務(wù)流,分別用藍(lán)色和紅色標(biāo)注,每條業(yè)務(wù)流的傳輸速率都為10個(gè)單位。NSi由圖1中實(shí)線部分構(gòu)成,NSt由虛線部分構(gòu)成。根據(jù)NSi和NSt可生成TBDG如圖3(b)所示,圖中節(jié)點(diǎn)含義在表1中進(jìn)行詳細(xì)描述。

圖3 TBDG構(gòu)建示意圖Fig.3 Schematic of TBDG construction

表1 TBDG中的節(jié)點(diǎn)含義Table 1 Node meaning in TBDG

3 算法描述

本節(jié)對(duì)本文所提定時(shí)更新方法中的相關(guān)算法進(jìn)行詳細(xì)描述。

3.1 TBDG生成算法

在定時(shí)更新的階段2,控制器執(zhí)行TBDG生成算法,根據(jù)當(dāng)前和目標(biāo)網(wǎng)絡(luò)狀態(tài)生成TBDG。TBDG生成算法針對(duì)每一條業(yè)務(wù)流依次進(jìn)行計(jì)算。首先生成添加、刪除和修改規(guī)則的更新操作節(jié)點(diǎn),并添加操作節(jié)點(diǎn)之間的依賴關(guān)系。然后生成修改規(guī)則的更新操作所需要占用和釋放的鏈路資源節(jié)點(diǎn)。最后添加資源節(jié)點(diǎn)與操作節(jié)點(diǎn)之間的依賴關(guān)系,并添加相應(yīng)的時(shí)間標(biāo)記和資源標(biāo)記。TBDG生成算法如算法1所示。

算法1 TBDG生成算法輸入:初始網(wǎng)絡(luò)狀態(tài)NSi;目標(biāo)網(wǎng)絡(luò)狀態(tài)NSt輸出:TBDG1foreachf∈Fdo2 foreachv∈Pnf-sdo3 生成添加隧道的操作節(jié)點(diǎn)oadd4 endfor5 foreachv∈Pof-sdo6 生成刪除隧道的操作節(jié)點(diǎn)odel7 endfor8 生成修改流量分配權(quán)重的操作節(jié)點(diǎn)omod9 添加從oadd指向omod的邊10 添加從omod指向odel的邊11 foreache∈Pnfdo12 生成對(duì)應(yīng)鏈路e的資源節(jié)點(diǎn),記為r-13 計(jì)算從源節(jié)點(diǎn)s到該鏈路的時(shí)延tc14 添加從r-指向o*的邊,附加rmark=df,tmark=tc15 endfor16 foreache∈Pofdo17 生成對(duì)應(yīng)鏈路e的資源節(jié)點(diǎn),記為r+18 計(jì)算從源節(jié)點(diǎn)s到該鏈路的時(shí)延tc19 添加從o*指向r+的邊,附加rmark=df,tmark=tc20 endfor21endfor

算法第2～8行根據(jù)NSi和NSt生成要添加、刪除和修改的操作節(jié)點(diǎn);算法第9～10行添加操作節(jié)點(diǎn)之間的依賴關(guān)系,由于添加和刪除隧道只與交換機(jī)內(nèi)存有關(guān),因此不會(huì)與鏈路資源節(jié)點(diǎn)產(chǎn)生依賴關(guān)系;第11～20行生成鏈路資源節(jié)點(diǎn),并添加鏈路資源節(jié)點(diǎn)與更新操作節(jié)點(diǎn)之間的依賴關(guān)系,將業(yè)務(wù)流的需求作為帶寬資源標(biāo)記,將鏈路的時(shí)延作為時(shí)間標(biāo)記附加到有向邊上,表示更新操作的執(zhí)行對(duì)鏈路資源的需求和釋放以及相對(duì)應(yīng)的時(shí)間。

3.2 貪婪調(diào)度算法

在生成TBDG之后,控制器需要為每個(gè)更新操作oi分配一個(gè)更新時(shí)間ti。但最小化總更新時(shí)間是NP難問(wèn)題。因此，本節(jié)設(shè)計(jì)了一種貪婪調(diào)度算法。將時(shí)間劃分為時(shí)間步,根據(jù)TBDG中包含的節(jié)點(diǎn)之間的依賴關(guān)系,在每個(gè)時(shí)間步調(diào)度盡可能多的更新操作,同時(shí)不違背網(wǎng)絡(luò)的一致屬性,即在任意的時(shí)間點(diǎn)任意的鏈路上的負(fù)載不能超過(guò)其鏈路容量。

首先,將時(shí)間劃分為離散的時(shí)間步,即T={0,1,…}。文獻(xiàn)[18]假設(shè)網(wǎng)絡(luò)中的鏈路時(shí)延相同并設(shè)為單位時(shí)間。本文考慮了真實(shí)的鏈路時(shí)延,將鏈路時(shí)延的平均值設(shè)為單位時(shí)間。

然后,按照時(shí)間步進(jìn)行迭代,在每一個(gè)時(shí)間步i,計(jì)算出可以同時(shí)執(zhí)行的最多數(shù)目的更新操作集合Si;更新TBDG后進(jìn)入下一個(gè)時(shí)間步,直至所有的更新操作都被更新。從而將計(jì)算出合適的更新調(diào)度S={S1,S2,…,Sk}。貪婪調(diào)度算法每次貪婪地尋找最多數(shù)目的更新操作,從而減少執(zhí)行更新占用的總時(shí)間步數(shù)目,即可減少網(wǎng)絡(luò)更新時(shí)間。貪婪調(diào)度算法如算法2所示。

算法2 貪婪調(diào)度算法輸入:TBDG輸出:更新調(diào)度S1i=0;S0=Φ;變量初始化2whilei≥03 Si=Φ4 foreacho∈Oadddo5 Si=Si∪o;Oadd=Oadd-o6 endfor7 foreacho∈Odeldo8 ifo不存在父節(jié)點(diǎn)then9 Si=Si∪o;Odel=Odel-o10 endif11 endfor12 foreacho∈Omoddo13 ifCanSchedule(i,Si,o)then14 Si=Si∪o;Omod=Omod-o15 endif16 endfor17 TBDG=TBDG_ITERATE(TBDG,tmark);執(zhí)行TBDG迭代算法18 i=i+119 ifTBDG中不存在更新操作then20 終止算法21 endif22endwhile

算法第1行對(duì)時(shí)間步和更新調(diào)度進(jìn)行初始化;第2～22行對(duì)時(shí)間步進(jìn)行迭代,計(jì)算出在每個(gè)時(shí)間步i能夠執(zhí)行的最多數(shù)目的更新操作集合Si。其中第4～6行表示計(jì)算能夠執(zhí)行的添加規(guī)則操作;第7～11行表示計(jì)算能夠執(zhí)行的刪除規(guī)則操作;第12～16行表示計(jì)算能夠執(zhí)行的添加修改規(guī)則操作,通過(guò)第13行的CanSchedule算法檢測(cè)該操作是否能夠執(zhí)行,能夠執(zhí)行則該算法返回結(jié)果為true,否則返回false;第17～21行表示計(jì)算完每個(gè)時(shí)間步的更新調(diào)度后,需要執(zhí)行TBDG迭代算法對(duì)TBDG進(jìn)行迭代,并進(jìn)入下一個(gè)時(shí)間步,直至TBDG中所有的更新操作都被執(zhí)行。

3.2.1 CanSchedule算法

在計(jì)算能夠執(zhí)行的添加修改規(guī)則操作時(shí),需要執(zhí)行CanSchedule算法遍歷Omod中的所有更新操作節(jié)點(diǎn)。首先假設(shè)該節(jié)點(diǎn)o能夠在時(shí)間步i時(shí)執(zhí)行,將o加入更新調(diào)度Si中,而后執(zhí)行TBDG迭代算法,若存在其父節(jié)點(diǎn)r的可用鏈路資源不足,則說(shuō)明該操作無(wú)法執(zhí)行,返回False值,否則返回True值。CanSchedule算法如算法3所示。

算法3 CanSchedule算法輸入:TBDG;時(shí)間步i;更新調(diào)度Si;更新操作o輸出:True或False1Si=Si∪o2foreachr∈o的父節(jié)點(diǎn)3 TBDG=TBDG_ITERATE(TBDG,tmark);執(zhí)行TBDG迭代算法4 ifrmark<0then5 returnFalse6 終止算法7 endif8endfor9returnTure

3.2.2 TBDG迭代算法

在計(jì)算完每個(gè)時(shí)間步的更新調(diào)度后,進(jìn)入下一個(gè)時(shí)間步,需要執(zhí)行TBDG迭代算法對(duì)TBDG進(jìn)行迭代。

TBDG迭代算法對(duì)更新操作集合Si中的每一個(gè)更新操作進(jìn)行遍歷。由于Oadd中的添加規(guī)則操作和Odel中的刪除規(guī)則操作只與Omod中的修改規(guī)則操作存在依賴關(guān)系,與鏈路資源節(jié)點(diǎn)無(wú)關(guān),因此執(zhí)行操作后只需在TBDG中刪除該操作及與其連接的邊。對(duì)于Omod中的修改規(guī)則操作,執(zhí)行操作后需要修改與其具有依賴關(guān)系的鏈路資源節(jié)點(diǎn)的可用鏈路資源和時(shí)間標(biāo)記tmark。TBDG迭代算法如算法4所示。

算法4 TBDG_ITERATE算法輸入:TBDG;更新操作集合Si,時(shí)間間隔Δt輸出:TBDG1Δt=1;更新時(shí)間步初始化為12foreacho∈Sido3 ifo∈Oadd∪Odel4 在TBDG中刪除o及連接o的邊5 else6 foreachr屬于o的父節(jié)點(diǎn)7 ifr指向o的邊的tmark≤Δtthen8 r=r-rmark9 在TBDG中刪除該條邊10 else11 tmark=tmark-Δt12 endif13 endfor14 foreachr∈o的子節(jié)點(diǎn)15 ifo指向r的邊的tmark≤Δtthen16 r=r+rmark17 在TBDG中刪除該條邊18 else19 tmark=tmark-Δt20 endif21 endfor22 endif23endfor

4 仿真實(shí)驗(yàn)及分析

本文基于Exata 5.1網(wǎng)絡(luò)仿真軟件搭建航空集群機(jī)載網(wǎng)絡(luò)。本節(jié)對(duì)本文所提基于定時(shí)的更新方法TBU進(jìn)行仿真分析,將Dionysus和TPP兩種SDN更新方法作為基線算法進(jìn)行對(duì)比,從而分析所提更新方法的效能。

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

表2為本節(jié)仿真實(shí)驗(yàn)中的相關(guān)參數(shù)設(shè)定。為模擬航空集群機(jī)載網(wǎng)絡(luò),按照作戰(zhàn)半徑,在1 000 km×1 000 km的矩形范圍中隨機(jī)生成20～100個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。節(jié)點(diǎn)通信半徑設(shè)定為200 km,根據(jù)通信半徑生成網(wǎng)絡(luò)拓?fù)溥B通圖。節(jié)點(diǎn)在200～1 200 km/h的速度范圍內(nèi)隨機(jī)運(yùn)動(dòng)。隨機(jī)選擇源節(jié)點(diǎn)和目的節(jié)點(diǎn)生成40～200條業(yè)務(wù)流,每條業(yè)務(wù)流的流量需求服從正態(tài)分布N(1,1)。業(yè)務(wù)流采用基于隧道的轉(zhuǎn)發(fā),在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立起一條隧道,其上的每個(gè)節(jié)點(diǎn)根據(jù)隧道進(jìn)行相應(yīng)的轉(zhuǎn)發(fā)。控制器定期執(zhí)行流量工程和路由算法,根據(jù)初始網(wǎng)絡(luò)狀態(tài)NSi計(jì)算出目標(biāo)網(wǎng)絡(luò)狀態(tài)NSt,而后開(kāi)始進(jìn)行網(wǎng)絡(luò)更新。共完成了1 000次從NSi到NSt的連續(xù)網(wǎng)絡(luò)更新過(guò)程,并對(duì)每一次更新的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)、處理和分析。

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

仿真選擇對(duì)比的更新方法描述如下。

(1)Dionysus:該算法為動(dòng)態(tài)次序更新方法,首先根據(jù)網(wǎng)絡(luò)狀態(tài)生成更新依賴圖,而后按照依賴圖進(jìn)行動(dòng)態(tài)的異步更新。

(2)TPP:該算法為兩階段更新協(xié)議,采用版本號(hào)對(duì)新舊兩套流表規(guī)則進(jìn)行標(biāo)記和區(qū)分,第1個(gè)階段在內(nèi)部交換機(jī)上添加新流表規(guī)則,第2個(gè)階段在入口交換機(jī)上修改數(shù)據(jù)包版本號(hào)。

4.2 仿真結(jié)果分析

(1)更新時(shí)間比較

圖4為網(wǎng)絡(luò)更新時(shí)間的比較,更新時(shí)間為從初始網(wǎng)絡(luò)狀態(tài)轉(zhuǎn)變到目標(biāo)網(wǎng)絡(luò)狀態(tài)的一次完整的網(wǎng)絡(luò)更新所需要的時(shí)間。

從仿真結(jié)果可以看出,與Dionysus和TPP相比,TBU方法在更新時(shí)間上降低了約50%～60%,業(yè)務(wù)流數(shù)目越多效果越明顯。由于Dionysus基于依賴圖進(jìn)行動(dòng)態(tài)的更新,因此更新時(shí)間要短于TPP。在Dionysus和TPP中,更新順序協(xié)調(diào)占據(jù)了大量的更新時(shí)間[20],而TBU采用定時(shí)的更新,為每個(gè)更新操作預(yù)先分配時(shí)間點(diǎn),避免了異步更新方法中的復(fù)雜更新順序協(xié)調(diào),減少了節(jié)點(diǎn)頻繁交互帶來(lái)的高延遲;并且能夠通過(guò)多業(yè)務(wù)流同時(shí)更新解決流交換場(chǎng)景中的死鎖問(wèn)題,因此能夠顯著降低網(wǎng)絡(luò)更新完成時(shí)間。

圖4 更新時(shí)間比較Fig.4 Update time comparison

(2)更新死鎖率比較

圖5為網(wǎng)絡(luò)更新期間更新死鎖率的比較。由于更新操作與鏈路資源之間存在依賴關(guān)系。當(dāng)更新操作與鏈路資源相互依賴形成環(huán)路,將會(huì)導(dǎo)致更新死鎖。從仿真結(jié)果可以看出,更新死鎖率隨著業(yè)務(wù)流數(shù)目增加而增加。Dionysus和TPP兩種方法的更新死鎖率較高,約為10%～18%,而TBU方法始終保持較低的更新死鎖率,約為1%～2%。TBU方法能夠通過(guò)多業(yè)務(wù)流同時(shí)更新解決更死鎖問(wèn)題。有效降低了更新死鎖率。

圖5 更新死鎖率比較Fig.5 Update deadlock rate comparisons

(3)擁塞流數(shù)目比較

圖6為網(wǎng)絡(luò)更新期間擁塞流數(shù)目的比較。擁塞流數(shù)目即在更新期間產(chǎn)生網(wǎng)絡(luò)擁塞的流的數(shù)目。

從仿真結(jié)果可以看出,Dionysus和TPP始終存在約20%的業(yè)務(wù)流擁塞,兩者在擁塞流數(shù)目上相近。而在TBU中,在業(yè)務(wù)流數(shù)目較小時(shí),擁塞流數(shù)目始終為零。在業(yè)務(wù)流數(shù)目較大時(shí),存在極小程度的擁塞,約占總業(yè)務(wù)流的2%。這是由于TPP方法無(wú)法解決擁塞問(wèn)題,只能保持更新期間的數(shù)據(jù)包一致性,無(wú)法保持無(wú)擁塞一致性;Dionysus方法無(wú)法避免依賴圖中的死鎖問(wèn)題,只能用過(guò)降低業(yè)務(wù)流速率來(lái)緩解死鎖。而TBU方法通過(guò)實(shí)現(xiàn)多業(yè)務(wù)流的精準(zhǔn)定時(shí)更新,能夠較好的解決更新死鎖問(wèn)題,從而顯著降低更新期間的網(wǎng)絡(luò)擁塞。

圖6 擁塞流數(shù)目比較Fig.6 Comparison of congested flows numbers

(4)規(guī)則開(kāi)銷比較

圖7為網(wǎng)絡(luò)更新期間規(guī)則開(kāi)銷的比較。規(guī)則開(kāi)銷即在更新期間添加、刪除和修改的流表規(guī)則的數(shù)目。

圖7 規(guī)則開(kāi)銷比較Fig.7 Comparison of overhead of rules

從仿真結(jié)果可以看出,3種方法的流表規(guī)則數(shù)目均隨業(yè)務(wù)流數(shù)目的增加呈線性增長(zhǎng)。但TBU與Dionysus在規(guī)則開(kāi)銷上相近,而TPP的規(guī)則開(kāi)銷約為前兩者的2倍。這是由于TBU與Dionysus都基于依賴圖進(jìn)行調(diào)度,TBU方法中將時(shí)間參數(shù)與依賴圖相結(jié)合,不會(huì)對(duì)規(guī)則開(kāi)銷產(chǎn)生影響。而在TPP方法中,由于在更新期間需要同時(shí)存在新舊兩套流表規(guī)則,因此產(chǎn)生較高的規(guī)則開(kāi)銷。

5 結(jié) 論

本文針對(duì)異步網(wǎng)絡(luò)更新方法更新時(shí)間長(zhǎng)、難以解決更新死鎖的問(wèn)題,為軟件定義航空集群機(jī)載網(wǎng)絡(luò)設(shè)計(jì)了一種定時(shí)更新方法:① 提出的定時(shí)更新方法與異步更新方法相比,更新時(shí)間降低了約50%～60%,顯著提升更新速度。② 提出的定時(shí)更新方法利用多條流同時(shí)更新解決更新死鎖問(wèn)題,與異步更新相比,更新死鎖率和擁塞流數(shù)目均有顯著降低。③ 所提定時(shí)更新方法能夠滿足軟件航空集群場(chǎng)景下的快速一致網(wǎng)絡(luò)更新需求。