应用混合队列调度策略的AFDX实时性优化研究

刘 静

（1.渭南师范学院数学与信息科学学院，陕西渭南714099；2.渭南市智慧城市工程技术研究中心，陕西渭南714099）

应用混合队列调度策略的AFDX实时性优化研究

刘 静1，2

（1.渭南师范学院数学与信息科学学院，陕西渭南714099；2.渭南市智慧城市工程技术研究中心，陕西渭南714099）

航空电子全双工交换式以太网（AFDX）对传输的数据流采用先到先服务（FCFS）调度策略，导致安全关键性数据的网络延迟较大，拥塞情况下的数据流延迟存在不确定性。为解决该问题，提出一种用于优化AFDX网络实时性的混合队列调度策略，综合FCFS调度策略、静态优先级队列调度策略和差额轮询调度策略的优点，通过网络演算分析数据流的延迟上界，理论验证硬实时数据流满足AFDX网络通信需求。仿真实验结果表明，混合队列调度策略不仅可以保证AFDX网络中安全关键性数据流的实时性，以及非安全关键性数据流的调度公平性，而且能有效隔离恶意数据流。

混合队列调度策略；网络演算；航空电子全双工交换式以太网；虚链路；端到端延迟

1 概述

近年来，航空电子系统网络协议作为现代航空电子系统的重要组成部分，得到了快速发展［1］。航空电子全双工交换式以太网（Avionics Full Duplex Sw itched Ethernet Network，AFDX）是空中客车公司在研制空客A380的过程中，基于IEEE 802.3［2］和美国爱瑞克664（ARINC 664）［3］标准提出的新一代航空数据总线。相比之前的美国爱瑞克429（ARINC 429）、军标-1553（M IL-STD-1553）以及增强型1553B标准，AFDX进一步提高了机载网络的灵活性、模块性、扩展性、传输速率等。AFDX网络采用全双工技术避免传统以太网在终端系统中的资源冲突问题。然而，AFDX并没有完全消除传统以太网传输中的不确定性，各种数据流在交换机内部竞争资源，导致更大的延迟和不公平性［4］。

为此，越来越多的研究人员开始致力于AFDX网络的性能提升以及可靠性验证工作。网络性能指标一般包括吞吐量、端到端延时、延迟抖动、差错率等。其中端到端延时是AFDX网络的关键性能参数。目前关于AFDX网络端到端延时的研究主要包括计算端到端延时上界和减少网络端到端延时这2个方面。

AFDX协议［3］中使用先到先服务（First Come First Serve，FCFS）调度策略，该策略公平地对待每一种数据流，调度服务器按照数据流到达顺序来转发相应的数据。文献［4］用网络演算［5-6］方法计算了特定配置下的AFDX网络的端到端延时上界，发现网络演算方法计算了最坏情况下的网络端到端延时上界，通常实际网络中的端到端延时要小于该上界。文献［7］在运用网络演算分析计算数据流在FCFS策略下的网络端到端延时，发现FCFS策略不区分优先级，容易引起某些紧急数据流的传输超时，不能很好地满足不同数据流的实时性传输要求。

为了满足不同数据流的服务质量要求，文献［8］在交换机中应用静态优先级（Static Priority，SP）调度策略，使安全关键性数据流的延迟上界小于FCFS调度策略下的延迟上界，但仍不能完全满足航空电子系统中数据流的传输要求。文献［9］将AFDX网络数据流分为3个优先级，改进传统优先级算法，降低高优先级数据流的延迟抖动上界，但忽略了同一优先级的数据流的公平调度。文献［10］针对AFDX中有一定时延要求的非安全关键类数据流采用负载分类的方法，提高了较小负载的实时性，但导致较大负载面临更大时延。文献［11］分析了AFDX网络中多包发送的响应时间，可以应用于异构分布式网络，但在时延分析中以位为单位，所求得的结果存在误差。文献［12］提出通过优化虚链路的参数来提高AFDX网络的链路带宽利用率，降低了部分链路的最大延迟上界，但大幅提高了多包数据延迟。文献［13］结合静态优先级策略，并通过轨迹法得到AFDX网络中数据流的较小平均时延上限，但对部分数据的延迟影响很大。文献［14］在交换机中应用差额轮询（Deficit Round Robin，DRR）调度策略，保证数据流的公平调度，但降低了安全关键性数据流的实时性。综上所述，优化AFDX网络协议，建立确定网络端到端延迟的AFDX网络，对于扩大AFDX的应用范围具有重要作用。

本文在分析AFDX网络中数据流实时性需求的基础上，提出了一种新的调度策略，使AFDX中安全关键性数据流的实时性得以保障，同时为非安全关键性数据流提供公平的调度服务，并在特定的AFDX网络配置下，从理论推导和实验仿真2个方面证明新的调度策略对AFDX网络实时性的优化作用。

2 网络演算及调度策略

2.1 网络演算基本理论

20世纪90年代初，Cruz R L在研究网络传输时延的过程中分析了6种网络基础元素，同时定义了整形器、服务曲线和到达曲线等概念。随后，Boudec JY和Chang C S等人进一步发展了网络演算理论，特别是引入了极小代数的数学表示方法，使其得到了广泛应用，同时，随机性网络演算也取得了一些研究成果［15］。

现在的网络演算理论最重要的概念是到达曲线和服务曲线，网络演算理论可以使用这2个概念计算延迟、积压等参数的上确界。

定义1（广义增函数） 广义增函数f（t）是指当s≤t时，f（s）≤f（t）的函数。可记F为在t＜0时f（t）=0的广义增函数的集合，F0为在t≤0时f（t）=0的广义增函数的集合。

定义2（极小卷积） 设f，g∈F，则f和g的极小卷积为（f⊗g）（t）=inf｛f（t-s）+g（s）|0≤s≤t｝，且当t＜0时，（f⊗g）（t）=0。

定义3（到达曲线） 设A，α∈F，如果对于所有s≤t：A（t）-A（s）≤α（t-s），则称A的值受限于α，α为A的到达曲线，或者数据流A经过α整流。

定义4（服务曲线） 当网络元素S的输入和输出累积函数分别为A（t）和D（t）时，称服务曲线为β当且仅当β∈F0且D＞A⊗β。

网络演算理论可以计算已知到达曲线的数据流，通过已知服务曲线的网络元素过程中的数据流的延迟、交换机的积压等参数的上确界。

定义7（输出流的到达曲线） 假设一个到达曲线为α的流通过一个服务曲线为β的网络元素，则输出流的到达曲线为α*=α⊗β。

定义8（串联系统的服务曲线） 假设一个流顺序经过网络元素S1和S2，Si提供的服务曲线为βi，i=1，2，则串联系统所提供的服务曲线为βΣ=β1⊗β2。

当输入数据流的到达曲线为α（t）=rt+b，起到服务节点作用的网络元素的服务曲线为β（t）= C［t-d］+，则最大延迟为，最大积压为Backlog=rd+b，如图1所示。

图1 延迟和积压示意图

随着应用需求的不断提高，网络演算也不断发展，并在整形器和窗口流量控制领域取得了卓越的研究成果，更因为成功解释了突发量仅计算一次（pay burst only once）的串联链路延迟不需累加现象而得到进一步普及。

2.2 AFDX混合队列调度策略

在实际应用中，网络中传输各式各样的数据流，依据不同的实时性需求，可以将航电网络中传输的数据分为4类［16］：（1）非周期性，有极高时延要求的紧急数据，如警报；（2）周期性，有硬性时延要求的数据，如传感器数据；（3）非周期性，有一定时延要求但不紧急的数据；（4）非周期性，也没有时延要求的数据，如文件传输。其中，第（1）类和第（2）类为安全关键性数据流；第（3）类和第（4）类为非安全关键性数据流。本文主要研究前3类数据流的实时特性。

