draft-ietf-tcpm-1323bis-01.txt   draft-ietf-tcpm-1323bis-02.txt 
Network Working Group Network Working Group TCP Maintenance (TCPM) D. Borman
Internet-Draft D. Borman Internet-Draft Quantum Corporation
Obsoletes: 1323 Wind River Systems Intended status: Standards Track B. Braden
Intended Status: Standards Track R. Braden Expires: November 19, 2012 University of Southern
File: draft-ietf-tcpm-1323bis-01.txt ISI California
V. Jacobson V. Jacobson
Packet Design Packet Design
March 4, 2009 R. Scheffenegger, Ed.
NetApp, Inc.
May 18, 2012
TCP Extensions for High Performance TCP Extensions for High Performance
draft-ietf-tcpm-1323bis-02
Status of This Memo Abstract
This Internet-Draft is submitted to IETF in full conformance with the This memo presents a set of TCP extensions to improve performance
provisions of BCP 78 and BCP 79. over large bandwidth*delay product paths and to provide reliable
operation over very high-speed paths. It defines TCP options for
scaled windows and timestamps, which are designed to provide
compatible interworking with TCP's that do not implement the
extensions. The timestamps are used for two distinct mechanisms:
RTTM (Round Trip Time Measurement) and PAWS (Protection Against
Wrapped Sequences). Selective acknowledgments are not included in
this memo.
This document may contain material from IETF Documents or IETF This memo updates and obsoletes RFC 1323.
Contributions published or made publicly available before November
10, 2008. The person(s) controlling the copyright in some of this Status of this Memo
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process. This Internet-Draft is submitted in full conformance with the
Without obtaining an adequate license from the person(s) controlling provisions of BCP 78 and BCP 79.
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF). Note that other groups may also distribute
other groups may also distribute working documents as Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at This Internet-Draft will expire on November 19, 2012.
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on September 4, 2009.
Copyright
Copyright (c) 2009 IETF Trust and the persons identified as the Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of Provisions Relating to IETF Documents
publication of this document (http://trustee.ietf.org/license-info). (http://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
Abstract include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
This memo presents a set of TCP extensions to improve performance described in the Simplified BSD License.
over large bandwidth*delay product paths and to provide reliable
operation over very high-speed paths. It defines TCP options for
scaled windows and timestamps, which are designed to provide
compatible interworking with TCP's that do not implement the
extensions. The timestamps are used for two distinct mechanisms:
RTTM (Round Trip Time Measurement) and PAWS (Protection Against
Wrapped Sequences). Selective acknowledgments are not included in
this memo.
This memo updates and obsoletes RFC 1323.
TABLE OF CONTENTS Table of Contents
1. Introduction 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. TCP Window Scale Option 9 1.1. TCP Performance . . . . . . . . . . . . . . . . . . . . . 4
3. RTTM -- Round-Trip Time Measurement 12 1.2. TCP Reliability . . . . . . . . . . . . . . . . . . . . . 6
4. PAWS -- Protection Against Wrapped Sequence Numbers 18 1.3. Using TCP options . . . . . . . . . . . . . . . . . . . . 9
5. Conclusions and Acknowledgments 26 2. TCP Window Scale Option . . . . . . . . . . . . . . . . . . . 10
6. Security Considerations 27 2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 10
7. IANA Considerations 27 2.2. Window Scale Option . . . . . . . . . . . . . . . . . . . 10
8. References 27 2.3. Using the Window Scale Option . . . . . . . . . . . . . . 11
APPENDIX A: Implementation Suggestions 30 2.4. Addressing Window Retraction . . . . . . . . . . . . . . . 13
APPENDIX B: Duplicates from Earlier Connection Incarnations 31 3. RTTM -- Round-Trip Time Measurement . . . . . . . . . . . . . 13
APPENDIX C: Changes from RFC 1072, RFC 1185, RFC 1323 34 3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 13
APPENDIX D: Summary of Notation 36 3.2. TCP Timestamps Option . . . . . . . . . . . . . . . . . . 14
APPENDIX E: Pseudo-code Summary 37 3.3. The RTTM Mechanism . . . . . . . . . . . . . . . . . . . . 15
APPENDIX F: Event Processing 40 3.4. Which Timestamp to Echo . . . . . . . . . . . . . . . . . 17
APPENDIX G: Timestamps Edge Cases 46 4. PAWS -- Protection Against Wrapped Sequence Numbers . . . . . 19
Authors' Addresses 47 4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 19
4.2. The PAWS Mechanism . . . . . . . . . . . . . . . . . . . . 20
4.2.1. Basic PAWS Algorithm . . . . . . . . . . . . . . . . . 21
4.2.2. Timestamp Clock . . . . . . . . . . . . . . . . . . . 23
4.2.3. Outdated Timestamps . . . . . . . . . . . . . . . . . 24
4.2.4. Header Prediction . . . . . . . . . . . . . . . . . . 25
4.2.5. IP Fragmentation . . . . . . . . . . . . . . . . . . . 26
4.3. Duplicates from Earlier Incarnations of Connection . . . . 27
5. Conclusions and Acknowledgements . . . . . . . . . . . . . . . 27
6. Security Considerations . . . . . . . . . . . . . . . . . . . 28
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.1. Normative References . . . . . . . . . . . . . . . . . . . 28
8.2. Informative References . . . . . . . . . . . . . . . . . . 29
Appendix A. Implementation Suggestions . . . . . . . . . . . . . 31
Appendix B. Duplicates from Earlier Connection Incarnations . . . 32
B.1. System Crash with Loss of State . . . . . . . . . . . . . 32
B.2. Closing and Reopening a Connection . . . . . . . . . . . . 32
Appendix C. Changes from RFC 1072, RFC 1185, and RFC 1323 . . . . 34
Appendix D. Summary of Notation . . . . . . . . . . . . . . . . . 36
Appendix E. Pseudo-code Summary . . . . . . . . . . . . . . . . . 37
Appendix F. Event Processing Summary . . . . . . . . . . . . . . 39
Appendix G. Timestamps Edge Cases . . . . . . . . . . . . . . . . 44
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 45
1. INTRODUCTION 1. Introduction
The TCP protocol [Postel81] was designed to operate reliably over The TCP protocol [RFC0793] was designed to operate reliably over
almost any transmission medium regardless of transmission rate, almost any transmission medium regardless of transmission rate,
delay, corruption, duplication, or reordering of segments. delay, corruption, duplication, or reordering of segments.
Production TCP implementations currently adapt to transfer rates in Production TCP implementations currently adapt to transfer rates in
the range of 100 bps to 10**10 bps and round-trip delays in the range the range of 100 bps to 10^10 bps and round-trip delays in the range
1 ms to 100 seconds. Work on TCP performance has shown that TCP 1 ms to 100 seconds. Work on TCP performance has shown that TCP
without the extensions described in this memo can work well over a without the extensions described in this memo can work well over a
variety of Internet paths, ranging from 800 Mbit/sec I/O channels to variety of Internet paths, ranging from 800 Mbit/sec I/O channels to
300 bit/sec dial-up modems [Jacobson88a]. 300 bit/sec dial-up modems .
Over the years, advances in networking technology has resulted in Over the years, advances in networking technology has resulted in
ever-higher transmission speeds, and the fastest paths are well ever-higher transmission speeds, and the fastest paths are well
beyond the domain for which TCP was originally engineered. This memo beyond the domain for which TCP was originally engineered. This memo
defines a set of modest extensions to TCP to extend the domain of its defines a set of modest extensions to TCP to extend the domain of its
application to match this increasing network capability. It is an application to match this increasing network capability. It is an
update to and obsoletes RFC 1323 [Jacobson92d], which in turn is update to and obsoletes [RFC1323], which in turn is based upon and
based upon and obsoletes RFC 1072 [Jacobson88b] and RFC 1185 obsoletes [RFC1072] and [RFC1185].
[Jacobson90b].
There is no one-line answer to the question: "How fast can TCP go?". There is no one-line answer to the question: "How fast can TCP go?".
There are two separate kinds of issues, performance and reliability, There are two separate kinds of issues, performance and reliability,
and each depends upon different parameters. We discuss each in turn. and each depends upon different parameters. We discuss each in turn.
1.1 TCP Performance 1.1. TCP Performance
TCP performance depends not upon the transfer rate itself, but TCP performance depends not upon the transfer rate itself, but rather
rather upon the product of the transfer rate and the round-trip upon the product of the transfer rate and the round-trip delay. This
delay. This "bandwidth*delay product" measures the amount of data "bandwidth*delay product" measures the amount of data that would
that would "fill the pipe"; it is the buffer space required at "fill the pipe"; it is the buffer space required at sender and
sender and receiver to obtain maximum throughput on the TCP receiver to obtain maximum throughput on the TCP connection over the
connection over the path, i.e., the amount of unacknowledged data path, i.e., the amount of unacknowledged data that TCP must handle in
that TCP must handle in order to keep the pipeline full. TCP order to keep the pipeline full. TCP performance problems arise when
performance problems arise when the bandwidth*delay product is the bandwidth*delay product is large. We refer to an Internet path
large. We refer to an Internet path operating in this region as a operating in this region as a "long, fat pipe", and a network
"long, fat pipe", and a network containing this path as an "LFN" containing this path as an "LFN" (pronounced "elephan(t)").
(pronounced "elephan(t)").
High-capacity packet satellite channels are LFN's. For example, a High-capacity packet satellite channels are LFN's. For example, a
DS1-speed satellite channel has a bandwidth*delay product of 10**6 DS1-speed satellite channel has a bandwidth*delay product of 10^6
bits or more; this corresponds to 100 outstanding TCP segments of bits or more; this corresponds to 100 outstanding TCP segments of
1200 bytes each. Terrestrial fiber-optical paths will also fall 1200 bytes each. Terrestrial fiber-optical paths will also fall into
into the LFN class; for example, a cross-country delay of 30 ms at the LFN class; for example, a cross-country delay of 30 ms at a DS3
a DS3 bandwidth (45Mbps) also exceeds 10**6 bits. bandwidth (45Mbps) also exceeds 10^6 bits.
There are three fundamental performance problems with the current There are three fundamental performance problems with the current TCP
TCP over LFN paths: over LFN paths:
(1) Window Size Limit (1) Window Size Limit
The TCP header uses a 16 bit field to report the receive The TCP header uses a 16 bit field to report the receive window
window size to the sender. Therefore, the largest window size to the sender. Therefore, the largest window that can be
that can be used is 2**16 = 65K bytes. used is 2^16 = 65K bytes.
To circumvent this problem, Section 2 of this memo defines a To circumvent this problem, Section 2 of this memo defines a new
new TCP option, "Window Scale", to allow windows larger than TCP option, "Window Scale", to allow windows larger than 2^16.
2**16. This option defines an implicit scale factor, which This option defines an implicit scale factor, which is used to
is used to multiply the window size value found in a TCP multiply the window size value found in a TCP header to obtain
header to obtain the true window size. the true window size.
(2) Recovery from Losses (2) Recovery from Losses
Packet losses in an LFN can have a catastrophic effect on Packet losses in an LFN can have a catastrophic effect on
throughput. In the past, properly-operating TCP throughput. In the past, properly-operating TCP implementations
implementations would cause the data pipeline to drain with would cause the data pipeline to drain with every packet loss,
every packet loss, and require a slow-start action to and require a slow-start action to recover. The Fast Retransmit
recover. The Fast Retransmit and Fast Recovery algorithms and Fast Recovery algorithms [Jacobson90c], [RFC2581] and
[Jacobson90c] [Allman99] were introduced, and their combined [RFC5681] were introduced, and their combined effect was to
effect was to recover from one packet loss per window, recover from one packet loss per window, without draining the
without draining the pipeline. However, more than one packet pipeline. However, more than one packet loss per window
loss per window typically resulted in a retransmission typically resulted in a retransmission timeout and the resulting
timeout and the resulting pipeline drain and slow start. pipeline drain and slow start.
Expanding the window size to match the capacity of an LFN Expanding the window size to match the capacity of an LFN
results in a corresponding increase of the probability of results in a corresponding increase of the probability of more
more than one packet per window being dropped. This could than one packet per window being dropped. This could have a
have a devastating effect upon the throughput of TCP over an devastating effect upon the throughput of TCP over an LFN. In
LFN. In addition, since the publication of RFC 1323, addition, since the publication of RFC 1323, congestion control
congestion control mechanism based upon some form of random mechanism based upon some form of random dropping have been
dropping have been introduced into gateways, and randomly introduced into gateways, and randomly spaced packet drops have
spaced packet drops have become common; this increases the become common; this increases the probability of dropping more
probability of dropping more than one packet per window. than one packet per window.
To generalize the Fast Retransmit/Fast Recovery mechanism to To generalize the Fast Retransmit/Fast Recovery mechanism to
handle multiple packets dropped per window, selective handle multiple packets dropped per window, selective
acknowledgments are required. Unlike the normal cumulative acknowledgments are required. Unlike the normal cumulative
acknowledgments of TCP, selective acknowledgments give the acknowledgments of TCP, selective acknowledgments give the
sender a complete picture of which segments are queued at the sender a complete picture of which segments are queued at the
receiver and which have not yet arrived. receiver and which have not yet arrived.
Since the publication of RFC 1323, selective acknowledgments Since the publication of [RFC1323], selective acknowledgments
have become important in the LFN regime. RFC 1072 defined a (SACK) have become important in the LFN regime. SACK has been
new TCP "SACK" option to send a selective acknowledgment, but published as a [RFC2018], "TCP Selective Acknowledgment
at the time that RFC 1323 was published, important technical Options".. Additional information about SACK can be found in
issues still had to be worked out concerning both the format [RFC2883], "An Extension to the Selective Acknowledgement (SACK)
and semantics of the SACK option, so it was split off from option for TCP" and [RFC3517], "A Conservative Selective
RFC 1323. SACK has now been published as a separate Acknowledgment (SACK)-based Loss Recovery Algorithm for TCP".
document, RFC 2018 [Mathis96]. Additional information about
SACK can be found in RFC 2883, "An Extension to the Selective
Acknowledgement (SACK) option for TCP" [Floyd00] and RFC
3517, "A Conservative Selective Acknowledgment (SACK)-based
Loss Recovery Algorithm for TCP" [Blanton03].
(3) Round-Trip Measurement (3) Round-Trip Measurement
TCP implements reliable data delivery by retransmitting TCP implements reliable data delivery by retransmitting segments
segments that are not acknowledged within some retransmission that are not acknowledged within some retransmission timeout
timeout (RTO) interval. Accurate dynamic determination of an (RTO) interval. Accurate dynamic determination of an
appropriate RTO is essential to TCP performance. RTO is appropriate RTO is essential to TCP performance. RTO is
determined by estimating the mean and variance of the determined by estimating the mean and variance of the measured
measured round-trip time (RTT), i.e., the time interval round-trip time (RTT), i.e., the time interval between sending a
between sending a segment and receiving an acknowledgment for segment and receiving an acknowledgment for it [Jacobson88a].
it [Jacobson88a].
Section 4 introduces a new TCP option, "Timestamps", and then Section 3.2 introduces a new TCP option, "Timestamps", and then
defines a mechanism using this option that allows nearly defines a mechanism using this option that allows nearly every
every segment, including retransmissions, to be timed at segment, including retransmissions, to be timed at negligible
negligible computational cost. We use the mnemonic RTTM computational cost. We use the mnemonic RTTM (Round Trip Time
(Round Trip Time Measurement) for this mechanism, to Measurement) for this mechanism, to distinguish it from other
distinguish it from other uses of the Timestamps option. uses of the Timestamps option.
1.2 TCP Reliability 1.2. TCP Reliability
Now we turn from performance to reliability. High transfer rate Now we turn from performance to reliability. High transfer rate
enters TCP performance through the bandwidth*delay product. enters TCP performance through the bandwidth*delay product. However,
However, high transfer rate alone can threaten TCP reliability by high transfer rate alone can threaten TCP reliability by violating
violating the assumptions behind the TCP mechanism for duplicate the assumptions behind the TCP mechanism for duplicate detection and
detection and sequencing. sequencing.
An especially serious kind of error may result from an accidental An especially serious kind of error may result from an accidental
reuse of TCP sequence numbers in data segments. Suppose that an reuse of TCP sequence numbers in data segments. Suppose that an "old
"old duplicate segment", e.g., a duplicate data segment that was duplicate segment", e.g., a duplicate data segment that was delayed
delayed in Internet queues, is delivered to the receiver at the in Internet queues, is delivered to the receiver at the wrong moment,
wrong moment, so that its sequence numbers falls somewhere within so that its sequence numbers falls somewhere within the current
the current window. There would be no checksum failure to warn of window. There would be no checksum failure to warn of the error, and
the error, and the result could be an undetected corruption of the the result could be an undetected corruption of the data. Reception
data. Reception of an old duplicate ACK segment at the of an old duplicate ACK segment at the transmitter could be only
transmitter could be only slightly less serious: it is likely to slightly less serious: it is likely to lock up the connection so that
lock up the connection so that no further progress can be made, no further progress can be made, forcing an RST on the connection.
forcing an RST on the connection.
TCP reliability depends upon the existence of a bound on the TCP reliability depends upon the existence of a bound on the lifetime
lifetime of a segment: the "Maximum Segment Lifetime" or MSL. An of a segment: the "Maximum Segment Lifetime" or MSL. An MSL is
MSL is generally required by any reliable transport protocol, generally required by any reliable transport protocol, since every
since every sequence number field must be finite, and therefore sequence number field must be finite, and therefore any sequence
any sequence number may eventually be reused. In the Internet number may eventually be reused. In the Internet protocol suite, the
protocol suite, the MSL bound is enforced by an IP-layer MSL bound is enforced by an IP-layer mechanism, the "Time-to-Live" or
mechanism, the "Time-to-Live" or TTL field. TTL field.
Duplication of sequence numbers might happen in either of two Duplication of sequence numbers might happen in either of two ways:
ways:
(1) Sequence number wrap-around on the current connection (1) Sequence number wrap-around on the current connection
A TCP sequence number contains 32 bits. At a high enough A TCP sequence number contains 32 bits. At a high enough
transfer rate, the 32-bit sequence space may be "wrapped" transfer rate, the 32-bit sequence space may be "wrapped"
(cycled) within the time that a segment is delayed in queues. (cycled) within the time that a segment is delayed in queues.
(2) Earlier incarnation of the connection (2) Earlier incarnation of the connection
Suppose that a connection terminates, either by a proper Suppose that a connection terminates, either by a proper close
close sequence or due to a host crash, and the same sequence or due to a host crash, and the same connection (i.e.,
connection (i.e., using the same pair of sockets) is using the same pair of sockets) is immediately reopened. A
immediately reopened. A delayed segment from the terminated delayed segment from the terminated connection could fall within
connection could fall within the current window for the new the current window for the new incarnation and be accepted as
incarnation and be accepted as valid. valid.
Duplicates from earlier incarnations, Case (2), are avoided by Duplicates from earlier incarnations, Case (2), are avoided by
enforcing the current fixed MSL of the TCP spec, as explained in enforcing the current fixed MSL of the TCP spec, as explained in
Section 5.3 and Appendix B. However, case (1), avoiding the Section 4.3 and Appendix B. However, case (1), avoiding the reuse of
reuse of sequence numbers within the same connection, requires an sequence numbers within the same connection, requires an MSL bound
MSL bound that depends upon the transfer rate, and at high enough that depends upon the transfer rate, and at high enough rates, a new
rates, a new mechanism is required. mechanism is required.
More specifically, if the maximum effective bandwidth at which TCP More specifically, if the maximum effective bandwidth at which TCP is
is able to transmit over a particular path is B bytes per second, able to transmit over a particular path is B bytes per second, then
then the following constraint must be satisfied for error-free the following constraint must be satisfied for error-free operation:
operation:
2**31 / B > MSL (secs) [1] 2^31 / B > MSL (secs) [1]
The following table shows the value for Twrap = 2**31/B in The following table shows the value for Twrap = 2^31/B in seconds,
seconds, for some important values of the bandwidth B: for some important values of the bandwidth B:
Network B*8 B Twrap +------------------+----------+-------------+--------------------+
bits/sec bytes/sec secs | Network | bits/sec | B bytes/sec | Twrap secs |
_______ _______ ______ ______ +------------------+----------+-------------+--------------------+
| Dialup | 56kbps | 7kBps | 3*10^5 (~3.6 days) |
| DS1 | 1.5Mbps | 190kBps | 10^4 (~3 hours) |
| 10MBit Ethernet | 10Mbps | 1.25MBps | 1700 (~0.5 hours) |
| DS3 | 45Mbps | 5.6MBps | 380 |
| 100MBit Ethernet | 100Mbps | 12.5MBps | 170 |
| Gigabit Ethernet | 1Gbps | 125MBps | 17 |
| 10Gig Ethernet | 10Gbps | 1.25GBps | 1.7 |
+------------------+----------+-------------+--------------------+
Dialup 56kbps 7KBps 3*10**5 (~3.6 days) It is clear that wrap-around of the sequence space is not a problem
for 56kbps packet switching or even 10Mbps Ethernets. On the other
hand, at DS3 and 100mbit speeds, Twrap is comparable to the 2 minute
MSL assumed by the TCP specification [RFC0793]. Moving towards and
beyond gigabit speeds, Twrap becomes too small for reliable
enforcement by the Internet TTL mechanism.
DS1 1.5Mbps 190KBps 10**4 (~3 hours) The 16-bit window field of TCP limits the effective bandwidth B to
2^16/RTT, where RTT is the round-trip time in seconds [RFC1110]. If
the RTT is large enough, this limits B to a value that meets the
constraint [1] for a large MSL value. For example, consider a
transcontinental backbone with an RTT of 60ms (set by the laws of
physics). With the bandwidth*delay product limited to 64KB by the
TCP window size, B is then limited to 1.1MBps, no matter how high the
theoretical transfer rate of the path. This corresponds to cycling
the sequence number space in Twrap = 2000 secs, which is safe in
today's Internet.
10mbit It is important to understand that the culprit is not the larger
Ethernet 10Mbps 1.25MBps 1700 (~30 mins) window but rather the high bandwidth. For example, consider a (very
large) FDDI LAN with a diameter of 10km. Using the speed of light,
we can compute the RTT across the ring as (2*10^4)/(3*10^8) = 67
microseconds, and the delay*bandwidth product is then 833 bytes. A
TCP connection across this LAN using a window of only 833 bytes will
run at the full 100mbps and can wrap the sequence space in about 3
minutes, very close to the MSL of TCP. Thus, high speed alone can
cause a reliability problem with sequence number wrap-around, even
without extended windows.
DS3 45Mbps 5.6MBps 380 Watson's Delta-T protocol [Watson81] includes network-layer
mechanisms for precise enforcement of an MSL. In contrast, the IP
mechanism for MSL enforcement is loosely defined and even more
loosely implemented in the Internet. Therefore, it is unwise to
depend upon active enforcement of MSL for TCP connections, and it is
unrealistic to imagine setting MSL's smaller than the current values
(e.g., 120 seconds specified for TCP).
100mbit A possible fix for the problem of cycling the sequence space would be
Ethernet 100Mbps 12.5MBps 170 to increase the size of the TCP sequence number field. For example,
the sequence number field (and also the acknowledgment field) could
be expanded to 64 bits. This could be done either by changing the
TCP header or by means of an additional option.
Gigabit Section 4 presents a different mechanism, which we call PAWS (Protect
Ethernet 1Gbps 125MBps 17 Against Wrapped Sequence numbers), to extend TCP reliability to
transfer rates well beyond the foreseeable upper limit of network
bandwidths. PAWS uses the TCP Timestamps option defined in
Section 3.2 to protect against old duplicates from the same
connection.
10GigE 10Gbps 1.25GBps 1.7 1.3. Using TCP options
It is clear that wrap-around of the sequence space is not a The extensions defined in this memo all use new TCP options. We must
problem for 56kbps packet switching or even 10Mbps Ethernets. On address two possible issues concerning the use of TCP options: (1)
the other hand, at DS3 and 100mbit speeds, Twrap is comparable to compatibility and (2) overhead.
the 2 minute MSL assumed by the TCP specification [Postel81].
Moving towards and beyond gigabit speeds, Twrap becomes too small
for reliable enforcement by the Internet TTL mechanism.
The 16-bit window field of TCP limits the effective bandwidth B to We must pay careful attention to compatibility, i.e., to
2**16/RTT, where RTT is the round-trip time in seconds interoperation with existing implementations. The only TCP option
[McKenzie89]. If the RTT is large enough, this limits B to a defined previously, MSS, may appear only on a SYN segment. Every
value that meets the constraint [1] for a large MSL value. For implementation should (and we expect that most will) ignore unknown
example, consider a transcontinental backbone with an RTT of 60ms options on SYN segments. When RFC 1323 was published, there was
(set by the laws of physics). With the bandwidth*delay product concern that some buggy TCP implementation might be crashed by the
limited to 64KB by the TCP window size, B is then limited to first appearance of an option on a non-SYN segment. However, bugs
1.1MBps, no matter how high the theoretical transfer rate of the like that can lead to DOS attacks against a TCP, so it is now
path. This corresponds to cycling the sequence number space in expected that most TCP implementations will properly handle unknown
Twrap= 2000 secs, which is safe in today's Internet. options on non-SYN segments. But it is still prudent to be
conservative in what you send, and avoiding buggy TCP implementation
is not the only reason for negotiating TCP options on SYN segments.
Therefore, for each of the extensions defined below, TCP options will
be sent on non-SYN segments only after an exchange of options on the
the SYN segments has indicated that both sides understand the
extension. Furthermore, an extension option will be sent in a
<SYN,ACK> segment only if the corresponding option was received in
the initial <SYN> segment.
It is important to understand that the culprit is not the larger A question may be raised about the bandwidth and processing overhead
window but rather the high bandwidth. For example, consider a for TCP options. Those options that occur on SYN segments are not
(very large) FDDI LAN with a diameter of 10km. Using the speed of likely to cause a performance concern. Opening a TCP connection
light, we can compute the RTT across the ring as requires execution of significant special-case code, and the
(2*10**4)/(3*10**8) = 67 microseconds, and the delay*bandwidth processing of options is unlikely to increase that cost
product is then 833 bytes. A TCP connection across this LAN using significantly.
a window of only 833 bytes will run at the full 100mbps and can
wrap the sequence space in about 3 minutes, very close to the MSL
of TCP. Thus, high speed alone can cause a reliability problem
with sequence number wrap-around, even without extended windows.
Watson's Delta-T protocol [Watson81] includes network-layer On the other hand, a Timestamps option may appear in any data or ACK
mechanisms for precise enforcement of an MSL. In contrast, the IP segment, adding 12 bytes to the 20-byte TCP header. We believe that
mechanism for MSL enforcement is loosely defined and even more the bandwidth saved by reducing unnecessary retransmissions will more
loosely implemented in the Internet. Therefore, it is unwise to than pay for the extra header bandwidth.
depend upon active enforcement of MSL for TCP connections, and it
is unrealistic to imagine setting MSL's smaller than the current
values (e.g., 120 seconds specified for TCP).
A possible fix for the problem of cycling the sequence space would There is also an issue about the processing overhead for parsing the
be to increase the size of the TCP sequence number field. For variable byte-aligned format of options, particularly with a RISC-
example, the sequence number field (and also the acknowledgment architecture CPU. Appendix A contains a recommended layout of the
field) could be expanded to 64 bits. This could be done either by options in TCP headers to achieve reasonable data field alignment.
changing the TCP header or by means of an additional option. In the spirit of Header Prediction, a TCP can quickly test for this
layout and if it is verified then use a fast path. Hosts that use
this canonical layout will effectively use the options as a set of
fixed-format fields appended to the TCP header. However, to retain
the philosophical and protocol framework of TCP options, a TCP must
be prepared to parse an arbitrary options field, albeit with less
efficiency.
Section 5 presents a different mechanism, which we call PAWS Finally, we observe that most of the mechanisms defined in this memo
(Protect Against Wrapped Sequence numbers), to extend TCP are important for LFN's and/or very high-speed networks. For low-
reliability to transfer rates well beyond the foreseeable upper speed networks, it might be a performance optimization to NOT use
limit of network bandwidths. PAWS uses the TCP Timestamps option these mechanisms. A TCP vendor concerned about optimal performance
defined in Section 4 to protect against old duplicates from the over low-speed paths might consider turning these extensions off for
same connection. low-speed paths, or allow a user or installation manager to disable
them.
1.3 Using TCP options 2. TCP Window Scale Option
The extensions defined in this memo all use new TCP options. We 2.1. Introduction
must address two possible issues concerning the use of TCP
options: (1) compatibility and (2) overhead.
We must pay careful attention to compatibility, i.e., to The window scale extension expands the definition of the TCP window
interoperation with existing implementations. The only TCP option to 32 bits and then uses a scale factor to carry this 32-bit value in
defined previously, MSS, may appear only on a SYN segment. Every the 16-bit Window field of the TCP header (SEG.WND in RFC 793). The
implementation should (and we expect that most will) ignore scale factor is carried in a new TCP option, Window Scale. This
unknown options on SYN segments. When RFC 1323 was published, option is sent only in a SYN segment (a segment with the SYN bit on),
there was concern that some buggy TCP implementation might be hence the window scale is fixed in each direction when a connection
crashed by the first appearance of an option on a non-SYN segment. is opened. (Another design choice would be to specify the window
However, bugs like that can lead to DOS attacks against a TCP, so scale in every TCP segment. It would be incorrect to send a window
it is now expected that most TCP implementations will properly scale option only when the scale factor changed, since a TCP option
handle unknown options on non-SYN segments. But it is still in an acknowledgement segment will not be delivered reliably (unless
prudent to be conservative in what you send, and avoiding buggy the ACK happens to be piggy-backed on data in the other direction).
TCP implementation is not the only reason for negotiating TCP Fixing the scale when the connection is opened has the advantage of
options on SYN segments. Therefore, for each of the extensions lower overhead but the disadvantage that the scale factor cannot be
defined below, TCP options will be sent on non-SYN segments only changed during the connection.)
after an exchange of options on the the SYN segments has indicated
that both sides understand the extension. Furthermore, an
extension option will be sent in a <SYN,ACK> segment only if the
corresponding option was received in the initial <SYN> segment.
A question may be raised about the bandwidth and processing The maximum receive window, and therefore the scale factor, is
overhead for TCP options. Those options that occur on SYN determined by the maximum receive buffer space. In a typical modern
segments are not likely to cause a performance concern. Opening a implementation, this maximum buffer space is set by default but can
TCP connection requires execution of significant special-case be overridden by a user program before a TCP connection is opened.
code, and the processing of options is unlikely to increase that This determines the scale factor, and therefore no new user interface
cost significantly. is needed for window scaling.
On the other hand, a Timestamps option may appear in any data or 2.2. Window Scale Option
ACK segment, adding 12 bytes to the 20-byte TCP header. We
believe that the bandwidth saved by reducing unnecessary
retransmissions will more than pay for the extra header bandwidth.
There is also an issue about the processing overhead for parsing The three-byte Window Scale option may be sent in a SYN segment by a
the variable byte-aligned format of options, particularly with a TCP. It has two purposes: (1) indicate that the TCP is prepared to
RISC-architecture CPU. Appendix A contains a recommended layout do both send and receive window scaling, and (2) communicate a scale
of the options in TCP headers to achieve reasonable data field factor to be applied to its receive window. Thus, a TCP that is
alignment. In the spirit of Header Prediction, a TCP can quickly prepared to scale windows should send the option, even if its own
test for this layout and if it is verified then use a fast path. scale factor is 1. The scale factor is limited to a power of two and
Hosts that use this canonical layout will effectively use the encoded logarithmically, so it may be implemented by binary shift
options as a set of fixed-format fields appended to the TCP operations.
header. However, to retain the philosophical and protocol
framework of TCP options, a TCP must be prepared to parse an
arbitrary options field, albeit with less efficiency.
Finally, we observe that most of the mechanisms defined in this TCP Window Scale Option (WSopt):
memo are important for LFN's and/or very high-speed networks. For
low-speed networks, it might be a performance optimization to NOT
use these mechanisms. A TCP vendor concerned about optimal
performance over low-speed paths might consider turning these
extensions off for low-speed paths, or allow a user or
installation manager to disable them.
2. TCP WINDOW SCALE OPTION Kind: 3
2.1 Introduction Length: 3 bytes
The window scale extension expands the definition of the TCP +---------+---------+---------+
window to 32 bits and then uses a scale factor to carry this | Kind=3 |Length=3 |shift.cnt|
32-bit value in the 16-bit Window field of the TCP header (SEG.WND +---------+---------+---------+
in RFC 793). The scale factor is carried in a new TCP option,
Window Scale. This option is sent only in a SYN segment (a
segment with the SYN bit on), hence the window scale is fixed in
each direction when a connection is opened. (Another design
choice would be to specify the window scale in every TCP segment.
It would be incorrect to send a window scale option only when the
scale factor changed, since a TCP option in an acknowledgement
segment will not be delivered reliably (unless the ACK happens to
be piggy-backed on data in the other direction). Fixing the scale
when the connection is opened has the advantage of lower overhead
but the disadvantage that the scale factor cannot be changed
during the connection.)
The maximum receive window, and therefore the scale factor, is This option is an offer, not a promise; both sides must send Window
determined by the maximum receive buffer space. In a typical Scale options in their SYN segments to enable window scaling in
modern implementation, this maximum buffer space is set by default either direction. If window scaling is enabled, then the TCP that
but can be overridden by a user program before a TCP connection is sent this option will right-shift its true receive-window values by
opened. This determines the scale factor, and therefore no new 'shift.cnt' bits for transmission in SEG.WND. The value 'shift.cnt'
user interface is needed for window scaling. may be zero (offering to scale, while applying a scale factor of 1 to
the receive window).
2.2 Window Scale Option This option may be sent in an initial <SYN> segment (i.e., a segment
with the SYN bit on and the ACK bit off). It may also be sent in a
<SYN,ACK> segment, but only if a Window Scale option was received in
the initial <SYN> segment. A Window Scale option in a segment
without a SYN bit should be ignored.
The three-byte Window Scale option may be sent in a SYN segment by The Window field in a SYN (i.e., a <SYN> or <SYN,ACK>) segment itself
a TCP. It has two purposes: (1) indicate that the TCP is prepared is never scaled.
to do both send and receive window scaling, and (2) communicate a
scale factor to be applied to its receive window. Thus, a TCP
that is prepared to scale windows should send the option, even if
its own scale factor is 1. The scale factor is limited to a power
of two and encoded logarithmically, so it may be implemented by
binary shift operations.
TCP Window Scale Option (WSopt): 2.3. Using the Window Scale Option
Kind: 3 A model implementation of window scaling is as follows, using the
notation of [RFC0793]:
Length: 3 bytes o All windows are treated as 32-bit quantities for storage in the
connection control block and for local calculations. This
includes the send-window (SND.WND) and the receive- window
(RCV.WND) values, as well as the congestion window.
+---------+---------+---------+ o The connection state is augmented by two window shift counts,
| Kind=3 |Length=3 |shift.cnt| Snd.Wind.Scale and Rcv.Wind.Scale, to be applied to the incoming
+---------+---------+---------+ and outgoing window fields, respectively.
This option is an offer, not a promise; both sides must send o If a TCP receives a <SYN> segment containing a Window Scale
Window Scale options in their SYN segments to enable window option, it sends its own Window Scale option in the <SYN,ACK>
scaling in either direction. If window scaling is enabled, segment.
then the TCP that sent this option will right-shift its true
receive-window values by 'shift.cnt' bits for transmission in
SEG.WND. The value 'shift.cnt' may be zero (offering to scale,
while applying a scale factor of 1 to the receive window).
This option may be sent in an initial <SYN> segment (i.e., a o The Window Scale option is sent with shift.cnt = R, where R is the
segment with the SYN bit on and the ACK bit off). It may also value that the TCP would like to use for its receive window.
be sent in a <SYN,ACK> segment, but only if a Window Scale
option was received in the initial <SYN> segment. A Window
Scale option in a segment without a SYN bit should be ignored.
The Window field in a SYN (i.e., a <SYN> or <SYN,ACK>) segment o Upon receiving a SYN segment with a Window Scale option containing
itself is never scaled. shift.cnt = S, a TCP sets Snd.Wind.Scale to S and sets
Rcv.Wind.Scale to R; otherwise, it sets both Snd.Wind.Scale and
Rcv.Wind.Scale to zero.
2.3 Using the Window Scale Option o The window field (SEG.WND) in the header of every incoming
segment, with the exception of SYN segments, is left-shifted by
Snd.Wind.Scale bits before updating SND.WND:
A model implementation of window scaling is as follows, using the SND.WND = SEG.WND << Snd.Wind.Scale
notation of RFC 793 [Postel81]:
* All windows are treated as 32-bit quantities for storage in (assuming the other conditions of RFC 793 are met, and using the
the connection control block and for local calculations. "C" notation "<<" for left-shift).
This includes the send-window (SND.WND) and the receive-
window (RCV.WND) values, as well as the congestion window.
* The connection state is augmented by two window shift counts, o The window field (SEG.WND) of every outgoing segment, with the
Snd.Wind.Scale and Rcv.Wind.Scale, to be applied to the exception of SYN segments, is right-shifted by Rcv.Wind.Scale
incoming and outgoing window fields, respectively. bits:
* If a TCP receives a <SYN> segment containing a Window Scale SND.WND = RCV.WND >> Rcv.Wind.Scale
option, it sends its own Window Scale option in the <SYN,ACK>
segment.
* The Window Scale option is sent with shift.cnt = R, where R TCP determines if a data segment is "old" or "new" by testing whether
is the value that the TCP would like to use for its receive its sequence number is within 2^31 bytes of the left edge of the
window. window, and if it is not, discarding the data as "old". To insure
that new data is never mistakenly considered old and vice- versa, the
left edge of the sender's window has to be at most 2^31 away from the
right edge of the receiver's window. Similarly with the sender's
right edge and receiver's left edge. Since the right and left edges
of either the sender's or receiver's window differ by the window
size, and since the sender and receiver windows can be out of phase
by at most the window size, the above constraints imply that 2 * the
max window size must be less than 2^31, or
* Upon receiving a SYN segment with a Window Scale option max window < 2^30
containing shift.cnt = S, a TCP sets Snd.Wind.Scale to S and
sets Rcv.Wind.Scale to R; otherwise, it sets both
Snd.Wind.Scale and Rcv.Wind.Scale to zero.
* The window field (SEG.WND) in the header of every incoming Since the max window is 2^S (where S is the scaling shift count)
segment, with the exception of SYN segments, is left-shifted times at most 2^16 - 1 (the maximum unscaled window), the maximum
by Snd.Wind.Scale bits before updating SND.WND: window is guaranteed to be < 2*30 if S <= 14. Thus, the shift count
must be limited to 14 (which allows windows of 2^30 = 1 Gbyte). If a
Window Scale option is received with a shift.cnt value exceeding 14,
the TCP should log the error but use 14 instead of the specified
value.
SND.WND = SEG.WND << Snd.Wind.Scale The scale factor applies only to the Window field as transmitted in
the TCP header; each TCP using extended windows will maintain the
window values locally as 32-bit numbers. For example, the
"congestion window" computed by Slow Start and Congestion Avoidance
is not affected by the scale factor, so window scaling will not
introduce quantization into the congestion window.
(assuming the other conditions of RFC 793 are met, and using 2.4. Addressing Window Retraction
the "C" notation "<<" for left-shift).
* The window field (SEG.WND) of every outgoing segment, with When a non-zero scale factor is in use, there are instances when a
the exception of SYN segments, is right-shifted by retracted window can be offered [Mathis08]. The end of the window
Rcv.Wind.Scale bits: will be on a boundary based on the granularity of the scale factor
being used. If the sequence number is then updated by a number of
bytes smaller than that granularity, the TCP will have to either
advertise a new window that is beyond what it previously advertised
(and perhaps beyond the buffer), or will have to advertise a smaller
window, which will cause the TCP window to shrink. Implementations
should ensure that they handle a shrinking window, as specified in
section 4.2.2.16 of [RFC1122].
SEG.WND = RCV.WND >> Rcv.Wind.Scale. For the receiver, this implies that:
TCP determines if a data segment is "old" or "new" by testing 1) The receiver MUST honor, as in-window, any segment that would
whether its sequence number is within 2**31 bytes of the left edge have been in-window for any ACK sent by the receiver.
of the window, and if it is not, discarding the data as "old". To
insure that new data is never mistakenly considered old and vice-
versa, the left edge of the sender's window has to be at most
2**31 away from the right edge of the receiver's window.
Similarly with the sender's right edge and receiver's left edge.
Since the right and left edges of either the sender's or
receiver's window differ by the window size, and since the sender
and receiver windows can be out of phase by at most the window
size, the above constraints imply that 2 * the max window size
must be less than 2**31, or
max window < 2**30
Since the max window is 2**S (where S is the scaling shift count) 2) When window scaling is in effect, the receiver SHOULD track the
times at most 2**16 - 1 (the maximum unscaled window), the maximum actual maximum window sequence number (which is likely to be
window is guaranteed to be < 2*30 if S <= 14. Thus, the shift greater than the window announced by the most recent ACK, if more
count must be limited to 14 (which allows windows of 2**30 = 1 than one segment has arrived since the application consumed any
Gbyte). If a Window Scale option is received with a shift.cnt data in the receive buffer).
value exceeding 14, the TCP should log the error but use 14
instead of the specified value.
The scale factor applies only to the Window field as transmitted On the sender side:
in the TCP header; each TCP using extended windows will maintain
the window values locally as 32-bit numbers. For example, the
"congestion window" computed by Slow Start and Congestion
Avoidance is not affected by the scale factor, so window scaling
will not introduce quantization into the congestion window.
When a non-zero scale factor is in use, there are instances when a 3) The initial transmission MUST honor window on most recent ACK.
retracted window can be offered [Mathis08]. The end of the window
will be on a boundary based on the granularity of the scale factor
being used. If the sequence number is then updated by a number of
bytes smaller than that granularity, the TCP will have to either
advertise a new window that beyond what it previously advertised
(and perhaps beyond the buffer), or will have to advertise a
smaller window, which will cause the TCP window to shrink.
Implementations should ensure that they handle a shrinking window,
as specified in section 4.2.2.16 of RFC 1122 [Braden89].
3. RTTM: ROUND-TRIP TIME MEASUREMENT 4) On first retransmission, or if it is out-of-window by less than
(2^Rcv.Wind.Scale) then do normal retransmission(s) without
regard to receiver window as long as the original segment was in
window when it was sent.
3.1 Introduction 5) On subsequent retransmissions, treat it as zero window probes.
Accurate and current RTT estimates are necessary to adapt to 3. RTTM -- Round-Trip Time Measurement
changing traffic conditions and to avoid an instability known as
"congestion collapse" [Nagle84] in a busy network. However,
accurate measurement of RTT may be difficult both in theory and in
implementation.
Many TCP implementations base their RTT measurements upon a sample 3.1. Introduction
of one packet per window or less. While this yields an adequate
approximation to the RTT for small windows, it results in an
unacceptably poor RTT estimate for an LFN. If we look at RTT
estimation as a signal processing problem (which it is), a data
signal at some frequency, the packet rate, is being sampled at a
lower frequency, the window rate. This lower sampling frequency
violates Nyquist's criteria and may therefore introduce "aliasing"
artifacts into the estimated RTT [Hamming77].
A good RTT estimator with a conservative retransmission timeout Accurate and current RTT estimates are necessary to adapt to changing
calculation can tolerate aliasing when the sampling frequency is traffic conditions and to avoid an instability known as "congestion
"close" to the data frequency. For example, with a window of 8 collapse" [RFC0896] in a busy network. However, accurate measurement
packets, the sample rate is 1/8 the data frequency -- less than an of RTT may be difficult both in theory and in implementation.
order of magnitude different. However, when the window is tens or
hundreds of packets, the RTT estimator may be seriously in error,
resulting in spurious retransmissions.
If there are dropped packets, the problem becomes worse. Zhang Many TCP implementations base their RTT measurements upon a sample of
[Zhang86], Jain [Jain86] and Karn [Karn87] have shown that it is one packet per window or less. While this yields an adequate
not possible to accumulate reliable RTT estimates if retransmitted approximation to the RTT for small windows, it results in an
segments are included in the estimate. Since a full window of unacceptably poor RTT estimate for an LFN. If we look at RTT
data will have been transmitted prior to a retransmission, all of estimation as a signal processing problem (which it is), a data
the segments in that window will have to be ACKed before the next signal at some frequency, the packet rate, is being sampled at a
RTT sample can be taken. This means at least an additional lower frequency, the window rate. This lower sampling frequency
window's worth of time between RTT measurements and, as the error violates Nyquist's criteria and may therefore introduce "aliasing"
rate approaches one per window of data (e.g., 10**-6 errors per artifacts into the estimated RTT [Hamming77].
bit for the Wideband satellite network), it becomes effectively
impossible to obtain a valid RTT measurement.
A solution to these problems, which actually simplifies the sender A good RTT estimator with a conservative retransmission timeout
substantially, is as follows: using TCP options, the sender places calculation can tolerate aliasing when the sampling frequency is
a timestamp in each data segment, and the receiver reflects these "close" to the data frequency. For example, with a window of 8
timestamps back in ACK segments. Then a single subtract gives the packets, the sample rate is 1/8 the data frequency -- less than an
sender an accurate RTT measurement for every ACK segment (which order of magnitude different. However, when the window is tens or
will correspond to every other data segment, with a sensible hundreds of packets, the RTT estimator may be seriously in error,
receiver). We call this the RTTM (Round-Trip Time Measurement) resulting in spurious retransmissions.
mechanism.
It is vitally important to use the RTTM mechanism with big If there are dropped packets, the problem becomes worse. Zhang
windows; otherwise, the door is opened to some dangerous [Zhang86], Jain [Jain86] and Karn [Karn87] have shown that it is not
instabilities due to aliasing. Furthermore, the option is possible to accumulate reliable RTT estimates if retransmitted
probably useful for all TCP's, since it simplifies the sender. segments are included in the estimate. Since a full window of data
will have been transmitted prior to a retransmission, all of the
segments in that window will have to be ACKed before the next RTT
sample can be taken. This means at least an additional window's
worth of time between RTT measurements and, as the error rate
approaches one per window of data (e.g., 10^-6 errors per bit for the
Wideband satellite network), it becomes effectively impossible to
obtain a valid RTT measurement.
3.2 TCP Timestamps Option A solution to these problems, which actually simplifies the sender
substantially, is as follows: using TCP options, the sender places a
timestamp in each data segment, and the receiver reflects these
timestamps back in ACK segments. Then a single subtract gives the
sender an accurate RTT measurement for every ACK segment (which will
correspond to every other data segment, with a sensible receiver).
We call this the RTTM (Round-Trip Time Measurement) mechanism.
TCP is a symmetric protocol, allowing data to be sent at any time It is vitally important to use the RTTM mechanism with big windows;
in either direction, and therefore timestamp echoing may occur in otherwise, the door is opened to some dangerous instabilities due to
either direction. For simplicity and symmetry, we specify that aliasing. Furthermore, the option is probably useful for all TCP's,
timestamps always be sent and echoed in both directions. For since it simplifies the sender.
efficiency, we combine the timestamp and timestamp reply fields
into a single TCP Timestamps Option.
TCP Timestamps Option (TSopt): 3.2. TCP Timestamps Option
Kind: 8 TCP is a symmetric protocol, allowing data to be sent at any time in
either direction, and therefore timestamp echoing may occur in either
direction. For simplicity and symmetry, we specify that timestamps
always be sent and echoed in both directions. For efficiency, we
combine the timestamp and timestamp reply fields into a single TCP
Timestamps Option.
Length: 10 bytes TCP Timestamps Option (TSopt):
+-------+-------+---------------------+---------------------+ Kind: 8
|Kind=8 | 10 | TS Value (TSval) |TS Echo Reply (TSecr)|
+-------+-------+---------------------+---------------------+
1 1 4 4
The Timestamps option carries two four-byte timestamp fields. Length: 10 bytes
The Timestamp Value field (TSval) contains the current value of
the timestamp clock of the TCP sending the option.
The Timestamp Echo Reply field (TSecr) is valid if the ACK bit +-------+-------+---------------------+---------------------+
is set in the TCP header; if it is valid, it echos a timestamp |Kind=8 | 10 | TS Value (TSval) |TS Echo Reply (TSecr)|
value that was sent by the remote TCP in the TSval field of a +-------+-------+---------------------+---------------------+
Timestamps option. When TSecr is not valid, its value must be 1 1 4 4
zero. The TSecr value will generally be from the most recent
Timestamp option that was received; however, there are
exceptions that are explained below.
A TCP may send the Timestamps option (TSopt) in an initial The Timestamps option carries two four-byte timestamp fields. The
<SYN> segment (i.e., a segment containing a SYN bit and no ACK Timestamp Value field (TSval) contains the current value of the
bit), and may send a TSopt in other segments only if it timestamp clock of the TCP sending the option.
received a TSopt in the initial <SYN> or <SYN,ACK> segment for
the connection. Once a TSopt has been sent or received in a
non <SYN> segment, it must be sent in all segments. Once a
TSopt has been received in a non <SYN> segment, then any
successive segment that is received without the RST bit and
without a TSopt may dropped without further processing, and an
ACK of the current SND.UNA generated.
In the case of crossing SYN packets where one SYN contains a The Timestamp Echo Reply field (TSecr) is valid if the ACK bit is set
TSopt and the other doesn't, both sides should put a TSopt in in the TCP header; if it is valid, it echos a timestamp value that
the <SYN,ACK> segment. was sent by the remote TCP in the TSval field of a Timestamps option.
When TSecr is not valid, its value must be zero. However, a value of
zero does not imply TSecr being invalid. The TSecr value will
generally be from the most recent Timestamp option that was received;
however, there are exceptions that are explained below.
3.3 The RTTM Mechanism A TCP may send the Timestamps option (TSopt) in an initial <SYN>
segment (i.e., a segment containing a SYN bit and no ACK bit). Once
a TSopt has been sent or received in a non <SYN> segment, it must be
sent in all segments. Once a TSopt has been received in a non <SYN>
segment, then any successive segment that is received without the RST
bit and without a TSopt may be dropped without further processing,
and an ACK of the current SND.UNA generated.
RTTM places a Timestamps option in every segment, with a TSval In the case of crossing SYN packets where one SYN contains a TSopt
that is obtained from a (virtual) "timestamp clock". Values of and the other doesn't, both sides should put a TSopt in the <SYN,ACK>
this clock values must be at least approximately proportional to segment.
real time, in order to measure actual RTT.
These TSval values are echoed in TSecr values in the reverse 3.3. The RTTM Mechanism
direction. The difference between a received TSecr value and the
current timestamp clock value provides an RTT measurement.
When timestamps are used, every segment that is received will RTTM places a Timestamps option in every segment, with a TSval that
contain a TSecr value; however, these values cannot all be used to is obtained from a (virtual) "timestamp clock". Values of this clock
update the measured RTT. The following example illustrates why. values must be at least approximately proportional to real time, in
It shows a one-way data flow with segments arriving in sequence order to measure actual RTT.
without loss. Here A, B, C... represent data blocks occupying
successive blocks of sequence numbers, and ACK(A),... represent
the corresponding cumulative acknowledgments. The two timestamp
fields of the Timestamps option are shown symbolically as <TSval=
x,TSecr=y>. Each TSecr field contains the value most recently
received in a TSval field.
TCP A TCP B These TSval values are echoed in TSecr values in the reverse
direction. The difference between a received TSecr value and the
current timestamp clock value provides an RTT measurement.
<A,TSval=1,TSecr=120> ------> When timestamps are used, every segment that is received will contain
a TSecr value; however, these values cannot all be used to update the
measured RTT. The following example illustrates why. It shows a
one-way data flow with segments arriving in sequence without loss.
Here A, B, C... represent data blocks occupying successive blocks of
sequence numbers, and ACK(A),... represent the corresponding
cumulative acknowledgments. The two timestamp fields of the
Timestamps option are shown symbolically as <TSval=x,TSecr=y>. Each
TSecr field contains the value most recently received in a TSval
field.
<---- <ACK(A),TSval=127,TSecr=1> TCP A TCP B
<B,TSval=5,TSecr=127> ------> <A,TSval=1,TSecr=120> ------>
<---- <ACK(B),TSval=131,TSecr=5> <---- <ACK(A),TSval=127,TSecr=1>
<B,TSval=5,TSecr=127> ------>
<---- <ACK(B),TSval=131,TSecr=5>
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
<C,TSval=65,TSecr=131> ------> <C,TSval=65,TSecr=131> ------>
<---- <ACK(C),TSval=191,TSecr=65> <---- <ACK(C),TSval=191,TSecr=65>
(etc) (etc)
The dotted line marks a pause (60 time units long) in which A had The dotted line marks a pause (60 time units long) in which A had
nothing to send. Note that this pause inflates the RTT which B nothing to send. Note that this pause inflates the RTT which B could
could infer from receiving TSecr=131 in data segment C. Thus, in infer from receiving TSecr=131 in data segment C. Thus, in one-way
one-way data flows, RTTM in the reverse direction measures a value data flows, RTTM in the reverse direction measures a value that is
that is inflated by gaps in sending data. However, the following inflated by gaps in sending data. However, the following rule
rule prevents a resulting inflation of the measured RTT: prevents a resulting inflation of the measured RTT:
RTTM Rule: A TSecr value received in a segment is used to RTTM Rule: A TSecr value received in a segment is used to update
update the averaged RTT measurement only if the segment the averaged RTT measurement only if
acknowledges some new data, i.e., only if it advances the
left edge of the send window.
Since TCP B is not sending data, the data segment C does not a) the segment acknowledges some new data, i.e., only if it
acknowledge any new data when it arrives at B. Thus, the inflated advances the left edge of the send window, and
RTTM measurement is not used to update B's RTTM measurement.
Implementors should note that with Timestamps multiple RTTMs can b) the segment does not indicate any loss or reordering, i.e.
be taken per RTT. Many RTO estimators have a weighting factor contains SACK options
based on an implicit assumption that at most one RTTM will be
gotten per RTT. When using multiple RTTMs per RTT to update the
RTO estimator, the weighting factor needs to be decreased to take
into account the more frequent RTTMs. For example, an
implementation could choose to just use one sample per RTT to
update the RTO estimator, or or vary the gain based on the
congestion window, or take an average of all the RTTM measurements
received over one RTT, and then use that value to update the RTO
estimator. This document does not prescribe any particular method
for modifying the RTO estimator, the important point is that the
implementation should do something more than just feeding
additional RTTM samples from one RTT into the RTO estimator.
3.4 Which Timestamp to Echo Since TCP B is not sending data, the data segment C does not
If more than one Timestamps option is received before a reply acknowledge any new data when it arrives at B. Thus, the inflated
segment is sent, the TCP must choose only one of the TSvals to RTTM measurement is not used to update B's RTTM measurement.
echo, ignoring the others. To minimize the state kept in the
receiver (i.e., the number of unprocessed TSvals), the receiver
should be required to retain at most one timestamp in the
connection control block.
There are three situations to consider: Implementors should note that with Timestamps multiple RTTMs can be
taken per RTT. Many RTO estimators have a weighting factor based on
an implicit assumption that at most one RTTM will be gotten per RTT.
When using multiple RTTMs per RTT to update the RTO estimator, the
weighting factor needs to be decreased to take into account the more
frequent RTTMs. For example, an implementation could choose to just
use one sample per RTT to update the RTO estimator, or or vary the
gain based on the congestion window, or take an average of all the
RTTM measurements received over one RTT, and then use that value to
update the RTO estimator. This document does not prescribe any
particular method for modifying the RTO estimator, the important
point is that the implementation should do something more than just
feeding additional RTTM samples from one RTT into the RTO estimator.
(A) Delayed ACKs. 3.4. Which Timestamp to Echo
Many TCP's acknowledge only every Kth segment out of a group If more than one Timestamps option is received before a reply segment
of segments arriving within a short time interval; this is sent, the TCP must choose only one of the TSvals to echo, ignoring
policy is known generally as "delayed ACKs". The data-sender the others. To minimize the state kept in the receiver (i.e., the
TCP must measure the effective RTT, including the additional number of unprocessed TSvals), the receiver should be required to
time due to delayed ACKs, or else it will retransmit retain at most one timestamp in the connection control block.
unnecessarily. Thus, when delayed ACKs are in use, the
receiver should reply with the TSval field from the earliest
unacknowledged segment.
(B) A hole in the sequence space (segment(s) have been lost). There are three situations to consider:
The sender will continue sending until the window is filled, (A) Delayed ACKs.
and the receiver may be generating ACKs as these out-of-order
segments arrive (e.g., to aid "fast retransmit").
The lost segment is probably a sign of congestion, and in Many TCP's acknowledge only every Kth segment out of a group of
that situation the sender should be conservative about segments arriving within a short time interval; this policy is
retransmission. Furthermore, it is better to overestimate known generally as "delayed ACKs". The data-sender TCP must
than underestimate the RTT. An ACK for an out-of-order measure the effective RTT, including the additional time due to
segment should therefore contain the timestamp from the most delayed ACKs, or else it will retransmit unnecessarily. Thus,
recent segment that advanced the window. when delayed ACKs are in use, the receiver should reply with the
TSval field from the earliest unacknowledged segment.
The same situation occurs if segments are re-ordered by the (B) A hole in the sequence space (segment(s) have been lost).
network.
(C) A filled hole in the sequence space. The sender will continue sending until the window is filled, and
the receiver may be generating ACKs as these out-of-order
segments arrive (e.g., to aid "fast retransmit").
The segment that fills the hole represents the most recent The lost segment is probably a sign of congestion, and in that
measurement of the network characteristics. On the other situation the sender should be conservative about
hand, an RTT computed from an earlier segment would probably retransmission. Furthermore, it is better to overestimate than
include the sender's retransmit time-out, badly biasing the underestimate the RTT. An ACK for an out-of-order segment
sender's average RTT estimate. Thus, the timestamp from the should therefore contain the timestamp from the most recent
latest segment (which filled the hole) must be echoed. segment that advanced the window.
An algorithm that covers all three cases is described in the The same situation occurs if segments are re-ordered by the
following rules for Timestamps option processing on a synchronized network.
connection:
(1) The connection state is augmented with two 32-bit slots: (C) A filled hole in the sequence space.
TS.Recent holds a timestamp to be echoed in TSecr whenever a The segment that fills the hole represents the most recent
segment is sent, and Last.ACK.sent holds the ACK field from measurement of the network characteristics. On the other hand,
the last segment sent. Last.ACK.sent will equal RCV.NXT an RTT computed from an earlier segment would probably include
except when ACKs have been delayed. the sender's retransmit time-out, badly biasing the sender's
average RTT estimate. Thus, the timestamp from the latest
segment (which filled the hole) must be echoed.
(2) If: An algorithm that covers all three cases is described in the
following rules for Timestamps option processing on a synchronized
connection:
SEG.TSval >= TSrecent and SEG.SEQ <= Last.ACK.sent (1) The connection state is augmented with two 32-bit slots:
then SEG.TSval is copied to TS.Recent; otherwise, it is TS.Recent holds a timestamp to be echoed in TSecr whenever a
ignored. segment is sent, and Last.ACK.sent holds the ACK field from the
last segment sent. Last.ACK.sent will equal RCV.NXT except when
ACKs have been delayed.
(3) When a TSopt is sent, its TSecr field is set to the current (2) If:
TS.Recent value.
The following examples illustrate these rules. Here A, B, C... SEG.TSval >= TSrecent and SEG.SEQ <= Last.ACK.sent
represent data segments occupying successive blocks of sequence
numbers, and ACK(A),... represent the corresponding
acknowledgment segments. Note that ACK(A) has the same sequence
number as B. We show only one direction of timestamp echoing, for
clarity.
o Packets arrive in sequence, and some of the ACKs are delayed. then SEG.TSval is copied to TS.Recent; otherwise, it is ignored.
By Case (A), the timestamp from the oldest unacknowledged (3) When a TSopt is sent, its TSecr field is set to the current
segment is echoed. TS.Recent value.
TS.Recent The following examples illustrate these rules. Here A, B, C...
<A, TSval=1> -------------------> represent data segments occupying successive blocks of sequence
1 numbers, and ACK(A),... represent the corresponding acknowledgment
<B, TSval=2> -------------------> segments. Note that ACK(A) has the same sequence number as B. We
1 show only one direction of timestamp echoing, for clarity.
<C, TSval=3> ------------------->
1
<---- <ACK(C), TSecr=1>
(etc)
o Packets arrive out of order, and every packet is o Packets arrive in sequence, and some of the ACKs are delayed.
acknowledged.
By Case (B), the timestamp from the last segment that By Case (A), the timestamp from the oldest unacknowledged segment
advanced the left window edge is echoed, until the missing is echoed.
segment arrives; it is echoed according to Case (C). The
same sequence would occur if segments B and D were lost and
retransmitted..
TS.Recent TS.Recent
<A, TSval=1> -------------------> <A, TSval=1> ------------------->
1 1
<---- <ACK(A), TSecr=1> <B, TSval=2> ------------------->
1 1
<C, TSval=3> -------------------> <C, TSval=3> ------------------->
1 1
<---- <ACK(A), TSecr=1>
1
<B, TSval=2> ------------------->
2
<---- <ACK(C), TSecr=2>
2
<E, TSval=5> ------------------->
2
<---- <ACK(C), TSecr=2>
2
<D, TSval=4> ------------------->
4
<---- <ACK(E), TSecr=4>
(etc)
4. PAWS: PROTECTION AGAINST WRAPPED SEQUENCE NUMBERS <---- <ACK(C), TSecr=1>
(etc)
4.1 Introduction o Packets arrive out of order, and every packet is acknowledged.
Section 4.2 describes a simple mechanism to reject old duplicate By Case (B), the timestamp from the last segment that advanced the
segments that might corrupt an open TCP connection; we call this left window edge is echoed, until the missing segment arrives; it
mechanism PAWS (Protection Against Wrapped Sequence numbers). is echoed according to Case (C). The same sequence would occur if
PAWS operates within a single TCP connection, using state that is segments B and D were lost and retransmitted..
saved in the connection control block. Section 4.3 and Appendix C
discuss the implications of the PAWS mechanism for avoiding old
duplicates from previous incarnations of the same connection.
4.2 The PAWS Mechanism TS.Recent
<A, TSval=1> ------------------->
1
<---- <ACK(A), TSecr=1>
1
<C, TSval=3> ------------------->
1
<---- <ACK(A), TSecr=1>
1
<B, TSval=2> ------------------->
2
<---- <ACK(C), TSecr=2>
2
<E, TSval=5> ------------------->
2
<---- <ACK(C), TSecr=2>
2
<D, TSval=4> ------------------->
4
<---- <ACK(E), TSecr=4>
(etc)
PAWS uses the same TCP Timestamps option as the RTTM mechanism 4. PAWS -- Protection Against Wrapped Sequence Numbers
described earlier, and assumes that every received TCP segment
(including data and ACK segments) contains a timestamp SEG.TSval
whose values are monotonically non-decreasing in time. The basic
idea is that a segment can be discarded as an old duplicate if it
is received with a timestamp SEG.TSval less than some timestamp
recently received on this connection.
In both the PAWS and the RTTM mechanism, the "timestamps" are 4.1. Introduction
32-bit unsigned integers in a modular 32-bit space. Thus, "less
than" is defined the same way it is for TCP sequence numbers, and
the same implementation techniques apply. If s and t are
timestamp values, s < t if 0 < (t - s) < 2**31, computed in
unsigned 32-bit arithmetic.
The choice of incoming timestamps to be saved for this comparison Section 4.2describes a simple mechanism to reject old duplicate
must guarantee a value that is monotonically increasing. For segments that might corrupt an open TCP connection; we call this
example, we might save the timestamp from the segment that last mechanism PAWS (Protection Against Wrapped Sequence numbers). PAWS
advanced the left edge of the receive window, i.e., the most operates within a single TCP connection, using state that is saved in
recent in-sequence segment. Instead, we choose the value the connection control block. Section 4.3 and Appendix C discuss the
TS.Recent introduced in Section 3.4 for the RTTM mechanism, since implications of the PAWS mechanism for avoiding old duplicates from
using a common value for both PAWS and RTTM simplifies the previous incarnations of the same connection.
implementation of both. As Section 3.4 explained, TS.Recent
differs from the timestamp from the last in-sequence segment only
in the case of delayed ACKs, and therefore by less than one
window. Either choice will therefore protect against sequence
number wrap-around.
RTTM was specified in a symmetrical manner, so that TSval 4.2. The PAWS Mechanism
timestamps are carried in both data and ACK segments and are
echoed in TSecr fields carried in returning ACK or data segments.
PAWS submits all incoming segments to the same test, and therefore
protects against duplicate ACK segments as well as data segments.
(An alternative non-symmetric algorithm would protect against old
duplicate ACKs: the sender of data would reject incoming ACK
segments whose TSecr values were less than the TSecr saved from
the last segment whose ACK field advanced the left edge of the
send window. This algorithm was deemed to lack economy of
mechanism and symmetry.)
TSval timestamps sent on {SYN} and {SYN,ACK} segments are used to PAWS uses the same TCP Timestamps option as the RTTM mechanism
initialize PAWS. PAWS protects against old duplicate non-SYN described earlier, and assumes that every received TCP segment
segments, and duplicate SYN segments received while there is a (including data and ACK segments) contains a timestamp SEG.TSval
synchronized connection. Duplicate {SYN} and {SYN,ACK} segments whose values are monotonically non-decreasing in time. The basic
received when there is no connection will be discarded by the idea is that a segment can be discarded as an old duplicate if it is
normal 3-way handshake and sequence number checks of TCP. received with a timestamp SEG.TSval less than some timestamp recently
received on this connection.
RFC 1323 recommended that RST segments NOT carry timestamps, and In both the PAWS and the RTTM mechanism, the "timestamps" are 32-bit
that they be acceptable regardless of their timestamp. At that unsigned integers in a modular 32-bit space. Thus, "less than" is
time, the thinking was that old duplicate RST segments should be defined the same way it is for TCP sequence numbers, and the same
exceedingly unlikely, and their cleanup function should take implementation techniques apply. If s and t are timestamp values,
precedence over timestamps. More recently, discussion about
various blind attacks on TCP connections have raised the
suggestion that if the Timestamps option is present, SEG.TSecr
could be used to provide stricter acceptance tests for RST
packets. While still under discussion, to enable research into
this area it is now recommended that when generating a RST, that
if the packet causing the RST to be generated contained a
Timestamps option that the RST also contain a Timestamps option.
In the RST segment, SEG.TSecr should be set to SEG.TSval from the
incoming packet and SEG.TSval should be set to zero. If a RST is
being generated because of a user abort, and Snd.TS.OK is set,
then a Timestamps option should be included in the RST. When a
RST packet is received, it must not be subjected to PAWS checks,
and information from the Timestamps option must not be use to
update connection state information. SEG.TSecr may be used to
provide stricter RST acceptance checks.
4.2.1 Basic PAWS Algorithm s < t if 0 < (t - s) < 2^31,
The PAWS algorithm requires the following processing to be computed in unsigned 32-bit arithmetic.
performed on all incoming segments for a synchronized
connection:
R1) If there is a Timestamps option in the arriving segment, The choice of incoming timestamps to be saved for this comparison
SEG.TSval < TS.Recent, TS.Recent is valid (see later must guarantee a value that is monotonically increasing. For
discussion) and the RST bit is not set, then treat the example, we might save the timestamp from the segment that last
arriving segment as not acceptable: advanced the left edge of the receive window, i.e., the most recent
in-sequence segment. Instead, we choose the value TS.Recent
introduced in Section 3.4 for the RTTM mechanism, since using a
common value for both PAWS and RTTM simplifies the implementation of
both. As Section 3.4 explained, TS.Recent differs from the timestamp
from the last in-sequence segment only in the case of delayed ACKs,
and therefore by less than one window. Either choice will therefore
protect against sequence number wrap-around.
Send an acknowledgement in reply as specified in RFC RTTM was specified in a symmetrical manner, so that TSval timestamps
793 page 69 and drop the segment. are carried in both data and ACK segments and are echoed in TSecr
fields carried in returning ACK or data segments. PAWS submits all
incoming segments to the same test, and therefore protects against
duplicate ACK segments as well as data segments. (An alternative
non-symmetric algorithm would protect against old duplicate ACKs: the
sender of data would reject incoming ACK segments whose TSecr values
were less than the TSecr saved from the last segment whose ACK field
advanced the left edge of the send window. This algorithm was deemed
to lack economy of mechanism and symmetry.)
Note: it is necessary to send an ACK segment in order TSval timestamps sent on >SYN< and >SYN,ACK< segments are used to
to retain TCP's mechanisms for detecting and initialize PAWS. PAWS protects against old duplicate non-SYN
recovering from half-open connections. For example, segments, and duplicate SYN segments received while there is a
see Figure 10 of RFC 793. synchronized connection. Duplicate >SYN< and >SYN,ACK< segments
received when there is no connection will be discarded by the normal
3-way handshake and sequence number checks of TCP.
R2) If the segment is outside the window, reject it (normal RFC 1323 recommended that RST segments NOT carry timestamps, and that
TCP processing) they be acceptable regardless of their timestamp. At that time, the
thinking was that old duplicate RST segments should be exceedingly
unlikely, and their cleanup function should take precedence over
timestamps. More recently, discussion about various blind attacks on
TCP connections have raised the suggestion that if the Timestamps
option is present, SEG.TSecr could be used to provide stricter
acceptance tests for RST packets. While still under discussion, to
enable research into this area it is now recommended that when
generating a RST, that if the packet causing the RST to be generated
contained a Timestamps option that the RST also contain a Timestamps
option. In the RST segment, SEG.TSecr should be set to SEG.TSval
from the incoming packet and SEG.TSval should be set to zero. If a
RST is being generated because of a user abort, and Snd.TS.OK is set,
then a Timestamps option should be included in the RST. When a RST
packet is received, it must not be subjected to PAWS checks, and
information from the Timestamps option must not be use to update
connection state information. SEG.TSecr may be used to provide
stricter RST acceptance checks.
R3) If an arriving segment satisfies: SEG.SEQ <= Last.ACK.sent 4.2.1. Basic PAWS Algorithm
(see Section 3.4), then record its timestamp in TS.Recent.
R4) If an arriving segment is in-sequence (i.e., at the left The PAWS algorithm requires the following processing to be performed
window edge), then accept it normally. on all incoming segments for a synchronized connection:
R5) Otherwise, treat the segment as a normal in-window, out- R1) If there is a Timestamps option in the arriving segment,
of-sequence TCP segment (e.g., queue it for later delivery SEG.TSval < TS.Recent, TS.Recent is valid (see later discussion)
to the user). and the RST bit is not set, then treat the arriving segment as
not acceptable:
Steps R2, R4, and R5 are the normal TCP processing steps Send an acknowledgement in reply as specified in RFC 793 page
specified by RFC 793. 69 and drop the segment.
It is important to note that the timestamp is checked only when Note: it is necessary to send an ACK segment in order to
a segment first arrives at the receiver, regardless of whether retain TCP's mechanisms for detecting and recovering from
it is in-sequence or it must be queued for later delivery. half-open connections. For example, see Figure 10 of RFC
793.
Consider the following example. R2) If the segment is outside the window, reject it (normal TCP
processing)
Suppose the segment sequence: A.1, B.1, C.1, ..., Z.1 has R3) If an arriving segment satisfies: SEG.SEQ <= Last.ACK.sent (see
been sent, where the letter indicates the sequence number Section 3.4), then record its timestamp in TS.Recent.
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 R4) If an arriving segment is in-sequence (i.e., at the left window
window of data is in transit at all times, and after a loss a edge), then accept it normally.
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 R1-R5 R5) Otherwise, treat the segment as a normal in-window, out- of-
could lead to discarding some segments unnecessarily, as shown sequence TCP segment (e.g., queue it for later delivery to the
in the following example: user).
Suppose again that segments: A.1, B.1, C.1, ..., Z.1 have Steps R2, R4, and R5 are the normal TCP processing steps specified by
been sent in sequence and that segment B.1 has been lost. RFC 793.
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 It is important to note that the timestamp is checked only when a
triggered by a timeout, some of the segments C.1, ... Z.1 must segment first arrives at the receiver, regardless of whether it is
have been delayed longer than the RTO time. This is presumably in-sequence or it must be queued for later delivery.
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 Consider the following example.
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 Suppose the segment sequence: A.1, B.1, C.1, ..., Z.1 has been
in which timestamps will cause performance degradation by sent, where the letter indicates the sequence number and the digit
unnecessarily discarding segments. 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.
4.2.2 Timestamp Clock 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.
It is important to understand that the PAWS algorithm does not In certain unlikely circumstances, the algorithm of rules R1-R5 could
require clock synchronization between sender and receiver. The lead to discarding some segments unnecessarily, as shown in the
sender's timestamp clock is used to stamp the segments, and the following example:
sender uses the echoed timestamp to measure RTT's. However,
the receiver treats the timestamp as simply a monotonically
increasing serial number, without any necessary connection to
its clock. From the receiver's viewpoint, the timestamp is
acting as a logical extension of the high-order bits of the
sequence number.
The receiver algorithm does place some requirements on the Suppose again that segments: A.1, B.1, C.1, ..., Z.1 have been
frequency of the timestamp clock. 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.
(a) The timestamp clock must not be "too slow". 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.
It must tick at least once for each 2**31 bytes sent. In Even if a segment were delayed past the RTO, the Fast Retransmit
fact, in order to be useful to the sender for round trip mechanism [Jacobson90c] will cause the delayed packets to be
timing, the clock should tick at least once per window's retransmitted at the same time as B.2, avoiding an extra RTT and
worth of data, and even with the window extension defined therefore causing a very small performance penalty.
in Section 2.2, 2**31 bytes must be at least two windows.
To make this more quantitative, any clock faster than 1 We know of no case with a significant probability of occurrence in
tick/sec will reject old duplicate segments for link which timestamps will cause performance degradation by unnecessarily
speeds of ~8 Gbps. A 1ms timestamp clock will work at discarding segments.
link speeds up to 8 Tbps (8*10**12) bps!
(b) The timestamp clock must not be "too fast". 4.2.2. Timestamp Clock
Its recycling time must be greater than MSL seconds. It is important to understand that the PAWS algorithm does not
Since the clock (timestamp) is 32 bits and the worst-case require clock synchronization between sender and receiver. The
MSL is 255 seconds, the maximum acceptable clock frequency sender's timestamp clock is used to stamp the segments, and the
is one tick every 59 ns. sender uses the echoed timestamp to measure RTT's. However, the
receiver treats the timestamp as simply a monotonically increasing
serial number, without any necessary connection to its clock. From
the receiver's viewpoint, the timestamp is acting as a logical
extension of the high-order bits of the sequence number.
However, it is desirable to establish a much longer The receiver algorithm does place some requirements on the frequency
recycle period, in order to handle outdated timestamps on of the timestamp clock.
idle connections (see Section 4.2.3), and to relax the MSL
requirement for preventing sequence number wrap-around.
With a 1 ms timestamp clock, the 32-bit timestamp will
wrap its sign bit in 24.8 days. Thus, it will reject old
duplicates on the same connection if MSL is 24.8 days or
less. This appears to be a very safe figure; an MSL of
24.8 days or longer can probably be assumed by the gateway
system without requiring precise MSL enforcement by the
TTL value in the IP layer.
Based upon these considerations, we choose a timestamp clock (a) The timestamp clock must not be "too slow".
frequency in the range 1 ms to 1 sec per tick. This range also
matches the requirements of the RTTM mechanism, which does not
need much more resolution than the granularity of the
retransmit timer, e.g., tens or hundreds of milliseconds.
The PAWS mechanism also puts a strong monotonicity requirement It must tick at least once for each 2^31 bytes sent. In fact,
on the sender's timestamp clock. The method of implementation in order to be useful to the sender for round trip timing, the
of the timestamp clock to meet this requirement depends upon clock should tick at least once per window's worth of data, and
the system hardware and software. even with the window extension defined in Section 2.2, 2^31
bytes must be at least two windows.
* Some hosts have a hardware clock that is guaranteed to be To make this more quantitative, any clock faster than 1 tick/sec
monotonic between hardware resets. will reject old duplicate segments for link speeds of ~8 Gbps.
A 1ms timestamp clock will work at link speeds up to 8 Tbps
(8*10^12) bps!
* A clock interrupt may be used to simply increment a binary (b) The timestamp clock must not be "too fast".
integer by 1 periodically.
* The timestamp clock may be derived from a system clock Its recycling time must be greater than MSL seconds. Since the
that is subject to being abruptly changed, by adding a clock (timestamp) is 32 bits and the worst-case MSL is 255
variable offset value. This offset is initialized to seconds, the maximum acceptable clock frequency is one tick
zero. When a new timestamp clock value is needed, the every 59 ns.
offset can be adjusted as necessary to make the new value
equal to or larger than the previous value (which was
saved for this purpose).
4.2.3 Outdated Timestamps However, it is desirable to establish a much longer recycle
period, in order to handle outdated timestamps on idle
connections (see Section 4.2.3), and to relax the MSL
requirement for preventing sequence number wrap-around. With a
1 ms timestamp clock, the 32-bit timestamp will wrap its sign
bit in 24.8 days. Thus, it will reject old duplicates on the
same connection if MSL is 24.8 days or less. This appears to be
a very safe figure; an MSL of 24.8 days or longer can probably
be assumed by the gateway system without requiring precise MSL
enforcement by the TTL value in the IP layer.
If a connection remains idle long enough for the timestamp Based upon these considerations, we choose a timestamp clock
clock of the other TCP to wrap its sign bit, then the value frequency in the range 1 ms to 1 sec per tick. This range also
saved in TS.Recent will become too old; as a result, the PAWS matches the requirements of the RTTM mechanism, which does not need
mechanism will cause all subsequent segments to be rejected, much more resolution than the granularity of the retransmit timer,
freezing the connection (until the timestamp clock wraps its e.g., tens or hundreds of milliseconds.
sign bit again).
With the chosen range of timestamp clock frequencies (1 sec to The PAWS mechanism also puts a strong monotonicity requirement on the
1 ms), the time to wrap the sign bit will be between 24.8 days sender's timestamp clock. The method of implementation of the
and 24800 days. A TCP connection that is idle for more than 24 timestamp clock to meet this requirement depends upon the system
days and then comes to life is exceedingly unusual. However, hardware and software.
it is undesirable in principle to place any limitation on TCP
connection lifetimes.
We therefore require that an implementation of PAWS include a o Some hosts have a hardware clock that is guaranteed to be
mechanism to "invalidate" the TS.Recent value when a connection monotonic between hardware resets.
is idle for more than 24 days. (An alternative solution to the
problem of outdated timestamps would be to send keep-alive
segments at a very low rate, but still more often than the
wrap-around time for timestamps, e.g., once a day. This would
impose negligible overhead. However, the TCP specification has
never included keep-alives, so the solution based upon
invalidation was chosen.)
Note that a TCP does not know the frequency, and therefore, the
wraparound time, of the other TCP, so it must assume the worst.
The validity of TS.Recent needs to be checked only if the basic
PAWS timestamp check fails, i.e., only if SEG.TSval <
TS.Recent. If TS.Recent is found to be invalid, then the
segment is accepted, regardless of the failure of the timestamp
check, and rule R3 updates TS.Recent with the TSval from the
new segment.
To detect how long the connection has been idle, the TCP may o A clock interrupt may be used to simply increment a binary integer
update a clock or timestamp value associated with the by 1 periodically.
connection whenever TS.Recent is updated, for example. The
details will be implementation-dependent.
4.2.4 Header Prediction o The timestamp clock may be derived from a system clock that is
subject to being abruptly changed, by adding a variable offset
value. This offset is initialized to zero. When a new timestamp
clock value is needed, the offset can be adjusted as necessary to
make the new value equal to or larger than the previous value
(which was saved for this purpose).
"Header prediction" [Jacobson90a] is a high-performance 4.2.3. Outdated Timestamps
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 If a connection remains idle long enough for the timestamp clock of
the following recommended sequence for processing an arriving the other TCP to wrap its sign bit, then the value saved in TS.Recent
TCP segment: will become too old; as a result, the PAWS mechanism will cause all
subsequent segments to be rejected, freezing the connection (until
the timestamp clock wraps its sign bit again).
H1) Check timestamp (same as step R1 above) With the chosen range of timestamp clock frequencies (1 sec to 1 ms),
the time to wrap the sign bit will be between 24.8 days and 24800
days. A TCP connection that is idle for more than 24 days and then
comes to life is exceedingly unusual. However, it is undesirable in
principle to place any limitation on TCP connection lifetimes.
H2) Do header prediction: if segment is next in sequence and We therefore require that an implementation of PAWS include a
if there are no special conditions requiring additional mechanism to "invalidate" the TS.Recent value when a connection is
processing, accept the segment, record its timestamp, and idle for more than 24 days. (An alternative solution to the problem
skip H3. of outdated timestamps would be to send keep-alive segments at a very
low rate, but still more often than the wrap-around time for
timestamps, e.g., once a day. This would impose negligible overhead.
However, the TCP specification has never included keep-alives, so the
solution based upon invalidation was chosen.)
H3) Process the segment normally, as specified in RFC 793. Note that a TCP does not know the frequency, and therefore, the
This includes dropping segments that are outside the wraparound time, of the other TCP, so it must assume the worst. The
window and possibly sending acknowledgments, and queueing validity of TS.Recent needs to be checked only if the basic PAWS
in-window, out-of-sequence segments. timestamp check fails, i.e., only if SEG.TSval < TS.Recent. If
TS.Recent is found to be invalid, then the segment is accepted,
regardless of the failure of the timestamp check, and rule R3 updates
TS.Recent with the TSval from the new segment.
Another possibility would be to interchange steps H1 and H2, To detect how long the connection has been idle, the TCP may update a
i.e., to perform the header prediction step H2 FIRST, and clock or timestamp value associated with the connection whenever
perform H1 and H3 only when header prediction fails. This TS.Recent is updated, for example. The details will be
could be a performance improvement, since the timestamp check implementation-dependent.
in step H1 is very unlikely to fail, and it requires unsigned
modulo arithmetic, 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 produce a measurable reduction in CPU time for TCP
protocol processing on high-speed networks.
However, putting H2 first would create a hazard: a segment from 4.2.4. Header Prediction
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.
If all segments are equally likely to show up as old "Header prediction" [Jacobson90a] is a high-performance transport
duplicates, then the probability of an old duplicate protocol implementation technique that is most important for high-
exactly matching the left window edge is the maximum speed links. This technique optimizes the code for the most common
segment size (MSS) divided by the size of the sequence case, receiving a segment correctly and in order. Using header
space. This ratio must be less than 2**-16, since MSS prediction, the receiver asks the question, "Is this segment the next
must be < 2**16; for example, it will be (2**12)/(2**32) = in sequence?" This question can be answered in fewer machine
2**-20 for an FDDI link. However, the older a segment is, instructions than the question, "Is this segment within the window?"
the less likely it is to be retained in the Internet, and
under any reasonable model of segment lifetime the
probability of an old duplicate exactly at the left window
edge must be much smaller than 2**-16.
The 16 bit TCP checksum also allows a basic unreliability Adding header prediction to our timestamp procedure leads to the
of one part in 2**16. A protocol mechanism whose following recommended sequence for processing an arriving TCP
reliability exceeds the reliability of the TCP checksum segment:
should be considered "good enough", i.e., it won't
contribute significantly to the overall error rate. We
therefore believe we can ignore the problem of an old
duplicate being accepted by doing header prediction before
checking the timestamp.
However, this probabilistic argument is not universally H1) Check timestamp (same as step R1 above)
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 H2 follow H1.
4.2.5 IP Fragmentation H2) 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 H3.
At high data rates, the protection against old packets provided H3) Process the segment normally, as specified in RFC 793. This
by PAWS can be circumvented by errors in IP fragment reassembly includes dropping segments that are outside the window and
[Heffner07]. The only way to protect against incorrect IP possibly sending acknowledgments, and queueing in-window, out-
fragment reassembly is to not allow the packets to be of-sequence segments.
fragmented. This is done by setting the Don't Fragment (DF)
bit in the IP header. Setting the DF bit implies the use of
Path MTU Discovery as described in RFC 1191 [Mogul90], thus any
TCP implementation that implements PAWS must also implement
Path MTU Discovery.
4.3. Duplicates from Earlier Incarnations of Connection Another possibility would be to interchange steps H1 and H2, i.e., to
The PAWS mechanism protects against errors due to sequence number perform the header prediction step H2 FIRST, and perform H1 and H3
wrap-around on high-speed connection. Segments from an earlier only when header prediction fails. This could be a performance
incarnation of the same connection are also a potential cause of improvement, since the timestamp check in step H1 is very unlikely to
old duplicate errors. In both cases, the TCP mechanisms to fail, and it requires unsigned modulo arithmetic, a relatively
prevent such errors depend upon the enforcement of a maximum expensive operation. To perform this check on every single segment
segment lifetime (MSL) by the Internet (IP) layer (see Appendix of is contrary to the philosophy of header prediction. We believe that
RFC 1185 for a detailed discussion). Unlike the case of sequence this change might produce a measurable reduction in CPU time for TCP
space wrap-around, the MSL required to prevent old duplicate protocol processing on high-speed networks.
errors from earlier incarnations does not depend upon the transfer
rate. If the IP layer enforces the recommended 2 minute MSL of
TCP, and if the TCP rules are followed, TCP connections will be
safe from earlier incarnations, no matter how high the network
speed. Thus, the PAWS mechanism is not required for this case.
We may still ask whether the PAWS mechanism can provide additional However, putting H2 first would create a hazard: a segment from 2^32
security against old duplicates from earlier connections, allowing bytes in the past might arrive at exactly the wrong time and be
us to relax the enforcement of MSL by the IP layer. Appendix B accepted mistakenly by the header-prediction step. The following
explores this question, showing that further assumptions and/or reasoning has been introduced in [RFC1185] to show that the
mechanisms are required, beyond those of PAWS. This is not part probability of this failure is negligible.
of the current extension.
5. CONCLUSIONS AND ACKNOWLEDGMENTS If all segments are equally likely to show up as old duplicates,
then the probability of an old duplicate exactly matching the left
window edge is the maximum segment size (MSS) divided by the size
of the sequence space. This ratio must be less than 2^-16, since
MSS must be < 2^16; for example, it will be (2^12)/(2^32) = 2^-20
for a FDDI link. However, the older a segment is, the less likely
it is to be retained in the Internet, and under any reasonable
model of segment lifetime the probability of an old duplicate
exactly at the left window edge must be much smaller than 2^-16.
The 16 bit TCP checksum also allows a basic unreliability of one
part in 2^16. A protocol mechanism whose reliability exceeds the
reliability of the TCP checksum should be considered "good
enough", i.e., it won't contribute significantly to the overall
error rate. We therefore believe we can ignore the problem of an
old duplicate being accepted by doing header prediction before
checking the timestamp.
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 H2 follow H1.
4.2.5. IP Fragmentation
At high data rates, the protection against old packets provided by
PAWS can be circumvented by errors in IP fragment reassembly (see
[RFC4963]). The only way to protect against incorrect IP fragment
reassembly is to not allow the packets to be fragmented. This is
done by setting the Don't Fragment (DF) bit in the IP header.
Setting the DF bit implies the use of Path MTU Discovery as described
in [RFC1191], thus any TCP implementation that implements PAWS must
also implement Path MTU Discovery.
4.3. Duplicates from Earlier Incarnations of Connection
The PAWS mechanism protects against errors due to sequence number
wrap-around on high-speed connection. Segments from an earlier
incarnation of the same connection are also a potential cause of old
duplicate errors. In both cases, the TCP mechanisms to prevent such
errors depend upon the enforcement of a maximum segment lifetime
(MSL) by the Internet (IP) layer (see Appendix of RFC 1185 for a
detailed discussion). Unlike the case of sequence space wrap-around,
the MSL required to prevent old duplicate errors from earlier
incarnations does not depend upon the transfer rate. If the IP layer
enforces the recommended 2 minute MSL of TCP, and if the TCP rules
are followed, TCP connections will be safe from earlier incarnations,
no matter how high the network speed. Thus, the PAWS mechanism is
not required for this case.
We may still ask whether the PAWS mechanism can provide additional
security against old duplicates from earlier connections, allowing us
to relax the enforcement of MSL by the IP layer. Appendix B explores
this question, showing that further assumptions and/or mechanisms are
required, beyond those of PAWS. This is not part of the current
extension.
5. Conclusions and Acknowledgements
This memo presented a set of extensions to TCP to provide efficient This memo presented a set of extensions to TCP to provide efficient
operation over large-bandwidth*delay-product paths and reliable operation over large-bandwidth*delay-product paths and reliable
operation over very high-speed paths. These extensions are designed operation over very high-speed paths. These extensions are designed
to provide compatible interworking with TCP's that do not implement to provide compatible interworking with TCP's that do not implement
the extensions. the extensions.
These mechanisms are implemented using new TCP options for scaled These mechanisms are implemented using new TCP options for scaled
windows and timestamps. The timestamps are used for two distinct windows and timestamps. The timestamps are used for two distinct
mechanisms: RTTM (Round Trip Time Measurement) and PAWS (Protect mechanisms: RTTM (Round Trip Time Measurement) and PAWS (Protect
skipping to change at page 27, line 6 skipping to change at page 28, line 10
within the End-to-End Task Force on the theoretical limitations of within the End-to-End Task Force on the theoretical limitations of
transport protocols in general and TCP in particular. Task force transport protocols in general and TCP in particular. Task force
members and other on the end2end-interest list have made valuable members and other on the end2end-interest list have made valuable
contributions by pointing out flaws in the algorithms and the contributions by pointing out flaws in the algorithms and the
documentation. Continued discussion and development since the documentation. Continued discussion and development since the
publication of RFC 1323 originally occurred in the IETF TCP Large publication of RFC 1323 originally occurred in the IETF TCP Large
Windows Working Group, later on in the End-to-End Task Force, and Windows Working Group, later on in the End-to-End Task Force, and
most recently in the IETF TCP Maintenance Working Group. The authors most recently in the IETF TCP Maintenance Working Group. The authors
are grateful for all these contributions. are grateful for all these contributions.
6. SECURITY CONSIDERATIONS 6. Security Considerations
The TCP sequence space is a fixed size, and as the window becomes The TCP sequence space is a fixed size, and as the window becomes
larger it becomes easier for an attacker to generate forged packets larger it becomes easier for an attacker to generate forged packets
that can fall within the TCP window, and be accepted as valid that can fall within the TCP window, and be accepted as valid
packets. While use of Timestamps and PAWS can help to mitigate this, packets. While use of Timestamps and PAWS can help to mitigate this,
when using PAWS, if an attacker is able to forge a packet that is when using PAWS, if an attacker is able to forge a packet that is
acceptable to the TCP connection, a timestamp that is in the future acceptable to the TCP connection, a timestamp that is in the future
would cause valid packets to be dropped due to PAWS checks. Hence, would cause valid packets to be dropped due to PAWS checks. Hence,
implementors should take care to not open the TCP window drastically implementors should take care to not open the TCP window drastically
beyond the requirements of the connection. beyond the requirements of the connection.
skipping to change at page 27, line 29 skipping to change at page 28, line 33
SYN, such as TSopt, a high speed connection that needs PAWS would not SYN, such as TSopt, a high speed connection that needs PAWS would not
have that protection. In this situation, an implementor could have that protection. In this situation, an implementor could
provide a mechanism for the application to determine whether or not provide a mechanism for the application to determine whether or not
PAWS is in use on the connection, and chose to terminate the PAWS is in use on the connection, and chose to terminate the
connection if that protection doesn't exist. connection if that protection doesn't exist.
Mechanisms to protect the TCP header from modification should also Mechanisms to protect the TCP header from modification should also
protect the TCP options. protect the TCP options.
Expanding the TCP window beyond 64K for IPv6 allows Jumbograms Expanding the TCP window beyond 64K for IPv6 allows Jumbograms
[Borman99] to be used when the local network supports packets larger [RFC2675] to be used when the local network supports packets larger
than 64K. When larger TCP packets are used, the TCP checksum becomes than 64K. When larger TCP packets are used, the TCP checksum becomes
weaker. weaker.
7. IANA CONSIDERATIONS 7. IANA Considerations
This document has no actions for IANA. This document has no actions for IANA.
8. REFERENCES 8. References
Normative References 8.1. Normative References
[Mogul90] Mojul, J. and Deering, S., "Path MTU Discovery", RFC [RFC0793] Postel, J., "Transmission Control Protocol", STD 7,
1191, November 1990. RFC 793, September 1981.
[Postel81] Postel, J., "Transmission Control Protocol - DARPA [RFC1191] Mogul, J. and S. Deering, "Path MTU discovery", RFC 1191,
Internet Program Protocol Specification", RFC 793, DARPA, November 1990.
September 1981.
Informative References 8.2. Informative References
[Allman99] Allman, M., Paxson, V., Stevens, W., "TCP Congestion [Garlick77]
Control", RFC 2581, NASA Glenn/Sterling Software, ACIRI / ICSI, Garlick, L., Rom, R., and J. Postel, "Issues in Reliable
April 1999. Host-to-Host Protocols", Proc. Second Berkeley Workshop on
Distributed Data Management and Computer Networks ,
May 1977, <http://www.rfc-editor.org/ien/ien12.txt>.
[Borman99] Borman, D., Deering, S., and Hinden, R, "IPv6 [Hamming77]
Jumbograms" RFC 2675, August 1999. Hamming, R., "Digital Filters", Prentice Hall, Englewood
Cliffs, N.J. ISBN 0-13-212571-4, 1977.
[Braden89] Braden, R., editor, "Requirements for Internet Hosts -- [Jacobson88a]
Communication Layers", RFC 1122, October, 1989 Jacobson, V., "Congestion Avoidance and Control", SIGCOMM
'88, Stanford, CA. , August 1988,
<http://ee.lbl.gov/papers/congavoid.pdf>.
[Floyd00] Floyd, S., Mahdavi, J., Mathis, M., Podolsky, M., "An [Jacobson90a]
Extension to the Selective Acknowledgement (SACK) Option for TCP", Jacobson, V., "4BSD Header Prediction", ACM Computer
RFC 2883, July 2000. Communication Review , April 1990.
[Blanton03] Blanton, E., Allman, M., Fall, K., Wang, L., "A [Jacobson90c]
Conservative Selective Acknowledgment (SACK)-based Loss Recovery Jacobson, V., "Modified TCP congestion avoidance
Algorithm for TCP", RFC 3517, April 2003. algorithm", Message to end2end-interest mailing list ,
April 1990,
<ftp://ftp.isi.edu/end2end/end2end-interest-1990.mail>.
[Garlick77] Garlick, L., R. Rom, and J. Postel, "Issues in [Jain86] Jain, R., "Divergence of Timeout Algorithms for Packet
Reliable Host-to-Host Protocols", Proc. Second Berkeley Workshop Retransmissions", Proc. Fifth Phoenix Conf. on Comp. and
on Distributed Data Management and Computer Networks, May 1977. Comm., Scottsdale, Arizona , March 1986,
<http://arxiv.org/ftp/cs/papers/9809/9809097.pdf>.
[Hamming77] Hamming, R., "Digital Filters", ISBN 0-13-212571-4, [Karn87] Karn, P. and C. Partridge, "Estimating Round-Trip Times in
Prentice Hall, Englewood Cliffs, N.J., 1977. Reliable Transport Protocols", Proc. SIGCOMM '87 ,
August 1987.
[Heffner07] Heffner, J., Mathis, M., and Chandler, B., "IPv4 [Martin03]
Reassembly Errors at High Data Rates" RFC 4963, PSC, July 2007. Martin, D., "[Tsvwg] RFC 1323.bis", Message to the tsvwg
mailing list , September 2003, <http://www.ietf.org/
mail-archive/web/tsvwg/current/msg04435.html>.
[Jacobson88a] Jacobson, V., "Congestion Avoidance and Control", [Mathis08]
SIGCOMM '88, Stanford, CA., August 1988. Mathis, M., "[tcpm] Example of 1323 window retraction
problemPer my comments at the microphone at TCPM...",
Message to the tcpm mailing list , March 2008, <http://
www.ietf.org/mail-archive/web/tcpm/current/msg03564.html>.
[Jacobson88b] Jacobson, V., and R. Braden, "TCP Extensions for [RFC0896] Nagle, J., "Congestion control in IP/TCP internetworks",
Long-Delay Paths", RFC 1072, LBL and USC/Information Sciences RFC 896, January 1984.
Institute, October 1988.
[Jacobson90a] Jacobson, V., "4BSD Header Prediction", ACM [RFC1072] Jacobson, V. and R. Braden, "TCP extensions for long-delay
Computer Communication Review, April 1990. paths", RFC 1072, October 1988.
[Jacobson90b] Jacobson, V., Braden, R., and Zhang, L., "TCP [RFC1110] McKenzie, A., "Problem with the TCP big window option",
Extension for High-Speed Paths", RFC 1185, LBL and USC/Information RFC 1110, August 1989.
Sciences Institute, October 1990.
[Jacobson90c] Jacobson, V., "Modified TCP congestion avoidance [RFC1122] Braden, R., "Requirements for Internet Hosts -
algorithm", Message to end2end-interest mailing list, April 1990. Communication Layers", STD 3, RFC 1122, October 1989.
[Jacobson92d] Jacobson, V., Braden, R., and Borman, D., "TCP [RFC1185] Jacobson, V., Braden, B., and L. Zhang, "TCP Extension for
Extension for High Performance", RFC 1323, LBL, USC/Information High-Speed Paths", RFC 1185, October 1990.
Sciences Institute and Cray Research, May 1992.
[Jain86] Jain, R., "Divergence of Timeout Algorithms for Packet [RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions
Retransmissions", Proc. Fifth Phoenix Conf. on Comp. and Comm., for High Performance", RFC 1323, May 1992.
Scottsdale, Arizona, March 1986.
[Karn87] Karn, P. and C. Partridge, "Estimating Round-Trip Times [RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP
in Reliable Transport Protocols", Proc. SIGCOMM '87, Stowe, VT, Selective Acknowledgment Options", RFC 2018, October 1996.
August 1987.
[Martin03] Martin, D., "[Tsvwg] RFC 1323.bis" Message to tsvwg [RFC2581] Allman, M., Paxson, V., and W. Stevens, "TCP Congestion
mailing list, September 30, 2003. Control", RFC 2581, April 1999.
[Mathis96] Mathis, M., Mahdavi, J., Floyd, S., and Romanow, A., [RFC2675] Borman, D., Deering, S., and R. Hinden, "IPv6 Jumbograms",
"TCP Selective Acknowledgment Options", RFC 2018, October, 1996. RFC 2675, August 1999.
[Mathis08] Mathis, M., "[tcpm] Example of 1323 window retraction [RFC2883] Floyd, S., Mahdavi, J., Mathis, M., and M. Podolsky, "An
problemPer my comments at the microphone at TCPM...", Message to Extension to the Selective Acknowledgement (SACK) Option
the tcpm mailing list, March 2008. for TCP", RFC 2883, July 2000.
[McKenzie89] McKenzie, A., "A Problem with the TCP Big Window [RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A
Option", RFC 1110, BBN STC, August 1989. Conservative Selective Acknowledgment (SACK)-based Loss
Recovery Algorithm for TCP", RFC 3517, April 2003.
[Nagle84] Nagle, J., "Congestion Control in IP/TCP [RFC4963] Heffner, J., Mathis, M., and B. Chandler, "IPv4 Reassembly
Internetworks", RFC 896, FACC, January 1984. Errors at High Data Rates", RFC 4963, July 2007.
[Watson81] Watson, R., "Timer-based Mechanisms in Reliable [RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion
Transport Protocol Connection Management", Computer Networks, Vol. Control", RFC 5681, September 2009.
5, 1981.
[Zhang86] Zhang, L., "Why TCP Timers Don't Work Well", Proc. [Watson81]
SIGCOMM '86, Stowe, Vt., August 1986. Watson, R., "Timer-based Mechanisms in Reliable Transport
Protocol Connection Management", Computer Networks, Vol.
5 , 1981.
APPENDIX A: IMPLEMENTATION SUGGESTIONS [Zhang86] Zhang, L., "Why TCP Timers Don't Work Well", Proc. SIGCOMM
'86, Stowe, VT , August 1986.
Appendix A. Implementation Suggestions
TCP Option Layout TCP Option Layout
The following layouts are recommended for sending options on The following layouts are recommended for sending options on non-
non-SYN segments, to achieve maximum feasible alignment of SYN segments, to achieve maximum feasible alignment of 32-bit and
32-bit and 64-bit machines. 64-bit machines.
+--------+--------+--------+--------+ +--------+--------+--------+--------+
| NOP | NOP | TSopt | 10 | | NOP | NOP | TSopt | 10 |
+--------+--------+--------+--------+ +--------+--------+--------+--------+
| TSval timestamp | | TSval timestamp |
+--------+--------+--------+--------+ +--------+--------+--------+--------+
| TSecr timestamp | | TSecr timestamp |
+--------+--------+--------+--------+ +--------+--------+--------+--------+
Interaction with the TCP Urgent Pointer Interaction with the TCP Urgent Pointer
The TCP Urgent pointer, like the TCP window, is a 16 bit value. The TCP Urgent pointer, like the TCP window, is a 16 bit value.
Some of the original discussion for the TCP Window Scale option Some of the original discussion for the TCP Window Scale option
included proposals to increase the Urgent pointer to 32 bits. included proposals to increase the Urgent pointer to 32 bits. As
As it turns out, this is unnecessary. There are two it turns out, this is unnecessary. There are two observations
observations that should be made: that should be made:
(1) With IP Version 4, the largest amount of TCP data that can (1) With IP Version 4, the largest amount of TCP data that can be
be sent in a single packet is 65495 bytes (64K - 1 - size sent in a single packet is 65495 bytes (64K - 1 - size of
of fixed IP and TCP headers). fixed IP and TCP headers).
(2) Updates to the urgent pointer while the user is in "urgent (2) Updates to the urgent pointer while the user is in "urgent
mode" are invisible to the user. mode" are invisible to the user.
This means that if the Urgent Pointer points beyond the end of This means that if the Urgent Pointer points beyond the end of the
the TCP data in the current packet, then the user will remain in TCP data in the current packet, then the user will remain in
urgent mode until the next TCP packet arrives. That packet will urgent mode until the next TCP packet arrives. That packet will
update the urgent pointer to a new offset, and the user will update the urgent pointer to a new offset, and the user will never
never have left urgent mode. have left urgent mode.
Thus, to properly implement the Urgent Pointer, the sending TCP Thus, to properly implement the Urgent Pointer, the sending TCP
only has to check for overflow of the 16 bit Urgent Pointer only has to check for overflow of the 16 bit Urgent Pointer field
field before filling it in. If it does overflow, than a value before filling it in. If it does overflow, than a value of 65535
of 65535 should be inserted into the Urgent Pointer. should be inserted into the Urgent Pointer.
The same technique applies to IP Version 6, except in the case The same technique applies to IP Version 6, except in the case of
of IPv6 Jumbograms. When IPv6 Jumbograms are supported, RFC IPv6 Jumbograms. When IPv6 Jumbograms are supported, [RFC2675]
2675 [Borman99] requires additional steps for dealing with the requires additional steps for dealing with the Urgent Pointer,
Urgent Pointer, these are described in section 5.2 of RFC 2675. these are described in section 5.2 of [RFC2675].
APPENDIX B: DUPLICATES FROM EARLIER CONNECTION INCARNATIONS Appendix B. Duplicates from Earlier Connection Incarnations
There are two cases to be considered: (1) a system crashing (and There are two cases to be considered: (1) a system crashing (and
losing connection state) and restarting, and (2) the same connection losing connection state) and restarting, and (2) the same connection
being closed and reopened without a loss of host state. These will being closed and reopened without a loss of host state. These will
be described in the following two sections. be described in the following two sections.
B.1 System Crash with Loss of State B.1. System Crash with Loss of State
TCP's quiet time of one MSL upon system startup handles the loss TCP's quiet time of one MSL upon system startup handles the loss of
of connection state in a system crash/restart. For an connection state in a system crash/restart. For an explanation, see
explanation, see for example "When to Keep Quiet" in the TCP for example "When to Keep Quiet" in the TCP protocol specification
protocol specification [Postel81]. The MSL that is required here [RFC0793]. The MSL that is required here does not depend upon the
does not depend upon the transfer speed. The current TCP MSL of 2 transfer speed. The current TCP MSL of 2 minutes seems acceptable as
minutes seems acceptable as an operational compromise, as many an operational compromise, as many host systems take this long to
host systems take this long to boot after a crash. boot after a crash.
However, the timestamp option may be used to ease the MSL However, the timestamp option may be used to ease the MSL
requirements (or to provide additional security against data requirements (or to provide additional security against data
corruption). If timestamps are being used and if the timestamp corruption). If timestamps are being used and if the timestamp clock
clock can be guaranteed to be monotonic over a system can be guaranteed to be monotonic over a system crash/restart, i.e.,
crash/restart, i.e., if the first value of the sender's timestamp if the first value of the sender's timestamp clock after a crash/
clock after a crash/restart can be guaranteed to be greater than restart can be guaranteed to be greater than the last value before
the last value before the restart, then a quiet time will be the restart, then a quiet time will be unnecessary.
unnecessary.
To dispense totally with the quiet time would require that the To dispense totally with the quiet time would require that the host
host clock be synchronized to a time source that is stable over clock be synchronized to a time source that is stable over the crash/
the crash/restart period, with an accuracy of one timestamp clock restart period, with an accuracy of one timestamp clock tick or
tick or better. We can back off from this strict requirement to better. We can back off from this strict requirement to take
take advantage of approximate clock synchronization. Suppose that advantage of approximate clock synchronization. Suppose that the
the clock is always re-synchronized to within N timestamp clock clock is always re-synchronized to within N timestamp clock ticks and
ticks and that booting (extended with a quiet time, if necessary) that booting (extended with a quiet time, if necessary) takes more
takes more than N ticks. This will guarantee monotonicity of the than N ticks. This will guarantee monotonicity of the timestamps,
timestamps, which can then be used to reject old duplicates even which can then be used to reject old duplicates even without an
without an enforced MSL. enforced MSL.
B.2 Closing and Reopening a Connection B.2. Closing and Reopening a Connection
When a TCP connection is closed, a delay of 2*MSL in TIME-WAIT When a TCP connection is closed, a delay of 2*MSL in TIME-WAIT state
state ties up the socket pair for 4 minutes (see Section 3.5 of ties up the socket pair for 4 minutes (see Section 3.5 of [RFC0793].
[Postel81]. Applications built upon TCP that close one connection Applications built upon TCP that close one connection and open a new
and open a new one (e.g., an FTP data transfer connection using one (e.g., an FTP data transfer connection using Stream mode) must
Stream mode) must choose a new socket pair each time. The TIME- choose a new socket pair each time. The TIME- WAIT delay serves two
WAIT delay serves two different purposes: different purposes:
(a) Implement the full-duplex reliable close handshake of TCP. (a) Implement the full-duplex reliable close handshake of TCP.
The proper time to delay the final close step is not really The proper time to delay the final close step is not really
related to the MSL; it depends instead upon the RTO for the related to the MSL; it depends instead upon the RTO for the FIN
FIN segments and therefore upon the RTT of the path. (It segments and therefore upon the RTT of the path. (It could be
could be argued that the side that is sending a FIN knows argued that the side that is sending a FIN knows what degree of
what degree of reliability it needs, and therefore it should reliability it needs, and therefore it should be able to
be able to determine the length of the TIME-WAIT delay for determine the length of the TIME-WAIT delay for the FIN's
the FIN's recipient. This could be accomplished with an recipient. This could be accomplished with an appropriate TCP
appropriate TCP option in FIN segments.) option in FIN segments.)
Although there is no formal upper-bound on RTT, common Although there is no formal upper-bound on RTT, common network
network engineering practice makes an RTT greater than 1 engineering practice makes an RTT greater than 1 minute very
minute very unlikely. Thus, the 4 minute delay in TIME-WAIT unlikely. Thus, the 4 minute delay in TIME-WAIT state works
state works satisfactorily to provide a reliable full-duplex satisfactorily to provide a reliable full-duplex TCP close.
TCP close. Note again that this is independent of MSL Note again that this is independent of MSL enforcement and
enforcement and network speed. network speed.
The TIME-WAIT state could cause an indirect performance The TIME-WAIT state could cause an indirect performance problem
problem if an application needed to repeatedly close one if an application needed to repeatedly close one connection and
connection and open another at a very high frequency, since open another at a very high frequency, since the number of
the number of available TCP ports on a host is less than available TCP ports on a host is less than 2^16. However, high
2**16. However, high network speeds are not the major network speeds are not the major contributor to this problem;
contributor to this problem; the RTT is the limiting factor the RTT is the limiting factor in how quickly connections can be
in how quickly connections can be opened and closed. opened and closed. Therefore, this problem will be no worse at
Therefore, this problem will be no worse at high transfer high transfer speeds.
speeds.
(b) Allow old duplicate segments to expire. (b) Allow old duplicate segments to expire.
To replace this function of TIME-WAIT state, a mechanism To replace this function of TIME-WAIT state, a mechanism would
would have to operate across connections. PAWS is defined have to operate across connections. PAWS is defined strictly
strictly within a single connection; the last timestamp within a single connection; the last timestamp (TS.Recent) is
(TS.Recent) is kept in the connection control block, and kept in the connection control block, and discarded when a
discarded when a connection is closed. connection is closed.
An additional mechanism could be added to the TCP, a per-host An additional mechanism could be added to the TCP, a per-host
cache of the last timestamp received from any connection. cache of the last timestamp received from any connection. This
This value could then be used in the PAWS mechanism to reject value could then be used in the PAWS mechanism to reject old
old duplicate segments from earlier incarnations of the duplicate segments from earlier incarnations of the connection,
connection, if the timestamp clock can be guaranteed to have if the timestamp clock can be guaranteed to have ticked at least
ticked at least once since the old connection was open. This once since the old connection was open. This would require that
would require that the TIME-WAIT delay plus the RTT together the TIME-WAIT delay plus the RTT together must be at least one
must be at least one tick of the sender's timestamp clock. tick of the sender's timestamp clock. Such an extension is not
Such an extension is not part of the proposal of this RFC. part of the proposal of this RFC.
Note that this is a variant on the mechanism proposed by Note that this is a variant on the mechanism proposed by
Garlick, Rom, and Postel [Garlick77], which required each Garlick, Rom, and Postel [Garlick77], which required each host
host to maintain connection records containing the highest to maintain connection records containing the highest sequence
sequence numbers on every connection. Using timestamps numbers on every connection. Using timestamps instead, it is
instead, it is only necessary to keep one quantity per remote only necessary to keep one quantity per remote host, regardless
host, regardless of the number of simultaneous connections to of the number of simultaneous connections to that host.
that host.
APPENDIX C: CHANGES FROM RFC 1072, RFC 1185, RFC 1323 Appendix C. Changes from RFC 1072, RFC 1185, and RFC 1323
The protocol extensions defined in RFC 1323 document differ in The protocol extensions defined in RFC 1323 document differ in
several important ways from those defined in RFC 1072 and RFC 1185. several important ways from those defined in RFC 1072 and RFC 1185.
(a) SACK has been split off into a separate document, RFC 2018 (a) SACK has been split off into a separate document, [RFC2018].
[Mathis96].
(b) The detailed rules for sending timestamp replies (see Section (b) The detailed rules for sending timestamp replies (see
3.4) differ in important ways. The earlier rules could result Section 3.4) differ in important ways. The earlier rules could
in an under-estimate of the RTT in certain cases (packets result in an under-estimate of the RTT in certain cases (packets
dropped or out of order). dropped or out of order).
(c) The same value TS.Recent is now shared by the two distinct (c) The same value TS.Recent is now shared by the two distinct
mechanisms RTTM and PAWS. This simplification became possible mechanisms RTTM and PAWS. This simplification became possible
because of change (b). because of change (b).
(d) An ambiguity in RFC 1185 was resolved in favor of putting (d) An ambiguity in RFC 1185 was resolved in favor of putting
timestamps on ACK as well as data segments. This supports the timestamps on ACK as well as data segments. This supports the
symmetry of the underlying TCP protocol. symmetry of the underlying TCP protocol.
skipping to change at page 35, line 10 skipping to change at page 35, line 15
(a) The description of which TSecr values can be used to update the (a) The description of which TSecr values can be used to update the
measured RTT has been clarified. Specifically, with Timestamps, measured RTT has been clarified. Specifically, with Timestamps,
the Karn algorithm [Karn87] is disabled. The Karn algorithm the Karn algorithm [Karn87] is disabled. The Karn algorithm
disables all RTT measurements during retransmission, since it is disables all RTT measurements during retransmission, since it is
ambiguous whether the ACK is is for the original packet, or the ambiguous whether the ACK is is for the original packet, or the
retransmitted packet. With Timestamps, that ambiguity is retransmitted packet. With Timestamps, that ambiguity is
removed since the TSecr in the ACK will contain the TSval from removed since the TSecr in the ACK will contain the TSval from
whichever data packet made it to the destination. whichever data packet made it to the destination.
(b) In RFC 1323, section 3.4, step (2) of the algorithm to control (b) In RFC1323, section 3.4, step (2) of the algorithm to control
which timestamp is echoed was incorrect in two regards: which timestamp is echoed was incorrect in two regards:
(1) It failed to update TSrecent for a retransmitted segment (1) It failed to update TSrecent for a retransmitted segment
that resulted from a lost ACK. that resulted from a lost ACK.
(2) It failed if SEG.LEN = 0. (2) It failed if SEG.LEN = 0.
In the new algorithm, the case of SEG.TSval = TSrecent is In the new algorithm, the case of SEG.TSval = TSrecent is
included for consistency with the PAWS test. included for consistency with the PAWS test.
skipping to change at page 35, line 36 skipping to change at page 35, line 41
(e) Appendix A has been expanded with information about the TCP MSS (e) Appendix A has been expanded with information about the TCP MSS
option and the TCP Urgent Pointer. option and the TCP Urgent Pointer.
(f) It is now recommended that Timestamps options be included in RST (f) It is now recommended that Timestamps options be included in RST
packets if the incoming packet contained a Timestamps option. packets if the incoming packet contained a Timestamps option.
(g) RST packets are explicitly excluded from PAWS processing. (g) RST packets are explicitly excluded from PAWS processing.
(h) Snd.TSoffset and Snd.TSclock variables have been added. (h) Snd.TSoffset and Snd.TSclock variables have been added.
Snd.TSoffset is the sum of my.TSclock and Snd.TSoffset. This Snd.TSclock is the sum of my.TSclock and Snd.TSoffset. This
allows the starting points for timestamps to be randomized on a allows the starting points for timestamps to be randomized on a
per-connection basis. Setting Snd.TSoffset to zero yields the per-connection basis. Setting Snd.TSoffset to zero yields the
same results as RFC 1323. same results as [RFC1323].
APPENDIX D: SUMMARY OF NOTATION (i) RTTM update processing explicitly excludes packets containing
SACK options. This addresses inflation of the RTT during
episodes of packet loss in both directions.
(j) In Section 3.2 the if-clause allowing sending of timestamps only
when received in a <SYN> or <SYN,ACK> was removed, to allow for
late timestamp negotiation.
(k) Section 2.4 was added describing the unavoidable window
retraction issue, and explicitly describing the mitigation steps
necessary.
Appendix D. Summary of Notation
The following notation has been used in this document. The following notation has been used in this document.
Options Options
WSopt: TCP Window Scale Option WSopt: TCP Window Scale Option
TSopt: TCP Timestamps Option TSopt: TCP Timestamps Option
Option Fields Option Fields
shift.cnt: Window scale byte in WSopt. shift.cnt: Window scale byte in WSopt
TSval: 32-bit Timestamp Value field in TSopt. TSval: 32-bit Timestamp Value field in TSopt
TSecr: 32-bit Timestamp Reply field in TSopt. TSecr: 32-bit Timestamp Reply field in TSopt
Option Fields in Current Segment Option Fields in Current Segment
SEG.TSval: TSval field from TSopt in current segment. SEG.TSval: TSval field from TSopt in current segment
SEG.TSecr: TSecr field from TSopt in current segment. SEG.TSecr: TSecr field from TSopt in current segment
SEG.WSopt: 8-bit value in WSopt SEG.WSopt: 8-bit value in WSopt
Clock Values Clock Values
my.TSclock: System wide source of 32-bit timestamp values my.TSclock: System wide source of 32-bit timestamp values
my.TSclock.rate: Period of my.TSclock (1 ms to 1 sec). my.TSclock.rate: Period of my.TSclock (1 ms to 1 sec)
Snd.TSoffset: A offset for randomizing Snd.TSclock Snd.TSoffset: A offset for randomizing Snd.TSclock
Snd.TSclock: my.TSclock + Snd.TSoffset Snd.TSclock: my.TSclock + Snd.TSoffset
Per-Connection State Variables Per-Connection State Variables
TS.Recent: Latest received Timestamp TS.Recent: Latest received Timestamp
Last.ACK.sent: Last ACK field sent Last.ACK.sent: Last ACK field sent
Snd.TS.OK: 1-bit flag
Snd.TS.OK: 1-bit flag Snd.WS.OK: 1-bit flag
Snd.WS.OK: 1-bit flag Rcv.Wind.Scale: Receive window scale power
Snd.Wind.Scale: Send window scale power
Rcv.Wind.Scale: Receive window scale power Start.Time: Snd.TSclock value when segment being timed was
Snd.Wind.Scale: Send window scale power sent (used by pre-1323 code).
Start.Time: Snd.TSclock value when segment being
timed was sent (used by pre-1323 code).
Procedure Procedure
Update_SRTT( m ) Procedure to update the smoothed RTT and RTT Update_SRTT(m) Procedure to update the smoothed RTT and RTT
variance estimates, using the rules of variance estimates, using the rules of
[Jacobson88a], given m, a new RTT measurement. [Jacobson88a], given m, a new RTT measurement
APPENDIX E: PSEUDO-CODE SUMMARY Appendix E. Pseudo-code Summary
Create new TCB => { Create new TCB => {
Rcv.wind.scale = Rcv.wind.scale =
MIN( 14, MAX(0, floor(log2(receive buffer space)) - 15) ); MIN( 14, MAX(0, floor(log2(receive buffer space)) - 15) );
Snd.wind.scale = 0; Snd.wind.scale = 0;
Last.ACK.sent = 0; Last.ACK.sent = 0;
Snd.TS.OK = Snd.WS.OK = FALSE; Snd.TS.OK = Snd.WS.OK = FALSE;
Snd.TSoffset = random 32 bit value Snd.TSoffset = random 32 bit value
} }
Send initial {SYN} segment => { Send initial <SYN> segment => {
SEG.WND = MIN( RCV.WND, 65535 ); SEG.WND = MIN( RCV.WND, 65535 );
Include in segment: TSopt(TSval=Snd.TSclock, TCecr=0); Include in segment: TSopt(TSval=Snd.TSclock, TCecr=0);
Include in segment: WSopt = Rcv.wind.scale; Include in segment: WSopt = Rcv.wind.scale;
} }
Send {SYN, ACK} segment => { Send <SYN,ACK> segment => {
SEG.ACK = Last.ACK.sent = RCV.NXT; SEG.ACK = Last.ACK.sent = RCV.NXT;
SEG.WND = MIN( RCV.WND, 65535 ); SEG.WND = MIN( RCV.WND, 65535 );
if (Snd.TS.OK) then if (Snd.TS.OK) then
Include in segment: Include in segment:
TSopt(TSval=Snd.TSclock, TSecr=TS.Recent); TSopt(TSval=Snd.TSclock, TSecr=TS.Recent);
if (Snd.WS.OK) then if (Snd.WS.OK) then
Include in segment: WSopt = Rcv.wind.scale; Include in segment: WSopt = Rcv.wind.scale;
} }
Receive {SYN} or {SYN,ACK} segment => { Receive <SYN> or <SYN,ACK> segment => {
if (Segment contains TSopt) then { if (Segment contains TSopt) then {
TS.Recent = SEG.TSval; TS.Recent = SEG.TSval;
Snd.TS.OK = TRUE; Snd.TS.OK = TRUE;
if (is {SYN,ACK} segment) then if (is <SYN,ACK> segment) then
Update_SRTT( Update_SRTT(
(Snd.TSclock - SEG.TSecr)/my.TSclock.rate); (Snd.TSclock - SEG.TSecr)/my.TSclock.rate);
} }
if (Segment contains WSopt) then { if (Segment contains WSopt) then {
Snd.wind.scale = SEG.WSopt; Snd.wind.scale = SEG.WSopt;
Snd.WS.OK = TRUE; Snd.WS.OK = TRUE;
if (the ACK bit is not set, and Rcv.wind.scale has not been if (the ACK bit is not set, and Rcv.wind.scale has not been
initialized by the user) then initialized by the user) then
Rcv.wind.scale = Snd.wind.scale; Rcv.wind.scale = Snd.wind.scale;
} }
else else
Rcv.wind.scale = Snd.wind.scale = 0; Rcv.wind.scale = Snd.wind.scale = 0;
} }
skipping to change at page 38, line 49 skipping to change at page 39, line 4
if (SEG.ACK > SND.UNA) then { if (SEG.ACK > SND.UNA) then {
/* (At least part of) first segment in /* (At least part of) first segment in
* retransmission queue has been ACKd * retransmission queue has been ACKd
*/ */
if (Segment contains TSopt) then if (Segment contains TSopt) then
Update_SRTT( Update_SRTT(
(Snd.TSclock - SEG.TSecr)/my.TSclock.rate); (Snd.TSclock - SEG.TSecr)/my.TSclock.rate);
else else
Update_SRTT( /* for compatibility */ Update_SRTT( /* for compatibility */
(Snd.TSclock - Start.Time)/my.TSclock.rate); (Snd.TSclock - Start.Time)/my.TSclock.rate);
} }
} }
APPENDIX F: EVENT PROCESSING SUMMARY Appendix F. Event Processing Summary
Event Processing OPEN Call
OPEN Call ...
... An initial send sequence number (ISS) is selected. Send a SYN
An initial send sequence number (ISS) is selected. Send a SYN segment of the form:
segment of the form:
<SEQ=ISS><CTL=SYN><TSval=Snd.TSclock><WSopt=Rcv.Wind.Scale> <SEQ=ISS><CTL=SYN><TSval=Snd.TSclock><WSopt=Rcv.Wind.Scale>
... ...
SEND Call SEND Call
CLOSED STATE (i.e., TCB does not exist) CLOSED STATE (i.e., TCB does not exist)
... ...
LISTEN STATE LISTEN STATE
If the foreign socket is specified, then change the connection If the foreign socket is specified, then change the connection
from passive to active, select an ISS. Send a SYN segment from passive to active, select an ISS. Send a SYN segment
containing the options: <TSval=Snd.TSclock> and containing the options: <TSval=Snd.TSclock> and
<WSopt=Rcv.Wind.Scale>. Set SND.UNA to ISS, SND.NXT to ISS+1. <WSopt=Rcv.Wind.Scale>. Set SND.UNA to ISS, SND.NXT to ISS+1.
Enter SYN-SENT state. ... Enter SYN-SENT state. ...
SYN-SENT STATE SYN-SENT STATE
SYN-RECEIVED STATE SYN-RECEIVED STATE
... ...
ESTABLISHED STATE ESTABLISHED STATE
CLOSE-WAIT STATE CLOSE-WAIT STATE
Segmentize the buffer and send it with a piggybacked Segmentize the buffer and send it with a piggybacked
acknowledgment (acknowledgment value = RCV.NXT). ... acknowledgment (acknowledgment value = RCV.NXT). ...
If the urgent flag is set ... If the urgent flag is set ...
If the Snd.TS.OK flag is set, then include the TCP Timestamps If the Snd.TS.OK flag is set, then include the TCP Timestamps
option <TSval=Snd.TSclock,TSecr=TS.Recent> in each data segment. option <TSval=Snd.TSclock,TSecr=TS.Recent> in each data
segment.
Scale the receive window for transmission in the segment header: Scale the receive window for transmission in the segment
header:
SEG.WND = (RCV.WND >> Rcv.Wind.Scale). SEG.WND = (RCV.WND >> Rcv.Wind.Scale).
SEGMENT ARRIVES SEGMENT ARRIVES
... ...
If the state is LISTEN then If the state is LISTEN then
first check for an RST first check for an RST
... ...
second check for an ACK second check for an ACK
... ...
third check for a SYN third check for a SYN
if the SYN bit is set, check the security. If the ... if the SYN bit is set, check the security. If the ...
... ...
If the SEG.PRC is less than the TCB.PRC then continue. if the SEG.PRC is less than the TCB.PRC then continue.
Check for a Window Scale option (WSopt); if one is found, save Check for a Window Scale option (WSopt); if one is found,
SEG.WSopt in Snd.Wind.Scale and set Snd.WS.OK flag on. save SEG.WSopt in Snd.Wind.Scale and set Snd.WS.OK flag on.
Otherwise, set both Snd.Wind.Scale and Rcv.Wind.Scale to zero Otherwise, set both Snd.Wind.Scale and Rcv.Wind.Scale to
and clear Snd.WS.OK flag. zero and clear Snd.WS.OK flag.
Check for a TSopt option; if one is found, save SEG.TSval in the Check for a TSopt option; if one is found, save SEG.TSval in
variable TS.Recent and turn on the Snd.TS.OK bit. the variable TS.Recent and turn on the Snd.TS.OK bit.
Set RCV.NXT to SEG.SEQ+1, IRS is set to SEG.SEQ and any other Set RCV.NXT to SEG.SEQ+1, IRS is set to SEG.SEQ and any
control or text should be queued for processing later. ISS other control or text should be queued for processing later.
should be selected and a SYN segment sent of the form: ISS should be selected and a SYN segment sent of the form:
<SEQ=ISS><ACK=RCV.NXT><CTL=SYN,ACK> <SEQ=ISS><ACK=RCV.NXT><CTL=SYN,ACK>
If the Snd.WS.OK bit is on, include a WSopt option If the Snd.WS.OK bit is on, include a WSopt option
<WSopt=Rcv.Wind.Scale> in this segment. If the Snd.TS.OK bit is <WSopt=Rcv.Wind.Scale> in this segment. If the Snd.TS.OK
on, include a TSopt <TSval=Snd.TSclock,TSecr=TS.Recent> in this bit is on, include a TSopt
segment. Last.ACK.sent is set to RCV.NXT. <TSval=Snd.TSclock,TSecr=TS.Recent> in this segment.
Last.ACK.sent is set to RCV.NXT.
SND.NXT is set to ISS+1 and SND.UNA to ISS. The connection SND.NXT is set to ISS+1 and SND.UNA to ISS. The connection
state should be changed to SYN-RECEIVED. Note that any other state should be changed to SYN-RECEIVED. Note that any
incoming control or data (combined with SYN) will be processed other incoming control or data (combined with SYN) will be
in the SYN-RECEIVED state, but processing of SYN and ACK should processed in the SYN-RECEIVED state, but processing of SYN
not be repeated. If the listen was not fully specified (i.e., and ACK should not be repeated. If the listen was not fully
the foreign socket was not fully specified), then the specified (i.e., the foreign socket was not fully
unspecified fields should be filled in now. specified), then the unspecified fields should be filled in
now.
fourth other text or control fourth other text or control
...
If the state is SYN-SENT then ...
first check the ACK bit If the state is SYN-SENT then
... first check the ACK bit
fourth check the SYN bit ...
... ...
If the SYN bit is on and the security/compartment and precedence fourth check the SYN bit
are acceptable then, RCV.NXT is set to SEG.SEQ+1, IRS is set to
SEG.SEQ, and any acknowledgements on the retransmission queue
which are thereby acknowledged should be removed.
Check for a Window Scale option (WSopt); if is found, save ...
SEG.WSopt in Snd.Wind.Scale; otherwise, set both Snd.Wind.Scale
and Rcv.Wind.Scale to zero.
Check for a TSopt option; if one is found, save SEG.TSval in If the SYN bit is on and the security/compartment and
variable TS.Recent and turn on the Snd.TS.OK bit in the precedence are acceptable then, RCV.NXT is set to SEG.SEQ+1,
connection control block. If the ACK bit is set, use IRS is set to SEG.SEQ, and any acknowledgements on the
Snd.TSclock - SEG.TSecr as the initial RTT estimate. retransmission queue which are thereby acknowledged should
be removed.
If SND.UNA > ISS (our SYN has been ACKed), change the connection Check for a Window Scale option (WSopt); if it is found,
state to ESTABLISHED, form an ACK segment: save SEG.WSopt in Snd.Wind.Scale; otherwise, set both
Snd.Wind.Scale and Rcv.Wind.Scale to zero.
<SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK> Check for a TSopt option; if one is found, save SEG.TSval in
variable TS.Recent and turn on the Snd.TS.OK bit in the
connection control block. If the ACK bit is set, use
Snd.TSclock - SEG.TSecr as the initial RTT estimate.
and send it. If the Snd.Echo.OK bit is on, include a TSopt If SND.UNA > ISS (our SYN has been ACKed), change the
option <TSval=Snd.TSclock,TSecr=TS.Recent> in this ACK segment. connection state to ESTABLISHED, form an ACK segment:
Last.ACK.sent is set to RCV.NXT.
Data or controls which were queued for transmission may be <SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK>
included. If there are other controls or text in the segment
then continue processing at the sixth step below where the URG
bit is checked, otherwise return.
Otherwise enter SYN-RECEIVED, form a SYN,ACK segment: and send it. If the Snd.Echo.OK bit is on, include a TSopt
option <TSval=Snd.TSclock,TSecr=TS.Recent> in this ACK
segment. Last.ACK.sent is set to RCV.NXT.
<SEQ=ISS><ACK=RCV.NXT><CTL=SYN,ACK> Data or controls which were queued for transmission may be
included. If there are other controls or text in the
segment then continue processing at the sixth step below
where the URG bit is checked, otherwise return.
and send it. If the Snd.Echo.OK bit is on, include a TSopt Otherwise enter SYN-RECEIVED, form a SYN,ACK segment:
option <TSval=Snd.TSclock,TSecr=TS.Recent> in this segment. If
the Snd.WS.OK bit is on, include a WSopt option
<WSopt=Rcv.Wind.Scale> in this segment. Last.ACK.sent is set to
RCV.NXT.
If there are other controls or text in the segment, queue them <SEQ=ISS><ACK=RCV.NXT><CTL=SYN,ACK>
for processing after the ESTABLISHED state has been reached,
return.
fifth, if neither of the SYN or RST bits is set then drop the and send it. If the Snd.Echo.OK bit is on, include a TSopt
segment and return. option <TSval=Snd.TSclock,TSecr=TS.Recent> in this segment.
If the Snd.WS.OK bit is on, include a WSopt option
<WSopt=Rcv.Wind.Scale> in this segment. Last.ACK.sent is
set to RCV.NXT.
Otherwise, If there are other controls or text in the segment, queue
them for processing after the ESTABLISHED state has been
reached, return.
First, check sequence number fifth, if neither of the SYN or RST bits is set then drop the
segment and return.
SYN-RECEIVED STATE Otherwise,
ESTABLISHED STATE
FIN-WAIT-1 STATE
FIN-WAIT-2 STATE
CLOSE-WAIT STATE
CLOSING STATE
LAST-ACK STATE
TIME-WAIT STATE
Segments are processed in sequence. Initial tests on arrival First, check sequence number
are used to discard old duplicates, but further processing is
done in SEG.SEQ order. If a segment's contents straddle the
boundary between old and new, only the new parts should be
processed.
Rescale the received window field: SYN-RECEIVED STATE
ESTABLISHED STATE
FIN-WAIT-1 STATE
FIN-WAIT-2 STATE
CLOSE-WAIT STATE
CLOSING STATE
LAST-ACK STATE
TIME-WAIT STATE
TrueWindow = SEG.WND << Snd.Wind.Scale, Segments are processed in sequence. Initial tests on
arrival are used to discard old duplicates, but further
processing is done in SEG.SEQ order. If a segment's
contents straddle the boundary between old and new, only the
new parts should be processed.
and use "TrueWindow" in place of SEG.WND in the following steps. Rescale the received window field:
Check whether the segment contains a Timestamps option and bit TrueWindow = SEG.WND << Snd.Wind.Scale,
Snd.TS.OK is on. If so:
If SEG.TSval < TS.Recent and the RST bit is off, then test and use "TrueWindow" in place of SEG.WND in the following
whether connection has been idle less than 24 days; if all are steps.
true, then the segment is not acceptable; follow steps below
for an unacceptable segment.
If SEG.SEQ is equal to Last.ACK.sent, then save SEG.ECopt in Check whether the segment contains a Timestamps option and
variable TS.Recent. bit Snd.TS.OK is on. If so:
There are four cases for the acceptability test for an incoming If SEG.TSval < TS.Recent and the RST bit is off, then
segment: test whether connection has been idle less than 24 days;
if all are true, then the segment is not acceptable;
follow steps below for an unacceptable segment.
... If SEG.SEQ is equal to Last.ACK.sent, then save SEG.TSval
in variable TS.Recent.
If an incoming segment is not acceptable, an acknowledgment There are four cases for the acceptability test for an
should be sent in reply (unless the RST bit is set, if so drop incoming segment:
the segment and return):
<SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK> ...
Last.ACK.sent is set to SEG.ACK of the acknowledgment. If the If an incoming segment is not acceptable, an acknowledgment
Snd.Echo.OK bit is on, include the Timestamps option should be sent in reply (unless the RST bit is set, if so
<TSval=Snd.TSclock,TSecr=TS.Recent> in this ACK segment. Set drop the segment and return):
Last.ACK.sent to SEG.ACK and send the ACK segment. After
sending the acknowledgment, drop the unacceptable segment and
return.
... <SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK>
fifth check the ACK field. Last.ACK.sent is set to SEG.ACK of the acknowledgment. If
the Snd.Echo.OK bit is on, include the Timestamps option
<TSval=Snd.TSclock,TSecr=TS.Recent> in this ACK segment.
Set Last.ACK.sent to SEG.ACK and send the ACK segment.
After sending the acknowledgment, drop the unacceptable
segment and return.
if the ACK bit is off drop the segment and return. ...
if the ACK bit is on fifth check the ACK field.
... if the ACK bit is off drop the segment and return.
ESTABLISHED STATE if the ACK bit is on
If SND.UNA < SEG.ACK =< SND.NXT then, set SND.UNA <- SEG.ACK. ...
Also compute a new estimate of round-trip time. If Snd.TS.OK
bit is on, use Snd.TSclock - SEG.TSecr; otherwise use the
elapsed time since the first segment in the retransmission
queue was sent. Any segments on the retransmission queue
which are thereby entirely acknowledged...
... ESTABLISHED STATE
Seventh, process the segment text. If SND.UNA < SEG.ACK <= SND.NXT then, set SND.UNA <-
SEG.ACK. Also compute a new estimate of round-trip time.
If Snd.TS.OK bit is on, use Snd.TSclock - SEG.TSecr;
otherwise use the elapsed time since the first segment in
the retransmission queue was sent. Any segments on the
retransmission queue which are thereby entirely
acknowledged...
ESTABLISHED STATE ...
FIN-WAIT-1 STATE
FIN-WAIT-2 STATE
... Seventh, process the segment text.
Send an acknowledgment of the form: ESTABLISHED STATE
FIN-WAIT-1 STATE
FIN-WAIT-2 STATE
<SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK> ...
If the Snd.TS.OK bit is on, include Timestamps option Send an acknowledgment of the form:
<TSval=Snd.TSclock,TSecr=TS.Recent> in this ACK segment. Set
Last.ACK.sent to SEG.ACK of the acknowledgment, and send it.
This acknowledgment should be piggy-backed on a segment being
transmitted if possible without incurring undue delay.
... <SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK>
APPENDIX G: Timestamps Edge Cases If the Snd.TS.OK bit is on, include Timestamps option
<TSval=Snd.TSclock,TSecr=TS.Recent> in this ACK segment.
Set Last.ACK.sent to SEG.ACK of the acknowledgment, and send
it. This acknowledgment should be piggy-backed on a segment
being transmitted if possible without incurring undue delay.
...
Appendix G. Timestamps Edge Cases
While the rules laid out for when to calculate RTTM produce the While the rules laid out for when to calculate RTTM produce the
correct results most of the time, there are some edge cases where an correct results most of the time, there are some edge cases where an
incorrect RTTM can be calculated. All of these situations involve incorrect RTTM can be calculated. All of these situations involve
the loss of packets. It is felt that these scenarios are rare, and the loss of packets. It is felt that these scenarios are rare, and
that if they should happen, they will cause a single RTTM measurement that if they should happen, they will cause a single RTTM measurement
to be inflated, which mitigates its effects on RTO calculations. to be inflated, which mitigates its effects on RTO calculations.
[Martin03] cites two similar cases when the returning ACK is lost, [Martin03] cites two similar cases when the returning ACK is lost,
and before the retransmission timer fires, another returning packet and before the retransmission timer fires, another returning packet
arrives, which ACKs the data. In this case, the RTTM calculated will arrives, which ACKs the data. In this case, the RTTM calculated will
be inflated: be inflated:
clock clock
tc=1 <A, TSval=1> -------------------> tc=1 <A, TSval=1> ------------------->
tc=2 (lost) <---- <ACK(A), TSecr=1, win=n> tc=2 (lost) <---- <ACK(A), TSecr=1, win=n>
(RTTM would have been 1) (RTTM would have been 1)
(receive window opens, window update is sent) (receive window opens, window update is sent)
tc=5 <---- <ACK(A), TSecr=1, win=m> tc=5 <---- <ACK(A), TSecr=1, win=m>
(RTTM is calculated at 4) (RTTM is calculated at 4)
One thing to note about this situation is that it is somewhat bounded One thing to note about this situation is that it is somewhat bounded
by RTO + RTT, limiting how far off the RTTM calculation will be. by RTO + RTT, limiting how far off the RTTM calculation will be.
While more complex scenarios can be constructed that produce larger While more complex scenarios can be constructed that produce larger
inflations (e.g., retransmissions are lost), those scenarios involve inflations (e.g., retransmissions are lost), those scenarios involve
multiple packet losses, and the connection will have other more multiple packet losses, and the connection will have other more
serious operational problems than using an inflated RTTM in the RTO serious operational problems than using an inflated RTTM in the RTO
calculation. ------------- calculation.
Authors' Addresses Authors' Addresses
David Borman David Borman
Wind River Systems Quantum Corporation
Mendota Heights, MN 55120 Mendota Heights MN 55120
USA
Phone: (651) 454-3052 Email: david.borman@quantum.com
Email: david.borman@windriver.com
Bob Braden Bob Braden
University of Southern California University of Southern California
Information Sciences Institute
4676 Admiralty Way 4676 Admiralty Way
Marina del Rey, CA 90292 Marina del Rey CA 90292
USA
Phone: (310) 448-9173 Email: braden@isi.edu
EMail: Braden@ISI.EDU
Van Jacobson Van Jacobson
Packet Design Packet Design
2465 Latham Street 2465 Latham Street
Mountain View, CA 94040 Mountain View CA 94040
USA
EMail: van@packetdesign.com Email: van@packetdesign.com
Richard Scheffenegger (editor)
NetApp, Inc.
Am Euro Platz 2
Vienna, 1120
Austria
Email: rs@netapp.com
 End of changes. 386 change blocks. 
1398 lines changed or deleted 1411 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/