|
|
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) |
| Zeile 1: |
Zeile 1: |
| == Slow‐Start ==
| | #WEITERLEITUNG [[Transmission Control Protocol/Überlastungskontrolle#Slow‐Start]] |
| [[File:10000000000001F0000003FA16C6D581AFBE2A68.png|mini|200px]]
| |
| * 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?
| |
| | |
| [[File:100000000000026A00000079CCCF49EA7B60F589.png|200px]]
| |
| | |
| ; 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 ===
| |
| [[File:100000000000058C000003E0029DE23F83687997.png|600px| Quelle: Andrew S. Tanenbaum, „Computer Networks“, Fourth Edition, 2003]]
| |
| | |
| === Fast‐Retransmit ===
| |
| [[File:1000000000000294000003FF33D9FFE40B52F1F5.png|mini|200px]]
| |
| * 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 ===
| |
| | |
| [[File:100000000000059E000002EF2DCDB5F907FDD83E.png|600px]]
| |
| | |
| * 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:
| |
| [[File:100000000000049F000000B09BBC39E0392F3040.png|200px]]
| |
| | |
| 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:
| |
| | |
| [[File:10000000000003440000019B51F3691DF18F84C0.png|400px]]
| |
| | |
| D.h. zwischen MinThresh und MaxThresh als Formel:
| |
| | |
| [[File:10000000000003AF000000967788DF9AF0FE5CA4.png|400px]]
| |
| | |
| Zähle die Anzahl count der nicht verworfenen Pakete während AvgLen zwischen MinThresh und MaxThresh war und berechne:
| |
| | |
| [[File:10000000000003760000007EFDC9243F34C0EDF4.png|400px]]
| |
| | |
| == 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 | |
| [[Kategorie:Transmission Control Protocol]] | |