Top

Real-Time Systems

Published in:

23-11-2023

Configuration optimization for heterogeneous time-sensitive networks

Authors: Niklas Reusch, Mohammadreza Barzegaran, Luxi Zhao, Silviu S. Craciunas, Paul Pop

Published in: Real-Time Systems | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Time-Sensitive Networking (TSN) collectively defines a set of protocols and standard amendments that enhance IEEE 802.1Q Ethernet nodes with time-aware and fault-tolerant capabilities. Specifically, the IEEE 802.1Qbv amendment defines a timed-gate mechanism that governs the real-time transmission of critical traffic via a so-called Gate Control List (GCL) schedule encoded in each TSN-capable network device. Most TSN scheduling mechanisms are designed for homogeneous TSN networks in which all network devices must have at least the TSN capabilities related to scheduled gates and time synchronization. However, this assumption is often unrealistic since many distributed applications use heterogeneous TSN networks with legacy or off-the-shelf end systems that are unscheduled and/or unsynchronized. We propose a new scheduling paradigm for heterogeneous TSN networks that intertwines a network calculus worst-case interference analysis within the scheduling step. Through this, we compromise on the solution’s optimality to be able to support heterogeneous TSN networks featuring unscheduled and/or unsynchronized end-systems while guaranteeing the real-time properties of critical communication. Within this new paradigm, we propose two solutions to solve the problem, one based on a Constraint Programming formulation and one based on a Simulated Annealing metaheuristic, that provide different trade-offs and scalability properties. We compare and evaluate our flexible window-based scheduling methods using both synthetic and real-world test cases, validating the correctness and scalability of our implementation. Furthermore, we use OMNET++ to validate the generated GCL schedules.

previous article A formal framework to design and prove trustworthy memory controllers

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Note that (Craciunas et al. 2016; Serna Oliver et al. 2018; Pop et al. 2016) cannot be used in our context because they require scheduled and synchronized ESs.

You can find CPWO on GitHub at https://github.com/rezabarzegaran/TSN.

Ashjaei M, Lo Bello L, Daneshtalab M, Patti G, Saponara S, Mubeen S (2021) Time-sensitive networking in automotive embedded systems: state of the art and research opportunities. JSA 117:102137. https://doi.org/10.1016/j.sysarc.2021.102137CrossRef

Barzegaran M, Reusch N, Zhao L, Craciunas SS, Pop P (2022) Real-time traffic guarantees in heterogeneous time-sensitive networks. In: Proceedings of RTNS. ACM, New York, pp 46–57. https://doi.org/10.1145/3534879.3534921

Berisa A, Zhao L, Craciunas SS, Ashjaei M, Mubeen S, Daneshtalab M, Sjödin M (2022) AVB-aware routing and scheduling for critical traffic in time-sensitive networks with preemption. In: Proceedings of RTNS. ACM, New York

Böhm M, Wermser D (2021) Multi-domain time-sensitive networks-control plane mechanisms for dynamic inter-domain stream configuration. Electronics. https://doi.org/10.3390/electronics10202477CrossRef

Boyer M, Daigmorte H, Navet N, Migge J (2016) Performance impact of the interactions between time-triggered and rate-constrained transmissions in TTEthernet. In: Proceedings of ERTS

Burke EK, Kendall G (eds) (2014) Search methodologies, 2nd edn. Springer, New York

Campelo F, Aranha C (2023) Lessons from the evolutionary computation bestiary. Artif Life. https://doi.org/10.1162/artl_a_00402CrossRef

Craciunas SS, Serna Oliver R (2016) Combined task- and network-level scheduling for distributed time-triggered systems. J Real Time Syst 52(2):161–200CrossRef

Craciunas SS, Serna Oliver R (2017) An overview of scheduling mechanisms for time-sensitive networks. Technical report, Real-time Summer School, L’École d’Été Temps Réel (ETR)

Craciunas SS, Serna Oliver R, Chmelik M, Steiner W (2016) Scheduling real-time communication in IEEE 802.1Qbv Time Sensitive Networks. In: Proceedings of RTNS, pp 183–192

De Azua JAR, Boyer M (2014) Complete modelling of AVB in network calculus framework. In: Proceedings of RTNS, pp 55–64

Diemer J, Thiele D, Ernst R (2012) Formal worst-case timing analysis of ethernet topologies with strict-priority and AVB switching. In: Proceedings of SIES, pp 1–10

Dürr F, Nayak NG (2016) No-wait packet scheduling for IEEE Time-sensitive Networks (TSN). In: Proceedings of the 24th international conference on real-time networks and systems, pp 203–212. https://doi.org/10.1145/2997465.2997494

Falk J, Dürr F, Rothermel K (2018) Exploring practical limitations of joint routing and scheduling for TSN with ILP. In: Proceedings of RTCSA

Falk J, Hellmanns D, Carabelli B, Nayak N, Dürr F, Kehrer S, Rothermel K (2019) NeSTiNg: simulating IEEE time-sensitive networking (TSN) in OMNeT++. In: Proceedings of NetSys, pp 1–8

