Transmission Control Protocol/Slow‐Start

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