基于TTE的改进加权轮询调度算法

张英静; 何锋; 卢广山; 熊华钢

doi:10.13700/j.bh.1001-5965.2016.0590

基于TTE的改进加权轮询调度算法

doi: 10.13700/j.bh.1001-5965.2016.0590

北京航空航天大学电子信息工程学院, 北京 100083

基金项目:

国家自然科学基金 61301086

航空科学基金 20131951027

详细信息

作者简介:
张英静女, 博士研究生。主要研究方向:实时通信系统、分布式网络

何锋男, 博士, 讲师。主要研究方向:航空电子网络、分布式实时系统

通讯作者:
何锋, E-mail:robinleo@buaa.edu.cn

中图分类号: V247.5;TN914
计量
- 文章访问数: 1038
- HTML全文浏览量: 150
- PDF下载量: 482
- 被引次数: 0
出版历程
- 收稿日期: 2016-07-13
- 录用日期: 2016-09-02
- 网络出版日期: 2017-08-20

A modified weighted round robin scheduling algorithm in TTE

School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China

Funds:

National Natural Science Foundation of China 61301086

Aeronautical Science Foundation of China 20131951027

More Information

Corresponding author: HE Feng, E-mail:robinleo@buaa.edu.cn

摘要

摘要:
在时间触发以太网（TTE）中，TT消息优先级最高，RC消息只能在TT消息调度的离散时间片内传输，因此，TT消息离线调度表的设计会对RC消息调度产生一定影响。针对这一问题，提出了基于最优时间片的改进加权轮询（MWRR）调度算法。首先，通过TT消息约束条件限制获得TT消息离线调度表，进而得到保证RC消息较大资源利用率的时间片信息；其次，在离散时间片对不同类型RC消息进行调度，并运用网络演算方法对其最坏端到端延迟进行分析；最后，通过实验仿真证实了本文算法不仅具有较低的复杂度和较好的公平性，保证了实际应用中算法的可行性，而且在时延性方面均优于先到先得（FIFO）、优先级（PQ）和加权轮询（WRR）调度算法。
- 时间触发以太网(TTE) /
- 调度算法 /
- 速率约束 /
- 加权轮询(WRR) /
- 网络演算
Abstract:
TT messages that have the top priority among three kinds of traffics affect RC message communication inevitably in time-triggered Ethernet (TTE). Therefore, RC messages have to be scheduled among discrete time slices caused by TT message offline schedule table. A modified weighted round robin (MWRR) scheduling method based on optimal time slice was proposed in this paper. Firstly, TT message offline schedule table was calculated satisfying the requirements of TT message constraints in order to get optimal time resources for RC flow transmission; secondly, different kinds of RC flows were scheduled in several time slices and the worst end to end delays were analyzed by network calculus in TTE; finally, experiments show that MWRR algorithm in the paper not only has low complexity, good fairness and feasibility in practical application, but also obtains better real-time performance than first input first output (FIFO), priority queue (PQ) and weighted round robin (WRR) scheduling algorithm.
- time-triggered Ethernet (TTE) /
- scheduling algorithm /
- rate-constrained /
- weighted round robin (WRR) /
- network calculus

HTML全文

图 1 TTE拓扑实例

Figure 1. A TTE topological example

下载: 全尺寸图片幻灯片

图 2 RC消息调度

Figure 2. RC message scheduling policy

下载: 全尺寸图片幻灯片

图 3 TT消息离线调度表

Figure 3. TT message offline schedule table

下载: 全尺寸图片幻灯片

图 4 端到端延迟概率分布

Figure 4. End to end delay probability distribution

下载: 全尺寸图片幻灯片

表 1 TT消息参数

Table 1. Parameters of TT message

TT消息	周期/μs
TT₁~TT₂	2 000
TT₃~TT₆	4 000
TT₇~TT₁₄	8 000
TT₁₅~TT₃₀	16 000
TT₃₁~TT₆₂	32 000
TT₆₃~TT₁₂₆	64 000

下载: 导出CSV

表 2 RC消息参数

Table 2. Parameters of RC message

BAG/μs	消息类型
BAG/μs	航空控制类	数据通信类	多媒体
2 000	RC₁~RC₂
4 000	RC₃	RC₄~RC₆
8 000	RC₇~RC₉	RC₁₀~RC₁₁	RC₁₂~RC₁₄
16 000	RC₁₅~RC₁₇	RC₁₈~RC₂₀	RC₂₁~RC₂₂
32 000	RC₂₃	RC₂₄~RC₂₅	RC₂₆~RC₂₈
64 000	RC₂₉~RC₃₀		RC₃₁~RC₃₂

下载: 导出CSV

表 3 平均端到端延迟

Table 3. Average end to end delay

算法	平均端到端延迟/μ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

下载: 导出CSV

表 4 最坏端到端延迟

Table 4. The worst end to end delay

算法	最坏端到端延迟/μ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

下载: 导出CSV

参考文献(19)

[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. http://bhxb.buaa.edu.cn/CN/abstract/abstract13350.shtml 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). http://bhxb.buaa.edu.cn/CN/abstract/abstract13350.shtml
[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