Skip to main content

Appendix A. Strong Packet Conservation Bound

The Strong Packet Conservation Bound is a formal property that can be established for PRR-CRB. It states that under all conditions and sequences of events during recovery, PRR-CRB strictly bounds the data transmitted to be equal to or less than the amount of data delivered to the receiver.

A.1. Formal Definition​

Let:

  • D(t) = cumulative data delivered to the receiver at time t
  • S(t) = cumulative data sent by the sender at time t during recovery
  • R = the initial value of inflight at the start of recovery (RecoverFS)

Then PRR-CRB guarantees:

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

for all t during the recovery phase, where S(0) and D(0) are the values at the beginning of recovery.

A.2. Intuition​

The Strong Packet Conservation Bound ensures that during recovery:

  1. No burst transmission beyond delivered data: The sender never sends more new data into the network than has been confirmed as delivered to the receiver.

  2. Constant queue length property: If there is a standing queue at a bottleneck with no cross traffic, the queue will maintain an exactly constant length for the duration of recovery, except for ±1 segment fluctuations due to differences in packet arrival and departure times.

  3. Self-clocking preservation: The bound preserves Van Jacobson's packet conservation principle in its strongest form - each packet delivered triggers at most one packet sent.

A.3. Mathematical Proof Sketch​

PRR-CRB maintains the invariant:

prr_out ≤ prr_delivered

When inflight ≤ ssthresh, PRR-CRB computes:

SndCnt = MAX(prr_delivered - prr_out, DeliveredData)

This ensures:

  1. The base case prr_delivered - prr_out maintains the conservation bound
  2. The DeliveredData term ensures forward progress
  3. The final MIN(ssthresh - inflight, SndCnt) clamp prevents exceeding the target window

A.4. Implications for Network Behavior​

Queue Stability​

Under the Strong Packet Conservation Bound:

  • Stable bottleneck queues: If a flow has a standing queue at a bottleneck, PRR-CRB will not cause that queue to grow during recovery
  • No congestion amplification: Recovery does not make existing congestion worse
  • Predictable behavior: Network operators can reason about worst-case queue occupancy

Trade-offs​

While the Strong Packet Conservation Bound provides strong guarantees:

Advantages:

  • Eliminates retransmission-induced congestion collapse
  • Provides predictable, conservative behavior
  • Guarantees forward progress while maintaining queue stability

Disadvantages:

  • May be too conservative in some scenarios (see Section 7 and Section 8 examples)
  • Can lead to longer recovery times when actual losses exceed the target window reduction
  • May not fully utilize available bandwidth during recovery

A.5. Relationship to PRR-SSRB​

PRR-SSRB relaxes the Strong Packet Conservation Bound slightly by allowing one additional segment per ACK (when SafeACK is true):

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

This means PRR-SSRB can temporarily violate the strict bound by at most:

(number of ACKs) × SMSS

However, this violation is bounded and controlled:

  • Only occurs when inflight < ssthresh
  • Only when SafeACK indicates good recovery progress
  • Typically results in faster recovery with minimal risk

A.6. Historical Context​

The Strong Packet Conservation Bound formalizes and strengthens Van Jacobson's original packet conservation principle [Jacobson88]. While the original principle allowed packets "presumed lost" to be considered as having left the network, the Strong Bound only counts packets actually delivered to the receiver.

This stricter interpretation ensures that:

  1. Estimation errors in the pipe calculation do not cause bursts
  2. The algorithm remains conservative even under reordering
  3. Recovery behavior is self-correcting based on actual receiver feedback

A.7. Practical Considerations​

Implementation Notes​

Implementers should note that:

  • The bound applies to the conceptual algorithm; implementation optimizations must preserve the property
  • Byte counting (rather than segment counting) provides better granularity and defense against ACK splitting attacks
  • The bound holds regardless of the accuracy of other estimators (pipe, cwnd, etc.)

Performance Implications​

In practice:

  • PRR-CRB's strict bound may be too conservative for heavy loss scenarios
  • The adaptive SafeACK heuristic (switching to PRR-SSRB) provides better real-world performance
  • The bound's value lies in providing a safety guarantee, not optimal performance in all cases

A.8. Formal Invariants​

PRR-CRB maintains the following invariants throughout recovery:

Invariant 1 (Conservation):

prr_out ≤ prr_delivered

Invariant 2 (Target Convergence):

lim (prr_out) = ssthresh
t→end

(assuming minimal losses and no application stalls)

Invariant 3 (Monotonicity):

prr_delivered(t₁) ≤ prr_delivered(t₂) for all t₁ < t₂
prr_out(t₁) ≤ prr_out(t₂) for all t₁ < t₂

These invariants ensure:

  • Forward progress (monotonicity)
  • Conservation (Invariant 1)
  • Correct final state (Invariant 2)

A.9. Conclusion​

The Strong Packet Conservation Bound provides a rigorous foundation for PRR-CRB, ensuring that TCP recovery never amplifies existing congestion. While PRR-SSRB and the SafeACK heuristic relax this bound for better performance, the Strong Bound remains an important theoretical baseline that guarantees safe operation even in worst-case scenarios.

Last updated on