Network Calculus und Optimierung


Network Calculus (NC) ist ein systemtheoretischer Ansatz zur deterministischen Leistungsanalyse. Dabei kommen mathematische Methoden zum Einsatz, um Leistungsgarantien für Kommunikationssystemen bestimmen zu können. Die Methode kann sowohl in der Planungsphase für zukünftige Systeme als auch bei der Analyse bestehender Systeme eingesetzt werden. In Echtzeitsystemen spielt die Rechtzeitigkeit bestimmter Ereignisse eine entscheidende Rolle. Daher ist es wichtig, die Ergebnisse klassischer Leistungsanalyse, die stochastische Erwartungswerte wie etwa Mittelwerte liefert, durch mathematische Methoden zu ergänzen, die garantierte Schranken für Worst-Case-Szenarien liefern können. Network Calculus ermöglicht die Bestimmung von oberen Grenzen für Ende-zu-Ende-Verzögerungen für einzelne Netzwerkknoten und Folgen von Knoten in einem Netzwerk, Obergrenzen für die benötigten Puffer und Grenzen für den ausgehenden Verkehr. Diese analytischen Grenzen charakterisieren das Verhalten im Worst-Case und erlauben eine korrekte Dimensionierung der Systeme.
Aktuell studieren wir die Grenzen der Anwendbarkeit von Network Calculus für das Multiplexen von Datenströmen, insbesondere, wenn die Aggregation von Strömen nicht nach dem FIFO-Prinzip erfolgt. Die Aggregation von Strömen spielt eine wichtige Rolle, wenn Multiplex-Verfahren modelliert werden. Wir setzen Network Calculus beim Multiplexen an einzelnen Knoten und bei der Hintereinanderschaltung mehrerer Knoten in einem Netzwerk ein.
Wir haben Methoden des Network Calcus erfolgreich in industriellen Anwendungen der internen Fahrzeugkommunikation eingesetzt. Eingebettete Netze in Fahrzeugen müssen harte Echtzeitbedingungen erfüllen. Während TDMA-Verfahren wie in FlexRay die Erfüllung von Grenzen garantieren, erlaubt das stochastische Multiplexen in CAN-Netzen lediglich die Bestimmung von Grenzen für die höchste Priorität. Durch die Anwendung von Network Calculus können wir Grenzen für alle Prioritätsklassen bestimmen, ohne dass wir einen konkreten Kommunikationsablauf vorgeben müssen. Es genügt für die Bestimmung der harten Echtzeitgrenzen, wenn lediglich obere Grenzen für die Menge der an den Knoten ankommenden Daten bekannt sind.
Ein weiteres Einsatzgebiet für Network Calculus ist die industrielle Kommunikation. In der Industrieautomatisierung sind meist auch harte Grenzen für die Ende-zu-Ende-Verzögerung gefordert. Der Einsatz von Ethernet mit unterschiedlichen Prioritätsklassen erlaubt eine kostengünstige Implementierung solcher Fabrikautomatisierungssysteme. Aber ohne strikte Planung der Netze können die geforderten Verzögerungsgrenzen aufgrund des statistischen Multiplexens nicht garantiert werden. Wird Network Calculus bereits in der Planungsphase solcher Netze eingesetzt, können die Netze so dimensioniert werden, dass alle nötigen Grenzen eingehalten werden können. Neben den Verzögerungszeiten können auch die benötigten Puffergrößen in Knoten wie etwa in Industrial Ethernet Switches begrenzt werden. Aktuell fordern einige Anwender von Industieautomatisierungslösungen die einfache Integration von nicht echtzeitfähigen Komponenten in bestehende Netze, sei es von IP-Kameras oder von Bedienterminals. Ohne zusätzliche Analysen kann der Verkehr der zusätzlichen Geräte die Echtzeitkommunikation derart stören, dass bestehende Grenzen für die Verzögerung und den Puffer von Echtzeitverkehr nicht mehr eingehalten werden können. Durch Berücksichtigung des Nicht-Echzeitverkehrs in Network Calculus und durch Verkehrsformung dieser Datenströme können die Netze so dimensioniert werden, dass die Grenzen weiterhin eingehalten werden. Aktuell werden Netwok-Calculus-Berechnungen in ein bestehendes automatisiertes Netzwerkplanungswerkzeug integriert.

  • Projektdauer: 2004-03-01 - dato

Projektmitglieder

  1. Kai-Steffen Jens Hielscher, "Industrial Application of Network Calculus," Network Calculus (Dagstuhl Seminar 15112), Schloss Dagstuhl, Wadern, Germany, Dagstuhl, Germany, pp. 72-73, März 2015  
  2. Ulrich Klehmet und 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 und 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 und Kai-Steffen Jens Hielscher, "Strictness of Rate-Latency Service Curves," 2nd Workshop on Network Calculus (WoNeCa-2), Bamberg, Germany, März 2014
  5. Ulrich Klehmet und 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, März 2013
  6. Ulrich Klehmet und Kai-Steffen Jens Hielscher, "Strictness of Rate-Latency Service Curves," Proc. of International Conference on Data Communication Networking, Rom, Juli 2012
  7. Sven Kerschbaum, Kai-Steffen Jens Hielscher, Ulrich Klehmet und Reinhard German, "Network Calculus: Application to an Industrial Automation Network," MMB & DFT 2012 Workshop Proceedings, Kaiserslautern, März 2012
  8. Thomas Herpel, Kai-Steffen Jens Hielscher, Ulrich Klehmet und Reinhard German, "Stochastic and deterministic performance evaluation of automotive CAN communication," in Computer Networks Bd. 53, pp. 1171-1185., 2009  
  9. Ulrich Klehmet, Thomas Herpel, Kai-Steffen Jens Hielscher und Reinhard German, "Real-Time Guarantees for CAN Traffic," 2008 IEEE 67th Vehicular Technology Conference, Piscataway, N.J., Marina Bay, Singapore, pp. 3037-3041, Mai 2008
  10. Ulrich Klehmet, Thomas Herpel, Kai-Steffen Jens Hielscher und 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, März 2008
  11. Ulrich Klehmet, Thomas Herpel, Kai-Steffen Jens Hielscher und 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, März 2007
  13. Ulrich Klehmet, "Introduction to Network Calculus," Proc. 12th Int. Conf. on Analytical and Stochastic Modelling Techniques and Applications, Riga, Latvia, pp. 89, Juni 2005