留言板

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

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

软件定义时间触发网络的调度算法优化

鲁俊 何锋 熊华钢 郑重

鲁俊, 何锋, 熊华钢, 等 . 软件定义时间触发网络的调度算法优化[J]. 北京航空航天大学学报, 2021, 47(5): 1004-1014. doi: 10.13700/j.bh.1001-5965.2020.0106
引用本文: 鲁俊, 何锋, 熊华钢, 等 . 软件定义时间触发网络的调度算法优化[J]. 北京航空航天大学学报, 2021, 47(5): 1004-1014. doi: 10.13700/j.bh.1001-5965.2020.0106
LU Jun, HE Feng, XIONG Huagang, et al. Scheduling algorithms optimization in software defined time-triggered network[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(5): 1004-1014. doi: 10.13700/j.bh.1001-5965.2020.0106(in Chinese)
Citation: LU Jun, HE Feng, XIONG Huagang, et al. Scheduling algorithms optimization in software defined time-triggered network[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(5): 1004-1014. doi: 10.13700/j.bh.1001-5965.2020.0106(in Chinese)

软件定义时间触发网络的调度算法优化

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

国家自然科学基金 71701020

装备预研领域基金 61403120404

详细信息
    作者简介:

    鲁俊  男, 博士研究生。主要研究方向: 航空电子信息综合、软件定义网络和嵌入式系统

    何锋  男, 博士, 副教授, 博士生导师。主要研究方向: 实时通信、通信网络、航空电子综合、嵌入式系统

    熊华钢  男, 博士, 教授, 博士生导师。主要研究方向: 通信网络理论与技术、航空电子信息综合、机载网络

    郑重  男, 博士研究生。主要研究方向: 时间触发式以太网和系统优化

    通讯作者:

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

  • 中图分类号: TP393.1

Scheduling algorithms optimization in software defined time-triggered network

Funds: 

National Natural Science Foundation of China 71701020

Equipment Pre-research Field Foundation 61403120404

More Information
  • 摘要:

    软件定义时间触发以太网(TTE)作为优化航空电子系统中消息调度的一种新模式,其动态在线调度算法必须尽力保证任何情况下所有消息的传输确定性。针对时间触发(TT)消息调度间隔小于消息帧长(小时隙)时,速率约束RC消息延迟增大、传输确定性降低的问题,对TT消息调度算法进行改进。首先,构建了TTE的系统模型,阐明了最小延迟(MID)调度算法和背靠背(B2B)调度算法的机制;然后在其基础上提出了大孔隙(MAV)调度算法,以减少(RC)消息的等待延迟;最后,利用OMNeT++实验分析这3种调度算法的性能。实验结果表明:当无小时隙TT消息时,B2B算法的消息延迟最大、MAV调度算法和MID调度算法的消息延迟接近。当有小时隙TT消息时,MAV调度算法的消息传输确定性更好,相比于MID调度算法,MAV调度算法下RC消息的传输确定性提高了87.3%。

     

  • 图 1  软件定义时间触发以太网的网络架构

    Figure 1.  Network framework of SDTTE

    图 2  背靠背调度算法的RC消息延迟

    Figure 2.  RC message delay by B2B scheduling algorithm

    图 3  大孔隙调度算法的RC消息延迟

    Figure 3.  RC message delay by macrovoid scheduling algorithm

    图 4  大孔隙调度算法的流程图

    Figure 4.  Flowchart of macrovoid scheduling algorithm

    图 5  无小时隙TT消息时不同调度算法的RC最坏延迟

    Figure 5.  RC message worst case delays by different scheduling algorithms without small time interval TT messages

    图 6  小时隙TT消息下不同调度算法的RC最坏延迟

    Figure 6.  RC message worst case delays by different scheduling algorithms with small time interval TT messages

    图 7  基于OMNeT

    Figure 7.  End system module based on OMNeT++

    图 8  网络拓扑

    Figure 8.  Network topology

    图 9  无小时隙TT消息下不同调度算法的TT消息延迟

    Figure 9.  TT message delays by different scheduling algorithms without small time interval TT messages

    图 10  无小时隙TT消息下不同调度算法的RC消息延迟

    Figure 10.  RC message delays by different scheduling algorithms without small time interval TT messages

    图 11  有小时隙TT消息下不同调度算法的TT消息延迟

    Figure 11.  TT message delays by different scheduling algorithms with small time interval TT messages

    图 12  有小时隙TT消息下不同调度算法的RC消息延迟

    Figure 12.  RC message delays by different scheduling algorithms with small time interval TT messages

    图 13  不同场景下不同调度算法的RC消息延迟

    Figure 13.  RC message delays by different scheduling algorithms in different scenarios

    表  1  实验消息配置

    Table  1.   Message configuration in experiment

    终端系统 类型 参数 配置
    ES 1~ES 4 TT 数量 32条
    帧长 1 250 B
    周期 32 ms
    间隔时间 150 μs/240 μs
    RC 数量 32条
    帧长 1 250 B
    BAG 32 ms
    下载: 导出CSV

    表  2  无小时隙TT消息下不同调度算法的消息延迟统计

    Table  2.   Statistics of message delays by different scheduling algorithms without small time interval TT messages

    算法 TT/ms RC/ms
    最大 平均 标准差 最大 平均 标准差
    MID 0.401 0.355 0.069 32.396 31.298 0.789
    B2B 1.610 0.960 0.371 37.595 32.259 1.708
    MAV 0.401 0.355 0.069 32.396 31.298 0.789
    下载: 导出CSV

    表  3  有小时隙TT消息下不同调度算法的消息延迟统计

    Table  3.   Statistics of message delays by different scheduling algorithms with small time interval TT messages

    算法 TT/ms RC/ms
    最大 平均 标准差 最大 平均 标准差
    MID 0.401 0.355 0.069 36.792 31.992 1.511
    B2B 4.400 2.355 1.201 35.567 31.653 1.197
    MAV 0.479 0.395 0.072 32.830 31.364 0.756
    下载: 导出CSV
  • [1] KOPETZ H, ADEMAJ A, GRILLINGER P, et al. The Time-Triggered Ethernet (TTE) design[C]//Proceedings of the 8th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing. Piscataway: IEEE Press, 2005: 22-33.
    [2] STEINER W, BAUER G, HALL B, et al. TTEthernet dataflow concept[C]//Proceedings of the 8th IEEE International Symposium on Network Computing & Applications. Piscataway: IEEE Press, 2009: 319-322.
    [3] KOPETZ H. Event-triggered versus time-triggered real-time systems[M]. Berlin: Springer, 1991: 86-101.
    [4] GOPALAKRISHNAN S, CACCAMO M, SHA L. Switch scheduling and network design for real-time systems[C]//Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium. Piscataway: IEEE Press, 2006: 289-300.
    [5] SUETHANUWONG E. Scheduling time-triggered traffic in TTEthernet systems[C]//Proceedings of the 2012 IEEE 17th Conference on Emerging Technologies & Factory Automation. Piscataway: IEEE Press, 2012: 1-4.
    [6] CRACIUNAS S S, OLIVER R S, ECKER V. Optimal static scheduling of real-time tasks on distributed time-triggered networked systems[C]//Proceedings of the 2012 IEEE 17th Conference on Emerging Technology & Factory Automation. Piscataway: IEEE Press, 2014: 1-8.
    [7] BARRETT C, TINELLI C. Satisfiability modulo theories[M]. Berlin: Springer, 2018: 305-343.
    [8] SEBASTIANI R. Lazy satisfiability modulo theories[J]. Journal on Satisfiability, Boolean Modeling and Computation, 2007, 3: 141-224. doi: 10.3233/SAT190034
    [9] CRACIUNAS S S, OLIVER R S. Combined task-and network-level scheduling for distributed time-triggered systems[J]. Real-time Systems, 2016, 52(2): 161-200. doi: 10.1007/s11241-015-9244-x
    [10] SCHOLER C, KRENZ-BAATH R, MURSHED A, et al. Computing optimal communication schedules for time-triggered networks using an SMT solver[C]//Proceedings of the IEEE International Symposium on Industrial Embedded Systems. Piscataway: IEEE Press, 2016: 1-9.
    [11] STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//Proceedings of the 31st IEEE Real-Time Systems Symposium. Piscataway: IEEE Press, 2010: 375-384.
    [12] POZO F, STEINER W, RODRIGUEZ-NAVAS G, et al. A decomposition approach for SMT-based schedule synthesis for time-triggered networks[C]//Proceedings of the IEEE 20th Conference on Emerging Technologies & Factory Automation. Piscataway: IEEE Press, 2015: 1-8.
    [13] TAMAS-SELICEAN D, POP P, STEINER W. Timing analysis of rate constrained traffic for the ttethernet communication protocol[C]//Proceedings of the IEEE 18th International Symposium on Real-Time Distributed Computing. Piscataway: IEEE Press, 2015: 119-126.
    [14] YAO J, XU X, LIU X. MixCPS: Mixed time/event-triggered architecture of cyber-physical systems[J]. Proceedings of the IEEE, 2016, 104(5): 923-937. doi: 10.1109/JPROC.2016.2519381
    [15] ZHAO L X, POP P, LI Q, et al. Timing analysis of rate-constrained traffic in TTEthernet using network calculus[J]. Real-time Systems, 2017, 53(2): 254-287. doi: 10.1007/s11241-016-9265-0
    [16] BOYER M, DAIGMORTE H, NAVET N, et al. Performance impact of the interactions between time-triggered and rate-constrained transmissions in TTEthernet[J]. Embedded Real time Systems, 2016, 14(2): 217-225. http://hal.archives-ouvertes.fr/hal-01255939
    [17] STEINER W. Synthesis of static communication schedules for mixed-criticality systems[C]//IEEE International Symposium on Object/Component/Service-Oriented Real-time Distributed Computing Workshops. Piscataway: IEEE Press, 2011: 11-18.
    [18] TAMAS-SELICEAN D, POP P, STEINER W. Synthesis of communication schedules for TTEthernet-based mixed-criticality systems[C]//Proceedings of the 8th ACM International Conference on Hardware/Software Codesign & System Synthesis. New York: ACM, 2012: 473-482.
    [19] ZHANG L, GOSWAMI D, SCHNEIDER R, et al. Task-and network-level schedule co-synthesis of Ethernet-based time-triggered systems[C]//Proceedings of the 19th Asia and South Pacific Design Automation Conference (ASP-DAC). Piscataway: IEEE Press, 2014: 119-124.
    [20] FORGET J, BONIOL F, GROLLEAU E, et al. Scheduling dependent periodic tasks without synchronization mechanisms[C]//Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium. Piscataway: IEEE Press, 2010: 301-310
    [21] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: Enabling innovation in campus networks[J]. ACM Sigcomm Computer Communication Review, 2008, 38(2): 69-74. doi: 10.1145/1355734.1355746
    [22] TIAN Z, LI S, WANG Y, et al. Priority scheduling of networked control system based on fuzzy controller with self-tuning scale factor[J]. IAENG International Journal of Computer Science, 2017, 44(3): 308-315. http://www.researchgate.net/publication/319458469_Priority_scheduling_of_networked_control_system_based_on_fuzzy_controller_with_self-tuning_scale_factor
    [23] SAMPIGETHAYA K. Software-defined networking in aviation: Opportunities and challenges[C]//Proceedings of the 8th Integrated Communication, Navigation, and Surveillance Conference (ICNS). Piscataway: IEEE Press, 2015: 1-21.
    [24] HEISE P, GEYER F, OBERMAISSER R. Deterministic OpenFlow: Performance evaluation of SDN hardware for avionic networks[C]//Proceedings of the 8th 11th International Conference on Network and Service Management (CNSM). Piscataway: IEEE Press, 2016: 372-377.
    [25] KUMAR R, HASAN M, PADHY S, et al. End-to-end network delay guarantees for real-time systems using SDN[C]//Proceedings of the 8th IEEE Real-Time Systems Symposium (RTSS). Piscataway: IEEE Press, 2017: 231-242.
    [26] LU J, XIONG H G, HE F, et al. Enhancing real-time and determinacy for network-level schedule in distributed mixed-critical system[J]. IEEE Access, 2020, 8: 23720-23731. doi: 10.1109/ACCESS.2020.2970266
    [27] CRACIUNAS S, OLIVER R. SMT-based task-and network-level static schedule generation for time-triggered networked systems[C]//International Conference on Real-time Networks & Systems. New York: ACM, 2014: 45-54.
    [28] 何锋, 周璇, 赵长啸, 等. 航空电子系统机载网络实时性能评价技术[J]. 北京航空航天大学学报, 2020, 46(4): 651-665. doi: 10.13700/j.bh.1001-5965.2019.0297

    HE F, ZHOU X, ZHAO C X, et al. Real-time performance evaluation technology of airborne network for avionics system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 651-665(in Chinese). doi: 10.13700/j.bh.1001-5965.2019.0297
    [29] 王荣巍, 何锋, 周璇, 等. 面向无人机蜂群的航电云多层任务调度模型[J]. 航空学报, 2019, 40(11): 1-12. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201911019.htm

    WANG R W, HE F, ZHOU X, et al. Avionics cloud multi-layer task scheduling model for UAV swarm[J]. Acta Aeronautica et Astronautica Sinica, 2019, 40(11): 1-12(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201911019.htm
    [30] 鲁俊, 何锋, 熊华钢. 航空电子云系统架构与网络[J]. 航空电子技术, 2017, 28(3): 1-9. https://www.cnki.com.cn/Article/CJFDTOTAL-HKDZ201703001.htm

    LU J, HE F, XIONG H G. System and network architecture of avionics cloud[J]. Avionics Technology, 2017, 28(3): 1-9(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HKDZ201703001.htm
    [31] TIAN Z, LI S, WANG Y, et al. Scheduling method for networked control system with resource constraints based on fuzzy feedback priority and variable sampling period[J]. Transactions of the Institute of Measurement & Control, 2018, 40(4): 1136-1149. http://smartsearch.nstl.gov.cn/paper_detail.html?id=74806279b8fe25ee41ac9b1a8cee93e9
    [32] FRANCES F, FRABOUL C, GRIEU J. Using network calculus to optimize the AFDX network[J]. Medical Imaging IEEE Transactions on Embedded Real Time Systems, 2006, 25(10): 1319-1328. http://www.researchgate.net/publication/27813294_Using_network_calculus_to_optimize_the_AFDX_network/download
    [33] BOYER M, MIGGE J, FUMEY M. PEGASE-A robust and efficient tool for worst-case network traversal time evaluation on AFDX[J]. Physiology and Behavior, 2011, 25(4): 589-593. http://www.researchgate.net/publication/289860018_PEGASE_-_A_robust_and_efficient_tool_for_worst-case_network_traversal_time_evaluation_on_AFDX?ev=auth_pub
    [34] KLEIN D, JARSCHEL M. An OpenFlow extension for the OMNeT++ INET framework[C]//Proceedings of the 6th International Institute for Computer Sciences, Social-Informatics and Telecommunications (ICST) Conference on Simulation Tools and Techniques. Reston: ACM, 2013: 322-329.
    [35] SALIH M A, COSMAS J, ZHANG Y. OpenFlow 1.3 extension for OMNeT++[C]//2015 IEEE International Conference on Computer and Information Technology Ubiquitous Computing and Communications Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing. Piscataway: IEEE Press, 2015: 1632-1637.
  • 加载中
图(13) / 表(3)
计量
  • 文章访问数:  639
  • HTML全文浏览量:  87
  • PDF下载量:  65
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-03-24
  • 录用日期:  2020-07-18
  • 网络出版日期:  2021-05-20

目录

    /

    返回文章
    返回
    常见问答