时间触发总线流量调度机制及其实时性分析

赵 罡，何 锋，徐亚军，李 峭

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

时间触发总线流量调度机制及其实时性分析

赵 罡，何 锋，徐亚军，李 峭

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

根据航空航天综合电子系统中的消息传输要求，在时间触发总线网络架构及时间触发协议（TTP）的基础上，分析时间触发总线的流量类型。针对TTP总线中时间触发周期消息和事件触发非周期消息2种类型的流量，设计基于流量转换策略的消息调度机制，包括周期消息优先级调度算法及非周期消息缩微重排序调度算法。通过建立TTP总线的消息传输模型，分析并计算TTP总线中周期消息的传输时延，结合通信降级机制及网络演算方法，得到TTP总线中非周期消息的服务曲线、到达曲线和延迟上界。通过建立TTP总线仿真模型，得出实验最大时延与理论最大时延一致，从而验证基于流量转换策略的消息调度机制能够保证不同类型流量的实时传输。

时间触发协议；调度；实时性；网络演算；缩微重排序

DO I：10.3969/j.issn.1000-3428.2015.10.012

1 概述

航空航天综合电子系统对数据的通信和收发操作具有严格的时间要求。在具有分布式综合模块化的航空航天电子平台的互连技术的发展过程中［1］，引入了时间触发通信体制，基于精确全局的同步时钟引导全网活动。时间触发总线技术是该通信体制在共享介质网络中的具体实现，美国机动车工程师学会（Society of Automotive Engineers，SAE）标准化组织发布了时间触发协议（Time-triggered Protocol，TTP）标准，即TTP总线。TTP总线在发展过程中提出TTP/A和TTP/C规范，其中，TTP/A适用于汽车电子等低成本的非关键应用［2］；TTP/C面向航空航天应用设计，是具有双冗余故障容错能力的高性能实时通信总线，已应用于波音787飞机的环境控制系统、空客A 380舱压控制系统等航空航天领域，并

可以在容纳时间触发周期消息的同时，支持非周期流量，除非特别说明，本文TTP总线均为TTP/C配置。

在基于时间触发的实时通信研究领域中，SAE AS6003规范给出TTP网络拓扑结构［3］，文献［3-5］提出TTP网络的时分多路复用（Time Division Multiple Access，TDMA）调度方式，但未涉及混合关键性设计准则下的流量调度。TTP总线的实时调度在一定程度上可以借鉴交换式时间触发通信中的成果，例如：对于TTE［6］，AFDX（Avionics Full DupleXed Switched Ethernet）［7］，CAN（Controller Area Network）［8］网络实时通信的建模分析以及时分多路复用调度方式的研究［9］。文献［10-11］对AFDX网络时间关键流量的实时性进行建模分析，提出网络演算最坏情况分析方法。文献［12］提出的TTE流量转换策略对于TTP总线流量转换调度机制的设计具有启发意义。

为适应目前航空航天电子综合化电子系统中安全关键性和任务关键性的设计特点，本文在原有时间触发体制的基础上研究消息调度方法，提出一种基于流量转换策略的消息调度机制，并给出TTP总线中周期流量实时性建模方法及非周期流量的演算实时分析方法，保证不同流量类型的实时通信完整性。

2 TTP总线网络结构及调度机制

2.1 网络结构和调度方式

典型TTP网络通过双冗余总线形式连接多个节点，每个节点包含应用层主机、通信协议栈接口和通信控制器模块，如图1所示，习惯上将整体的TTP网络称为一个集群，而集群中的综合化模块在建模中可以被抽象为节点。

图1 典型TTP协议网络结构

TTP网络采用时分多路复用方式实现消息调度，通过一个全局时钟进行触发，整个系统的行为不仅在功能上是确定的，而且在时序上也是确定的。TTP系统控制信号的产生是由时间推进来触发的，不同节点的时隙序列组成一个TP=1 ms的TDMA周期，而TDMA周期组成集群周期，这样一个集群周期可以包括一二个或更多TDMA周期［13］。TTP协议的调度机制要求在系统设计时需给系统中的每个节点分配固定的周期性时隙，如图2所示。

图2 TTP总线的TDMA访问方式

