一種面向航空集群機載網絡的分布式更新方法

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

(空軍工程大學信息與導航學院，西安，710077)

航空作戰力量在現代戰爭中往往占據著一定戰略地位，建設和發展航空網絡的重要性不言而喻?，F代軍事思想不斷衍生發展，未來航空集群作戰的理念已被廣泛認同[1-2]。為滿足航空集群多平臺多任務靈巧協同作戰的需求，有研究人員將軟件定義網絡(Software-defined Networking, SDN)的思想運用在機載網絡中，提出軟件定義航空集群機載網絡(Software-defined Airborne Network of Aviation Swarm, SDAN-AS)，賦予了機載網絡靈活的網絡控制和管理、自動化可編程的業務部署，從而提供與多任務靈活耦合的網絡服務[3]。SDN的引入能夠突破單個作戰平臺的效能瓶頸，多平臺之間展開的靈活、高效協同能夠彌補單一平臺的弱點，從而形成優勢互補的強大體系作戰能力[1-3]。

在SDAN-AS中，也同樣避免不了SDN固有的網絡一致性更新問題，一致性更新是所有集中式控制的網絡都面臨的問題，即如何在改變網絡配置期間保持網絡的一致屬性(如無路由黑洞、無轉發循環和無鏈路擁塞)[4-6]。但由于控制器與交換機之間存在著固有延遲，即使同時發送更新指令，指令也難以同時到達所有的交換機。即使同時到達所有的交換機，完成更新的時間也難以同步。因此無法同時進行整個網絡的更新，現有更新方法往往需要通過多個輪次來進行[7-8]。

網絡的一致性更新近些年來受到廣泛關注，研究人員針對更新期間的各種一致屬性開展了各類研究。文獻[9]首次提出兩階段更新方法，實現了更新過程中的數據包一致屬性，保證轉發路徑不會是新舊兩套轉發規則的混合。文獻[10]基于兩階段更新提出增量兩階段更新方法，犧牲更新時間來降低規則開銷。文獻[11]提出SWAN更新系統，采用預留鏈路帶寬的方法實現無鏈路擁塞的更新。文獻[12]提出Dionysus動態更新系統，通過構建更新依賴圖減少網絡更新時間，從而加快更新速度。以上幾種現有更新方法在一定程度上能夠較好地保持網絡更新期間的各種一致屬性，但都屬于集中式更新方法，往往分為很多個輪次，通過控制器與數據平面的頻繁交互來協調交換機的更新順序?？刂破飨掳l更新指令到網絡中的部分交換機，收到更新指令的交換機完成更新后向控制器發送確認消息，控制器在接收到所有的確認消息后完成更新的一個輪次，開始進入下一個輪次，下發新的更新指令到網絡中的交換機。在集中式更新方法中，控制器與交換機之間的頻繁交互將會大大增加更新的完成時間[13-14]。同時集中式更新方法在更新過程中全程依賴控制器的計算與調度，SDAN-AS中的控制器搭載于資源有限的空中平臺，難以承載較高的負荷。

本文針對上述集中式更新方法的缺點，提出一種面向航空集群機載網絡的分布式更新方法，設計改進的更新消息格式，將更新依賴關系編碼到更新消息中，采用詢問和通知2種消息實現數據平面的分布式交互，將控制器的更新順序協調功能轉移到數據平面上進行，從而實現快速一致的分布式更新，有效降低網絡更新時間。對于追求高實時性、高動態組網的SDAN-AS而言，降低網絡更新時間從而減少更新期間的網絡性能下降具有重要意義。

1 問題描述

1.1 網絡模型

為方便描述，首先引入本文的網絡模型抽象。在SDAN-AS中，通常由大型空中平臺擔任網絡控制器。由若干個小型空中平臺擔任網絡交換機共同構成網絡的數據平面。因此可以將SDAN-AS的數據平面抽象為由若干個節點和鏈路連接起來的無向圖G=(V,E)。其中其中V={v1,v2,…,vm}表示網絡中交換機的集合，E={e1,e2,…,en}表示鏈路集合。對于?e∈E，Ce表示該鏈路的容量。μ={μe1,μe2,…,μen}表示網絡鏈路利用率的集合。

