Im Oktober 1986 erlitt das frühe Internet seinen ersten Überlastungszusammenbruch: Der Durchsatz vom Lawrence Berkeley Lab zur UC Berkeley, 400 Yards entfernt, fiel von 32 Kbps auf 40 bps. Die Hosts wiederholten verlorene Pakete mit voller Geschwindigkeit und überfluteten das Netz dadurch weiter.

Van Jacobsons Aufsatz „Congestion Avoidance and Control“ von 1988 erklärte den Mechanismus und schrieb die Lösung vor: Sender sollten ihr Fenster pro Roundtrip um ein Paket erhöhen, wenn kein Verlust auftritt, und es bei einem Paketverlust halbieren – eine Politik der additiven Erhöhung und multiplikativen Verringerung.

Da jeder TCP-Sender demselben Algorithmus folgt, erreicht das Netz ohne zentrale Steuerung ein stabiles, annähernd faires Gleichgewicht. Die Idee wurde in TCP übernommen und später zusammen mit Slow Start, Fast Retransmit und Fast Recovery in RFC 5681 kodifiziert.

Verlust erkennen, Geschwindigkeit halbieren; dann langsam wieder hochkriechen

Verlust ist ein Überlastungssignal, das jeder Sender ohnehin empfängt, sodass keine zusätzliche Netzmechanik nötig ist.

Die multiplikative Verringerung reagiert schnell auf Probleme; die additive Erhöhung tastet die Kapazität langsam ab.

Dass alle Sender dieselbe Regel befolgen, bedeutet, dass Fairness aus individuellem Verhalten entsteht.

Es behob den Ausfall, ohne Router zu ändern oder Bandbreite hinzuzufügen.

Wenn die rationale Reaktion jedes Akteurs eine gemeinsame Ressource verschlechtert, ändere die Regel, der alle folgen: Lass die sichere Handlung langsam hochskalieren und die schädliche Handlung scharf herunterskalieren.

Der Algorithmus wurde zum Standardverhalten von TCP, dem Transportprotokoll, das den Großteil des Internetverkehrs trägt. RFC 5681, veröffentlicht 2009, führt Slow Start, Congestion Avoidance, Fast Retransmit und Fast Recovery weiterhin als Standard auf, und die Forschung zur Überlastungskontrolle entwickelte sich aus diesem Aufsatz zu einem eigenen Feld.

DEN BELEGEN FOLGEN

Die Quellen

  1. Congestion Avoidance and Control (Van Jacobson & Michael Karels, November 1988) Lawrence Berkeley National Laboratory · ee.lbl.gov
  2. RFC 5681 — TCP Congestion Control Internet Engineering Task Force · rfc-editor.org