ZHANG Yingjing, HE Feng, LU Guangshan, XIONG Huagang. Scheduling Rate-Constrained Flows with Dynamic Programming Priority in Time-Triggered Ethernet[J]. Chinese Journal of Electronics, 2017, 26(4): 849-855. doi: 10.1049/cje.2017.06.002
Citation: ZHANG Yingjing, HE Feng, LU Guangshan, XIONG Huagang. Scheduling Rate-Constrained Flows with Dynamic Programming Priority in Time-Triggered Ethernet[J]. Chinese Journal of Electronics, 2017, 26(4): 849-855. doi: 10.1049/cje.2017.06.002

Scheduling Rate-Constrained Flows with Dynamic Programming Priority in Time-Triggered Ethernet

doi: 10.1049/cje.2017.06.002
Funds:  This work is supported by the National Natural Science Foundation of China (No.61301086), the Aeronautical Science Foundation of China (No.20131951027), and the Basic Scientific Research (No.YWF-15-GJSYS-055).
More Information
  • Corresponding author: HE Feng (corresponding author) is an assistant professor in school of Electronic and Information Engineering, Beihang University. His research interests include real-time communication system, distributed real-time network system, the integrated avionic system, etc. (Email: robinleo@.buaa.edu.cn)
  • Received Date: 2015-03-13
  • Rev Recd Date: 2015-06-25
  • Publish Date: 2017-07-10
  • Time-triggered (TT), Rate-constrained (RC) and Best-effort (BE) traffics are included in Timetriggered ethernet (TTEthernet). For RC messages transmission is affected by TT messages, traditional scheduling policy cannot be well applied in TTEthernet. Dynamic programming priority (DPP) algorithm combines priority policy and dynamic programming algorithm for scheduling RC flows. The time slice for RC flows transmission is got by SMT solver YICES; RC flows are classified to different groups according to the priorities; Higher priority packets in one time slice are scheduled using First input first output (FIFO) policy and lower priority packets are scheduled by Dynamic programming policy. DPP policy guarantees different real-time requirements of heterogeneous RC flows, and make the best of time slice resource in aviation industries. The upper bound End-End of three methods and algorithm feasibility is analyzed. Simulation in aviation shows that DPP policy can obtain better real-time performance than other scheduling algorithms.
  • loading
  • SAE AS6802, “Time-triggered ethernet”, Society of Automotive Engineers, Washington, 1997.
    W. Steiner, “Candidate security solutions for ttethernet”, IEEE/AIAA 32nd Digital Avionics Systems Conference (DASC), 2014.
    Luxi Zhao and Huagang Xiong, “Improving worst-case latency analysis for rate-constrained traffic in the time-triggered ethernet network”, Communications Letters, Vol.18, No.4, pp.1927-1930, 2014.
    R. Wolfig and M. Jakovljevic, “Architectural, communication and certification attributes”, Proc. 27th Digital Avionics Systems Conference (DASC), 2008.
    ARINC Specification 664 P7, ARINC 664 Aircraft Data Network, “Avionics full duplex switched ethernet (AFDX) network”, Airlines Electronic ARINC 664 Engineering Committee (AEEC), 2005.
    M. Boyer and C. Fraboul, “Tightening end to end delay upper bound for AFDX network calculus with rate latency FIFO servers using network calculus”, Proc. IEEE Int’l Workshop Factory Comm. Systems, pp.11-20, 2008.
    Z.Z. He, et al., “Schedulability of fault tolerant real time system based on local optimum checkpoint under priority mixed strategy”, Chinese Journal of Electronics, Vol.24, pp.236-244, 2015.
    J. Bennett and H. Zhang, “WF2Q: Worst-case fair weighted fair queueing”, Proc. INFOCOM, 1996.
    Yuan Xin and Z. Duan, “Fair round-robin: A low complexity packet scheduler with proportional and worst-case fairness”, IEEE Transactions on Computers, Vol.3, pp.365-379, 2009.
    P. Valente, “Providing near-optimal fair-queueing guarantees at round-robin amortized cost”, Computer Communications and Networks (ICCCN), the 22nd International Conference, pp.1-7, 2013.
    C.K. Pang, et al., “Evaluation of dynamic programming based methods and multiple area representation for thermal unit commitments”, IEEE Transactions on Power Apparatus and Systems, Vol.100, No.3, pp.1212-1218, 1981.
    B. Elshqeirat and S. Soh, “A dynamic programming algorithm for reliable network design”, IEEE Transactions on reliability, pp.443-454, 2014.
    Shanjiang Tang, Ce Yu and Jizhou Sun, “An efficient parallel dynamic programming runtime system for computational biology”, IEEE Trans. Parallel and Distributed Systems, Vol.23, No.5, pp.862-872, 2012.
    Y. Hua and X. Liu, “Scheduling heterogeneous flows with delayaware deduplication for avionics applications”, IEEE Trans. On Parallel and Distributed Systems, Vol.23, No.9, pp.1790-1802, 2012.
    W. Steiner, “An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks”, Proc. IEEE 31st Real-Time Systems Symposium, pp.375-384, 2010.
    W. Steiner, “Synthesis of static communication schedules for mixed-criticality systems”, Proc. 8th IEEE/ACM/IFIP Inter-National Conference on Hardware/Software Code Design and System Synthesis, pp.11-17, 2011.
    D. Tamas, P. Pop and W. Steiner, “Synthesis of communication schedules for TTEthernet-based mixed-criticality systems”, 2012 Proc. 8th IEEE/ACM/IFIP Inter-National Conference on Hardware/Software Code Design and System Synthesis, pp.473-482, 2012.
    M. Tawk, J. Li and X. Liu, “Optimal scheduling and delay analysis for AFDX end-systems”, Aero Tech Congress and Exhibition, 2011.
    Z. Ni, H. He and J. Wen, “Adaptive learning in tracking control based on the dual critic network design”, IEEE Trans. Neural Netw. Learn. Syst, Vol.24, No.6, pp.913-928, 2013.
    J. Scharbarg, F. Ridouard and C. Fraboul, “A probabilistic analysis of end-to-end delays on an AFDX network”, IEEE Trans. Ind. Informat, Vol.5, No.1, pp.38-49, 2009.
    X. Liu and T. Abdelzaher, “Non-utilization bounds and feasible regions for arbitrary fixed-priority policies”, J. ACM Trans. Embedded Computing Systems, Vol.10, 2010.
    D. Wunsch, W.B. PowellW and A.G. Barto, “Handbook of learning and approximate dynamic programming”, IEEE Press Series on Computational Intelligence, 2004.
    H. Bauer, L. Scharbarg and C. Fraboul, “Improving the worstcase delay analysis of an AFDX network using an optimized trajectory approach”, IEEE Transactions on Industrial Informatics, Vol.6, No.4, pp.521-533, 2010.
    J. Michael, Neely and Senior Member, “Delayed-based network utility maximization”, IEEE/ACM Transactions on Networking, Vol.21, No.1, 2013.
    R.L. Cruz, “A calculus for network delay, Part I: Network elements in isolation”, IEEE Transactions on Information Theory, Vol.37, No.1, pp.114-131, 1991.
    J.-Y. L, Boudec and P. Thiran, “A calculus for network delay, Part I: Network elements in isolation”, IEEE Transactions on Information Theory, Springer Verlag, pp.40-43, 2012.
    TTTech Company, “TTEthernet: A powerful network solution for advanced integrated systems”, http://www.ge-ip.com, 2010.
    Hui Lu and Ruiyao Niu, “Constraint-guided methods with evolutionary algorithm for the automatic test task scheduling problem”, Chinese Journal of Electronics, Vol.23, pp.616-620, 2014.
    M.J. Neely, “Opportunistic scheduling with worst case delay guarantees in single and multi-hop networks”, Proc. IEEE INFOCOM, pp.728-1736, 2011.
    P. Giaccone, E. Leonardi and D. Shah, “Throughput region of finite buffered networks”, IEEE Trans. Parallel Distrib.Syst., Vol.18, No.2, pp.251-263, 2007.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (160) PDF downloads(1043) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return