时间触发以太网(Time-Triggered Ethernet, TTE)利用时钟同步保证全网在统一时钟下进行时间触发服务：通过离线调度表的规定时刻发送时间触发(Time-Triggered, TT)消息，保证TT消息传输的实时性[1-2]。文献[3-4]提出了“priori schedule porosity”调度算法，指出在TT消息发送间隔，进行速率约束(Rate Constraint，RC)消息的调度发送。文献[5]在文献[3-4]基础上进一步提出了“posteriori schedule porosity”调度算法。然而，这些算法均是针对TT消息的静态调度研究，并未对RC消息的动态在线调度进行分析。对于RC消息调度算法，应从实时性、公平性和复杂度3个方面综合考虑[5-6]。现有调度算法中，先到先得(First Input First Output, FIFO)是目前应用最广泛的算法，其调度简单，易于实现，但不能满足不同服务要求下的分组消息调度要求[7-8]；优先级(Priority Queue, PQ)调度算法考虑到了分组消息的情况[9]，然而，高优先级的消息过多到来会严重影响低优先级消息的传输，公平性难以保证；加权公平队列(Weighted Fair Queuing, WFQ)[10]、最坏情况下加权公平队列(Worst-case Fair Weighted Fair Queuing，WF2Q)[11]虽具有较好的时延性和公平性，但其复杂度较大，影响RC消息调度的实时性，不适合其在线调度；加权轮询(Weighted Round Robin, WRR)调度算法[12-14]兼具公平性和时间复杂度低的特点。然而，上述调度算法均未考虑TT消息对RC消息的影响，因此不适用于TTE。
针对TTE的特点，本文提出了基于最优时间片的改进加权轮询(Modified Weighted Round Robin, MWRR)调度算法。通过可满足性模理论(Satisfiability Modulo Theories, SMT)[5]计算出最利于RC消息传输的TT消息离线调度表，从而得到RC消息传输的最优时间片，在时间片内实现不同类型RC消息的调度，仿真证明了本文算法在复杂性、公平性和时延性等多个方面均优于常规调度算法。
1 时间触发以太网的消息TTE在单一网络中可以支持3种不同类型的数据通信来满足不同实时和安全等级的应用需要：TT消息、RC消息和传统以太网的尽力发送(Best Effort，BE)消息[15]。消息的类型可通过消息的目的地址相区别。
在3类消息中，TT消息采用全局时钟同步，确保通信的实时性。TT消息的调度遵循离线调度表的规定，以确保消息在预先定义的时刻进行通信，适用于延迟抖动小、延迟确定的通信场合。同时，TT消息优先级最高，即较其他消息可优先获得资源调度，在确认时间槽中没有TT消息通信的情况下，才将空闲时间片分配给其他类型的数据流。
RC消息优先级低于TT消息，用于实现确定性和实时性比TT网络相对较弱的应用。在同一时间点，不同的控制器可以发送多个RC消息到同一接收端，因此，会导致不同的RC消息在交换机中排队的现象，造成传输通信的抖动增加。
相对于TT消息和RC消息，BE消息利用网络剩余的带宽进行数据传输，优先级最低。在网络中没有TT消息和RC消息的情况下，网络所有带宽都可以分配给BE消息使用。BE消息具有传输灵活的优势，但是存在消息延迟的大小不确定的问题。
图 1为TTE拓扑实例，包含3个交换机和7个端系统，由于本文重点研究TT消息和RC消息的调度算法，故每条物理链路中只包含TT消息和RC消息的数据链路。时间触发网络物理拓扑可以定义为顶点为V、边为E的无向图G(V, E)。其中，无向图的顶点表示网络中的端系统或者交换机。无向图的边表示连接网络端系统或交换机的物理链路，而每条物理链路中可有多条双向的数据链路。
|
| 图 1 TTE拓扑实例 Fig. 1 A TTE topological example |
若vk和vr为任意2个顶点，则[vk, vr]表示为从顶点vk到顶点vr的物理链路，图 1中从端系统顶点ES1到交换机顶点SW1的物理链路为[ES1, SW1]，表示为E1。网络中任意一时间触发消息表示为TTi。其中，TTi包含了TTi的消息周期TTi.period、消息长度TTi.length以及消息调度时刻TTi.offset。
|
(1) |
RCj网络中任意一事件触发消息。其中，RCj包含了RCj的最小消息间隔RCj.BAG和消息长度RCj.length。
|
(2) |
MWRR调度算法主要分为2个步骤：
1) RC消息传输最优时间片的计算。
2) 在最优时间片下，对不同类型RC消息进行调度。
2.1 最优时间片的计算由于TT消息的优先级高于RC消息，因此，RC消息的传输不可避免地受到TT消息传输的约束，这种约束主要体现在TT消息离线调度表对传输RC消息时间片的影响，此时间片为TT消息调度后的时间孔隙。而在TTE中，TT消息调度为非确定性多项式完全问题(Non-deterministic Polynomial complete problem，NP-complete)。满足TT消息传输约束的SMT[16]算法可以生成TT消息离线调度表，从而得到时间片。
SMT算法下TT消息传输约束条件如下。
1) 无冲突约束
在物理链路[vk, vr]上，任意2个TT消息TTi[vk, vr]和TTm[vk, vr]传输应满足无冲突约束条件，即为避免冲突，一个消息的发送时刻应迟于前一个消息的发送完成时刻。
|
(3) |
2) 路径依赖约束
路径依赖约束规定了任意TT消息TTi单跳延迟的限制。假定[vr, vy]为[vk, vr]的下一条路径，hopdelaymax为任意消息单跳延迟的规定最大值，hopdelaymin为其规定的最小值，则
|
(4) |
3) 同时传递约束
同时传递约束规定了在多播传输的情况下，同一TT消息TTi从同一发送端vk向不同接收端vr和vy发送时，发送时刻应相同。
|
(5) |
4) 端到端传输约束
在实际应用中，为保证消息传输的实时性，限定了消息的端到端最大传输延迟max(latency)。假定[vk, vr]为消息TTi的第1条物理链路，[vx, vy]为消息TTi的最后1条物理链路，TTi[vk, vr].arrive表示为TTi的到达时刻，则
|
(6) |
5) 协议控制帧(Protocol Control Frame, PCF)约束
由于TTE需要通过节点间传递PCF实现网络时钟同步，以保证消息按照全局统一时间进行调度传输，因此PCF帧的传输优先级高于TT消息，即TT消息应为PCF传输预留资源。由于PCF帧位于同步周期开始阶段，对后续的消息调度无影响，因此，为了简化说明问题，本文忽略PCF传输所需资源。
6) 应用层约束
在应用层，鉴于不同TT消息，如TTi[vk, vr]和TTm[vk, vr]具有不同的任务要求，不同类型TT消息传输间应设置最小传输间隔δ。
|
(7) |
7) 时间片数量最小约束
由于高优先级TT消息的影响，RC消息只能在离散时间片内调度。若TT消息分布较分散，则供RC消息传输的时间片较分散，不利于RC消息资源的合理利用。为避免这一现象，需满足时间片数量最小约束。在实际应用中，TT消息周期一般为2n ms(1≤n)，因此，保证时间片数量最小，应保证不同TT消息间的背靠背传输。
若TT(1)i为消息TTi第1个周期的数据帧，TT(a)m为消息TTm任意周期的数据帧。
|
(8) |
在航空领域中，RC消息可分为不同类型：航空控制类消息、数据通信类消息和多媒体消息。不同类型消息实时性要求不同，因此权重值不同。
航空控制类消息多用于系统中线控制动或线控转向，对实时性要求最高，故较其他类型RC消息具有最大权重值。数据通信类消息实时性要求略低于航空控制类消息，用于数据可靠性传输。相比之下，多媒体消息实时性要求最低，权重分配最小，其作用为系统传递传感器的视频、音频信息。
为了保证实时性要求高的类型消息优先调度和避免实时性要求较低的消息长期得不到服务，带有权重值的轮询调度尤为必要。
任意类RC消息权重值为wn，每类消息均设计数器保证消息调度的公平性。若第n类消息计数器值为θn，则差额计数器值Dθn为
|
(9) |
此调度算法采用非抢占调度机制，且遵循以下规则。
1) 规则1:在每个消息调度前需判断时间片剩余时间，若剩余时间小于消息最大帧长时，优先调度使资源利用率最大的消息。
2) 规则2:每次调度消息前比较各类消息差额计数器值Dθn的大小，优先调度差额计数器值较大的RC消息。
如图 2所示，假设3类RC消息的权重分别为3, 2, 1，A1A2A3为航空控制类消息；B1B2为数据通信类消息；C1为多媒体消息。传统WRR调度算法调度顺序为A1A2A3B1B2C1，为防止权重值较低的消息延迟过大，在保证带宽按权重值分配的前提下，按规则2调度顺序为A1B1C1A2B2A3。在发送C1后，A2的传输时间大于时间片S剩余时间，在已到达消息B2A3中按照规则1选取发送资源利用率较大的消息B2，最终得到图 2中的调度结果A1B1C1B2A2A3。此算法使得全网消息调度比例符合权重值的要求，因此，更有效地保证了消息传输的公平性，另外，按照时间片剩余资源合理调整调度顺序，又在一定程度上提高了资源利用率。
|
| 图 2 RC消息调度 Fig. 2 RC message scheduling policy |
本文算法步骤1) 中，RC消息传输最优时间片通过TT消息离线调度表计算获得，而TT消息为离线调度，由于离线调度不会影响到消息调度的实时性，故无需分析此步骤中SMT算法的复杂度。
然而，步骤2) 中的不同类型RC消息为动态调度，因此，分析算法复杂度尤为重要。本文算法对于RC消息在线调度在传统WRR调度算法基础上进行改进，复杂度与其相同，均为O(1)，且实际应用中RC消息排队队列较短，其计算时间可以忽略。
3.2 最坏延迟分析运用确定型网络演算方法分析调度算法的最坏时延[17-19]。其中，极大代数下的消息到达曲线α(t)与服务曲线β(t)的卷积和反卷积分别表示为
|
(10) |
|
(11) |
经过交换机后新输出曲线为到达曲线α(t)与服务曲线β(t)的反卷积，表示为
|
(12) |
若交换机1和交换机2为级联交换机，则经过级联交换机后新服务曲线β′(t)为交换机1服务曲线β1(t)与交换机2服务曲线β2(t)的卷积。
|
(13) |
消息最坏的端到端延时为其到达曲线与服务曲线的水平距离。
定义网络传输带宽为C；消息TTi的最大帧长为TTi_max length，数量为p；若任意消息RCj为航空控制类消息，则数据包间隔为BAGj1，最大帧长为RCj1_max length，数量为q1，权重值为w1；若为数据通信类消息，则数据包间隔为BAGj2，最大帧长为RCj2_max length，数量为q2，权重值为w2；若为多媒体消息，则数据包间隔为BAGj3，最大帧长为RCj3_max length，数量为q3，权重值为w3。
由于消息到达符合流量整形的约束，TT消息到达速率为TTi_max length/TTi.period。因此，TT消息的到达曲线为
|
(14) |
同理，航空控制类、数据通信类和多媒体RC消息的到达曲线分别为
|
(15) |
|
(16) |
|
(17) |
TT消息优先级高于RC消息，高优先级的数据包优先发送，其等待时间为最大数据包的时间，因此TT消息的服务曲线为
|
(18) |
低优先级的RC消息的服务曲线为
|
(19) |
|
(20) |
|
(21) |
式中：C*为TT消息影响下RC消息的传输带宽；TRC为其消息等待时间。
航空控制类RC消息的服务曲线为
|
(22) |
根据不同分类的RC消息权重不同，带宽公平分配，航空控制类消息占用3类RC消息总带宽的比例遵循权重约束，因此，可推出其带宽C1为
|
(23) |
其中，航空控制类消息的等待服务时间为优先调度的TT消息、其他2类RC消息传输时间与自身消息最大帧长所需传输时间之和，可得出
|
(24) |
可进一步化简为
|
(25) |
|
(26) |
同理，可推出数据通信类RC消息的服务曲线中带宽与等待服务时间为
|
(27) |
|
(28) |
多媒体RC消息的服务曲线中带宽与等待服务时间为
|
(29) |
|
(30) |
本文利用Visual C++的编译环境，进行网络仿真平台的搭建。网络拓扑结构和消息分布如图 1所示，且物理链路带宽C为100 Mbit/s，由于消息帧长范围为64~1 518 bytes，本文中设定TT消息帧长为1 200 bytes。
|
(31) |
TT消息的周期设置如表 1所示，例如消息TT1的周期为2 000 μs，即
| TT消息 | 周期/μs |
| TT1~TT2 | 2 000 |
| TT3~TT6 | 4 000 |
| TT7~TT14 | 8 000 |
| TT15~TT30 | 16 000 |
| TT31~TT62 | 32 000 |
| TT63~TT126 | 64 000 |
|
(32) |
根据3.1节中的SMT算法以及消息的约束条件计算出TT消息离线调度表。网络中所有TT消息周期的最小公倍周期定义为一个集成周期。图 3显示了一个集成周期内的各个TT消息调度时刻TTi.offset。
|
| 图 3 TT消息离线调度表 Fig. 3 TT message offline schedule table |
在TT消息发送间隔时间片内调度RC消息。RC消息长度可设置为在64 ~1 518 bytes区间服从均匀分布，即RCj.length~U(64, 1 518)。消息间最小间隔BAG如表 2所示，例如RC1为航空控制类消息，RC1.BAG为2 000 μs。网络中共设置了32条RC消息，其中，航空控制类、数据通信类和多媒体消息的权重值分别设为3, 2, 1。
| BAG/μs | 消息类型 | ||
| 航空控制类 | 数据通信类 | 多媒体 | |
| 2 000 | RC1~RC2 | ||
| 4 000 | RC3 | RC4~RC6 | |
| 8 000 | RC7~RC9 | RC10~RC11 | RC12~RC14 |
| 16 000 | RC15~RC17 | RC18~RC20 | RC21~RC22 |
| 32 000 | RC23 | RC24~RC25 | RC26~RC28 |
| 64 000 | RC29~RC30 | RC31~RC32 | |
为使算法对比更加明显，所有算法中TT消息的发送均采用图 3中的离线调度表。通过与FIFO、PQ、WRR算法仿真对比，验证本文算法的性能。
经过500次蒙特卡罗试验，所得RC消息的端到端延迟概率分布如图 4所示。对于航空控制类消息，PQ算法的端到端延迟优于其他算法，然而PQ算法下数据通信类消息和多媒体消息的端到端延迟均大于本文MWRR算法，这说明此算法公平性最差。这是因为优先调度高优先级消息的策略使得低优先级消息一直处于等待状态中，得不到服务。
|
| 图 4 端到端延迟概率分布 Fig. 4 End to end delay probability distribution |
FIFO算法调度不考虑消息类型的特点，只是按照先到达先服务的原则，且未考虑资源利用率的问题，其3类消息的端到端延迟虽差距不大，但总体较差。
WRR算法和MWRR算法中，通过权重分配考虑了消息优先级，满足了实际应用中不同消息实时性不一致要求。当到达消息数量不符合权重比例情况下，由于WRR算法采用不等待策略，会导致网络传输中3类消息的调度比例与权重比例不一致的情况。此外，WRR算法也未根据合理利用资源的需要，相应调整消息的发送次序。MWRR算法在WRR算法基础上增加了计数器来保证消息类型的传输比例，不仅弥补了WRR算法这一缺陷，而且提高了资源利用率。
表 3为4种算法下3类消息的平均端到端延迟，表 4为根据第3节的最坏延迟分析得出网络演算方法分析下的最坏端到端延迟。由表 3和表 4可看出，对于航空控制类消息，FIFO算法未体现其优先级，因此端到端延迟最大；PQ算法的航空控制类消息以牺牲其他类型消息的实时性为条件，得到了较小的端到端延迟最小，多媒体消息的平均端到端延迟达到8 152.6 μs，最坏端到端延迟达73 880 μs，均为最大。比较而言，MWRR算法的3类RC消息均有较小的端到端延迟。
| 算法 | 平均端到端延迟/μs | ||
| 航空控制类消息 | 数据通信类消息 | 多媒体消息 | |
| FIFO | 2 472.8 | 2 469.1 | 2 478.2 |
| PQ | 481.4 | 1 142.1 | 8 152.6 |
| WRR | 1 998.3 | 2 657.8 | 3 496.2 |
| MWRR | 939.5 | 965.7 | 1 057.3 |
| 算法 | 最坏端到端延迟/μs | ||
| 航空控制类消息 | 数据通信类消息 | 多媒体消息 | |
| FIFO | 17 713 | 17 238 | 17 428 |
| PQ | 2 627 | 9 284 | 73 880 |
| WRR | 14 391 | 13 590 | 17 340 |
| MWRR | 7 797 | 8 097 | 9 553 |
5 结论
MWRR算法在算法复杂度、公平性和实时性方面优于其他算法，总结如下：
1) MWRR算法相对于WFQ算法和WF2Q算法复杂度较低，仅为O(1)，使得其在实际应用中节省了计算和存储开销，更加适合航空高速网络设备。
2) 具有较好的公平性。在仿真实验中，航空控制类、数据通信类和多媒体RC消息平均端到端延迟和最坏端到端延迟均相当，体现了算法的公平性。
3) 端到端延迟较小。MWRR算法的数据通信和多媒体RC消息的延迟均低于其他3类算法，航空控制类消息虽延迟略高于PQ算法，但就3类消息总体而言，MWRR算法的实时性最好。
| [1] | SAE International Group.Time-triggered Ethernet:AS6802[S].Washington, D.C.:SAE International, 2011. |
| [2] | HU M L, LUO J. Holistic scheduling of real-time applications in time-triggered in vehicle networks[J]. IEEE Transactions on Industrial Informatics, 2014, 10 (3): 1817–1828. DOI:10.1109/TII.2014.2327389 |
| [3] | STEINER W.An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//2010 IEEE 31st Real-Time Systems Symposium.Piscataway, NJ:IEEE Press, 2010:375-384. |
| [4] | CRACIUNAS S S, OLIVE R S.SMT-based task and network-level static schedule generation for time-triggered networked systems[C]//International Conference on Real-Time Networks and Systems.New York:Association for Computing Machinery, 2014:45-54. |
| [5] | STEINER W.Synthesis of static communication schedules for mixed-criticality systems[C]//International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops.Piscataway, NJ:IEEE Press, 2011:11-18. |
| [6] | FREIER M, CHEN J J.Time-triggered communication scheduling analysis for real-time multicore systems[C]//IEEE International Symposium on Industrial Embedded Systems.Piscataway, NJ:IEEE Press, 2015:1-9. |
| [7] | GANDEVA B S, WISETO P A.Performance analysis of packet scheduling with QoS in IEEE 802.16e networks[C]//International Conference on Telecommunication Systems, Services and Applications.Piscataway, NJ:IEEE Press, 2012:4-8. |
| [8] | ELES P, DOBOLI A. Scheduling with bus access optimization for distributed embedded systems[J]. IEEE Transactions on Very Large Scale Integration Systems, 2000, 8 (5): 472–491. DOI:10.1109/92.894152 |
| [9] | BOYER M, FRABOUL C.Tightening end to end delay upper bound for AFDX network calculus with rate latency FIFO servers using network calculus[C]//IEEE International Workshop on Factory Communication Systems.Piscataway, NJ:IEEE Press, 2008:11-20. |
| [10] | HE Z Z, MEN C G. Schedulability of fault tolerant real time system based on local optimum checkpoint under priority mixed strategy[J]. Chinese Journal of Electronics, 2015, 24 (2): 236–244. DOI:10.1049/cje.2015.04.003 |
| [11] | ANIRUDHA S, MANJUNATH D. Revisiting WFQ:Minimum packet lengths tighten delay and fairness bounds[J]. IEEE Communications Letters, 2007, 11 (4): 366–368. DOI:10.1109/LCOM.2007.348303 |
| [12] | ZHOU J, GUO Y F.Guaranteeing maximum reliability and minimum delay QoS routing based on WF2Q[C]//International Conference on Computational Intelligence and Security.Piscataway, NJ:IEEE Press, 2009:11-14. |
| [13] | XIN Y, DUAN Z. Fair round-robin:A low complexity packet scheduler with proportional and worst-case fairness[J]. IEEE Transactions on Computers, 2009, 58 (3): 365–379. DOI:10.1109/TC.2008.176 |
| [14] | VALENTE P.Providing near-optimal fair-queueing guarantees at round-robin amortized cost[C]//The 22nd International Conference on Computer Communications and Networks (ICCCN).Piscataway, NJ:IEEE Press, 2013:1-7. |
| [15] | FUCHSEN R. A new technology for the Scarlett program[J]. IEEE Transactions on Aerospace and Electronic Systems, 2010, 25 (10): 10–16. DOI:10.1109/MAES.2010.5631720 |
| [16] |
徐晓飞, 曹晨, 郭骏, 等. TT-RMS:时间触发网络通信表生成算法[J].
北京航空航天大学学报, 2015, 41 (8): 1403–1408.
XU X F, CAO C, GUO J, et al. TT-RMS:Communication table generation algorithm of time-triggered network[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41 (8): 1403–1408. (in Chinese) |
| [17] | ZHAO L X, XIONG H G. Improving worst-case latency analysis for rate-constrained traffics in the time-triggered Ethernet network[J]. IEEE Communications Letters, 2014, 18 (11): 1927–1930. DOI:10.1109/LCOMM.2014.2358233 |
| [18] | CRUZ R L. A calculus for network delay.Part Ⅰ:Network elements in isolation[J]. IEEE Transactions on Information Theory, 1991, 37 (1): 114–131. DOI:10.1109/18.61109 |
| [19] | BAUER H. Improving worst-case latency analysis for rate-constrained traffics in the time-triggered Ethernet network using an optimized trajectory approach[J]. IEEE Transactions on Industrial Informatics, 2010, 6 (4): 521–533. DOI:10.1109/TII.2010.2055877 |