Anwendung der Large Deviations Theorie auf Fragen des Verkehrsmanagements
Final Report Abstract
2.1 Allgemeinverständliche Darstellung der wesentlichen Ergebnisse und der erzielten Fortschritte gegenüber dem Stand des Wissens Das steigende Interesse an der Übertragung von Multimedia Information und anderen Echtzeitanwendungen über das Internet motiviert die Untersuchung von möglichen Dienstgütegarantien. Das Ziel ist immer, die Netzressourcen so effizient wie möglich zu nutzen, ohne Dienstgütegarantien zu verletzen. Auf diesem Wege liefert das vorliegende Projekt zwei wesentliche Beiträge: 1. Eine Methodologie, um die Einhaltung von Echtzeitbedingungen in einem IP Router Netz quantitativ zu erfassen; 2. Ein Verfahren, um eine Minimalzahl von Quellen zu bestimmen, für die Dienstgütegarantien aufgrund eines Invarianzgesetzes ausgesprochen werden können, das bisher nur für unendlich viele Quellen bekannt war (Invarianz der effektiven Bandbreite). Zul. Der so genannte Network Calculus erlaubt es, Verzögerungen und Pufferrückstände netzweit über mehrere Knoten hinweg zu bestimmen. Dazu werden Einhüllende für Ankunfts- und Bedienprozesse betrachtet. Der Statistical Network Calculus ist eine probabilistische Version des ersteren, der mögliche Multiplexgewinne berücksichtigt, während der rechnerische Zugang zu den Dienstgütekenngrößen erhalten bleibt. Betrachtet man eine Abfolge von Knoten im Netz, werden die durch Einhüllende beschriebenen Ankunfts- und Bedienprozesse immer ungenauer erfasst und die resultierenden Schranken, etwa für die Verzögerung, werden immer ungenauer. An dieser Stelle hilft die Idee weiter, Ankunftsprozesse durch effektive Bandbreiten und Bedienprozesse durch den neu geschaffenen Begriff einer effektiven Kapazität zu beschreiben; effektive Bandbreiten haben nämlich die Eigenschaft beim Durchgang durch ein Netz weitgehend invariant zu bleiben und nicht unter einer fortschreitenden Verwässerung ihrer Aussagekraft zu leiden. Diese Aussage gilt zumindest im Grenzfall unendlich vieler Ankunftsprozesse, wobei es sich aber in der Praxis herausstellt, dass schon eine verblüffend kleine Zahl von Quellen für diese Invarianzeigenschaft ausreicht - wie mit dem zweiten wesentlichen Ergebnis dieser Arbeit belegt wird (s.u.). Die erfolgreiche Verknüpfung von effektiver Bandbreite, effektiver Kapazität und Statistical Network Calculus erlaubt es einerseits, Obergrenzen für Verzögerungen und Pufferrückstände zu berechnen und andererseits eine recht enge obere Schranke für die effektive Bandbreite des Abgangsprozesses anzugeben, der ja wieder den Ankunftsprozess für den nächsten Knoten darstellt. Auf diese Art können die gewünschten Schranken der Leistungsparameter Schritt für Schritt auf dem Weg von einem Knoten zum nächsten bestimmt werden. Zu 2. Das zweite wichtige Ergebnis des Projektes ist die Bestimmung der so genannten effektiven Schwelle. Sie wurde unter Nutzung der Large Deviations Theory und des Statistical Network Calculus bestimmt und gibt eine Minimalanzahl von unabhängigen Quellen an, die in einem Multiplex benötigt werden, um die Invarianz der effektiven Bandbreite (in beliebiger Näherung) zu garantieren. Hierfür werden zwei Wege beschritten: Zum einen wurde die effektive Schwelle mit Argumenten der Large Deviations Theory aus Pufferüberlaufwahrscheinlichkeiten berechnet; zum zweiten wurde die schon angesprochene obere Schranke für die effektive Bandbreite des Abgangsprozesses von einem Knoten zur Bestimmung der effektiven Schwelle herangezogen. Schließlich konnten die auf der Invarianz der effektiven Bandbreite beruhenden Netzdimensionierungsregeln, die aufgrund der Kenntnis der effektiven Schwelle jetzt eine reale Bedeutung erhalten haben, gegenüber dem Stand der Wissenschaft weiter präzisiert und verfeinert werden. 2.2 Ausblick auf künftige Arbeiten und Beschreibung möglicher Anwendungen Verkehrsplanung auf der Basis von effektiven Bandbreiten (und ihrer nunmehr fassbaren Invarianz) sowie den effektiven Kapazitäten erlaubt es, verschiedene Aufgaben im Bereich der Netzplanung mit Blick auf Dienstgüteanforderungen präziser anzugeben. Die entwickelte Methodik ist unabhängig von irgendwelchen technologischen Vorgaben und mithin im Bereich drahtgebundener und drahtloser Kommunikation gleichermaßen anwendbar. Zukünftige Arbeiten sollten sich vornehmlich um Erweiterungen mit Blick auf stochastische Bedienprozesse (z.B. bei der drahtlosen Übertragung) sowie um die tatsächliche effektive Bandbreite des Abgangsprozesses (und nicht nur um eine obere Schranke) bemühen.
Publications
- K. Angrishi, U. Killat Analysis of a Real-Time Network using Statistical Network Calculus with Approximate Invariance of Effective Bandwidth, Proceedings 15. ITG/GI-Fachtagung Kommunikation in Verteilten Systemen (KIVS 2007), Bern, Switzerland, March 2007, Springer Verlag, pp. 189-200.
- K. Angrishi,andU.Killat Analysis of a Real-Time Network using Statistical Network Calculus with Effective Bandwidth and Effective Capacity, 14. GI/ITG Konferenz Messung, Modellierung und Bewertung von Rechen- und Kommunikationssystemen (MMB 2008), Dortmund, Germany, March 2008.
- S. Zhang, K. Angrishi, U. Killat, An Attempt to Offer Differentiated Services in An Industrial Real-time Network, Proceedings of the 4rd Polish-German Teletraffic Symposium (PGTS 2006), Wroclaw, Poland, September 2006, pp. 43-53.
