Network Calculus and Optimization

Internally funded project


Project Details

Project leader:
Dr.-Ing. Kai-Steffen Hielscher

Project members:
Lisa Maile

Contributing FAU Organisations:
Computer Science 7 (Computer Networks and Communication Systems)

Start date: 01/03/2004


Research Fields

Quality of Service
Computer Science 7 (Computer Networks and Communication Systems)


Abstract (technical / expert 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.


Publications
Go to first page Go to previous page 1 of 2 Go to next page Go to last page

Hielscher, K.-S. (2015). Industrial Application of Network Calculus. In Network Calculus (Dagstuhl Seminar 15112) (pp. 72-73). Dagstuhl, Germany, DE: Schloss Dagstuhl, Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
Klehmet, U., & Hielscher, K.-S. (2015). Problems of Strict and Non-strict Service Curves in Connection with Aggregate Scheduling.
Klehmet, U., & Berndt, R. (2015). Worst Case Modeling of Aggregate Scheduling by Network Calculus. In Proceedings. Barcelona, Spain.
Klehmet, U., & Berndt, R. (2014). Alternative Approaches of Convolution within Network Calculus. Journal of Applied Mathematics and Physics, 2, 987-995.
Klehmet, U., & Hielscher, K.-S. (2013). Different Scenarios of Concatenation at Aggregate Scheduling of Multiple Nodes. In ICNS 2013: The Ninth International Conference on Networking and Services (pp. -). Lisbon, Portugal, PT.
Kerschbaum, S., Hielscher, K.-S., Klehmet, U., & German, R. (2012). Network Calculus: Application to an Industrial Automation Network. In MMB & DFT 2012 Workshop Proceedings (pp. -). Kaiserslautern.
Klehmet, U., & Hielscher, K.-S. (2012). Strictness of Rate-Latency Service Curves. In Proc. of International Conference on Data Communication Networking (pp. 75-78). Rom.
Herpel, T., Hielscher, K.-S., Klehmet, U., & German, R. (2009). Stochastic and deterministic performance evaluation of automotive CAN communication. Computer Networks, 53, 1171-1185. https://dx.doi.org/10.1016/j.comnet.2009.02.008
Klehmet, U., Herpel, T., Hielscher, K.-S., & German, R. (2008). Delay Bounds for CAN Communication in Automotive Applications. In Proc. 14th GI/ITG Conference Measurement, Modelling and Evaluation of Computer and Communication Systems (pp. 157-171). Dortmund, Germany, DE: Berlin: VDE Verlag GmbH.
Klehmet, U., Herpel, T., Hielscher, K.-S., & German, R. (2008). Real-Time Guarantees for CAN Traffic. In 2008 IEEE 67th Vehicular Technology Conference (pp. 3037-3041). Marina Bay, Singapore, SG: Piscataway, N.J.: IEEE Conference eXpress Publishing.

Last updated on 2019-24-04 at 11:19