Evaluierung

In diesem Kapitel wird die Funktionsfähigkeit der Weltmodell-Propagation, des Best-Effort-Routing-Protokolls und der QoS-Schicht im Simulator getestet und die Messergebnisse vorgestellt und ausgewertet.

Propagation des Weltmodells

Die Aktualität des Weltmodells ist eine wichtige Grundlage für die Funktionsweise des Routings und der QoS-Übertragung. Die Propagation der Weltmodell-Daten wird allerdings durch reguläre Datenübertragungen verzögert.

Um zu überprüfen, wie schnell sich das Weltmodell in Abhängigkeit von der Netzwerk-Belastung mit anderen Daten ausbreitet, wurde die Geschwindigkeit der Weltmodell-Propagation bei unterschiedlichen Lasten gemessen.

Weltmodell-Korrektheit

Um den Grad der Propagation zu einem bestimmten Zeitpunkt zu bestimmen, wurde ein Maß für die lokale und globale Weltmodell-Korrektheit $k$ bzw. $\mathcal{K}$ eingeführt.

Die lokale Weltmodell-Korrektheit eines Knotens beschreibt die Abweichung seines Weltmodells von der realen Topologie. Sie bestimmt sich aus der Anzahl korrekter (also mit der realen Topologie übereinstimmender) Links abzüglich der inkorrekt im lokalen Weltmodell abgelegten Verknüpfungen (von Links, die nicht mehr tatsächlich existieren).

Um den Wert zu unterschiedlichen Zeitpunkten vergleichen zu können, wird er normalisiert und die auf diese Weise erhaltene relative Angabe verwendet.

Ist ein vorhandener Link dem Weltmodell nicht bekannt, so trägt das zu einem kleineren Wert bei, da die Anzahl der realen Links größer ist als die im Weltmodell. Damit sind sowohl positive als auch negative Abweichungen berücksichtigt.

Der Wert für die lokale Korrektheit kann höchstens $1$ sein, wenn die Abbildung exakt mit der realen Topologie übereinstimmt, er ist $0$, wenn der Knoten keinerlei Weltmodell-Daten hat, und kann negativ werden, wenn die Anzahl falscher Informationen die richtigen überwiegt.

Die globale Weltmodell-Korrektheit ergibt sich als der Durchschnitt der lokalen Korrektheiten aller Knoten. Auch hier gilt, die Werte sind $1$ bei perfekter Propagation im gesamten Netz und werden bei zunehmenden Abweichungen kleiner.

Versuchsaufbau

Um die Weltmodell-Korrektheit zu testen, wurde die zeitliche Qualität der Propagation in unterschiedlichen Belastungsszenarien gemessen. Dazu wurde im Simulator ns-2 ein $1000\times1000m^2$ großes Feld ohne Hindernisse mit 100 zufällig verteilten Knoten erzeugt (weitere Einstellungen in Tabelle 5.1).

Table 5.1: Konfiguration des Simulators

Parameter	Wert
Feldgröße	$1000\times1000m^2$
Anzahl Stationen	$100$
Verteilung Stationen	zufällig
Senderadius	$250m$
Interferenzradius	$500m$
WLAN-Datenrate	$54MBit/s$
Verlustrate	$5\%$
max. Clients pro Cluster	$16$
max. Heads pro Client	$7$
Slot-Länge	$4ms$

Die Messung wurde dabei im 1-Sekunden-Takt ab dem Moment durchgeführt, wenn die ersten Verbindungen zwischen Knoten geschlossen wurden. Dazu gab jeder simulierte Knoten seine unmittelbare tatsächliche Nachbarschaft, sowie sein komplettes Weltmodell zu jedem Messzeitpunkt aus.

Die prozentuale Belastung des Mediums wurde dadurch erzeugt, dass jeder Knoten mit der vorgegebenen Wahrscheinlichkeit 1-Hop-Datenpakete an die MAC-Schicht übertragen hat, wenn er zum Versand aufgefordert wurde. Die verbleibenden Zeitschlitze wurden für die Propagation des Weltmodells eingesetzt.

Der Versuch wurde zunächst ohne Knotenmobilität ausgeführt, was zu einer geringen Fluktuationsrate der Verbindungen führte. Damit wurde untersucht, wie schnell sich das Weltmodell über alle Knoten ausbreitet. Die Netzwerkbelastung wurde dabei von 0 an in 10%-Schritten erhöht. Der Bereich zwischen 90% und 100% wurde zusätzlich in 1%-Schritten gemessen, um das Verhalten unter extrem hoher Last zu studieren.

Danach wurde der Versuch mit Knotenmobilität wiederholt. Das Mobilitätsmodell besteht dabei darin, dass alle Knoten abwechselnd für eine zufällige Zeit zwischen $10$ und $1000$ Sekunden auf ihrer Position verharren und sich dann mit einer festen Geschwindigkeit zwischen $3 - 5 \frac{m}{s}$ zu einem zufällig bestimmten Zielpunkt innerhalb des Terrains bewegen.

Auswertung

Unter normalen Bedingungen (bei einer Netzbelastung bis 90%, Abb. 5.1) sieht man, dass das Weltmodell sich innerhalb weniger Sekunden über das gesamte Netz ausbreitet, und dass die Ausbreitungsgeschwindigkeit von der Netzwerkbelastung abhängt. Interessant ist, dass der Einfluss der Netzwerkbelastung bis zu 80% nur gering ist - ohne Last ist die Weltmodell-Korrektheit nach 3 Sekunden bei 70%, mit 80% Last nach 10 Sekunden. Nimmt die Netzlast um ein weiteres Zehntel zu, dauert es aber 6 Sekunden länger, bis die Korrektheit 70% erreicht.

Dadurch, dass im Verlauf der Simulation einige Links auf- und abgebaut werden, erreicht die Weltmodell-Korrektheit selbst bei geringer Belastung nicht den Idealwert von 100%.

Figure 5.1: Propagation des Weltmodells unter geringer Last

Betrachtet man höhere Netzlasten (Abb. 5.2), muss zunächst der Zeitrahmen der Untersuchung ausgedehnt werden, hier auf 90 Sekunden. Dabei kann man feststellen, dass die Qualität des Weltmodells selbst bei einer Netzwerkauslastung von 99% noch stetig besser wird. Bei einer vollständigen Auslastung des Netzwerks (100%, alle Slots werden für höher priorisierte Daten eingesetzt) jedoch kann das Weltmodell nicht mehr propagiert werden, jeder Knoten hat nur seine eigene Nachbarschaft im Weltmodell und kommt damit bei insgesamt 100 Knoten zu einer Kenntnis von 1% der Topologie.

Figure 5.2: Propagation des Weltmodells unter hoher Last

Figure 5.3: Netzwerktopologie ohne Mobilität nach 90 Sekunden

Abbildung 5.3 zeigt beispielhaft die Netzwerktopologie nach 90 Sekunden in einem Szenario ohne Knotenmobilität.

Figure 5.4: Propagation des Weltmodells bei Knotenmobilität

Knotenmobilität

Betrachtet man die Ausbreitung der Topologiedaten in einem Netz mit sich bewegenden Knoten (Abb. 5.4), sind die Unterschiede zu still stehenden Teilnehmern bei einer Belastung bis 90% nur marginal. Bei 95% Last erkennt man dagegen, dass die Korrektheit sich zwischen 70 und 80% einstellt. Hier halten sich die änderungsbedingten Topologiedaten und die generierte Netzlast die Waage. Wird die Netzlast erhöht, verschiebt sich dieses Gleichgewicht auf eine kleinere Weltmodell-Korrektheit (60% bei 97% Auslastung). Bei 99% Last wird der Gleichgewichtspunkt im Verlauf der Simulation nicht erreicht. Bei kompletter Auslastung findet genau wie bei der vorangegangenen Messreihe ohne Mobilität keine Ausbreitung der Weltmodelldaten statt.

