Routing mit Qualitätsgarantien

Die Hauptaufgabe einer Routing-Schicht für QoS besteht darin, gegenüber den Anwendungen Zusagen über die Zustellung von Paketen zu geben. Diese Garantien betreffen die bereitgestellte Bandbreite, die Laufzeit der Pakete und die Verlustraten. Die genauen Anforderungen muss die Anwendung über eine festgelegte Schnittstelle spezifizieren, woraufhin die QoS-Schicht prüft, ob eine Erfüllung möglich ist, und die Ressourcen reserviert. Danach muss sie stetig kontrollieren, ob die Verbindung nach wie vor hinreichend ist und auftretende Garantieverletzungen der Anwendung mitteilen.

Den zweiten wesentlichen Bestandteil der vorliegenden Arbeit bildete die Entwicklung und Implementierung eines Protokolls, welches diesen Anforderungen genügt. Im Folgenden wird der grundsätzliche Aufbau des Protokolls und seiner Komponenten vorgestellt und detailliert auf die einzelnen Bestandteile eingegangen. Daraufhin wird dargelegt, welche Garantien das Protokoll gewährleisten kann und worauf diese im Einzelnen beruhen. Schließlich wird die Implementierung mit ihren spezifischen Details vorgestellt.

Aufgaben und Lösungskonzepte

Um in einem Netzwerk für eine Verbindung Ressourcen garantieren zu können, müssen diese zunächst auf allen beteiligten Knoten reserviert werden. Wenn die Reservierung bestätigt ist und QoS-Daten übertragen werden, muss die Verbindung ständig überwacht werden, um Ausfälle schnell zu erkennen und die Anwendung zu benachrichtigen.

Reservierung

Das Reservieren einer QoS-Verbindung erfordert eine Signalisierung der Anforderungen vom Sender zum Empfänger und eine Rücksignalisierung der Bestätigung oder Ablehnung. Dazu gibt es zwei grundlegende Verfahren. Die Reservierung kann in-band (als Zusatzfeld in normalen Datenpaketen) oder out-of-band (mit im Voraus ausgetauschten Zusatzpaketen) erfolgen.

Obwohl der geringere Overhead für die In-Band-Arbeitsweise spricht, hat diese andere Nachteile. So sind die Anwendungsanforderungen nicht von vorn herein erfüllt, sondern werden erst nach dem Verbindungsaufbau signalisiert und bestätigt bzw. abgelehnt. Daher können die QoS-Anforderungen auch nicht bei der Pfadsuche berücksichtigt werden, was zur Verwendung von Pfaden führen kann, welche die Garantien nicht anbieten können.

Dies macht eine der eigentlichen Verbindung vorangehende Out-Of-Band-Reservierung sinnvoller, die mit der Suche eines adäquaten Pfades verbunden ist. Dort greifen dann die Garantien für alle versendeten Datenpakete und es ist von vorn herein klar, dass die gefundene Route der Anwendung genügt.

Pfadsuche für QoS

Die Pfadsuche erfolgt analog zum Best-Effort-Routing nach dem Fish-Eye-Prinzip, indem das Paket immer ausgehend vom lokalen Weltmodell in Richtung des Empfängers weitergeleitet wird. Zusätzlich müssen auf dem Weg aber von jedem Gateway-Knoten Slots in seinem Ziel-Cluster reserviert werden, um die spätere Datenübertragung zu gewährleisten. Die Anzahl der Slots (und damit die Bandbreite der Verbindung) wird dabei von der Anwendung vorgegeben.

Für eine Pfadreservierung müssen Informationen darüber vorliegen, auf welchen Links noch genügend Bandbreite verfügbar ist, und wo die Verbindung nicht mehr entlanggeführt werden kann. Dieses kann proaktiv übermittelt werden, indem das Weltmodell mit den freien Bandbreiten einzelner Knoten bzw. Cluster angereichert wird. Ein solcher Ansatz führt aber dazu, dass nach jedem Routen-Auf- und Abbau sich die Bandbreiten-Daten der beteiligten Knoten ändern, was zusätzliche Netzbelastung durch Weltmodell-Updates nach sich zieht. Außerdem kann es immer noch passieren, dass durch veraltete Informationen eine Route durch einen Cluster gelegt wird, der die Bandbreite nicht mehr anbieten kann.

Aus diesen Gründen wurde für die Bandbreitenreservierung ein optimistisches reaktives Verfahren gewählt: Es wird davon ausgegangen, dass auf dem kürzesten Pfad hinreichend Bandbreite vorhanden ist, und wenn diese Annahme nicht erfüllt wird, so wird zur Laufzeit mit Hilfe eines verteilten Backtracking-Verfahrens um den Engpass herum geleitet.

Dazu überprüft jedes Gateway, der an einem QoS-Verbindungsaufbau teilnimmt, ob in dem Cluster, der zum Ziel führt, genug Bandbreite verfügbar ist. Ist dies nicht der Fall, schließt er diesen Cluster von der Pfadsuche aus und nimmt den nächsten mit dem kürzesten Weg. Findet er über keinen seiner Cluster einen Weg, so gibt er das Paket an seinen Vorgänger zurück, der weitere alternative Pfade ausprobiert. Die Liste der bereits überprüften Cluster wird dabei auch an den Vorgänger übertragen, so dass er diese nicht mehr in Betracht zieht.