本文采用標準的流模型，F={f1,f2,…,fm}表示網絡中的業務流集合，其中每條業務流f表示在一個源節點和一個目的節點之間的一組數據包的集合，其流量需求表示為df?？刂破骺梢酝ㄟ^定期收集數據平面信息或根據帶寬資源分配計算出網絡中業務流需求的估計值。業務流采用基于隧道的轉發，對于每條業務流，采用VLAN標簽建立多條從源節點到目的節點的隧道，隧道上的每個節點根據匹配VLAN標簽的流表規則進行相應的轉發。

1.2 網絡更新問題

G表示網絡狀態，即決定網絡中所有業務流的數據包轉發規則的集合。網絡控制器定期執行流量工程，根據業務需求變化和網絡拓撲信息，執行路由算法或流量調度算法計算出新的路由轉發規則，Po(f)表示流f在當前網絡狀態Go中的舊轉發路徑，Pn(f)表示流f在目標網絡狀態Gn中的新轉發路徑。執行網絡更新將網絡從狀態Go轉變為狀態Gn，將流量從舊轉發路徑遷移到新轉發路徑上。

由于更新的過程不是瞬態，而是異步分布式的過程。需要謹慎地協調交換機流表規則的更新順序，否則交換機流表規則的不一致將會導致網絡配置的不一致，從而產生如路由黑洞、循環轉發、鏈路擁塞等問題[15-16]，嚴重影響更新期間的網絡性能。為了避免網絡配置的各種不一致，需要網絡更新算法滿足對應的一致屬性。本文所設計的網絡更新方法主要滿足以下3種一致屬性：

1)無路由黑洞一致性：更新期間網絡中所有數據包都不會被丟棄。

2)無轉發循環一致性：更新期間網絡中所有數據包的轉發不會產生環路[17]。

3)無鏈路擁塞一致性：更新期間網絡中所有鏈路的負載都不會超過其容量[11-18]。

由于網絡更新是異步的過程，可以將每一次網絡更新U序列化為一系列的更新操作的集合，表示為U={o1,o2,…,on}，其中每一個更新操作o表示插入、修改或刪除一條流表規則。為了保持更新期間的網絡配置一致屬性，最小化更新操作之間產生的沖突，需要安排更新操作以合適的順序執行。由于更新操作之間具有相互依賴的關系，根據依賴關系可以建立起更新依賴圖，從而根據更新依賴圖計算出合適的更新順序。

2 更新消息設計

為減緩控制器負載，直接在數據平面實現網絡的分布式更新，本節設計了改進的更新消息格式，將更新依賴關系編碼到更新消息中。

2.1 更新依賴圖

為了更好地闡述改進的更新消息設計，首先引入更新依賴圖的概念。更新依賴圖是描述網絡更新操作之間依賴關系的有向圖。根據當前網絡狀態Go以及目標網絡狀態Gn，可以計算出從Go更新到Gn的過程中所需要執行的一系列更新操作。而后根據更新操作之間的相互依賴關系、網絡鏈路帶寬資源以及更新操作對鏈路帶寬資源的需求等信息，可以為每一個給定當前網絡狀態Go和目標網絡狀態Gn的完整網絡更新過程構建出滿足其一致性要求的更新依賴圖。

如圖1所示，圖1(a)中存在2條業務流，用不同的顏色表示，分別是源節點為1、目的節點為3的f1和源節點為2、目的節點為4的f2。每條業務流的需求都為10個單位，網絡中的每條鏈路的鏈路容量為10個單位。其中實線部分表示當前網絡狀態Go，虛線部分表示目標網絡狀態Gn。

根據圖1(a)的網絡拓撲圖生成的更新依賴圖如圖1(b)所示，其中圓形節點表示操作節點，操作節點與操作的對應關系如表1所示；矩形節點表示鏈路資源節點，表示鏈路e(2,3)上的可用鏈路帶寬資源為0，指向性直線表示節點之間的依賴關系。操作C的執行將會在鏈路e(2,3)上釋放10個單位的鏈路帶寬資源，操作E的執行需要鏈路e(2,3)上具有10個單位的可用鏈路帶寬資源。

圖1 更新依賴圖示例

表1 依賴圖節點含義表示

2.2 改進型更新消息

為了實現分布式的快速一致網絡更新，本小節設計了改進型更新消息格式，將操作之間的依賴關系編碼到更新消息中。網絡控制器采用改進型的更新消息來進行數據平面的網絡配置，通過節點之間的分布式協調來執行網絡更新。

改進型更新消息中包含以下3個字段的信息。

1)操作：表示一個任意的更新操作；

2)前置條件：表示執行該更新操作所需要預先執行的前置更新操作的組合，以邏輯布爾表達式呈現，更新操作之間采用邏輯關系式進行連接，只有前置條件滿足之后才可執行該操作。

3)后置操作：表示依賴于該更新操作執行的一系列更新操作的集合。

控制器根據從數據平面收集到的網絡狀態信息為網絡更新中的每一個更新操作計算出一個對應該操作的更新消息?？刂破饔嬎阃旮孪⒑?，同時下發所有的更新消息到對應的網絡節點。節點接收到更新消息后按照以下規則進行執行。

對于一個收到更新消息的節點v：

1)只有當該更新消息中的前置條件被滿足之后，才能夠執行該更新消息中的操作；

2)在更新消息中的操作被執行之后，節點v向其后置操作中的所有更新操作所對應的節點發送通知消息。

前置條件中的邏輯布爾表達式由單個或多個更新操作通過&和||2種邏輯運算符連接起來。

定義1運算符&：對于任意的操作o1和o2，o1&o2表示o1與o2都被執行。

定義2運算符||：對于任意的操作o1和o2，o1||o2表示o1與o2至少存在一個被執行。

例如，若更新操作o1依賴于更新操作o2和o3的執行，則o1的前置條件為o2&o3，o2和o3的后置操作都為{o1}。前置條件和后置操作的計算在第3節中的算法2進行詳細介紹。

2.3 分布式更新協調

在本文的分布式更新方法中，為數據平面上的分布式更新順序協調定義了兩種消息：詢問消息、通知消息。取代了集中式更新方法中控制器的更新順序協調功能，數據平面中的節點通過詢問和通知兩種消息進行分布式交互，協調更新順序，從而減少控制器與數據平面之間的頻繁交互所帶來的延遲。

詢問消息：當一個交換機接收到控制器發送的一條更新消息后，將會發送詢問消息到其前置條件中的所有更新操作所對應的交換機，詢問這些更新操作是否已執行。

通知消息：在一條更新消息中的操作被其對應的節點執行后，該節點將會發送通知消息到其后置條件中的所有更新操作所對應的交換機，從而通知這些交換機該更新操作已經執行。

詢問和通知2種消息能夠確保更新操作在數據平面被分布式地執行。操作之間的執行順序完全由數據平面完成，從而取代控制器的更新順序協調功能。網絡控制器只需根據更新依賴圖為所有的更新操作構造對應的更新消息并下發到數據平面，即使更新消息到達的時間不同，也能夠保證更新操作按照更新依賴圖中的依賴關系進行執行。

對于圖1中的情況，控制器能夠根據圖1(b)中的更新依賴圖構造出每一個更新操作所對應的更新消息，如第3節中圖1的更新消息構造如表2所示。

表2 更新消息示例

當網絡控制器將所有的更新消息下發到數據平面的各交換機后，由于更新操作A、B的前置條件均不存在，因此節點3接收到更新消息4后可直接執行更新操作B，向并其后置操作E所對應的節點2發送通知消息。同理，節點5在接收到更新消息5后可直接執行更新操作A，并向節點1發送通知消息。節點1接收到更新消息1后，不能立即執行更新操作C，只有在更新操作A執行之后才能更新，因此節點1需要向其前置條件(即操作C)對應的節點5發送詢問消息，當節點1接收到節點5發送的通知消息后，即可執行更新操作C，并向其后置操作D、E所對應的節點2發送通知消息。

數據平面的交換機之間利用詢問和通知兩種消息進行分布式交互來協調更新順序，最終完成整個網絡的分布式更新。

3 分布式更新方法

3.1 更新方法流程描述

階段1控制器根據從數據平面收集到的網絡拓撲信息，將網絡更新分解為一系列的更新操作。

階段2根據網絡狀態信息將一系列更新操作生成更新依賴圖。再根據更新依賴圖計算出每一個更新操作所對應的前置條件和后置操作，構造更新消息并下發到該更新操作對應的交換機。

階段3數據平面中的交換機接收到控制器發送的更新消息后，根據更新消息中的前置條件和后置操作開始執行分布式更新，采用詢問、通知兩種消息進行更新順序的協調，從而完成數據平面的分布式網絡更新。

3.2 算法描述

3.2.1 更新依賴圖生成

對于更新依賴圖的生成，首先根據網絡所需要滿足的一致屬性，提取出約束條件，然后根據約束條件進行更新依賴圖的生成。本文主要關注無路由黑洞、無循環轉發和無擁塞3種一致屬性。

無路由黑洞一致性約束：要確保添加隧道的操作在流量從入口交換機輸入之前執行，刪除隧道的操作要在流量遷移出該隧道之后執行。即修改入口交換機流量分配權重的操作依賴于添加隧道的操作，刪除隧道的操作依賴于修改入口交換機流量分配權重的操作。

無循環轉發一致性約束：由于網絡采用基于隧道的轉發，只有建立起一條新轉發路徑的隧道，才能夠在其上進行數據包的轉發，因此一定滿足無循環轉發的一致性。

無鏈路擁塞一致性約束：要確保更新操作的執行必須具有相應的可用鏈路帶寬，即更新操作依賴于鏈路可用帶寬資源，同時更新操作也會釋放一些鏈路帶寬資源。

生成更新依賴圖算法如算法1所示。

算法1：更新依賴圖生成算法

輸入：流集合F；路徑集合P；流需求集合df；

輸出：更新依賴圖

1.for eachf∈Fdo

2.尋找業務流f的入口交換機s

3.生成“修改s上的流量分配權重”操作節點，記為o*

4.for eachv∈Pn(f)-sdo

5.生成“在v中添加隧道Pn(f)”的操作節點，記為oadd

6.添加一條從oadd指向o*的邊

7.end for

8.for eachv∈Po(f)-sdo

9.生成“在v中刪除隧道Po(f)”的操作節點，記為odel

10.添加一條從o*指向odel的邊

11.end for

12.for eache∈Pn(f)do

13.生成對應鏈路e的資源節點，記為r-

14.添加一條附加數值df，從r-指向o*的邊

15.end for

16.for eache∈Po(f)do

17.生成對應鏈路e的資源節點，記為r+

18.添加一條附加數值df，從o*指向r+的邊

19.end for

20.end for

3.2.2 構造更新消息

在生成更新依賴圖之后，控制器需要為每一個更新操作構造出一條更新消息，下發到數據平面中相對應的交換機。

更新消息構造的關鍵是計算前置條件和后置操作，前置條件為一系列更新操作的組合，表現為邏輯布爾表達式的形式；后置操作為一系列更新操作的集合。更新消息構造算法如算法2所示。

算法2：更新消息構造算法

輸入：更新依賴圖

輸出：更新消息

1.初始化所有操作的前置條件和后置操作

2.for eachoido

3.if ?oj∈oi的父節點且oj∈U then

4.oi的前置條件=oi的前置條件&oj

5.end if

6.end for

7.for eachrdo

8.ifr的可用資源

9.計算r子節點優先級

10.將r子節點按照優先級從高到低排列

11.for eacho∈r子節點do

12.r的可用資源=r的可用資源-o的鏈路需求

13.ifr的可用資源<0 then