Best-Effort-Routing

Verfügen die Knoten über Topologie-Informationen, können sie Datenpakete über das Netz verschicken. Dabei hängt die Qualität der Übertragung von dem Anteil der erfolgreich übertragenen Pakete an den ausgesendeten Paketen und von der Laufzeit vom Sender zum Empfänger ab.

Versuchsaufbau

Um die Übertragungsqualität zu testen, wurden in einem Simulationsexperiment mit den selben Parametern wie zuvor (Tabelle 5.1) zehn Knoten bestimmt, die jeweils zu einem drei Links entfernten anderen Knoten Datenpakete gesendet haben, die vom Zielknoten zu beantworten waren (Ping-Versand mit der Test-Anwendung aus Abschnitt 3.7.11). Durch den Abstand wurde sichergestellt, dass zwischen den kommunizierenden Stationen jeweils ein Gateway und ein Cluster-Head platziert waren. Auf dem Sender wurde im Versuch die summierte Laufzeit für die Übertragung zum Empfänger und zurück gemessen.

Außer den Ping-Paketen wurden auf dem Medium nur Weltmodell-Datenpakete mit einer geringeren Priorität versendet.

Die Gesamtzeit der Simulationsläufe wurde auf 180 Sekunden erhöht. Um Einflüsse eines noch nicht aufgebauten Weltmodells zu minimieren wurde der Versand der Datenpakete erst 20 Sekunden nach Start der Simulation begonnen. Nach 60 Sekunden Sendezeit (bei $80s$ Simulationszeit) wurde der Versand dann wieder eingestellt, um allen Knoten anschließend Zeit zu geben, ihre Sendewarteschlangen zu leeren und alle sich noch auf dem Weg befindenden Pakete auszuliefern.

In mehreren Versuchen wurde dabei nach und nach die Netzwerklast erhöht, indem die Sendewahrscheinlichkeit der 10 Knoten kontinuierlich von 0% auf 100% erhöht wurde. Dieser Wert gibt an, mit welcher Wahrscheinlichkeit ein Knoten ein Ping-Paket versendet, wenn er vom zum Ziel führenden Cluster-Head kontaktiert wird.

Auswertung

In Abbildung 5.5 ist die Anzahl der versendeten Pakete in Abhängigkeit von der Sendewahrscheinlichkeit abgebildet. Man kann sehen, dass auch bei hoher Netzlast fast alle Pakete zugestellt und beantwortet werden. Die Nichtzustellung ist dabei auf inkorrekte Weltmodell-Daten zurückzuführen, deren Präzision mit steigender Belastung des Netzwerks abnimmt.

Figure: Multi-Hop-Paketzustellung

Abb. 5.6 zeigt die durchschnittlichen Paketlaufzeiten in Abhängigkeit von der Last bei diesem Versuch. Das Diagramm bildet die Mindest- und Höchstwerte sowie den Durchschnitt und die Standardabweichung (senkrechte Striche über dem Durchschnitt) in Abhängigkeit von der Senderate ab. Dabei kann man sehen, dass der Jitter (Differenz zwischen Minimum und Maximum) bei der Best-Effort-Übertragung anfangs moderat ausfällt, aber bei zunehmender Netzwerkbelastung (ab 30%) deutlich ansteigt.

Figure: Multi-Hop-Laufzeiten über 3 Hops

Die Ursache dafür sind zum einen Paketverluste auf dem Medium, die eine Wiederholung des Pakets in der nächsten Runde erforderlich machen, zum anderen aber volllaufende Paketwarteschlangen auf den Gateways, auf denen die Datenpakete nach dem FIFO-Prinzip abgearbeitet werden. Die Mindestlaufzeiten bleiben jedoch gering, da zum Anfang und zum Ende der Versuche die Warteschlangen leer sind und die Pakete damit zügig zugestellt werden können. Ist das Netzwerk dagegen ausgelastet, verzögert sich die Auslieferung deutlich.

Knotenmobilität

