Connected: An Internet Encyclopedia
4.2.1 Basic PAWS Algorithm

Up: Connected: An Internet Encyclopedia
Up: Requests For Comments
Up: RFC 1323
Up: 4.2 The PAWS Mechanism
Prev: 4.2 The PAWS Mechanism
Next: 4.2.2 Timestamp Clock

4.2.1 Basic PAWS Algorithm

4.2.1 Basic PAWS Algorithm

The PAWS algorithm requires the following processing to be performed on all incoming segments for a synchronized connection:

  1. If there is a Timestamps option in the arriving segment and SEG.TSval < TS.Recent and if TS.Recent is valid (see later discussion), then treat the arriving segment as not acceptable:

  2. If the segment is outside the window, reject it (normal TCP processing)

  3. If an arriving segment satisfies: SEG.SEQ <= Last.ACK.sent (see Section 3.4), then record its timestamp in TS.Recent.

  4. If an arriving segment is in-sequence (i.e., at the left window edge), then accept it normally.

  5. Otherwise, treat the segment as a normal in-window, out- of-sequence TCP segment (e.g., queue it for later delivery to the user).

Steps 2, 4, and 5 are the normal TCP processing steps specified by RFC-793.

It is important to note that the timestamp is checked only when a segment first arrives at the receiver, regardless of whether it is in-sequence or it must be queued for later delivery. Consider the following example.

This rule allows reasonable performance under loss. A full window of data is in transit at all times, and after a loss a full window less one packet will show up out-of-sequence to be queued at the receiver (e.g., up to ~2**30 bytes of data); the timestamp option must not result in discarding this data.

In certain unlikely circumstances, the algorithm of rules 1-4 could lead to discarding some segments unnecessarily, as shown in the following example:

This case is very unlikely to occur. If the retransmission was triggered by a timeout, some of the segments C.1, ... Z.1 must have been delayed longer than the RTO time. This is presumably an unlikely event, or there would be many spurious timeouts and retransmissions. If B's retransmission was triggered by the "fast retransmit" algorithm, i.e., by duplicate ACKs, then the queued segments that caused these ACKs must have been received already.

Even if a segment were delayed past the RTO, the Fast Retransmit mechanism [Jacobson90c] will cause the delayed packets to be retransmitted at the same time as B.2, avoiding an extra RTT and therefore causing a very small performance penalty.

We know of no case with a significant probability of occurrence in which timestamps will cause performance degradation by unnecessarily discarding segments.

Next: 4.2.2 Timestamp Clock

Connected: An Internet Encyclopedia
4.2.1 Basic PAWS Algorithm