2.3.9 Anpassung an die Netzkapazität

Im Internet, wo in der Regel zwischen Sender und Empfänger mehrere Router und unterschiedlich schnelle Subnetze liegen, kann jederzeit eine sog. Congestion eintreten. Dieser Begriff beschreibt eine Situation, in der die Verzögerungszeiten entlang eines bestimmten Pfades durch das Netz sehr hoch sind, weil mindestens einer der genutzten Router überlastet ist. Daraus können drastische Reduzierungen des Datendurchsatzes resultieren.

Solange der Speicher des Routers reicht, werden die Pakete bis zu ihrer Weiterleitung in Warteschlangen aufbewahrt. Bei starker Überflutung laufen die Puffer allerdings über und die Pakete, für die kein Platz mehr ist, gehen verloren. Die Probleme verschärfen sich automatisch, wenn es auf Grund nicht oder nicht rechtzeitig eintreffender Quittungen zu Sendewiederholungen kommt. Der erhöhte Verkehr sowie die starken Verzögerungen schaukeln sich gegenseitig hoch, bis das Netz nicht mehr benutzbar ist. Man spricht dann mitunter vom Congestion Collapse.

Um derartige Zusammenbrüche zu verhindern, muß TCP die Senderate reduzieren, wenn es im Netz zum Paketstau kommt. Router überwachen die Längen ihrer Queues und melden in der Regel den Sendern die aufgetretenen Pufferüberläufe durch ICMP-Meldungen vom Typ Source Quench. TCP kann aber auch von sich aus helfen, den Problemen entgegenzuwirken, indem es die Senderate bei steigenden Verzögerungen selbständig vermindert. Dabei ist aber der Tatsache Rechnung zu tragen, daß die Verzögerungszeiten auch unter normalen Bedingungen teilweise recht beträchtlich schwanken.

TCP begegnet den genannten Problemen durch zwei weitere von Van Jacobson entwickelte und in dem schon erwähnten Paper Congestion Avoidance and Control beschriebene Algorithmen: Slow-Start und Congestion Avoidance. Es handelt sich dabei um voneinander unabhängige Verfahren mit unterschiedlichen Zielsetzungen, die sich allerdings sehr gut ergänzen und deshalb in der Regel zusammen in Form eines kombinierten Algorithmus implementiert werden. Gemäß RFC 1122 sind sie obligatorisch, allerdings verwenden manche Implementierungen den Slow-Start nur, wenn sich Sender und Empfänger nicht im gleichen Netz befinden.

Der Slow-Start hat die Aufgabe, den Datenfluß einer TCP-Verbindung sowohl unmittelbar nach dem Start als auch nach Paketverlusten in Gang zu bringen und einen stabilen Zustand zu erreichen. Dazu wird die Senderate schrittweise erhöht, bis eine Sättigung des Netzes eintritt. Er arbeitet genau wie der Nagle-Algorithmus "self-clocking". Die Implementierung ist trivial:

Der Begriff Slow-Start ist etwas irreführend, da der Start unter normalen Bedingungen eher ziemlich zügig verläuft. Nach dem Senden des ersten Pakets und dem Empfang der zugehörigen Quittung hat das Fenster bereits eine Größe von zwei Segmenten. Somit kann man nachfolgend zwei Pakete verschicken und zwei Bestätigungen erhalten. Dann wächst cwnd auf vier Segmente. Allgemein bedarf es also nur log2N Rundreisen, bis das Congestion Window N Segmente groß ist. Es erfolgt also ein exponentielles Wachstum, das allerdings beim weiter unten diskutierten kombinierten Verfahren an einer bestimmten Stelle durch die Congestion Avoidance abgeschwächt wird.

Ein Sender muß jederzeit damit rechnen, daß im Netz eine Congestion vorliegt oder sich gerade eine solche anbahnt, und darauf mit dem Schließen des durch den Slow-Start schrittweise geöffneten Congestion-Fensters reagieren. An dieser Stelle kommt nun bei TCP der Algorithmus Congestion Avoidance zum Einsatz, der sich ebenfalls sehr leicht implementieren läßt:

Mittels Congestion Avoidance paßt TCP seine Sendeintensität dynamisch den sich verändernden Bedingungen im Netz an. Man unterstellt dabei, daß SRTT und RTO mit Hilfe der weiter oben diskutierten Techniken sinnvoll eingestellt wurden, so daß ein Timeout mit hoher Wahrscheinlichkeit auf einen Paketverlust hindeutet. Daran zeigt sich noch einmal recht deutlich die Notwendigkeit einer möglichst guten Schätzung der SRTT, die ja die wichtigste Basis für den RTO darstellt.

Pakete gehen aus zwei Gründen verloren: durch Beschädigung beim Transport oder infolge des Verwerfens bei einer Congestion. In den meisten Netzen werden allerdings deutlich weniger als 1 Prozent der Pakete beschädigt, so daß Paketverluste fast immer eine Congestion anzeigen, wobei als Indikatoren nicht nur Timeouts dienen, sondern auch Duplikate bereits empfangener Bestätigungen.

Nachfolgend wollen wir uns die in praktischen TCP-Implementierungen genutzte Kombination von Slow-Start und Congestion Avoidance anschauen. Als Basis sollen die Beschreibungen von Stevens im Band 1 von TCP/IP Illustrated sowie im RFC 2001 dienen. Der Algorithmus, dessen Details z.T. implementationsabhängig sind, sieht im wesentlichen folgendermaßen aus:

  1. Der Sender verwaltet zum Zweck der Congestion-Behandlung zwei Variablen: die Größe des Congestion-Fensters, cwnd, sowie einen Schwellwert für den Slow-Start, ssthresh, der das Umschalten zwischen den beiden Algorithmen steuert. Beide Werte werden in Bytes angegeben.

    cwnd wird für jede neue Verbindung mit der Größe eines Segments (MSS) und ssthresh mit 65535 initialisiert.

  2. Beim Senden verhält sich TCP so, als entspräche die Größe des Sendefensters dem Minimum von cwnd und der vom Empfänger im TCP-Kopf spezifizierten Fenstergröße. D.h., wie wir oben schon erwähnt hatten, daß dieses Minimum von cwnd und der Größe des Empfangsfensters das Maximum der Anzahl der Bytes darstellt, die TCP aktuell versenden darf.

    Die Angabe der Fenstergröße im TCP-Kopf dient der vom Empfänger gesteuerten Flußkontrolle und hängt vom verfügbaren Empfangspuffer ab. Congestion Avoidance ist dagegen eine vom Sender ausgehende und an der Netzlast orientierte Steuerung des Datenflusses.

  3. Sobald eine durch Timeout oder Quittungs-Duplikate angezeigte Congestion eintritt, wird die halbe Größe des aktuellen Sendefensters, mindestens aber die Länge von zwei Segmenten (2×MSS), in ssthresh gespeichert. Dies bewirkt die multiplikative Abnahme der Fenstergröße bei Congestion Avoidance. Sofern ein Timeout als Indikator vorlag, setzt man zusätzlich cwnd auf die Byteanzahl eines Segments (MSS) und initiiert so den Slow-Start.

  4. Trifft eine Bestätigung neuer Daten ein, erhöhen wir cwnd, wobei die Details davon abhängen, ob wir uns gerade in der Phase Congestion Avoidance oder Slow-Start befinden.

    Solange cwnd kleiner als oder gleich ssthresh ist, wird der Slow-Start fortgeführt, d.h., cwnd wächst um ein Segment. Das durch den Slow-Start bewirkte exponentielle Öffnen des Congestion-Fensters (1, 2, 4, 8, 16, ...) dauert bis zum Erreichen der in ssthresh gespeicherten und als sicherer Arbeitspunkt angesehenen halben Größe desjenigen Fensters an, das Paketverluste verursacht und so zum Slow-Start geführt hat.

    Danach geht der Algorithmus zur Congestion Avoidance über und erhöht die Fenstergröße nur noch langsam, um sich bis zur verfügbaren Bandbreite vorzutasten. Konkret bedeutet das, mit jeder Bestätigung für neue Daten wird cwnd um die durch N geteilte Größe eines Segments (MSS/N Bytes) erhöht. Es handelt sich hierbei um eine lineare Zunahme der Fenstergröße, im Gegensatz zur exponentiellen bei Slow-Start. Wie wir oben gesehen haben, öffnet sich dadurch das Fenster pro Zeitintervall der Länge RTT um maximal 1 Segment, unabhängig davon, wieviele Quittungen in diesem Intervall empfangen wurden. Bei Slow-Start wird cwnd dagegen um die Anzahl der innerhalb eines RTT-Intervalls empfangenen Quittungen inkrementiert.

Jacobson hat 1990 eine modifizierte Version dieses Algorithmus vorgeschlagen, die zwei zusätzliche Techniken enthält: Fast Retransmit und Fast Recovery. Bevor wir uns die Änderungen näher ansehen, wollen wir zunächst eine Vorbetrachtung anstellen.

Für ein Segment, das außerhalb der normalen Reihenfolge (out-of-order) ankommt, d.h. dessen Sequenznummer nicht am linken Rand des Empfangsfensters liegt, kann und sollte TCP unverzüglich eine Quittung generieren. Diese wiederholt allerdings, bedingt durch ihren kumulativen Charakter, zwangsläufig die zuletzt ausgesendete Bestätigungsnummer und wird daher auch als duplicate ACK bezeichnet. Der Sinn dieser duplizierten Quittungen besteht darin, den Sender umgehend zu informieren, daß ein Segment außerhalb der normalen Reihenfolge angekommen ist.

Duplizierte Quittungen können sowohl eine Umordnung als auch den Verlust von Paketen anzeigen. Man geht davon aus, daß im Falle der Umordnung von Segmenten nur sehr wenige (1 oder 2) duplizierte Bestätigungen beim Sender eintreffen und danach wieder ein neue Quittung erscheint, da mittlerweile das am linken Fensterrand liegende Segment empfangen wurde.

Treffen dagegen hintereinander drei oder mehr duplizierte Bestätigungen beim Sender ein, so ist mit hoher Wahrscheinlichkeit vom Verlust eines Segments auszugehen. In diesem Fall kommt es zum Fast Retransmit: TCP löst die Retransmission des als vernichtet betrachteten Segments sofort aus und wartet nicht erst wie sonst bis zum Ablauf des Retransmission-Timers.

Im Anschluß an den Fast Retransmit wird zum Fast Recovery übergegangen. Dieser Algorithmus besagt, daß TCP nach der durch den Fast Retransmit bewirkten Sendewiederholung nicht mit dem Slow-Start, sondern mit Congestion Avoidance fortfährt. Diese Modifikation stellt eine Verbesserung der bisherigen Situation dar, da sie im Falle einer "moderaten" Congestion einen hohen Durchsatz erlaubt. Dies gilt vor allem für große Fenster.

Duplizierte Quittungen signalisieren ihrem Empfänger nicht nur den Verlust eines von ihm gesendeten Pakets, sondern auch, daß es noch einen Datenfluß zwischen beiden Partnern gibt, denn duplizierte Bestätigungen werden ja nur dann generiert, wenn Segmente empfangen wurden, die im Bytestrom der TCP-Verbindung logisch hinter dem verlorengegangenen Segment liegen. Deshalb ist es sinnvoll, den Datenfluß nicht abrupt zu reduzieren, wie dies beim Slow-Start der Fall wäre. Das ist der Grund dafür, daß Fast Recovery den Übergang zu Congestion Avoidance und den Verzicht auf Slow-Start vorschreibt.

Fast Retransmit und Fast Recovery werden gewöhnlich kombiniert implementiert:

  1. Wenn die dritte duplizierte Quittung (duplicate ACK) in Folge eintrifft, wird die halbe Größe des aktuellen Sendefensters, mindestens aber die Länge von zwei Segmenten (2×MSS), in ssthresh gespeichert.

    Die Retransmission des verlorengegangenen Segments wird ausgelöst.

    cwnd erhält den Wert ssthresh + 3×MSS. Dadurch wird das Congestion-Fenster um die Gesamtgröße der durch die drei duplizierten Quittungen bestätigten und von ihrem Empfänger temporär im Empfangspuffer zwischengespeicherten Segmente erhöht.

  2. Bei jedem Eintreffen einer weiteren duplizierten Quittung wird cwnd um die Größe eines Segments erhöht. Dadurch wird das Congestion-Fenster um das zusätzliche Paket vergrößert, das seinen Empfänger erreicht hat.

    Sofern es der neue Wert von cwnd zuläßt, ist ein neues, d.h. bisher noch nie versendetes Daten-Paket zu übertragen, sofern seitens der Applikation entsprechende Daten vorliegen. Es geht hier also nicht um Sendewiederholungen.

  3. Wenn die nächste Quittung für neue Daten (also kein delayed ACK) eintrifft, wird cwnd auf denjenigen Wert gesetzt, der im ersten Schritt in ssthresh gespeichert worden war.

    Die gerade empfangene neue Quittung wird als reguläre, mit einer Verzögerung von einer RTT eintreffende Bestätigung der im Schritt 1 ausgelösten Retransmission interpertiert. Des weiteren sollte diese Quittung auch den Empfang all derjenigen Segmente bestätigen, die zwischen dem verlorengegangenen Paket und dem Empfang der ersten duplizierten Quittung gesendet wurden.

    Bei diesem dritten Schritt handelt es sich um Congestion Avoidance, da TCP die Größe seines Congestion-Fensters und damit seine Senderate auf die Hälfte desjenigen Wertes reduziert, der aktuell war, als der Paketverlust auftrat.


Frage 2.3.9.1:

Wie wird sich infolge der Flußsteuerung eine (knappe) Bandbreite auf mehrere TCP-Verbindungen aufteilen?

Frage 2.3.9.2:

Eine konstante, knappe Bandbreite sei bisher ausschließlich von TCP-Verbindungen genutzt worden. Zu einem bestimmten Zeitpunkt kommen mehrere UDP-basierte Paketströme hinzu, von denen jeder für sich eine konstante "Paketrate" beansprucht (z.B. ein Paket alle 20 ms). Wie wirkt sich das auf die TCP-Verbindungen aus?


© Holger Trapp, 28.5.1998