基于度中心性的AFDX網絡拓撲生成

王智宇， 何鋒,*， 谷曉燕

(1. 北京航空航天大學電子信息工程學院, 北京 100083； 2. 北京信息科技大學信息管理學院， 北京 100192)

航空電子全雙工交換式以太網(Avionics Full Duplex Switched Ethernet，AFDX)標準定義于ARINC664 Part7[1]，是新一代民用航空總線標準。AFDX網絡是基于商用以太網IEEE802.3標準進行改進使其成為適合航空電子系統數據傳輸的全雙工確定性交換式以太網，已經成功應用于空客公司的A380飛機和波音公司波音787飛機[2]。

近年來復雜網絡(complex network)[3]受到了來自科學與工程等各個領域的強烈關注，作為研究復雜性網絡的全新視角和有力工具，由于其模型不僅兼顧樣本個體屬性，還更加注重從宏觀結構上將樣本局部與整體的關系緊密連接，這些優勢促使復雜網絡在網絡生成研究問題中應用廣泛。依據復雜網絡視角對一般網絡建模的研究，文獻[4]從復雜網絡的統計特性出發，提取真實的互聯網所具備的統計特征，對互聯網進行建模抽象。復雜網絡的拓撲結構如何影響網絡的動力學行為已有大量研究，例如，文獻[5]對基于流量感知路由策略的復雜網絡拓撲結構對流量傳輸的影響進行研究，考慮網絡拓撲、信息生成速率和各個節點的信息處理能力，解決拓撲對復雜網絡流量動態的影響問題。復雜網絡視角與其他視角的不同之處在于它可以定量描述一個復雜網絡的屬性[6]。然而定量描述網絡的前提是必須要對其進行測量，其中度中心性[7](degree centrality)作為復雜網絡中研究的重要測度，是網絡拓撲中與節點直接相連邊的數目的累加和，體現了網絡中個體與相鄰個體的交互能力[6]。度中心性的概念已廣泛應用于社交網絡關系的分析中，文獻[8]利用測量度中心性的方法分析了社交網絡中有影響力的人物關系以及交互次數的關系權重。文獻[9]則從多層社交網絡角度出發，提取多層社交網絡的組成結構，針對不同程度的度中心性進行網絡分析，得出節點在社交網絡中的關鍵程度。在航電網絡中，由于端系統之間信息交互差異巨大，采用度中心性理論可以有效分析信息交互頻繁的端節點在網絡中的關鍵地位，并以此為依據對航電網絡進行拓撲設計。

現有航空電子網絡拓撲的設計大多依靠人工，技術人員一般依據終端節點之間的通信關系以及交換機的特有連接構型對航電網絡拓撲進行設計。然而，當面對航電網絡節點規模日益龐大，信息交互量級不斷增加，任務性能保障訴求逐漸嚴格的情況下，依賴于設計人員經驗和技術的網絡設計就顯得捉襟見肘。因此，本文用節點度的大小表征節點間交互關系，將節點間數據交互規模加以考慮，提出基于度中心性理論依據節點間通信數據幀長的航空電子網絡拓撲自動生成算法，構建2種不同的組網規模，利用確定性網絡演算方法和仿真方法對生成網絡的實時性能進行評估。

1 AFDX網絡拓撲生成

1.1 AFDX網絡模型

對AFDX網絡研究一般采用離散事件的建模方法。離散事件建模的系統由模型實體以及實體之間的關系構成[10]。AFDX網絡拓撲由3部分組成：端系統、交換機和虛擬通信鏈路。AFDX網絡消息的通信過程由駐留于端系統的分區產生，并交由端系統上的虛擬鏈路來承載，虛擬鏈路從源端系統發出，經過交換機網絡的靜態路由轉發，最后到達目的端系統分區中。AFDX網絡的拓撲結構具有一定靈活性，適應大中型飛機的航空電子綜合化互聯。

AFDX網絡模型主要由端系統和交換機組成，采用雙冗余拓展型星型拓撲結構，異步傳輸模式，終端節點之間通過虛擬鏈路進行數據幀的交換。

1) 端系統模型

AFDX網絡的端系統中存在UDP/IP協議處理棧負責與應用分區的接口。端系統模型抽象如圖1[10]所示。依據抽象出的結構模型，可將端系統細分為發送端系統和接收端系統。

2) 交換機模型

交換機是具備網絡收發功能的模型，內部通過總線和交換控制模塊完成數據幀的交換轉發功能，且交換機各端口相互獨立。交換機端口具有接收和發送2種功能，在完成對數據的接收后查詢配置表，即可將數據轉發到目的端口。一組交換機端口從接收到發送的功能模型如圖2[10]所示，交換機模型則由多個端口模型共同構成。

3) 通信鏈路

AFDX網絡中的通信物理鏈路，指的是2個節點之間的連接。例如2個交換節點或1個交換節點和1個終端節點之間，它可以為消息傳輸提供給定的數率。此外，在一個物理連接中可能有多個邏輯鏈接。邏輯鏈接又叫虛擬鏈路(VirtualLink，VL)，是消息源和其目的端之間的邏輯鏈接，可以看作是用于消息交換的全局邏輯通道。通常，虛擬鏈路可以用帶寬分配間隔和最大數據包長度來表示。

圖1 端系統模型抽象圖[10]Fig.1 Schematic of end system model[10]

圖2 一組交換機端口模型圖[10]Fig.2 One set of switch port models[10]

1.2 AFDX網絡拓撲生成算法

AFDX網絡中不同終端節點所承載的通信任務緊要程度不同，根據所承載任務的緊要程度，可以將終端節點分為2種類型，即核心處理節點與外圍接入節點。核心處理節點承載了對實時性等性能要求較高的任務，同時也承載了部分對實時性要求較低的任務；外圍接入節點所承載的任務對實時性等性能要求相對較低。因此，在AFDX網絡拓撲生成算法中可將終端節點分成兩類考慮。

網絡拓撲生成算法將源終端節點與目的終端節點之間的數據交互規模加以考慮，AFDX網絡節點之間信息交互規模較大，任務通信較頻繁，則需要盡量滿足通信鏈路所經過的交換機跳數較少，使數據在傳輸過程中的延遲較小，保證數據傳輸的實時性。在AFDX網絡中，消息具體的傳輸過程包含固定時延和有界時延。有界時延包括多路復用排隊時延和鏈路傳輸時延，二者都與數據幀長緊密相關。考慮到AFDX網絡拓撲中端節點之間邊的實際意義與數據幀長的關系，將兩節點之間存在所有VL的數據幀長度求和作為節點的度中心性抽象指標。

對于AFDX網絡，兩節點間通信幀長總和越大，表征節點度越大，就意味著這個節點的度中心性越高，說明該節點在AFDX網絡中的數據交互規模龐大，任務通信繁雜。由于度中心性高的核心處理端節點占網絡所有信息交互規模比重較大，因此需要將兩節點之間的通信幀長總和以及交換機對于信息的處理轉發能力加以考慮，按照核心處理節點占總終端節點的比例將端節點進行集合劃分，盡可能減少虛擬鏈路經過交換機的跳數，降低數據傳輸的排隊轉發延遲以及鏈路傳輸延遲。在進行交換機連接拓撲的生成過程中，由于交換機需要對其上連接的所有端節點的數據進行存儲轉發操作，因此將劃分集合后的端節點作為整體考慮，進行交換機連接判斷。算法具體流程如下：

1) AFDX網絡配置設定

輸入AFDX網絡的交換機配置、各個終端節點的通信配置以及虛擬鏈路的配置。

在配置過程中，將AFDX網絡中用到的交換機個數，交換機端口數以及交換機技術延遲等參數進行說明。將終端節點之間交互信息的屬性進行說明，包括：源終端節點、目的終端節點、數據幀長，幀間間隔以及虛擬鏈路路由規則。

對于本算法虛擬鏈路的配置，其路徑皆要遵循最短路徑原則。

2) 核心處理節點集合劃分

