Network Calculus and Optimization


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.

  • Keywords: deterministic queueing; QoS guarantees; min-plus algebra; optimization
  • Project Period: 2004-03-01 - present

Project Members

  1. Kai-Steffen Jens Hielscher, "Industrial Application of Network Calculus," Network Calculus (Dagstuhl Seminar 15112), Schloss Dagstuhl, Wadern, Germany, Dagstuhl, Germany, pp. 72-73, March 2015  
  2. Ulrich Klehmet and Kai-Steffen Jens Hielscher, "Problems of Strict and Non-strict Service Curves in Connection with Aggregate Scheduling," Friedrich-Alexander-Universität, Technischer Report, 2015
  3. Ulrich Klehmet and Rüdiger Berndt, "Worst Case Modeling of Aggregate Scheduling by Network Calculus," 14th International Conference on Networks (ICN 2015), Barcelona, Spain, April 2015
  4. Ulrich Klehmet and Kai-Steffen Jens Hielscher, "Strictness of Rate-Latency Service Curves," 2nd Workshop on Network Calculus (WoNeCa-2), Bamberg, Germany, March 2014
  5. Ulrich Klehmet and Kai-Steffen Jens Hielscher, "Different Scenarios of Concatenation at Aggregate Scheduling of Multiple Nodes," ICNS 2013: The Ninth International Conference on Networking and Services, Lisbon, Portugal, March 2013
  6. Ulrich Klehmet and Kai-Steffen Jens Hielscher, "Strictness of Rate-Latency Service Curves," Proc. of International Conference on Data Communication Networking, Rom, July 2012
  7. Sven Kerschbaum, Kai-Steffen Jens Hielscher, Ulrich Klehmet and Reinhard German, "Network Calculus: Application to an Industrial Automation Network," MMB & DFT 2012 Workshop Proceedings, Kaiserslautern, March 2012
  8. Thomas Herpel, Kai-Steffen Jens Hielscher, Ulrich Klehmet and Reinhard German, "Stochastic and deterministic performance evaluation of automotive CAN communication," in Computer Networks vol. 53, pp. 1171-1185., 2009  
  9. Ulrich Klehmet, Thomas Herpel, Kai-Steffen Jens Hielscher and Reinhard German, "Real-Time Guarantees for CAN Traffic," 2008 IEEE 67th Vehicular Technology Conference, Piscataway, N.J., Marina Bay, Singapore, pp. 3037-3041, May 2008
  10. Ulrich Klehmet, Thomas Herpel, Kai-Steffen Jens Hielscher and Reinhard German, "Delay Bounds for CAN Communication in Automotive Applications," Proc. 14th GI/ITG Conference Measurement, Modelling and Evaluation of Computer and Communication Systems, Berlin, Dortmund, Germany, pp. 157-171, March 2008
  11. Ulrich Klehmet, Thomas Herpel, Kai-Steffen Jens Hielscher and Reinhard German, "Worst Case Analysis for Multiple Priorities in Bitwise Arbitration," GI/ITG-Workshop MMBnet: Leistungs-, Zuverlässigkeits- und Verlässlichkeitsbewertung von Kommunikationsnetzen und verteilten Systemen, Hamburg, Germany, pp. 27-35, September 2007
  12. Ulrich Klehmet, "Analysis of sensor networks in real time," 6th Int. Conf. Quality, Reliability, and Maintenance, UK, Oxford, UK, pp. 139-143, March 2007
  13. Ulrich Klehmet, "Introduction to Network Calculus," Proc. 12th Int. Conf. on Analytical and Stochastic Modelling Techniques and Applications, Riga, Latvia, pp. 89, June 2005