基于虚拟时钟的AFDX调度算法研究及其延时计算

刘晓胜，李莹雪，张鹏宇，郑检，吴海涛

（哈尔滨工业大学 电气工程及自动化学院，黑龙江 哈尔滨 150001）

1 引言

AFDX 是用于航空子系统之间进行数据交换的一种通信协议，调度算法是保证AFDX 实时性的关键。常用的调度机制，如先进先出策略，静态优先级调度（AVLSP）和加权公平队列[1]，在大型AFDX网络结构下转发同一优先级的数据时可能会由于路径的不同而使各个虚拟链路上的数据延时上限差过大，导致AFDX网络负载不平衡。

分组交换网络[2]中,基于虚拟时钟算法是通过使用一个按数据分组的虚拟时钟值排序的队列来模拟公平队列中的多个队列 从而在不同的流之间实现对资源的公平分配。借助这一思想，在AFDX 网络中调度同一优先级的数据时将其等待时间从小到大排队，优先转发排在队首的数据，可以减小同优先级的数据延时差，均衡AFDX 网络负载。在计算网络延时时间上限时采用轨迹方法[3]，代替网络演算法[4]，这种方法分析数据包在它传输路径上的最坏情况，更适合计算延时上限。

本文将虚拟时钟引入AFDX 网络，针对同优先级的数据调度，进行建模与分析。利用轨迹方法对同优先级数据的传输延时上限进行计算，并与静态优先级调度方法下的延时时间比较，说明虚拟时钟调度方法可以均衡AFDX网络负载并通过仿真进行验证。

2 基于虚拟时钟的调度算法

虚拟时钟这一概念广泛应用在分组交换网络中，它支持多优先级服务，用一个根据虚拟时钟排队的队列模拟公平队列调度中的多个队列[5]。将虚拟时钟这一思想引入AFDX 网络中，实现均衡网络负载，保证数据转发的实时性。

2.1 AFDX 网络

AFDX 是具有确定性的航空电子交换式以太网，支持星型拓扑结构。AFDX 网络结构示例如图1所示。它包括六个交换机S1-S6 和六个终端系统e1-e6，交换机工作在全双工方式下，端系统的之间的每条数据链路提供了一个虚拟的点对点的单向通信通道。虚拟链路（VL）是虚拟的通信通道，每个虚拟链路建立了一个从源终端系统到多个目的终端系统的无方向的逻辑连接。图1中v6 是一个多播的虚拟链路，传输路径分别是e4-S3-S4-S5-S6-e5 和e4-S3-S6-e6，其它的则是单播的虚拟链路，例如v3，它的传输路径是e2-S1-S4-S5-S6-e6。

图1 AFDX 网络结构示例 Fig.1 An illustrative AFDX network configuration

虚拟链路的重要参数是带宽分配间隔（BAG）和最大帧长（Smax）。带宽分配间隔是指两个连续的AFDX 帧起始位之间的最小间隔，BAG的值在l～128 ms 内。每个VL 的最大可用带宽是由它的BAG 和它所规定的Smax所决定的。

2.2 AVLSP 调度算法

AFDX 网络中不同类型的数据按照其紧急程度赋予不同的优先级。在AVLSP 调度策略下数据流经过整形后，进入相关优先级的缓冲队列中，虚电路调度器工作通常以非抢占方式和工作保持方式进行优先级调度。

紧急数据具有高优先级，高优先级数据帧发送延迟小于低优先级数据帧的延迟，这克服了标准AFDX调度器中所有数据帧的延迟上界均相同的缺陷，但是忽略了数据帧在队列中的等待时间。为解决这一问题，本文提出虚拟时钟调度策略。

2.3 虚拟时钟调度算法

在分组交换网络中，对每个分组的虚拟时钟值进行排队，优先转发排在队首的数据。AFDX网络中利用虚拟时钟的调度方法与分组交换网络中虚拟时钟的调度有所不同，数据的转发是以帧为单位，采用非抢占优先级，在每个交换节点上为同一优先级的虚拟链路上的数据都建立一个虚拟时钟iVC，数据包i是虚拟链路vi上的数据，i为数据所在的虚拟链路号。

计算数据包到达某一节点前的延时，延时最小的数据包最先到达该节点，考虑该节点正处理数据，则该数据包在这一节点处等待处理的时间最长，iVC为虚拟链路iVL的数据到达节点时刻起至节点开始处理该数据为止的等待时间。将到达该节点的同一优先级的iVC从小到大排列，优先处理转发排在队首的数据。

2.4 建模分析

分析图2所示的一种AFDX 网络结构。

图2 AFDX 示例结构 Fig.2 An illustrative model

假设图2中v1-v5 都是单播的虚拟链路，具有相同的BAG（4 000 μs）和Smax（4 000 bits），其中v1 和v2 具有高优先级，v3-v5 具有低优先级。每条链路工作速率为100 Mb/s，数据在链路上的延迟时间为16 μs，每个节点处理数据时间iC为 maxS/R= 40 μs。

系统中数据包都经过静态的路径。高优先级的数据包1 和数据包2 的路径分别为e1-S-S1-S4-S5-S6-S7-e6和 e2-SS-S1-S2-S3-S6-S7-e6，低优先级的数据包3-5 的传输路径分别为e3-S1-S4-S7-e7，e4-S4-S7-e7 和 e5-S-S4-S5-S6-S7-e7。S 和SS 为两个延时环节，延时时间分别为40 μs 和80 μs。

分析数据包1 和2，到达节点S1 前的路径分别为e1-S 和 e2-SS，数据包到达节点S1 前的延时包括节点处延时和链路延时。计算数据包1 和2到达节点S1 之前的延时时间分别为40 + 80 + 16 × 2 = 152 μs 和40 + 40 + 16 × 2 = 112 μs，说明数据包2 先到达S1，由于数据包3 更早到达节点而被优先处理，采用非抢占优先级，数据包1 和2等待处理，到达S1 时分别为它们建立虚拟时钟VC1和VC2，记录从到达节点开始至开始被处理的等待时间。VC1＜VC2，则数据包1 排在队首，节点处理完数据包3 后优先处理转发数据包1。

数据包3-5 同为低优先级，数据包4 先到达节点S4 优先被处理，数据包3 和5 到达节点S4前传输路径分别为e3 - S1 和 e5-S，延时分别为40 × 2 + 16 × 2 = 112 μs 和40 + 80 + 16 × 2 = 152 μs，虚拟时钟VC5＜VC3,数据包5 优先被处理。

3 延时分析计算

利用网络演算法[6]计算端到端的延迟和抖动，延时上限为服务曲线和到达曲线的最大水平距离，但是几条链路上的数据不能同时被转发，多个服务曲线相加的情况不可能发生。轨迹方法确定AFDX 网络延时上限时考虑随机的数据流，减少不必要的悲观因素的影响。

3.1 轨迹方法

轨迹方法计算确定的延时上限，它假设数据流只经过它路径上的各节点一次，不会重复经过。

虚拟链路端到端的延时时间是通过每个节点的时间和链路上的延迟时间之和，通过每个节点的时间由3 个因素决定：数据包到达节点时刻是否有剩余数据帧被处理、数据的优先级和节点处理数据包的时间。