Eine Wiederholung der Versuchsreihe mit mobilen Knoten (und dem Mobilitätsmodell aus dem Weltmodell-Versuch) hat ähnliche Ergebnisse bezüglich der Zustellraten (Abb. 5.7) und der Laufzeiten (Abb. 5.8) ergeben. Man kann allerdings sehen, dass bei einer Auslastung von mehr als 90% die Anzahl der korrekt beim Empfänger zugestellten Pakete nicht mit der Senderate zunimmt.

Figure: Multi-Hop-Paketzustellung bei Mobilität

Die Paketlaufzeiten verschlechtern sich dagegen nicht, wenn die Knoten sich bewegen. Auch das ist ein Hinweis darauf, dass die langen Laufzeiten in erster Linie von den vollen Warteschlangen und nicht von anderen Faktoren abhängen. Die maximalen Zustellzeiten sind bei mobilen Knoten z.T. höher, da sich die kommunizierenden Stationen voneinander entfernen können und die Pakete deshalb mehr Zwischenstationen passieren müssen.

Figure: Multi-Hop-Laufzeiten bei Mobilität

Die unkalkulierbaren und z.T. sehr langen Zustellzeiten lassen sich mit den Best-Effort-Mitteln jedoch nicht umgehen, da bei einer Verkleinerung der Warteschlangen Pakete verworfen werden und bei großen Warteschlangen Pakete lange unterwegs sind.

Quality of Service

Um die Latenzzeiten der Datenübertragungen auch ohne das Verwerfen von Datenpaketen gering zu halten, muss ein Prioritätsschema eingesetzt werden, welches Überlastungen an einzelnen Knoten vermeidet. Dieses wird vom QoS-Routing-Modul bereitgestellt, das Verbindungen um Engpässe herum aufbaut und damit einem Volllaufen der Warteschlangen entgegenwirkt. In diesem Abschnitt soll die Qualität dieses Verfahrens überprüft und mit dem Datenversand ohne Garantien in Relation gesetzt werden.

Versuchsaufbau

Zum Testen der Skalierbarkeit wurde in aufeinander folgenden Versuchen die Anzahl der aufzubauenden QoS-Verbindungen von 0 auf die Anzahl der Knoten, also 100, erhöht. Die Sender- und Empfängerknoten (und damit die Pfadlängen) wurden dabei zufällig ausgesucht.

Da QoS-Verbindungen nur in eine Richtung bestehen, wurde statt einem bidirektionalen Paketfluss nur die Laufzeit vom Sender zum Empfänger gemessen. Um die Messwerte mit dem Best-Effort-Routing vergleichen zu können, wurde mit letzterem die selbe Versuchsreihe durchgeführt, bei der Daten direkt (und damit ohne Garantien) versendet wurden. Die Senderate entsprach dabei der Datenrate der QoS-Strecken und die Anzahl der sendenden Knoten wurde nach und nach erhöht.

Um die beiden Verfahren zu vergleichen, wurden die maximalen und durchschnittlichen Paketlaufzeiten gemessen und die Anzahl der ausgelieferten Pakete vermerkt. Beim QoS-Routing wurden zusätzlich die für den Verbindungsaufbau nötigen Zeiten erfasst.

Die Übertragung bzw. Routenreservierung begann 20 Sekunden nach Simulationsstart und wurde 60 Sekunden später eingestellt. Die Gesamtdauer jedes Experiments war 180 Sekunden. Die Versuchsreihen wurden sowohl mit statisch positionierten Knoten als auch mit dem zuvor genutzten Mobilitätsmodell durchgeführt. Da die Ergebnisse sehr ähnlich ausgefallen sind, wird im Folgenden nur auf die Experimente mit beweglichen Knoten eingegangen.

Auswertung

Wie man in Abbildung 5.9 sehen kann, steigen die maximalen und durchschnittlichen Übertragungszeiten bei Best-Effort-Transfers mit der Netzwerkauslastung an. Ihr Anstieg ist in etwa linear, zur besseren Veranschaulichung der stark gestreuten Best-Effort-Maximalzeiten wurde eine Annäherungsgerade eingefügt. Die QoS-Übertragungen bieten dagegen selbst bei hoher Netzwerkbelastung und weiten Verbindungen stabile maximale Latenzzeiten.

Figure: Paketlaufzeiten QoS und Best-Effort

Obwohl die durchschnittlichen Laufzeiten der Best-Effort-Pakete in der selben Größenordnung liegen, kann für deren Zustellung keine Garantie gegeben werden und einzelne Pakete benötigen deutlich länger. Im Gegenzug dazu wurden alle QoS-Pakete in weniger als $13s$ zugestellt.

Dieser Wert erscheint zwar für normale Netzwerke recht hoch, ergibt sich aber in erster Linie aus dem Zeitschlitz-Verfahren der teilnehmenden Cluster. Durch das nicht vom QoS-Modul beeinflussbare Polling-Schema verbleibt jedes Datenpaket einige Zeit auf jedem Gateway des Pfades. Bei Übertragungsfehlern wird die Wartezeit bis zur Wiederholung nochmal deutlich erhöht.

Figure: Paketlaufzeiten von QoS-Verbindungen

Einen deutlich geringeren Einfluss auf die Latenz haben der Versand der Pakete auf dem Medium und die Verarbeitung auf den Zwischenstationen. Da diese Verzögerungen alle Pakete unabhängig von der Cluster-Zusammenarbeit betreffen, gelten sie auch für die schnellsten Pakete, deren Laufzeiten deutlich unter einer Sekunde bleiben (Abb. 5.10). Lediglich bei weniger als 10 Knoten ist die Anzahl der versendeten Pakete so klein, dass nur ungünstige Cluster-Konstellationen auftreten.

Figure: Zugestellte Pakete QoS und Best-Effort

Betrachtet man die Menge der erfolgreich zugestellten Datenpakete (Abb. 5.11), ergibt sich ein gänzlich anderes Bild: Während die Paketmenge bei Best-Effort-Übertragungen mit der Anzahl der Teilnehmer steigt, stagniert sie bei QoS-Verbindungen bei mehr als 50 aktiven Stationen. Dies beruht darauf, dass nur dann Datenpakete versendet werden können, wenn eine QoS-Verbindung aufgebaut ist. Versuchen mehr als 50 Knoten, an der Kommunikation teilzunehmen, ist das Netzwerk ausgelastet und weitere Verbindungsversuche werden abgelehnt.

Ergebnisse

Die Evaluierung hat gezeigt, dass die Teilmodule gut funktionieren und auch ihre Zusammenarbeit problemlos erledigen. Die Propagation der Topologiedaten klappt auch bei hoher Knotenmobilität und starker Auslastung des Netzwerks; lediglich wenn alle Teilnehmer permanent Daten senden, können keine lokalen Weltmodelle mehr aufgebaut werden.

Das Weiterleiten von Datenpaketen ohne Garantien funktioniert auch, allerdings tritt bei steigender Belastung des Mediums eine Warteschlangensättigung auf den Gateway-Knoten ein: Es werden mehr Datenpakete eingeliefert als versendet werden können. Dieser Effekt führt dazu, dass die Zustellung der eigenen Datenpakete fast beliebig verzögert werden kann, oder dass die Pakete durch den Überlauf einer Warteschlange gar nicht ankommen.

Versendet man seine Daten über eine QoS-Verbindung, so sind die Latenzzeiten dagegen genau so kalkulierbar wie die erreichbare Datenrate. Allerdings ist die Anzahl der QoS-Verbindungen, die durch ein Netzwerk führen können, stark limitiert und der Aufbau solcher Verbindungen ist mit einem erhöhten Aufwand verbunden.

Aus diesem Grund sollte beim Design von Anwendungen besonders sorgfältig abgewogen werden, ob eine QoS-Verbindung für bestimmte Datentransfers erforderlich ist, oder ob die Informationen auf dem Best-Effort-Kanal versendet werden können.