在网络中所有的节点均按照离线设计的消息描述表（Message Description List，MEDL）配置表行事，使系统具有很高的时间确定性。

2.2 TTP网络流量类型

TTP规范定义的时间触发服务使得总线网络上的时间触发通信成为可能。TTP网络中同一物理网络上能够在保证时间触发的前提条件下容纳事件触发通信的流量，即：在各节点预先离线设计好任务调度表，调度表中包含一个由若干基本周期组成的矩阵周期，每个基本矩阵周期可分为2段，前一段周期中固定的时隙承载周期性时间触发（Time-Triggered，TT）流量，其中空闲时隙资源在进行严格调度策略检查的前提下允许事件触发（Event-Triggered，ET）流量接入。

在TTP总线网络中，TT流量消息在网络上以预先定义的时刻发送；ET流量的优先级低于TT消息，被用于时间确定性要求程度较弱的应用，它们可以是周期性的，也可以是带有突发度约束的非周期性流量。

传统的TTP标准也支持事件触发流量，但仅限节点内部分配，ET消息只允许在静态分配的时间窗内发送。为更灵活地利用整体剩余带宽，提出基于缩微重排序的ET消息访问控制方法。

节点依据MEDL得知TT消息占用的时间窗，避免TT消息在剩余时间段调度ET消息。ET消息发送请求时，发现总线忙碌，说明其他节点正利用该时间段进行发送，会自主等待，将待发送的ET消息缓存到自身节点，并采用缩微重排序的方式对该消息重新调度，即：规定在监听到总线从忙到闲后，以

前发送过请求的节点自主地在下一个 Tover=Tp/ Nshrink的仲裁排序时隙内重新调度排序，如图3所示，其中，Tp为周期；Nshrink为缩减系数，经验上取 Tp= 1 m s，Nshrink=128，可使大部分仲裁请求仍在TTP定时精度可分辨的能力之内。这相当于将需要重新排序的ET消息的时段等比缩小进行排序，确保空闲时段 ET消息的发送不会互相抢占。对于降级的TT-ET消息而言，为保证其优先级高于ET消息，可在Tover缩微重排序时段内将其发送时刻T′TT-ET默认为0；而规定在上一个忙时段没有发送请求的原始ET消息，必须在忙时段结束后 Tover才能发出请求，相当于T′ET=Tover。

图3 ET消息缩微重排序

2.3 TTP总线网络中的流量转换策略

目前，TT消息依赖于离线设计的MEDL，但为了适应先进航空航天系统容错和重构的要求，可以考虑在TTP总线网络中引入流量类型转变策略，提高符合延迟界限约束条件消息的可调度比例。即：在TT消息因节点之间的时间偏差产生冲突时，或某一节点负载过大，TMDA周期无法对其调度时，将TT流量转变为ET流量调度。

为避免TTP总线网络中时间触发消息因冲突碰撞而丢失，在TTP总线网络交换机中设计将TT流转换为ET流的降级通信策略，用于完成消息类型由TT向ET的单向转换。在该策略下，每个TT数据帧在进入到交换机端口时，记录到达时刻tIN，根据数据帧长估算出其离开当前端口的时刻tOUT，并将该数据帧的时间窗定为［tIN，tOUT］。下一个TT数据帧抵达时，同样记录其到达时刻t2并进行时间窗检测，如果t2∈［tIN，tOUT］，则意味着该帧可能与上一个 TT数据帧发送碰撞，并将当前帧转换为ET类型进行传播。当节点TT流量负载较大，有部分TT消息因带宽冲突无法调度时，采用降级策略将TT消息转化为ET消息，降级通信策略的流量转换调度模型如图4所示。

图4 TTP控制器中的流量转换模型

经过流量转换后，TT-ET流量具有比原始ET流量更高的优先级，但它仍被作为事件触发性质的流量进行多路复用。但是，为保证转换后的流量对于低优先级通信任务的影响可控，必须结合特定的优先级调度算法和与转换策略匹配的性能保证调度解决方案。

3 TTP总线网络中的优先级调度算法

