Document Open Access Logo

End-To-End Deadlines over Dynamic Topologies

Authors Victor Millnert, Johan Eker, Enrico Bini

PDF
Thumbnail PDF

File

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

Document Identifiers

Author Details

Victor Millnert
  • Lund University, Sweden
Johan Eker
  • Lund University, Sweden
  • Ericsson Research, Sweden
Enrico Bini
  • University of Turin, Italy

Cite As Get BibTex

Victor Millnert, Johan Eker, and Enrico Bini. End-To-End Deadlines over Dynamic Topologies. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ECRTS.2019.10

Abstract

Despite the creativity of the scientific community and the funding agencies, the underlying model of computation behind IoT, WSN, cloud, edge, fog, and mist is fundamentally the same; Computational nodes which are dynamically interconnected to form a system in where both processing capacity and connectivity may vary over time. On top of such a system, we consider applications that need packets to flow along a path and adhere to end-to-end deadlines. This application model is motivated by both control and automation systems, as well as telecom systems. The challenge is to guarantee end-to-end deadlines when allowing nodes and applications to join or leave.
The mainstream, and to some extent natural, approach to this is to relax the stringency of the constraint (e.g. use probabilistic guarantees, soft deadlines). In this paper we take a different approach and keep the end-to-end deadlines as hard constraints and instead partially limit the freedom of how nodes and applications are allowed to leave and join. We present a theoretical framework for modeling such systems along with proofs that deadlines are always honored.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Cloud computing
  • Networks → Cloud computing
Keywords
  • Cloud
  • real-time
  • end-to-end latency guarantee
  • end-to-end response time guarantee
  • dynamic network

Metrics

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

References

  1. Mohammad Ashjaei, Saad Mubeen, Moris Behnam, Luis Almeida, and Thomas Nolte. End-to-End Resource Reservations in Distributed Embedded Systems. In 22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 1-11, August 2016. Google Scholar
  2. Marco Di Natale and John A. Stankovic. Dynamic End-to-end Guarantees in Distributed Real Time Systems. In Proceedings of the 15th IEEE Real-Time Systems Symposium, pages 215-227, December 1994. Google Scholar
  3. Neha Gandhi, Dawn M Tilbury, Yixin Diao, J Hellerstein, and Sujay Parekh. Mimo control of an apache web server: Modeling and controller design. In American Control Conference, 2002. Proceedings of the 2002, volume 6, pages 4922-4927. IEEE, 2002. Google Scholar
  4. Ricardo Garibay-Martínez, Geoffrey Nelissen, Luis Lino Ferreira, and Luis Miguel Pinho. Task partitioning and priority assignment for distributed hard real-time systems. Journal of Computer and System Sciences, 81(8):1542-1555, 2015. Google Scholar
  5. Richard Gerber, Seongsoo Hong, and Manas Saksena. Guaranteeing Real-Time Requirements with Resource-based Calibration of Periodic Processes. IEEE Transaction on Software Engineering, 21(7):579-592, July 1995. Google Scholar
  6. Arne Hamann, Marek Jersak, Kai Richter, and Rolf Ernst. A framework for modular analysis and exploration of heterogeneous embedded systems. Real-Time Systems, 33(1):101-137, July 2006. URL: http://dx.doi.org/10.1007/s11241-006-6884-x.
  7. Dan Henriksson, Ying Lu, and Tarek Abdelzaher. Improved prediction for web server delay control. In Real-Time Systems, 2004. ECRTS 2004. Proceedings. 16th Euromicro Conference on, pages 61-68. IEEE, 2004. Google Scholar
  8. Shengyan Hong, Thidapat Chantem, and Xiaobo Sharon Hu. Local-deadline assignment for distributed real-time systems. IEEE Transactions on Computers, 64(7):1983-1997, 2015. URL: http://dx.doi.org/10.1109/TC.2014.2349494.
  9. Romain Jacob, Marco Zimmerling, Pengcheng Huang, Jan Beutel, and Lothar Thiele. End-to-end real-time guarantees in wireless cyber-physical systems. In Proceedings 2016 IEEE Real-Time Systems Symposium. RTSS 2016, pages 167-178. IEEE, 2016. Google Scholar
  10. Praveen Jayachandran and Tarek Abdelzaher. Delay Composition Algebra: A Reduction-Based Schedulability Algebra for Distributed Real-Time Systems. In Proceedings of the 29th IEEE Real-Time Systems Symposium, pages 259-269, December 2008. URL: http://dx.doi.org/10.1109/RTSS.2008.38.
  11. Shengbing Jiang. A decoupled scheduling approach for distributed real-time embedded automotive systems. In Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 191-198, 2006. Google Scholar
  12. Cristian Klein, Martina Maggio, Karl-Erik Årzén, and Francisco Hernández-Rodriguez. Brownout: Building more robust cloud applications. In Proceedings of the 36th International Conference on Software Engineering, pages 700-711. ACM, 2014. Google Scholar
  13. Jean-Yves Le Boudec and Patrick Thiran. Network Calculus: a theory of deterministic queuing systems for the internet, volume 2050 of Lecture Notes in Computer Science. Springer, 2001. Google Scholar
  14. José L. Lorente, Giuseppe Lipari, and Enrico Bini. A hierarchical scheduling model for component-based real-time systems. In Proc. of the 20th International Parallel and Distributed Processing Symp., April 2006. URL: http://dx.doi.org/10.1109/IPDPS.2006.1639405.
  15. Dana Marinca, Pascale Minet, and Laurent George. Analysis of deadline assignment methods in distributed real-time systems. Computer Communications, 27(15):1412-1423, 2004. Google Scholar
  16. Victor Millnert, Johan Eker, and Enrico Bini. Dynamic control of NFV forwarding graphs with end-to-end deadline constraints. In IEEE International Conference on Communications, pages 1-7. IEEE, 2017. Google Scholar
  17. Victor Millnert, Johan Eker, and Enrico Bini. Achieving predictable and low end-to-end latency for a network of smart services. In IEEE GLOBECOM 2018, 2018. Google Scholar
  18. Tommi Nylander, Marcus Thelander Andrén, Karl-Erik Årzén, and Martina Maggio. Cloud Application Predictability through Integrated Load-Balancing and Service Time Control. In 2018 IEEE International Conference on Autonomic Computing (ICAC), pages 51-60. IEEE, 2018. Google Scholar
  19. Pradeep Padala, Kang G Shin, Xiaoyun Zhu, Mustafa Uysal, Zhikui Wang, Sharad Singhal, Arif Merchant, and Kenneth Salem. Adaptive control of virtualized resources in utility computing environments. In ACM SIGOPS Operating Systems Review, volume 41, pages 289-302. ACM, 2007. Google Scholar
  20. José Carlos Palencia and Michael González Harbour. Schedulability Analysis for Tasks with Static and Dynamic Offsets. In Proceedings of the 19th IEEE Real-Time Systems Symposium, pages 26-37, December 1998. Google Scholar
  21. Rodolfo Pellizzoni and Giuseppe Lipari. Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling. Journal of Computer and System Sciences, 73(2):186-206, March 2007. URL: http://dx.doi.org/10.1016/j.jcss.2006.04.002.
  22. Nicola Serreli, Giuseppe Lipari, and Enrico Bini. The Demand Bound Function Interface of Distributed Sporadic Pipelines of Tasks Scheduled by EDF. In Proceedings of the 22nd Euromicro Conference on Real-Time Systems, pages 187-196, July 2010. URL: http://dx.doi.org/10.1109/ECRTS.2010.17.
  23. Lothar Thiele, Samarjit Chakraborty, and Martin Naedele. Real-time calculus for scheduling hard real-time systems. In Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. The 2000 IEEE International Symposium on, volume 4, pages 101-104. IEEE, 2000. Google Scholar
  24. Ken Tindell and John Clark. Holistic Schedulability Analysis for Distributed Hard Real-Time Systems. Microprocessing and Microprogramming, 50:117-134, April 1994. Google Scholar
  25. Thiemo Voigt and Per Gunningberg. Adaptive resource-based Web server admission control. In ISCC, 2002. Google Scholar
  26. Qi Zhu, Haibo Zeng, Wei Zheng, Marco Di Natale, and Alberto Sangiovanni-Vincentelli. Optimization of Task Allocation and Priority Assignment in Hard Real-time Distributed Systems. ACM Transactions on Embedded Computing Systems, 11(4):85:1-85:30, January 2013. URL: http://dx.doi.org/10.1145/2362336.2362352.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact