劉 成 李 航 何 鋒 盧廣山

(北京航空航天大學 電子信息工程學院，北京100191)

航空電子全雙工交換式以太網(wǎng)(AFDX，Avionics Full Duplex Switched Ethernet)［1－2］是由工業(yè)以太網(wǎng)經(jīng)過適應性改造而成的航空電子系統(tǒng)互連確定性網(wǎng)絡，目前已經(jīng)被應用于空中客車A380大型飛機和波音787寬體客機中.

針對航空電子網(wǎng)絡嚴格的實時性要求，AFDX網(wǎng)絡對虛擬鏈路(VL，Virtual Link)采用了帶寬分配機制和靜態(tài)路由機制，規(guī)劃了數(shù)據(jù)包的帶寬和路徑，限制數(shù)據(jù)源的突發(fā)度，在交換機中采用漏桶算法，隔離了擁塞，這些都保證了AFDX網(wǎng)絡行為的確定性.這些AFDX網(wǎng)絡的確定性機制結合網(wǎng)絡演算理論［3－4］和軌跡計算方法［5］，發(fā)展出了適用于AFDX網(wǎng)絡的最大延時計算的方法［6－8］.這些方法能得到虛擬鏈路上數(shù)據(jù)包的最大端到端延時，為研究AFDX網(wǎng)絡的實時性提供理論依據(jù).

雖然AFDX網(wǎng)絡有著保證網(wǎng)絡行為確定性的機制和網(wǎng)絡演算理論依據(jù)，作為AFDX網(wǎng)絡關鍵技術的VL靜態(tài)路由配置卻沒能把它們結合起來.目前，AFDX網(wǎng)絡中虛擬鏈路的靜態(tài)路由配置算法常采用的是最短路徑算法［9］和負載均衡算法［10］，這些算法只是對網(wǎng)絡的資源進行了有效的利用，并沒有針對VL的延時約束特性進行優(yōu)化，無法保證所有的VL的最大網(wǎng)絡延遲滿足其約束.本文提出一種結合 AFDX網(wǎng)絡的軌跡方法［7－8］對VL進行靜態(tài)路由配置的 TRJ算法.該靜態(tài)路由配置算法在AFDX網(wǎng)絡資源充足的前提下，保證配置后的所有VL的端到端最大延遲不超過初始給定的VL延時約束.

1 軌跡方法

1.1 定 義

確定性網(wǎng)絡演算(network calculus)技術最初是由 Cruz R.較為系統(tǒng)地提出的［3－4］，用來計算網(wǎng)絡中數(shù)據(jù)包的最大端到端延時值.文章［6］結合AFDX網(wǎng)絡的特點對確定性網(wǎng)絡演算進行了適應性改進.法國圖盧茲大學IRIT實驗室的學者在常規(guī)軌跡計算方法［5］的基礎上提出一種計算AFDX網(wǎng)絡數(shù)據(jù)包端到端最大延時的軌跡方法［7］，在文獻［8］中將此方法與常用AFDX網(wǎng)絡演算方法［6］進行了比較，證明了基于AFDX網(wǎng)絡的軌跡方法是一種端到端最大延時計算結果更緊的AFDX網(wǎng)絡演算方法.

根據(jù)軌跡方法［5］定義，VL的最大端到端延時被限定在:

其中:

3)(1+?(t+ji)/Ti」)+·Ci，是數(shù)據(jù)包 m 在路徑Pi中，經(jīng)過最慢節(jié)點時的發(fā)送延時.

6)(|Pi|－1)·lmax，是交換機的技術時延之和，通常技術時延是8 μs.

1.2 延時約束分析

證明

將等式右邊與時間t有關的項提出來，得到

其中，Cj=Lmaxj/C，C是AFDX網(wǎng)絡的帶寬，Lmaxj是Vj最大的幀長，經(jīng)過變換得到

由文獻［7］可知，Ai，j?Tj，ji?Ti，可以進行簡化，易證端到端最大延時值表達式. 證畢

定理2 新配置的 Vn+1((n+1)?［1，n］)若在路徑上與已配置Vi同流向交集，最多增加Vi的端到端最大延時值為

證明 若Vn+1若在路徑上與已配置Vi同流向交集，由式(3)給出的端端最大延時表達式易證 ΔRi=Ri－Rj(i∈［1，n+1］，j∈［1，n］)的差值如定理2所示. 證畢

2 路由配置算法

2.1 定 義

定義1 延時約束比

Ti是Vi的延時約束比;Ri是Vi的最大端到端延時值;Di是Vi給定的約束延時值.當Ti≤1時，Vi滿足延時約束;當Ti＞1，Vi不滿足延時約束.

定義2 延時余度幀長

ΔRi=Di－Ri是Vi最多可以增加的延時值，將算出的 ΔRi代入式(4)中，解出 Cn+1，Lmax(n+1)=Cn+1·C則是Vi的延時余度幀長，物理意義是在Vi路由路徑中，可以加入的Vn+1的最大幀長.

定理3 采用最寬最短路徑算法［9］(WSP，Widest Shortest Path，優(yōu)先選取最短路徑，同為最短路徑時，則選擇具有最大可用帶寬的一條路徑)配置全部VL的靜態(tài)路由后，計算所有VL的延時約束比，延時約束比越大，給該VL設置越高的配置優(yōu)先級，在實際結合軌跡方法的路由配置算法中，優(yōu)先配置.

證明 采用WSP算法配置的靜態(tài)路由，是VL的最短路徑下最大可用帶寬的路由路徑，即保證總資源占用率最小的情況下，兼顧負載均衡.此時，延時約束比大的VL最合理地減小約束比的方式是:保持自己當前的最短路徑，而減小其他VL與自己的交集.故延時約束比大的VL應該擁有較高的配置優(yōu)先級，先予以配置最短最寬的路徑;延時約束比低的VL擁有較低的配置優(yōu)先級，后配置，并結合軌跡方法，避開較高優(yōu)先級的VL已配置的路徑. 證畢

2.2 TRJ 算法描述

1)根據(jù)定理3，用WSP算法配置所有VL的靜態(tài)路由，根據(jù)給定的VL延時約束和計算得到的所有VL的端到端最大延時，計算VL的延時約束比D，按照延時約束比從大到小的順序給VL排序，對應標記為 Vi(i=1，2，…，n)，轉到2);

2)按照標記順序，重新配置所有VL的路由，初始值i=1;

3)若 i＞n，轉到 4)，否則計算所有 Vj(j＜i)的延時余度幀長，若小于Lmaxi則將Vj所經(jīng)過的路徑標記為斷路，然后配置Vi的K條最短路徑，在K條最短路徑中找到滿足Vj最大延時約束的最小跳均衡路徑，循環(huán)3)，若找不到滿足條件的路由路徑，跳到5);

4)所有滿足延時約束條件的VL路由配置完成;

5)無法配置全部滿足延時約束條件的VL路由.

2.3 算法復雜度分析

設一共有n個節(jié)點，m條VL.WSP路由的時間復雜度為O(n3);計算所有Vj(j＜i)的延時余度幀長的最大時間復雜度為O((i－1)2·n)，計算Vj的K條最小跳路采用K次Dijskra算法，時間復雜度為 O(K·n2)，配置 Vi時的時間復雜度為 O((i－1)2·n+K·n2).綜合計算得到 TRJ算法的時間復雜度為

3 實驗分析

本文設計了一個典型的AFDX網(wǎng)絡環(huán)境，拓撲如圖1所示，外圍4個交換機分別與16個端系統(tǒng)相連接，并且與內層的一個交換機級聯(lián)，這5個交換機構成了AFDX網(wǎng)絡的主干，承載了總共64個端系統(tǒng)，每條鏈路帶寬是100 Mbit/s.實驗設計了1000條VL，使用VLID作為VL的ID號，用來區(qū)分每條VL，Lmax服從64到512字節(jié)隨機均勻分布，VL 的 BAG 分為 4 類，32 ms，64 ms，128 ms和256 ms，每類 BAG分別配置有250條 VL，與BAG的關系所圖2所示.VL的延時約束設置為各自BAG的1/8.預計全部VL占用的總帶寬是33.75 Mbit/s，如式(6)所示;每個端系統(tǒng)的平均輸出帶寬占VL總帶寬的1/64，是0.53 Mbit/s.

33.75 × 10= ［(64+512)/2］× 8/0.032 ×

圖1 AFDX拓撲

圖2 VL的BAG配置