通过对数据划分优先级，可以有效地降低高优先级数据流的传输时延。本文在传统静态优先级队列调度机制的基础上，结合流量整形和轮询调度算法，提出应用于AFDX网络的混合队列调度策略（M ixed Queue Scheduling on AFDX，MQSA），用于满足AFDX网络中数据流的实时性需求。

MQSA策略依据数据流对实时性的需求，分别赋予其从高到低3个优先级。数据流在进入各自优先级的缓冲队列后，按照静态优先级策略进行调度。安全关键性数据流的数据帧一般比较短小，相同优先级的数据帧采用先到先服务（FCFS）的调度策略。非安全关键性数据流的数据帧的大小不一，对不同链路的非安全关键性数据流采用差额轮询调度策略。其中，交换机中的调度器工作通常以非抢占方式和工作保持方式进行服务。

在AFDX端系统中，使用虚链路（V irtual Link，VL）机制保证数据传输的实时性，且多条虚链路可以同时存在于同一物理链路中。虚链路中设有2个重要参数：（1）一条虚链路中2个相邻数据帧之间的最小带宽分配间隔（Bandw idth Allocation Gap，BAG），其取值范围是1 ms～128 ms；（2）虚链路中允许传输帧的最大长度为Lmax。MQSA策略的AFDX调度器逻辑结构如图2所示。

图2 AFDX混合队列调度器逻辑结构

在图2中，ES为端系统；矩形模块为数据库。不同数据进入相应的优先级队列中，等待调度与发送。设混合队列调度器物理链路输出速率为C bit/s。1号优先级队列的优先级最高，2号队列次之，3号队列的优先级最低。为了突出差额轮询调度（DRR）的特点，对部分数据绘制了不同的阴影。

2.3 调度策略时延分析

2.3.1 先到先服务调度策略

2.3.2 静态优先级队列调度策略

当端系统采用静态优先级（SP）队列策略服务时，高优先级的数据流将被优先发送。若有3个优先级（P1，P2，P3）的数据流，且P1优先级最高，P2次之，P3最低，则优先级Pi聚合流的到达曲线为αi：

其中，j为相同优先级、不同数据流的编号。

端系统对优先级为i的数据流服务曲线为βi，其具体表达式如下［9］：

由定义6可得，各优先级数据流的延迟上界具体如下：

此时，高优先级数据流的延迟上界明显小于低优先级的延迟上界。在航电系统中，将紧急的数据赋予较高优先级可知，采用静态优先级队列策略克服了传统AFDX调度器中所有数据帧延迟上界相同的缺陷，满足了航电应用需求。

2.3.3 差额轮询调度策略

差额轮询（DRR）调度策略是在一个轮询周期里访问所有非空队列的调度算法［17］。数据流在一轮服务中得到的服务量与该数据流所分配的带宽成正比，从而为不同的数据流提供较为公平的调度服务。因为DRR是一种不需要全局时钟和排序过程的公平调度算法，所以被广泛应用于思科路由器和微软W indow s NT等真实环境中。

在一个有n个输入流的调度中，DRR策略为第i个输入流队列维护一个计数器θi，每一个轮询周期为第i个队列分配ωi的带宽额。DRR策略以字节为调度单位，在一次轮询操作中，如果一个输入流队列中有长度li不大于计数器θi的待发数据帧时，则发送该数据帧，同时更新计数器θi=θi-li。如果li＞θi，则更新计数器θi=θi+ωi；如果无待发数据帧，则更新计数器θi=0。更新完计数器后，开始调度下一个队列。

其中，ωi和ωj是每个轮询周期为第i个和第j个队列分配的带宽额。

因为差额轮询调度是以字节为单位，且每次增加的固定带宽额为ωi，所以服务曲线的服务速率是离散而非连续的，因此，修正延迟上界为i=。

2.3.4 混合队列调度策略