繁忙周期[7]是轨迹方法中的一个重要概念。繁忙周期bp（busy period）定义为一段没有空闲时间的时间间隔[t,t’），t为节点处理完在t时刻前到达数据的时刻，t’为节点处理完到达数据包的时刻。利用轨迹方法计算时认为数据在t时刻开始传输，每个节点相当于AFDX 网络中的交换机，每个数据包对应相应的虚拟链路。计算iV在每个节点处的延时时间都是在每个节点的繁忙周期内。

轨迹方法[8]定义，iV的最大端到端延时被限定在：

t是数据包产生的起始时刻，lasti是VL 访问的最后节点，是数据在最后一个节点的发送时间。文献[9]中给出定义公式，结果是经过Vi的其它数据在节点处的通过时间、Vi在节点繁忙周期内的处理时间、传输路径上的延时和Vi不经过最后一个节点时的最大数据包处理时间之和。

3.2 示例分析

根据虚拟时钟调度算法，图2中AFDX 网络在节点S1、S4 和S6 处理数据包的顺序分别为packet 3-packet 1-packet 2 ，packet 4-packet 1-packet 5-packet 3 和packet 2-packet 1-packet 5。将数据包i记为pi。的计算过程如图3所示。结果为 536 μs。根据公式（1）可计算出最坏情况下的延时上限为+C1= 536 + 40 = 576 μs。图4所示v2 上的结果为416 μs，端到端延时上限为416+40=456 μs。表1给出其它虚拟链路上的数据包在最坏情况下的端到端延时上限计算结果。

图3 计算过程图解 Fig.3 The computation of

图4 计算过程图解 Fig.4 The computation of

表1 其它链路上的延时上限计算 Tab.1 The upper bound of delay on other three VLs

3.3 调度算法比较与分析

若图2中示例AFDX 网络结构在AVLSP 调度策略下调度，优先级高的数据包被优先处理和转发。对于数据包1 和2 节点S1 处数据包处理顺序为p3-p2-p1，对数据包3-5，节点S4 和节点S7 数据包处理顺序分别为 p4-p1-p3-p5 和p4 -p3-p5。和的计算过程如图5和6所示，AVLSP 调度策略下数据包1 和2 的延时上限分别为576 + 40 = 616 μs 和376 + 40 = 416 μs。其它数据包在最坏情况下的端到端延时上限计算结果见表2。

图5 AVLSP 调度策略的Fig.5 in AVLSP scheduling

图6 AVLSP 调度策略的 Fig.6 in AVLSP scheduling

表2 其它链路上的延时上限计算 Tab.2 The upper bound of delay in FIFO scheduling

与3.2 中的计算结果比较，虚拟时钟调度下数据包1和2的延时上限差为120 μs，比在AVLSP调度下减小了40%，根据表1和表2低优先级的数据包之间最大延时上限差是448 μs，也小于AVLSP 调度下的结果。比较结果说明当路径对同优先级数据包延时上限有很大影响时本文提出的调度算法能够均衡网络负载。

4 仿真与分析

按照图2示例的AFDX 网络结构为AFDX 端系统配置五条虚拟链路，两个优先级，利用网络仿真软件OPNET 进行仿真，模型如图7所示，得出两种调度方式下各个虚拟链路端到端的延时，结果如图8所示。

图7 仿真模型 Fig.7 Simulator model

比较两种调度策略下的仿真结果，数据包1和5 在虚拟时钟调度下延时上限比AVLSP 调度下的结果小，其它数据包的延时上限比较大，虚拟时钟调度下延时上限变化比较平缓，即延时上限差小。计算虚拟时钟调度和AVLSP 调度下各个 虚拟链路的数据包最大延时上限差分别是420 μs和280 μs，虚拟时钟调度的优越性得到验证。

图8 仿真结果 Fig.8 Results of simulation

5 结论

本文针对同优先级的虚拟链路数据包的处理和转发提出了虚拟时钟调度方法，减小数据间的延时上限差，达到均衡网络负载的目的。对示例的AFDX 网络结构利用轨迹方法计算两种调度方法下各个虚拟链路数据的端到端延时上限，基 于虚拟时钟的调度方法延时差比AVLSP 调度方式减小至少15%，并通过仿真验证。

在实际情况下AFDX 的网络结构更加复杂，虚拟链路上的数据传输延时受路径影响更大，利用本文提出的调度方法对均衡网络负载、保证数据传输确定性具有重要意义。本文介绍的虚拟时钟调度方法要求在每个节点为每个数据包建立虚拟时钟，会影响在高速网络下的可扩展性。因此，对这种调度方法还需要进一步改进。

[1] 陈昕，周拥军，蒋文保，等，万剑雄.AFDX 协议性能分析及调度算法研究[J].电子学报，2009,37（5）.

[2] 高文宇，陈松乔，王建新.分组交换网络中虚拟时钟调度算法研究[J].微电子学与计算机，2004,21（7）.

[3] Henri Bauer, Jean-Luc Scharbarg, Christian Fraboul.Applying Trajectory Approach with Static Priority Queuing for Improving the Use of Available AFDX resources.Real-Time Syst, no.48.

[4] 张连明，陈志刚，黄国盛.网络演算理论及应用研究[J].计算机工程与应用，2006（27）.

[5] 石改辉，张原.优先级管理的全双工交换式以太网实时通信[J].活力与指挥控制，2009（11）.

[6] 张奇智，张彬，张卫东.基于网络演算计算交换式工业以太网中的最大时延[J].控制与决策，2005（1）.

[7] Jean-Luc Scharbarg, Frédéric Ridouard ，Christian Raboul.A Probabilistic Analysis of End-To-End Delays on an AFDX Avionic Network.IEEE Transactions on Industrial Informatics, 2009，5（1）.

[8] Henri Bauer, Jean-Luc Scharbarg, Christian Fraboul.Improving the Worst-Case Delay Analysis of an AFDX Network Using an Optimized Trajectory Approach.IEEE Transactions on Industrial Informatics, 2010，6（4）.

[9] S.Martin and P.Minet.Schedulability Analysis of Flows Scheduled with FIFO：Application to the Expedited Forwarding Class.Proc.20th Int.Parallel and Distrib.Process.Symp.Rhodes Island, Greece, Apr.2006.