分別使用最短路徑的WSP算法、負載均衡的SWP算法(最短最寬路徑算法，選擇最大可用帶寬的路徑，如果同時存在幾條最寬路徑，則優(yōu)先考慮其中跳數(shù)最小的路徑)和TRJ算法，對該實驗網(wǎng)絡進行VL路由配置.使用AFDX軌跡方法分別對不同算法的VL路由配置結果進行計算，得到各個算法配置下的VL的最大端到端延時，并將計算的延時結果和初始約束值進行比較，如圖3～圖5所示.WSP算法的配置結果是，部分VL的端到端最大延時大大超過延時約束值，而SWP算法的配置結果稍好一些，部分VL的端到端最大延時值略微超過延時約束值，但這兩種算法都沒能使配置結果滿足延時約束.TRJ算法的配置結果則保證了所有的VL的端到端最大延時在延時約束的范圍內.

圖3 WSP的延時曲線

圖4 SWP的延時曲線

圖5 TRJ的延時曲線

WSP算法為所有VL都配置了最短路徑，消耗的網(wǎng)絡資源最少，主干鏈路的平均帶寬利用率是2.32%，但是可能在局部造成阻塞，導致大量通過阻塞局部的VL的端到端延時大大超過約束延時值.SWP算法選取了負載均衡的路由，代價是VL選擇了非最短的路徑，占用了更多的網(wǎng)絡資源，使得鏈路中流量的分配最為均衡，主干鏈路的平均帶寬利用率是2.89%，但是SWP算法并沒有能保證所有的VL的端到端最大延時值限定在約束值的范圍內.TRJ算法，結合了AFDX軌跡方法，在配置的過程中就限制了VL的路由路徑產(chǎn)生的端到端最大延時不會超過延時約束值，代價是VL選擇了不會超時的路由路徑，占用了較多網(wǎng)絡資源，主干鏈路的平均帶寬利用率是2.57%.在帶寬資源充足的情況下，TRJ算法不會影響網(wǎng)絡節(jié)點和VL的正常配置.

4 結束語

AFDX網(wǎng)絡是適用于新一代大型客機的航電互聯(lián)網(wǎng)絡，在實時性方面有著嚴格的保障機制，并且近年來新起的網(wǎng)絡延時計算技術，也為AFDX網(wǎng)絡的實時性提供了理論工具.但是對于AFDX網(wǎng)絡的關鍵技術——VL路由配置，卻沒有利用AFDX網(wǎng)絡的這些機制和理論工具.

為了優(yōu)化AFDX網(wǎng)絡的VL路由配置，滿足AFDX網(wǎng)絡對實時性的要求，本文提出一種結合AFDX網(wǎng)絡的軌跡方法對VL進行靜態(tài)路由配置的TRJ算法.該算法保證了配置后的VL的端到端最大延時在其給定的初始延時約束值的范圍內.經(jīng)過實驗驗證了該算法有效性，在對實時性要求嚴格的航空電子網(wǎng)絡環(huán)境下，較最短路徑算法和負載均衡算法更有針對性.

References)

［1］ARINC 664 Aircraft data network，part 2:Ethernet physical and data link layer specification［S］

［2］ARINC 664 Aircraft data network，part 7:avionics full duplex switched Ethernet(AFDX)Network［S］

［3］Cruz R.A calculus f or net work delay，part I:net work elements in isolation［J］.IEEE Trans Information Theory ，1991，37(1):114－131

［4］Cruz R.A calculus for net work delay，part II:network analysis［J］.IEEE Trans Information Theory，1991，37(1):132－141

［5］Martin S，Minet P.Schedulability analysis of flows scheduled with fifo:application to the expedited forwarding class［C］//Parallel and Distributed Processing Symposium，2006.IPDPS 2006.Rhodes Island:［s.n.］，2006

［6］Frances F，F(xiàn)raboul C，Grieu J.Using network calculus to optimize the AFDX network［C］//Proceedings of ERTS.Toulouse，F(xiàn)rance:［s.n.］，2006

［7］Bauer H，Scharbarg J－L，F(xiàn)raboul C.Applying and optimizing trajectory approach for performance evaluation of AFDX avionics network［C］//Proc 21th ECRTS WiP Section.Dublin，Ireland:［s.n.］，2009，57－60

［8］Bauer H，Scharbarg J－L，F(xiàn)raboul C.Improving the worst－case delay analysis of an AFDX network using an optimized trajectory approach［J］.IEEE Trans Industrial Informatics，2010，6(4):521－533

［9］Guerin R，Orda A，Williams D.QoS routing mechanisms and OSPF extensions［C］//Global Telecommunications Conference.［S.l.］:IEEE，1997:1903－1908

［10］Zheng Wang，CrowcroftJ.Quality－of－serviceroutingfor supporting multimedia applications［J］.IEEE Journal on Selected Area in Communications，1996，14(7):1228－1234