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
Bildquelle: Andrew S. Tanenbaum, „Computer Networks“, Fourth Edition, 2003
Fast‐Retransmit
Erinnerung: 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
Datei:Bild4.png* 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
TCP erlaubt Implementationsvarianten
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
diskutierten 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 und Literatur
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
Eine 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
Die Unterscheidung zwischen Überlastkontrolle und
Überlastvermeidung
Literatur
- [PetersonDavie2007] Larry L. Peterson and Bruce S. Davie, „Computer Networks: A Systems Approach“, Edition 4, 2007