混合队列调度策略（MQSA）是将数据流经过2次调度，保障硬实时数据流的实时性，同时对非硬实时数据流公平调度的策略。在混合队列调度策略中，优先级为1和2的硬实时数据流，先按照FIFO策略排队，然后使用SP队列调度机制服务，相当于经过一个串联服务系统。优先级为3的非硬实时数据流使用的是一个DRR和SP队列调度机制串联的系统。

此时，根据网络演算理论，可以得到MQSA策略为各个优先级的虚链路VLi提供的服务曲线。

通过对比应用MQSA策略的端系统为不同优先级数据流所提供的服务曲线，发现β1，i和β2，i同SP策略下的服务曲线相同，即MQSA策略保证了较高优先级数据流的实时性。

根据虚链路VLi的BAGi和设置，可以得到对应的到达曲线。根据网络演算理论，可以得到对应数据流经过调度器的延迟上界。

3 AFDX网络模型

3.1 模型设计

为了研究混合队列调度策略（MQSA）在AFDX网络中的作用，构建了一个AFDX网络原型系统，如图3所示。为了简化问题分析，本文不考虑AFDX本身的冗余传输系统，同时规定交换机的缓冲区够大，不存在丢包情况。系统由4台全双工交换机（SW 1，SW 2，SW 3，SW 4）连接，有9个源端系统（ES1，ES2，…，ES9）和1个目的端系统（ES10），网络中的每个物理链路中同时存在若干虚链路（VL）。每台交换机均使用MQSA策略进行服务，存储转发速率设为常见的C=100 M b/s，每根物理连接线长度设为10 m，电信号在电缆中的传输速率设为2× 108m/s。AFDX网络中所有虚链路都是静态的，不存在寻找路由的情况。4台交换机均为双全工交换机，级联时会降低交换机对部分数据流的服务曲线，但通过引理4可以分析该树形拓扑结构中交换机的服务曲线。本文研究的实时性是从一个源端系统到目的端系统的延迟。

图3 AFDX网络原型系统

本文将端系统发出优先级为P1的硬实时数据流称为紧急数据流（URG），优先级为P2的硬实时数据流称为传感器数据流（SEN），优先级为P3的硬实时数据流称为尽力而为服务数据流（BST），则系统中有91条虚链路传输紧急数据流，34条虚链路传输传感器数据流，42条虚链路传输尽力而为服务数据流。各类数据流的虚链路参数设置如表1～表3所示，其BAG值都设置在128 ms之内，且大部分数据帧的长度小于1 000 Byte［14］。

表1 紧急数据流的虚链路BAG值和帧长

表2 传感器数据流的虚链路BAG值和帧长

表3 尽力而为服务数据流的虚链路BAG值和帧长

为了验证MQSA策略为尽力服务数据流调度的公平性，将ES4和ES7所发出的BAG值为2 ms的2条虚链路中传输的数据帧长度，设置为最大长度1 518 Byte，则这2条数据流将占用SW 4的12 144 000 bit/s的带宽。这在实际应用中是需要避免的，本文称其为恶意数据流。

3.2 模型分析

网络系统中存在若干物理连接线，由于电信号在物理连接线中传输的速率是固定值，则连接线相当于Cruz所定义的固定延迟元素［5］，对应的服务曲线βC=C［t-Δ］+，Δ为电信号在10 m传输线的传输时延，即Δ=10m/（2×108m/s）=5×10-8s。

应用网络演算理论分析每条虚链路中数据流的延迟上界，需要将其所经过的一系列网络元素当作一个服务器。例如ES1所发出的一条紧急数据流，通过物理链路连接SW 1，而后依次连接SW 3，SW 4，最终达到目的端系统ES10，由此可知ES1到ES10经过了一个服务曲线为βE-E=βC⊗βSW1⊗βC⊗βSW3⊗βC⊗βSW4⊗βC的服务器。到达曲线需要分级分析，先分析不同优先级的聚合数据流，再分析同一聚合流下的微数据流。由此已知网络系统是一个树形结构，参考文献［18］可得到各个微数据流的延迟上界。

3.3 模型仿真