Gavrilut V, Zarrin B, Pop P, Samii S (2017) Fault-tolerant topology and routing synthesis for IEEE time-sensitive networking. In: Proceedings of RTNS. ACM, New York

Google (2020) Google OR-Tools. https://developers.google.com/optimization. Accessed Oct 2020

Heilmann F, Fohler G (2019) Size-based queuing: an approach to improve bandwidth utilization in TSN networks. SIGBED Rev 16(1):9–14CrossRef

Hellmanns D, Falk J, Glavackij A, Hummen R, Kehrer S, Dürr F (2020a) On the performance of stream-based, class-based time-aware shaping and frame preemption in TSN. In: Proceedings of ICIT, pp 298–303

Hellmanns D, Glavackij A, Falk J, Duerr F, Hummen R, Kehrer S (2020b) Scaling TSN scheduling for factory automation networks. In: Proceedings of WFCS, pp 1–8

Institute of Electrical and Electronics Engineers, Inc (2011) 802.1BA-Audio Video Bridging (AVB) systems. http://www.ieee802.org/1/pages/802:1ba.html. Accessed 23 Oct 2020

Institute of Electrical and Electronics Engineers, Inc (2016a) 802.1Qbv - Enhancements for scheduled traffic. Draft 3.1. http://www.ieee802.org/1/pages/802.1bv.html. Accessed 23 Oct 2020

Institute of Electrical and Electronics Engineers, Inc (2016b) Official Website of the 802.1 Time-Sensitive Networking Task Group. http://www.ieee802.org/1/pages/tsn.html. Accessed 23 Oct 2020

Institute of Electrical and Electronics Engineers, Inc (2017) 802.1AS-Rev—timing and synchronization for time-sensitive applications. http://www.ieee802.org/1/pages/802.1AS-rev.html. Accessed 23 Oct 2020

Issuing Committee (2011) As-2d2 deterministic ethernet and unified networking: SAE AS6802 time-triggered ethernet. http://standards.sae.org/as6802/. Accessed 23 Oct 2020

Jean-Yves LB, Patrick T (2001) Network calculus: a theory of deterministic queuing systems for the Internet. Real Time Systems, vol 51. Springer, Berlin

Khanh DD, Mifdaoui A (2014) Timing analysis of TDMA-based networks using network calculus and integer linear programming. In: Proceedings of MASCOTS, pp 21–30

Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680MathSciNetCrossRef

Kramer S, Ziegenbein D, Hamann A (2015) Real world automotive benchmarks for free. In: Proceedings of WATERS

Larrañaga A, Lucas-Estañ MC, Martinez I, Val I, Gozalvez J (2020) Analysis of 5G-TSN integration to support industry 4.0. In: Proceedings of ETFA. https://doi.org/10.1109/ETFA46521.2020.9212141

Luteberget B, Claessen K, Johansen C, Steffen M (2021) SAT modulo discrete event simulation applied to railway design capacity analysis. Formal Methods Syst Des 57(2):211–245. https://doi.org/10.1007/s10703-021-00368-2CrossRef

Mahfouzi R, Aminifar A, Samii S, Rezine A, Eles P, Peng Z (2018) Stability-aware integrated routing and scheduling for control applications in ethernet networks. In: Proceedings of DATE

Mateu DB, Ashjaei M, Papadopoulos AV, Proenza J, Nolte T (2021) LETRA: mapping legacy ethernet-based traffic into TSN traffic classes. In: Proceedings of ETFA. https://doi.org/10.1109/ETFA45728.2021.9613637

Nayak NG, Dürr F, Rothermel K (2018) Incremental flow scheduling and routing in time-sensitive software-defined networks. IEEE Trans Ind Inform 14(5):2066–2075CrossRef

Pahlevan M, Obermaisser R (2018) Genetic algorithm for scheduling time-triggered traffic in time-sensitive networks. In: Proceedings of ETFA. https://doi.org/10.1109/ETFA.2018.8502515

Pahlevan M, Tabassam N, Obermaisser R (2019) Heuristic list scheduler for time triggered traffic in time sensitive networks. SIGBED Rev 16(1):15–20CrossRef

Pop P, Lander Raagaard M, Craciunas SS, Steiner W (2016) Design optimization of cyber-physical distributed systems using IEEE time-sensitive networks (TSN). IET Cyber-Phys Syst Theory Appl 1(1):86–94CrossRef

Reusch N, Zhao L, Craciunas SS, Pop P (2020) Window-based schedule synthesis for industrial IEEE 802.1Qbv TSN networks. In: Proceedings of WFCS

Schmitt J, Hurley P, Hollick M, Steinmetz R (2003) Per-flow guarantees under class-based priority queueing. In: IEEE global telecommunications conference, pp 4169–4174