TTP总线网络的周期依赖于时刻调度表，调度表中的每行被定义为TDMA周期，SAE AS6003标准规定调度表中每个TDMA周期为1 m s，而整个调度表所描述的整个时间段被定义为集群周期，包含多个TDMA周期［14］。在集群周期下，节点在分配的窗口内发送消息。调度算法首先分别执行各个节点主机的发送时刻调度算法，配置总线网络的发送调度时刻表，然后通过节点的TTP控制器发送和接收消息。

3.1 算法定义

算法参数定义如下：定义链路带宽为C，单位为M b/s；节点i的周期消息标记为Mi，其最小周期为Pi，单位为m s，其数据包长度为Di；将其中第q个数据帧记为 Vk，q，q∈｛1，2，…，TP/Gi｝。设第 k个TDMA周期记为Tk，Tk周期上已配置的帧长和记为Lk。根据TTP协议，在传输携带有应用数据的N帧时，同步帧的帧长 LT为2 Byte，其最大帧长可达124 bit；在传输携带控制器状态消息时，其最大帧长D=124 bit，则在一个TDMA周期内能够发送的数据帧长为Lmaxk=10-3×C×124/8，单位为Byte。

3.2 优先级调度算法

在TTP总线网络中，节点分别执行如下的优先级调度算法，对TTP网络中的周期消息进行发送时刻规划，完成TT调度表。

（1）周期消息排序。按照消息周期（Pi）顺序从小到大给所有节点的周期消息升序排序，若同周期

则按照其数据包的长度（Di）从大到小的顺序降序排序。

（2）调度初始化。按照排序顺序对所有周期消息进行规划，初始状态令计数器 i=1，已配置帧长Lk=LTC。

（3）判定周期消息Vi的调度可行性。如图5所示，Mi以Pi为最小周期，在时刻调度表TP的集群周期中需循环调度TP/Pi次；在调度表［0，TP］区间内，找到已配置帧长Lk最大的TDMA周期Tk，若Lmaxk-Lk＞Dk，则消息可调度；否则带宽有限，无法配置该周期消息，需进行通信降级，将TT消息转化为ET消息进行调度。

图5 空闲时段调度

（4）周期消息调度。若判定Mi在Pi时间范围内可调度，则配置 Mi，q的发送时刻。将 Mi，q的 TP/ Pi个调度时刻配置在第k个TDMA周期上，其起始位置为Lk+1，则发送时间ts为：

将相应的TDMA周期Tk内的已配置帧长和更新为Lk=Lk+Dr，返回继续调度Vi，q+1，直至周期消息调度完成，如图6所示。

图6 TDMA调度

（5）判定消息冲突与流量转换。在配置帧 Mi，q后，根据帧Mi，q在发送节点的发送时刻ts，节点间因时间漂移和传输时延造成的时间偏差记为ΔT，计算出Mi，q到达接收节点的可能最晚时刻tr，单位为m s。

若tr在调度表中的空闲时段，即消息在接收窗区间内到达目的节点，则消息发送可以进行，若到达时刻tr在调度表中与其他任务冲突，则将Vi消息降级为ET流量。

（6）判定调度完成。在判定消息 Vi调度成功后，若i＞n，则所有周期消息调度完成；否则i=i+1并返回步骤（3），继续调度下一周期消息。

（7）按照SAE AS6003标准，对TT转为ET的TT-ET降级消息及ET消息进行调度。

4 TT消息实时性分析

4.1 实时性分析模型

时间触发周期消息从产生到封装成包，再到发送到网络中，最后被目的节点接收的整个过程如图7所示，若是消息被分片为帧群，计算延迟只要针对最后一个数据帧。

图7 总线网络中数据传输过程

TTP网络中端到端时延主要包括技术时延、滞后时延、传输时延、传播时延和处理时延。由此得到实时性分析模型：

其中，总时延为Δ；技术时延为Δpsp；滞后时延为Δdelay；传输时延为Δtran；传播时延为Δprop；处理时延为Δprp。

4.2 时延分析

航空航天电子环境中时延特性是实时性的具体体现，对TTP总线网络的各段时延分析如下：

（1）技术时延 Δpsp

在TTP帧发送过程中，主机将发送帧的相关消息递送给TTP控制器，并将需要传输的帧数据存储入主机接口中做好发送准备，这段时延是发送时刻前的技术延迟，技术时延的长短由TTP网络系统的软硬件性能和物理环境决定。据SAE AS6003标准，TTP总线网络的技术时延通常不超过10μs（Δ′psp），本文中引入修正系数X=1.5来分析技术时

