Education, Science, Technology, Innovation and Life
Open Access
Sign In
  1. Home
  2. Journals
  3. Computing, Performance and Communication Systems
  4. Vol 8, Issue 1, 2024

Improved Heuristic Joint Routing and Scheduling in Time-Sensitive Networking

Download as PDF

DOI: 10.23977/cpcs.2024.080109 | Downloads: 5 | Views: 148

Author(s)

Li Chuang 1, Wang Zhong 1

Affiliation(s)

1 Xi'an Research Institute of High Technology, Xi'an, Shaanxi, 710025, China

Corresponding Author

Li Chuang

ABSTRACT

The joint routing and scheduling problem in Time-Sensitive Networking is a Non-deterministic Polynomial problem that can be solved using heuristic algorithms. This paper proposes an improved heuristic scheduling algorithm, optimizes its search strategy, proposes a shorter path first strategy, standardizes the solution space of the heuristic algorithm, improves the search speed of the algorithm, and carries out scenario solving experiments and compares the solving efficiency with the other five algorithms. The results show that the improved heuristic scheduling algorithm has a greater improvement in the solution efficiency, compared with the other five algorithms to improve the overall solution efficiency of more than 17%, and is more adaptable to the complex topology and task flow of the scene.

KEYWORDS

Time-Sensitive Networking; Traffic scheduling; Heuristic algorithms; Routing; Search strategy

CITE THIS PAPER

Li Chuang, Wang Zhong, Improved Heuristic Joint Routing and Scheduling in Time-Sensitive Networking. Computing, Performance and Communication Systems (2024) Vol. 8: 75-84. DOI: http://dx.doi.org/10.23977/cpcs.2024.080109.

REFERENCES

[1] Z. Tong, F. Jiaqi, M. Yanying, Q. Siyuan, and R. Fengyuan, "Survey on Traffic Scheduling in Time-Sensitive Networking," Jisuanji Yanjiu yu Fazhan, vol. 59, no. 4, pp. 747–764, 2022.
[2] T. Liu, D. He, Z. Jin, S. Shan, Y. Chen, and Q. Chen, "Research on flow scheduling of train communication based on time-sensitive network," Simul. Model. Pract. Theory, vol. 130, p. 102859, Jan. 2024, doi: 10.1016/j.simpat.2023.102859.
[3] T. Stüber, L. Osswald, S. Lindner, and M. Menth, "A Survey of Scheduling Algorithms for the Time-Aware Shaper in Time-Sensitive Networking (TSN)," Ieee Access, vol. 11, pp. 61192–61233, 2023, doi: 10.1109/ACCESS.2023.3286370.
[4] Y. Xu and J. Huang, "A Survey on Time-Sensitive Networking Standards and Applications for Intelligent Driving," Processes, vol. 11, no. 7, Art. no. 7, Jul. 2023, doi: 10.3390/pr11072211.
[5] J. Jiang, Y. Li, X. Zhang, M. Yu, C. D. Lee, and S. H. Hong, "Assessing the traffic scheduling method for time-sensitive networking (TSN) by practical implementation," Journal of Industrial Information Integration, vol. 33, p. 100464, Jun. 2023, doi: 10.1016/j.jii.2023.100464.
[6] N. G. Nayak, F. Dürr, and K. Rothermel, "Routing algorithms for IEEE802.1Qbv networks," ACM SIGBED Review, vol. 15, no. 3, pp. 13–18, Aug. 2018, doi: 10.1145/3267419.3267421.
[7] D. Hellmanns, L. Haug, M. Hildebrand, F. Dürr, S. Kehrer, and R. Hummen, "How to Optimize Joint Routing and Scheduling Models for TSN Using Integer Linear Programming," Apr. 2021. doi: 10.1145/3453417.3453421.
[8] M. Pahlevan, N. Tabassam, and R. Obermaisser, "Heuristic list scheduler for time triggered traffic in time sensitive networks," SIGBED Rev., vol. 16, no. 1, pp. 15–20, Feb. 2019, doi: 10.1145/3314206.3314208.
[9] X. Jin et al., "Real-Time Scheduling of Massive Data in Time Sensitive Networks With a Limited Number of Schedule Entries," IEEE Access, vol. 8, pp. 6751–6767, 2020, doi: 10.1109/ACCESS.2020.2964690.
[10] Y. Zhang, Q. Xu, S. Wang, Y. Chen, L. Xu, and C. Chen, "Scalable No-wait Scheduling with Flow-aware Model Conversion in Time-Sensitive Networking," in 2022 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM 2022), in IEEE Global Communications Conference. New York: IEEE, 2022, pp. 413–418. doi: 10.1109/GLOBECOM48099.2022.10001004.
[11] M. Vlk, K. Brejchová, Z. Hanzálek, and S. Tang, "Large-scale periodic scheduling in time-sensitive networks," Computers & Operations Research, vol. 137, p. 105512, Jan. 2022, doi: 10.1016/j.cor.2021.105512.
[12] D. Bujosa, M. Ashjaei, A. V. Papadopoulos, T. Nolte, and J. Proenza, "HERMES: Heuristic Multi-queue Scheduler for TSN Time-Triggered Traffic with Zero Reception Jitter Capabilities," in Proceedings of the 30th International Conference on Real-Time Networks and Systems, Paris France: ACM, Jun. 2022, pp. 70–80. doi: 10.1145/3534879. 3534906.
[13] J. Falk, F. Durr, and K. Rothermel, "Time-Triggered Traffic Planning for Data Networks with Conflict Graphs," in 2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), Sydney, NSW, Australia: IEEE, Apr. 2020, pp. 124–136. doi: 10.1109/RTAS48715.2020.00-12.
[14] A. A. Atallah, G. B. Hamad, and O. A. Mohamed, "Routing and Scheduling of Time-Triggered Traffic in Time-Sensitive Networks," Ieee Trans. Ind. Informat., vol. 16, no. 7, pp. 4525–4534, Jul. 2020, doi: 10.1109/TII.2019.2950887.
[15] C. Xue, T. Zhang, Y. Zhou, and S. Han, "Real-Time Scheduling for Time-Sensitive Networking: A Systematic Review and Experimental Study," arXiv.org, 2023, Accessed: Nov. 03, 2023. [Online]. Available: https://www. semanticscholar.org/paper/Real-Time-Scheduling-for-Time-Sensitive-Networking%3A-Xue-Zhang/450704e2188a 2138 0e46c89 cbc1c26de81581b70.

Subscription
E-Mail Alert
Most popular papers
Call for Special Issue
Publication Ethics & OA Statement
Plagiarism Policy
Contact Us
Downloads: 2433
Visits: 119909

Sponsors, Associates, and Links

All published work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright © 2016 - 2031 Clausius Scientific Press Inc. All Rights Reserved.