Document Open Access Logo

A Residual Service Curve of Rate-Latency Server Used by Sporadic Flows Computable in Quadratic Time for Network Calculus

Authors Marc Boyer , Pierre Roux , Hugo Daigmorte , David Puechmaille

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2021.14.pdf
  • Filesize: 1.18 MB
  • 21 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Networks → Formal specifications
  • Networks → Network performance evaluation
  • Networks → Network reliability
  • Software and its engineering → Formal methods
  • General and reference → Verification
Keywords
  • Network Calculus
  • response time
  • residual curve
  • rate-latency server
  • sporadic workload
  • formal proof
  • Coq

Metrics

Abstract

Computing response times for resources shared by periodic workloads (tasks or data flows) can be very time consuming as it depends on the least common multiple of the periods. In a previous study, a quadratic algorithm was provided to upper bound the response time of a set of periodic tasks with a fixed-priority scheduling. This paper generalises this result by considering a rate-latency server and sporadic workloads and gives a response time and residual curve that can be used in other contexts. It also provides a formal proof in the Coq language.

Cite As Get BibTex

Marc Boyer, Pierre Roux, Hugo Daigmorte, and David Puechmaille. A Residual Service Curve of Rate-Latency Server Used by Sporadic Flows Computable in Quadratic Time for Network Calculus. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ECRTS.2021.14

Author Details

Marc Boyer
  • ONERA / DTIS - Université de Toulouse, F-31055 Toulouse, France
Pierre Roux
  • ONERA / DTIS - Université de Toulouse, F-31055 Toulouse, France
Hugo Daigmorte
  • RealTime-at-Work, F-54600 Villers-lès-Nancy, France
David Puechmaille
  • RealTime-at-Work, F-54600 Villers-lès-Nancy, France

Supplementary Materials

References

  1. Yves Bertot, Georges Gonthier, Sidi Ould Biha, and Ioana Pasca. Canonical big operators. In Otmane Ait Mohamed, César Muñoz, and Sofiène Tahar, editors, Theorem Proving in Higher Order Logics, pages 86-101, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  2. Enrico Bini, Andrea Parri, and Giacomo Dossena. A quadratic-time response time upper bound with a tightness property. In Proc. of the 36th IEEE Real-Time Systems Symposium (RTSS 2015), San Antonio, USA, December 2015. Google Scholar
  3. Luca Bisti, Luciano Lenzini, Enzo Mingozzi, and Giovanni Stea. DEBORAH: a tool for worst-case analysis of FIFO tandems. In Proc. of the 4th Int. Symp. On Leveraging Applications of Formal Methods, Verification and Validation (ISoLA 2010), LNCS. Springer, 2010. Google Scholar
  4. Steffen Bondorf and Jens B. Schmitt. The DiscoDNC v2 - a comprehensive tool for deterministic network calculus. In Proc. of the 8th Int. Conf. on Performance Evaluation Methodologies and Tools (VALUETOOLS 2014), 2014. Google Scholar
  5. Anne Bouillard, Marc Boyer, and Euriell Le Corronc. Deterministic Network Calculus - From theory to practical implementation. Wiley, 2018. Google Scholar
  6. Anne Bouillard and Éric Thierry. An algorithmic toolbox for network calculus. Discrete Event Dynamic Systems, 18(1):3-49, October 2008. Google Scholar
  7. Marc Boyer and Christian Fraboul. Tightening end to end delay upper bound for AFDX network with rate latency FCFS servers using network calculus. In Proc. of the 7th IEEE Int. Workshop on Factory Communication Systems Communication in Automation (WFCS 2008), pages 11-20. IEEE industrial Electrony Society, May 21-23 2008. Google Scholar
  8. Marc Boyer, Jörn Migge, and Marc Fumey. PEGASE, a robust and efficient tool for worst case network traversal time. In Proc. of the SAE 2011 AeroTech Congress & Exhibition, Toulouse, France, 2011. Google Scholar
  9. Marc Boyer, Jörn Migge, and Nicolas Navet. An efficient and simple class of functions to model arrival curve of packetised flows. In Proc. of the 1st Int. Workshop on Worst-Case Traversal Time (WCTT'2011), pages 43-50. ACM, 2011. Google Scholar
  10. Marc Boyer, Nicolas Navet, and Marc Fumey. Experimental assessment of timing verification techniques for AFDX. In Proc. of the 6th Int. Congress on Embedded Real Time Software and Systems, Toulouse, France, 2012. Google Scholar
  11. Felipe Cerqueira, Felix Stutz, and Björn B. Brandenburg. PROSA: A case for readable mechanized schedulability analysis. In Proc. of the 28th Euromicro Conference on Real-Time Systems (ECRTS 2016), pages 273-284, Toulouse, France, July 5-8 2016. URL: https://doi.org/10.1109/ECRTS.2016.28.
  12. Cheng-Shang Chang. Performance Guarantees in communication networks. Telecommunication Networks and Computer Systems. Springer, 2000. Google Scholar
  13. The Coq development team. The Coq proof assistant reference manual, 2019. Version 8.11. URL: https://coq.inria.fr.
  14. Christian Fraboul and Nathan Fisher, editors. 28th Euromicro Conference on Real-Time Systems, ECRTS 2016, Toulouse, France, July 5-8, 2016. IEEE Computer Society, 2016. URL: https://ieeexplore.ieee.org/xpl/conhome/7557819/proceeding.
  15. Georges Gonthier, Assia Mahboubi, and Enrico Tassi. A Small Scale Reflection Extension for the Coq system. Research Report RR-6455, INRIA, 2008. URL: http://hal.inria.fr/inria-00258384.
  16. Ronghui Gu, Zhong Shao, Hao Chen, Xiongnan (Newman) Wu, Jieung Kim, Vilhelm Sjöberg, and David Costanzo. Certikos: An extensible architecture for building certified concurrent OS kernels. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 653-669, Savannah, GA, November 2016. USENIX Association. URL: https://www.usenix.org/conference/osdi16/technical-sessions/presentation/gu.
  17. Nan Guan and Wang Yi. Finitary real-time calculus: Efficient performance analysis of distributed embedded systems. In Proc. or the IEEE 34th Real-Time Systems Symposium (RTSS'2013), pages 330-339. IEEE, 2013. Google Scholar
  18. Kai Lampka, Steffen Bondorf, and Jens Schmitt. Achieving efficiency without sacrificing model accuracy: Network calculus on compact domains. In Proc. of the 24th IEEE Int. Symp. on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2016), 2016. Google Scholar
  19. Leslie Lamport. How to write a 21st century proof. Journal of Fixed Point Theory and Applications, 11(1):43-63, March 2012. Google Scholar
  20. Jean-Yves Le Boudec and Patrick Thiran. Network Calculus, volume 2050 of LNCS. Springer Verlag, 2001. http://lrcwww.epfl.ch/PS_files/NetCal.htm. Google Scholar
  21. E. Le Corronc, B. Cottenceau, and L. Hardouin. Container of (min,+)-linear systems. Journal of Discrete Event Dynamic Systems, 14(1):15-52, March 2014. Google Scholar
  22. Xavier Leroy. Formal verification of a realistic compiler. Commun. ACM, 52(7):107-115, 2009. URL: https://doi.org/10.1145/1538788.1538814.
  23. Nicolas Navet, Tieu Long Mai, and Jörn Migge. Using machine learning to speed up the design space exploration of Ethernet TSN networks. Technical Report 10993/38604, University of Luxembourg, January 2019. Google Scholar
  24. Nicolas Navet, Jörn Migge, Josetxo Villanueva, and Marc Boyer. Pre-shaping bursty transmissions under IEEE802.1Q as a simple and efficient QoS mechanism. SAE Int. Journal of Passenger Cars—Electronic and Electrical System, 11(3), 2018. Google Scholar
  25. Hanrijanto Sariowan, Rene L. Cruz, and George C. Polyzos. SCED: A generalized scheduling policy for guaranteeing quality-of-service. IEEE/ACM transactions on networking, 7(5):669-684, October 1999. Google Scholar
  26. Jens B. Schmitt and Frank A. Zdarsky. The DISCO network calculator - a toolbox for worst case analysis. In Proc. of the First International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS'06), Pisa, Italy. ACM, 2006. Google Scholar
  27. Urban Suppiger, Simon Perathoner, Kai Lampka, and Lothar Thiele. A simple approximation method for reducing the complexity of modular performance analysis. TIK-Report 329, Computer Engineering and Networks Laboratory - Swiss Federal Institute of Technology (ETH), August 2010. Google Scholar
  28. Ernesto Wandeler. Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems. PhD thesis, ETH Zurich, September 2006. Google Scholar
  29. Ernesto Wandeler and Lothar Thiele. Real-Time Calculus (RTC) Toolbox. http://www.mpa.ethz.ch/Rtctoolbox, 2006.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact