Connected: An Internet Encyclopedia
4.2.4 Header Prediction

Up: Connected: An Internet Encyclopedia
Up: Requests For Comments
Up: RFC 1323
Up: 4. PAWS: PROTECT AGAINST WRAPPED SEQUENCE NUMBERS
Up: 4.2 The PAWS Mechanism
Prev: 4.2.3 Outdated Timestamps
Next: 4.3. Duplicates from Earlier Incarnations of Connection

4.2.4 Header Prediction

4.2.4 Header Prediction

"Header prediction" [Jacobson90a] is a high-performance transport protocol implementation technique that is most important for high-speed links. This technique optimizes the code for the most common case, receiving a segment correctly and in order. Using header prediction, the receiver asks the question, "Is this segment the next in sequence?" This question can be answered in fewer machine instructions than the question, "Is this segment within the window?"

Adding header prediction to our timestamp procedure leads to the following recommended sequence for processing an arriving TCP segment:

  1. Check timestamp (same as step 1 above)

  2. Do header prediction: if segment is next in sequence and if there are no special conditions requiring additional processing, accept the segment, record its timestamp, and skip next step.

  3. Process the segment normally, as specified in RFC-793. This includes dropping segments that are outside the win- dow and possibly sending acknowledgments, and queueing in-window, out-of-sequence segments.

Another possibility would be to interchange steps 1 and 2, i.e., to perform the header prediction step 2 FIRST, and perform 1 and 3 only when header prediction fails. This could be a performance improvement, since the timestamp check in step 1 is very unlikely to fail, and it requires interval arithmetic on a finite field, a relatively expensive operation. To perform this check on every single segment is contrary to the philosophy of header prediction. We believe that this change might reduce CPU time for TCP protocol processing by up to 5-10% on high-speed networks.

However, putting 2 first would create a hazard: a segment from 2**32 bytes in the past might arrive at exactly the wrong time and be accepted mistakenly by the header-prediction step. The following reasoning has been introduced [Jacobson90b] to show that the probability of this failure is negligible.

However, this probabilistic argument is not universally accepted, and the consensus at present is that the performance gain does not justify the hazard in the general case. It is therefore recommended that 2 follow 1.


Next: 4.3. Duplicates from Earlier Incarnations of Connection

Connected: An Internet Encyclopedia
4.2.4 Header Prediction