为了验证MQSA策略对AFDX网络实时性的优化效果，运用M atlab的TrueTime1.5工具箱构建了包含AFDX端系统和交换机的网络仿真平台。同时，对FIFO和SP队列调度机制进行实验仿真，对比3种队列调度策略在AFDX网络中的实时性能。

MQSA策略的实现关键是DRR调度的实现，其算法伪代码如下：

在该算法中，VL-Num是同一优先级下采用DRR调度的虚链路数量；theta为队列计数器；L为数据帧长度；W为每次分配的带宽额，本文的W值统一设定为1 00 Byte。该算法的时间复杂度为O（VL-Num），与FIFO策略的复杂度相同。

3.4 结果比较

将仿真程序在不同调度策略下分别运行1 000 s，不同类型数据流的延迟统计结果如图4～图6所示。图中横轴为不同BAG值和不同调度策略（从左至右分别为FIFO策略、SP策略、MQSA策略）组合的类别。仿真结果表明，FIFO策略公平地调度所有数据流，但没有根据数据流的实时性需求提供区分的服务质量。SP策略保证了硬实时数据流的实时性，却不能保障尽力而为服务数据流的公平发送，也不能隔离恶意数据流的影响。MQSA策略既可以保证硬实时数据的实时性，公平地调度尽力服务数据流，也能有效地隔离恶意数据流。

图4 URG数据流在不同调度策略下的延迟统计

图5 SEN数据流在不同调度策略下的延迟统计

图6 BST数据流在不同调度策略下的延迟统计

4 结束语

本文在分析AFDX网络中数据流实时性需求的基础上，对原有的调度策略进行改进，提出应用于AFDX的混合队列调度策略（MQSA），并利用网络演算方法分析了各个数据流的延迟上界，以确保硬实时数据流满足通信要求。实验仿真结果表明，MQSA策略不仅可以满足安全关键性数据流的实时性需要，公平地调度非安全关键性数据流，也能减少恶意数据流对其他数据流延迟的影响。本文对于发展和完善AFDX网络，加快AFDX网络在我国新一代飞机上的应用，推动国内航空数据总线的发展具有重要意义。今后的研究工作主要集中在进一步完善调度算法、确定交换机缓冲区大小、可靠性验证等方面，以期提高AFDX网络的运行效率，更好地满足航空电子系统的需求。

［1］ 郭利锋，王 勇，张 磊，等.AFDX交换机的队列整形调度研究［J］.计算机工程，2011，37（24）：58-60.

［2］ Frazier H.The 802.3 Zgigabit Ethernet Standard［J］. IEEE Network，1998，12（3）：6-7.

［3］ ARINC.ARINC 664-7-2005：Aircraft Data Network，Part7-deterministic Network［S］.2005.

［4］ Charara H，Scharbarg J，Ermont J，et al.Methods for Bounding End-to-end Delays on an AFDX Network［C］//Proceedings of the 18th Euromicro Conference on Real-time Systems.Washington D.C.，USA：IEEE Press，2006：192-202.

［5］ Cruz R L.A Calculus for Network Delay.I.Network Elements in Isolation［J］.IEEE Transactions on Information Theory，1991，37（1）：114-131.

［6］ Cruz R L.A Calculus for Network Delay.2.Network Analysis［J］.IEEE Transactions on Information Theory，1991，37（1）：132-141.

［7］ Scharbarg J，Ridouard F，Fraboul C.A Probabilistic Analysis of End-to-end Delays on an AFDX Avionic Network［J］.IEEE Transactions on Industrial Informatics，2009，5（1）：38-49.

［8］ Ridouard F，Scharbarg J，Fraboul C.Probabilistic Upper Bounds for Heterogeneous Flows Using a Static Priority Queuing on an AFDX Network［C］//Proceedings of the 13th International Conference on Emerging Technologies and Factory Automation.Washington D.C.，USA：IEEE Press，2008：1220-1227.

［9］ 陈 昕，周拥军，蒋文保，等.AFDX协议性能分析及调度算法研究［J］.电子学报，2009，37（5）：1000-1005.

