基于发布订阅架构的在线时间触发调度方法

doi:10.7527/S1000-6893.2023.28125

Abstract

Abstract:

The scheduling solution of hybrid critical messages is the key to its application in avionics systems, and increasingly dynamic applications rely more on the online solution of time-triggered scheduling. At present, time-triggered network scheduling is mostly based on offline scheduling design, which take a long time to be generated and are difficult to be adjusted online after generation in large-scale networking applications. In order to solve the scheduling table faster and make online adjustment, this paper constructs a time-triggered network architecture model based on the publish/subscribe model. Then, an online time-triggered scheduling algorithm is proposed based on unified time slots. Time is discretized into time slots with the unified maximum length, which optimizes the scheduling solution space and reduces the time of scheduling table generation. The link load is measured by the time slot length and is balanced in the process of scheduling to reduce the end-to-end delay of rate-constrained messages. The experimental results show that for the network with 300 messages, the scheduling solution speed of the proposed algorithm is thousands of times that of the SMT algorithm, and the worst-case end-to-end delay of rate-constrained messages is reduced by 17.4% compared with that of the SMT algorithm. For the network with 2 000 time-triggered messages, the time of generating schedule table with the proposed method is on the order of 100 milliseconds.

Key words: time-triggered, publish/subscribe architecture, online scheduling, time slicing, real-time performance

CLC Number:

V247

Yifan GAO, Feng HE, Sifan YU. Online time-triggered scheduling method based on publish/subscribe architecture[J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(18): 328125-328125.

Figures/Tables 18

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

TT message parameters

消息id	周期/ $μ s$	源节点	目的节点
1	2	N1	N3
2	4	N1	N3
3	8	N1	N2
4	4	N1	N3

Table 1

Fig.6

Fig.7

Fig. 8

Fig.9

Fig.10

Fig.11

Table 2

Fig.12

Table 3

Fig.13

Fig.14

Fig.15

References 24

1	ZHOU X， XIONG H G， HE F. Hybrid partition- and network-level scheduling design for distributed integrated modular avionics systems［J］. Chinese Journal of Aeronautics， 2020， 33（1）： 308-323.
2	何锋. 机载网络技术基础［M］. 北京：国防工业出版社， 2018： 171-172.
	HE F. Fundamentals of airborne network［M］. Beijing： National Defense Industry Press， 2018： 171-172 （in Chinese）.
3	KOPETZ H， ADEMAJ A， GRILLINGER P， et al. The time-triggered Ethernet （TTE） design［C］∥ Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing （ISORC'05）. Piscataway： IEEE Press， 2005： 22-33.
4	STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks［C］∥ 2010 31st IEEE Real-Time Systems Symposium. Piscataway： IEEE Press， 2011： 375-384.
5	PAHLEVAN M， OBERMAISSER R. Genetic algorithm for scheduling time-triggered traffic in time-sensitive networks［C］∥ 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation （ETFA）. Piscataway： IEEE Press， 2018： 337-344.
6	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.
7	LEE D， LIN B， CHENG C K. SMT-based contention-free task mapping and scheduling on SMART NoC［J］. IEEE Embedded Systems Letters， 2021， 13（4）： 158-161.
8	SERNA OLIVER R， CRACIUNAS S S， STEINER W. IEEE 802.1Qbv gate control list synthesis using array theory encoding［C］∥ 2018 IEEE Real-Time and Embedded Technology and Applications Symposium （RTAS）. Piscataway： IEEE Press， 2018： 13-24.
9	STEINER W， CRACIUNAS S S， OLIVER R S. Traffic planning for time-sensitive communication［J］. IEEE Communications Standards Magazine， 2018， 2（2）： 42-47.
10	ZHANG L C， GOSWAMI D， SCHNEIDER R， et al. Task- and network-level schedule co-synthesis of Ethernet-based time-triggered systems［C］∥ 2014 19th Asia and South Pacific Design Automation Conference （ASP-DAC）. Piscataway： IEEE Press， 2014： 119-124.
11	POP P， RAAGAARD M L， CRACIUNAS S S， et al. Design optimisation of cyber-physical distributed systems using IEEE time-sensitive networks［J］. IET Cyber-Physical Systems： Theory & Applications， 2016， 1（1）： 86-94.
12	SHI Y F， LI Q， YANG J H， et al. A topology-based decomposition approach for time-triggered message scheduling in network-on-chip［C］∥ 2019 IEEE/AIAA 38th Digital Avionics Systems Conference （DASC）. Piscataway： IEEE Press， 2020： 1-8.
13	鲁俊，何锋，熊华钢，等. 软件定义时间触发网络的调度算法优化［J］. 北京航空航天大学学报， 2021， 47（5）： 1004-1014.
	LU J， HE F， XIONG H G， 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 （in Chinese）.
14	TAMAS-SELICEAN D， POP P， STEINER W. Synthesis of communication schedules for TTEthernet-based mixed-criticality systems［C］∥ Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. New York： ACM， 2012： 473-482.
15	TĂMAŞ-SELICEAN D， POP P， STEINER W. Design optimization of TTEthernet-based distributed real-time systems［J］. Real-Time Systems， 2015， 51（1）： 1-35.
16	XU L， XU Q M， TU J Z， et al. Learning-based scalable scheduling and routing co-design with stream similarity partitioning for time-sensitive networking［J］. IEEE Internet of Things Journal， 2022， 9（15）： 13353-13363.
17	POZO F， RODRIGUEZ-NAVAS G， HANSSON H. Schedule reparability： enhancing time-triggered network recovery upon link failures［C］∥ 2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications （RTCSA）. Piscataway： IEEE Press， 2019： 147-156.
18	MONOSTORI L， KÁDÁR B， BAUERNHANSL T， et al. Cyber-physical systems in manufacturing［J］. CIRP Annals， 2016， 65（2）： 621-641.
19	ALNAJIM A， SALEHI S， SHEN C C. Incremental path-selection and scheduling for time-sensitive networks［C］∥ 2019 IEEE Global Communications Conference （GLOBECOM）. Piscataway： IEEE Press， 2020： 1-6.
20	NAYAK N G， DÜRR F， ROTHERMEL K. Incremental flow scheduling and routing in time-sensitive software-defined networks［J］. IEEE Transactions on Industrial Informatics， 2018， 14（5）： 2066-2075.
21	ZHANG S Q， LI Z H， WANG N C， et al. An offline equivalence scheduling technique for time-triggered Ethernet［C］∥ Proceedings of the 6th International Conference on Communications and Broadband Networking. New York： ACM， 2018： 65-70.
22	NASRI M， BRANDENBURG B B. Offline equivalence： a non-preemptive scheduling technique for resource-constrained embedded real-time systems （outstanding paper）［C］∥ 2017 IEEE Real-Time and Embedded Technology and Applications Symposium （RTAS）. Piscataway： IEEE Press， 2017： 75-86.
23	WANG N C， YU Q H， WAN H， et al. Adaptive scheduling for multicluster time-triggered train communication networks［J］. IEEE Transactions on Industrial Informatics， 2019， 15（2）： 1120-1130.
24	GUO M， GU C J， HE S B， et al. MSS： exploiting mapping score for CQF start time planning in time-sensitive networking［J］. IEEE Transactions on Industrial Informatics， 2023， 19（2）： 2140-2150.

TT消息总数	在线调度算法求解时间/ms	SMT算法求解时间/ms	MSS算法求解时间/ms
20	1	1 412	7
50	1	3 502	28
100	3	72 821	91
200	8	1 582 670	360
500	19		2 050
1 000	37		8 342
2 000	70		34 017

调度表生成方式	调度表生成时间/ms	RC消息平均延迟/ms	RC消息最坏延迟/ms
SMT求解	72 821	0.065 9	0.127 9
在线式求解	1	0.059 4	0.105 6

[1]	LUO Zexiong, QU Guoyuan, YAN Long, TANG Xueqian. A scheduling table generation method for time-triggered flows based on importance sampling [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(3): 325209-325209.
[2]	HE Feng, LI Ershuai, ZHOU Xuan, LI Haoruo, GONG Zijie. Design optimization and evaluation method for time-triggered communication scheduling in airborne networks [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(7): 324258-324258.
[3]	KONG Yunwen, LI Qiao, XIONG Huagang, CHENG Zijing. Time-triggered communication scheduling method for off-chip integrated interconnection [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(2): 321590-321590.
[4]	ZHAO Luxi, LI Qiao, LIN Wanqing, XIONG Huagang. Stochastic network calculus for analysis of latency on TTEthernet network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2016, 37(6): 1953-1961.
[5]	ZHAO Xijing, WANG Lixin, HE Zhikun, ZHANG Bo. Reducted Twice Augmented Square-root Cubature Kalman Filter and Its Application [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2014, 35(8): 2286-2298.
[6]	YI Juan, XIONG Huagang, HE Feng, WANG Tong. Research on Traffic Classes Transformation Strategy and Real-time Guarantee Scheduling Algorithm in TTEthernet [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2014, 35(4): 1071-1078.

Online time-triggered scheduling method based on publish/subscribe architecture

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 24

Related Articles 6

Recommended Articles

Metrics

Comments