集合的數量等于交換機的數量，集合序號與交換機序號一一對應。選取某一核心處理節點作為種子節點，計算該節點與其他所有核心節點間所有VL的數據幀長和，并作為節點度，按照數據幀長和的大小對其他核心節點進行降序排列。在集合劃分過程中，按照降序依次選擇其他核心處理節點與種子節點劃分到同一集合中，若某核心節點已經成為其他集合中的元素，則跳過該節點的劃分。為了對交換機端口做出一定預留，根據核心節點占所有節點數量的比例，在每個交換機上掛載核心處理節點的端口數占該交換機所有端口數的比例不超過該比例值。考慮交換機負載均衡的原因，為了避免將通信數據量規模較大的端系統分配到同一集合，掛載到同一交換機上，“集合劃分”會分兩輪進行。當集合第一輪分配結束后，還有剩余核心處理節點未劃分，針對剩余每個核心節點，分別比較該節點與各個集合中已有的所有核心節點的數據幀長之和，選擇和最大的集合，將該核心節點加入其中，直至所有核心節點劃分結束。核心處理節點集合劃分流程圖如圖3所示。

圖3 核心處理節點集合劃分流程圖Fig.3 Core processing node set division flowchart

3) 外圍接入節點集合劃分

對任意一個外圍節點計算與各個集合中已有的每一個核心節點的所有VL通信數據幀長的總和，選擇和最大的集合，將外圍節點加入到該集合中，直至所有外圍節點集合劃分完畢。

4) 終端節點與交換機連接

將每個集合中的節點分別掛載到交換機上。

5) 交換機拓撲構建

分別將兩集合內不同節點間的所有VL通信數據幀長求和，根據上述各集合間通信總幀長求集合間通信總幀長的平均值，將兩集合通信總幀長大于平均值所對應的交換機進行連接。

算法簡化示意圖如圖4所示。

圖4 基于度中心性的AFDX網絡拓撲生成算法Fig.4 AFDX network topology generation algorithm based on degree centrality

2 算法效能評估

2.1 算法評價

對于一個規劃完成的AFDX網絡，所有的終端節點的數據業務都是提前規定好的，而且網絡拓撲一旦設計完成，交換機的路由轉發也就固定不變。因此網絡拓撲生成算法的實時性能可以根據數據流的端到端延遲進行評價。

參照空客公司提出的典型AFDX網絡拓撲中交換機連接結構[11]，根據端系統之間通信聯系緊密程度、信息交互數據量大小以及減少交換機發生擁堵可能性的均衡原則將端系統掛載到各個交換機上，由此構建由8個交換機(S1～S8)和24個終端節點(E1～E24)組成的互聯網絡如圖5所示。

假定節點1～16承載的大部分任務實時性能較強，為核心處理節點；節點17～24承載的任務關鍵性較弱，為外圍接入節點。

終端節點之間通信配置信息如表1所示。利用基于度中心性AFDX網絡拓撲生成算法，生成的網絡拓撲如圖6所示。

分別采用解析方法(網絡演算)和仿真方法實現網絡性能的分析與評價，依據于具體的網絡和流量配置參數，探尋流量干擾影響，實現信息交互的端到端延遲評估。

2.2 解析方法

解析方法一般指利用數學建模方法計算消息端到端延遲上界，最常見的即為網絡演算方法。確定性網絡演算[12-13]是一種基于最小加代數(min-plus)理論的網絡性能分析方法，通過到達曲線和服務曲線的約束來計算消息最壞情況下的延遲上限。網絡演算中常用的核心公式包括到達曲線[14]α(t)、服務曲線[15]β(t)以及延遲上界h(α,β)，延遲上界為到達曲線α(t)和服務曲線β(t)之間的最大水平距離，由圖7中標記有h(α,β)的水平箭頭給出。圖中：ασ，ρ(t)為數據流的到達曲線，表示數據流允許最大發度為σ，且持續流量為ρ，βC,T(t)為輸出節點的服務曲線，表示具有固有技術時延為T,輸出速率為C。

圖5 人為規劃網絡拓撲Fig.5 Artificially designed network topology

表1 網絡參數配置信息Table 1 Network parameter configuration information

