Transmission Control Protocol/Überlastungskontrolle

Überlastungskontrolle

Bei Paketvermittelten Netzen kann es zu Überlastung kommen
Beim Zielhost
Innerhalb des Netzwerkes
Lösungen

Änderung der Fenstergröße

Congestion Windows Size (Größe des Überlastungsfensters)
Die tatsächliche Segmentgröße ist ein Limit aus beiden Werten

Slow Start with Congestion Avoidance

Beim Verbindungsaufbau wird das Überlastungfenster auf die Größe eines Segmentes gesetzt
Kommen die Quittungen des versandten Segmentes ohne Timeout an, wird die Größe des Überlastungsfensters verdoppelt
Dies geschieht bis zum Schwellenwert von 64 KByte
Danach pro erfolgreichem Sende- und Empfangszyklus um jeweils eine Segmentgröße
Dieser Algorithmus ist für zuverlässige Verbindungen konzipiert und sollte z. B. bei WLANs deaktiviert werden
Dort verringert er stark die effektive Bandbreite

Überlaststeuerung/Staukontrolle (Congestion Control)

Wird eine Verbindung stark belastet, werden immer mehr Pakete verworfen
Durch die Wiederholung steigt wiederum die Belastung, dies sorgt (ohne Maßnahmen) für einen Datenstau
Die Verlustrate wird von einem IP-Netzwerk ständig beobachtet
Normalerweise wird eine TCP/IP-Verbindung langsam gestartet (Slow-Start) und die Senderate schrittweise erhöht, bis zum Datenverlust
Ein Datenverlust verringert die Senderate, ohne Verlust wird sie wiederum erhöht

Algorithmus zur Überlaststeuerung

Gehen bei einer bestimmten Fenstergröße Pakete verloren, kann das festgestellt werden, wenn der Sender innerhalb einer bestimmten Zeit (Timeout) kein ACK erhält

Man muss davon ausgehen, dass das Paket aufgrund zu hoher Netzlast von einem Router im Netz verworfen wurde (Stau im Netz)
Um den Stau aufzulösen, müssen alle beteiligten Sender ihre Netzlast reduzieren

Dazu werden im RFC 2581 vier Algorithmen definiert:

slow start
congestion avoidance
fast retransmit
fast recovery

slow start und congestion avoidance werden zusammen verwendet
fast retransmit und fast recovery werden zusammen verwendet, sind eine Erweiterung von slow start und congestion avoidance

Slow Start Slow Start und Congestion Avoidance

Grafische Darstellung des Slow-Start-Algorithmus

Der Slow-Start-Algorithmus dient zur Bestimmung des congestion window
Da die momentane Auslastung des Netzes nicht bekannt ist, wird mit kleinen Datenmengen begonnen

Der Algorithmus startet mit einem kleinen Fenster, von einer Maximum Segment Size (MSS), in dem Datenpakete vom Sender zum Empfänger übertragen werden
Der Empfänger sendet ACK an den Sender zurück
Für jedes empfangene ACK wird die Größe des congestion window um eine MSS erhöht
- Dies führt innerhalb einer Roundtrip-Zeit zu einer Verdopplung des Congestion Windows
Dieses exponentielle Wachstum wird so lange fortgesetzt, bis der Slow-Start Threshold erreicht wird
- Die Phase des exponentiellen Wachstums wird auch Slow Start Phase genannt
Danach wird das Congestion Window nur noch um eine MSS erhöht, wenn alle Pakete aus dem Fenster erfolgreich übertragen wurden
- Es wächst pro Roundtrip-Zeit nur noch um eine MSS, also nur noch linear
  - Diese Phase wird als Congestion Avoidance Phase bezeichnet
- Das Wachstum wird beendet, wenn das vom Empfänger festgelegte Empfangsfenster erreicht worden ist

Kommt es zu einem Timeout, wird das congestion window auf 1 zurückgesetzt, der slow-start threshold wird auf die Hälfte der gesendeten, unquittierten Pakete herabgesetzt (Flight Size)

Die Phase des exponentiellen Wachstums wird also verkürzt
Das Fenster wächst bei häufigen Paketverlusten nur langsam

Fast-Retransmit und Fast-Recovery

Werden eingesetzt, um nach Paketverlust schneller auf die Stau-Situation zu reagieren
Empfänger informiert den Sender, wenn Pakete außer der Reihe ankommen und somit dazwischen ein Paketverlust vorliegt
Der Empfänger bestätigt das letzte korrekte Paket erneut für jedes weitere ankommende Paket außer der Reihe
Man spricht dabei von Dup-Acks (duplicate acknowledgments)
- Mehrere aufeinanderfolgende Nachrichten, welche dasselbe Datensegment ACKen
Der Sender bemerkt die duplizierten ACKS, und nach dem dritten Duplikat sendet er sofort, vor Ablauf des Timers, das verlorene Paket erneut
- Da nicht auf den Timerablauf gewartet werden muss, heißt das Prinzip Fast Retransmit
Dup-Acks: auch Hinweise darauf, dass ein Paketverlust stattfand, dennoch die folgenden Pakete angekommen sind
Das Sendefenster wird nach dem Fehler nur halbiert (kein Slow-Start)

Zusätzlich kann das Sendefenster noch um die Anzahl der Dup-Acks erhöht werden

Jedes Dup-Ack steht für ein weiteres Paket, welches den Empfänger erreicht hat
Dadurch kann nach dem Fehler schneller wieder die volle Sendeleistung erreicht werden
Das Prinzip nennt man Fast-Recovery

Verwaltung der TCP-Verbindungen als endlicher Automat

Überlaststeuerung/Staukontrolle (Congestion Control)

Im Internet, in dem viele Netze mit unterschiedlichen Eigenschaften verbunden werden, ist Datenverlust einzelner Pakete durchaus normal.

Wird eine Verbindung stark belastet, werden immer mehr Pakete verworfen, die entsprechend wiederholt werden müssen.
Durch die Wiederholung steigt wiederum die Belastung, ohne geeignete Maßnahmen kommt es zu einem Datenstau.

Die Verlustrate wird von einem IP-Netzwerk ständig beobachtet.

Abhängig von der Verlustrate wird die Senderate durch geeignete Algorithmen beeinflusst: Normalerweise wird eine TCP/IP-Verbindung langsam gestartet (Slow-Start) und die Senderate schrittweise erhöht, bis es zum Datenverlust kommt.
Ein Datenverlust verringert die Senderate, ohne Verlust wird sie wiederum erhöht.
Insgesamt nähert sich die Datenrate so zunächst dem jeweiligen zur Verfügung stehenden Maximum und bleibt dann ungefähr dort.
Eine Überbelastung wird vermieden.

Algorithmus zur Überlaststeuerung

Gehen bei einer bestimmten Fenstergröße Pakete verloren, kann das festgestellt werden, wenn der Sender innerhalb einer bestimmten Zeit (Timeout) keine Bestätigung (ACK) erhält.

Man muss davon ausgehen, dass das Paket aufgrund zu hoher Netzlast von einem Router im Netz verworfen wurde.
Das heißt, der Puffer eines Routers ist vollgelaufen; es handelt sich hier sozusagen um einen Stau im Netz.
Um den Stau aufzulösen, müssen alle beteiligten Sender ihre Netzlast reduzieren.
Dazu werden im RFC 2581 vier Algorithmen definiert: slow start, congestion avoidance, fast retransmit und fast recovery, wobei slow start und congestion avoidance zusammen verwendet werden.
Die zwei Algorithmen fast retransmit und fast recovery werden auch zusammen verwendet und sind eine Erweiterung der Algorithmen slow start und congestion avoidance.

Slow Start und Congestion Avoidance

Zu Beginn einer Datenübertragung dient der Slow-Start-Algorithmus zur Bestimmung des congestion window (wörtlich: Überlastfenster), um einer möglichen Überlastsituation vorzubeugen.

Man möchte Staus vermeiden, und da die momentane Auslastung des Netzes nicht bekannt ist, wird mit zunächst kleinen Datenmengen begonnen.
Der Algorithmus startet mit einem kleinen Fenster von einer MSS (Maximum Segment Size), in dem Datenpakete vom Sender zum Empfänger übertragen werden.

Der Empfänger sendet nun eine Bestätigung (ACK) an den Sender zurück.

Für jedes empfangene ACK wird die Größe des congestion window um eine MSS erhöht.
Da für jedes versandte Paket bei erfolgreicher Übertragung ein ACK geschickt wird, führt dies innerhalb einer Roundtrip-Zeit zu einer Verdopplung des Congestion Windows.
In dieser Phase gibt es also ein exponentielles Wachstum.
Wenn das Fenster beispielsweise das Versenden von zwei Paketen gestattet, so erhält der Sender auch zwei ACKs und erhöht das Fenster daher um 2 auf 4.
Dieses exponentielle Wachstum wird so lange fortgesetzt, bis der sogenannte Slow-Start Threshold erreicht wird (engl. Vorlage:Lang ‚Schwelle‘).
Die Phase des exponentiellen Wachstums wird auch Slow Start Phase genannt.

Danach wird das Congestion Window nur noch um eine MSS erhöht, wenn alle Pakete aus dem Fenster erfolgreich übertragen wurden.

Es wächst also pro Roundtrip-Zeit nur noch um eine MSS, also nur noch linear.
Diese Phase wird als Congestion Avoidance Phase bezeichnet.
Das Wachstum wird beendet, wenn das vom Empfänger festgelegte Empfangsfenster erreicht worden ist (siehe Fluss-Steuerung).

Kommt es zu einem Timeout, wird das Vorlage:Lang wieder auf 1 zurückgesetzt, und der Vorlage:Lang wird auf die Hälfte der Flight Size (Flight Size ist die Anzahl an Paketen, die verschickt, aber noch nicht quittiert wurden)^[1] herabgesetzt.

Die Phase des exponentiellen Wachstums wird also verkürzt, so dass das Fenster bei häufigen Paketverlusten nur langsam wächst.

Fast-Retransmit und Fast-Recovery

Vorlage:Lang und Vorlage:Lang („schnelles Erholen“) werden eingesetzt, um nach einem Paketverlust schneller auf die Stau-Situation zu reagieren.

Dazu informiert ein Empfänger den Sender, wenn Pakete außer der Reihe ankommen und somit dazwischen ein Paketverlust vorliegt.
Hierfür bestätigt der Empfänger das letzte korrekte Paket erneut für jedes weitere ankommende Paket außer der Reihe.
Man spricht dabei von Dup-Acks (Vorlage:Lang), also mehrere aufeinanderfolgende Nachrichten, welche dasselbe Datensegment ACKen.
Der Sender bemerkt die duplizierten Bestätigungen, und nach dem dritten Duplikat sendet er sofort, vor Ablauf des Timers, das verlorene Paket erneut.
Weil nicht auf den Ablauf des Timers gewartet werden muss, heißt das Prinzip Vorlage:Lang.
Die Dup-Acks sind auch Hinweise darauf, dass zwar ein Paketverlust stattfand, aber doch die folgenden Pakete angekommen sind.
Deshalb wird das Sendefenster nach dem Fehler nur halbiert und nicht wie beim Timeout wieder mit Slow-Start begonnen.
Zusätzlich kann das Sendefenster noch um die Anzahl der Dup-Acks erhöht werden, denn jedes steht für ein weiteres Paket, welches den Empfänger erreicht hat, wenn auch außer der Reihe.
Da dadurch nach dem Fehler schneller wieder die volle Sendeleistung erreicht wird, nennt man das Prinzip Vorlage:Lang.

Selective ACKs (SACK)

Vorlage:Lang werden genutzt, um noch mehr Kontrollinformationen über den Datenfluss vom Empfänger an den Sender zurückzuschicken.

Dabei wird nach einem Paketverlust vom Empfänger im TCP-Optionsfeld ein zusätzlicher Header eingefügt, aus welchem der Sender genau ersehen kann, welche Pakete bereits angekommen sind und welche fehlen (im Gegensatz zu den standardmäßigen kumulativen ACKs von TCP, s. o.).
Als bestätigt gelten die Pakete auch weiterhin erst dann, wenn der Empfänger dem Sender ein ACK für die Pakete übermittelt hat.

TCP-Tahoe und TCP-Reno

Bei den nach Orten in Nevada benannten TCP-Congestion-Control-Varianten Tahoe und Reno handelt es sich um zwei verschiedene Verfahren, wie TCP auf ein Überlast-Ereignis in Form von Timeouts oder Dup-Acks reagiert.

Das inzwischen nicht mehr verwendete TCP Tahoe reduziert, sobald ein Timeout vorliegt, das Congestion Window für die nächste Übertragungseinheit auf 1.

Anschließend startet wieder der TCP-Slow-Start-Prozess (mit verringertem Threshold, s. u.), bis ein neues Timeout- oder DUP-Acks-Ereignis stattfindet oder aber der Schwellwert (Threshold) zum Übergang in die Congestion-Avoidance-Phase erreicht wird.
Dieser Schwellwert wurde nach dem Auftreten des Überlast-Ereignisses auf die Hälfte der Größe des derzeitigen Congestion Window gesetzt.
Der Nachteil dieses Verfahrens ist zum einen, dass ein Paketverlust nur durch einen Timeout festgestellt wird, mitunter also recht lange dauert, und zum anderen die starke Reduktion des Congestion Windows auf 1.

Die Weiterentwicklung von Tahoe ist TCP-Reno.

Hierbei wird zwischen auftretenden Timeout- und Dup-Acks-Ereignissen unterschieden: Während TCP-Reno beim Auftreten eines Timeout genauso verfährt wie TCP Tahoe, wendet es beim Auftreten von drei doppelten Acks eine andere Variante für die Festlegung des nachfolgenden Congestion Windows an.
Die grundlegende Idee dabei ist, dass der Verlust eines Segments auf dem Weg zum Empfänger nicht nur durch einen Timeout erkannt werden kann, sondern auch dadurch, dass der Empfänger mehrfach dieselben ACKs für das unmittelbar vor dem verlorengegangenen Segment zurückschickt (und zwar jedes Mal, wenn er ein weiteres Segment nach der „Lücke“ empfängt).
Daher wird das nachfolgende Congestion Window auf die Hälfte des Wertes des Congestion Windows zum Zeitpunkt des Überlast-Ereignisses gesetzt; anschließend wird wieder in die Congestion Avoidance Phase übergegangen.
Dieses Verhalten wird, wie oben im Artikel erwähnt, als Fast-Recovery beschrieben.

Slow‐Start

Starte mit einem CongestionWindow der Länge MSS.
Erhöhe CongestionWindow um eine MSS pro ACK. Somit wird das CongestionWindow pro RTT wie weit erhöht?

Warum heißt das eigentlich Slow‐Start?

Historischer Grund: In TCP‐Anfängen wurde zum Starten direkt mit einem großen CongestionWindow gestartet.

Wann beginnt und endet der Slow‐Start?

Wenn eine Verbindung neu hergestellt wurde.

Setze CongestionWindow auf eine MSS
Beginne Slow‐Start
Wechsele in AdditiveIncrease sobald ein bestimmter
Schwellwert (CongestionThreshold) überschritten wurde

Wenn ein Timeout stattgefunden hat

CongestionThreshold = CongestionWindow/2 (man merkt sich also den CongestionWindow nach dem durch den Timeout ausgelösten MultiplicativeDecrease)
Setze CongestionWindow auf eine MSS
Beginne Slow‐Start
Wechsele in AdditiveIncrease sobald der Schwellwert CongestionThreshold überschritten wurde

Ein Beispiel

Fast‐Retransmit

ACKS sind kummulativ (d.h. bestätigen die bisher vollständig zusammenhängende Sequenz von Segmenten)
Verlorene Sequenz führt zu „duplicate ACKs“.
Fast‐Retransmit: Warte nicht auf Timeout, sondern reübertrage ein Segment, nach drei aufeinander folgenden Duplicate‐ACKs.

Die TCP‐Variante mit Fast‐Recovery

Slow‐Start, wenn die TCP‐Verbindung neu aufgebaut wurde.
Die Reübertragung wegen duplicate ACK lediglich CongestionWindow wie üblich halbieren.
Aber keinen Slow‐Start, sondern gewöhnlichen AdditiveIncrease.

TCP‐Überlastvermeidung

Motivation

TCP implementiert Überlastkontrolle, d.h. erst, wenn Segmente auf den Routern verworfen werden, wird an den Quellen die in das Netz gesendete Last reduziert.

Die Idee von Überlastvermeidung

Reduziere die an den Quellen erzeugte Last schon bevor die ersten Segmente (Pakete) an den Routern wegen voll gelaufener Queues verworfen werden.

TCP hat an den Quellknoten keine Mechanismen eingebaut, die eine solche Strategie unmittelbar ermöglicht. Man müsste hierzu TCP durch ein neues Protokoll ersetzen.

Idee: Router „gaukeln“ vorzeitig übergelaufene Queues vor, sodass die TCP‐Quellknoten auch vorzeitig die Last reduzieren und somit keine Überlast an den Routern auftreten kann.

Random‐Early‐Detection (RED)

Router berechnet regelmäßig die mittlere Queuelänge AvgLen anhand von gemessenen Queuelängensamples SampleLen:

Jeder Router hat ein MinThreshold und ein MaxThreshold. Bei Ankunft eines Paketes wird folgender Algorithmus ausgeführt:

if AvgLen <= MinThreshold
 speichere Paket in der Queue
else if AvgLen < MaxThreshold
 berechne Wahrscheinlichkeit p
verwerfe das Paket mit der Wahrscheinlichkeit p
else
 verwerfe das Paket immer

Berechnung der Drop‐Wahrscheinlichkeit

Bestimme die Wahrscheinlichkeit TempP zunächst in Abhängigkeit von AvgLen wie folgt:

D.h. zwischen MinThresh und MaxThresh als Formel:

Zähle die Anzahl count der nicht verworfenen Pakete während AvgLen zwischen MinThresh und MaxThresh war und berechne:

TCP‐Varianten

TCP erlaubt Implementationsvarianten

Send‐Policy

Keine Festlegung wie lange und wieviel gepuffert wird, bevor ein Segment gesendet wird
Abzuwägen ist: Response‐Zeit versus Overhead wegen Nachrichten‐Header

Deliver‐Policy

Keine Festlegung, wie lange Segmente auf der Empfängerseite gepuffert werden, bevor diese an die Anwendung weiter gegeben werden
Abzuwägen ist: Response‐Zeit versus Overhead wegen Processing in TCP‐ und User‐Software, sowie unnötige OS‐Interrupts

Accept‐Policy

Keine Festlegung, wie mit Out‐of‐Order Segmenten umzugehen ist
Zwei Optionen
- Verwerfe Out‐of‐Order‐Segmente
- Behalte alle Segmente, die in das Receive‐Fenster passen
Abzuwägen ist: Aufwand für Puffer‐Verwaltung versus Netzlast

Retransmit‐Policy

Keine Festlegung, wann ein gepuffertes und noch nicht bestätigtes Segment nochmals übertragen wird
Mögliche Strategien:
- First‐only: Ein Retransmit‐Timeout für das Segment am Anfang der Sende‐Queue (wenn Timeout stattfindet sende das erste Segment und setze den Timer erneut)
- Batch: Sende alle Segmente erneut sobald der Retransmit‐Timeout stattfindet
- Individuell: Ein Timer für jedes Segment in der Queue
Abzuwägen ist:
- First‐only: geringe Netzlast aber größere Verzögerung
- Batch und Individuell: geringere Verzögerung bei höherer Netzlast

Acknowledge‐Policy

Keine Festlegung, wann genau ein einkommendes Segment bestätigt werden muss
Mögliche Strategien:
- Immediate: sende leeres Segment (d.h. ohne Daten) mit Acknowledgement
- Cummulative: Sammele Daten auf der Empfangsseite und sende Acknowledgement erst dann (allerdings: Persit‐Timer, um Acknowledgement nicht zu lange zu verzögern)
Abzuwägen ist: Netzlast versus Verzögerung

Zusammengefasst

Im Rahmen der genannten Policies können TCP‐Varianten realisiert werden, die untereinander interoperabel sind.

Beispiele von TCP‐Varianten

TCP existiert/existierte in verschiedenen Varianten

TCP Tahoe

Ursprüngliche TCP‐Implementierung des beschriebenen Congestion‐Control‐Mechanismus
mit Ausnahme des Fast‐Recovery

TCP Reno

Unter anderem wurde Fast‐Recovery hinzugefügt.

TCP Vegas

Beobachtung der RTT auf den sendenden Knoten und proaktive Anpassung des CongestionWindows, um Congestion vorab zu vermeiden

Zusammenfassung

Die wichtigsten Internet‐Transportprotokolle

UDP (keine Aufwertung des IP Best‐Effort‐Dienstes)
TCP (zuverlässiger Byte‐Strom über IP)

Flusskontrolle und Überlastkontrolle

Flusskontrolle findet Ende‐zu‐Ende statt
Überlastkontrolle betrifft das ganze Netz

Design‐Merkmale

Ende‐zu‐Ende‐Argument: realisiere Funktion auf der Schicht, in der diese komplett implementierbar ist
TCP funktioniert nach dem Smart‐Sender/Dumb‐Receiver‐Prinzip

Weitere TCP‐Stärke

TCP erlaubt Erweiterungen
Hosts müssen sich einigen, welche Erweiterungen genutzt werden sollen
Neue TCP‐Erweiterung erfordert damit nicht im ganzen Internet TCP komplett neu zu installieren

Unterscheidung zwischen Überlastkontrolle und Überlastvermeidung

Literatur

[PetersonDavie2007] Larry L. Peterson and Bruce S. Davie, „Computer Networks: A Systems Approach“, Edition 4, 2007

↑

[1] ↑

[1]