Schriegel S, Kobzan T, Jasperneite J (2018) Investigation on a distributed sdn control plane architecture for heterogeneous time sensitive networks. In: Proceedings of WFCS. https://doi.org/10.1109/WFCS.2018.8402356

Serna Oliver R, Craciunas SS, Steiner W (2018) IEEE 802.1Qbv gate control list synthesis using array theory encoding. In: Proceedings of RTAS

Shalghum KM, Noordin NK, Sali A, Hashim F (2021) Network calculus-based latency for time-triggered traffic under flexible window-overlapping scheduling (FWOS) in a time-sensitive network (TSN). Appl Sci 11(9):3896

Sinnen O (2007) Task scheduling for parallel systems, vol 60. Wiley, HobokenCrossRef

Steiner W (2010) An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks. In: Proceedings of RTSS. IEEE, USA

Steiner W, Bauer G, Hall B, Paulitsch M (2011) TTEthernet: time-triggered ethernet. In: Obermaisser R (ed) Time-triggered communication. CRC Press, Boca Raton

Vlk M, Hanzálek Z, Brejchová K, Tang S, Bhattacharjee S, Fu S (2020) Enhancing schedulability and throughput of time-triggered traffic in IEEE 802.1Qbv time-sensitive networks. IEEE Trans Commun 68(11):7023–7038CrossRef

Vlk M, Hanzálek Z, Tang S (2021) Constraint programming approaches to joint routing and scheduling in time-sensitive networks. Comput Ind Eng 157:107317. https://doi.org/10.1016/j.cie.2021.107317CrossRef

Vlk M, Brejchová K, Hanzálek Z, Tang S (2022) Large-scale periodic scheduling in time-sensitive networks. Comput Oper Res 137:105512. https://doi.org/10.1016/j.cor.2021.105512MathSciNetCrossRef

Voß S, Woodruff DL (2002) Optimization software class libraries. Springer, BostonCrossRef

von Arnim C, Drǎgan M, Frick F, Lechler A, Riedel O, Verl A (2020) Tsn-based converged industrial networks: evolutionary steps and migration paths. In: Proceedings of ETFA, vol 1, pp 294–301. https://doi.org/10.1109/ETFA46521.2020.9212057

Wandeler E (2006) Modular performance analysis and interface-based design for embedded real-time systems. Shaker, Düren

Wandeler E, Thiele L (2006a) Optimal TDMA time slot and cycle length allocation for hard real-time systems. In: Proceedings of ASP-DAC

Wandeler E, Thiele L (2006b) Real-Time Calculus (RTC) Toolbox. http://www.mpa.ethz.ch/Rtctoolbox. Accessed 23 Oct 2020

Zhao LX, Xiong HG, Zheng Z, Li Q (2014) Improving worst-case latency analysis for rate-constrained traffic in the Time-Triggered Ethernet network. IEEE Commun Lett 18(11):1927–1930CrossRef

Zhao L, Pop P, Li Q, Chen J, Xiong H (2017) Timing analysis of rate-constrained traffic in TTEthernet using network calculus. Real Time Syst 52(2):254–287CrossRef

Zhao L, Pop P, Craciunas SS (2018) Worst-case latency analysis for IEEE 802.1Qbv time sensitive networks using network calculus. IEEE Access 6:41803–41815. https://doi.org/10.1109/ACCESS.2018.2858767CrossRef

Zhao L, Pop P, Gong ZJ, Fang BW (2020) Improving latency analysis for flexible window-based GCL scheduling in TSN networks by integration of consecutive nodes offsets. IEEE Internet Things. https://doi.org/10.1109/JIOT.2020.3031932)

Zhao L, Pop P, Steinhorst S (2017) Quantitative performance comparison of various traffic shapers in time-sensitive networking. CoRR. arXiv:abs/2103.13424

Zhou Y, Samii S, Eles P, Peng Z (2021a) Asil-decomposition based routing and scheduling in safety-critical time-sensitive networking. In: Proceedings of RTAS. https://doi.org/10.1109/RTAS52030.2021.00023

Zhou Y, Samii S, Eles P, Peng Z (2021b) Reliability-aware scheduling and routing for messages in time-sensitive networking. ACM Trans Embed Comput Syst. https://doi.org/10.1145/3458768CrossRef

Title: Configuration optimization for heterogeneous time-sensitive networks
Authors: Niklas Reusch
Mohammadreza Barzegaran
Luxi Zhao
Silviu S. Craciunas
Paul Pop
Publication date: 23-11-2023
Publisher: Springer US
Published in: Real-Time Systems / Issue 4/2023
Print ISSN: 0922-6443
Electronic ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-023-09414-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2023

Time-sensitive autonomous architectures

Evaluating virtualization for fog monitoring of real-time applications in mixed-criticality systems

A formal framework to design and prove trustworthy memory controllers

Supporting AI-powered real-time cyber-physical systems on heterogeneous platforms via hypervisor technology

A real-time vital control module to increase capabilities of railway control systems in highly automated train operations

Special issue on embedded real-time applications

Premium Partner