Wie funktioniert das Internet?

TCP in Aktion

In meinem letzten Blogbeitrag habe ich die Grundlagen der Transportschicht basierend auf dem «klassischen» TCP Reno diskutiert. Diese besteht aus den Zuständen Slow Start, Congestion Avoidance und Fast Recovery, die diagrammatisch dargestellt wie folgt ineinander übergehen:

Falls diese Konzepte noch unklar sind, lohnt es sich, vor diesem Beitrag den vorherigen anzuschauen. In diesem Beitrag zeige ich TCP Reno und die modernen TCP-Algorithmen, die vom Linux-Kernel verwendet werden, in Aktion. Dazu lasse ich sie auf eine simulierte, verlustbehaftete Netzwerkverbindung los.

Das Setup

Ich verwende einen Desktop-PC mit Ubuntu 26.04 LTS und ändere zunächst das Verhalten des Loopback-Interfaces (lo), sodass sich sein Traffic wie echter Ethernet-Traffic mit einer Segmentgrösse von 1500 Bytes verhält:

sudo ip link set dev lo mtu 1500            # set MTU to 1500 Bytes
sudo ethtool -K lo tso off gso off gro off  # turn off offload mechanisms

sudo ip link set dev lo mtu 1500            # set MTU to 1500 Bytes
sudo ethtool -K lo tso off gso off gro off  # turn off offload mechanisms

Anschliessend füge ich dem Loopback-Interface eine Zeitverzögerung von 50 Millisekunden, eine Transmissionsrate von 10 MBit/s, einen Buffer von 100 Segmenten und eine Verlustwahrscheinlichkeit von 0% (später 0.1%) hinzu:

# Clear anything already on lo
sudo tc qdisc del dev lo root 2>/dev/null

# Set delay, rate, limit and loss
sudo tc qdisc add dev lo root netem delay 50ms rate 10mbit limit 100 loss 0% # or loss 0.1%

# Clear anything already on lo
sudo tc qdisc del dev lo root 2>/dev/null

# Set delay, rate, limit and loss
sudo tc qdisc add dev lo root netem delay 50ms rate 10mbit limit 100 loss 0% # or loss 0.1%

Diese Einstellungen werden jeweils beim Verlassen des Loopback-Interfaces (Egress) angewendet:

Insgesamt beträgt die Zeitverzögerung der Pakete sowohl vom Sender zum Empfänger als auch vom Empfänger zum Sender jeweils mindestens 50 Millisekunden. Dazu kommt die Zeit, die die Pakete aufgrund der limitierten Bandbreite von 10 MBit/s im Buffer verbringen. Pakete können verloren gehen, wenn der Buffer überläuft, oder wenn sie zufällig (mit einer Wahrscheinlichkeit von 0% bzw. 0.1%) fallengelassen werden. Letzteres geschieht ebenfalls in beide Richtungen.

Als nächstes wähle ich den Algorithmus für die Überlastungskontrolle. Standardmässig verwendet Linux TCP CUBIC (mehr dazu später). Zunächst möchte ich aber TCP Reno in Aktion sehen:

sudo sysctl -w net.ipv4.tcp_congestion_control=reno    # or cubic

sudo sysctl -w net.ipv4.tcp_congestion_control=reno    # or cubic

Als Server verwende ich einen einfachen HTTP-Server, der ein 10 MiB grosses Testfile mit zufälligen Daten (testfile.bin) über lo (127.0.0.1) bereitstellt:

# Create random 10MiB of data 
dd if=/dev/urandom of=testfile.bin bs=1M count=10

# Serve test file on loopback interface
python3 -m http.server 8080 --bind 127.0.0.1

# Create random 10MiB of data 
dd if=/dev/urandom of=testfile.bin bs=1M count=10

# Serve test file on loopback interface
python3 -m http.server 8080 --bind 127.0.0.1

Auf der Client-Seite verwende ich curl, um das Testfile herunterzuladen:

# Download test file from loopback interface
curl -o /dev/null http://127.0.0.1:8080/testfile.bin

# Download test file from loopback interface
curl -o /dev/null http://127.0.0.1:8080/testfile.bin

Am heruntergeladenen File selbst bin ich nicht interessiert, daher sende ich den Output direkt nach /dev/null. Sehr wohl interessieren mich aber die TCP-Segmente, die über lo versendet werden, sowie die Werte für cwnd und ssthresh, die der Linux-Kernel während der Übertragung wählt. Um beide aufzuzeichnen, starte ich vor dem Download folgende Befehle:

# Capture TCP segments with tshark
sudo tshark -i lo -f 'tcp port 8080' -w capture.pcap

# Capture cwnd and ssthresh with bpftrace
sudo bpftrace -e '
kprobe:tcp_rcv_established
/((struct sock *)arg0)->__sk_common.skc_num == 8080/
{
  $tp = (struct tcp_sock *)arg0;
  printf("%llu cwnd=%u ssthresh=%u srtt=%u snd_wnd=%u rcv_wnd=%u\n",
         nsecs, $tp->snd_cwnd, $tp->snd_ssthresh,
         $tp->srtt_us >> 3, $tp->snd_wnd, $tp->rcv_wnd);
}' > tcp_probe.log

# Capture TCP segments with tshark
sudo tshark -i lo -f 'tcp port 8080' -w capture.pcap

# Capture cwnd and ssthresh with bpftrace
sudo bpftrace -e '
kprobe:tcp_rcv_established
/((struct sock *)arg0)->__sk_common.skc_num == 8080/
{
  $tp = (struct tcp_sock *)arg0;
  printf("%llu cwnd=%u ssthresh=%u srtt=%u snd_wnd=%u rcv_wnd=%u\n",
         nsecs, $tp->snd_cwnd, $tp->snd_ssthresh,
         $tp->srtt_us >> 3, $tp->snd_wnd, $tp->rcv_wnd);
}' > tcp_probe.log

Soweit so gut, wir können starten…

TCP Reno

TCP-Handshake

Die TCP-Verbindung beginnt mit dem üblichen Handshake: Der Client sendet ein SYN-Segment (Segment 1) an den Server. Aufgrund der oben konfigurierten Zeitverzögerung, und da der Buffer noch leer ist, antwortet dieser 50 Millisekunden später mit einem SYN-ACK (Segment 2). Der Handshake wird durch das letzte ACK-Segment (Segment 3) vom Client an den Server finalisiert. Während des Handshakes einigen sich beide Seiten auf die Menge an Daten (MSS), die pro TCP-Segment gesendet werden soll (hier 1460 Bytes), und sie teilen sich gegenseitig ihr Empfangsfenster (Win oder rwnd) mit.

Die Segmentnummern (Seq) beginnen auf beiden Seiten bei 0, da TShark für ein einfacheres Verständnis die relativen Segmentnummern anzeigt. In Wirklichkeit initialisieren beide Seiten ihre Segmentnummern jedoch zufällig, sodass im Falle des Eintreffens von Segmenten einer vorherigen TCP-Verbindung diese von den Paketen der neuen Verbindung unterschieden werden können.

HTTP-Request

Anschliessend beginnt die Übertragung des HTTP-Requests:

Der Client sendet den HTTP-GET-Request für das testfile.bin an den Server (Segment 4). Der Server bestätigt den Erhalt des TCP-Segments mit einem ACK (Segment 5), und sendet anschliessend ein HTTP-Paket mit dem Statuscode 200 an den Client zurück. Damit wird auch auf Anwendungsschicht der Erhalt des GET-Requests bestätigt.

Slow start

Nun beginnt der eigentliche Datentransfer:

Unmittelbar nach Segment 6 sendet der Server neun weitere Segmente. Diese enthalten Teile der Daten von testfile.bin. Insgesamt hat der Server in dieser ersten Phase somit zehn Segmente versendet. Das ist kein Zufall: cwnd wird von Linux bei einer neuen TCP-Verbindung auf zehn initialisiert, während ssthresh auf unendlich gesetzt wird. Durch das Limit

nextSeqNum - sendBase <= min(rwnd, cwnd)

nextSeqNum - sendBase <= min(rwnd, cwnd)

kann der Server nicht mehr als zehn unbestätigte Pakete gleichzeitig versenden.

50 Millisekunden später kommen die Pakete beim Client an, der deren Erhalt mit ACKs bestätigt:

Da wir uns im Slow Start befinden, erhöht der Server bei jedem Erhalt eines ACKs sein Überlastungsfenster (cwnd). Im nächsten Schritt wird er daher zunächst 20 Segmente gleichzeitig versenden, dann 40, 80, und so weiter. Die folgende Grafik zeigt cwnd und ssthresh als Funktionen der Zeit:

Während Slow Start (Bereich ① in der Grafik) wächst cwnd exponentiell – es wird nach jeder Rundlaufzeit (RTT, vom Englischen round trip time) verdoppelt. Anfangs beträgt die RTT aufgrund der eingestellten Zeitverzögerung und des leeren Buffers ziemlich genau 100 Millisekunden. Dies wird durch die Streifen mit einer Breite von 100 Millisekunden im Hintergrund der Grafik verdeutlicht.

Fast REcovery

Irgendwann versendet der Server so viele Pakete gleichzeitig, dass der Buffer des simulierten Routers, der 100 Segmente fasst, überläuft – es gehen Pakete verloren. Der Server erfährt davon durch den Erhalt duplizierter ACKs und wechselt in den Fast Recovery Modus (Bereich ② in obiger Grafik). Im «klassischen» TCP Reno würde der Server nun sofort cwnd und ssthresh auf

ssthresh = cwnd / 2 
cwnd = ssthresh + 3 mss

ssthresh = cwnd / 2 
cwnd = ssthresh + 3 mss

setzen, das älteste unbestätigte Paket erneut versenden und cwnd bei jedem weiteren erhaltenen duplizierten ACK um

cwnd = cwnd + mss 

cwnd = cwnd + mss 

erhöhen. Dieser Zustand würde enden, wenn das älteste unbestätigte Paket bestätigt wird oder der entsprechende Timer ausläuft. Dieser Algorithmus hat mehrere Nachteile:

1. Da cwnd sofort halbiert wird, aber nextSeqNum–sendBase noch dem alten cwnd entspricht, müssen erst knapp (nextSeqNum–sendBase)/2 duplizierte ACKs beim Sender ankommen, bevor er weitere Pakete versendet. Dadurch entsteht eine «Stille» von einer halben RTT, während der der Sender keine neuen Segmente übermittelt.
2. Wenn duplizierte ACKs auf dem Weg vom Empfänger zum Sender verloren gehen, erhöht der Sender sein cwnd nicht, obwohl Segmente beim Empfänger angekommen sind und dort im Buffer liegen. Erhält der Empfänger das ausstehende Segment endlich durch die Retransmission und bestätigt alle aufeinanderfolgenden Segmente durch ein kumulatives ACK, dann schnellt nextSeqNum–sendBase beim Sender auf einen Schlag nach unten. Er überträgt auf einmal viele weitere Pakete.

Beide Punkte führen dazu, dass der Sender bei einer kleineren Störung im Netz zunächst keine neuen Daten und dann mehrere Segmente direkt nacheinander versendet – kein gutes Verhalten bei einem ohnehin überlasteten Netzwerk.

Proportional Rate reduction (PRR)

Der Proportional-Rate-Reduction (PRR) Algorithmus löst diese Probleme, indem er cwnd graduell anpasst. Er lässt den Algorithmus für die Überlastungskontrolle den neuen Wert von ssthresh wählen (im Fall von TCP Reno wäre das ssthresh = cwnd/2), und verändert dann cwnd kontinuierlich so, dass es nach einer RTT den Wert ssthresh erreicht.

Grob zusammengefasst belässt der Algorithmus cwnd zunächst auf dem Wert vor Fast Recovery. Bei Erhalt eines duplizierten ACKs versendet er aber nur in ssthresh/(nextSeqNum–sendBase) aller Fälle ein weiteres Paket. Dadurch sinkt die Anzahl der sich in Umlauf befindlichen Segmente (diese Anzahl wird Pipe gennant) innerhalb von einer RTT graduell von nextSeqNum–sendBase auf ssthresh.

In der Praxis wird PRR erst durch Selective Acknowledgements (SACKs) richtig gut. Dabei versendet der Empfänger im Falle eines Segmentverlusts nicht einfach nur ein dupliziertes ACK, sondern hängt dem ACK auch Informationen darüber an, welche Folgesegmente bereits in seinem Buffer liegen. Wenn beispielsweise das Segment mit der Nummer 200 verloren ging, die beiden folgenden Segmente aber bereits empfangen wurden und im Buffer liegen, würde der Empfänger ein SACK mit

Kind: Sack (5)
Length: 10 
left edge = 1660
right edge = 4580
[TCP SACK Count: 1]

Kind: Sack (5)
Length: 10 
left edge = 1660
right edge = 4580
[TCP SACK Count: 1]

versenden. Dank SACK kann PRR sehr genau abschätzen, wie viele Segmente aktuell noch unterwegs sind (Pipe) und wie viele bereits im Buffer des Empfängers angekommen sind. Ensprechend kann die Skalierung von cwnd angepasst werden. In Pseudocode sieht der PRR-Algorithmus wie folgt aus (siehe Proportional Rate Reduction for TCP):

# Target cwnd after recovery (set by congestion control algorithm)
ssthresh = CongestionControlAlgorithm() 
# Total bytes sent / delivered during recovery
prrOut = 0
prrDelivered = 0 
# Flight size at the start of recovery
flightSize = nextSeqNum - sendBase

loop (forever) { 
  switch (event)  
    event: ACK received during recovery 
      # deliveredData is the number of new bytes that the 
      # current acknowledgment (cumulative ACK and SACK) 
      # indicates have been delivered to the receiver
      deliveredData = delta(sendBase) + delta(SACK)
      prrDelivered += deliveredData
      pipe = EstimateCurrentPipe() # defined in RFC 3517
      
      if (pipe > ssthresh) {
        # Proportional rate reduction 
        sndCnt = Ceil(prrDelivered * ssthresh / flightSize) - prrOut
      } else {
        # Not covered here
        ...
      }
      sndCnt = Max(sndCnt, 0)
      cwnd = pipe + sndCnt
      
    event: Data transmission or retransmission
      prrOut = prrOut + dataSent
      
    event: End of recovery 
      cwnd = ssthresh
}

# Target cwnd after recovery (set by congestion control algorithm)
ssthresh = CongestionControlAlgorithm() 
# Total bytes sent / delivered during recovery
prrOut = 0
prrDelivered = 0 
# Flight size at the start of recovery
flightSize = nextSeqNum - sendBase

loop (forever) { 
  switch (event)  
    event: ACK received during recovery 
      # deliveredData is the number of new bytes that the 
      # current acknowledgment (cumulative ACK and SACK) 
      # indicates have been delivered to the receiver
      deliveredData = delta(sendBase) + delta(SACK)
      prrDelivered += deliveredData
      pipe = EstimateCurrentPipe() # defined in RFC 3517
      
      if (pipe > ssthresh) {
        # Proportional rate reduction 
        sndCnt = Ceil(prrDelivered * ssthresh / flightSize) - prrOut
      } else {
        # Not covered here
        ...
      }
      sndCnt = Max(sndCnt, 0)
      cwnd = pipe + sndCnt
      
    event: Data transmission or retransmission
      prrOut = prrOut + dataSent
      
    event: End of recovery 
      cwnd = ssthresh
}

PRR ist der Grund, warum cwnd im Bereich ② der obigen Grafik erst nach einer gewissen Verzögerung von 160 auf 80 fällt.

Congestion avoidance

Sobald das ACK für das ausstehende Segment beim Sender ankommt, wechselt dieser von Fast Recovery zu Congestion Avoidance. Er setzt cwnd auf ssthresh, was dank PRR ohnehin schon der Fall ist.

Bei TCP Reno folgt ein langsamer, linearer Anstieg, bei dem cwnd nach jeder RTT um 1 MSS erhöht wird. Dies ist im Bereich ③ der obigen Grafik gut ersichtlich. Ohne weitere Verluste bleibt der Sender für den Rest der Übertragung in Congestion Avoidance.

Um das Ganze interessanter zu machen, erhöhe ich die Anzahl der Verluste:

# Increase loss
sudo tc qdisc add dev lo root netem delay 50ms rate 10mbit limit 100 loss 0.1%

# Increase loss
sudo tc qdisc add dev lo root netem delay 50ms rate 10mbit limit 100 loss 0.1%

Dadurch gehen Segmente nicht nur bei Überlaufen des Buffers verloren, sondern es werden zufällig 0.1% aller Segmente bei der Übertragung fallengelassen.

Aufgrund der zusätzlichen Verluste wechselt der Sender häufiger zwischen Fast Recovery und Congestion Avoidance. So entsteht das typische TCP-Sägezahnmuster mit additiver Zunahme und multiplikativer Abnahme (AIMD, vom Englischen additive increase, multiplicative decrease):

TCP CUBIC

Nun möchte ich mir den TCP-Algorithmus anschauen, der heutzutage vom Linux Kernel verwendet wird. Dazu setze ich den Algorithmus für die Überlastungskontrolle zurück auf den Standardwert – TCP CUBIC:

sudo sysctl -w net.ipv4.tcp_congestion_control=cubic

sudo sysctl -w net.ipv4.tcp_congestion_control=cubic

Obwohl TCP Reno nämlich viele gute Eigenschaften hat, ist es für das moderne Internet nicht geeignet:

1. Das Internet ist lang und dick geworden (ein sogenanntes LFN, vom Englischen long fat network): Da es für die Kommunikation über weite Strecken verwendet wird, hat die Laufzeit der Segmente zugenommen – das Internet ist lang geworden. Da es für die Kommunikation grosser Datenmengen verwendet wird, haben die Bandbreiten zugenommen – das Internet ist dick geworden. Um moderne Internetverbindungen voll auszulasten, muss cwnd daher in der Regel sehr gross sein. Die vorsichtige lineare Annäherung von TCP Reno an das Optimum von cwnd ist heutzutage schlicht zu langsam.
2. Gerade in modernen Rechenzentren konkurrieren Verbindungen mit stark unterschiedlichen RTTs um dieselben Leitungen. Da TCP Reno in der Congestion Avoidance cwnd nach jeder RTT um 1 MSS erhöht, haben Verbindungen mit kürzerer RTT einen erheblichen Vorteil. Dies ist unerwünscht, wenn der Algorithmus für die Überlastungskontrolle die verfügbaren Ressourcen fair zwischen den Verbindungen aufteilen soll.

TCP CUBIC löst diese Probleme, indem es die lineare Zunahme von TCP Reno durch eine Kubikfunktion ersetzt, die mit der verstrichenen Zeit und nicht mit der Anzahl der RTTs wächst. Im Falle eines Segmentverlustes (beim Erhalt drei duplizierter ACKs) setzt TCP CUBIC

Als multiplikativer Faktor wird meist 0.7 verwendet. Anschliessend wird cwnd als Funktion der Zeit seit des letzten Verlustevents mit

skaliert. ist ein Parameter, der meist auf 0.4 gesetzt wird. Der Vorteil der Kubikfunktion ist, dass sie anfangs schnell wächst, dann aber beim Wert des letzten Verlustevents nur noch langsam zunimmt (konkaver Teil). Wieder bei angekommen, wird bei Ausbleiben eines weiteren Segmentverlustes zunächst vorsichtig und dann immer schneller weiter erhöht (konvexer Teil). So erzielt TCP CUBIC mit einer einfachen Funktion genau das gewünschte Verhalten.

In Pseudocode sieht TCP CUBIC wie folgt aus (siehe CUBIC: A New TCP-Friendly High-Speed TCP Variant):

# ==================================
# Main
# ==================================
# Initialization
beta = 0.3; C = 0.4
CubicReset()

loop (forever) { 
  switch (event)  
    event: ACK received
      adjust rttMin to track smallest RTT observed since last loss
      
      if (cwnd <= ssthresh) {
        cwnd = cwnd + 1 # exponential growth as in Slow Start
      } else {
        cnt = CubicUpdate()
        
        # Increase cwnd every cnt ACKs
        if (cwndCnt > cnt) {
          cwnd = cwnd + 1; cwndCnt = 0
        } else {
          cwndCnt = cwndCnt + 1
        }
      }
      
    event: Packet loss 
      epochStart = 0; cwndMax = cwnd
      cwnd     = (1-beta) * cwndMax
      ssthresh = (1-beta) * cwndMax
      
    event: Timeout
      CubicReset()
      transition to Slow Start as in TCP Reno 
}


# ==================================
# Helper functions
# ==================================
# Reset all parameters
function CubicReset() {
  cwndMax = 0; epochStart = 0; originPoint = 0
  rttMin = 0; K = 0; ackCnt = 0
}

# Determine increase in cwnd
function CubicUpdate() {
  # Initialize new epoch (after each loss)
  if (epochStart <= 0) {
    epochStart = tcpTimeStamp
    if (cwnd < cwndMax) {
      # Concave, then convex growth
      K = Sqrt(3, (cwndMax - cwnd)/C); originPoint = cwndMax
    } else {
      # Convex growth 
      K = 0; originPoint = cwnd
    }
  }
  
  t = tcpTimeStamp + rttMin - epochStart # when to reach target
  target = C(t - K)^3 + originPoint      # what target to reach
  
  if (target > cwnd) {
    cnt = cwnd / (target-cwnd)
  } else {
    cnt = 100 * cwnd # do not increase cwnd
  }
  
  # Fall back to TCP Reno, if it would increase cwnd faster
  CubicTCPFriendliness() 
}

# ==================================
# Main
# ==================================
# Initialization
beta = 0.3; C = 0.4
CubicReset()

loop (forever) { 
  switch (event)  
    event: ACK received
      adjust rttMin to track smallest RTT observed since last loss
      
      if (cwnd <= ssthresh) {
        cwnd = cwnd + 1 # exponential growth as in Slow Start
      } else {
        cnt = CubicUpdate()
        
        # Increase cwnd every cnt ACKs
        if (cwndCnt > cnt) {
          cwnd = cwnd + 1; cwndCnt = 0
        } else {
          cwndCnt = cwndCnt + 1
        }
      }
      
    event: Packet loss 
      epochStart = 0; cwndMax = cwnd
      cwnd     = (1-beta) * cwndMax
      ssthresh = (1-beta) * cwndMax
      
    event: Timeout
      CubicReset()
      transition to Slow Start as in TCP Reno 
}


# ==================================
# Helper functions
# ==================================
# Reset all parameters
function CubicReset() {
  cwndMax = 0; epochStart = 0; originPoint = 0
  rttMin = 0; K = 0; ackCnt = 0
}

# Determine increase in cwnd
function CubicUpdate() {
  # Initialize new epoch (after each loss)
  if (epochStart <= 0) {
    epochStart = tcpTimeStamp
    if (cwnd < cwndMax) {
      # Concave, then convex growth
      K = Sqrt(3, (cwndMax - cwnd)/C); originPoint = cwndMax
    } else {
      # Convex growth 
      K = 0; originPoint = cwnd
    }
  }
  
  t = tcpTimeStamp + rttMin - epochStart # when to reach target
  target = C(t - K)^3 + originPoint      # what target to reach
  
  if (target > cwnd) {
    cnt = cwnd / (target-cwnd)
  } else {
    cnt = 100 * cwnd # do not increase cwnd
  }
  
  # Fall back to TCP Reno, if it would increase cwnd faster
  CubicTCPFriendliness() 
}

Im Vergleich zu TCP Reno ist obiger Code um einiges komplexer. Der Hauptgrund dafür ist, dass die Skalierung von cwnd zwar, wie erwähnt, von RTT entkoppelt werden soll, der Algorithmus aber weiterhin nur bei Erhalt eines ACKs aufgerufen wird. Da dieses Ereignis von der RTT abhängt, muss die Unabhängigkeit von der RTT über eine geschickte Entkopplung per Code sichergestellt werden.

Falls TCP Reno zu einer schnelleren Skalierung von cwnd als TCP CUBIC führen würde, fällt TCP CUBIC auf TCP Reno zurück. Dies kann während der langsamen anfänglichen Skalierung von TCP CUBIC in der konvexen Region vorkommen. Dadurch wird sichergestellt, dass TCP CUBIC keinen Nachteil gegenüber Legacy-Systemen hat.

Nach so viel Theorie wird es Zeit für experimentelle Daten:

Die kubische Skalierung von cwnd ist im Bereich ⑤ gut erkennbar. Nach dem Erhalt duplizierter ACKs werden und gesetzt (Bereich ③). Durch PRR fällt cwnd selbst innerhalb von einer RTT auf ssthresh (Bereich ④). Anschliessend beginnt die Skalierung durch die kubische Funktion, zunächst schnell, dann immer langsamer, je näher an den früheren Wert herankommt (konkaver Teil). Darüber hinaus würde die konvexe Zunahme von cwnd beginnen. Die Übertragung war hier aber bereits vorher abgeschlossen.

HyStart

Es bleiben zwei Punkte zu erklären: das Verhalten des Senders beim Übergang von Bereich ① zu Bereich ② und den linearen Anstieg von cwnd in Bereich ②. Ersteres wird nicht durch ein Verlustevent (duplizierte ACKs) ausgelöst, da cwnd sonst in der Folge durch PRR reduziert werden würde. Stattdessen scheint der Sender den Slow Start plötzlich abzubrechen, ssthresh auf den aktuellen Wert von cwnd zu setzen, und in Congestion Avoidance überzugehen.

Dahinter steckt der HyStart-Algorithmus, der im Linux-Kernel zusammen mit TCP CUBIC verwendet wird. Der Zweck von Slow Start ist es, den ungefähren Wert ssthresh abzuschätzen, ab dem Segmentverluste eintreten. Normalerweise geschieht dies, indem cwnd so lange erhöht wird, bis tatsächlich Segmente verloren gehen. Dabei werden die Buffer der Router entlang des Weges aufgefüllt und das Netzwerk wird belastet.

HyStart macht das geschickter: Es versucht, die Auslastung des Netzwerks über die Zeitdifferenz zwischen empfangenen ACKs und der Zunahme der RTT zu bestimmen. Wenn Router mit der Übermittlung der Pakete nicht mehr nachkommen und sich ihre Buffer langsam füllen, nimmt einerseits die RTT zu, da die Pakete im Buffer warten müssen. Andererseits treffen die Segmente nicht mehr gleichmässig über eine RTT verteilt beim Empfänger ein, da der «Zug» der Pakete im Buffer gestaucht wird. Entsprechend treffen auch die ACKs zeitlich nicht mehr gleichmässig verteilt, sondern in schneller Abfolge kurz nacheinander beim Sender ein. In diesem Fall stoppt HyStart den Slow Start frühzeitig, setzt ssthresh auf den aktuellen Wert von cwnd und lässt den Sender zur Congestion Avoidance übergehen.

