Abstract
Guaranteeing performance bounds of data flows is an essential part of network engineering and certification of networks with real-time constraints. A prevalent analytical method to derive guarantees for end-to-end delay and buffer size is Deterministic Network Calculus (DNC). Due to the DNC system model, one decisive restriction is that only unicast flows can be analyzed. Previous attempts to analyze networks with multicast flows circumvented this restriction instead of overcoming it. E.g., they replaced the system model with an overly-pessimistic one that consists of unicast flows only. Such approaches impair modeling accuracy and thus inevitably result in inaccurate performance bounds.
In this chapter, we approach the problem of multicast flows differently. We start from the existing DNC analysis procedure, the unicast feed-forward analysis, and generalize it to a multicast feed-forward analysis. To that end, we contribute a novel analysis procedure that leaves the network model containing multicast flows unchanged, preserves its accuracy, allows for DNC principles such as pay multiplexing only once, and therefore derives more accurate performance bounds than existing approaches.
This chapter is an extended version of [4]: Generalizing Network Calculus Analysis to Derive Performance Guarantees for Multicast Flows, in Proc. of EAI ValueTools (2016).
Part of this work has been conducted at the Distributed Computer Systems Lab, TU Kaiserslautern (TUK), D-67663 Kaiserslautern, Germany, with support of the Carl Zeiss Foundation.
Part of this work has been conducted at Airbus Group Innovations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Due to a lack of software tools, TA and FA are not included.
References
H. Bauer, Analyse pire cas de flux hétérogènes dans un réseau embarqué avion. Ph.D. thesis, Université de Toulouse, 2011
H. Bauer, J. Scharbarg, C. Fraboul, Applying and optimizing trajectory approach for performance evaluation of AFDX avionics network, in Proceedings of IEEE ETFA (2009)
L. Bisti, L. Lenzini, E. Mingozzi, G. Stea, Numerical analysis of worst-case end-to-end delay bounds in fifo tandem networks. Springer Real-Time Syst. J. 48, 527–569 (2012)
S. Bondorf, F. Geyer, Generalizing network calculus analysis to derive performance guarantees for multicast flows, in Proceedings of EAI ValueTools (2016)
S. Bondorf, J.B. Schmitt, The DiscoDNC v2 – a comprehensive tool for deterministic network calculus, in Proceedings of EAI ValueTools (2014)
S. Bondorf, J.B. Schmitt, Boosting sensor network calculus by thoroughly bounding cross-traffic, in Proceedings IEEE INFOCOM (2015)
S. Bondorf, J.B. Schmitt, Calculating accurate end-to-end delay bounds – you better know your cross-traffic, in Proceedings of EAI ValueTools (2015)
S. Bondorf, J.B. Schmitt, Improving cross-traffic bounds in feed-forward networks – there is a job for everyone, in Proceedings of GI/ITG MMB & DFT (2016)
S. Bondorf, P. Nikolaus, J.B. Schmitt, Quality and cost of deterministic network calculus – design and evaluation of an accurate and fast analysis, in Proceedings of ACM SIGMETRICS (2017)
A. Bouillard, Algorithms and Efficiency of Network Calculus. Habilitation thesis, ENS, 2014
M. Boyer, P. Roux, A common framework embedding network calculus and event stream theory, in Proceedings of IEEE ETFA (2016)
M. Boyer, N. Navet, M. Fumey, Experimental assessment of timing verification techniques for AFDX, in Proceedings of ERTS (2012)
C.S. Chang, Performance Guarantees in Communication Networks (Springer, Berlin, 2000)
F. Geyer, G. Carle, Network engineering for real-time networks: comparison of automotive and aeronautic industries approaches. IEEE Commun. Mag. 54, 106–112 (2016)
J. Grieu, Analyse et évaluation de techniques de commutation Ethernet pour l’interconnexion des systèmes avioniques. Ph.D. thesis, Institut National Polytechnique de Toulouse, 2004
O. Hotescu, K. Jaffres-Runser, J.L. Scharbarg, C. Fraboul, Towards quality of service provision with avionics full duplex switching, in Euromicro ECRTS, Work-in-Progress Session (2017)
G. Kemayo, N. Benammar, F. Ridouard, H. Bauer, P. Richard, Improving AFDX End-to-End delays analysis, in Proceedings of IEEE ETFA (2015)
K. Lampka, S. Bondorf, J.B. Schmitt, N. Guan, W. Yi, Generalized finitary real-time calculus, in Proceedings IEEE INFOCOM (2017)
J.-Y. Le Boudec, P. Thiran, Network Calculus: A Theory of Deterministic Queuing Systems for the Internet (Springer, Berlin, 2001)
S. Martin, P. Minet, Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class, in Proceedings of IPDPS (2006)
J. Migge, L’ordonnancement sous contraintes temps-réel un modèle à base de trajectoires. Ph.D. thesis, INRIA Sophia Antipolis, 1999
J.B. Schmitt, F.A. Zdarsky, M. Fidler, Delay bounds under arbitrary multiplexing: when network calculus leaves you in the lurch…, in Proceedings of IEEE INFOCOM (2008)
J.B. Schmitt, F.A. Zdarsky, I. Martinovic, Improving performance bounds in feed-forward networks by paying multiplexing only once, in Proceedings of GI/ITG MMB (2008)
K. Tindell, J. Clark, Holistic schedulability analysis for distributed hard real-time systems. Microprocess. Microprogramm. 40, 117–134 (1994)
N. Tobeck, Enforcing domain segregation in unified cabin data networks, in Proceedings of IEEE/AIAA DASC (2017)
Acknowledgements
The authors would like to thank Bruno Oliveira Cattelan for his work on implementing the explicit intermediate bounds analysis and the multicast feed-forward analysis in the Disco Deterministic Network Calculator.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Bondorf, S., Geyer, F. (2019). Deterministic Network Calculus Analysis of Multicast Flows. In: Puliafito, A., Trivedi, K. (eds) Systems Modeling: Methodologies and Tools. EAI/Springer Innovations in Communication and Computing. Springer, Cham. https://doi.org/10.1007/978-3-319-92378-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-92378-9_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-92377-2
Online ISBN: 978-3-319-92378-9
eBook Packages: EngineeringEngineering (R0)