Improved Heuristic Joint Routing and Scheduling in Time-Sensitive Networking
DOI: 10.23977/cpcs.2024.080109 | Downloads: 8 | Views: 262
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 ChuangABSTRACT
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 strategyCITE 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.
Downloads: | 2622 |
---|---|
Visits: | 127718 |
Sponsors, Associates, and Links
-
Power Systems Computation
-
Internet of Things (IoT) and Engineering Applications
-
Journal of Artificial Intelligence Practice
-
Advances in Computer, Signals and Systems
-
Journal of Network Computing and Applications
-
Journal of Web Systems and Applications
-
Journal of Electrotechnology, Electrical Engineering and Management
-
Journal of Wireless Sensors and Sensor Networks
-
Journal of Image Processing Theory and Applications
-
Mobile Computing and Networking
-
Vehicle Power and Propulsion
-
Frontiers in Computer Vision and Pattern Recognition
-
Knowledge Discovery and Data Mining Letters
-
Big Data Analysis and Cloud Computing
-
Electrical Insulation and Dielectrics
-
Crypto and Information Security
-
Journal of Neural Information Processing
-
Collaborative and Social Computing
-
International Journal of Network and Communication Technology
-
File and Storage Technologies
-
Frontiers in Genetic and Evolutionary Computation
-
Optical Network Design and Modeling
-
Journal of Virtual Reality and Artificial Intelligence
-
Natural Language Processing and Speech Recognition
-
Journal of High-Voltage
-
Programming Languages and Operating Systems
-
Visual Communications and Image Processing
-
Journal of Systems Analysis and Integration
-
Knowledge Representation and Automated Reasoning
-
Review of Information Display Techniques
-
Data and Knowledge Engineering
-
Journal of Database Systems
-
Journal of Cluster and Grid Computing
-
Cloud and Service-Oriented Computing
-
Journal of Networking, Architecture and Storage
-
Journal of Software Engineering and Metrics
-
Visualization Techniques
-
Journal of Parallel and Distributed Processing
-
Journal of Modeling, Analysis and Simulation
-
Journal of Privacy, Trust and Security
-
Journal of Cognitive Informatics and Cognitive Computing
-
Lecture Notes on Wireless Networks and Communications
-
International Journal of Computer and Communications Security
-
Journal of Multimedia Techniques
-
Automation and Machine Learning
-
Computational Linguistics Letters
-
Journal of Computer Architecture and Design
-
Journal of Ubiquitous and Future Networks