Überwachung und Signalisierung

Für die Mitteilung von erfolgreichen und gescheiterten Verbindungsaufbauversuchen sowie zur Meldung von Topologieänderungen, die eine Route unbenutzbar machen, werden weitere Kontrollnachrichten benötigt. Dabei müssen Topologieänderungen auf jedem Knoten überwacht und mit der Routing-Tabelle für QoS abgeglichen werden, um zerstörte Verbindungen zu erkennen.

Dies sollte zum einen periodisch erfolgen, um Timeouts zu erkennen, und zum anderen bei Änderungen der Nachbarschaft stattfinden, um auf zusammengebrochene Verbindungen sofort reagieren zu können. Zudem müssen die von anderen Knoten versendeten Kontrollnachrichten ausgewertet und weitergegeben werden.

Optimistische Reaktive Pfadsuche

Die Pfadsuche für eine QoS-Verbindung unterscheidet sich in zwei Aspekten vom Best-Effort-Routing: Die Menge der möglichen Pfade zum Ziel ist geringer, weil nicht alle Cluster auf dem Weg die für die Verbindung angeforderten Garantien anbieten können. Außerdem kann jedes Best-Effort-Paket einen anderen Pfad zum Ziel einschlagen, während QoS-Pakete durch die erforderliche Reservierung an die am Anfang gewählte Route gebunden sind.

Zunächst wird optimistisch davon ausgegangen, dass alle Cluster auf der vom Weltmodell bestimmten kürzesten Strecke zum Ziel die von der Anwendung geforderte Bandbreite bereitstellen können. Um das zu überprüfen, wird das Anfragepaket von Gateway zu Gateway auf dem Pfad zum Ziel weitergegeben und dabei jeweils Bandbreite in den Clustern dazwischen reserviert.

Scheitert eine der Reservierungen, so sucht das Gateway, welches den Fehler feststellt, einen alternativen Pfad. Wenn es keinen alternativen Pfad findet, signalisiert es seinem Vorgänger, dass dieser eine neue Route finden soll.

Zu diesem Zweck führt jedes Paket eine Liste der bereits besuchten Cluster, sowie der Cluster, von denen bekannt ist, dass sie zu wenig freie Bandbreite besitzen. Erstere dient der Vermeidung von Routing-Schleifen, in letztere werden alle die Cluster als Bad Guys eingetragen, die die Reservierungsanforderung abgelehnt haben. Beide Listen haben eine vom Initiator der Verbindung vorgegebene Höchstgröße: Wird diese erreicht, dann wird ein Scheitern des Verbindungsaufbaus zurücksignalisiert.

Bei der Pfadberechnung wird die Bad-Guy-Liste dem Weltmodell übergeben, Der Dijkstra-Suchalgorithmus wird dann erneut durchgeführt, allerdings werden keine durch die übergebenen Bad Guys führenden Verbindungen berücksichtigt. Durch die vorhandenen globalen Link-State-Daten ist das Weltmodell dann in der Lage, trotz der eingeschränkten Knoten-Auswahl alternative Pfade aufzufinden, sofern sie existieren.

Figure 4.1: Optimistische Reaktive Pfadsuche: Beispiel

Am Beispiel sieht das wie folgt aus (Abb. 4.1): Knoten 1 versucht eine QoS-Verbindung zu Knoten 10 herzustellen. Dazu bestimmt er den kürzesten Pfad, der über Cluster 3 und Gateway 5 führt. Er reserviert daraufhin die nötige Bandbreite beim Cluster-Head und versendet das Initialisierungspaket an Knoten 5 (Schritt 1). Knoten 5 bestimmt wiederum den kürzesten Pfad zu Knoten 10. Er stellt fest, dass das Ziel bereits in einem seiner Cluster ist und über den Head von Cluster 9 erreicht werden kann. Dazu versucht er eine Bandbreitenreservierung in Cluster 9 (Schritt 2). Diese wird jedoch vom Head abgelehnt (3), und daraufhin wird Cluster 9 im Paket als Bad Guy vermerkt. Das Weltmodell wird erneut nach einem Pfad befragt, berücksichtigt dabei die Nichterreichbarkeit über Knoten 9 und gibt Cluster 8 als Ziel aus. Daraufhin reserviert Knoten 5 die Bandbreite in Cluster 8 und versendet die Anforderung weiter (Schritt 4).

Struktur des QoS-Routing-Systems

Das QoS-Modul ist das Bindeglied zwischen der Clustering-MAC-Schicht, deren Weltmodell und der QoS-Anwendung (Abb. 4.2).

Nach oben hin kommuniziert das Modul mit der Anwendung, welcher es erlaubt, Verbindungen aufzubauen, Statusmitteilungen über bestehende Verbindungen zu erhalten und Pakete zu versenden und zu empfangen.

Figure: Einordnung des QoS-Moduls

Von der MAC-Schicht bezieht das QoS-Modul das Weltmodell und benutzt deren Slot-Reservierungs-Schnittstelle, sowie die Funktionen zum Paketversand und zur Auswertung empfangener Pakete.

Figure: Komponenten des QoS-Moduls

Damit das QoS-Routing funktioniert, müssen zahlreiche Aufgaben erfüllt werden. Für eine bessere Modularität erfolgt die Abarbeitung der Teilaufgaben von einzelnen Komponenten, die miteinander interagieren, um die Gesamtanforderungen zu bewältigen. Eine Übersicht darüber findet sich in Abb. 4.3, das Zusammenspiel der Komponenten und ihre Funktionsweise wird im Folgenden erklärt. Ihre Interaktion lässt sich am besten am Ablauf einer Reservierung veranschaulichen.

Ablauf einer Reservierung

Eine Anwendung, die eine QoS-Verbindung aufbauen will, richtet ihre Anfrage zunächst an den Reservierer/Pfadsucher. Dieser überprüft mit Hilfe des Weltmodells, ob ein Pfad zum Zielknoten aufgebaut werden kann, und startet eine Slot-Reservierung für den Cluster, durch den diese Verbindung geht. Er fügt einen Eintrag in die Routing-Tabelle ein, markiert diesen als offene lokale Reservierung und fügt ein Initialisierungspaket mit den Daten der Verbindung hinzu. Sobald die Reservierung erfolgt ist, wird dies von der MAC-Schicht an den Reservierer signalisiert, und dieser setzt den Status der Route auf Remote-Reservierung. Wenn der dazugehörige Cluster-Head das nächste Mal Daten anfordert, wird das Initialisierungspaket vom Scheduler an ihn ausgeliefert. Danach wartet der Knoten, bis eine Rückmeldung zurückkommt oder die Wartezeit überschritten wird. Letzteres überwacht der Monitor und meldet es an die Anwendung, die dann einen neuen Verbindungsaufbau versuchen kann.

Empfängt der nächste Knoten ein Initialisierungspaket, leitet sein Auswerter es an den Reservierer weiter, wo die QoS-Anforderung genau wie ein lokaler Verbindungsaufbau behandelt wird.

Erreicht die Aufbaunachricht schließlich den Empfänger, generiert dieser daraufhin eine Bestätigung, die den selben Pfad zurückgeht. Dabei setzen alle beteiligten Stationen die Route auf ,,reserviert''. Wenn der Sender die Bestätigung erhält, ist die Route vollständig aufgebaut und die Anwendung kann Pakete mit der ihr nun zugesicherten Bandbreite versenden.

Wenn Pakete verschickt werden, wird der Timeout-Wert der zugehörigen Verbindung auf allen Gateways aktualisiert und die Route bleibt in deren Tabellen erhalten. Verschwindet der Sender plötzlich, so findet keine Erneuerung mehr statt und die Einträge werden als ,,veraltet'' markiert und dann gelöscht.

Routing-Tabelle

Zu jeder Verbindung, die über einen Knoten läuft (unabhängig davon, ob der Knoten Sender, Empfänger oder Gateway ist), muss dieser bestimmte Informationen speichern (Tabelle 4.1).

Table: Inhalt der Routing-Tabelle pro Verbindung

Zunächst gehört dazu eine eindeutige Kennzeichnung der Verbindung, die aus der Sender-Knoten-Id und einer vom Sender vergebenen eindeutigen Routen-Id aufgebaut ist. Diese beiden Werte zusammen kennzeichnen eine Verbindung eineindeutig und werden zur späteren Zuordnung von Paketen zu dieser Verbindung eingesetzt.

Der Zustand der Reservierung wird auch in der Tabelle abgelegt. Daran kann das Gateway erkennen, ob gerade eine lokale Reservierung bearbeitet wird und welche Aktionen mit ankommenden Paketen, die zu dieser Verbindung gehören, durchgeführt werden müssen.

Weiterhin muss bei jeder Verbindung vermerkt werden, welche Bandbreite dieser zugesichert wurde - entsprechend dem Cluster-Schema, auf dem das Routing basiert, wird diese Bandbreite in Slots gemessen. Daher befindet sich in der Routenbeschreibung die Anzahl der für die Verbindung reservierten Slots.

Um Datenpakete weiterzuleiten, muss der Nachfolger, also der Knoten, an den die Datenpakete weitergesendet werden, abgespeichert werden. Um Verbindungsunterbrechungen zu bemerken, wird außerdem der Vorgänger mit abgelegt. Zusätzlich wird die Verbindung über einen Timeout abgesichert - läuft dieser ab, ohne dass Pakete übertragen wurden, so kann die Verbindung stillschweigend abgebaut werden.

Pfadsucher

Da einzelne Knoten nicht über ein vollständiges und aktuelles Gesamtweltmodell verfügen und ihre Informationen über entfernte Knoten nicht auf dem neuesten Stand sind, ist die vollständige Pfadberechnung durch den Sender weder für Best-Effort noch für QoS zweckmäßig.

Daher wird das Weltmodell bei beiden Verbindungsklassen nur für die Bestimmung der Richtung verwendet, ausgehend von der Annahme, dass die Knoten sich im Netz nicht schnell bewegen, dass alte Informationen nicht vollkommen irreführend sind und dass die Weltmodelle der Knoten näher zum Ziel auch präziser sind.

Für QoS-Pakete muss die Route nur beim Verbindungsaufbau berechnet werden, danach ist der Pfad für Datenpakete vorgegeben und braucht nicht neu ermittelt werden. Die Pfadsuche erfolgt verteilt auf den Gateways, ausgehend von dem Initiator der Verbindung. Das grundsätzliche Verfahren arbeitet zunächst genauso wie bei Best-Effort-Paketen - aus dem eigenen Weltmodell wird bestimmt, welcher Nachbar dem Ziel am nächsten ist. Allerdings werden dabei zwei Einschränkungen in die Weltmodell-Sicht integriert:

Cluster, die im gerade weitergeleiteten Paket als Bad Guys markiert sind, also solche, die bereits angefragt wurden und die Bandbreitenkriterien nicht erfüllen, werden komplett übergangen. Dadurch vermeidet der Algorithmus bereits bekannte Engpässe im Netzwerk. Kann keine alternative Strecke um die Engpass-Cluster herum ermittelt werden, so wird der Vorgänger-Knoten darüber informiert, der daraufhin wenn möglich einen anderen Pfad probiert. Die Gesamtanzahl der Backtracking-Versuche ist dabei sowohl durch die Vorgabe eine maximale Suchtiefe im Paket als auch durch die Größe des mobilen Netzwerks begrenzt.

Reservierer

Wenn der Pfadsucher unter Berücksichtigung der Bad Guys einen Pfad zum Ziel gefunden hat, wird die Verbindung in die Routing-Tabelle eingetragen und der Reservierer fordert bei der MAC-Schicht eine Erhöhung der Slots für den eigenen Knoten im Zielcluster an. Bis diese abgeschlossen ist, verbleibt das Initialisierungspaket in einem Zwischenpuffer und die Routing-Tabelle enthält einen entsprechend markierten Eintrag.

Wenn die MAC-Schicht die erfolgreiche Reservierung mitteilt, wird das Init-Paket zum Versand freigegeben, bei einer Ablehnung wird der Ziel-Cluster als Bad Guy eingetragen und der Pfadsucher mit einer neuen Routen-Berechnung beauftragt.

Paket-Scheduler

Ein Knoten kann nur asynchron Pakete verschicken - der Sendezeitpunkt wird von der MAC-Schicht (bzw. vom Cluster-Head) vorgegeben. Eine Anwendung, die QoS-Datenpakete versenden möchte, kann daher warten, bis der Knoten vom Head zum Datenversand aufgefordert wird, und ihr Paket dann generieren. Weitergeleitete Pakete dagegen müssen in einem Puffer zwischengespeichert und auf Anfrage des entsprechenden Cluster-Heads gesendet werden.

Dazu wird der Paket-Zwischenpuffer bei einer Cluster-Head-Anfrage nach QoS-Datenpaketen durchsucht, die in diesen Cluster zu verschicken sind. Findet der Scheduler ein solches Paket, so liefert er es als Antwort an den Head aus. Liegen keine Datenpakete vor, so wird überprüft, ob QoS-Metapakete (Fehler oder Routenaufbaunachrichten, die keine reservierten Slots und damit eine geringere Priorität haben) in diesen Cluster verschickt werden müssen.

Liegen weder QoS-Daten- noch Meta-Pakete zum Versenden in den entsprechenden Cluster vor, so gibt der Scheduler die Kontrolle zurück und es können Best-Effort-Pakete oder Weltmodell-Informationen versendet werden.

Paket-Auswertung

Bei empfangenen Paketen ruft die MAC-Schicht über die entsprechende Callback-Routine den Paketauswerter auf. Dieser überprüft, ob es sich um QoS-Frames handelt und gibt ansonsten die Kontrolle sofort zurück. Pakete, die eine neue QoS-Verbindung initiieren, werden an den Reservierer zur weiteren Bearbeitung weitergegeben, weiterzuleitende QoS-Datenpakete in die entsprechenden Slots in der Routing-Tabelle (die gleichzeitig als Zwischenpuffer dient) eingetragen. Wird ein an diesen Knoten adressiertes QoS-Datenpaket empfangen, so wird die Anwendung benachrichtigt und kann den Inhalt auswerten.

Empfängt der Knoten Bestätigungspakete für eine über ihn führende Route, so wird der Reservierungsstatus in der Routing-Tabelle bestätigt und das ACK-Paket weiter an den Vorgänger in der Pfad-Kette gesendet.

Werden QoS-Ablehnungspakete empfangen, so gibt es einige Besonderheiten. Gehört die Ablehnung zu einer Route, die gerade aufgebaut wird, so muss ein neuer Pfad bestimmt werden. Verläuft der neue Pfad durch einen anderen Cluster als bisher, muss die Reservierung im vorherigen aufgehoben und im neuen angefordert werden. Gehört die Ablehnung zu einer bereits komplett aufgebauten Verbindung, oder hat das QoS-Init-Paket seine maximale Suchtiefe/Breite erreicht, so werden die reservierten Slots freigegeben und eine Ablehnung an den Vorgänger geschickt.

Monitor

Ein wesentlicher Bestandteil in einem QoS-System ist eine Überwachungsinstanz, die den Ist- und Soll-Zustand der reservierten Ressourcen miteinander vergleicht und Diskrepanzen an die Anwendung meldet.

Dazu müssen mehrere Mechanismen miteinander kombiniert werden. Zunächst einmal muss die Routing-Tabelle periodisch auf abgelaufene Timeouts überprüft und gegebenenfalls Reservierungen rückgängig gemacht und Einträge gelöscht werden.

Der zweite Mechanismus überprüft die von der MAC-Schicht gelieferten Nachbarschaftsinformationen. Verliert der Knoten die Zugehörigkeit zu einem Cluster, so müssen alle durch diesen Cluster führenden Routen entfernt werden. Weiterhin müssen die Nachbarschaftsbeziehungen der eigenen Cluster-Heads überprüft werden, um den Ausfall von Gateway-Knoten festzustellen.

Für jeden dieser Ausfälle muss ein Benachrichtigungspaket über den Routenausfall generiert werden. Dabei muss unterschieden werden, ob der Ausfall auf dem Pfad vor dem eigenen Knoten (also im Vorgängercluster) oder nach dem eigenen Knoten (im dem Ziel zugewandten Cluster) stattfand. Die Ausfallnachricht wird dabei in die jeweils andere Richtung gesendet. Da der Ausfall auf beiden Seiten erkannt wird, werden zwei Signalisierungspakete von der Bruchstelle aus zum Sender und zum Empfänger gesendet, so dass die Route schnell abgebaut wird.

Der letzte Monitoring-Mechanismus besteht darin, Ausfallnachrichten von anderen Knoten auszuwerten, betroffene Routen zu dereservieren und die Nachrichten weiterzuleiten. Die Weiterleitung erfolgt dabei an den in der Routing-Tabelle vermerkten Knoten und nicht auf dem direkten Weg zum Ziel - denn die Nachricht ist auch an alle Zwischenstationen gerichtet, die auf dem reservierten Pfad liegen.

Dadurch, dass die Unterbrechung eines Links von beiden Seiten erkannt wird und beide Gateway-Knoten eine Benachrichtigung versenden, werden die Reservierungen auf beiden Seiten schnell abgebaut und Sender und Empfänger zügig informiert.

Bekommt ein Gateway-Knoten ein Datenpaket für eine nicht in seiner Routing-Tabelle enthaltene Verbindung, so ist diese höchstwahrscheinlich zuvor durch einen Timeout gelöscht worden. In diesem Fall erzeugt das Gateway eine Ausfallnachricht und schickt sie zurück, damit der Vorgänger die Route abbauen und der Sender eine neue aufbauen kann.

Da die Dereservierungsnachrichten als Best-Effort-Pakete verschickt werden, ist deren Verlust auf dem Weg nicht auszuschließen. Aus diesem Grund erfolgt die doppelte Absicherung über Nachrichten und Timeouts - geht eine Abbaunachricht verloren, so wird die Route trotzdem abgebaut, jedoch erst nach dem der Timeout erreicht wurde. Wird die Route danach wieder verwendet, so bemerkt das Gateway die Diskrepanz und schickt ein Dereservierungspaket. Dasselbe passiert auch, wenn eine Route nur teilweise abgebaut wurde und der Timeout noch nicht erreicht worden ist - es wird eine neue Abbaunachricht erzeugt und die restliche Route abgebaut.

Figure 4.4: Signalisierung einer Routenunterbrechung

In Abbildung 4.4 wird eine zuvor aufgebaute QoS-Verbindung (1 $\rightarrow$ 5 $\rightarrow$ 10; Cluster-Heads 3 und 8) zwischen den Knoten 5 und 8 unterbrochen. Der QoS-Monitor auf Knoten 5 bekommt diese Information unmittelbar von seiner MAC-Schicht und erzeugt eine Abbaunachricht, die zu seinem Vorgänger, Knoten 1, geschickt wird. Die in Cluster 10 reservierte Bandbreite kann dabei nicht mehr explizit freigegeben werden, da keine Verbindung mehr zum Head besteht.

Knoten 10 beobachtet die Nachbarschaft seines Cluster-Heads 8 und stellt darüber (gepunktete Linie) fest, dass Knoten 5 nicht mehr im Cluster ist. Daher wird die lokale Anwendung über den Zusammenbruch informiert und die Route gelöscht.

Knoten 1 bekommt die Nachricht von Knoten 5 (Bogenpfeil 5 $\rightarrow$ 1) und informiert die Anwendung. Danach teilt er dem Head 3 mit, dass er weniger Slots benötigt und entfernt auch den Eintrag aus der Routing-Tabelle.

Implementierung

Dieser Abschnitt beschreibt wichtige Implementierungsdetails des QoS-Moduls. Dazu gehören neben einigen internen Strukturen das Paketformat und die Schnittstellen zur Anwendung und zur MAC-Schicht.

Einbindung ins System

Wird das QoS-Modul geladen, bindet es sich in die selben Rückruf-Schnittstellen ein wie das Best-Effort-Routing, allerdings mit einer höheren Priorität als dieses (Abb. 4.5). Zusätzlich verwendet es das MAC-Weltmodell für die Berechnung von Routen. Danach wird das QoS-Modul im Object Repository vermerkt, was es der Anwendung erlaubt, eine Referenz darauf zu bekommen.

Gegenüber der Anwendung werden Sende- und Empfangs-Callbacks für QoS-Pakete (QOS/fillpacketHooks, QOS/recvHooks) bereitgestellt. Dazu kommt eine Funktion zum Reservieren von Routen (startReservation()), die den Zielknoten, die erforderliche Bandbreite und eine Rückruffunktion für die Fehler- und Erfolgssignalisierung als Parameter erwartet.

Figure: Verwendung von Hooks für die QoS-API

Paketaufbau für QoS

Für QoS-Verbindungen gelten etwas andere Regeln als für Best-Effort-Datenverkehr. Hier speichert jedes Gateway Zustandsinformationen, so dass diese nicht mehr im Paket übertragen werden müssen. Das macht den Netzwerk-Overhead geringer, erfordert aber mehr Speicher auf den Stationen als der Versand von Best-Effort-Paketen.

Entsprechend ist der Header von QoS-Paketen (Tabelle 4.2) schlanker als der von Best-Effort-Daten. Neben der eindeutigen Routen-Kennung, bestehend aus Absender- und Routen-Id, enthält er das nächste Gateway (das zur Weiterleitung des Pakets erforderlich ist) und den Pakettyp. Je nach Pakettyp weicht der weitere Aufbau des Pakets ab.

Table: QoSPacket-Datenfelder

Table: QoSPacket: Datenfelder Routen-Initialisierung

Initialisierungspakete führen weitere Datenfelder (Tabelle 4.3), die erforderlich sind, damit alle Zwischenstationen die Route reservieren können. So wird dort der Zielknoten und die Bandbreite abgelegt. Anhand des Ziels berechnet das Gateway die weitere Route, auf der das Paket versendet wird. Im Unterschied zu Best-Effort-Routing wird dabei aber die Liste der ,,Bad Guys'' aus dem Paket ausgewertet - diese Cluster werden bei der Pfadsuche nicht als Möglichkeit betrachtet.

Für das Marshalling der Daten, also die Umwandlung aus den verwendeten Datentypen in das an die MAC-Schicht übergebene Byte-Feld wurde die Klasse QoSPacket eingeführt. Bei der Initialisierung muss ihr eine BcPacket-Instanz, also ein Paket der MAC-Schicht übergeben werden, danach werden alle Schreib- und Leseoperationen direkt in dem Datenfeld des MAC-Pakets durchgeführt.

QoSPacket stellt Get- und Set-Methoden für alle in den Tabellen 4.2 und 4.3 vorgestellten Datenfelder, überprüft aber vor dem Zugriff, ob der Inhalt der PktType-Variable diesen Zugriff erlaubt.

QoS-Routing-Tabelle

Die Routing-Tabelle ist ein zentrales Element des QoS-Moduls. Sie übt zwar keine eigenen Aktivitäten aus, wird aber von allen anderen Teilkomponenten verwendet. Sie dient auch als Ablage für Status- und Datenpakete, damit diese effizient über die Routen-Id gefunden werden können.

Table: QoS-Routing-Tabelle: Elemente eines Eintrags

Zu jeder über den Knoten führenden Route enthält die Routing-Tabelle detaillierte Informationen (Tabelle 4.4). Das erste Feld enthält den Status der Reservierung, der zum Anfang der Reservierung auf LocalReserving gesetzt wird, während die für die Verbindung erforderliche Bandbreite im lokalen Cluster angefordert wird. Danach wird der Status auf RemoteReserving gesetzt und das Initialisierungspaket weitergesendet. Nach Erhalt der Bestätigung vom Zielknoten gilt die Verbindung als reserviert (Reserved). Wird der Timeout überschritten oder die Verbindung abgebaut, so wird der Eintrag zunächst auf Closing gestellt und einige Zeit später komplett entfernt.

Das Feld lastnode ist nur auf dem Zielknoten true, es signalisiert, dass die Daten an die Anwendung und nicht an den nextHop weiterzuleiten sind.

In bandwidth ist die Anzahl der zu reservierenden bzw. der reservierten Slots abgelegt. Die Reservierung bezieht sich auf den in nextHead gespeicherten Cluster. Die anderen NodeId-Variablen enthalten den Pfad vor und nach dem Knoten (Abb. 4.6).

Figure: Sicht eines Gateways auf die QoS-Route

Die timeout-Variable enthält den Zeitpunkt, an dem der Eintrag nicht mehr gültig ist und data ist ein Zeiger auf ein Paket, welches in der Warteschlange des Gateways verbleibt. Dies wird durch das asynchrone Polling der Cluster-Heads erforderlich: Jedes Paket muss zwischengespeichert werden, bis der Knoten vom nextHead zum Weiterleiten aufgefordert wird. Je nach Zustand der Route kann es sich dabei um ein Statuspaket (Routenaufbau oder -abbau) oder um ein Datenpaket handeln. In dem Fall, dass für die Route mehrere Slots reserviert wurden, kann es bei ungünstigem Polling-Verhalten dazu kommen, dass mehrere Datenpakete abgelegt werden müssen. Dann wird über den data-Zeiger eine verkettete Liste der abgelegten Datenpakete realisiert.

Ändert sich der Zustand der Reservierung, so werden eventuell zwischengespeicherte Pakete gelöscht - so wird verhindert, dass veraltete Informationen versendet werden bzw. Daten, für die keine Reservierung mehr besteht, das Netzwerk überfüllen.

Zugriff auf Routing-Tabellen-Einträge

Die Routing-Tabelle weist zwei unterschiedliche Zugriffsmuster auf: Wird ein QoS-Paket empfangen, muss anhand der Sender-Id und Routen-Id aus dem Paket der entsprechende Eintrag in der Tabelle ermittelt werden. Bei hohen Paketraten empfiehlt sich an dieser Stelle ein schneller Zugriffspfad, der mit einem balancierten Baum umgesetzt werden kann. Die Standard Template Library von C++ [Str00] bietet bereits eine entsprechende Datenstruktur (stl::map), die hier eingesetzt wird.

Ein weiteres Zugriffsmuster kommt beim Versenden von Paketen zum Tragen: Dort müssen Einträge gefunden werden, die einen bestimmten Cluster als nextHead haben und ein Paket zum Versand zwischenspeichern. Für dieses Muster wurde keine Optimierung implementiert; dies kann aber bei Bedarf nachgeholt werden.

Schließlich müssen regelmäßig alle Einträge auf abgelaufene Timeouts und unterbrochene Verbindungen kontrolliert werden. Dazu wird mit Hilfe eines Iterators der Inhalt der stl::map traversiert und jedes Element einzeln untersucht.

Reservierungsablauf

Figure: Ablauf der QoS-Reservierung

Will ein Knoten eine Route aufbauen, erzeugt er zunächst eine eindeutige Routen-Id. Dazu führt er einen Zähler, dessen Wert in die Id der neuen Verbindung übernommen wird und der danach inkrementiert wird.

Steht die Routen-Id fest, wird die Reservierung durchgeführt (Abb. 4.7). Dazu wird erst mit Hilfe des Weltmodells bestimmt, in welchen Cluster die Verbindung führt. Danach wird ein eine Slot-Reservierung für diesen Cluster gestartet. Ist die Reservierung erfolgreich, so wird beim nächsten Poll-Request ein Init-Paket in diesen Cluster geschickt.

Sind im Ziel-Cluster nicht mehr genügend Zeitschlitze frei, so gibt es zwei Möglichkeiten - entweder das Gateway versucht, einen Pfad über einen anderen Cluster zu finden, oder - falls keine alternativen Pfade existieren - wird eine Ablehnung an den vorangegangenen Knoten gesendet. Dabei entspricht die Ablehnung von ihrem Aufbau her dem Init-Paket und enthält entsprechend den Cluster mit unzureichender Bandbreite in der Bad-Guy-Liste.

Diese Traversierung wird solange durchgeführt, bis das Ziel erreicht ist, oder die Bad-Guy-Liste keine Cluster mehr aufnehmen kann. Im letzten Fall wird ein NACK-Paket an den Sender zurückgeschickt.

Die Beschränkung der Hop- und Traversierungstiefe erlaubt es, die maximale Anzahl der zu durchlaufenden Knoten und damit auch die maximale Laufzeit des Pakets im Voraus festzulegen.

Garantien

Im Folgenden wird betrachtet, wie schnell QoS-Datenpakete innerhalb des Netzwerks zugestellt werden können. Diese Betrachtung gilt eingeschränkt auch für QoS-Statusnachrichten und Multi-Hop-Daten, nämlich dann, wenn keine Pakete mit einer höheren Priorität im Netzwerk unterwegs sind. Die höchste Priorität besitzen QoS-Daten, danach folgen QoS-Verbindungs- und Fehler-Pakete, gefolgt von regulären Best-Effort-Paketen. Die geringste Priorität haben Pakete mit Weltmodell-Daten. Entsprechend kann ein Best-Effort-Paket in der selben Zeit wie ein QoS-Paket zugestellt werden, sofern kein Netzwerkengpass vorliegt und die Warteschlangen aller beteiligten Knoten leer sind. Allerdings kann der Sender diese zeitlichen Anforderungen nicht vorhersagen, da er den Pfad zum Ziel im Gegensatz zu einer aufgebauten QoS-Verbindung nicht kennt.

Sind die Warteschlangen der Gateways dagegen nicht leer, so ist die Verweildauer des Pakets auf den Zwischenstationen entsprechend länger - die Auslieferung gleich priorisierter Daten erfolgt nach dem FIFO-Prinzip.

Die MAC-Schicht erlaubt es, zuverlässig Pakete an andere Knoten im selben Cluster zuzustellen. Sie geht dabei von der Annahme aus, dass ein Paket spätestens nach drei Zustellungsversuchen garantiert ankommt. Um diese nicht auszuschöpfen, wird allerdings bei jeder Runde überprüft, ob das Paket in der vorherigen Runde erfolgreich ausgeliefert werden konnte. Im positiven Fall kann der Zeitschlitz dann für andere Informationen verwendet werden, ansonsten wird das Paket der Vorrunde wiederholt.

Die Rundenzeit berechnet sich dabei aus mehreren Faktoren: Eine Runde dauert so lange, bis alle $N$ Cluster-Heads, die überlappungsfrei im selben Sendebereich arbeiten können, ihre $M$ Clients befragt und eine Antwort erhalten haben. Die Zeit für eine Frage (Poll-Request) und die Antwort des Clients hängt dabei hauptsächlich von der Übertragungszeit auf dem Medium ab. Dazu kommt noch die Verarbeitungszeit auf dem Client (Empfang des Pakets, Bearbeitung und Versenden der Antwort), die aber nicht so signifikant ist.

Das Versenden eines üblichen Pakets auf der MAC-Schicht dauert bei einer Brutto-Datenrate von $54MBit/s$ ca. $0.3ms$. Ausgehend von einem Netz, in dem $6$ Cluster mit je $16$ Clients koexistieren können, ergibt das eine Rundenzeit von $16\cdot6\cdot2\cdot0.3ms = 57.6ms$, wenn die Verarbeitungszeit vernachlässigt wird.

Da jedes Datenpaket, das der Head von einem Client empfängt, sofort wiederholt wird, um alle Stationen im Cluster erreichen zu können (es wird nicht davon ausgegangen, dass die Clients untereinander eine Sichtverbindung haben müssen), erreicht es im Idealfall nach $t_{intra} = 0.6ms$ sein Ziel. Scheitert der erste Versand, wird es nach einer Runde wiederholt, kommt also nach $58.2ms$ an. Im schlechtesten Fall, also wenn die Auslieferung drei Runden benötigt, dauert die Zustellung des Pakets $115.5ms$.

Schwieriger ist die Vorhersage der Zustellung über Cluster-Grenzen hinweg. Dafür ist nicht nur die Zustellung innerhalb der Cluster, sondern auch die Wartezeit auf den Gateway-Knoten relevant, bis das Paket vom Head des Zielclusters angefordert wird. Diese Zeit $t_{inter}$ variiert zwischen $0$ und $57.0ms$ (eine Rundendauer abzüglich eines Zeitschlitzes), da jeder Knoten mindestens einmal pro Runde gerufen werden muss und die Aufrufe aus unterschiedlichen Clustern nicht synchronisiert werden können. Da Knoten häufig auch mehr als einmal pro Runde abgefragt werden, ist diese Latenz zudem nicht vorhersagbar, da die Polling-Reihenfolge sich ständig ändert.

Ein Paket, welches von einem Knoten in einen anderen Cluster versendet wird, benötigt für die Zustellung an das Gateway in seinem Cluster $t_{intra}$, für jedes weitere Gateway und für das Ziel jeweils $t_{inter} + t_{intra}$. Dabei ist zu beachten, dass zwischen zwei Gateways immer ein Cluster-Head ist, den diese Berechnung berücksichtigt.

Das ergibt eine maximale Laufzeit von $115.5ms + N\cdot172.5ms$ für eine Strecke über N Gateways. Geht man von einem Medium ohne Übertragungsfehler aus, so sinkt die Zeit auf $0.6ms + N\cdot57.6ms$ bei ungünstiger Cluster-Kopplung bzw. $0.6ms + N\cdot0.6ms$ im idealen Übertragungs-Fall, dies ergibt einen Jitter von $N\cdot57ms$.

Wenn die Auslieferung an einen Cluster-Head erfolgen soll, bzw. wenn ein Cluster-Head der Sender ist, gelten die selben Betrachtungen, da der Head bezogen auf die Aussendung und den Empfang von Paketen einen internen Client emuliert.

Routen-Aufbau

Der Aufbau einer QoS-Verbindung muss als Best-Effort-Anfrage erfolgen, da zu diesem Zeitpunkt noch keine Bandbreite zwischen Start und Ziel reserviert ist. Entsprechend ist eine Vorhersage der Höchstzeitdauer bis zum Empfang der Antwort (ob positiv oder negativ) nur unter der Voraussetzung möglich, dass zeitgleich keine weiteren Verbindungen über die selben Knoten aufgebaut werden.

Das Weltmodell liefert dabei nur einen Richtwert für die Anzahl der Zwischenstationen, der reale Wert muss zur Laufzeit durch die verteilte Pfadsuche bestimmt werden und ist durch den MaxHopCount-Wert nach oben begrenzt. Dazu kommen die möglichen Umleitungen aufgrund unpräziser Weltmodelldaten oder fehlender Bandbreite, deren Begrenzung als MaxBadGuyCount im Paket gelistet ist.

Im Gegensatz zu normalen Best-Effort- und QoS-Datenpaketen kommt beim Verbindungsaufbau aber eine weitere Verzögerung hinzu: Die Zeitschlitze für eine Verbindung muss der Client beim Head anfordern und auf die Bestätigung warten. Die Anforderung kann dabei erst nach einem vom Cluster einmal pro Runde verschickten JoinRequest erfolgen und das Ergebnis wird erst im nächsten JoinRequest bekanntgegeben. Erst danach kann die Verbindungsaufbaunachricht (auf einen Poll des Heads hin) verschickt werden.

Zusammengefasst bedeutet das Folgendes: Ein Gateway empfängt die Nachricht aus einem anderen Cluster (bzw. der Sender von der Anwendung) und startet sofort eine Slot-Reservierung. Diese wird nach dem Ende der laufenden Runde ($0$ - $57ms$) an den Head gesendet und eine Runde später ($+57.6ms$) kommt die Antwort beim Client an. In der folgenden Runde wird der Client von dem Head kontaktiert und versendet das Paket ($+0$ bis $57ms$).