Connected: An Internet Encyclopedia
4.2.1 Basic PAWS Algorithm
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 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:
- 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:
Send an acknowledgement in reply as specified in
RFC-793 page 69 and drop the segment.
Note: it is necessary to send an ACK segment in order
to retain TCP's mechanisms for detecting and
recovering from half-open connections. For example,
see Figure 10 of RFC-793.
- If the segment is outside the window, reject it (normal
TCP processing)
- If an arriving segment satisfies: SEG.SEQ <= Last.ACK.sent
(see Section 3.4), then record its timestamp in TS.Recent.
- If an arriving segment is in-sequence (i.e., at the left
window edge), then accept it normally.
- 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.
Suppose the segment sequence: A.1, B.1, C.1, ..., Z.1 has
been sent, where the letter indicates the sequence number
and the digit represents the timestamp. Suppose also that
segment B.1 has been lost. The timestamp in TS.TStamp is
1 (from A.1), so C.1, ..., Z.1 are considered acceptable
and are queued. When B is retransmitted as segment B.2
(using the latest timestamp), it fills the hole and causes
all the segments through Z to be acknowledged and passed
to the user. The timestamps of the queued segments are
*not* inspected again at this time, since they have
already been accepted. When B.2 is accepted, TS.Stamp is
set to 2.
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:
Suppose again that segments: A.1, B.1, C.1, ..., Z.1 have
been sent in sequence and that segment B.1 has been lost.
Furthermore, suppose delivery of some of C.1, ... Z.1 is
delayed until AFTER the retransmission B.2 arrives at the
receiver. These delayed segments will be discarded
unnecessarily when they do arrive, since their timestamps
are now out of date.
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