Die Transportschicht
Das Internet ist beeindruckend! Ich kann von meinem Airbnb in Südfrankreich aus, wo ich gerade Urlaub mache, Datenpakete an einen Server in New York senden, und erhalte innerhalb von weniger als 100 Millisekunden eine Antwort. Ich kann das beweisen:
sudo mtr -rw 158.255.213.100
# HOST: Lucs-MacBook-Pro.local Loss% Snt Last Avg Best Wrst StDev
# 1.|-- 192.168.1.1 0.0% 10 2.2 2.8 2.2 7.2 1.6
# 2.|-- 192.168.10.254 0.0% 10 2.5 3.0 2.5 5.8 1.0
# 3.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 4.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 5.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 6.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 7.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 8.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 9.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 10.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 11.|-- ??? 100.0 10 0.0 0.0 0.0 0.0 0.0
# 12.|-- 100-213-255-158.static.edis.at 0.0% 10 94.2 94.7 89.8 105.3 4.2Der obige Befehl zeigt die Zwischenstationen (Router) und die Gesamtlaufzeit der Pakete auf dem Weg von meinem Laptop (Lucs-MacBook-Pro.local) zum Server in New York (158.255.213.100) an. Aus Sicherheitsgründen antworten nicht alle Router auf die Anfragen des Befehls, um die genaue Struktur des Internets nicht öffentlich preiszugeben. Dennoch ist ersichtlich, dass die Datenpakete auf ihrem Weg zehn Router passieren. Das sind zehn Abzweigungen, bei denen jeweils der richtige Ausgang genommen werden musste.
Was passiert, wenn beim Download einer grossen Datei ein Datenpaket auf dem Weg verloren geht – eines von Tausenden? Wie kann sichergestellt werden, dass der Download trotzdem funktioniert? Oder was passiert, wenn ein später gesendetes Paket vor einem früheren Paket am Ziel ankommt? Ist dann der gesamte Datentransfer durcheinander? Hinzu kommen die Performanz-Aspekte: Wie kann die verfügbare Bandbreite möglichst gut ausgenutzt werden, ohne das Netz zu überlasten? Genau diesen Fragen zur Zuverlässigkeit und Performance des Internets möchte ich in diesem Blogpost nachgehen.
Die Schichten des Internets
Wie viele andere gute Dinge ist auch das Internet geschichtet. Die einzelnen Schichten sind voneinander unabhängig, sodass auf unterschiedlichen Schichten unterschiedliche Protokolle eingesetzt werden können. So bleibt trotz der Komplexität des Gesamtkonstrukts eine gewisse Flexibilität erhalten, die es ermöglicht, überschaubare Komponenten zu entwickeln, zu verbessern und auszutauschen.
Die oberste Schicht ist die Anwendungsschicht (Schicht 7). In ihr sind die Anwendungen zu finden, die auf Basis des Internets entwickelt wurden. Ein Beispiel ist ein Webserver, der über das Hypertext Transfer Protocol (HTTP) eine Website wie Google oder Facebook an einen Nutzer sendet. Das Herzstück des Internets ist die Netzwerkschicht (Schicht 3). In dieser Schicht befindet sich das Internet Protocol (IP), das festlegt, wie Pakete von einem Router zum nächsten gesendet werden. Es organisiert gewissermassen die zehn Sprünge (Hops auf Englisch), die meine Pakete von Südfrankreich aus in die USA genommen haben. Obwohl IP in der Praxis sehr gut funktioniert, garantiert es streng genommen keine Zuverlässigkeit – es ist ein «Best Effort»-Service. Für Zuverlässigkeit und Performance braucht es eine Schicht dazwischen: die Transportschicht (Schicht 4). Sie ist es, die das Internet gut macht.
Im Gegensatz zur Netzwerkschicht, die über alle Router des Internets verteilt ist, findet die Transportschicht in den Endpunkten einer Verbindung statt. Im obigen Beispiel sind das mein Laptop und der Server in New York. Die Transportschicht muss gewährleisten, dass die Internetverbindung trotz des formal unzuverlässigen Services der Netzwerkschicht stets (i) zuverlässig und (ii) performant funktioniert. In der Praxis wird das meist durch das Transmission Control Protocol (TCP) erreicht. Im Folgenden werde ich erläutern, wie die Punkte (i) und (ii) in TCP umgesetzt sind.
Das Transmission Control Protocol (TCP)
Zuverlässige Datenübertragung
Beginnen wir mit der zuverlässigen Datenübertragung (reliable data transfer, RDT): Die Transportschicht des Senders erhält Daten von der Anwendungsschicht über ihr und übermittelt sie über die unzuverlässige Netzwerkschicht an den Empfänger. Die Transportschicht des Empfängers empfängt die Daten von der Netzwerkschicht unter ihr und leitet sie an die Anwendungsschicht weiter. Wenn die Netzwerkschicht zuverlässig wäre, dann würde die Arbeit der Transportschicht diagrammatisch ganz einfach aussehen:
In obigem Diagramm werden Zustände als blaue Kreise und Aktionen als Pfeile dargestellt. Die Transportschicht des Senders schickt Pakete (in der Transportschicht Segmente genannt) zum Empfänger, die im Fall hier alle korrekt und in der richtigen Reihenfolge ankommen. Es fliessen alle Segmente nur in eine Richtung: vom Sender zum Empfänger.
In der Realität können Segmente jedoch von der Netzwerkschicht falsch übermittelt werden. Betrachten wir zunächst den Fall, dass die Segmente zwar alle in der richtigen Reihenfolge ankommen, bei einem aber fälschlicherweise ein Bit geändert wurde (z.B. eine 0 in eine 1).
Alle TCP-Segmente enthalten eine Checksumme, die vom Sender auf Basis des Paketinhalts errechnet wird. Bei Erhalt des Segments berechnet der Empfänger die Checksumme neu und vergleicht das Ergebnis mit der im Segment enthaltenen Checksumme. Stimmen diese beiden Werte nicht überein, weiss der Empfänger, dass der Inhalt des Segments auf dem Weg verändert worden sein muss. Er kann den Sender dann auffordern, das veränderte Segment erneut zu übermitteln. Dies geschieht mittels Bestätigungen (ACKs, vom Englischen acknowledgements).
Die Idee dabei ist, dass die Segmente nummeriert werden und der Empfänger jeweils eine Bestätigungsnachricht (ein ACK) mit der Nummer des zuletzt korrekt empfangenen Segments zurücksendet. Im vereinfachten Fall, dass der Sender zu jedem Zeitpunkt nur ein Segment mit ausstehender Bestätigung ausgesendet hat, genügen die Segmentnummern 0 und 1. Der Sender funktioniert dann wie folgt:
Der Sender verschickt ein Segment mit der Nummer 0 oder 1 über den unzuverlässigen Kanal der Netzwerkschicht (unreliable data transfer, UDT) und wartet darauf, bis das Segment von der Gegenseite mit einem entsprechenden ACK bestätigt wurde. Falls dies geschieht, so erstellt er das nächste Segment mit der Nummer 1 oder 0. Falls dies nicht geschieht (z.B. wenn die Gegenseite statt des neuen Segments den Erhalt des letzten Segments erneut bestätigt), überträgt der Sender das gleiche Segment erneut.
Der Empfänger funktioniert analog dazu:
Der Empfänger erwartet ein Segment mit der Nummer 0 oder 1 und bestätigt es mit einem ACK, wenn er es erhält. Anschliessend erwartet er ein Segment mit der Nummer 1 oder 0. Falls er ein falsches Segment erhält, bestätigt er dem Sender das zuletzt korrekt erhaltene Segment erneut. Der Erhalt einer doppelten Bestätigung informiert also den Sender, dass nicht das erwartete nächste Segment empfangen wurde. Dadurch wird das Setup einfacher: Anstatt ACKs und NAKs (Nicht-ACKs) werden nur ACKs benötigt.
Durch die Übertragung von Datenpaketen vom Sender zum Empfänger und von Bestätigungspaketen vom Empfänger zurück zum Sender kann ein zuverlässiger Paketaustausch sichergestellt werden. Es gibt jedoch ein Problem: Was passiert, wenn ein Segment auf dem Weg verloren geht, also gar nicht erst beim Empfänger ankommt? In diesem Fall kann der Empfänger gar nicht wissen, dass ein Segment gesendet wurde und entsprechend auch keine Bestätigung zurückschicken.
Für diesen Fall muss ein Timer hinzugefügt werden, der mit dem Versenden eines Segments auf der Senderseite gestartet wird und jeweils beim Erhalt der entsprechenden Bestätigung gestoppt wird. Läuft der Timer ab, bevor das Segment bestätigt wurde, geht der Sender davon aus, dass es auf dem Weg verloren gegangen ist, und versendet es erneut. Der Sender wird wie folgt angepasst:
Der Empfänger muss nicht angepasst werden, da er beim Verlust eines Segments nichts mitbekommt.
Mehr Segmente
Das oben beschriebene RDT 3.0-Protokoll ist zwar zuverlässig, aber unglaublich langsam. In einem TCP-Segment können gewöhnlich etwa 1460 Bytes (Maximum Segment Size, MSS) an Daten versendet werden. Wenn die Reisedauer eines Segments 100 Millisekunden vom Sender zum Empfänger und zurück beträgt (wie im obigen Beispiel), könnte man damit maximal 14.6 kB/s übertragen. Das reicht nicht für hochauflösende Katzenvideos.
Glücklicherweise gibt es eine einfache Lösung: Der Sender verschickt mehr Segmente gleichzeitig, ohne das ACK für jedes einzelne Segment abzuwarten. Wenn das Verschicken weniger lange dauert als die Reise der Segmente – was in der Praxis meist der Fall ist –, wird so eine Menge Zeit gespart.
Um den Überblick über die verschickten Segmente zu behalten, müssen die Segmentnummern von 0 und 1 auf eine fortlaufende ganze Zahl erweitert werden. Als Segmentnummer wird die Nummer des ersten Bytes im jeweiligen Segment in Bezug auf den gesamten Datenstrom verwendet. Das heisst, wenn das erste Segment die Nummer 200 und eine Länge von 1460 Bytes (MSS) hat, so erhält das zweite Segment die Nummer 1660, das dritte die 3120, und so weiter. Der Empfänger bestätigt den korrekten Erhalt eines Segments (und aller Segmente davor) mit der Segmentnummer, die er als nächstes erwartet. Das heisst, er erhält das Segment mit der Nummer 200 und sendet ein ACK mit der Nummer 1660 zurück. Er erhält das Segment mit der Nummer 1660 und sendet ein ACK mit der Nummer 3120 zurück, und so weiter.
sendBase und nextSeqNumAnstatt zwischen den Zuständen 0 und 1 zu wechseln (siehe RDT 3.0 oben), speichert der Sender nun zwei Zahlen ab: Erstens die Segmentnummer des ältesten bereits verschickten Segments mit ausstehender Bestätigung (sendBase) und zweitens die Segmentnummer des nächsten zu verschickenden Segments (nextSeqNum). In Pseudocode funktioniert dies wie folgt:
# Assume sender is not constrained by the TCP flow or congestion control,
# that data from above is less than MSS in size,
# and that data transfer is in one direction only
sendBase = CreateInitialSeqNumber() # at random
nextSeqNum = CreateInitialSeqNumber() # at random
loop (forever) {
switch (event)
event: data received from application layer above
create TCP segment with sequence number nextSeqNum
if (timer currently not running)
start timer
pass segment to network layer
nextSeqNumber = nextSeqNum + Length(data)
break;
event: timer timeout
retransmit not-yet-ACKed segment with smallest sequence number
start timer
break;
event: ACK received, with ACK field value of y
if (y > sendBase) {
sendBase = y
if (there are currently any not-yet-ACKed segments)
start timer
}
break;
} Falls der Timer ausläuft, überträgt der Sender das älteste bereits verschickte Segment mit ausstehender Bestätigung erneut – und nur dieses. Dahinter steckt die Annahme, dass der Empfänger alle erhaltenen Segmente in einem Buffer zwischenspeichert. Geht ein Segment auf dem Weg verloren, überträgt der Sender es nach Ablauf des Timers erneut, und der Empfänger kann nach dessen erfolgreichem Erhalt direkt auch die im Buffer zwischengespeicherten Folgesegmente verarbeiten.
Damit haben wir unser RDT-Protokoll von 14.6 kB/s auf eine a priori unlimitierte Bandbreite erweitert. So weit, so
Eine weitere Leistungsverbesserung besteht darin, dass nicht nur im Fall des Ablaufs des Timers das älteste unbestätigte Segment erneut versendet wird, sondern dies auch beim Erhalt duplizierter ACKs geschieht. Angenommen, Segment 200 geht auf dem Weg verloren, dann schickt der Empfänger beim Erhalt von Segment 1660 ein ACK mit 200. Gleiches gilt für Segment 3120, das wiederum mit einem ACK mit 200 beantwortet wird, und so weiter. Der Sender kann die mehrfach erhaltenen ACKs als Hinweis dafür nehmen, dass das Segment 200 nicht korrekt übertragen wurde, und dies entsprechend nachholen. In Pseudocode sieht das wie folgt aus:
# Assume sender is not constrained by the TCP flow or congestion control,
# that data from above is less than MSS in size,
# and that data transfer is in one direction only
sendBase = CreateInitialSeqNumber() # at random
nextSeqNum = CreateInitialSeqNumber() # at random
loop (forever) {
switch (event)
event: ...
event: ...
event: ACK received, with ACK field value of y
# new ACK
if (y > sendBase) {
sendBase = y
if (there are currently any not-yet-ACKed segments)
start timer
}
# duplicate ACK
else {
increment number of duplicate ACKs received for y
if (number of duplicate ACKs received for y == 3)
resend segment with sequence number y
}
break;
}Überlastungskontrolle
Damit sind wir schon sehr weit gekommen. Ein grosses Problem habe ich jedoch bisher überhaupt nicht angesprochen:
Taylor Swift. Nein, folgendes: Wie viele unbestätigte Segmente dürfen wir gleichzeitig versenden, ohne das System zu überlasten? Wenn wir zu wenige gleichzeitig versenden, lassen wir verfügbare Bandbreite ungenutzt. Versenden wir zu viele, laufen die Buffer von Routern entlang des Weges über, Segmente gehen verloren, und wir müssen ständig Segmente nachübertragen. Im schlimmsten Fall verstopfen wir so das gesamte Netzwerk. Hinzu kommt, dass sich die Auslastung des Netzwerks stetig ändern kann, abhängig davon, was andere Nutzer gleichzeitig tun.
TCP implementiert eine dynamische Ende-zu-Ende-Überlastungskontrolle, die ausschliesslich auf den Informationen der beiden miteinander kommunizierenden Endpunkten basiert. TCP überwacht zwei Zahlen: Erstens das Empfangsfenster (rwnd, vom Englischen receive window), das angibt, wie viel Speicherplatz im Buffer des Empfängers noch verfügbar ist. Zweitens das Überlastungsfenster (cwnd, vom Englischen congestion window), das abschätzt, wie viele Segmente gleichzeitig über das Netz übertragen werden können, ohne es zu überlasten. Der Sender überträgt zu jeder Zeit nur so viele Segmente, dass beide Fenster eingehalten werden:
nextSeqNum - sendBase <= min(rwnd, cwnd)Während der Wert von rwnd exakt ist, da er dem Sender vom Empfänger in den ACK-Segmenten mitgeteilt wird, ist der Wert von cwnd eine Schätzung. Meist äussert sich die Überlastung des Netzwerks darin, dass ein Router mit dem Weiterleiten der Pakete nicht mehr nachkommt und sein Buffer überläuft. Diese Information ist für die Transportschicht jedoch nicht (immer) verfügbar, da sie ausschliesslich in den Endpunkten einer Verbindung stattfindet. Das einzige für die Transportschicht erkennbare Symptom einer Überlastung sind verlorene Segmente.
Um cwnd zu jedem Zeitpunkt möglichst akkurat abzuschätzen, verwendet TCP drei Zustände: Slow Start, Congestion Avoidance und Fast Recovery. Im Folgenden werde ich jeden Zustand kurz für das «klassische» TCP Reno beschreiben. Modernere TCP-Algorithmen diskutiere ich in einem nächsten Beitrag, siehe unten.
Slow Start
Beim Slow Start wird der Schwellwert (ssthresh, vom Englischen slow start threshold) von cwnd grob abgeschätzt, ab dem Überlastung beginnt einzusetzen. Dazu werden cwnd zunächst auf einen sehr kleinen Wert (z.B. 1 MSS), und ssthresh auf einen unendlich grossen Wert initialisiert. Für jedes erfolgreich bestätigte Segment wird cwnd anschliessend um ein MSS erhöht:
cwnd = cwnd + mss Dadurch wächst cwnd zeitlich exponentiell:
cwndSlow Start endet, wenn
- ein Timeout eintritt. Dies ist ein Zeichen dafür, dass
cwndzu gross ist und eine Überlastung des Netzes stattgefunden hat. In diesem Fall wirdssthresh = cwnd/2gesetzt undcwndwird neu initialisiert (z.B. auf 1MSS). Anschliessend wird Slow Start mit dem verbesserten Schwellwert erneut durchgeführt. cwndden Schwellwertssthresherreicht. Ab diesem Zeitpunkt ist Vorsicht geboten und Slow Start geht in Congestion Avoidance über (siehe unten).- drei duplizierte
ACKs erhalten wurden. Das ist ein Zeichen dafür, dass eine kleinere Störung im Netz vorliegt. Der Schwellwert wird aufssthresh = cwnd/2angepasst undcwnd = ssthresh + 3 MSS. Anschliessend geht Slow Start in Fast Recovery über (siehe unten).
Congestion Avoidance
Sobald cwnd den Bereich erreicht, ab dem Überlastung eintritt, sollte der Wert nur noch langsam erhöht werden. Genau das ist die Idee hinter Congestion Avoidance. Anstatt cwnd wie in Slow Start exponentiell zu erhöhen, erhöht Congestion Avoidance das Überlastungsfenster pro erfolgreich bestätigtem Segment lediglich um
cwnd = cwnd + mss * mss/cwnd Diese Formel bedeutet, dass cwnd nur noch (annähernd) linear mit der Zeit wächst.
cwndCongestion Avoidance endet bei einem Timeout oder drei duplizierten ACKs, analog zu Slow Start.
Fast Recovery
Fast Recovery ist nicht unbedingt notwendig, da die Überlastungskontrolle auch mit Slow Start und Congestion Avoidance umgesetzt werden kann. Es ist jedoch nützlich, um kleinere Störungen im Netz aufzulösen. Wenn nämlich nur ein einziges Segment verloren geht, erfährt der Sender durch den Erhalt mehrerer (in Praxis wird drei als Schwellwert genommen) duplizierter ACKs davon. Das gibt ihm zwei Informationen: Erstens ist das Netz potenziell leicht überlastet und zweitens sind drei gesendete Segmente beim Empfänger angekommen. Unter diesen Segmenten war zwar nicht das nächste vom Empfänger erwartete Segment (daher die duplizierten ACKs), aber dennoch sind das drei Segmente, die bereits beim Empfänger liegen und nicht mehr das Netz verstopfen. Der Sender adressiert beide Punkte, indem er
ssthresh = cwnd / 2
cwnd = ssthresh + 3 msssetzt und das unbestätigte Segment erneut sendet. Für jedes weitere duplizierte ACK kann der Sender
cwnd = cwnd + msssetzen, da ein weiteres Segment beim Empfänger angekommen ist, das jetzt dort im Buffer liegt. Dadurch stellt Fast Recovery sicher, dass im Falle einer geringen Überlastung die Datenübertragung nicht sofort hart gedrosselt wird, sondern der Datenfluss mit etwas geringerer Rate weiterläuft.
Findet ein Timeout statt, geht Fast Recovery wie die anderen Zustände zu Slow Start zurück. Wird das unbestätigte Segment schliesslich bestätigt, wird wieder cwnd = ssthresh gesetzt und Fast Recovery wechselt zu Congestion Avoidance.
Die Überlastungskontrolle von TCP Reno sieht in ihrer ganzen Pracht wie folgt aus:
Ausblick
In diesem Beitrag habe ich mir die Grundlagen der Transportschicht basierend auf dem «klassischen» TCP Reno angesehen. Dabei habe ich viele spannende Punkte ausgelassen, zum Beispiel den TCP-Handshake, moderne TCP-Algorithmen (PRR, CUBIC, HyStart), oder die Fairness der Überlastungskontrolle. Aber keine Sorge, ich greife auf die Doppellauf-Schrotflinte zurück: In einer Woche folgt ein weiterer Blogbeitrag, in dem ich das moderne TCP des Linux-Kernels auf eine verlustbehaftete Netzwerkverbindung loslasse und im Detail analysiere, was passiert.
Bis dahin…
Quellen
Viele Informationen und Ideen dieses Beitrags stammen aus dem Buch Computer Networking – A Top-Down Approach. Auch die Grafiken sind an Grafiken im Buch angelehnt. Das Buch ist super.
Beitragsbild: Photo by Taylor Vick on Unsplash
Katzen-GIFs: