Skip to main content
SpringerLink
Log in

Configuration optimization for heterogeneous time-sensitive networks

  • Published:
Real-Time Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Algorithm 1
Algorithm 2
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. 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.

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

References

  • 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.102137

    Article  Google Scholar 

  • 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/electronics10202477

    Article  Google Scholar 

  • 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_00402

    Article  Google Scholar 

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

    Article  Google Scholar 

  • 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–14

    Article  Google Scholar 

  • 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–680

    Article  MathSciNet  Google Scholar 

  • 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-2

    Article  Google Scholar 

  • 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–2075

    Article  Google Scholar 

  • 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–20

    Article  Google Scholar 

  • 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–94

    Article  Google Scholar 

  • 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, Hoboken

    Book  Google Scholar 

  • 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

    Google Scholar 

  • 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–7038

    Article  Google Scholar 

  • 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.107317

    Article  Google Scholar 

  • 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.105512

    Article  MathSciNet  Google Scholar 

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

    Book  Google Scholar 

  • 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

    Google Scholar 

  • 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–1930

    Article  Google Scholar 

  • 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–287

    Article  Google Scholar 

  • 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.2858767

    Article  Google Scholar 

  • 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/3458768

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Technical University of Denmark, Kongens Lyngby, Denmark

    Niklas Reusch & Paul Pop

  2. Univerity of California Irvine, Irvine, CA, USA

    Mohammadreza Barzegaran

  3. Beihang University, Beijing, China

    Luxi Zhao

  4. TTTech Computertechnik AG, Vienna, Austria

    Silviu S. Craciunas

Authors
  1. Niklas Reusch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammadreza Barzegaran
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luxi Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Silviu S. Craciunas
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Paul Pop
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Silviu S. Craciunas.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Reusch, N., Barzegaran, M., Zhao, L. et al. Configuration optimization for heterogeneous time-sensitive networks. Real-Time Syst 59, 705–747 (2023). https://doi.org/10.1007/s11241-023-09414-0

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11241-023-09414-0

Keywords

Search

Navigation