延，即：

（2）滞后时延Δdelay

在理想状况下，TTP帧的接收时刻应该和延迟接收时刻是同时的。在实时性分析中，考虑由于发送端的时钟比接收端的时钟稍快一些，最终导致TTP帧的接收时刻比延迟接收时刻要早。

如图8所示，为便于对TTP总线网络进行实时性分析，引入时间偏差表示发送端和接收端时钟的偏差，存在如下关系：

其中，Δrw为消息的接收窗口；ε为接收窗半窗长；tAT′r为延迟接收时刻。

其中，tAT′s为延迟发送时刻；tATs为起始发送时刻。

其中，Δcorr为时钟校正值。在实际情况中，滞后时延Δdelay是由TTP控制器根据其内部运行并计算所得的时钟校正Δcorr、传播时延 Δprop和接收窗半窗长 ε等参数计算而得。滞后时延Δdelay是由总线网络物理条件和节点本身的运行性能决定的。

图8 传输阶段端到端时延

（3）传输时延Δtran

传输时延为数据帧长度与发送速率之比。总线带宽是数据在信道上的最大发送速率，常称为数据在信道上的最大传输速率。

（4）传播时延 Δprop

传播时延是指数据帧在传输介质中的传输时延。传播时延为发送距离与传播速率之比，在光纤、双绞线、电缆等传输媒体中，传播速率是固定的，因此传播时延主要是与传输距离有关，而与发送数据大小无关。

（5）处理时延 Δprp

处理时延包括消息到达接收节点后协议服务处理时间（Δ′prp）和流量整形时间（Δrec）。

据SAE AS6003标准，标准TTP总线网络的处理时延不超过10μs（Δ′prp），因此本文引入修正系数X′，即：

其中，M是当前积压在发送节点i的TTP控制器中属于节点i的数据帧总数；Pi是节点i周期任务的最小周期；Ti+1是节点TTP控制器中下一帧被整形所要等待的时间，单位为μs。

由实时性分析模型得到：

据SAE AS6003标准中所提供的最大传播时延为25.6μs，取 Δprop=25.6μs；时间精度间隔 Π≤12.75μs，由于滞后时延不可大于时间精度间隔，因此取滞后时延Δdelay=12.75μs。技术时延Δpsp和处理时延 Δprp均取最大时延上界 Δpsp=15μs，Δprp= 20μs。最大时延上界为：

在航空航天电子应用环境中，根据总线网络的性能情况及网络带宽、发送距离等参数可以准确地分析TT消息的实时性，从而满足TTP总线网络的硬实时要求。

5 ET消息实时性分析

在TTP总线网络中，ET消息优先级低于TT消息，其调度等待时间无法通过4.2节的建模方法分析得出，本文采用网络演算方法来分析TTP总线网络ET消息的实时性参数。

在网络演算理论中，可变的排队延迟发生在多路复用元件（MUX）［15］。对于交换式网络，ET消息调度在交换机上缓冲排队；而对于本文研究的总线网络，采用监听和缩微重排序的方法进行仲裁，ET消息分别缓存在各节点［16］。然而，由于享有精确的全局定时调度，总体的积压等于各节点缓存量之和，

仍然可以采用一个 MUX元件进行建模。这样文献［12］提出的流量转换策略下的优先级排队分析方法依然有效，只是需要在缩微重排序的开销条件下进行修正。

TTE网络的流量转换策略都是基于时间触发的调度方式，且是基于周期消息到非周期消息的降级通信策略。因此，根据文献［12］中PTCTS的相关定理，结合本文TTP总线网络的调度算法，可对降级转流消息队列QTT-＞ET与ET消息队列QET作出分析。

5.1 算法假定

在［ts，t］时间周期内，周期时长T=t-ts。对于ET消息队列QET与降级转流消息队列QTT-＞ET而言，不妨规定QET中数据帧长为集合｛LET｝，QTT-＞ET中消息数目为N，数据帧长为集合｛LTT-ET｝。

5.2 服务曲线

队列QET，QTT-＞ET服务曲线非负，周期时长与仲裁时间之和为ΔT=T+TP/Nshrink，根据定义，服务曲线为：

2个消息队列提供的服务曲线分别为：

5.3 到达曲线

假定在TDMA集群周期中的ET消息均能在当前时间段内发送完毕，根据网络演算理论中到达曲线的基本定义，到达曲线可以表示为：

根据ET类型数据流的特性，原始ET数据流的数据帧离开节点时的到达曲线为：

由TT类型转换而来的ET流量，在转换后添加了转流标识，并且有相应的任务周期，因此此类型数据帧的到达曲线为：

到达曲线与服务曲线示意图如图9所示。

图9 到达曲线与服务曲线示意图

5.4 延迟上界

根据调度算法及网络演算相关概念，服务曲线和到达曲线的最大偏差值即为流量延迟上界，可以计算2种流量延迟上界：

TT类型转换而来的ET流量，延迟上界是关于N的减函数；未经过转换的ET流量，其延迟上界是关于N的增函数。根据2种流量的聚集情况以及航空航天电子环境的实际情况，设置N的门限值，满足消息的实时性要求。

6 仿真实验与结果分析

TTP实时性仿真实验采用典型的四节点总线网络拓扑，如图10所示，共有4个节点构成网络主干，TDMA周期为1 000μs，集群周期由4个TDMA周期组成。节点中节点1～节点3是发送节点，节点4为接收节点，链路带宽配置为C M b/s。

图10 仿真网络拓扑

假定节点1发送消息M1，周期为1 000μs、长度为40 Byte，节点2发送消息M2，周期为2 000μs、长度为10 Byte，节点3发送消息M3，周期为4 000μs、

长度为20 Byte。仿真过程采用TTTech-TTP仿真平台进行，根据TTP协议调度机制及所设计的调度算法，可以实现调度时间分配，以及调度可视化显示。TTP协议网络采用N帧或I帧来传输数据消息，据TTP帧类型及结构可知，在传输携带有应用数据的N帧或I帧时，其最大帧长可达4+12×8+24= 124 bit［17-18］。根据式（12），在发送数据长度及链路带宽确定的情况下，可计算出理论延迟上界，将计算结果与仿真结果进行对比，结果如表1所示。根据上述实验及分析结果，TTP网络中的TT消息及ET消息的实验时延均低于理论时延上界，说明所设计的调度算法及所采用的降级通信策略可以有效保障TTP总线网络的稳定性，满足航空航天电子环境对网络实时性的要求。

表1 最大时延的理论数据与实验数据对比

7 结束语

本文在TTP标准原有调度规则的基础上，结合同时包含TT和ET消息流量的系统设计和分析方法，提出一种基于缩微重排序的降级通信流量转换策略，并据此设计任务优先级调度算法。算法同时支持优先级等级从高到低的TT流量、转换后的TTET流量和原ET流量，并利用使得TT消息通过仲裁机制向ET消息进行降级转化处理的调度机制，解决了跨节点的动态ET消息访问问题，对该TTP总线网络调度算法进行建模，得到流量转换方案下非周期消息计算服务曲线、到达曲线和延迟上界。分析和实验结果验证了本文建模和分析方法的有效性，并且有助于TTP总线网络在航空航天电子平台上的应用推广。本文调度机制和建模分析策略不仅为均衡TTP网络实时性和运行开销提供了参数选择的理论依据，也为进一步分析TTP总线在航空电子环境中的消息动态访问机制和流量实时性奠定了理论基础。

［1］ 熊华钢.机载总线网络及其发展［J］.航空学报，2006，27（6）：1135-1144.

［2］ Kopetz H.A Comparison of TTP/C and FlexRay［Z］. 2001.

［3］ SAE International’s AS-2 Em bedded Computing System s Committee.SAE AS6003-2011 TTP Communication Protocol［S］.2011.

［4］ Pfeifer H.Formal Verification of the TTP Group Membership Algorithm［M］.Berlin，Germany：Springer，2000.

［5］ Kopetz H，Bauer G.The Tim e-triggered Architecture［J］.Proceedings of the IEEE，2003，91（1）：112-126.

［6］ Ming Dexiang，Wang Yueke，Zhong Xiaopeng.Open Architecture and Technology of Test Control Network［C］// Proceedings of the 3rd International Symposium on Instrumentation Science and Technology.Washington D.C.，USA：IEEE Press，2004：18-22.

［7］ Xia Jiqiang.Real-time and Reliability Analysis of Timetriggered CAN-bus［J］.Chinese Journal of Aeronautics，2013，26（1）：171-178.

［8］ Liu Wanchun.Research on Time-triggerd-ethernet Synchronization and Scheduling Mechanism［J］.Aeronautical Computing Technique，2011，41（4）：122-127.

［9］ Wandeler E，Thiele L.Optimal TDMA Time Slot and Cycle Length Allocation for Hard Real-time System s［C］// Proceedings of ASP-DAC’06.Washington D.C.，USA：IEEE Press，2006：479-484.

［10］ 张勇涛，黄 臻，熊华钢.保证速率的AFDX交换机实时调度算法［J］.北京航空航天大学学报，2010，36（12）：1412-1416.

［11］ 刘 成，王 彤，李 铮，等.时间触发AFDX网络的设计和实时性分析［J］.北京航空航天大学学报，2013，39（6）：728-733.

［12］ 易 娟，熊华钢，何 锋，等.TTE网络流量转换策略及其延时性能保障调度算法研究［J］.航空学报，2014，（4）：1071-1078.

［13］ 樊葆华，窦 强，张鹤颖.网络演算的矩阵解释［J］.计算机学报，2009，32（12）：2411-2419.

［14］ 张 一，胡媛媛，陈冬梅.基于时间触发架构的系统通信设计应用研究［J］.航空电子技术，2011，42（3）：145-152.

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

［16］ 王 婧，张 欣.汽车网络通信协议TTP/C和FlexRay的研究分析［J］.北京汽车，2006，（6）：40-44.

［17］ 汪健甄，许宗泽.航空电子高速数据总线性能分析及其实时性仿真［J］.南京航空航天大学学报，2008，40（3）：345-349.

［18］ 赵 妮，严小军.通信网仿真置信度评估的方法研究［J］.计算机工程，2006，32（24）：110-111.

编辑 陆燕菲

Flow Scheduling Mechanism of Time-triggered Bus and Its Real-time Analysis

ZHAO Gang，HE Feng，XU Yajun，LI Qiao
（School of Electronic and Information Engineering，Beihang University，Beijing 100191，China）

According to the requirement of information transmission in aviation and aerospace integrated electronic system，flow type is analyzed based on the architecture of time-triggered bus and Time-triggered Protocol（TTP）.An information scheduling mechanism based on flow conversion strategy is proposed，which includes periodic Time-triggered（TT）message scheduling algorithm and non-periodic Event-triggered（ET）message micro-reordering scheduling algorithm.The transmission delay for TT message in scheduling algorithm is analyzed by modeling message transmission in TTP bus.Moreover，combining with communication degrading strategy and network calculus method，the server curve，arrival curve and delay bound for non-periodic ET message are obtained.A TTP simulation case is constructed.The results show the maximal delay obtained in experiment is consistent with the worst-case delay in theory analysis，and the flow conversion strategy proposed in this paper can realize a real-time transmission for different flow type.

Time-triggered Protocol（TTP）；scheduling；real-time；network calculus；micro-reordering

赵 罡，何 锋，徐亚军，等.时间触发总线流量调度机制及其实时性分析［J］.计算机工程，2015，41（10）：59-65.

英文引用格式：Zhao Gang，He Feng，Xu Yajun，et al.Flow Scheduling Mechanism of Time-triggered Bus and Its Realtime Analysis［J］.Computer Engineering，2015，41（10）：59-65.

1000-3428（2015）10-0059-07

A

TN914

国家自然科学基金资助项目（61301086）；教育部基础科研业务费基金资助项目（YWF-14-DZXY-018，YWF-14-DZXY-023）。

赵 罡（1990-），男，硕士研究生，主研方向：航空电子系统，数据通信；何 锋，讲师、博士；徐亚军，副研究员、博士；李 峭，讲师、博士。

2014-10-11

2014-11-07E-m ail：zhaogang@gmail.com