根據交叉通信且通信鏈路源和目的端涵蓋大多數端節點的原則，由表1提取核心節點之間、核心節點與外圍接入節點之間以及外圍接入節點之間部分VL配置，如表2所示，利用確定性網絡演算方法進行數據流的端到端延遲計算來驗證網絡拓撲生成算法的實時性能，路徑規劃遵循最短路徑原則，網絡鏈路傳輸為100 Mbit/s，交換機技術延遲為16 μs[16]。

在相同配置下人為規劃網絡拓撲與基于度中心性的AFDX網絡拓撲生成算法生成的網絡拓撲的端到端延遲對比，如圖8所示。從圖8中可以看出在50條VL組網規模下基于度中心性的拓撲生成算法生成的網絡拓撲中75%的VL實時性能優于人為規劃網絡拓撲，且端到端延遲平均減小9.37%。

2.3 仿真方法

利用OMNet++平臺構建網絡仿真模型，模擬AFDX網絡[17]，配置參數如表1所示，共1 400條VL。網絡鏈路傳輸為100 Mbit/s，交換機技術延遲為16 μs[16]。

結果分析：利用仿真實驗對比人為規劃網絡拓撲與基于度中心性的拓撲生成算法生成的網絡拓撲的平均端到端延遲，如圖9所示。在圖9中，橫坐標代表虛擬鏈路編號，縱坐標表示各條虛擬鏈路的平均端到端延遲，紅色實線表示人為規劃拓撲中不同虛擬鏈路的平均端到端延遲，藍色虛線則表示算法生成拓撲的不同虛擬鏈路的平均端到端延遲。從圖9中可以看出算法生成的網絡拓撲中94.3%的VL實時性能優于人為規劃網絡拓撲，且平均端到端延遲平均減小50.2%。然而虛擬鏈路編號681～730以及781～810處，算法生成拓撲的平均端到端延遲要略高于人為規劃拓撲的端到端延遲。針對本案例，是由于承載上述虛擬鏈路必經的交換機上連接的皆為核心處理節點，且上述核心處理節點處理的數據規模相對于其他核心節點較大，造成當前時刻交換機瞬時擁塞，引起轉發排隊延遲時間較長，增加了排隊延遲，因此導致這一小部分數據流端到端延遲沒有明顯改善。

圖6 算法生成網絡拓撲Fig.6 Algorithm generated network topology

圖7 確定性網絡演算分析模型Fig.7 Deterministic network calculus analysis model

表2 網絡演算配置信息Table 2 Network calculus configuration information

圖8 網絡演算對比人為規劃網絡拓撲和算法生成拓撲最壞端到端延遲Fig.8 Network calculus comparison of the worst end-to-end delay between artificially designed network topology and algorithm generated network topology

圖9 人為規劃拓撲和算法生成拓撲平均端到端延遲仿真對比Fig.9 Simulation comparison of average end-to-end delay between artificially designed network topology and algorithm generated topology

3 結 論

1) 本文基于復雜網絡中的度中心性理論，以AFDX網絡節點之間所有VL通信數據幀長之和為度，根據兩節點間通信幀長總和，提出了適應于AFDX網絡的拓撲結構生成算法。

2) 應用網絡演算方法對比分析了人為規劃的網絡拓撲與自動生成算法生成的網絡拓撲的實時性能。從計算結果可以看出自動生成算法生成的拓撲中75%的虛擬鏈路的實時性優于人為規劃的拓撲。

3) 基于OMNet++平臺，設計人為規劃拓撲與算法生成拓撲的行為仿真模型，對人為規劃拓撲和算法生成拓撲實時性進行了仿真對比分析。在1 400條數據流量的配置下，其中有1 320條流量在算法生成拓撲中實時性能較好，較人為規劃拓撲實時性提高了50.2%；算法改善了大部分虛擬鏈路的實時性能，然而由于數據流突發等原因，增加了小部分虛擬鏈路的排隊延遲，導致80條流量端到端延遲沒有很大改善。

本算法以流量均衡分布和就近接入為目標，可以在絕大多數情況下為流量的接入交換和骨干交換提供一個平穩的流量交互網絡拓撲，保證了大多數流量傳輸的實時性。從數據分析中也可以看出算法在很大程度上提高了AFDX網絡的實時性能。