Network Calculus and Optimization 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.
| Projektleitung: Prof. Dr.-Ing. Reinhard German, Dr.-Ing. Kai-Steffen Jens Hielscher
Beginn: 1.3.2004
Kontakt: Hielscher, Kai-Steffen Jens Telefon +49 9131 85 27932, Fax +49 9131 85 27409, E-Mail: kai-steffen.hielscher@fau.de
| Publikationen |
---|
Herpel, Thomas ; Hielscher, Kai-Steffen Jens ; Klehmet, Ulrich ; German, Reinhard: Stochastic and deterministic performance evaluation of automotive CAN communication. In: Computer Networks 53 (2009), S. 1171-1185. [doi>10.1016/j.comnet.2009.02.008] | Klehmet, Ulrich ; Herpel, Thomas ; Hielscher, Kai-Steffen Jens ; German, Reinhard: Real-Time Guarantees for CAN Traffic. In: n.b. (Hrsg.) : 2008 IEEE 67th Vehicular Technology Conference (VTC2008-Spring Marina Bay, Singapore 11 - 14 May 2008). Piscataway, N.J. : IEEE Conference eXpress Publishing, 2008, S. 3037-3041. - ISBN 978-1-4244-1645-5 | Klehmet, Ulrich ; Herpel, Thomas ; Hielscher, Kai-Steffen Jens ; German, Reinhard: Delay Bounds for CAN Communication in Automotive Applications. In: Bause, Falco ; Buchholz, Peter (Hrsg.) : Proc. 14th GI/ITG Conference Measurement, Modelling and Evaluation of Computer and Communication Systems (MMB Dortmund, Germany March 31 - April 2, 2008). Berlin : VDE Verlag GmbH, 2008, S. 157-171. - ISBN 978-3-8007-3090-2 | Klehmet, Ulrich: Analysis of sensor networks in real time. In: Thomas, R.A. (Hrsg.) : 6th Int. Conf. Quality, Reliability, and Maintenance ((QRM 2007) Oxford, UK 22-23 March). UK : Coxmoore Publishing Company, 2007, S. 139-143. | Klehmet, Ulrich ; Herpel, Thomas ; Hielscher, Kai-Steffen Jens ; German, Reinhard: Worst Case Analysis for Multiple Priorities in Bitwise Arbitration. In: Wolfinger, Bernd ; Heidtmann, Klaus (Hrsg.) : GI/ITG-Workshop MMBnet: Leistungs-, Zuverlässigkeits- und Verlässlichkeitsbewertung von Kommunikationsnetzen und verteilten Systemen ((GI/ITG-Workshop MMBnet) Hamburg, Germany 13.-14. September). 2007, S. 27-35. | Klehmet, Ulrich: Introduction to Network Calculus. In: Al-Begain, Khalid ; Bolch, Gunter ; Telek, Miklos (Hrsg.) : Proc. 12th Int. Conf. on Analytical and Stochastic Modelling Techniques and Applications (ASMTA 2005 Riga, Latvia June 1-4, 2005). 2005, S. 89. | Klehmet, Ulrich ; Hielscher, Kai-Steffen Jens: Different Scenarios of Concatenation at Aggregate Scheduling of Multiple Nodes. In: ICNS (Hrsg.) : ICNS 2013: The Ninth International Conference on Networking and Services (The Ninth International Conference on Networking and Services Lisbon, Portugal 24.-29.März 2013). 2013, S. -. | Kerschbaum, Sven ; Hielscher, Kai-Steffen Jens ; Klehmet, Ulrich ; German, Reinhard: Network Calculus: Application to an Industrial Automation Network. In: MMB & DFT 2012 (Veranst.) : MMB & DFT 2012 Workshop Proceedings (MMB & DFT 2012 Kaiserslautern 19.-21. 03.2012). Bd. 388/12. 2012, S. -. | Klehmet, Ulrich ; Hielscher, Kai-Steffen Jens: Strictness of Rate-Latency Service Curves. In: ICETE 2012 (Veranst.) : Proc. of International Conference on Data Communication Networking (International Conference on Data Communication Networking Rom 24.-27. July 2012). 2012, S. -. | Hielscher, Kai-Steffen Jens: Industrial Application of Network Calculus. In: Ciucu, Florin ; Fidler, Markus ; Liebeherr, Jörg ; Schmitt, Jens (Veranst.) : Network Calculus (Dagstuhl Seminar 15112) (Network Calculus (Dagstuhl Seminar 15112) Dagstuhl, Germany March 8-11, 2015). Schloss Dagstuhl, Wadern, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015, S. 72-73. (Dagstuhl Reports Bd. 5, Nr. 3) [doi>10.4230/DagRep.5.3.63] | Klehmet, Ulrich ; Hielscher, Kai-Steffen Jens: Problems of Strict and Non-strict Service Curves in Connection with Aggregate Scheduling. Erlangen : Friedrich-Alexander-Universität. 2015. - Interner Bericht. 33 Seiten (Technischer Report) | Klehmet, Ulrich ; Berndt, Rüdiger: Worst Case Modeling of Aggregate Scheduling by Network Calculus. In: 14th International Conference on Networks (ICN 2015). Barcelona, Spain : 2015. | Klehmet, Ulrich ; Hielscher, Kai-Steffen Jens: Strictness of Rate-Latency Service Curves. In: 2nd Workshop on Network Calculus (WoNeCa-2). Bamberg, Germany : 2014. |
Institution: Lehrstuhl für Informatik 7 (Rechnernetze und Kommunikationssysteme)
|
|