［10］ Dong Haiyong，Lin Yi，Zhang Yanyuan，et al.Using Static Priority Queueing to optimize the Avionics Full Duplex Sw itched Ethernet［C］//Proceedings of the 9th International Conference on Natural Computation. Washington D.C.，USA：IEEE Press，2013：23-25.

［11］ Gutiérrez J J，Palencia J C，Harbour M G.Holistic Schedulability Analysis for Multipacket Messages in AFDX Networks［J］.Real-tim e System s，2014，50（2）：230-269.

［12］ Sheikh A，Brun O，Chéram y M，et al.Optimal Design of Virtual Links in AFDX Networks［J］.Real-time System s，2013，49（3）：308-336.

［13］ Bauer H，Scharbarg J L，Fraboul C.Applying Trajectory Approach with Static Priority Queuing for Improving the Use of Available AFDX Resources［J］.Real-time Systems，2012，48（1）：101-133.

［14］ Hua Yu，Liu Xue.Scheduling Heterogeneous Flow s with Delay-aware Deduplication for Avionics Applications［J］.IEEE Transactions on Parallel and Distributed System s，2012，23（9）：1790-1802.

［15］ 樊葆华.基于网络演算的计算机网络性能分析模型研究［D］.长沙：国防科学技术大学，2009.

［16］ Mifdaoui A，Frances F，Fraboul C.Full Duplex Switched Ethernet for Next Generation“1553B”-based Applications［C］//Proceedings of the 13 th IEEE Real Time and Em bedded Technology and Applications Symposium. Washington D.C.，USA：IEEE Press，2007：45-56.

［17］ Shreedhar M，Varghese G.Efficient Fair Queuing Using Deficit Round-robin［J］.IEEE/ACM Transactions on Networking，1996，4（3）：375-385.

［18］ 张奇智，张 彬，张卫东，等.基于网络演算计算交换式工业以太网中的最大时延［J］.控制与决策，2005，20（1）：117-120.

编辑陆燕菲

Research on Optimization of AFDX Real-tim e Using Mixed Queue Scheduling Policy

LIU Jing1，2
（1.College of Mathematics and Information Science，Weinan Normal University，Weinan 714099，China；2.Research Center of Weinan Wisdom City Engineering Technology，Weinan 714099，China）

Avionics Full Duplex Switched Ethernet Network（AFDX）is an aircraft data network using the First Come First Serve（FCFS）scheduling strategy to transmit data.In this circumstance，the delay of the critical data is large while congestion is uncertain.To cope with this problem，this paper presents a Mixed Queue Scheduling Policy on AFDX（MQSA）to optimize the real-time performance.The policy integrates the advantages of FCFS，Static Priority（SP）and Deficit Round Robin（DRR）.It analyzes the delay bounds using MQSA based on network calculus，and delay bounds of critical data can meet requirement of communication.Simulation results show that this policy not only ensures real time critical data，but also ensures the fairness of scheduling non-critical data，and it can isolate malicions data flow effectively.

mixed queue scheduling policy；network calculus；Avionics Full Duplex Switched Ethernet Network（AFDX）；Virtual Link（VL）；end to end delay

刘 静.应用混合队列调度策略的AFDX实时性优化研究［J］.计算机工程，2015，41（11）：135-141.

英文引用格式：Liu Jing.Research on Optimization of AFDX Real-time Using Mixed Queue Scheduling Policy［J］. Computer Engineering，2015，41（11）：135-141.

1000-3428（2015）11-0135-07

A

TN915.03

10.3969/j.issn.1000-3428.2015.11.024

国家自然科学青年基金资助项目（61402335）；国家统计局科研计划基金资助项目（2012LY 056）；陕西省自然科学基金资助项目（2012JM 8031）；渭南师范学院科研计划基金资助项目（15YKP002）。

刘 静（1983-），女，讲师、博士研究生，主研方向：航空电子系统，智能信息处理。

2014-12-02

2015-02-01 E-m ail：liujing8318@126.com