Verifying Weakly-Hard Real-Time Properties of Traffic Streams in Switched Networks

Authors Leonie Ahrendts, Sophie Quinton, Thomas Boroske, Rolf Ernst



PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2018.15.pdf
  • Filesize: 1.04 MB
  • 22 pages

Document Identifiers

Author Details

Leonie Ahrendts
  • Institute for Network and Computer Engineering, TU Braunschweig, Braunschweig, Germany
Sophie Quinton
  • Inria Grenoble Rhône-Alpes, Montbonnot, France
Thomas Boroske
  • Institute for Network and Computer Engineering, TU Braunschweig, Braunschweig, Germany
Rolf Ernst
  • Institute for Network and Computer Engineering, TU Braunschweig, Braunschweig, Germany

Cite AsGet BibTex

Leonie Ahrendts, Sophie Quinton, Thomas Boroske, and Rolf Ernst. Verifying Weakly-Hard Real-Time Properties of Traffic Streams in Switched Networks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ECRTS.2018.15

Abstract

In this paper, we introduce the first verification method which is able to provide weakly-hard real-time guarantees for tasks and task chains in systems with multiple resources under partitioned scheduling with fixed priorities. Existing weakly-hard real-time verification techniques are restricted today to systems with a single resource. A weakly-hard real-time guarantee specifies an upper bound on the maximum number m of deadline misses of a task in a sequence of k consecutive executions. Such a guarantee is useful if a task can experience a bounded number of deadline misses without impacting the system mission. We present our verification method in the context of switched networks with traffic streams between nodes, and demonstrate its practical applicability in an automotive case study.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Embedded systems
  • Computer systems organization → Real-time systems
  • Software and its engineering → Formal software verification
  • Networks → Network performance analysis
Keywords
  • embedded and cyber-physical systems
  • weakly-hard real-time systems and networks
  • timing analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Guillem Bernat, Alan Burns, and Albert Liamosi. Weakly hard real-time systems. IEEE transactions on Computers, 50(4):308-321, 2001. Google Scholar
  2. Rainer Blind and Frank Allgöwer. Towards networked control systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process. In Decision and Control (CDC), 2015 IEEE 54th Annual Conference on, pages 7510-7515. IEEE, 2015. Google Scholar
  3. Robert I Davis, Alan Burns, Reinder J Bril, and Johan J Lukkien. Controller area network (can) schedulability analysis: Refuted, revisited and revised. Real-Time Systems, 35(3):239-272, 2007. Google Scholar
  4. Jonas Diemer, Philip Axer, and Rolf Ernst. Compositional performance analysis in python with pycpa. Proc. of WATERS, 2012. Google Scholar
  5. Jonas Diemer, Philip Axer, Daniel Thiele, and Johannes Schlatow. pyCPA. URL: https://pycpa.readthedocs.io/en/latest/index.html#.
  6. Jonas Diemer, Jonas Rox, and Rolf Ernst. Modeling of ethernet avb networks for worst-case timing analysis. IFAC Proceedings Volumes, 45(2):848-853, 2012. Google Scholar
  7. Jonas Diemer, Daniel Thiele, and Rolf Ernst. Formal worst-case timing analysis of ethernet topologies with strict-priority and avb switching. In Industrial Embedded Systems (SIES), 2012 7th IEEE International Symposium on, pages 1-10. IEEE, 2012. Google Scholar
  8. Goran Frehse, Arne Hamann, Sophie Quinton, and Matthias Woehrle. Formal analysis of timing effects on closed-loop properties of control software. In Real-Time Systems Symposium (RTSS), 2014 IEEE, pages 53-62. IEEE, 2014. Google Scholar
  9. Mongi Ben Gaid, Daniel Simon, and Olivier Sename. A design methodology for weakly-hard real-time control. IFAC Proceedings Volumes, 41(2):10258-10264, 2008. Google Scholar
  10. Zain AH Hammadeh, Sophie Quinton, and Rolf Ernst. Extending typical worst-case analysis using response-time dependencies to bound deadline misses. In Proceedings of the 14th International Conference on Embedded Software, page 10. ACM, 2014. Google Scholar
  11. Rafik Henia, Arne Hamann, Marek Jersak, Razvan Racu, Kai Richter, and Rolf Ernst. System level performance analysis-the symta/s approach. IEE Proceedings-Computers and Digital Techniques, 152(2):148-166, 2005. Google Scholar
  12. Jean-Yves Le Boudec and Patrick Thiran. Network calculus: a theory of deterministic queuing systems for the internet, volume 2050. Springer Science &Business Media, 2001. Google Scholar
  13. John P Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Real-Time Systems Symposium, 1990. Proceedings., 11th, pages 201-209. IEEE, 1990. Google Scholar
  14. Sophie Quinton, Matthias Hanke, and Rolf Ernst. Formal analysis of sporadic overload in real-time systems. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 515-520. EDA Consortium, 2012. Google Scholar
  15. Parameswaran Ramanathan. Overload management in real-time control applications using (m, k)-firm guarantee. IEEE Transactions on Parallel and Distributed Systems, 10(6):549-559, 1999. Google Scholar
  16. Kai Richter. Compositional Scheduling Analysis Using Standard Event Models. PhD thesis, TU Braunschweig, IDA, 2005. Google Scholar
  17. Simon Schliecker, Jonas Rox, Matthias Ivers, and Rolf Ernst. Providing accurate event models for the analysis of heterogeneous multiprocessor systems. In Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis, pages 185-190. ACM, 2008. Google Scholar
  18. Simon Schliecker, Jonas Rox, Matthias Ivers, and Rolf Ernst. Providing accurate event models for the analysis of heterogeneous multiprocessor systems. In Intern. Conference on HW/SW Codesign and System Synthesis. Proceedings, pages 185-190, New York, 2008. ACM. Google Scholar
  19. Youcheng Sun and Marco Di Natale. Weakly hard schedulability analysis for fixed priority scheduling of periodic real-time tasks. ACM Transactions on Embedded Computing Systems (TECS), 16(5s):171, 2017. Google Scholar
  20. Daniel Thiele, Philip Axer, Rolf Ernst, and Jan R Seyler. Improving formal timing analysis of switched ethernet by exploiting traffic stream correlations. In Proceedings of the 2014 International Conference on Hardware/Software Codesign and System Synthesis, page 15. ACM, 2014. Google Scholar
  21. Wenbo Xu, Zain AH Hammadeh, Alexander Kröller, Rolf Ernst, and Sophie Quinton. Improved deadline miss models for real-time systems using typical worst-case analysis. In Real-Time Systems (ECRTS), 2015 27th Euromicro Conference on, pages 247-256. IEEE, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail