[ Main | Local ]

Die TCP Implementation der University of Berkeley

Es ist bekannte Unix-Geschichte, das Ken Thompson einige Zeit an der University of California in Berkeley Vorlesungen zum Thema "Design und Implementation eines Betriebssystems" gehalten hat. Das ist unter anderem der Grund für die Unix-Version aus Berkely, die als Berkeley Software Distribution (BSD) bekannt geworden ist. Aufgrund der offenen Lizenz sind Teile von BSD in fast allen Betriebssystemen zu finden.

Besonders der TCP/IP Stack ist der Ausgangspunkt der meisten heute aktuellen Stacks gewesen. Der erste, breit eingesetzte Stack fand sich in 4.2BSD (1982). Eine verbesserte Version, aber immer noch mit unverändertem Protokoll, wurde im 4.3BSD (1986) implementiert. Aufgrund verschiedener Probleme mit der TCP/IP Suite wurde der Stack im 4.3BSD 1988 erweitert. Das Ergebniss ist als Tahoe bekannt und führte folgende Erweiterungen ein: Fast Retransmit, Slowstart und Congestion Avoidance. Wenig später, 1990, wurden unter dem Namen Reno diese Verbesserungen zusammengefaßt: Fast Recovery, TCP Header Prediction, SLIP Header Compression sowie Änderungen bei der Handhabung der Routing Table. Mit New Reno werden Erweiterungen der Performance-Algorithmen von Reno verbunden. Mit Vegas werden Techniken zur Flußanalyse und somit zur Senderseitigen Flußsteuerung eingeführt. Allerdings ist Vegas noch nicht in den breiten Gebrauch gelangt. Die aktuelle Version von BSD ist 4.4BSD (1993), was für TCP Multicasting und die verbesserte Unterstützung schneller und breitbandiger Verbindungstechniken brachte.

Tahoe TCP

• Neue Algorithmen:
  Slowstart, Congestion Avoidance, Fast Retransmit
  Verbesserungen:
  Round Trip Time Estimator, Retransmission Timeouts.
  Die Veränderungen sind gut beschrieben - hier die Quellen:
  Richard W. Stevens, TCP/IP Illustrated, Volume 1: The Protocols. Addison Wesley, 1994.
  V. Jacobson, Congestion Avoidance and Control, SIGCOMM Symposium on Communications Architectures and Protocols, p. 314, 1988. ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z
  

• Slow Start:
  

• Congestion Avoidance:
  

• Fast Retransmit:
  Nachdem TCP einige (meist 3) doppelte ACKs für ein und dasselbe Segment empfangen hat, geht der Sender davon aus, das die seitdem gesendeten Daten verloren sind und sendet neu. Schließlich ist jedes ACK die Reaktion auf den Empfang eines Paketes, was für den Empfänger aus der Reihe fällt, weil ihm Teile fehlen - deshalb bestätigt er den Empfang des letzten, von ihm wirklich anerkannten Segment. Unter AIX ist das ein "normales" ACK und 3 "dup ACKs". Dann wird eine Retransmission durchgeführt, unabhängig davon, ob der Retransmission Timer schon zugeschlagen hat. Der Sender geht dann in Slow Start.

Reno TCP

• Verbesserungen:
  Der Fast Retransmit Algorithmus wurde um Fast Recovery erweitert. ( V. Jacobson, Modified TCP Congestion Avoidance Algorithm, Technical Report 30. April 1990. ftp://ftp.ee.lbl.gov/email/vanj.90apr30.txt).

• Fast Recovery:
  Verhindert, das bei einem Retransmit die Leitung (Pipe) der Verbindung leerläuft und man neu durch Slow Start geht. Konkret geht das so: Nach einem bestimmten Schwellenwert von dup ACKs (meist 3) wird das Paket neu gesendet und das Congestion Window auf die Hälfte gesetzt. Statt aber jetzt Slow Start auszuführen (wie Tahoe), nutzt der Reno Sender die weiter hereinkommenden dup ACKs als Zeichen, das jeweils ein Segment die Pipe verlassen hat und schickt seinerseits ein neues Segment. Sobald das ACK für das retransmittete Paket empfangen wird, geht der Reno Sender wieder in normalen Mode über. Das ist optimiert für einzelne Paketverluste, da nur ein Paket pro Round Trip Time neu gesendet werden kann.

New Reno TCP

• Kommt bald..:
  

Vegas TCP

• Kommt bald..:
  Vegas nutzt nicht den Verlust von Paketen zur Steuerung des Paket-Flusses, sondern die Verzögerung, die Pakete erfahren.

Woher kommen die Namen?

Die Namen sind von den Betriebsystem-Namen der BSD Releases abgeleitet.

So war mit der Version 4.3BSD eigentlich klar, das die VAX Plattform nicht mehr zukunftssicher war. Daher wurde begonnen, auf eine neue Power PC Plattform zu schwenken, die vom Hersteller mit dem Code-Namen Tahoe geführt wurde (aus dem Projekt wurde dann nichts, aber die der BSD-Code wurde getrennt in Hardwarespezifischen und allgemeinen Code).

Dann wurde vom 4.3BSD eine Interims-Version auf dem Weg nach 4.4BSD abgezweigt - diese Version wurde als sehr experimentel angesehen und war nur etwas für Spieler. Daher der Name Reno, als Symbol für das hohe Risiko, aber auch die große Chance.

Zu Vegas kann ich nichts sagen, jedenfalls gibt es kein BSD Release mit diesem Namen, und der TCP Stack ist auch nicht mehr so eng an das Betriebssystem gebunden. Ich gehe davon aus, daß die Entwickler an der Universität Arizona an die Tradition anknüpfen möchten.

[ Main | Local ]

[ Allgemein | UNIX | AIX | TCP-IP | TCP | ROUTING | DNS | NTP | NFS | FreeBSD | Linux | RPi | SMTP | Tracing | GPS | LW ]