Mohammadreza Barzegaran
Silviu S. Craciunas
ABSTRACT
Time-Sensitive Networks (TSN) enhance standard IEEE 802.1Q Ethernet devices with real-time and time-aware capabilities. The forwarding of time-critical frames is done according to a so-called Gate Control List (GCL) schedule via the timed-gate mechanism introduced in IEEE 802.1Qbv. Most TSN scheduling mechanisms impose that all devices in the network must have the TSN capabilities related to scheduled gates and time synchronization. However, this is often an unrealistic assumption since many distributed applications use heterogeneous TSN networks with legacy or off-the-shelf end systems that are unscheduled and/or unsynchronized.
This paper proposes a novel, more flexible TSN scheduling algorithm that intertwines a worst-case delay analysis within the scheduling synthesis step. Through this, we leverage the solution’s optimality to support heterogeneous TSN networks featuring unscheduled and/or unsynchronized end-systems while still guaranteeing the timeliness of critical communication. We evaluate the performance of our approach using both synthetic and real-world use cases, comparing it with existing TSN scheduling mechanisms. Furthermore, we use OMNET++ to validate the generated GCL schedules.
- Mohammad Ashjaei, Lucia Lo Bello, Masoud Daneshtalab, Gaetano Patti, Sergio Saponara, and Saad Mubeen. 2021. Time-Sensitive Networking in automotive embedded systems: State of the art and research opportunities. JSA 117(2021), 102137. https://doi.org/10.1016/j.sysarc.2021.102137Google Scholar
Digital Library
- Mohammadreza Barzegaran, Niklas Reusch, Luxi Zhao, Silviu S. Craciunas, and Paul Pop. 2021. Real-Time Guarantees for Critical Traffic in IEEE 802.1Qbv TSN Networks with Unscheduled and Unsynchronized End-Systems. CoRR abs/2105.01641(2021). https://arxiv.org/pdf/2105.01641.Google Scholar
- Mohammadreza Barzegaran, Bahram Zarrin, and Paul Pop. 2020. Quality-of-control-aware scheduling of communication in TSN-based fog computing platforms using constraint programming. In 2nd Workshop on Fog Computing and the IoT (Fog-IoT 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.Google Scholar
- M. Boyer, H. Daigmorte, N. Navet, and J. Migge. 2016. Performance impact of the interactions between time-triggered and rate-constrained transmissions in TTEthernet. In Proc. ERTS.Google Scholar
- E. K. Burke, G. Kendall, 2005. Search methodologies. Springer.Google Scholar
- Martin Böhm and Diederich Wermser. 2021. Multi-Domain Time-Sensitive Networks—Control Plane Mechanisms for Dynamic Inter-Domain Stream Configuration. Electronics 10, 20 (2021). https://doi.org/10.3390/electronics10202477Google Scholar
- Silviu S. Craciunas and Ramon Serna Oliver. 2016. Combined Task- and Network-level Scheduling for Distributed Time-Triggered Systems. Journal of Real-Time Systems 52, 2 (2016), 161–200.Google ScholarDigital Library
- S. S. Craciunas and R. Serna Oliver. 2017. An Overview of Scheduling Mechanisms for Time-sensitive Networks. Technical report, Real-time summer school L’École d’Été Temps Réel (ETR).Google Scholar
- S. S. Craciunas, R. Serna Oliver, M. Chmelik, and W. Steiner. 2016. Scheduling Real-Time Communication in IEEE 802.1Qbv Time Sensitive Networks. In Proc. RTNS. 183–192.Google Scholar
- J. A. R. De Azua and M. Boyer. 2014. Complete Modelling of AVB in Network Calculus Framework. In Proc. RTNS. 55–64.Google Scholar
- J. Diemer, D. Thiele, and R. Ernst. 2012. Formal worst-case timing analysis of Ethernet topologies with strict-priority and AVB switching. In Proc. SIES. 1–10.Google Scholar
- Aellison Cassimiro T. dos Santos, Ben Schneider, and Vivek Nigam. 2019. TSNSCHED: Automated Schedule Generation for Time Sensitive Networking. In Proc. FMCAD. https://doi.org/10.23919/FMCAD.2019.8894249Google ScholarCross Ref
- F. Dürr and N. G. Nayak. 2016. No-wait Packet Scheduling for IEEE Time-sensitive Networks (TSN). In Proc. RTNS. ACM.Google ScholarDigital Library
- Jonathan Falk, Frank Dürr, and Kurt Rothermel. 2018. Exploring Practical Limitations of Joint Routing and Scheduling for TSN with ILP. In Proc. RTCSA.Google ScholarCross Ref
- J. Falk, D. Hellmanns, B. Carabelli, N. Nayak, F. Dürr, S. Kehrer, and K. Rothermel. 2019. NeSTiNg: Simulating IEEE Time-sensitive Networking (TSN) in OMNeT++. In Proc. NetSys. 1–8.Google Scholar
- V. Gavrilut, B. Zarrin, P. Pop, and S. Samii. 2017. Fault-Tolerant Topology and Routing Synthesis for IEEE Time-Sensitive Networking. In Proc. RTNS. ACM.Google Scholar
- Google. Accessed on Oct 2020. Google OR-Tools. https://developers.google.com/optimization.Google Scholar
- F. Heilmann and G. Fohler. 2019. Size-Based Queuing: An Approach to Improve Bandwidth Utilization in TSN Networks. SIGBED Rev. 16, 1 (2019), 9–14.Google ScholarDigital Library
- D. Hellmanns, J. Falk, A. Glavackij, R. Hummen, S. Kehrer, and F. Dürr. 2020. On the Performance of Stream-based, Class-based Time-aware Shaping and Frame Preemption in TSN. In Proc. ICIT. 298–303.Google Scholar
- D. Hellmanns, A. Glavackij, J. Falk, F. Duerr, R. Hummen, and S. Kehrer. 2020. Scaling TSN Scheduling for Factory Automation Networks. In Proc. WFCS. 1–8.Google Scholar
- 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.10.2020.Google Scholar
- Institute of Electrical and Electronics Engineers, Inc. 2016. 802.1Qbv - Enhancements for Scheduled Traffic. http://www.ieee802.org/1/pages/802.1bv.html. Draft 3.1, Accessed: 23.10.2020.Google Scholar
- Institute of Electrical and Electronics Engineers, Inc. 2016. Official Website of the 802.1 Time-Sensitive Networking Task Group. http://www.ieee802.org/1/pages/tsn.html. Accessed: 23.10.2020.Google Scholar
- 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.10.2020.Google Scholar
- Issuing Committee: As-2d2 Deterministic Ethernet And Unified Networking. 2011. SAE AS6802 Time-Triggered Ethernet. http://standards.sae.org/as6802/. Accessed: 23.10.2020.Google Scholar
- D. D. Khanh and A. Mifdaoui. 2014. Timing Analysis of TDMA-based Networks using Network Calculus and Integer Linear Programming. In Proc. MASCOTS. 21–30.Google Scholar
- Ana Larrañaga, M. Carmen Lucas-Estañ, Imanol Martinez, Iñaki Val, and Javier Gozalvez. 2020. Analysis of 5G-TSN Integration to Support Industry 4.0. In Proc. ETFA. https://doi.org/10.1109/ETFA46521.2020.9212141Google ScholarCross Ref
- Rouhollah Mahfouzi, Amir Aminifar, Soheil Samii, Ahmed Rezine, Petru Eles, and Zebo Peng. 2018. Stability-aware integrated routing and scheduling for control applications in Ethernet networks. In Proc. DATE.Google ScholarCross Ref
- Daniel Bujosa Mateu, Mohammad Ashjaei, Alessandro V. Papadopoulos, Julian Proenza, and Thomas Nolte. 2021. LETRA: Mapping Legacy Ethernet-Based Traffic into TSN Traffic Classes. In Proc. ETFA. https://doi.org/10.1109/ETFA45728.2021.9613637Google ScholarDigital Library
- N. G. Nayak, F. Dürr, and K. Rothermel. 2018. Incremental Flow Scheduling and Routing in Time-Sensitive Software-Defined Networks. IEEE Trans Industr Inform 14, 5 (2018).Google Scholar
- Maryam Pahlevan and Roman Obermaisser. 2018. Genetic Algorithm for Scheduling Time-Triggered Traffic in Time-Sensitive Networks. In Proc. ETFA. https://doi.org/10.1109/ETFA.2018.8502515Google ScholarDigital Library
- Maryam Pahlevan, Nadra Tabassam, and Roman Obermaisser. 2019. Heuristic List Scheduler for Time Triggered Traffic in Time Sensitive Networks. SIGBED Rev. 16, 1 (2019), 15–20.Google ScholarDigital Library
- P. Pop, M. L. Raagaard, S. S. Craciunas, and W. Steiner. 2016. Design Optimization of Cyber-Physical Distributed Systems using IEEE Time-Sensitive Networks (TSN). IET Cyber-Physical Systems: Theory and Applications 1, 1(2016), 86–94.Google ScholarCross Ref
- N. Reusch, L. Zhao, S. S. Craciunas, and P. Pop. 2020. Window-Based Schedule Synthesis for Industrial IEEE 802.1Qbv TSN Networks. In Proc. WFCS.Google Scholar
- J. Schmitt, P. Hurley, M. Hollick, and R. Steinmetz. 2003. Per-flow guarantees under class-based priority queueing. In IEEE Global Telecommunications Conference. 4169–4174.Google Scholar
- Sebastian Schriegel, Thomas Kobzan, and Jürgen Jasperneite. 2018. Investigation on a distributed SDN control plane architecture for heterogeneous time sensitive networks. In Proc. WFCS. https://doi.org/10.1109/WFCS.2018.8402356Google ScholarCross Ref
- R. Serna Oliver, S. S. Craciunas, and W. Steiner. 2018. IEEE 802.1Qbv Gate Control List Synthesis using Array Theory Encoding. In Proc. RTAS.Google Scholar
- Khaled M. Shalghum, Nor Kamariah Noordin, Aduwati Sali, and Fazirulhisyam Hashim. 2021. Network Calculus-Based Latency for Time-Triggered Traffic under Flexible Window-Overlapping Scheduling (FWOS) in a Time-Sensitive Network (TSN). Applied Sciences 11, 9 (2021).Google ScholarCross Ref
- O. Sinnen. 2007. Task scheduling for parallel systems. Vol. 60. John Wiley & Sons.Google Scholar
- Wilfried Steiner. 2010. An Evaluation of SMT-based Schedule Synthesis For Time-Triggered Multi-Hop Networks. In Proc. RTSS. IEEE.Google ScholarDigital Library
- W. Steiner, G. Bauer, B. Hall, and M. Paulitsch. 2011. TTEthernet: Time-Triggered Ethernet. In Time-Triggered Communication, Roman Obermaisser (Ed.). CRC Press.Google Scholar
- Marek Vlk, Kateřina Brejchová, Zdeněk Hanzálek, and Siyu Tang. 2022. Large-scale periodic scheduling in time-sensitive networks. Computers & Operations Research 137 (2022), 105512. https://doi.org/10.1016/j.cor.2021.105512Google ScholarDigital Library
- M. Vlk, Z. Hanzálek, K. Brejchová, S. Tang, S. Bhattacharjee, and S. Fu. 2020. Enhancing Schedulability and Throughput of Time-Triggered Traffic in IEEE 802.1Qbv Time-Sensitive Networks. IEEE Transactions on Communications 68, 11 (2020), 7023–7038.Google ScholarCross Ref
- Marek Vlk, Zdeněk Hanzálek, and Siyu Tang. 2021. Constraint programming approaches to joint routing and scheduling in time-sensitive networks. Computers & Industrial Engineering 157 (2021), 107317. https://doi.org/10.1016/j.cie.2021.107317Google ScholarCross Ref
- Christian von Arnim, Mihai Drǎgan, Florian Frick, Armin Lechler, Oliver Riedel, and Alexander Verl. 2020. TSN-based Converged Industrial Networks: Evolutionary Steps and Migration Paths. In Proc. ETFA, Vol. 1. 294–301. https://doi.org/10.1109/ETFA46521.2020.9212057Google ScholarCross Ref
- E. Wandeler. 2006. Modular performance analysis and interface-based design for embedded real-time systems. Shaker.Google Scholar
- E. Wandeler and L. Thiele. 2006. Optimal TDMA time slot and cycle length allocation for hard real-time systems. In Proc. ASP-DAC.Google Scholar
- E. Wandeler and L. Thiele. 2006. Real-Time Calculus (RTC) Toolbox. http://www.mpa.ethz.ch/Rtctoolbox. http://www.mpa.ethz.ch/Rtctoolbox Accessed: 23.10.2020.Google Scholar
- L. Zhao, P. Pop, and S. S. Craciunas. 2018. Worst-Case Latency Analysis for IEEE 802.1Qbv Time Sensitive Networks Using Network Calculus. IEEE Access 6(2018), 41803–41815. https://doi.org/10.1109/ACCESS.2018.2858767Google ScholarCross Ref
- L. Zhao, P. Pop, Z. J. Gong, and B. W. Fang. 2020, Early Access Article. Improving Latency Analysis for Flexible Window-Based GCL Scheduling in TSN Networks by Integration of Consecutive Nodes Offsets. IEEE Internet of Things(2020, Early Access Article). https://doi.org/10.1109/JIOT.2020.3031932Google Scholar
- L. Zhao, P. Pop, Q. Li, J. Chen, and H. Xiong. 2017. Timing analysis of rate-constrained traffic in TTEthernet using network calculus. Real-Time Systems 52, 2 (2017), 254–287.Google ScholarDigital Library
- Luxi Zhao, Paul Pop, and Sebastian Steinhorst. 2017. Quantitative Performance Comparison of Various Traffic Shapers in Time-Sensitive Networking. CoRR abs/2103.13424(2017). arxiv:2103.13424https://arxiv.org/abs/2103.13424.Google Scholar
- L. X. Zhao, H. G. Xiong, Z. Zheng, and Q. Li. 2014. Improving worst-case latency analysis for rate-constrained traffic in the Time-Triggered Ethernet network. IEEE Communications Letters 18, 11 (2014), 1927–1930.Google ScholarCross Ref
- Yuanbin Zhou, Soheil Samii, Petru Eles, and Zebo Peng. 2021. ASIL-Decomposition Based Routing and Scheduling in Safety-Critical Time-Sensitive Networking. In Proc. RTAS. https://doi.org/10.1109/RTAS52030.2021.00023Google ScholarCross Ref
- Yuanbin Zhou, Soheil Samii, Petru Eles, and Zebo Peng. 2021. Reliability-Aware Scheduling and Routing for Messages in Time-Sensitive Networking. ACM Trans. Embed. Comput. Syst. 20, 5, Article 41(2021), 24 pages. https://doi.org/10.1145/3458768Google ScholarDigital Library
Recommendations
AVB-aware Routing and Scheduling for Critical Traffic in Time-sensitive Networks with Preemption
RTNS '22: Proceedings of the 30th International Conference on Real-Time Networks and SystemsThe Time-Sensitive Network (TSN) amendments and protocols add capabilities on top of standard 802.1 Ethernet for guaranteeing the timeliness of both (isochronous) scheduled traffic (ST) and shaped (audio-video) communication (AVB) in distributed ...
Guarantees for runnable entities with heterogeneous real-time requirements
DATE '16: Proceedings of the 2016 Conference on Design, Automation & Test in EuropeClassical real-time (RT) analysis proves temporal properties of tasks. In industrial practice, however, tasks are often composed of runnable entities with heterogeneous RT requirements. If RT guarantees are only available at task granularity, the ...
Weakly-Hard Real-Time Guarantees for Weighted Round-Robin Scheduling of Real-Time Messages
2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA)Communication resources often exist in distributed real-time systems, therefore, providing guarantees on a predefined end-to-end deadline requires a timing analysis of the communication resource. Worst-case response time analysis techniques for ...
Comments