Zum Hauptinhalt springen

Anhang A. Starke Paketerhaltungsgrenze (Strong Packet Conservation Bound)

Die starke Paketerhaltungsgrenze (Strong Packet Conservation Bound) ist eine formale Eigenschaft, die für PRR-CRB etabliert werden kann. Sie besagt, dass unter allen Bedingungen und Ereignissequenzen während der Wiederherstellung PRR-CRB die übertragenen Daten strikt auf einen Wert begrenzt, der gleich oder kleiner als die Menge der an den Empfänger gelieferten Daten ist.

A.1. Formale Definition (Formal Definition)​

Sei:

  • D(t) = kumulative Daten, die zum Zeitpunkt t an den Empfänger geliefert wurden
  • S(t) = kumulative Daten, die zum Zeitpunkt t während der Wiederherstellung vom Sender gesendet wurden
  • R = der anfängliche Wert von inflight zu Beginn der Wiederherstellung (RecoverFS)

Dann garantiert PRR-CRB:

S(t) - S(0) ≤ D(t) - D(0)

für alle t während der Wiederherstellungsphase, wobei S(0) und D(0) die Werte zu Beginn der Wiederherstellung sind.

A.2. Intuition​

Die starke Paketerhaltungsgrenze stellt während der Wiederherstellung sicher:

  1. Keine Burst-Übertragung über gelieferte Daten hinaus: Der Sender sendet niemals mehr neue Daten ins Netzwerk, als als an den Empfänger geliefert bestätigt wurde.

  2. Konstante Warteschlangenlängeneigenschaft: Wenn an einem Engpass eine stehende Warteschlange ohne Querverkehr existiert, wird die Warteschlange für die Dauer der Wiederherstellung eine exakt konstante Länge beibehalten, mit Ausnahme von ±1-Segment-Schwankungen aufgrund von Unterschieden in Paketankunfts- und -abgangszeiten.

  3. Selbsttakterhaltung: Die Grenze bewahrt Van Jacobsons Paketerhaltungsprinzip in seiner stärksten Form - jedes gelieferte Paket löst höchstens das Senden eines Pakets aus.

A.3. Mathematischer Beweisskizze (Mathematical Proof Sketch)​

PRR-CRB erhält die Invariante:

prr_out ≤ prr_delivered

Wenn inflight ≤ ssthresh, berechnet PRR-CRB:

SndCnt = MAX(prr_delivered - prr_out, DeliveredData)

Dies stellt sicher:

  1. Der Basisfall prr_delivered - prr_out erhält die Erhaltungsgrenze
  2. Der Term DeliveredData gewährleistet Fortschritt
  3. Die finale MIN(ssthresh - inflight, SndCnt) Klemmung verhindert das Überschreiten des Zielfensters

A.4. Auswirkungen auf das Netzwerkverhalten (Implications for Network Behavior)​

Warteschlangenstabilität (Queue Stability)​

Unter der starken Paketerhaltungsgrenze:

  • Stabile Engpass-Warteschlangen: Wenn ein Fluss eine stehende Warteschlange an einem Engpass hat, wird PRR-CRB nicht veranlassen, dass diese Warteschlange während der Wiederherstellung wächst
  • Keine Stauungsverstärkung: Die Wiederherstellung verschlimmert bestehende Stauung nicht
  • Vorhersagbares Verhalten: Netzwerkbetreiber können über die Warteschlangenbelegung im schlimmsten Fall nachdenken

Kompromisse (Trade-offs)​

Obwohl die starke Paketerhaltungsgrenze starke Garantien bietet:

Vorteile:

  • Eliminiert retransmissionsinduzierte Stauungszusammenbrüche
  • Bietet vorhersagbares, konservatives Verhalten
  • Garantiert Fortschritt bei gleichzeitiger Aufrechterhaltung der Warteschlangenstabilität

Nachteile:

  • Kann in einigen Szenarien zu konservativ sein (siehe Abschnitt 7 und Abschnitt 8 Beispiele)
  • Kann zu längeren Wiederherstellungszeiten führen, wenn tatsächliche Verluste die Zielfensterreduktion überschreiten
  • Kann verfügbare Bandbreite während der Wiederherstellung möglicherweise nicht vollständig nutzen

A.5. Beziehung zu PRR-SSRB (Relationship to PRR-SSRB)​

PRR-SSRB lockert die starke Paketerhaltungsgrenze geringfügig, indem es ein zusätzliches Segment pro ACK erlaubt (wenn SafeACK wahr ist):

SndCnt = MAX(prr_delivered - prr_out, DeliveredData) + SMSS

Dies bedeutet, dass PRR-SSRB die strenge Grenze vorübergehend um höchstens verletzen kann:

(Anzahl der ACKs) × SMSS

Diese Verletzung ist jedoch begrenzt und kontrolliert:

  • Tritt nur auf, wenn inflight < ssthresh
  • Nur wenn SafeACK guten Wiederherstellungsfortschritt anzeigt
  • Führt typischerweise zu schnellerer Wiederherstellung mit minimalem Risiko

A.6. Historischer Kontext (Historical Context)​

Die starke Paketerhaltungsgrenze formalisiert und verstärkt Van Jacobsons ursprüngliches Paketerhaltungsprinzip [Jacobson88]. Während das ursprüngliche Prinzip erlaubte, dass Pakete "vermutlich verloren" als das Netzwerk verlassen habend betrachtet werden, zählt die starke Grenze nur Pakete, die tatsächlich an den Empfänger geliefert wurden.

Diese strengere Interpretation stellt sicher:

  1. Schätzfehler in der Pipe-Berechnung verursachen keine Bursts
  2. Der Algorithmus bleibt auch bei Neuordnung konservativ
  3. Das Wiederherstellungsverhalten ist selbstkorrigierend basierend auf tatsächlichem Empfänger-Feedback

A.7. Praktische Überlegungen (Practical Considerations)​

Implementierungshinweise (Implementation Notes)​

Implementierer sollten beachten, dass:

  • Die Grenze für den konzeptionellen Algorithmus gilt; Implementierungsoptimierungen müssen die Eigenschaft bewahren
  • Byte-Zählung (statt Segment-Zählung) bietet bessere Granularität und Verteidigung gegen ACK-Splitting-Angriffe
  • Die Grenze gilt unabhängig von der Genauigkeit anderer Schätzer (pipe, cwnd usw.)

Leistungsauswirkungen (Performance Implications)​

In der Praxis:

  • PRR-CRBs strenge Grenze kann für schwere Verlustszenarien zu konservativ sein
  • Die adaptive SafeACK-Heuristik (Umschaltung auf PRR-SSRB) bietet bessere reale Leistung
  • Der Wert der Grenze liegt in der Bereitstellung einer Sicherheitsgarantie, nicht in optimaler Leistung in allen Fällen

A.8. Formale Invarianten (Formal Invariants)​

PRR-CRB erhält die folgenden Invarianten während der gesamten Wiederherstellung:

Invariante 1 (Erhaltung):

prr_out ≤ prr_delivered

Invariante 2 (Zielkonvergenz):

lim (prr_out) = ssthresh
t→end

(bei minimalen Verlusten und ohne Anwendungsstillstände)

Invariante 3 (Monotonie):

prr_delivered(t₁) ≤ prr_delivered(t₂) für alle t₁ < t₂
prr_out(t₁) ≤ prr_out(t₂) für alle t₁ < t₂

Diese Invarianten gewährleisten:

  • Fortschritt (Monotonie)
  • Erhaltung (Invariante 1)
  • Korrekter Endzustand (Invariante 2)

A.9. Schlussfolgerung (Conclusion)​

Die starke Paketerhaltungsgrenze bietet eine rigorose Grundlage für PRR-CRB und stellt sicher, dass die TCP-Wiederherstellung bestehende Stauung niemals verstärkt. Während PRR-SSRB und die SafeACK-Heuristik diese Grenze für bessere Leistung lockern, bleibt die starke Grenze eine wichtige theoretische Basislinie, die sicheren Betrieb auch in Worst-Case-Szenarien garantiert.

Letztes Update am