Network Calculus and Optimization

Project Description

Logo network_calculus

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