Scalable Scheduling for Industrial Time-Sensitive Networking: A Hyper-Flow Graph-Based Scheme
Authors: 
Yanzhou Zhang, Cailian Chen, Qimin Xu, Shouliang Wang, Lei Xu, Xinping GuanAuthors Info & Claims
Pages 4810 - 4825
Abstract
Industrial Time-Sensitive Networking (TSN) provides deterministic mechanisms for real-time and reliable flow transmission. Increasing attention has been paid to efficient scheduling for time-sensitive flows with stringent requirements such as ultra-low latency and jitter. In TSN, the fine-grained traffic shaping protocol, cyclic queuing and forwarding (CQF), eliminates uncertain delay and frame loss via traffic timing in and out of queues. However, it inevitably causes high scheduling complexity. Moreover, complexity is quite sensitive to flow attributes and network scale. The problem stems in part from the lack of an attribute mining mechanism in existing frame-based scheduling. For time-critical industrial networks with large-scale complex flows, a so-called hyper-flow graph based scheduling scheme is proposed to improve the scheduling scalability in terms of schedulability, scheduling efficiency and latency & jitter. The hyper-flow graph is built by aggregating similar flow sets as hyper-flow nodes and designing a hierarchical scheduling framework. The flow attribute-sensitive scheduling information is embedded into the condensed maximal cliques, and reverse maps them precisely to congestion flow portions for re-scheduling. Its parallel scheduling reduces network scale induced complexity. Further, this scheme is designed in its entirety as a comprehensive scheduling algorithm GH2. It improves the three criteria of scalability along a Pareto front. Extensive simulation studies demonstrate its superiority. Notably, GH2 is verified its scheduling stability with a runtime of less than 100 ms for 1000 flows and near 1/190 of the SOTA FITS method for 3000 flows.
References
[1]
A. Nasrallah et al., “Ultra-low latency (ULL) networks: The IEEE TSN and IETF DetNet standards and related 5G ULL research,” IEEE Commun. Surveys Tuts., vol. 21, no. 1, pp. 88–145, 1st Quart., 2019.
[2]
M. Wollschlaeger, T. Sauter, and J. Jasperneite, “The future of industrial communication: Automation networks in the era of the Internet of Things and Industry 4.0,” IEEE Ind. Electron. Mag., vol. 11, no. 1, pp. 17–27, Mar. 2017.
[3]
IEEE Standard for Local and Metropolitan Area Networks—Bridges and Bridged Networks—Amendment 25: Enhancements for Scheduled Traffic, IEEE Standard, 2015, pp. 1–57.
[4]
IEEE Standard for Local and Metropolitan Area Networks—Bridges and Bridged Networks—Amendment 28: Per-Stream Filtering and Policing, IEEE Standard, 2017, pp. 1–65.
[5]
IEEE Standard for Local and Metropolitan Area Networks—Timing and Synchronization for Time-Sensitive Applications, IEEE Standard, 2020, pp. 1–421.
[6]
IEEE Standard for Local and Metropolitan Area Networks—Bridges and Bridged Networks—Amendment 29: Cyclic Queuing and Forwarding, IEEE Standard, 2017, pp. 1–30.
[7]
S. S. Craciunas, R. S. Oliver, M. Chmelík, and W. Steiner, “Scheduling real-time communication in IEEE 802.1Qbv time sensitive networks,” in Proc. 24th Int. Conf. Real-Time Netw. Syst. (RTNS), Oct. 2016, pp. 183–192.
[8]
R. Serna Oliver, S. S. Craciunas, and W. Steiner, “IEEE 802.1Qbv gate control list synthesis using array theory encoding,” in Proc. IEEE Real-Time Embedded Technol. Appl. Symp. (RTAS), Apr. 2018, pp. 13–24.
[9]
J. Falk, F. Dürr, and K. Rothermel, “Exploring practical limitations of joint routing and scheduling for TSN with ILP,” in Proc. IEEE 24th Int. Conf. Embedded Real-Time Comput. Syst. Appl. (RTCSA), Aug. 2018, pp. 136–146.
[10]
T. L. Mai, N. Navet, and J. Migge, “On the use of supervised machine learning for assessing schedulability: Application to Ethernet TSN,” in Proc. 27th Int. Conf. Real-Time Netw. Syst., Nov. 2019, pp. 143–153.
[11]
T. L. Mai, N. Navet, and J. Migge, “A hybrid machine learning and schedulability analysis method for the verification of TSN networks,” in Proc. 15th IEEE Int. Workshop Factory Commun. Syst., May 2019, pp. 1–8.
[12]
N. G. Nayak, F. Dürr, and K. Rothermel, “Incremental flow scheduling and routing in time-sensitive software-defined networks,” IEEE Trans. Ind. Informat., vol. 14, no. 5, pp. 2066–2075, May 2018.
[13]
W. Quan, J. Yan, X. Jiang, and Z. Sun, “On-line traffic scheduling optimization in IEEE 802.1Qch based time-sensitive networks,” in Proc. IEEE 22nd Int. Conf. High Perform. Comput. Commun., IEEE 18th Int. Conf. Smart City, IEEE 6th Int. Conf. Data Sci. Syst. (HPCC/SmartCity/DSS), Dec. 2020, pp. 369–376.
[14]
M. Guo, C. Gu, S. He, Z. Shi, and J. Chen, “MSS: Exploiting mapping score for CQF start time planning in time-sensitive networking,” IEEE Trans. Ind. Informat, vol. 19, no. 2, pp. 2140–2150, Feb. 2023.
[15]
L. Xu et al., “Learning-based scalable scheduling and routing co-design with stream similarity partitioning for time-sensitive networking,” IEEE Internet Things J., vol. 9, no. 15, pp. 13353–13363, Aug. 2022.
[16]
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.
[17]
D. Yang, Z. Cheng, W. Zhang, H. Zhang, and X. Shen, “Burst-aware time-triggered flow scheduling with enhanced multi-CQF in time-sensitive networks,” IEEE/ACM Trans. Netw., vol. 31, no. 6, pp. 2809–2824, Dec. 2023.
[18]
Y. Lu et al., “An intelligent deterministic scheduling method for ultralow latency communication in edge enabled industrial Internet of Things,” IEEE Trans. Ind. Informat., vol. 19, no. 2, pp. 1756–1767, Feb. 2023.
[19]
J. Lin et al., “Rethinking the use of network cycle in time-sensitive networking (TSN) flow scheduling,” in Proc. IEEE/ACM 30th Int. Symp. Quality Service (IWQoS), Jun. 2022, pp. 1–11.
[20]
Y. Zhang, Q. Xu, L. Xu, C. Chen, and X. Guan, “Efficient flow scheduling for industrial time-sensitive networking: A divisibility theory-based method,” IEEE Trans. Ind. Informat., vol. 18, no. 12, pp. 9312–9323, Dec. 2022.
[21]
J. Yan, W. Quan, X. Jiang, and Z. Sun, “Injection time planning: Making CQF practical in time-sensitive networking,” in Proc. IEEE INFOCOM Conf. Comput. Commun., Jul. 2020, pp. 616–625.
[22]
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 Proc. IEEE Global Commun. Conf., Dec. 2022, pp. 413–418.
[23]
Z. Li et al., “An enhanced reconfiguration for deterministic transmission in time-triggered networks,” IEEE/ACM Trans. Netw., vol. 27, no. 3, pp. 1124–1137, Jun. 2019.
[24]
IEEE Standard for Local and Metropolitan Area Networks—Bridges and Bridged Networks—Amendment 31: Stream Reservation Protocol (SRP) Enhancements and Performance Improvements, IEEE Standard, 2018, pp. 1–208.
[25]
Use Cases IEC/IEEE 60802. (2024). IEC/IEEE 60802 TSN Profile for Industrial Automation. [Online]. Available: https://1.ieee802.org/tsn/iec-ieee-60802/
[26]
E. Tomita, A. Tanaka, and H. Takahashi, “The worst-case time complexity for generating all maximal cliques and computational experiments,” Theor. Comput. Sci., vol. 363, no. 1, pp. 28–42, Oct. 2006.
[27]
D. Eppstein, M. Löffler, and D. Strash, “Listing all maximal cliques in large sparse real-world graphs,” ACM J. Experim. Algorithmics, vol. 18, pp. 3.1–3.21, Nov. 2013.
[28]
R. Mahfouzi, A. Aminifar, S. Samii, A. Rezine, P. Eles, and Z. Peng, “Stability-aware integrated routing and scheduling for control applications in Ethernet networks,” in Proc. Design, Autom. Test Eur. Conf. Exhib. (DATE), Mar. 2018, pp. 682–687.
Index Terms
- Scalable Scheduling for Industrial Time-Sensitive Networking: A Hyper-Flow Graph-Based Scheme
Index terms have been assigned to the content through auto-classification.
Recommendations
Enhanced Real-time Scheduling of AVB Flows in Time-Sensitive Networking
Time-Sensitive Networking (TSN) realizes high bandwidth and time determinism for data transmission and thus becomes the crucial communication technology in time-critical systems. The Gate Control List (GCL) is used to control the transmission of different ...
An efficient scheduling approach for multi-level industrial chain flows in time-sensitive networking
AbstractTime-sensitive networking (TSN) is a promising real-time network technology that has deterministic delay and jitter guarantee capabilities. However, TSN flow scheduling faces challenges in the multi-level topology due to the cooperative ...
A low-delay AVB flow scheduling method occupying the guard band in Time-Sensitive Networking
AbstractTime-Sensitive Networking (TSN) is used in time-critical systems because of its high-bandwidth and time determinization. To ensure the deterministic transmission of Time-Triggered (TT) flows, TSN adopts the guard band mechanism to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1063-6692 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 August 2024
Published in TON Volume 32, Issue 6
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 3Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)3
Reflects downloads up to 29 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in