基于轨迹方法的AFDX网络路由配置算法

刘 成 李 航 何 锋 卢广山

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

航空电子全双工交换式以太网(AFDX，Avionics Full Duplex Switched Ethernet)［1－2］是由工业以太网经过适应性改造而成的航空电子系统互连确定性网络，目前已经被应用于空中客车A380大型飞机和波音787宽体客机中.

针对航空电子网络严格的实时性要求，AFDX网络对虚拟链路(VL，Virtual Link)采用了带宽分配机制和静态路由机制，规划了数据包的带宽和路径，限制数据源的突发度，在交换机中采用漏桶算法，隔离了拥塞，这些都保证了AFDX网络行为的确定性.这些AFDX网络的确定性机制结合网络演算理论［3－4］和轨迹计算方法［5］，发展出了适用于AFDX网络的最大延时计算的方法［6－8］.这些方法能得到虚拟链路上数据包的最大端到端延时，为研究AFDX网络的实时性提供理论依据.

虽然AFDX网络有着保证网络行为确定性的机制和网络演算理论依据，作为AFDX网络关键技术的VL静态路由配置却没能把它们结合起来.目前，AFDX网络中虚拟链路的静态路由配置算法常采用的是最短路径算法［9］和负载均衡算法［10］，这些算法只是对网络的资源进行了有效的利用，并没有针对VL的延时约束特性进行优化，无法保证所有的VL的最大网络延迟满足其约束.本文提出一种结合 AFDX网络的轨迹方法［7－8］对VL进行静态路由配置的 TRJ算法.该静态路由配置算法在AFDX网络资源充足的前提下，保证配置后的所有VL的端到端最大延迟不超过初始给定的VL延时约束.

1 轨迹方法

1.1 定 义

确定性网络演算(network calculus)技术最初是由 Cruz R.较为系统地提出的［3－4］，用来计算网络中数据包的最大端到端延时值.文章［6］结合AFDX网络的特点对确定性网络演算进行了适应性改进.法国图卢兹大学IRIT实验室的学者在常规轨迹计算方法［5］的基础上提出一种计算AFDX网络数据包端到端最大延时的轨迹方法［7］，在文献［8］中将此方法与常用AFDX网络演算方法［6］进行了比较，证明了基于AFDX网络的轨迹方法是一种端到端最大延时计算结果更紧的AFDX网络演算方法.

根据轨迹方法［5］定义，VL的最大端到端延时被限定在:

其中:

3)(1+⎿(t+ji)/Ti」)+·Ci，是数据包 m 在路径Pi中，经过最慢节点时的发送延时.

6)(|Pi|－1)·lmax，是交换机的技术时延之和，通常技术时延是8 μs.

1.2 延时约束分析

证明

将等式右边与时间t有关的项提出来，得到

其中，Cj=Lmaxj/C，C是AFDX网络的带宽，Lmaxj是Vj最大的帧长，经过变换得到

由文献［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，优先选取最短路径，同为最短路径时，则选择具有最大可用带宽的一条路径)配置全部VL的静态路由后，计算所有VL的延时约束比，延时约束比越大，给该VL设置越高的配置优先级，在实际结合轨迹方法的路由配置算法中，优先配置.

证明 采用WSP算法配置的静态路由，是VL的最短路径下最大可用带宽的路由路径，即保证总资源占用率最小的情况下，兼顾负载均衡.此时，延时约束比大的VL最合理地减小约束比的方式是:保持自己当前的最短路径，而减小其他VL与自己的交集.故延时约束比大的VL应该拥有较高的配置优先级，先予以配置最短最宽的路径;延时约束比低的VL拥有较低的配置优先级，后配置，并结合轨迹方法，避开较高优先级的VL已配置的路径. 证毕

2.2 TRJ 算法描述

1)根据定理3，用WSP算法配置所有VL的静态路由，根据给定的VL延时约束和计算得到的所有VL的端到端最大延时，计算VL的延时约束比D，按照延时约束比从大到小的顺序给VL排序，对应标记为 Vi(i=1，2，…，n)，转到2);

2)按照标记顺序，重新配置所有VL的路由，初始值i=1;

3)若 i＞n，转到 4)，否则计算所有 Vj(j＜i)的延时余度帧长，若小于Lmaxi则将Vj所经过的路径标记为断路，然后配置Vi的K条最短路径，在K条最短路径中找到满足Vj最大延时约束的最小跳均衡路径，循环3)，若找不到满足条件的路由路径，跳到5);

4)所有满足延时约束条件的VL路由配置完成;

5)无法配置全部满足延时约束条件的VL路由.

2.3 算法复杂度分析

设一共有n个节点，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网络环境，拓扑如图1所示，外围4个交换机分别与16个端系统相连接，并且与内层的一个交换机级联，这5个交换机构成了AFDX网络的主干，承载了总共64个端系统，每条链路带宽是100 Mbit/s.实验设计了1000条VL，使用VLID作为VL的ID号，用来区分每条VL，Lmax服从64到512字节随机均匀分布，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)所示;每个端系统的平均输出带宽占VL总带宽的1/64，是0.53 Mbit/s.

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

图1 AFDX拓扑

图2 VL的BAG配置

分别使用最短路径的WSP算法、负载均衡的SWP算法(最短最宽路径算法，选择最大可用带宽的路径，如果同时存在几条最宽路径，则优先考虑其中跳数最小的路径)和TRJ算法，对该实验网络进行VL路由配置.使用AFDX轨迹方法分别对不同算法的VL路由配置结果进行计算，得到各个算法配置下的VL的最大端到端延时，并将计算的延时结果和初始约束值进行比较，如图3～图5所示.WSP算法的配置结果是，部分VL的端到端最大延时大大超过延时约束值，而SWP算法的配置结果稍好一些，部分VL的端到端最大延时值略微超过延时约束值，但这两种算法都没能使配置结果满足延时约束.TRJ算法的配置结果则保证了所有的VL的端到端最大延时在延时约束的范围内.

图3 WSP的延时曲线

图4 SWP的延时曲线

图5 TRJ的延时曲线

WSP算法为所有VL都配置了最短路径，消耗的网络资源最少，主干链路的平均带宽利用率是2.32%，但是可能在局部造成阻塞，导致大量通过阻塞局部的VL的端到端延时大大超过约束延时值.SWP算法选取了负载均衡的路由，代价是VL选择了非最短的路径，占用了更多的网络资源，使得链路中流量的分配最为均衡，主干链路的平均带宽利用率是2.89%，但是SWP算法并没有能保证所有的VL的端到端最大延时值限定在约束值的范围内.TRJ算法，结合了AFDX轨迹方法，在配置的过程中就限制了VL的路由路径产生的端到端最大延时不会超过延时约束值，代价是VL选择了不会超时的路由路径，占用了较多网络资源，主干链路的平均带宽利用率是2.57%.在带宽资源充足的情况下，TRJ算法不会影响网络节点和VL的正常配置.

4 结束语

AFDX网络是适用于新一代大型客机的航电互联网络，在实时性方面有着严格的保障机制，并且近年来新起的网络延时计算技术，也为AFDX网络的实时性提供了理论工具.但是对于AFDX网络的关键技术——VL路由配置，却没有利用AFDX网络的这些机制和理论工具.

为了优化AFDX网络的VL路由配置，满足AFDX网络对实时性的要求，本文提出一种结合AFDX网络的轨迹方法对VL进行静态路由配置的TRJ算法.该算法保证了配置后的VL的端到端最大延时在其给定的初始延时约束值的范围内.经过实验验证了该算法有效性，在对实时性要求严格的航空电子网络环境下，较最短路径算法和负载均衡算法更有针对性.

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，Fraboul C，Grieu J.Using network calculus to optimize the AFDX network［C］//Proceedings of ERTS.Toulouse，France:［s.n.］，2006

［7］Bauer H，Scharbarg J－L，Fraboul 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，Fraboul 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