TCP Performance in AdHoc Networks: Difference between revisions

From
Jump to navigation Jump to search
No edit summary
 
 
(20 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Motivation: Warum überhaupt TCP ? ==
=== ===

=== ===
Nun, TCP ist eine Schicht des '''TCP/IP-Stacks''' ist der Standard-Protokoll-Stack im Internet. Will also ein Rechner über das Internet mit anderen Rechnern kommunizieren, so muss er den TCP/IP-Stack implementieren.
===Explicit Link Failure Notification (ELFN)===

== ==
== ==
== Was ist TCP ? ==

TCP ist die Abkürzung für ''Transmission Transport Protocol'' und stellt im TCP/IP-Stack die Transportschicht dar. Damit stellt TCP Dienste für das Senden und Empfangen von Daten bereit. Der Zweck ist hier konkret einen verlässlichen Byte-Strom in einem unzuverlässigen Netzwerk bereitzustellen. Folgende Mechanismen sind essentielle Bestandteile von TCP

;Segmentierung und Assemblierung
:Meist gibt es mindestens eine Schicht, welche die maximale Größe eines Pakets begrenzt, so besitzen z.B. Ethernet-Pakete eine maximale Größe von 1500 Bytes.

;Fehlerbehandlung
:Um einen verlässlichen Byte-Strom zu etablieren ist es natürlich essentiell, aufgetretene Fehler zu entdecken und diese ggf. zu korrigieren. Hierfür werden die TCP-Pakete nummeriert und deren Empfang bestätigt. Erhält der Sender nach einer bestimmten Zeit keine Bestätigung, so sendet er das betreffende Paket erneut.

;Flusskontrolle
:Um zu verhindern, dass der Sender den Empfänger überlastet, erhält ersterer eine Sendekredit, welcher angibt wieviele Pakte ein Sender ohne das Warten auf Bestätigungen versenden darf.

;Staukontrolle
:Um nun auch zu verhindern, dass das gesamte Netzwerk überlastet wird, schließlich teilt man sich hier ein Übertragungsmedium, gibt die Staukontrolle. Hierfür besitzt der Sender ein zusätzlich Fenster ähnlich dem Sendekredit. Es werden nur soviele Pakete auf einmal gesendet, wie es das Minimum von Sendekredit und Überlastungsfenster erlauben.

;Slow-Start-Algorithmus
:Die Größe des Überlastungsfenster ist keineswegs ein fester Wert, sondern wird dynamisch vom Slow-Start-Algorithmus errechnet. Hierbei wächst die Größe des Fensters zunächst exponentiell bis ein Schwellwert erreicht wird, ab dem es nur noch linear wächst. Die Größe des Fensters steigt solange bis ein Stau auftritt, d.h. die Bestätigungen für gesendete Pakete treffen nicht innerhalb des RTO ein. Jetzt wird der Schwellwert halbiert und das Überlastungsfenster zurückgesetzt und der Algorithmus beginnt von vorn.


== Probleme mit TCP ==

TCP stammt aus den 70ger Jahren und ist somit für drahtgebundene Netzwerke entwickelt wurden. Hier besteht implizit die Annahme, dass TimeOuts ausschließlich von einer Netzwerküberlastung herühren und nicht von Übertragungsfehlern.

In AdHoc Netzwerken sieht dies allerdings ganz anders aus. Zum einen geht hier bedingt durch die drahtlose Übertragungs jedes zwanzigste Paket verloren und zum anderen kommt es durch die Mobilität der Knoten sehr häufig zu Verbindungsabbrüchen. Diese Umstände führen dann natürlich zu TimeOuts, welche von TCP als Netzwerküberlastung interpretiert werden. Daraufhin wird das Überlastungsfenster reduziert und zusätzlich der RTO zurückgesetzt. Das Ergebnis hiervon manifestiert sich in einem dramatischen Zusammenbruch des Durchsatzes der TCP-Verbindung.

In dem uns vorliegendem Paper wurden dabei nur das Ausmaß Verbindungsabbrüche auf den TCP-Durchsatz untersucht.

== Leistungsmetrik ==

In dem uns vorliegendem Paper wurden dabei nur das Ausmaß Verbindungsabbrüche auf den TCP-Durchsatz untersucht. Hier für ist es wichtig eine aussagekräftige theoretische obere Schranke zu wählen, den sogenannten ''expected throughput''. Dieser liegt immer über den gemessenem Durchsatz, da hier der Overhead durch das Routing Protokoll zum Finden der Routen nicht berücksichtigt wird. Zusätzlich wählt DSR nicht immer den kürzesteten möglichen Weg zwischen Knoten.

== Intuition und Beobachtung ==

Intuitiv lässt sich vermuten, dass je höher die Bewegungsgeschwindigkeit der Knoten ist desto geringer ist der erreichte Durchsatz. Diese Anti-Proportionalität kann allerdings nicht durch die Beobachtung verifzizert werden. Hier hat sich gezeigt, dass eine Erhöhung der Durchschnittsgeschwindigkeit von 2 m/s auf 10 m/s den Durchsatz signifikant fallen lässt, allerdings fällt dieser bei einer Erhöhung von 10 m/s auf 20 m/s oder 30 m/s nur noch relativ leicht. Bei einigen Bewegungsmustern kommt es sogar zu einer Erhöhung des Durchsatzes mit steigender Geschwindigkeit.

== Ursachen und Folgerungen ==

Bei der Auswertung der Beobachtungen hat sich geziegt, dass die Hauptursachen für den schlechten Durchsatz beim Routing Protokoll zu finden sind. Hier kommt es durch das Zwischenspeichern von Routen dazu, dass veraltete Routen für das Weiterleiten benutzt werden und diese sogar auch noch im Netzwerk verbreitet werden.

Man könnte also überlegen, lieber das Routing Protokoll zu verbessern anstatt TCP. Allerdings könnte man nie völlig das Partitionieren des Netzwerks und das Auftreten von Verzögerungen aufgrund der Mobilität der Knoten auschließen. Es wäre also eine bessere Lösung durch leichte Veränderungen an TCP, dieses in die zu Lage versetzen, zu erkennen, wann mobilitätsinduzierte Verzögerungen und Paketverluste auftreten. Diesen Ansatz verfolgt ELFN.

==Explicit Link Failure Notification (ELFN)==

Eines der Hauptprobleme bei Mobilität in drahtlosen Netzwerken ist das gestörte Links als vermeintlicher Stau im Netzwerk angesehen werden. Eine sehr simple Lösung wäre demnach dem Absender einfach kenntlich zu machen, dass ein fehlerhafter Link vorliegt. Genau dies macht die hier vorgestellte Erweiterung. Dazu nehmen wir die eh vorhandenen DSR-Routing Nachrichten und packen in Ihren Payload noch eine ebensolche angesprochene Notiz. Daraufhin kommt nichtmehr die Überlaststeuerung zu tragen, sondern der Absender geht in einen Warte-Modus - er "freezed". In bestimmten zeitlichen Abständen schickt er nun eine Anfrage ins Netz um zu schauen, ob die Verbindung wieder steht. Sollte dies der Fall sein, kann es mehr oder weniger normal weitergehen.

===Simulation===
Hier nun ein paar Graphen mit ELFN im Einsatz. Die ersten beiden Diagramme zeigen jeweils pro Bewegungsmuster den erreichten Durchsatz im Vergleich zum optimalen Durchsatz (gestrichelte Gerade). Zum Vergleich sind jeweils die Ergebnisse ohne ELFN in rot abgetragen.

Das dritte Diagramm konzentriert sich nur auf verschiedene Zeitintervalle in denen Anfragen ins Netz geschickt werden.
{|width="100%" border="0"
|-
|width="50%"|[[Image:2msb.png|thumb|center|300px|Per-pattern performance of TCP with ELFN using a 2s probe intervall. Mean Speed 2ms.]]
|width="50%"|[[Image:10ms.png|thumb|center|300px|Per-pattern performance of TCP with ELFN using a 2s probe intervall. Mean Speed 10ms.]]
|-
|width="50%" colspan="2"|[[Image:Probe.png|thumb|center|450px|Performance comparison using different probe intervalls]]

|}

Latest revision as of 18:15, 15 July 2007

Motivation: Warum überhaupt TCP ?

Nun, TCP ist eine Schicht des TCP/IP-Stacks ist der Standard-Protokoll-Stack im Internet. Will also ein Rechner über das Internet mit anderen Rechnern kommunizieren, so muss er den TCP/IP-Stack implementieren.

Was ist TCP ?

TCP ist die Abkürzung für Transmission Transport Protocol und stellt im TCP/IP-Stack die Transportschicht dar. Damit stellt TCP Dienste für das Senden und Empfangen von Daten bereit. Der Zweck ist hier konkret einen verlässlichen Byte-Strom in einem unzuverlässigen Netzwerk bereitzustellen. Folgende Mechanismen sind essentielle Bestandteile von TCP

Segmentierung und Assemblierung
Meist gibt es mindestens eine Schicht, welche die maximale Größe eines Pakets begrenzt, so besitzen z.B. Ethernet-Pakete eine maximale Größe von 1500 Bytes.
Fehlerbehandlung
Um einen verlässlichen Byte-Strom zu etablieren ist es natürlich essentiell, aufgetretene Fehler zu entdecken und diese ggf. zu korrigieren. Hierfür werden die TCP-Pakete nummeriert und deren Empfang bestätigt. Erhält der Sender nach einer bestimmten Zeit keine Bestätigung, so sendet er das betreffende Paket erneut.
Flusskontrolle
Um zu verhindern, dass der Sender den Empfänger überlastet, erhält ersterer eine Sendekredit, welcher angibt wieviele Pakte ein Sender ohne das Warten auf Bestätigungen versenden darf.
Staukontrolle
Um nun auch zu verhindern, dass das gesamte Netzwerk überlastet wird, schließlich teilt man sich hier ein Übertragungsmedium, gibt die Staukontrolle. Hierfür besitzt der Sender ein zusätzlich Fenster ähnlich dem Sendekredit. Es werden nur soviele Pakete auf einmal gesendet, wie es das Minimum von Sendekredit und Überlastungsfenster erlauben.
Slow-Start-Algorithmus
Die Größe des Überlastungsfenster ist keineswegs ein fester Wert, sondern wird dynamisch vom Slow-Start-Algorithmus errechnet. Hierbei wächst die Größe des Fensters zunächst exponentiell bis ein Schwellwert erreicht wird, ab dem es nur noch linear wächst. Die Größe des Fensters steigt solange bis ein Stau auftritt, d.h. die Bestätigungen für gesendete Pakete treffen nicht innerhalb des RTO ein. Jetzt wird der Schwellwert halbiert und das Überlastungsfenster zurückgesetzt und der Algorithmus beginnt von vorn.


Probleme mit TCP

TCP stammt aus den 70ger Jahren und ist somit für drahtgebundene Netzwerke entwickelt wurden. Hier besteht implizit die Annahme, dass TimeOuts ausschließlich von einer Netzwerküberlastung herühren und nicht von Übertragungsfehlern.

In AdHoc Netzwerken sieht dies allerdings ganz anders aus. Zum einen geht hier bedingt durch die drahtlose Übertragungs jedes zwanzigste Paket verloren und zum anderen kommt es durch die Mobilität der Knoten sehr häufig zu Verbindungsabbrüchen. Diese Umstände führen dann natürlich zu TimeOuts, welche von TCP als Netzwerküberlastung interpretiert werden. Daraufhin wird das Überlastungsfenster reduziert und zusätzlich der RTO zurückgesetzt. Das Ergebnis hiervon manifestiert sich in einem dramatischen Zusammenbruch des Durchsatzes der TCP-Verbindung.

In dem uns vorliegendem Paper wurden dabei nur das Ausmaß Verbindungsabbrüche auf den TCP-Durchsatz untersucht.

Leistungsmetrik

In dem uns vorliegendem Paper wurden dabei nur das Ausmaß Verbindungsabbrüche auf den TCP-Durchsatz untersucht. Hier für ist es wichtig eine aussagekräftige theoretische obere Schranke zu wählen, den sogenannten expected throughput. Dieser liegt immer über den gemessenem Durchsatz, da hier der Overhead durch das Routing Protokoll zum Finden der Routen nicht berücksichtigt wird. Zusätzlich wählt DSR nicht immer den kürzesteten möglichen Weg zwischen Knoten.

Intuition und Beobachtung

Intuitiv lässt sich vermuten, dass je höher die Bewegungsgeschwindigkeit der Knoten ist desto geringer ist der erreichte Durchsatz. Diese Anti-Proportionalität kann allerdings nicht durch die Beobachtung verifzizert werden. Hier hat sich gezeigt, dass eine Erhöhung der Durchschnittsgeschwindigkeit von 2 m/s auf 10 m/s den Durchsatz signifikant fallen lässt, allerdings fällt dieser bei einer Erhöhung von 10 m/s auf 20 m/s oder 30 m/s nur noch relativ leicht. Bei einigen Bewegungsmustern kommt es sogar zu einer Erhöhung des Durchsatzes mit steigender Geschwindigkeit.

Ursachen und Folgerungen

Bei der Auswertung der Beobachtungen hat sich geziegt, dass die Hauptursachen für den schlechten Durchsatz beim Routing Protokoll zu finden sind. Hier kommt es durch das Zwischenspeichern von Routen dazu, dass veraltete Routen für das Weiterleiten benutzt werden und diese sogar auch noch im Netzwerk verbreitet werden.

Man könnte also überlegen, lieber das Routing Protokoll zu verbessern anstatt TCP. Allerdings könnte man nie völlig das Partitionieren des Netzwerks und das Auftreten von Verzögerungen aufgrund der Mobilität der Knoten auschließen. Es wäre also eine bessere Lösung durch leichte Veränderungen an TCP, dieses in die zu Lage versetzen, zu erkennen, wann mobilitätsinduzierte Verzögerungen und Paketverluste auftreten. Diesen Ansatz verfolgt ELFN.

Explicit Link Failure Notification (ELFN)

Eines der Hauptprobleme bei Mobilität in drahtlosen Netzwerken ist das gestörte Links als vermeintlicher Stau im Netzwerk angesehen werden. Eine sehr simple Lösung wäre demnach dem Absender einfach kenntlich zu machen, dass ein fehlerhafter Link vorliegt. Genau dies macht die hier vorgestellte Erweiterung. Dazu nehmen wir die eh vorhandenen DSR-Routing Nachrichten und packen in Ihren Payload noch eine ebensolche angesprochene Notiz. Daraufhin kommt nichtmehr die Überlaststeuerung zu tragen, sondern der Absender geht in einen Warte-Modus - er "freezed". In bestimmten zeitlichen Abständen schickt er nun eine Anfrage ins Netz um zu schauen, ob die Verbindung wieder steht. Sollte dies der Fall sein, kann es mehr oder weniger normal weitergehen.

Simulation

Hier nun ein paar Graphen mit ELFN im Einsatz. Die ersten beiden Diagramme zeigen jeweils pro Bewegungsmuster den erreichten Durchsatz im Vergleich zum optimalen Durchsatz (gestrichelte Gerade). Zum Vergleich sind jeweils die Ergebnisse ohne ELFN in rot abgetragen.

Das dritte Diagramm konzentriert sich nur auf verschiedene Zeitintervalle in denen Anfragen ins Netz geschickt werden.

Per-pattern performance of TCP with ELFN using a 2s probe intervall. Mean Speed 2ms.
Per-pattern performance of TCP with ELFN using a 2s probe intervall. Mean Speed 10ms.
Performance comparison using different probe intervalls