Network Calculus and Optimization
Project Description
Network calculus (NC) is a system theory for deterministic performance
evaluation. It uses mathematical methods to provide performance
guarantees for communication systems. It can be applied in the
design phase of future systems as well as the analysis of existing
systems. In real-time systems, the timeliness of events plays an
important role. Therefore, the classical performance evaluation based on
stochastic methods that result in (stochastic) expectation values, i.e.
mean values, has to be extended by mathematical tools producing
guaranteed bounds for worst case scenarios. Network calculus allows to
obtain upper bounds for end-to-end delays for one nodes or a
series of nodes within a network, upper bounds for the required buffer
space and bounds for the output flow.
These analytic performance bounds characterize the worst-case behavior
of traffic flows and allow dimensioning the corresponding systems.
Currently, we study the applicability of NC for multiplexed flows, in
particular when the FIFO property cannot be assumed at the merging of
individual flows. The aggregation of data flows plays an important role
in modelling the multiplexing scheme. We apply NC for performance
evaluation both of aggregate multiplexing at one node and at
concatenation of aggregated multiple nodes in different scenarios.
We have successfully introduced network calculus methods in the
field of internal automotive communication systems in industrial
applications. Embedded in-car networks need to fulfill hard
real-time constraints. While TDMA-based access schemes in FlexRay
guarantee that certain bound can be met, statistical multiplexing
in CAN networks only allows to calculate bounds for the highest
priority messages. By applying network calculus, we obtained bounds
for all priority classes without the need to specify a concrete
scheduling of the messages. Upper bounds for the amount of data
that arrives at each network node are enough to determine hard
bounds for the end-to-end delay in CAN networks.
Another field of application is industrial communication.
Factory automation often also requires hard real-time bounds
for the end-to-end delay of messages. The use of Ethernet with
priority tagging allows cost-efficient implementation of
factory automation systems. But without stringent planning
of the network, the required bounds on the end-to-end delay
cannot be guaranteed. Network calculus allows to obtain the
required bounds when applied in the planning phase of the
network. It also allows to dimension the buffers of nodes,
e.g. of industrial Ethernet switches. Nowadays, some of
the users of industrial Ethernet need to integrate
non-real-time products like web cams and remote operation
terminals into existing networks. Without
additional analysis, the additional traffic caused by devices
that do not require hard real-time constraints will
cause a violation of the bounds for the delay and buffer
space for real-time traffic. By taking into account this
non-real-time traffic in network calculus and by applying
traffic shaping for the non-real-time flows allows to
dimension the network so that all bounds are met.
Network calculus is currently integrated into an existing
automated industrial network planning tool.
Project Period
- 2004-03-01 – present
Project Leader
Related Publications
Worst Case Modeling of Aggregate Scheduling by Network Calculus
14th International Conference on Networks (ICN 2015)
In: Proceedings, Barcelona, Spain: 2015
BibTeX: Download
, :
Introduction to Network Calculus
ASMTA 2005 (Riga, Latvia)
In: Proc. 12th Int. Conf. on Analytical and Stochastic Modelling Techniques and Applications 2005
BibTeX: Download
:
Alternative Approaches of Convolution within Network Calculus
In: Journal of Applied Mathematics and Physics (2014), p. 987-995
ISSN: 2327-4352
BibTeX: Download
, :
Industrial Application of Network Calculus
Network Calculus (Dagstuhl Seminar 15112) (Dagstuhl, Germany)
In: Network Calculus (Dagstuhl Seminar 15112), Schloss Dagstuhl, Wadern, Germany: 2015
DOI: 10.4230/DagRep.5.3.63
URL: http://drops.dagstuhl.de/opus/volltexte/2015/5269
BibTeX: Download
:
Problems of Strict and Non-strict Service Curves in Connection with Aggregate Scheduling
(2015), p. 33
BibTeX: Download
, :
Strictness of Rate-Latency Service Curves
International Conference on Data Communication Networking (Rom, 2012-07-24 - 2012-07-27)
In: Proc. of International Conference on Data Communication Networking 2012
URL: http://www7.informatik.uni-erlangen.de/~klehmet/publications/Papers/NCstrict.pdf
BibTeX: Download
, :
Different Scenarios of Concatenation at Aggregate Scheduling of Multiple Nodes
The Ninth International Conference on Networking and Services (Lisbon, Portugal)
In: ICNS 2013: The Ninth International Conference on Networking and Services 2013
URL: http://www7.informatik.uni-erlangen.de/~klehmet/publications/Papers/ICNS2013.pdf
BibTeX: Download
, :
Network Calculus: Application to an Industrial Automation Network
MMB & DFT 2012 (Kaiserslautern)
In: MMB & DFT 2012 Workshop Proceedings 2012
URL: http://www7.informatik.uni-erlangen.de/~klehmet/publications/Papers/WoNeCa_IndustrialApplication.pdf
BibTeX: Download
, , , :
Stochastic and deterministic performance evaluation of automotive CAN communication
In: Computer Networks 53 (2009), p. 1171-1185
ISSN: 1389-1286
DOI: 10.1016/j.comnet.2009.02.008
BibTeX: Download
, , , :
Real-Time Guarantees for CAN Traffic
VTC2008-Spring (Marina Bay, Singapore, 2008-05-11 - 2008-05-14)
In: 2008 IEEE 67th Vehicular Technology Conference, Piscataway, N.J.: 2008
DOI: 10.1109/VETECS.2008.327
URL: http://www7.informatik.uni-erlangen.de/~ksjh/Pub/pdf/VTC2008-draft.pdf
BibTeX: Download
, , , :
Delay Bounds for CAN Communication in Automotive Applications
MMB (Dortmund, Germany, 2008-03-31 - 2008-04-02)
In: Proc. 14th GI/ITG Conference Measurement, Modelling and Evaluation of Computer and Communication Systems, Berlin: 2008
URL: http://www7.informatik.uni-erlangen.de/~ksjh/Pub/pdf/Klehmet-CAN-MMB08.pdf
BibTeX: Download
, , , :
Worst Case Analysis for Multiple Priorities in Bitwise Arbitration
(GI/ITG-Workshop MMBnet) (Hamburg, Germany)
In: GI/ITG-Workshop MMBnet: Leistungs-, Zuverlässigkeits- und Verlässlichkeitsbewertung von Kommunikationsnetzen und verteilten Systemen 2007
URL: http://www.informatik.uni-hamburg.de/bib/medoc/B-281-07.pdf
BibTeX: Download
, , , :
Analysis of sensor networks in real time
(QRM 2007) (Oxford, UK)
In: 6th Int. Conf. Quality, Reliability, and Maintenance, UK: 2007
URL: http://www7.informatik.uni-erlangen.de/~klehmet/publications/Papers/QRM_07.pdf
BibTeX: Download
: