1. Allgemeines

2. Slow Start

3. Congestion Avoidence

4. Fast Retransmit

5. Gesamtablauf

6. Aufgabentyp 'berechnen'

7. Aufgabentyp 'auswerten'

8. Aufgabentyp 'zeichnen'

   

Allgemeines    oben

 

Voraussetzung bei diesem Applet ist, dass der Empfänger nicht überlastet ist (d.h. die flow control Mechanismen bleiben unberücksichtigt). Desweiteren wird innerhalb des Applets die Einheit "Segemente" verwendet.
Unter Congestion Control versteht man das Bereitstellen von Methoden zur Überlastkontrolle. In einem Netz kann es dazu kommen, daß alle Sender im Netz immer so viele Pakete losschicken, wie bei den Empfängern in den Puffer passen. Dabei kann es zu einer Überlast (Congestion) im Netz kommen, da keine Rücksicht auf die momentane Situation im Netz genommen wird. Dies ist insbesondere im Internet ein häufiges Problem. Wenn ein Netz über seine Kapazität hinaus beansprucht wird, treten Überlastungen auf.

Abb. 1: Überlast im inneren des Netzes

Wenn alle Verbindungen die gleiche Bandbreite haben und sowohl A als auch B mit der vollen Bandbreite der Verbindung senden, dann kommt es hier zur Überlastung im Inneren des Netzes (Congestion). TCP-Verbindungen erkennen dies und regeln freiwillig die Bandbreite herunter!

Die Vermittlungsschicht versucht zwar, Überlastungen abzuwehren, allerdings wird die tatsächliche Überlastkontrolle von Protokollen der Transportschicht, insbesondere von TCP (Transmission Control Protocol) übernommen, da nur in der Verringerung der übertragenen Datenrate eine tatsächliche Lösung besteht. Ein Algorithmus der von TCP zur Verfügung gestellt wird, Überlast zu erkennen und zu reduzieren, ist der im folgenden beschriebene Algorithmus mit Congestion Window. Theoretisch könnten Überlastungsprobleme dadurch angegangen werden, daß Pakete erst dann ins Netz eingespeist werden, nachdem ein altes übertragen wurde. TCP versucht, dieses Ziel durch dynamische Manipulation der Fenstergröße zu erreichen. Dabei besagt die Fenstergröße die maximale Anzahl von Paketen, die unbestätigt im Netz verbreitet werden dürfen. Wichtig ist zu beachten, daß TCP nicht versucht, Überlast von vornherein zu vermeiden. Tatsächlich erhöht TCP wiederholt die Last, die es dem Netzwerk auferlegt, um Verluste zu erzeugen, um dadurch die für die Verbindung verfügbare Bandbreite zu finden.

Um Überlast zu verringern muß beim Aufbau der Verbindung eine geeignete Fenstergröße gewählt werden. Der Empfänger kann ein Fenster auf der Grundlage seiner Puffergröße spezifizieren. Hält der Sender sich an diese Fenstergröße, können Probleme nicht aufgrund eines Pufferüberlaufs am Empfangsende auftreten. Die Möglichkeit einer internen Überlastung im Netz besteht aber weiter. Die Lösung besteht darin, zwei potentielle Probleme zu realisieren, die Netz- und die Empfängerkapazität. Um Congestion zu verhindern, wird beim Sender ein zusätzliches Congestion Window (cwnd) mitgeführt. Dieses Congestion Window wird, wie das vom Empfänger mitgeteilte Fenster zur Puffergröße (Flow Control Window) in Bytes geführt. Es spiegelt die Anzahl der Bytes wider, die vom Sender übertragen werden können. Ein Sender darf nur das Minimum aus Congestion Window und Flow Control Window (min(cwnd, Empfänger Window)) an Daten senden.

 

Slow Start   oben

Beim Aufbau einer Verbindung initialisiert der Sender das Überlastungsfenster auf die Größe des maximalen Segments. Dann wird ein maximales Segment gesendet. Wird dieses Segment bestätigt, bevor der Timer abläuft, wird die Menge eines Segmentes in Byte dem Congestion Window hinzugefügt, um daraus zwei Segmente mit maximaler Größe zu machen. Es werden dann zwei Segmente gesendet. Im Folgenden wird das Congestion Window solange um ein Segment pro bestätigtes Segment erhöht, bis ein Verlust auftritt. Das heißt, daß jede übertragene und bestätigte Spitzenmenge das Überlastungsfenster verdoppelt. Das Congestion Window nimmt exponentiell zu, bis entweder ein Timer abläuft oder das Fenster des Empfängers erreicht ist. Der im folgenden betrachtete Algorithmus verwendet noch eine weitere Entscheidungsgröße, einen Schwellenwert (Threshold), kurz als ssthresh bezeichnet. Slow Start stoppt auch, wenn dieser Schwellenwert erreicht ist.

Mittels Slow Start soll so schnell der Wert ermittelt werden, den man senden kann, ohne einen Paketverlust hervorzurufen. Dieser Wert ist erreicht, wenn das cwnd so groß ist, daß die Verbindung zum Empfänger mit Paketen gefüllt bleibt. Slow Start terminiert, wenn die ersten Paketverluste auftreten oder der Schwellenwert ssthresh erreicht ist.

In Formeln gefaßt läßt sich der Wert des Congestion Windows während des Slow Start folgendermaßen ausdrücken:

 

Congestion Avoidence   oben

Der Congestion Avoidence Algorithmus steht in engem Zusammenhang mit dem Slow Start Algorithmus. Nachdem durch diesen sich die Datenmenge auf ein Optimum eingependelt hat, kann sich durch eine sich verändernde Netzlast das eigentliche Optimum verschieben. Terminiert der Slow Start Algorithmus weil der Schwellenwert erreicht wurde, dann wird das Congestion Window langsam durch sogenanntes Additive Increase weiter erhöht. Dabei vergrößert sich das cwnd pro bestätigtem Segment um 1/cwnd. Das bedeutet, das von da ab ein lineares Wachstum des Congestion Windows stattfindet, bis ein Paketverlust auftritt.

Wenn ein Paketverlust auftritt, wird das Congestion Window multiplikativ verringert, indem es auf die Hälfte zurückgesetzt wird. Daher heißt dieser Algorithmus auch Additive Increase – Multiplicative Decrease. Neben dem cwnd wird auch der Schwellenwert ssthresh auf die Größe des halben Congestion Window gesetzt. Der Algorithmus Congestion Avoidence mit Additive Increase und Multiplicative Decrease wird fortgesetzt, da Schwellenwert und neues Congestion Window übereinstimmen und damit cwnd >= ssthresh. Wird jedoch ein Paketverlust nur aufgrund eines Timeouts entdeckt, so wird das cwnd auf ein Segment gesetzt und der Schwellenwert ssthresh auf die Größe des halben Congestion Window verringert. Es wird dann erneut der Slow Start Algorithmus gestartet, jedoch mit geringerem Schwellenwert.

 

Fast Retransmit   oben

Um nicht nur aufgrund von Timeouts auf Paketverluste schließen zu können, wird innerhalb des TCP ein weiterer Algorithmus verwendet. Dabei wird vom Empfänger beim Empfangen eines Paketes das höchste Segment, das in Reihenfolge empfangen wird, bestätigt. Der Empfänger schickt duplicate acks, d.h. er bestätigt das letzte Paket vor einer Lücke erneut, wenn er Segmente erhält, die nicht in der richtigen Reihenfolge eintreffen. Erhält der Sender ein duplicate ack, kann entweder die Reihenfolge der Pakete im Netz verändert worden sein, oder ein Paketverlust vorliegen.

Wenn wenige duplicate acks in Folge ankommen, wird angenommen, daß die Reihenfolge verändert wurde. Der Sender ignoriert die Acknoledgements und sendet weiter. Treten mehr als zwei duplicate acks in Folge auf, wird vom Sender ein Paketverlust angenommen und das betroffene Segment erneut übertragen. Man spricht in diesem Zusammenhang auch von Triple Duplicate Acks (TDACK), da bei dem dritten duplicate ack erneut gesendet wird. Wenn ein kontinuierlicher Datenstrom vom Sender gesendet wird, werden so einzelne Paketverluste deutlich schneller erkannt und repariert. Daher resultiert der Name dieses Verfahrens: Fast Retransmit.

Gesamtablauf   oben

Der von TCP angewandte Algorithmus ist eine Kombination aus Slow Start, Congestion Avoidence und Fast Retransmit. Kurz zusammengefaßt ergibt sich folgender Ablauf:

Graphisch kann dies wie folgt veranschaulicht werden:

Abb. 2: Slow Start und Congestion Avoidance

   

Aufgabentyp 'berechnen'   oben

Dieser Aufgabentyp verlangt die Berechnung des Congestion Windows sowie des Schwellenwertes am Ende des Betrachtungszeitraumes.

Die Aufgabenstellung gibt nach Wahl der Anzahl der Ereignisse sowie des der Wahl des Betrachtungszeitraumes einen zufälligen Ablauf der Ereignisse vor. Dies geschieht nach Betätigen des Buttons 'Aufgabe erzeugen'.

 

Die Berechnung der Aufgabe erfolgt nun wie folgt:

