4. PAWS -- Schutz gegen Überlauf von Sequenznummern
4.1 Einführung
Abschnitt 4.2 beschreibt einen einfachen Mechanismus zum Ablehnen alter doppelter Segmente, die eine offene TCP-Verbindung beschädigen könnten; wir nennen diesen Mechanismus PAWS (Protect Against Wrapped Sequence numbers, Schutz gegen Überlauf von Sequenznummern). PAWS arbeitet innerhalb einer einzelnen TCP-Verbindung und verwendet Zustände, die im Verbindungssteuerblock gespeichert sind. Abschnitt 4.3 und Anhang C diskutieren die Auswirkungen des PAWS-Mechanismus zur Vermeidung alter Duplikate aus früheren Inkarnationen derselben Verbindung.
4.2 Der PAWS-Mechanismus
PAWS verwendet dieselbe TCP Timestamps-Option wie der zuvor beschriebene RTTM-Mechanismus und geht davon aus, dass jedes empfangene TCP-Segment (einschließlich Daten- und ACK-Segmente) einen Zeitstempel SEG.TSval enthält, dessen Werte in der Zeit monoton nicht abnehmend sind. Die Grundidee ist, dass ein Segment als altes Duplikat verworfen werden kann, wenn es mit einem Zeitstempel SEG.TSval empfangen wird, der kleiner ist als ein kürzlich auf dieser Verbindung empfangener Zeitstempel.
Sowohl im PAWS- als auch im RTTM-Mechanismus sind die "Zeitstempel (timestamps)" 32-Bit-Ganzzahlen ohne Vorzeichen in einem modularen 32-Bit-Raum. Daher wird "kleiner als (less than)" auf dieselbe Weise definiert wie für TCP-Sequenznummern, und dieselben Implementierungstechniken gelten. Wenn s und t Zeitstempelwerte sind, gilt s < t, wenn 0 < (t - s) < 2**31, berechnet in 32-Bit-Arithmetik ohne Vorzeichen.
Die Wahl der eingehenden Zeitstempel, die für diesen Vergleich gespeichert werden sollen, muss einen Wert garantieren, der monoton steigend ist. Zum Beispiel könnten wir den Zeitstempel aus dem Segment speichern, das zuletzt die linke Kante des Empfangsfensters vorwärts bewegt hat, d.h. das aktuellste Segment in der Reihenfolge. Stattdessen wählen wir den in Abschnitt 3.4 für den RTTM-Mechanismus eingeführten Wert TS.Recent, da die Verwendung eines gemeinsamen Werts sowohl für PAWS als auch für RTTM die Implementierung von beiden vereinfacht. Wie Abschnitt 3.4 erklärte, unterscheidet sich TS.Recent vom Zeitstempel des letzten Segments in der Reihenfolge nur im Fall verzögerter ACKs und daher um weniger als ein Fenster. Beide Optionen schützen daher vor Sequenznummernüberlauf.
RTTM wurde auf symmetrische Weise spezifiziert, sodass TSval-Zeitstempel sowohl in Daten- als auch in ACK-Segmenten getragen und in TSecr-Feldern zurückgesendet werden, die in zurückkehrenden ACK- oder Datensegmenten getragen werden. PAWS unterwirft alle eingehenden Segmente demselben Test und schützt daher sowohl gegen doppelte ACK-Segmente als auch gegen Datensegmente. (Ein alternativer asymmetrischer Algorithmus würde gegen alte doppelte ACKs schützen: Der Absender von Daten würde eingehende ACK-Segmente ablehnen, deren TSecr-Werte kleiner waren als der TSecr, der aus dem letzten Segment gespeichert wurde, dessen ACK-Feld die linke Kante des Sendefensters vorwärts bewegt hat. Dieser Algorithmus wurde als mangelhaft an Mechanismusökonomie und Symmetrie angesehen.)
TSval-Zeitstempel, die auf {SYN}- und {SYN,ACK}-Segmenten gesendet werden, werden zur Initialisierung von PAWS verwendet. PAWS schützt gegen alte doppelte Nicht-SYN-Segmente und doppelte SYN-Segmente, die empfangen werden, während eine synchronisierte Verbindung besteht. Doppelte {SYN}- und {SYN,ACK}-Segmente, die empfangen werden, wenn keine Verbindung besteht, werden durch den normalen 3-Wege-Handshake und Sequenznummernprüfungen von TCP verworfen.
Es wird empfohlen, dass RST-Segmente KEINE Zeitstempel tragen und dass RST-Segmente unabhängig von ihrem Zeitstempel akzeptabel sind. Alte doppelte RST-Segmente sollten äußerst unwahrscheinlich sein, und ihre Bereinigungsfunktion sollte Vorrang vor Zeitstempeln haben.
4.2.1 Grundlegender PAWS-Algorithmus
Der PAWS-Algorithmus erfordert, dass die folgende Verarbeitung für alle eingehenden Segmente einer synchronisierten Verbindung durchgeführt wird:
Wenn es eine Timestamps-Option im ankommenden Segment gibt und SEG.TSval < TS.Recent und wenn TS.Recent gültig ist (siehe spätere Diskussion), dann behandeln Sie das ankommende Segment als nicht akzeptabel:
Senden Sie eine Bestätigung als Antwort, wie in RFC-793 Seite 69 angegeben, und verwerfen Sie das Segment.
Hinweis: Es ist notwendig, ein ACK-Segment zu senden, um die Mechanismen von TCP zur Erkennung und Wiederherstellung von halb offenen Verbindungen beizubehalten. Siehe beispielsweise Abbildung 10 von RFC-793.
Wenn das Segment außerhalb des Fensters liegt, lehnen Sie es ab (normale TCP-Verarbeitung)
Wenn ein ankommendes Segment erfüllt: SEG.SEQ <= Last.ACK.sent (siehe Abschnitt 3.4), dann zeichnen Sie seinen Zeitstempel in TS.Recent auf.
Wenn ein ankommendes Segment in der Reihenfolge ist (d.h. an der linken Fensterkante), dann akzeptieren Sie es normal.
Andernfalls behandeln Sie das Segment als normales Segment im Fenster, außerhalb der Reihenfolge TCP-Segment (z.B. stellen Sie es für spätere Zustellung an den Benutzer in die Warteschlange).
Die Schritte R2, R4 und R5 sind die normalen TCP-Verarbeitungsschritte, die von RFC-793 spezifiziert werden.
Es ist wichtig zu beachten, dass der Zeitstempel nur überprüft wird, wenn ein Segment zum ersten Mal beim Empfänger ankommt, unabhängig davon, ob es in der Reihenfolge ist oder für spätere Zustellung in die Warteschlange gestellt werden muss. Betrachten Sie das folgende Beispiel.
Angenommen, die Segmentsequenz: A.1, B.1, C.1, ..., Z.1 wurde gesendet, wobei der Buchstabe die Sequenznummer angibt und die Ziffer den Zeitstempel darstellt. Angenommen auch, dass Segment B.1 verloren gegangen ist. Der Zeitstempel in TS.TStamp ist 1 (von A.1), daher werden C.1, ..., Z.1 als akzeptabel betrachtet und in die Warteschlange gestellt. Wenn B als Segment B.2 (mit dem neuesten Zeitstempel) erneut übertragen wird, füllt es die Lücke und bewirkt, dass alle Segmente bis Z bestätigt und an den Benutzer weitergegeben werden. Die Zeitstempel der in der Warteschlange befindlichen Segmente werden zu diesem Zeitpunkt nicht erneut überprüft, da sie bereits akzeptiert wurden. Wenn B.2 akzeptiert wird, wird TS.Stamp auf 2 gesetzt.
Diese Regel ermöglicht eine angemessene Leistung bei Verlust. Ein vollständiges Datenfenster ist jederzeit unterwegs, und nach einem Verlust wird ein vollständiges Fenster minus ein Paket außerhalb der Reihenfolge erscheinen, um beim Empfänger in die Warteschlange gestellt zu werden (z.B. bis zu ~2**30 Bytes Daten); die Zeitstempeloption darf nicht dazu führen, dass diese Daten verworfen werden.
Unter bestimmten unwahrscheinlichen Umständen könnte der Algorithmus der Regeln R1-R4 dazu führen, dass einige Segmente unnötigerweise verworfen werden, wie das folgende Beispiel zeigt:
Angenommen wiederum, dass Segmente: A.1, B.1, C.1, ..., Z.1 in der Reihenfolge gesendet wurden und dass Segment B.1 verloren gegangen ist. Angenommen ferner, dass die Zustellung einiger der C.1, ... Z.1 verzögert wird, bis NACH der Neuübertragung B.2 beim Empfänger ankommt. Diese verzögerten Segmente werden unnötigerweise verworfen, wenn sie ankommen, da ihre Zeitstempel jetzt veraltet sind.
Dieser Fall tritt sehr unwahrscheinlich auf. Wenn die Neuübertragung durch ein Timeout ausgelöst wurde, müssen einige der Segmente C.1, ... Z.1 länger als die RTO-Zeit verzögert worden sein. Dies ist vermutlich ein unwahrscheinliches Ereignis, sonst würde es viele falsche Timeouts und Neuübertragungen geben. Wenn die Neuübertragung von B durch den "Schnelle Neuübertragung (fast retransmit)"-Algorithmus ausgelöst wurde, d.h. durch doppelte ACKs, dann müssen die in der Warteschlange befindlichen Segmente, die diese ACKs verursacht haben, bereits empfangen worden sein.
Selbst wenn ein Segment über das RTO hinaus verzögert wurde, wird der Schnelle Neuübertragungsmechanismus [Jacobson90c] dazu führen, dass die verzögerten Pakete zur gleichen Zeit wie B.2 neu übertragen werden, wodurch ein zusätzliches RTT vermieden wird und daher eine sehr geringe Leistungseinbuße verursacht wird.
Wir kennen keinen Fall mit einer signifikanten Auftretenswahrscheinlichkeit, in dem Zeitstempel durch unnötiges Verwerfen von Segmenten zu Leistungseinbußen führen werden.
4.2.2 Zeitstempeluhr
Es ist wichtig zu verstehen, dass der PAWS-Algorithmus keine Uhrsynchronisation zwischen Sender und Empfänger erfordert. Die Zeitstempeluhr des Senders wird verwendet, um die Segmente zu stempeln, und der Sender verwendet den zurückgesendeten Zeitstempel, um RTTs zu messen. Der Empfänger behandelt den Zeitstempel jedoch einfach als eine monoton steigende Seriennummer, ohne notwendige Verbindung zu seiner Uhr. Aus Sicht des Empfängers wirkt der Zeitstempel als logische Erweiterung der höherwertigen Bits der Sequenznummer.
Der Empfängeralgorithmus stellt einige Anforderungen an die Frequenz der Zeitstempeluhr.
Die Zeitstempeluhr darf nicht "zu langsam" sein.
Sie muss mindestens einmal für jede 231 gesendeten Bytes ticken. Tatsächlich sollte die Uhr, um für den Sender für die Rundlaufzeitmessung nützlich zu sein, mindestens einmal pro Fenster an Daten ticken, und selbst mit der RFC-1072-Fenstererweiterung müssen 231 Bytes mindestens zwei Fenster sein.
Um dies quantitativer zu machen, wird jede Uhr, die schneller als 1 Tick/Sek ist, alte doppelte Segmente für Verbindungsgeschwindigkeiten von ~8 Gbps ablehnen. Eine 1ms-Zeitstempeluhr funktioniert bei Verbindungsgeschwindigkeiten bis zu 8 Tbps (8*10**12) bps!
Die Zeitstempeluhr darf nicht "zu schnell" sein.
Ihre Recyclingzeit muss größer als MSL Sekunden sein. Da die Uhr (Zeitstempel) 32 Bit beträgt und die MSL im schlimmsten Fall 255 Sekunden beträgt, ist die maximal akzeptable Uhrfrequenz ein Tick alle 59 ns.
Es ist jedoch wünschenswert, eine viel längere Recyclingperiode festzulegen, um veraltete Zeitstempel bei inaktiven Verbindungen zu handhaben (siehe Abschnitt 4.2.3) und die MSL-Anforderung zur Verhinderung von Sequenznummernüberlauf zu lockern. Mit einer 1-ms-Zeitstempeluhr wird der 32-Bit-Zeitstempel sein Vorzeichenbit in 24,8 Tagen überlaufen. Daher wird er alte Duplikate auf derselben Verbindung ablehnen, wenn MSL 24,8 Tage oder weniger beträgt. Dies scheint eine sehr sichere Zahl zu sein; eine MSL von 24,8 Tagen oder länger kann wahrscheinlich vom Gateway-System angenommen werden, ohne eine präzise MSL-Durchsetzung durch den TTL-Wert in der IP-Schicht zu erfordern.
Basierend auf diesen Überlegungen wählen wir eine Zeitstempeluhrfrequenz im Bereich von 1 ms bis 1 Sek pro Tick. Dieser Bereich entspricht auch den Anforderungen des RTTM-Mechanismus, der nicht viel mehr Auflösung als die Granularität des Neuübertragungstimers benötigt, z.B. Dutzende oder Hunderte von Millisekunden.
Der PAWS-Mechanismus stellt auch eine starke Monotonieanforderung an die Zeitstempeluhr des Senders. Die Implementierungsmethode der Zeitstempeluhr zur Erfüllung dieser Anforderung hängt von der Systemhardware und -software ab.
-
Einige Hosts haben eine Hardwareuhr, die garantiert zwischen Hardware-Resets monoton ist.
-
Ein Uhrinterrupt kann verwendet werden, um einfach eine binäre Ganzzahl periodisch um 1 zu erhöhen.
-
Die Zeitstempeluhr kann von einer Systemuhr abgeleitet werden, die abrupt geändert werden kann, indem ein variabler Offset-Wert hinzugefügt wird. Dieser Offset wird auf Null initialisiert. Wenn ein neuer Zeitstempeluhrwert benötigt wird, kann der Offset bei Bedarf angepasst werden, um den neuen Wert gleich oder größer als den vorherigen Wert zu machen (der für diesen Zweck gespeichert wurde).
4.2.3 Veraltete Zeitstempel
Wenn eine Verbindung lange genug inaktiv bleibt, damit die Zeitstempeluhr des anderen TCP sein Vorzeichenbit überläuft, wird der in TS.Recent gespeicherte Wert zu alt; infolgedessen wird der PAWS-Mechanismus dazu führen, dass alle nachfolgenden Segmente abgelehnt werden, wodurch die Verbindung eingefroren wird (bis die Zeitstempeluhr ihr Vorzeichenbit erneut überläuft).
Mit dem gewählten Bereich von Zeitstempeluhrfrequenzen (1 Sek bis 1 ms) liegt die Zeit zum Überlaufen des Vorzeichenbits zwischen 24,8 Tagen und 24800 Tagen. Eine TCP-Verbindung, die länger als 24 Tage inaktiv ist und dann zum Leben erwacht, ist äußerst ungewöhnlich. Es ist jedoch prinzipiell unerwünscht, irgendeine Einschränkung der Lebensdauer von TCP-Verbindungen vorzunehmen.
Wir fordern daher, dass eine Implementierung von PAWS einen Mechanismus enthält, um den TS.Recent-Wert zu "invalidieren (invalidate)", wenn eine Verbindung länger als 24 Tage inaktiv ist. (Eine alternative Lösung für das Problem veralteter Zeitstempel wäre das Senden von Keepalive-Segmenten mit einer sehr niedrigen Rate, aber immer noch häufiger als die Überlaufzeit für Zeitstempel, z.B. einmal pro Tag. Dies würde einen vernachlässigbaren Overhead auferlegen. Die TCP-Spezifikation hat jedoch nie Keepalives enthalten, daher wurde die Lösung basierend auf Invalidierung gewählt.)
Beachten Sie, dass ein TCP die Frequenz und daher die Überlaufzeit des anderen TCP nicht kennt, daher muss es vom Schlimmsten ausgehen. Die Gültigkeit von TS.Recent muss nur überprüft werden, wenn die grundlegende PAWS-Zeitstempelprüfung fehlschlägt, d.h. nur wenn SEG.TSval < TS.Recent. Wenn TS.Recent als ungültig befunden wird, wird das Segment akzeptiert, unabhängig vom Fehler der Zeitstempelprüfung, und Regel R3 aktualisiert TS.Recent mit dem TSval aus dem neuen Segment.
Um zu erkennen, wie lange die Verbindung inaktiv war, kann das TCP beispielsweise jedes Mal, wenn TS.Recent aktualisiert wird, eine Uhr oder einen Zeitstempelwert aktualisieren, der mit der Verbindung verbunden ist. Die Details sind implementierungsabhängig.
4.2.4 Header-Vorhersage
"Header-Vorhersage (Header prediction)" [Jacobson90a] ist eine Hochleistungs-Transportprotokoll-Implementierungstechnik, die für Hochgeschwindigkeitsverbindungen am wichtigsten ist. Diese Technik optimiert den Code für den häufigsten Fall, ein Segment korrekt und in der Reihenfolge zu empfangen. Mit Header-Vorhersage stellt der Empfänger die Frage: "Ist dieses Segment das nächste in der Reihenfolge?" Diese Frage kann in weniger Maschinenanweisungen beantwortet werden als die Frage "Ist dieses Segment im Fenster?"
Das Hinzufügen der Header-Vorhersage zu unserem Zeitstempelverfahren führt zu der folgenden empfohlenen Sequenz für die Verarbeitung eines ankommenden TCP-Segments:
Zeitstempel prüfen (wie Schritt R1 oben)
Header-Vorhersage durchführen: Wenn das Segment das nächste in der Reihenfolge ist und wenn es keine besonderen Bedingungen gibt, die zusätzliche Verarbeitung erfordern, akzeptieren Sie das Segment, zeichnen Sie seinen Zeitstempel auf und überspringen Sie H3.
Das Segment normal verarbeiten, wie in RFC-793 angegeben. Dies umfasst das Verwerfen von Segmenten, die außerhalb des Fensters liegen, und möglicherweise das Senden von Bestätigungen sowie das Einreihen von Segmenten im Fenster, die außerhalb der Reihenfolge liegen.
Eine andere Möglichkeit wäre, die Schritte H1 und H2 zu vertauschen, d.h. den Header-Vorhersage-Schritt H2 ZUERST durchzuführen und H1 und H3 nur durchzuführen, wenn die Header-Vorhersage fehlschlägt. Dies könnte eine Leistungsverbesserung sein, da die Zeitstempelprüfung in Schritt H1 sehr unwahrscheinlich fehlschlägt und sie Intervall-Arithmetik auf einem endlichen Feld erfordert, eine relativ teure Operation. Diese Prüfung bei jedem einzelnen Segment durchzuführen, widerspricht der Philosophie der Header-Vorhersage. Wir glauben, dass diese Änderung die CPU-Zeit für die TCP-Protokollverarbeitung in Hochgeschwindigkeitsnetzwerken um bis zu 5-10% reduzieren könnte.
Das Voranstellen von H2 würde jedoch eine Gefahr schaffen: Ein Segment von 2**32 Bytes in der Vergangenheit könnte genau zur falschen Zeit ankommen und fälschlicherweise durch den Header-Vorhersage-Schritt akzeptiert werden. Die folgende Argumentation wurde eingeführt [Jacobson90b], um zu zeigen, dass die Wahrscheinlichkeit dieses Fehlers vernachlässigbar ist.
Wenn alle Segmente gleich wahrscheinlich als alte Duplikate auftauchen, dann ist die Wahrscheinlichkeit, dass ein altes Duplikat genau mit der linken Fensterkante übereinstimmt, die maximale Segmentgröße (MSS) geteilt durch die Größe des Sequenzraums. Dieses Verhältnis muss kleiner als 2**-16 sein, da MSS < 216 sein muss; zum Beispiel wird es (212)/(232) = 2-20 für eine FDDI-Verbindung sein. Je älter jedoch ein Segment ist, desto weniger wahrscheinlich ist es, dass es im Internet beibehalten wird, und unter jedem vernünftigen Modell der Segmentlebensdauer muss die Wahrscheinlichkeit eines alten Duplikats genau an der linken Fensterkante viel kleiner als 2**-16 sein.
Die 16-Bit-TCP-Prüfsumme ermöglicht auch eine grundlegende Unzuverlässigkeit von einem Teil in 2**16. Ein Protokollmechanismus, dessen Zuverlässigkeit die Zuverlässigkeit der TCP-Prüfsumme übertrifft, sollte als "gut genug" betrachtet werden, d.h. er wird nicht wesentlich zur Gesamtfehlerrate beitragen. Wir glauben daher, dass wir das Problem eines alten Duplikats, das akzeptiert wird, ignorieren können, indem wir Header-Vorhersage vor der Überprüfung des Zeitstempels durchführen.
Dieses probabilistische Argument wird jedoch nicht allgemein akzeptiert, und der gegenwärtige Konsens ist, dass der Leistungsgewinn die Gefahr im Allgemeinen nicht rechtfertigt. Es wird daher empfohlen, dass H2 auf H1 folgt.
4.3 Duplikate aus früheren Inkarnationen der Verbindung
Der PAWS-Mechanismus schützt vor Fehlern aufgrund von Sequenznummernüberlauf bei Hochgeschwindigkeitsverbindungen. Segmente aus einer früheren Inkarnation derselben Verbindung sind ebenfalls eine potenzielle Ursache für alte Duplikatfehler. In beiden Fällen hängen die TCP-Mechanismen zur Verhinderung solcher Fehler von der Durchsetzung einer maximalen Segmentlebensdauer (MSL) durch die Internet-(IP-)Schicht ab (siehe Anhang von RFC-1185 für eine ausführliche Diskussion). Im Gegensatz zum Fall des Sequenzraum-Überlaufs hängt die MSL, die erforderlich ist, um alte Duplikatfehler aus früheren Inkarnationen zu verhindern, nicht von der Übertragungsrate ab. Wenn die IP-Schicht die empfohlene 2-Minuten-MSL von TCP durchsetzt und wenn die TCP-Regeln befolgt werden, sind TCP-Verbindungen vor früheren Inkarnationen sicher, unabhängig davon, wie hoch die Netzwerkgeschwindigkeit ist. Daher ist der PAWS-Mechanismus für diesen Fall nicht erforderlich.
Wir können immer noch fragen, ob der PAWS-Mechanismus zusätzliche Sicherheit gegen alte Duplikate aus früheren Verbindungen bieten kann, was es uns ermöglicht, die Durchsetzung der MSL durch die IP-Schicht zu lockern. Anhang B untersucht diese Frage und zeigt, dass weitere Annahmen und/oder Mechanismen über die von PAWS hinaus erforderlich sind. Dies ist nicht Teil der aktuellen Erweiterung.