TCP CUBIC wird dann mit cwndMax=0 gestartet, da noch kein Segmentverlust aufgetreten ist. Wir fallen somit in den else-Block des obigen Pseudocodes, in dem TCP CUBIC direkt beginnt, mit konvexem Wachstum die Verfügbarkeit weiterer Bandbreite zu erproben:

  # Initialize new epoch (after each loss)
  if (epochStart <= 0) {
    epochStart = tcpTimeStamp
    if (cwnd < cwndMax) {
      ...
    } else {
      # Convex growth 
      K = 0; originPoint = cwnd
    }
  }
  
  t = tcpTimeStamp + rttMin - epochStart # when to reach target
  target = C(t - K)^3 + originPoint      # what target to reach
  
  ...
  
  # Fall back to TCP Reno, if it would increase cwnd faster
  CubicTCPFriendliness() 

  # Initialize new epoch (after each loss)
  if (epochStart <= 0) {
    epochStart = tcpTimeStamp
    if (cwnd < cwndMax) {
      ...
    } else {
      # Convex growth 
      K = 0; originPoint = cwnd
    }
  }
  
  t = tcpTimeStamp + rttMin - epochStart # when to reach target
  target = C(t - K)^3 + originPoint      # what target to reach
  
  ...
  
  # Fall back to TCP Reno, if it would increase cwnd faster
  CubicTCPFriendliness() 

Da dieses Wachstum zunächst langsamer ist als das lineare Wachstum von TCP Reno, wird die CubicTCPFriendliness() Funktion aufgerufen und cwnd wird linear skaliert. Das ist der Grund für den linearen Anstieg im Bereich ②.

Fazit

Bevor wir zum Fazit kommen, lohnt es sich kurz sauber zu machen. Ein verlustfreies Loopback-Interface ist meist von Vorteil…

sudo tc qdisc del dev lo root
sudo ip link set dev lo mtu 65536
sudo ethtool -K lo tso on gso on gro on
sudo sysctl -w net.ipv4.tcp_congestion_control=cubic

sudo tc qdisc del dev lo root
sudo ip link set dev lo mtu 65536
sudo ethtool -K lo tso on gso on gro on
sudo sysctl -w net.ipv4.tcp_congestion_control=cubic

Mich fasziniert an TCP, wie elegant und im Grunde einfach die Algorithmen sind, die im Hintergrund die Fäden des Internets zusammenhalten. Insbesondere TCP Reno in seiner klassichen Form mit multiplikativer Abnahme (Halbierung) und linearer Zunahme ist sehr minimalistisch. Das scheint mir der springende Punkt zu sein: Bei einem Konstrukt wie dem Internet, an dem Millionen von Endgeräten teilnehmen, lohnt es sich, die Algorithmen so einfach wie möglich zu halten. So sind sie für alle zugänglich, werden von allen gleich umgesetzt, und bieten allen den gleichen Service.

Gleichzeitig sind mit der Weiterentwicklung des Internets auch Verbesserungen der Algorithmen nötig, um einen guten Service zu gewährleisten. In diese Richtung habe ich mit PRR, SACK, CUBIC und HyStart mehrere Algorithmen vorgestellt. Obwohl sie komplexer als das «klassische» TCP Reno sind, weisen auch sie eine gewisse Eleganz auf. Ein Beispiel ist TCP CUBIC, das alle gewünschten Eigenschaften der Skalierung von cwnd in einer Kubikfunktion abbildet.

Es gibt weitere faszinierende Themen im Zusammenhang mit TCP, etwa die Aspekte der Fairness: Es besteht ein Zusammenhang zwischen der Fairness von TCP und Konzepten der Spieltheorie, siehe Rate control for communication networks: shadow prices, proportional fairness and stability. Eventuell werde ich in einem zukünftigen Blogbeitrag darauf eingehen. Bis dahin wünsche ich viel Spass mit zuverlässigem und performantem Internet. Ich freue mich immer über Kommentare oder Ideen für weitere Blogbeiträge!

FIN.

Quellen

Papers:

• N. Dukkipati, M. Mathis, Y. Cheng, M. Ghobadi (Google): Proportional Rate Reduction for TCP.
• S. Ha, I. Rhee (North Carolina State University), L. Xu (University of Nebraska): CUBIC: A New TCP-Friendly High-Speed TCP Variant.

Beitragsbild: Photo by Taylor Vick on Unsplash

Katzen-GIFs:

• Katze mit Sonnenbrille
• Katze auf Putzroboter