留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

张英静 何锋 卢广山 熊华钢

张英静, 何锋, 卢广山, 等 . 基于TTE的改进加权轮询调度算法[J]. 北京航空航天大学学报, 2017, 43(8): 1577-1584. doi: 10.13700/j.bh.1001-5965.2016.0590
引用本文: 张英静, 何锋, 卢广山, 等 . 基于TTE的改进加权轮询调度算法[J]. 北京航空航天大学学报, 2017, 43(8): 1577-1584. doi: 10.13700/j.bh.1001-5965.2016.0590
ZHANG Yingjing, HE Feng, LU Guangshan, et al. A modified weighted round robin scheduling algorithm in TTE[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(8): 1577-1584. doi: 10.13700/j.bh.1001-5965.2016.0590(in Chinese)
Citation: ZHANG Yingjing, HE Feng, LU Guangshan, et al. A modified weighted round robin scheduling algorithm in TTE[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(8): 1577-1584. doi: 10.13700/j.bh.1001-5965.2016.0590(in Chinese)

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

doi: 10.13700/j.bh.1001-5965.2016.0590
基金项目: 

国家自然科学基金 61301086

航空科学基金 20131951027

详细信息
    作者简介:

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

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

    通讯作者:

    何锋, E-mail:robinleo@buaa.edu.cn

  • 中图分类号: V247.5;TN914

A modified weighted round robin scheduling algorithm in TTE

Funds: 

National Natural Science Foundation of China 61301086

Aeronautical Science Foundation of China 20131951027

More Information
  • 摘要:

    在时间触发以太网(TTE)中,TT消息优先级最高,RC消息只能在TT消息调度的离散时间片内传输,因此,TT消息离线调度表的设计会对RC消息调度产生一定影响。针对这一问题,提出了基于最优时间片的改进加权轮询(MWRR)调度算法。首先,通过TT消息约束条件限制获得TT消息离线调度表,进而得到保证RC消息较大资源利用率的时间片信息;其次,在离散时间片对不同类型RC消息进行调度,并运用网络演算方法对其最坏端到端延迟进行分析;最后,通过实验仿真证实了本文算法不仅具有较低的复杂度和较好的公平性,保证了实际应用中算法的可行性,而且在时延性方面均优于先到先得(FIFO)、优先级(PQ)和加权轮询(WRR)调度算法。

     

  • 图 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
    TT1~TT22 000
    TT3~TT64 000
    TT7~TT148 000
    TT15~TT3016 000
    TT31~TT6232 000
    TT63~TT12664 000
    下载: 导出CSV

    表  2  RC消息参数

    Table  2.   Parameters of RC message

    BAG/μs消息类型
    航空控制类数据通信类多媒体
    2 000RC1~RC2
    4 000RC3RC4~RC6
    8 000RC7~RC9RC10~RC11RC12~RC14
    16 000RC15~RC17RC18~RC20RC21~RC22
    32 000RC23RC24~RC25RC26~RC28
    64 000RC29~RC30RC31~RC32
    下载: 导出CSV

    表  3  平均端到端延迟

    Table  3.   Average end to end delay

    算法平均端到端延迟/μs
    航空控制类消息数据通信类消息多媒体消息
    FIFO2 472.82 469.12 478.2
    PQ481.41 142.18 152.6
    WRR1 998.32 657.83 496.2
    MWRR939.5965.71 057.3
    下载: 导出CSV

    表  4  最坏端到端延迟

    Table  4.   The worst end to end delay

    算法最坏端到端延迟/μs
    航空控制类消息数据通信类消息多媒体消息
    FIFO17 71317 23817 428
    PQ2 6279 28473 880
    WRR14 39113 59017 340
    MWRR7 7978 0979 553
    下载: 导出CSV
  • [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
  • 加载中
图(4) / 表(4)
计量
  • 文章访问数:  901
  • HTML全文浏览量:  109
  • PDF下载量:  479
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-07-13
  • 录用日期:  2016-09-02
  • 网络出版日期:  2017-08-20

目录

    /

    返回文章
    返回
    常见问答