Ssthresh zu Beginn ist 64.
Nach einer Runde ist cwnd = 2 < 64
Nach 2 Runden ist cwnd = 2*2 = 4 <64
Nach 3 Runden ist cwnd = 4*2 = 8 <64
...

Nach 6 Runden ist cwnd = 32*2 = 64

Hier geht der Slow Start in Congestion Avoidence über.

Nach 7 Runden ist cwnd = 64+1 = 65
Nach 8 Runden ist cwnd = 65+1 = 66
Nach 9 Runden ist cwnd = 67
Nach 10 Runden ist cwnd = 68

Nun kommt ein TDACK, cwnd und ssthresh werden auf die halbe cwnd-Größe gesetzt_:
Der Algorithmus setzt fort mit Congestion Avoidence.

Nach 11 Runden ist cwnd = 68 / 2 = 34
Nach 11 Runden ist ssthresh = cwnd = 34

Nach 12 Runden ist cwnd = 34+1 = 35
Nach 13 Runden ist cwnd = 36
...
Nach 26 Runden ist cwnd = 49

Nun kommt ein TDACK, cwnd und ssthresh werden auf die halbe cwnd-Größe gesetzt_:
Der Algorithmus setzt fort mit Congestion Avoidence.

Nach 27 Runden ist cwnd = 49/2 = 24
Nach 27 Runden ist ssthresh = 24
...
Nach 35 Runden ist cwnd = 32

Nun kommt es zu einem Timeout, sstresh wird auf halbe cwnd-Größe gesetzt, cwnd wird auf 1 gesetzt.
Der Algorithmus beginnt erneut mit Slow Start.

Nach 36 Runden ist cwnd = 1
Nach 36 Runden ist ssthresh = 32/2 = 16

Nach 37 Runden ist cwnd = 2 < 16
Nach 38 Runden ist cwnd = 2*2 = 4 < 16
...
Nach 40 Runden ist cwnd = 8*2 = 16

Hier geht der Slow Start in Congestion Avoidence über.

Nach 41 Runden ist cwnd = 17
...
Nach 50 Runden ist cwnd = 26
Nach 50 Runden ist ssthresh = 16

Aufgabentyp 'auswerten'   oben

Dieser Aufgabentyp verlangt die Angabe der Ereignisse sowie deren Zeitpunkte.

Die Aufgabenstellung gibt nach Wahl der Anzahl der Ereignisse sowie des der Wahl des Betrachtungszeitraumes einen zufälligen Ablauf der Ereignisse grafisch vor. Dies geschieht nach Betätigen des Buttons 'Aufgabe erzeugen'.

Nun wird in einem Schaubild die Kurve angegeben sowie spezielle Wertepaare angegeben.

Angegeben werden Werte der Form (Zeitpunkt, cwnd). Es werden alle Werte angegeben, bei welchen ein Ereignis stattgefunden hat oder wenn der Slow Start in die Congestion Avoidence übergeht.

Hier ist zum Zeitpunkt 6 cwnd = 64.

Nach 16 ist cwnd = 74 > 64, also kein TDACK oder Timeout.

Nach 17 ist cwnd = 1

Nach 23 ist cwnd = 64

Nach 27 ist cwnd = 68 > 64, also kein TDACK oder Timeout

Nach 28 ist cwnd = 34 = 68/2

Nach 34 Runden ist cwnd = 40.

Nach 35 Runden ist cwnd = 20 = 40/2.

 

Aufgabentyp 'zeichnen'   oben

Bei diesem Aufgabentyp soll die Kurve des cwnd gezeichnet werden.
Dafür müssen die einzelnen Funktionsabschnitte nacheinander eingegeben werden.

Der Algorithmus beginnt mit Slow Start, das heißt mit 2^x.
Ssthresh startet mit 64.
Nach 1 Runde ist cwnd = 2.
Nach 6 Runden ist cwnd = 2^6=64, ab hier geht dann der Slow Start in Congestion Avoidence über.

Nach 7 Runden ist cwnd = 65

Nach 8 Runden kommt es zu einem TDACK.
Ssthresh = 65/2 = 32.

Nach einem TDACK geht der Algorithmus mit Congestion Avoidence weiter bis zum nächsten Ereignis.

Nach 37 Runden kommt es zu einem Timeout.
Cwnd = 1, ssthresh = 32/2 = 16.

Nach einem Timeout geht der Algorthmus mit Slow Start bis ssthresh oder einem Ereignis weiter.

Nach 39 Runden kommt es zu einem TDACK.
Ssthresh = ½ = 1 (min. 1).

Nach einem TDACK geht der Algorithmus mit Congestion Avoidence weiter bis zum nächsten Ereignis.