Scheduling Pattern of Time Triggered Ethernet Based on Reinforcement Learning

HE Feng; XIONG Li; ZHOU Xuan; LI Haoruo; XIONG Huagang

doi:10.23919/cje.2021.00.419

Volume 32 Issue 5

Sep. 2023

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > 32(5): 1022-1035

HE Feng, XIONG Li, ZHOU Xuan, et al., “Scheduling Pattern of Time Triggered Ethernet Based on Reinforcement Learning,” Chinese Journal of Electronics, vol. 32, no. 5, pp. 1022-1035, 2023, doi: 10.23919/cje.2021.00.419

Citation:

HE Feng, XIONG Li, ZHOU Xuan, et al., “Scheduling Pattern of Time Triggered Ethernet Based on Reinforcement Learning,” Chinese Journal of Electronics, vol. 32, no. 5, pp. 1022-1035, 2023, doi: 10.23919/cje.2021.00.419

Citation:

PDF( 7370 KB)

Scheduling Pattern of Time Triggered Ethernet Based on Reinforcement Learning

doi: 10.23919/cje.2021.00.419

HE Feng^{1, 2},
XIONG Li²,
ZHOU Xuan^2
,,
LI Haoruo²,
XIONG Huagang^2
,

1.
Shenzhen Institute of Beihang University, Shenzhen 518000, China
2.
School of Electronics and Information Engineering, Beihang University, Beijing 100191, China

Funds: This work was supported by the Technology Development Fund of Shenzhen (2021Szvup082) and the National Natural Science Foundation of China (62071023)

More Information

Author Bio:
Feng HE received the Ph.D. degree in communication and information systems from the School of Electronic Information Engineering, Beihang University, China, in 2008. He is an Associate Professor with the School of Electronic Information Engineering, Beihang University, China. In this area, he has published over 76 peer-reviewed papers and 2 books. He has presided more than ten major projects in total, such as National Natural Science Foundation of China, National 863 Program and Civil Aircraft Research. His research interests include digital communication technology, communication network theory and technology, avionics integration, software defined network, embedded system, and real-time network

Li XIONG was born in Nanchang, China. He received the B.S. degree in electronics and information engineering, Beihang University in 2020. He is currently pursuing the M.E. degree in communication and information system at the School of Electronic Information Engineering, Beihang University, China

Xuan ZHOU (corresponding author) received the Ph.D. degree in communication and information systems from Beihang University in 2021. She is currently a Postdoc at the School of Electronic Information Engineering, Beihang University. The main research direction is real-time communication system, scheduling design and performance evaluation. She has published more than ten papers in related fields. (Email: lomoo@buaa.edu.cn)

Haoruo LI was born in Chengdu, China. He received the B.S. degree in electronics and information engineering, Beihang University in 2018. Then, he received the M.S. degree in communication and information system at the School of Electronic Information Engineering, Beihang University, China, in 2020

Huagang XIONG received the Ph.D. degree in communication and information system from the School of Electronic Information Engineering, Beihang University, China, in 1998. He is currently a Full Professor with Beihang University, China. He has published over 305 peer-reviewed SCI/EI papers and 3 books. He has presided more than twenty major projects in total, such as National Natural Science Foundation of China, National 863 Program and Civil Aircraft Research. His research is focused on communication network theory and technology, avionics information integration, airborne network, and standards. He is the chief of BUAA-TTTech Time-Triggered Technology Joint Laboratory (TTTJL) at Beihang University. He is also the head of the Avionics and Bus Communications Research Team (ABC) at School of Electronic Information Engineering, Beihang University. Furthermore, he is a Member of China Aviation Electronics Standardization Committee, the director of Beijing Electronic Circuit Research Association, a Member of Avionics and Air Traffic Control Branch of China Society of Aeronautics and Astronautics, and an Expert of Civil Aircraft Scientific Research Group. (Email: hgxiong@buaa.edu.cn)
Received Date: 2021-12-06
Accepted Date: 2022-05-05

Available Online: 2023-01-31

Publish Date: 2023-09-05

Abstract

Abstract

Time-triggered Ethernet (TTEthernet or TTE for short) is a deterministic and congestion-free network based on the Ethernet standard. It supports mix-critical real-time applications by providing different message classes. The time-triggered (TT) messages have strict end-to-end delay and accurate jitter requirement, and the rate-constrained (RC) messages have less determinism than TT messages but with bounded end-to-end delay requirement. Traditionally, the scheduling of TT messages makes it free of conflicts for the transmission on physical links, but ignoring RC messages scheduling, so it cannot guarantee the transmission of RC messages with a bounded delay. Therefore, the design of TT schedule becomes the key to TTE network applications within avionics environment. In this paper, we propose an algorithm called RLTS based on reinforcement learning and tree search, to optimize the end-to-end delays of both TT and RC messages. Besides, its computation speed is dozens of times faster than satisfied modularity theory (SMT) with asynchronous method for the calculation of the optimal scheduling table. In the case of a large network with more than 1000 TT and 1000 RC messages, the RLTS method can find a scheduling timetable in 10 seconds, and reduce the worst-case delay of RC messages averagely by 20% compared to the genetic algorithm. Meanwhile, our algorithm has a good generalization performance, in another word, it can quickly adjust itself to satisfy the scheduling with the similar performance as before. By using our method, the scheduling pattern of TTEthernet is further discussed. According to the experimental results, the uniformly distributed slots scheduling pattern, namely the porosity scheduling model which is usually recommended for TTE application, is not always suitable for general situations.
- Time-triggered Ethernet,
- Schedule pattern,
- Reinforcement learning,
- Network calculus

FullText(HTML)

References(34)

References