14.根據r的父節點計算合適的調度S

15.o的前置條件=o的前置條件&S

16.end if

17.end for

18.end if

19.end for

20.for eachoido

21.if ?oj∈oi的前置條件 then

22.oj的后置操作=oj的后置操作∪oi

23.end if

24.end for

4 仿真實驗及分析

本文的仿真實驗搭建在CPU為Intel Xeon，主頻為3.2 GHz，內存16 GB的商用服務器上。軟件定義航空集群機載網絡的場景采用Exata 5.1網絡仿真平臺進行搭建。本節與現有集中式網絡更新方法的典型代表Dionysus更新系統進行對比，從而驗證分析所提方法的性能。

4.1 仿真參數設置

仿真參數設置如表3所示。節點按照控制器計算并下發的流表規則進行數據包轉發和處理?？刂破髟诿總€流量工程周期內根據當前網絡拓撲重新計算新的路由轉發，執行網絡更新。共進行1 000次完整的網絡更新過程，對每一次完整網絡更新數據進行統計、處理和分析。

表3 仿真參數設置

4.1.1 更新完成時間

圖2為網絡更新完成時間的比較。從仿真結果可以看出，計算時間只在更新完成時間中占據了很小的比例，更新完成時間主要表現在更新順序協調所消耗的協調時間。由于分布式更新方法采用詢問與通知2種消息直接在數據平面的交換機之間進行分布式交互，避免了集中式更新中依賴控制器進行更新調度的“控制器-交換機-控制器”模式所帶來的頻繁交互產生的高延遲，因此能夠顯著降低更新協調時間。與Dionysus更新系統相比，本文提出的分布式更新方法在更新計算時間上表現近似，但在更新協調時間上降低了約40%，從而顯著降低了整個更新完成時間。

圖2 更新完成時間比較

4.1.2 更新協調距離

圖3為本文分布式更新方法在仿真實驗中更新協調距離的累積密度函數。更新協調距離表示一個更新操作執行之后向被其依賴的更新操作所對應的節點發送通知消息所需要的跳數，其累計密度函數表示不大于該更新協調距離的操作在操作總數目中所占比例。從仿真結果可以看出，在分布式更新中約20%的更新協調距離為0，即相互依賴的更新操作在相同的交換機上執行；約36%的更新協調距離為1，即相互依賴的更新操作在相鄰的交換機上執行。而在集中式更新中，需要控制器與數據平面之間反復交互，每個操作的更新協調距離都至少為2。分布式更新方法利用相鄰交換機之間的直接交互，大大降低了消息交互所帶來的更新時間，從側面驗證了分布式更新方法在降低更新時間上的優勢。

圖3 更新協調距離比較

4.1.3 業務流更新時間

圖4為業務流更新時間的累計密度函數對比。業務流更新時間表示單條業務流更新完成所需要的時間，其累計密度函數表示不大于該更新時間的業務流數目在業務流總數目中所占比例。從仿真結果中可以看出，在集中式更新方法中，最長的業務流更新時間約為800 ms，90%的業務流在400 ms內完成更新；而分布式更新方法中最長的業務流更新時間約為600 ms，90%的業務流在250 ms內完成更新。在同等累計密度函數下，分布式更新方法的業務更新時間比集中式更新方法更短；在同等業務流更新時間的限制下，分布式更新方法完成了更多的業務流更新?？梢钥闯龇植际礁路椒ㄔ谔岣邩I務流更新速度方面表現較好。

圖4 業務流更新時間

5 結語

本文針對集中式網絡更新方法更新時間長、過于依賴控制器的問題，提出一種應用于軟件定義航空集群機載網絡的分布式更新方法。

與集中式更新方法相比，本文所提方法通過實現數據平面的分布式交互有效降低更新協調距離，減少了更新協調所需的交互次數，從而降低更新協調時間。仿真實驗表明，本文所提方法與集中式更新方法相比，更新計算時間大致保持相同，更新協調時間降低了約40%，從而顯著減少整個網絡的更新完成時間。