[1]	IEEE Std 802.3-2022: 1968, IEEE Standard for Ethernet, Available at: https://ieeexplore.ieee.org/document/9844436.
[2]	Y. H. Lee, Safety and Certification Approaches for Ethernet Based Aviation Databuses, Technical Report, DOT/FAA/AR-05/52, Federal Aviation Administration, 2005.
[3]	AEE Committee, Arinc specification 664 p7, ARINC 664 aircraft data network, Avionics full duplex switched Ethernet (AFDX) network, Technical report, Annapolis, MD, USA: Aeronautical Radio Inc., 2005.
[4]	R. I. Davis, A. Burns, R. J. Bril, et al., “Controller area network (CAN) schedulability analysis: refuted, revisited and revised,” Real-Time Systems, vol.35, no.3, pp.239–272, 2005. doi: 10.1007/s11241-007-9012-7
[5]	SAE. SAE AS6802 Time-triggered Ethernet, Warrendale: SAE International, 2011.
[6]	J. D. Decotignie, “Ethernet-based real-time and industrial communications,” Proceedings of the IEEE, vol.93, no.6, pp.1102–1117, 2005. doi: 10.1109/JPROC.2005.849721
[7]	W. Steiner, “An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks,” in 2010 31st IEEE Real-Time Systems Symposium, San Diego, CA, USA, pp.375–384, 2010.
[8]	V. Mnih, K. Kavukcuoglu, D. Silver, et al., “Human-level control through deep reinforcement learning,” Nature, vol.518, no.7540, pp.529–533, 2015. doi: 10.1038/nature14236
[9]	S. Daftry, J. A. Bagnell, and M. Hebert, “Learning transferable policies for monocular reactive MAV control,” in 15th International Symposium on Experimental Robotics, Nagasaki, Japan, pp.3–11, 2016.
[10]	D. Silver, J. Schrittwieser, K. Simonyan, et al., “Mastering the game of go without human knowledge,” Nature, vol.550, no.7676, pp.354–359, 2017. doi: 10.1038/nature24270
[11]	A. Ecoffet, J. Huizinga, J. Lehman, et al., Go-explore: a new approach for hard-exploration problems, arXiv preprint arXiv: 1901.10995, 2019, doi: 10.48550/arXiv.1901.10995.
[12]	H. J. Dai, E. B. Khalil, Y. Y. Zhang, et al., “Learning combinatorial optimization algorithms over graphs,” in Proceedings of the 31st International Conference on Neural Information Processing Systems, Long Beach CA, USA, 2017.
[13]	O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer networks,” in Proceedings of the 28th International Conference on Neural Information Processing Systems, Montreal, Canada, pp.2692–2700, 2015.
[14]	V. Mnih, A. P. Badia, M. Mirza, et al., “Asynchronous methods for deep reinforcement learning,” in Proceedings of the 33rd International Conference on International Conference on Machine Learning, New York, NY, USA, pp.1928–1937, 2016.
[15]	R. Dobrin and G. Fohler, “Implementing off-line message scheduling on controller area network (CAN),” in ETFA 2001. 8th International Conference on Emerging Technologies and Factory Automation, Antibes-Juan les Pins, France, pp.241–245, 2001.
[16]	R. I. Davis and A. Burns, “Robust priority assignment for messages on controller area network (CAN),” Real-Time Systems, vol.41, no.2, pp.152–180, 2009. doi: 10.1007/s11241-008-9065-2
[17]	R. Marau, L. Almeida, P. Pedreiras, et al., “Utilization-based schedulability analysis for switched Ethernet aiming dynamic QoS management,” in 2010 IEEE 15th Conference on Emerging Technologies & Factory Automation, Bilbao, Spain, pp.1–10, 2010.
[18]	E. Suethanuwong, “Scheduling time-triggered traffic in TTEthernet systems,” in Proceedings of 2012 IEEE 17th International Conference on Emerging Technologies & Factory Automation, Krakow, Poland, pp.1–4, 2012.
[19]	F. Glover, “Future paths for integer programming and links to artificial intelligence,” Computers & Operations Research, vol.13, no.5, pp.533–549, 1986. doi: 10.1016/0305-0548(86)90048-1
[20]	Y. J. Zhang, F. He, G. S. Lu, et al., “An imporosity message scheduling based on modified genetic algorithm for time-triggered Ethernet,” Science China Information Sciences, vol.61, article no.019102, 2018. doi: 10.1007/s11432-017-9121-6
[21]	D. Tămaş-Selicean, P. Pop, and W. Steiner, “Design optimization of TTEthernet-based distributed real-time systems,” Real-Time Systems, vol.51, no.1, pp.1–35, 2015. doi: 10.1007/s11241-014-9214-8
[22]	R. E. Korf, “Depth-first iterative-deepening: An optimal admissible tree search,” Artificial Intelligence, vol.27, no.1, pp.97–109, 1985. doi: 10.1016/0004-3702(85)90084-0
[23]	R. S. Sutton, D. A. McAllester, S. P. Singh, et al., “Policy gradient methods for reinforcement learning with function approximation,” in Proceedings of the 12th International Conference on Neural Information Processing Systems, Denver, CO, USA, pp.1057–1063, 1999.
[24]	H. R. Li, F. He, Z. Zheng, et al., “Time-triggered communication scheduling method based on reinforcement learning,” Journal of Beijing University of Aeronautics and Astronautics, vol.45, no.9, pp.1894–1901, 2019. (in Chinese) doi: 10.13700/j.bh.1001-5965.2018.0789
[25]	D. Silver, A. Huang, C. J. Maddison, et al., “Mastering the game of Go with deep neural networks and tree search,” Nature, vol.529, no.7587, pp.484–489, 2016. doi: 10.1038/nature16961
[26]	L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning,” in 17th European Conference on Machine Learning, Berlin, Germany, pp.282–293, 2006.
[27]	D. Silver, G. Lever, N. M. O. Heess, et al., “Deterministic policy gradient algorithms,” in Proceedings of the 31st International Conference on International Conference on Machine Learning, Beijing, China, pp.I-387–I-395, 2014.
[28]	P. Abbeel and A. Y. Ng, “Apprenticeship learning via inverse reinforcement learning,” in Proceedings of the Twenty-First International Conference on Machine Learning, Banff, Canada, pp.1–8, 2004.
[29]	D. Horgan, J. Quan, D. Budden, et al., “Distributed prioritized experience replay,” in 6th International Conference on Learning Representations, Vancouver, Canada, 2018.
[30]	L. X. Zhao, P. Pop, Q. Li, et al., “Timing analysis of rate-constrained traffic in TTEthernet using network calculus,” Real-Time Systems, vol.53, no.2, pp.254–287, 2017. doi: 10.1007/s11241-016-9265-0
[31]	X. Glorot, A. Bordes, and Y. Bengio, “Deep sparse rectifier neural networks,” in Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, Fort Lauderdale, FL, USA, pp.315–323, 2011.
[32]	D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in 3rd International Conference on Learning Representations, San Diego, CA, USA, 2015.
[33]	D. Clevert, T. Unterthiner, and S. Hochreiter, “Fast and accurate deep network learning by exponential linear units (ELUs),” in 4th International Conference on Learning Representations, San Juan, Puerto Rico, 2016.
[34]	Y. J. Zhang, F. He, G. S. Lu, et al., “Scheduling rate-constrained flows with dynamic programming priority in time-triggered ethernet,” Chinese Journal of Electronics, vol.26, no.4, pp.849–855, 2017. doi: 10.1049/cje.2017.06.002