idnits 2.17.1 draft-ietf-tcpm-1323bis-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 19. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 2078. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2089. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2096. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2102. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 5 instances of too long lines in the document, the longest one being 3 characters in excess of 72. ** The abstract seems to contain references ([Jacobson92d]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. -- The draft header indicates that this document obsoletes RFC1323, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == Line 261 has weird spacing: '...its/sec byt...' == Line 1350 has weird spacing: '... TSval times...' == Line 1352 has weird spacing: '... TSecr times...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (January 29, 2008) is 5903 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '1' on line 288 ** Obsolete normative reference: RFC 793 (ref. 'Postel81') (Obsoleted by RFC 9293) -- Obsolete informational reference (is this intentional?): RFC 2581 (ref. 'Allman99') (Obsoleted by RFC 5681) -- Obsolete informational reference (is this intentional?): RFC 3517 (ref. 'Blanton03') (Obsoleted by RFC 6675) -- Obsolete informational reference (is this intentional?): RFC 1072 (ref. 'Jacobson88b') (Obsoleted by RFC 1323, RFC 2018, RFC 6247) -- Obsolete informational reference (is this intentional?): RFC 1185 (ref. 'Jacobson90b') (Obsoleted by RFC 1323) -- Obsolete informational reference (is this intentional?): RFC 1323 (ref. 'Jacobson92d') (Obsoleted by RFC 7323) -- Duplicate reference: RFC1323, mentioned in 'Martin03', was also mentioned in 'Jacobson92d'. -- Obsolete informational reference (is this intentional?): RFC 1323 (ref. 'Martin03') (Obsoleted by RFC 7323) -- Obsolete informational reference (is this intentional?): RFC 1110 (ref. 'McKenzie89') (Obsoleted by RFC 6247) -- Obsolete informational reference (is this intentional?): RFC 896 (ref. 'Nagle84') (Obsoleted by RFC 7805) -- Obsolete informational reference (is this intentional?): RFC 879 (ref. 'Postel83') (Obsoleted by RFC 7805, RFC 9293) Summary: 5 errors (**), 0 flaws (~~), 5 warnings (==), 20 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Network Working Group 3 Internet-Draft D. Borman 4 Obsoletes: 1323 Wind River Systems 5 File: draft-ietf-tcpm-1323bis-00.txt R. Braden 6 ISI 7 V. Jacobson 8 Packet Design 9 January 29, 2008 11 TCP Extensions for High Performance 13 Status of This Memo 15 By submitting this Internet-Draft, each author represents that 16 any applicable patent or other IPR claims of which he or she is 17 aware have been or will be disclosed, and any of which he or she 18 becomes aware will be disclosed, in accordance with Section 6 of 19 BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that 23 other groups may also distribute working documents as Internet- 24 Drafts. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/1id-abstracts.html 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html 37 This Internet-Draftw will expire on July 29, 2008. 39 Copyright 41 Copyright (C) The IETF Trust (2008). 43 Abstract 45 This memo presents a set of TCP extensions to improve performance 46 over large bandwidth*delay product paths and to provide reliable 47 operation over very high-speed paths. It defines new TCP options for 48 scaled windows and timestamps, which are designed to provide 49 compatible interworking with TCP's that do not implement the 50 extensions. The timestamps are used for two distinct mechanisms: 51 RTTM (Round Trip Time Measurement) and PAWS (Protect Against Wrapped 52 Sequences). Selective acknowledgments are not included in this memo. 54 This memo updates and obsoletes RFC-1323 [Jacobson92d]. 56 TABLE OF CONTENTS 58 1. Introduction 2 59 2. TCP Window Scale Option 8 60 3. RTTM -- Round-Trip Time Measurement 11 61 4. PAWS -- Protect Against Wrapped Sequence Numbers 17 62 5. Conclusions and Acknowledgments 25 63 6. Security Considerations 26 64 7. References 26 65 APPENDIX A: Implementation Suggestions 29 66 APPENDIX B: Duplicates from Earlier Connection Incarnations 30 67 APPENDIX C: Changes from RFC-1072, RFC-1185, RFC-1323 33 68 APPENDIX D: Summary of Notation 35 69 APPENDIX E: Pseudo-code Summary 36 70 APPENDIX F: Event Processing 38 71 APPENDIX G: Timestamps Edge Cases 44 72 Authors' Addresses 44 74 1. INTRODUCTION 76 The TCP protocol [Postel81] was designed to operate reliably over 77 almost any transmission medium regardless of transmission rate, 78 delay, corruption, duplication, or reordering of segments. 79 Production TCP implementations currently adapt to transfer rates in 80 the range of 100 bps to 10**10 bps and round-trip delays in the range 81 1 ms to 100 seconds. Work on TCP performance has shown that TCP can 82 work well over a variety of Internet paths, ranging from 800 Mbit/sec 83 I/O channels to 300 bit/sec dial-up modems [Jacobson88a]. 85 Over the years, advances in networking technology has resulted in 86 ever-higher transmission speeds, and the fastest paths are well 87 beyond the domain for which TCP was originally engineered. This memo 88 defines a set of modest extensions to TCP to extend the domain of its 89 application to match this increasing network capability. It is an 90 update to and obsoletes RFC-1323 [Jacobson92d], which in turn is 91 based upon and obsoletes RFC-1072 [Jacobson88b] and RFC-1185 92 [Jacobson90b]. 94 There is no one-line answer to the question: "How fast can TCP go?". 96 There are two separate kinds of issues, performance and reliability, 97 and each depends upon different parameters. We discuss each in turn. 99 1.1 TCP Performance 101 TCP performance depends not upon the transfer rate itself, but 102 rather upon the product of the transfer rate and the round-trip 103 delay. This "bandwidth*delay product" measures the amount of data 104 that would "fill the pipe"; it is the buffer space required at 105 sender and receiver to obtain maximum throughput on the TCP 106 connection over the path, i.e., the amount of unacknowledged data 107 that TCP must handle in order to keep the pipeline full. TCP 108 performance problems arise when the bandwidth*delay product is 109 large. We refer to an Internet path operating in this region as a 110 "long, fat pipe", and a network containing this path as an "LFN" 111 (pronounced "elephan(t)"). 113 High-capacity packet satellite channels (e.g., DARPA's Wideband 114 Net) are LFN's. For example, a DS1-speed satellite channel has a 115 bandwidth*delay product of 10**6 bits or more; this corresponds to 116 100 outstanding TCP segments of 1200 bytes each. Terrestrial 117 fiber-optical paths will also fall into the LFN class; for 118 example, a cross-country delay of 30 ms at a DS3 bandwidth 119 (45Mbps) also exceeds 10**6 bits. 121 There are three fundamental performance problems with the current 122 TCP over LFN paths: 124 (1) Window Size Limit 126 The TCP header uses a 16 bit field to report the receive 127 window size to the sender. Therefore, the largest window 128 that can be used is 2**16 = 65K bytes. 130 To circumvent this problem, Section 2 of this memo defines a 131 new TCP option, "Window Scale", to allow windows larger than 132 2**16. This option defines an implicit scale factor, which 133 is used to multiply the window size value found in a TCP 134 header to obtain the true window size. 136 (2) Recovery from Losses 138 Packet losses in an LFN can have a catastrophic effect on 139 throughput. In the past, properly-operating TCP 140 implementations would cause the data pipeline to drain with 141 every packet loss, and require a slow-start action to 142 recover. The Fast Retransmit and Fast Recovery algorithms 143 [Jacobson90c] [Allman99] were introduced, and their combined 144 effect was to recover from one packet loss per window, 145 without draining the pipeline. However, more than one packet 146 loss per window typically resulted in a retransmission 147 timeout and the resulting pipeline drain and slow start. 149 Expanding the window size to match the capacity of an LFN 150 results in a corresponding increase of the probability of 151 more than one packet per window being dropped. This could 152 have a devastating effect upon the throughput of TCP over an 153 LFN. In addition, if a congestion control mechanism based 154 upon some form of random dropping were introduced into 155 gateways, randomly spaced packet drops would become common, 156 possible increasing the probability of dropping more than one 157 packet per window. 159 To generalize the Fast Retransmit/Fast Recovery mechanism to 160 handle multiple packets dropped per window, selective 161 acknowledgments are required. Unlike the normal cumulative 162 acknowledgments of TCP, selective acknowledgments give the 163 sender a complete picture of which segments are queued at the 164 receiver and which have not yet arrived. 166 Since the publication of RFC-1323, selective acknowledgments 167 have become important in the LFN regime. RFC-1072 defined a 168 new TCP "SACK" option to send a selective acknowledgment, but 169 at the time that RFC-1323 was published, important technical 170 issues still had to be worked out concerning both the format 171 and semantics of the SACK option, so it was split off from 172 RFC-1323. SACK has now been published as a separate 173 document, RFC-2018 [Mathis96]. Additional information about 174 SACK can be found in RFC-2883, "An Extension to the Selective 175 Acknowledgement (SACK) option for TCP" [Floyd00] and 176 RFC-3517, "A Conservative Selective Acknowledgment 177 (SACK)-based Loss Recovery Algorithm for TCP" [Blanton03]. 179 (3) Round-Trip Measurement 181 TCP implements reliable data delivery by retransmitting 182 segments that are not acknowledged within some retransmission 183 timeout (RTO) interval. Accurate dynamic determination of an 184 appropriate RTO is essential to TCP performance. RTO is 185 determined by estimating the mean and variance of the 186 measured round-trip time (RTT), i.e., the time interval 187 between sending a segment and receiving an acknowledgment for 188 it [Jacobson88a]. 190 Section 4 introduces a new TCP option, "Timestamps", and then 191 defines a mechanism using this option that allows nearly 192 every segment, including retransmissions, to be timed at 193 negligible computational cost. We use the mnemonic RTTM 194 (Round Trip Time Measurement) for this mechanism, to 195 distinguish it from other uses of the Timestamps option. 197 1.2 TCP Reliability 199 Now we turn from performance to reliability. High transfer rate 200 enters TCP performance through the bandwidth*delay product. 201 However, high transfer rate alone can threaten TCP reliability by 202 violating the assumptions behind the TCP mechanism for duplicate 203 detection and sequencing. 205 An especially serious kind of error may result from an accidental 206 reuse of TCP sequence numbers in data segments. Suppose that an 207 "old duplicate segment", e.g., a duplicate data segment that was 208 delayed in Internet queues, is delivered to the receiver at the 209 wrong moment, so that its sequence numbers falls somewhere within 210 the current window. There would be no checksum failure to warn of 211 the error, and the result could be an undetected corruption of the 212 data. Reception of an old duplicate ACK segment at the 213 transmitter could be only slightly less serious: it is likely to 214 lock up the connection so that no further progress can be made, 215 forcing an RST on the connection. 217 TCP reliability depends upon the existence of a bound on the 218 lifetime of a segment: the "Maximum Segment Lifetime" or MSL. An 219 MSL is generally required by any reliable transport protocol, 220 since every sequence number field must be finite, and therefore 221 any sequence number may eventually be reused. In the Internet 222 protocol suite, the MSL bound is enforced by an IP-layer 223 mechanism, the "Time-to-Live" or TTL field. 225 Duplication of sequence numbers might happen in either of two 226 ways: 228 (1) Sequence number wrap-around on the current connection 230 A TCP sequence number contains 32 bits. At a high enough 231 transfer rate, the 32-bit sequence space may be "wrapped" 232 (cycled) within the time that a segment is delayed in queues. 234 (2) Earlier incarnation of the connection 236 Suppose that a connection terminates, either by a proper 237 close sequence or due to a host crash, and the same 238 connection (i.e., using the same pair of sockets) is 239 immediately reopened. A delayed segment from the terminated 240 connection could fall within the current window for the new 241 incarnation and be accepted as valid. 243 Duplicates from earlier incarnations, Case (2), are avoided by 244 enforcing the current fixed MSL of the TCP spec, as explained in 245 Section 5.3 and Appendix B. However, case (1), avoiding the 246 reuse of sequence numbers within the same connection, requires an 247 MSL bound that depends upon the transfer rate, and at high enough 248 rates, a new mechanism is required. 250 More specifically, if the maximum effective bandwidth at which TCP 251 is able to transmit over a particular path is B bytes per second, 252 then the following constraint must be satisfied for error-free 253 operation: 255 2**31 / B > MSL (secs) [1] 257 The following table shows the value for Twrap = 2**31/B in 258 seconds, for some important values of the bandwidth B: 260 Network B*8 B Twrap 261 bits/sec bytes/sec secs 262 _______ _______ ______ ______ 264 ARPANET 56kbps 7KBps 3*10**5 (~3.6 days) 266 DS1 1.5Mbps 190KBps 10**4 (~3 hours) 268 Ethernet 10Mbps 1.25MBps 1700 (~30 mins) 270 DS3 45Mbps 5.6MBps 380 272 FDDI 100Mbps 12.5MBps 170 274 Gigabit 1Gbps 125MBps 17 276 10GigE 10Gbps 1.25GBps 1.7 278 It is clear that wrap-around of the sequence space is not a 279 problem for 56kbps packet switching or even 10Mbps Ethernets. On 280 the other hand, at DS3 and FDDI speeds, Twrap is comparable to the 281 2 minute MSL assumed by the TCP specification [Postel81]. Moving 282 towards and beyond gigabit speeds, Twrap becomes too small for 283 reliable enforcement by the Internet TTL mechanism. 285 The 16-bit window field of TCP limits the effective bandwidth B to 286 2**16/RTT, where RTT is the round-trip time in seconds 287 [McKenzie89]. If the RTT is large enough, this limits B to a 288 value that meets the constraint [1] for a large MSL value. For 289 example, consider a transcontinental backbone with an RTT of 60ms 290 (set by the laws of physics). With the bandwidth*delay product 291 limited to 64KB by the TCP window size, B is then limited to 292 1.1MBps, no matter how high the theoretical transfer rate of the 293 path. This corresponds to cycling the sequence number space in 294 Twrap= 2000 secs, which is safe in today's Internet. 296 It is important to understand that the culprit is not the larger 297 window but rather the high bandwidth. For example, consider a 298 (very large) FDDI LAN with a diameter of 10km. Using the speed of 299 light, we can compute the RTT across the ring as 300 (2*10**4)/(3*10**8) = 67 microseconds, and the delay*bandwidth 301 product is then 833 bytes. A TCP connection across this LAN using 302 a window of only 833 bytes will run at the full 100mbps and can 303 wrap the sequence space in about 3 minutes, very close to the MSL 304 of TCP. Thus, high speed alone can cause a reliability problem 305 with sequence number wrap-around, even without extended windows. 307 Watson's Delta-T protocol [Watson81] includes network-layer 308 mechanisms for precise enforcement of an MSL. In contrast, the IP 309 mechanism for MSL enforcement is loosely defined and even more 310 loosely implemented in the Internet. Therefore, it is unwise to 311 depend upon active enforcement of MSL for TCP connections, and it 312 is unrealistic to imagine setting MSL's smaller than the current 313 values (e.g., 120 seconds specified for TCP). 315 A possible fix for the problem of cycling the sequence space would 316 be to increase the size of the TCP sequence number field. For 317 example, the sequence number field (and also the acknowledgment 318 field) could be expanded to 64 bits. This could be done either by 319 changing the TCP header or by means of an additional option. 321 Section 5 presents a different mechanism, which we call PAWS 322 (Protect Against Wrapped Sequence numbers), to extend TCP 323 reliability to transfer rates well beyond the foreseeable upper 324 limit of network bandwidths. PAWS uses the TCP Timestamps option 325 defined in Section 4 to protect against old duplicates from the 326 same connection. 328 1.3 Using TCP options 330 The extensions defined in this memo all use new TCP options. We 331 must address two possible issues concerning the use of TCP 332 options: (1) compatibility and (2) overhead. 334 We must pay careful attention to compatibility, i.e., to 335 interoperation with existing implementations. The only TCP option 336 defined previously, MSS, may appear only on a SYN segment. Every 337 implementation should (and we expect that most will) ignore 338 unknown options on SYN segments. When RFC-1323 was published, 339 there was concern that some buggy TCP implementation might be 340 crashed by the first appearance of an option on a non-SYN segment. 341 However, bugs like that can lead to DOS attacks against a TCP, so 342 it is now expected that most TCP implementations will properly 343 handle unknown options on non-SYN segments. But it is still 344 prudent to be conservative in what you send, and avoiding buggy 345 TCP implementation is not the only reason for negotiating TCP 346 options on SYN segments. Therefore, for each of the extensions 347 defined below, TCP options will be sent on non-SYN segments only 348 after an exchange of options on the the SYN segments has indicated 349 that both sides understand the extension. Furthermore, an 350 extension option will be sent in a segment only if the 351 corresponding option was received in the initial segment. 353 A question may be raised about the bandwidth and processing 354 overhead for TCP options. Those options that occur on SYN 355 segments are not likely to cause a performance concern. Opening a 356 TCP connection requires execution of significant special-case 357 code, and the processing of options is unlikely to increase that 358 cost significantly. 360 On the other hand, a Timestamps option may appear in any data or 361 ACK segment, adding 12 bytes to the 20-byte TCP header. We 362 believe that the bandwidth saved by reducing unnecessary 363 retransmissions will more than pay for the extra header bandwidth. 365 There is also an issue about the processing overhead for parsing 366 the variable byte-aligned format of options, particularly with a 367 RISC-architecture CPU. Appendix A contains a recommended layout 368 of the options in TCP headers to achieve reasonable data field 369 alignment. In the spirit of Header Prediction, a TCP can quickly 370 test for this layout and if it is verified then use a fast path. 371 Hosts that use this canonical layout will effectively use the 372 options as a set of fixed-format fields appended to the TCP 373 header. However, to retain the philosophical and protocol 374 framework of TCP options, a TCP must be prepared to parse an 375 arbitrary options field, albeit with less efficiency. 377 Finally, we observe that most of the mechanisms defined in this 378 memo are important for LFN's and/or very high-speed networks. For 379 low-speed networks, it might be a performance optimization to NOT 380 use these mechanisms. A TCP vendor concerned about optimal 381 performance over low-speed paths might consider turning these 382 extensions off for low-speed paths, or allow a user or 383 installation manager to disable them. 385 2. TCP WINDOW SCALE OPTION 387 2.1 Introduction 389 The window scale extension expands the definition of the TCP 390 window to 32 bits and then uses a scale factor to carry this 391 32-bit value in the 16-bit Window field of the TCP header (SEG.WND 392 in RFC-793). The scale factor is carried in a new TCP option, 393 Window Scale. This option is sent only in a SYN segment (a 394 segment with the SYN bit on), hence the window scale is fixed in 395 each direction when a connection is opened. (Another design 396 choice would be to specify the window scale in every TCP segment. 397 It would be incorrect to send a window scale option only when the 398 scale factor changed, since a TCP option in an acknowledgement 399 segment will not be delivered reliably (unless the ACK happens to 400 be piggy-backed on data in the other direction). Fixing the scale 401 when the connection is opened has the advantage of lower overhead 402 but the disadvantage that the scale factor cannot be changed 403 during the connection.) 405 The maximum receive window, and therefore the scale factor, is 406 determined by the maximum receive buffer space. In a typical 407 modern implementation, this maximum buffer space is set by default 408 but can be overridden by a user program before a TCP connection is 409 opened. This determines the scale factor, and therefore no new 410 user interface is needed for window scaling. 412 2.2 Window Scale Option 414 The three-byte Window Scale option may be sent in a SYN segment by 415 a TCP. It has two purposes: (1) indicate that the TCP is prepared 416 to do both send and receive window scaling, and (2) communicate a 417 scale factor to be applied to its receive window. Thus, a TCP 418 that is prepared to scale windows should send the option, even if 419 its own scale factor is 1. The scale factor is limited to a power 420 of two and encoded logarithmically, so it may be implemented by 421 binary shift operations. 423 TCP Window Scale Option (WSopt): 425 Kind: 3 427 Length: 3 bytes 429 +---------+---------+---------+ 430 | Kind=3 |Length=3 |shift.cnt| 431 +---------+---------+---------+ 433 This option is an offer, not a promise; both sides must send 434 Window Scale options in their SYN segments to enable window 435 scaling in either direction. If window scaling is enabled, 436 then the TCP that sent this option will right-shift its true 437 receive-window values by 'shift.cnt' bits for transmission in 438 SEG.WND. The value 'shift.cnt' may be zero (offering to scale, 439 while applying a scale factor of 1 to the receive window). 441 This option may be sent in an initial segment (i.e., a 442 segment with the SYN bit on and the ACK bit off). It may also 443 be sent in a segment, but only if a Window Scale 444 option was received in the initial segment. A Window 445 Scale option in a segment without a SYN bit should be ignored. 447 The Window field in a SYN (i.e., a or ) segment 448 itself is never scaled. 450 2.3 Using the Window Scale Option 452 A model implementation of window scaling is as follows, using the 453 notation of RFC-793 [Postel81]: 455 * All windows are treated as 32-bit quantities for storage in 456 the connection control block and for local calculations. 457 This includes the send-window (SND.WND) and the receive- 458 window (RCV.WND) values, as well as the congestion window. 460 * The connection state is augmented by two window shift counts, 461 Snd.Wind.Scale and Rcv.Wind.Scale, to be applied to the 462 incoming and outgoing window fields, respectively. 464 * If a TCP receives a segment containing a Window Scale 465 option, it sends its own Window Scale option in the 466 segment. 468 * The Window Scale option is sent with shift.cnt = R, where R 469 is the value that the TCP would like to use for its receive 470 window. 472 * Upon receiving a SYN segment with a Window Scale option 473 containing shift.cnt = S, a TCP sets Snd.Wind.Scale to S and 474 sets Rcv.Wind.Scale to R; otherwise, it sets both 475 Snd.Wind.Scale and Rcv.Wind.Scale to zero. 477 * The window field (SEG.WND) in the header of every incoming 478 segment, with the exception of SYN segments, is left-shifted 479 by Snd.Wind.Scale bits before updating SND.WND: 481 SND.WND = SEG.WND << Snd.Wind.Scale 483 (assuming the other conditions of RFC-793 are met, and using 484 the "C" notation "<<" for left-shift). 486 * The window field (SEG.WND) of every outgoing segment, with 487 the exception of SYN segments, is right-shifted by 488 Rcv.Wind.Scale bits: 490 SEG.WND = RCV.WND >> Rcv.Wind.Scale. 492 TCP determines if a data segment is "old" or "new" by testing 493 whether its sequence number is within 2**31 bytes of the left edge 494 of the window, and if it is not, discarding the data as "old". To 495 insure that new data is never mistakenly considered old and vice- 496 versa, the left edge of the sender's window has to be at most 497 2**31 away from the right edge of the receiver's window. 498 Similarly with the sender's right edge and receiver's left edge. 499 Since the right and left edges of either the sender's or 500 receiver's window differ by the window size, and since the sender 501 and receiver windows can be out of phase by at most the window 502 size, the above constraints imply that 2 * the max window size 503 must be less than 2**31, or 505 max window < 2**30 507 Since the max window is 2**S (where S is the scaling shift count) 508 times at most 2**16 - 1 (the maximum unscaled window), the maximum 509 window is guaranteed to be < 2*30 if S <= 14. Thus, the shift 510 count must be limited to 14 (which allows windows of 2**30 = 1 511 Gbyte). If a Window Scale option is received with a shift.cnt 512 value exceeding 14, the TCP should log the error but use 14 513 instead of the specified value. 515 The scale factor applies only to the Window field as transmitted 516 in the TCP header; each TCP using extended windows will maintain 517 the window values locally as 32-bit numbers. For example, the 518 "congestion window" computed by Slow Start and Congestion 519 Avoidance is not affected by the scale factor, so window scaling 520 will not introduce quantization into the congestion window. 522 3. RTTM: ROUND-TRIP TIME MEASUREMENT 524 3.1 Introduction 526 Accurate and current RTT estimates are necessary to adapt to 527 changing traffic conditions and to avoid an instability known as 528 "congestion collapse" [Nagle84] in a busy network. However, 529 accurate measurement of RTT may be difficult both in theory and in 530 implementation. 532 Many TCP implementations base their RTT measurements upon a sample 533 of one packet per window or less. While this yields an adequate 534 approximation to the RTT for small windows, it results in an 535 unacceptably poor RTT estimate for an LFN. If we look at RTT 536 estimation as a signal processing problem (which it is), a data 537 signal at some frequency, the packet rate, is being sampled at a 538 lower frequency, the window rate. This lower sampling frequency 539 violates Nyquist's criteria and may therefore introduce "aliasing" 540 artifacts into the estimated RTT [Hamming77]. 542 A good RTT estimator with a conservative retransmission timeout 543 calculation can tolerate aliasing when the sampling frequency is 544 "close" to the data frequency. For example, with a window of 8 545 packets, the sample rate is 1/8 the data frequency -- less than an 546 order of magnitude different. However, when the window is tens or 547 hundreds of packets, the RTT estimator may be seriously in error, 548 resulting in spurious retransmissions. 550 If there are dropped packets, the problem becomes worse. Zhang 551 [Zhang86], Jain [Jain86] and Karn [Karn87] have shown that it is 552 not possible to accumulate reliable RTT estimates if retransmitted 553 segments are included in the estimate. Since a full window of 554 data will have been transmitted prior to a retransmission, all of 555 the segments in that window will have to be ACKed before the next 556 RTT sample can be taken. This means at least an additional 557 window's worth of time between RTT measurements and, as the error 558 rate approaches one per window of data (e.g., 10**-6 errors per 559 bit for the Wideband satellite network), it becomes effectively 560 impossible to obtain a valid RTT measurement. 562 A solution to these problems, which actually simplifies the sender 563 substantially, is as follows: using TCP options, the sender places 564 a timestamp in each data segment, and the receiver reflects these 565 timestamps back in ACK segments. Then a single subtract gives the 566 sender an accurate RTT measurement for every ACK segment (which 567 will correspond to every other data segment, with a sensible 568 receiver). We call this the RTTM (Round-Trip Time Measurement) 569 mechanism. 571 It is vitally important to use the RTTM mechanism with big 572 windows; otherwise, the door is opened to some dangerous 573 instabilities due to aliasing. Furthermore, the option is 574 probably useful for all TCP's, since it simplifies the sender. 576 3.2 TCP Timestamps Option 578 TCP is a symmetric protocol, allowing data to be sent at any time 579 in either direction, and therefore timestamp echoing may occur in 580 either direction. For simplicity and symmetry, we specify that 581 timestamps always be sent and echoed in both directions. For 582 efficiency, we combine the timestamp and timestamp reply fields 583 into a single TCP Timestamps Option. 585 TCP Timestamps Option (TSopt): 587 Kind: 8 589 Length: 10 bytes 591 +-------+-------+---------------------+---------------------+ 592 |Kind=8 | 10 | TS Value (TSval) |TS Echo Reply (TSecr)| 593 +-------+-------+---------------------+---------------------+ 594 1 1 4 4 596 The Timestamps option carries two four-byte timestamp fields. 597 The Timestamp Value field (TSval) contains the current value of 598 the timestamp clock of the TCP sending the option. 600 The Timestamp Echo Reply field (TSecr) is valid if the ACK bit 601 is set in the TCP header; if it is valid, it echos a timestamp 602 value that was sent by the remote TCP in the TSval field of a 603 Timestamps option. When TSecr is not valid, its value must be 604 zero. The TSecr value will generally be from the most recent 605 Timestamp option that was received; however, there are 606 exceptions that are explained below. 608 A TCP may send the Timestamps option (TSopt) in an initial 609 segment (i.e., a segment containing a SYN bit and no ACK 610 bit), and may send a TSopt in other segments only if it 611 received a TSopt in the initial or segment for 612 the connection. Once a TSopt has been sent or received in a 613 non segment, it must be sent in all segments. Once a 614 TSopt has been received in a non segment, then any 615 successive segment that is received without the RST bit and 616 without a TSopt may be ACKed and dropped without further 617 processing. 619 3.3 The RTTM Mechanism 621 RTTM places a Timestamps option in every segment, with a TSval 622 that is obtained from a (virtual) "timestamp clock". Values of 623 this clock values must be at least approximately proportional to 624 real time, in order to measure actual RTT. 626 These TSval values are echoed in TSecr values in the reverse 627 direction. The difference between a received TSecr value and the 628 current timestamp clock value provides an RTT measurement. 630 When timestamps are used, every segment that is received will 631 contain a TSecr value; however, these values cannot all be used to 632 update the measured RTT. The following example illustrates why. 633 It shows a one-way data flow with segments arriving in sequence 634 without loss. Here A, B, C... represent data blocks occupying 635 successive blocks of sequence numbers, and ACK(A),... represent 636 the corresponding cumulative acknowledgments. The two timestamp 637 fields of the Timestamps option are shown symbolically as . Each TSecr field contains the value most recently 639 received in a TSval field; these echoed values. labelled 640 "TS.Recent", are shown in parentheses. 642 TCP A TCP B 644 (TS.Recent) (TS.Recent) 646 1. (120) ---> (1) 648 2. (125) <--- (1) 650 3. (125) ---> (6) 652 4. (130) <--- (6) 654 . . . ( Pause for 60 timestamp clock ticks ) . . . . 656 5. (130) ---> (1) 658 6. (125) <--- (1) 660 4. (127) ---> ... 662 5. ... <--- (5) 664 TCP A TCP B 666 ------> 668 <---- 670 ------> 672 <---- 674 . . . . . . . . . . . . . . . . . . . . . . 676 ------> 678 <---- 680 (etc) 682 The dotted line marks a pause (60 time units long) in which A had 683 nothing to send. Note that this pause inflates the RTT which B 684 could infer from receiving TSecr=131 in data segment C. Thus, in 685 one-way data flows, RTTM in the reverse direction measures a value 686 that is inflated by gaps in sending data. However, the following 687 rule prevents a resulting inflation of the measured RTT: 689 RTTM Rule: A TSecr value received in a segment is used to 690 update the averaged RTT measurement only if the segment 691 acknowledges some new data, i.e., only if it advances the 692 left edge of the send window. 694 Since TCP B is not sending data, the data segment C does not 695 acknowledge any new data when it arrives at B. Thus, the inflated 696 RTTM measurement is not used to update B's RTTM measurement. 698 Implementors should note that with Timestamps multiple RTTMs can 699 be taken per RTT. Many RTO estimators have a weighting factor 700 based on an implicit assumption that at most one RTTM will be 701 gotten per RTT. When using multiple RTTMs per RTT to update the 702 RTO estimator, the weighting factor needs to be decreased to take 703 into account the more frequent RTTMs. For example, 705 3.4 Which Timestamp to Echo 707 If more than one Timestamps option is received before a reply 708 segment is sent, the TCP must choose only one of the TSvals to 709 echo, ignoring the others. To minimize the state kept in the 710 receiver (i.e., the number of unprocessed TSvals), the receiver 711 should be required to retain at most one timestamp in the 712 connection control block. 714 There are three situations to consider: 716 (A) Delayed ACKs. 718 Many TCP's acknowledge only every Kth segment out of a group 719 of segments arriving within a short time interval; this 720 policy is known generally as "delayed ACKs". The data-sender 721 TCP must measure the effective RTT, including the additional 722 time due to delayed ACKs, or else it will retransmit 723 unnecessarily. Thus, when delayed ACKs are in use, the 724 receiver should reply with the TSval field from the earliest 725 unacknowledged segment. 727 (B) A hole in the sequence space (segment(s) have been lost). 729 The sender will continue sending until the window is filled, 730 and the receiver may be generating ACKs as these out-of-order 731 segments arrive (e.g., to aid "fast retransmit"). 733 The lost segment is probably a sign of congestion, and in 734 that situation the sender should be conservative about 735 retransmission. Furthermore, it is better to overestimate 736 than underestimate the RTT. An ACK for an out-of-order 737 segment should therefore contain the timestamp from the most 738 recent segment that advanced the window. 740 The same situation occurs if segments are re-ordered by the 741 network. 743 (C) A filled hole in the sequence space. 745 The segment that fills the hole represents the most recent 746 measurement of the network characteristics. On the other 747 hand, an RTT computed from an earlier segment would probably 748 include the sender's retransmit time-out, badly biasing the 749 sender's average RTT estimate. Thus, the timestamp from the 750 latest segment (which filled the hole) must be echoed. 752 An algorithm that covers all three cases is described in the 753 following rules for Timestamps option processing on a synchronized 754 connection: 756 (1) The connection state is augmented with two 32-bit slots: 757 TS.Recent holds a timestamp to be echoed in TSecr whenever a 758 segment is sent, and Last.ACK.sent holds the ACK field from 759 the last segment sent. Last.ACK.sent will equal RCV.NXT 760 except when ACKs have been delayed. 762 (2) If: 764 SEG.TSval >= TSrecent and SEG.SEQ <= Last.ACK.sent 766 then SEG.TSval is copied to TS.Recent; otherwise, it is 767 ignored. 769 (3) When a TSopt is sent, its TSecr field is set to the current 770 TS.Recent value. 772 The following examples illustrate these rules. Here A, B, C... 773 represent data segments occupying successive blocks of sequence 774 numbers, and ACK(A),... represent the corresponding 775 acknowledgment segments. Note that ACK(A) has the same sequence 776 number as B. We show only one direction of timestamp echoing, for 777 clarity. 779 o Packets arrive in sequence, and some of the ACKs are delayed. 781 By Case (A), the timestamp from the oldest unacknowledged 782 segment is echoed. 784 TS.Recent 785 -------------------> 786 1 787 -------------------> 788 1 789 -------------------> 790 1 791 <---- 792 (etc) 794 o Packets arrive out of order, and every packet is 795 acknowledged. 797 By Case (B), the timestamp from the last segment that 798 advanced the left window edge is echoed, until the missing 799 segment arrives; it is echoed according to Case (C). The 800 same sequence would occur if segments B and D were lost and 801 retransmitted.. 803 TS.Recent 804 -------------------> 805 1 806 <---- 807 1 808 -------------------> 809 1 810 <---- 811 1 812 -------------------> 813 2 814 <---- 815 2 816 -------------------> 817 2 818 <---- 819 2 820 -------------------> 821 4 822 <---- 823 (etc) 825 4. PAWS: PROTECT AGAINST WRAPPED SEQUENCE NUMBERS 827 4.1 Introduction 829 Section 4.2 describes a simple mechanism to reject old duplicate 830 segments that might corrupt an open TCP connection; we call this 831 mechanism PAWS (Protect Against Wrapped Sequence numbers). PAWS 832 operates within a single TCP connection, using state that is saved 833 in the connection control block. Section 4.3 and Appendix C 834 discuss the implications of the PAWS mechanism for avoiding old 835 duplicates from previous incarnations of the same connection. 837 4.2 The PAWS Mechanism 839 PAWS uses the same TCP Timestamps option as the RTTM mechanism 840 described earlier, and assumes that every received TCP segment 841 (including data and ACK segments) contains a timestamp SEG.TSval 842 whose values are monotone non-decreasing in time. The basic idea 843 is that a segment can be discarded as an old duplicate if it is 844 received with a timestamp SEG.TSval less than some timestamp 845 recently received on this connection. 847 In both the PAWS and the RTTM mechanism, the "timestamps" are 848 32-bit unsigned integers in a modular 32-bit space. Thus, "less 849 than" is defined the same way it is for TCP sequence numbers, and 850 the same implementation techniques apply. If s and t are 851 timestamp values, s < t if 0 < (t - s) < 2**31, computed in 852 unsigned 32-bit arithmetic. 854 The choice of incoming timestamps to be saved for this comparison 855 must guarantee a value that is monotone increasing. For example, 856 we might save the timestamp from the segment that last advanced 857 the left edge of the receive window, i.e., the most recent in- 858 sequence segment. Instead, we choose the value TS.Recent 859 introduced in Section 3.4 for the RTTM mechanism, since using a 860 common value for both PAWS and RTTM simplifies the implementation 861 of both. As Section 3.4 explained, TS.Recent differs from the 862 timestamp from the last in-sequence segment only in the case of 863 delayed ACKs, and therefore by less than one window. Either 864 choice will therefore protect against sequence number wrap-around. 866 RTTM was specified in a symmetrical manner, so that TSval 867 timestamps are carried in both data and ACK segments and are 868 echoed in TSecr fields carried in returning ACK or data segments. 869 PAWS submits all incoming segments to the same test, and therefore 870 protects against duplicate ACK segments as well as data segments. 871 (An alternative un-symmetric algorithm would protect against old 872 duplicate ACKs: the sender of data would reject incoming ACK 873 segments whose TSecr values were less than the TSecr saved from 874 the last segment whose ACK field advanced the left edge of the 875 send window. This algorithm was deemed to lack economy of 876 mechanism and symmetry.) 878 TSval timestamps sent on {SYN} and {SYN,ACK} segments are used to 879 initialize PAWS. PAWS protects against old duplicate non-SYN 880 segments, and duplicate SYN segments received while there is a 881 synchronized connection. Duplicate {SYN} and {SYN,ACK} segments 882 received when there is no connection will be discarded by the 883 normal 3-way handshake and sequence number checks of TCP. 885 RFC-1323 recommended that RST segments NOT carry timestamps, and 886 that they be accetable regardless of their timestamp. At that 887 time, the thinking was that old duplicate RST segments should be 888 exceedingly unlikely, and their cleanup function should take 889 precedence over timestamps. More recently, discussion about 890 various blind attacks on TCP connections have raised the 891 suggestion that if the Timestamps option is present, SEG.TSecr 892 could be used to provide stricter acceptance tests for RST 893 packets. While still under discussion, to enable research into 894 this area it is now recommended that when generating a RST, that 895 if the packet causing the RST to be generated contained a 896 Timestamps option that the RST also contain a Timestamps option. 897 In the RST segment, SEG.TSecr should be set to SEG.TSval from the 898 incoming packet and SEG.TSval should be set to zero. If a RST is 899 being generated because of a user abort, and Snd.TS.OK is set, 900 then a Timestamps option should be included in the RST. When a 901 RST packet is received, it must not be subjected to PAWS checks, 902 and information from Timestamps option must not be use to update 903 connection state information. SEG.TSecr may be used to provide 904 stricter RST acceptance checks. 906 4.2.1 Basic PAWS Algorithm 908 The PAWS algorithm requires the following processing to be 909 performed on all incoming segments for a synchronized 910 connection: 912 R1) If there is a Timestamps option in the arriving segment, 913 SEG.TSval < TS.Recent, TS.Recent is valid (see later 914 discussion) and the RST bit is not set, then treat the 915 arriving segment as not acceptable: 917 Send an acknowledgement in reply as specified in 918 RFC-793 page 69 and drop the segment. 920 Note: it is necessary to send an ACK segment in order 921 to retain TCP's mechanisms for detecting and 922 recovering from half-open connections. For example, 923 see Figure 10 of RFC-793. 925 R2) If the segment is outside the window, reject it (normal 926 TCP processing) 928 R3) If an arriving segment satisfies: SEG.SEQ <= Last.ACK.sent 929 (see Section 3.4), then record its timestamp in TS.Recent. 931 R4) If an arriving segment is in-sequence (i.e., at the left 932 window edge), then accept it normally. 934 R5) Otherwise, treat the segment as a normal in-window, out- 935 of-sequence TCP segment (e.g., queue it for later delivery 936 to the user). 938 Steps R2, R4, and R5 are the normal TCP processing steps 939 specified by RFC-793. 941 It is important to note that the timestamp is checked only when 942 a segment first arrives at the receiver, regardless of whether 943 it is in-sequence or it must be queued for later delivery. 944 Consider the following example. 946 Suppose the segment sequence: A.1, B.1, C.1, ..., Z.1 has 947 been sent, where the letter indicates the sequence number 948 and the digit represents the timestamp. Suppose also that 949 segment B.1 has been lost. The timestamp in TS.TStamp is 950 1 (from A.1), so C.1, ..., Z.1 are considered acceptable 951 and are queued. When B is retransmitted as segment B.2 952 (using the latest timestamp), it fills the hole and causes 953 all the segments through Z to be acknowledged and passed 954 to the user. The timestamps of the queued segments are 955 *not* inspected again at this time, since they have 956 already been accepted. When B.2 is accepted, TS.Stamp is 957 set to 2. 959 This rule allows reasonable performance under loss. A full 960 window of data is in transit at all times, and after a loss a 961 full window less one packet will show up out-of-sequence to be 962 queued at the receiver (e.g., up to ~2**30 bytes of data); the 963 timestamp option must not result in discarding this data. 965 In certain unlikely circumstances, the algorithm of rules R1-R4 966 could lead to discarding some segments unnecessarily, as shown 967 in the following example: 969 Suppose again that segments: A.1, B.1, C.1, ..., Z.1 have 970 been sent in sequence and that segment B.1 has been lost. 971 Furthermore, suppose delivery of some of C.1, ... Z.1 is 972 delayed until AFTER the retransmission B.2 arrives at the 973 receiver. These delayed segments will be discarded 974 unnecessarily when they do arrive, since their timestamps 975 are now out of date. 977 This case is very unlikely to occur. If the retransmission was 978 triggered by a timeout, some of the segments C.1, ... Z.1 must 979 have been delayed longer than the RTO time. This is presumably 980 an unlikely event, or there would be many spurious timeouts and 981 retransmissions. If B's retransmission was triggered by the 982 "fast retransmit" algorithm, i.e., by duplicate ACKs, then the 983 queued segments that caused these ACKs must have been received 984 already. 986 Even if a segment were delayed past the RTO, the Fast 987 Retransmit mechanism [Jacobson90c] will cause the delayed 988 packets to be retransmitted at the same time as B.2, avoiding 989 an extra RTT and therefore causing a very small performance 990 penalty. 992 We know of no case with a significant probability of occurrence 993 in which timestamps will cause performance degradation by 994 unnecessarily discarding segments. 996 4.2.2 Timestamp Clock 998 It is important to understand that the PAWS algorithm does not 999 require clock synchronization between sender and receiver. The 1000 sender's timestamp clock is used to stamp the segments, and the 1001 sender uses the echoed timestamp to measure RTT's. However, 1002 the receiver treats the timestamp as simply a monotone- 1003 increasing serial number, without any necessary connection to 1004 its clock. From the receiver's viewpoint, the timestamp is 1005 acting as a logical extension of the high-order bits of the 1006 sequence number. 1008 The receiver algorithm does place some requirements on the 1009 frequency of the timestamp clock. 1011 (a) The timestamp clock must not be "too slow". 1013 It must tick at least once for each 2**31 bytes sent. In 1014 fact, in order to be useful to the sender for round trip 1015 timing, the clock should tick at least once per window's 1016 worth of data, and even with the RFC-1072 window 1017 extension, 2**31 bytes must be at least two windows. 1019 To make this more quantitative, any clock faster than 1 1020 tick/sec will reject old duplicate segments for link 1021 speeds of ~8 Gbps. A 1ms timestamp clock will work at 1022 link speeds up to 8 Tbps (8*10**12) bps! 1024 (b) The timestamp clock must not be "too fast". 1026 Its recycling time must be greater than MSL seconds. 1027 Since the clock (timestamp) is 32 bits and the worst-case 1028 MSL is 255 seconds, the maximum acceptable clock frequency 1029 is one tick every 59 ns. 1031 However, it is desirable to establish a much longer 1032 recycle period, in order to handle outdated timestamps on 1033 idle connections (see Section 4.2.3), and to relax the MSL 1034 requirement for preventing sequence number wrap-around. 1035 With a 1 ms timestamp clock, the 32-bit timestamp will 1036 wrap its sign bit in 24.8 days. Thus, it will reject old 1037 duplicates on the same connection if MSL is 24.8 days or 1038 less. This appears to be a very safe figure; an MSL of 1039 24.8 days or longer can probably be assumed by the gateway 1040 system without requiring precise MSL enforcement by the 1041 TTL value in the IP layer. 1043 Based upon these considerations, we choose a timestamp clock 1044 frequency in the range 1 ms to 1 sec per tick. This range also 1045 matches the requirements of the RTTM mechanism, which does not 1046 need much more resolution than the granularity of the 1047 retransmit timer, e.g., tens or hundreds of milliseconds. 1049 The PAWS mechanism also puts a strong monotonicity requirement 1050 on the sender's timestamp clock. The method of implementation 1051 of the timestamp clock to meet this requirement depends upon 1052 the system hardware and software. 1054 * Some hosts have a hardware clock that is guaranteed to be 1055 monotonic between hardware resets. 1057 * A clock interrupt may be used to simply increment a binary 1058 integer by 1 periodically. 1060 * The timestamp clock may be derived from a system clock 1061 that is subject to being abruptly changed, by adding a 1062 variable offset value. This offset is initialized to 1063 zero. When a new timestamp clock value is needed, the 1064 offset can be adjusted as necessary to make the new value 1065 equal to or larger than the previous value (which was 1066 saved for this purpose). 1068 4.2.3 Outdated Timestamps 1070 If a connection remains idle long enough for the timestamp 1071 clock of the other TCP to wrap its sign bit, then the value 1072 saved in TS.Recent will become too old; as a result, the PAWS 1073 mechanism will cause all subsequent segments to be rejected, 1074 freezing the connection (until the timestamp clock wraps its 1075 sign bit again). 1077 With the chosen range of timestamp clock frequencies (1 sec to 1078 1 ms), the time to wrap the sign bit will be between 24.8 days 1079 and 24800 days. A TCP connection that is idle for more than 24 1080 days and then comes to life is exceedingly unusual. However, 1081 it is undesirable in principle to place any limitation on TCP 1082 connection lifetimes. 1084 We therefore require that an implementation of PAWS include a 1085 mechanism to "invalidate" the TS.Recent value when a connection 1086 is idle for more than 24 days. (An alternative solution to the 1087 problem of outdated timestamps would be to send keepalive 1088 segments at a very low rate, but still more often than the 1089 wrap-around time for timestamps, e.g., once a day. This would 1090 impose negligible overhead. However, the TCP specification has 1091 never included keepalives, so the solution based upon 1092 invalidation was chosen.) 1094 Note that a TCP does not know the frequency, and therefore, the 1095 wraparound time, of the other TCP, so it must assume the worst. 1096 The validity of TS.Recent needs to be checked only if the basic 1097 PAWS timestamp check fails, i.e., only if SEG.TSval < 1098 TS.Recent. If TS.Recent is found to be invalid, then the 1099 segment is accepted, regardless of the failure of the timestamp 1100 check, and rule R3 updates TS.Recent with the TSval from the 1101 new segment. 1103 To detect how long the connection has been idle, the TCP may 1104 update a clock or timestamp value associated with the 1105 connection whenever TS.Recent is updated, for example. The 1106 details will be implementation-dependent. 1108 4.2.4 Header Prediction 1110 "Header prediction" [Jacobson90a] is a high-performance 1111 transport protocol implementation technique that is most 1112 important for high-speed links. This technique optimizes the 1113 code for the most common case, receiving a segment correctly 1114 and in order. Using header prediction, the receiver asks the 1115 question, "Is this segment the next in sequence?" This 1116 question can be answered in fewer machine instructions than the 1117 question, "Is this segment within the window?" 1119 Adding header prediction to our timestamp procedure leads to 1120 the following recommended sequence for processing an arriving 1121 TCP segment: 1123 H1) Check timestamp (same as step R1 above) 1125 H2) Do header prediction: if segment is next in sequence and 1126 if there are no special conditions requiring additional 1127 processing, accept the segment, record its timestamp, and 1128 skip H3. 1130 H3) Process the segment normally, as specified in RFC-793. 1131 This includes dropping segments that are outside the 1132 window and possibly sending acknowledgments, and queueing 1133 in-window, out-of-sequence segments. 1135 Another possibility would be to interchange steps H1 and H2, 1136 i.e., to perform the header prediction step H2 FIRST, and 1137 perform H1 and H3 only when header prediction fails. This 1138 could be a performance improvement, since the timestamp check 1139 in step H1 is very unlikely to fail, and it requires interval 1140 arithmetic on a finite field, a relatively expensive operation. 1141 To perform this check on every single segment is contrary to 1142 the philosophy of header prediction. We believe that this 1143 change might reduce CPU time for TCP protocol processing by up 1144 to 5-10% on high-speed networks. 1146 However, putting H2 first would create a hazard: a segment from 1147 2**32 bytes in the past might arrive at exactly the wrong time 1148 and be accepted mistakenly by the header-prediction step. The 1149 following reasoning has been introduced [Jacobson90b] to show 1150 that the probability of this failure is negligible. 1152 If all segments are equally likely to show up as old 1153 duplicates, then the probability of an old duplicate 1154 exactly matching the left window edge is the maximum 1155 segment size (MSS) divided by the size of the sequence 1156 space. This ratio must be less than 2**-16, since MSS 1157 must be < 2**16; for example, it will be (2**12)/(2**32) = 1158 2**-20 for an FDDI link. However, the older a segment is, 1159 the less likely it is to be retained in the Internet, and 1160 under any reasonable model of segment lifetime the 1161 probability of an old duplicate exactly at the left window 1162 edge must be much smaller than 2**-16. 1164 The 16 bit TCP checksum also allows a basic unreliability 1165 of one part in 2**16. A protocol mechanism whose 1166 reliability exceeds the reliability of the TCP checksum 1167 should be considered "good enough", i.e., it won't 1168 contribute significantly to the overall error rate. We 1169 therefore believe we can ignore the problem of an old 1170 duplicate being accepted by doing header prediction before 1171 checking the timestamp. 1173 However, this probabilistic argument is not universally 1174 accepted, and the consensus at present is that the performance 1175 gain does not justify the hazard in the general case. It is 1176 therefore recommended that H2 follow H1. 1178 4.2.5 IP Fragmentation 1180 At high data rates, the protection against old packets provided 1181 by PAWS can be circumvented by errors in IP fragment reassembly 1182 [Heffner07]. The only way to protect against incorrect IP 1183 fragment reassembly is to not allow the packets to be 1184 fragmented. This is done by setting the Don't Fragment (DF) 1185 bit in the IP header. Setting the DF bit implies that Path MTU 1186 Discovery as described in RFC-1191 [Mogul90]. Thus any TCP 1187 implementation that implements PAWS must also implement Path 1188 MTU Discovery. 1190 4.3. Duplicates from Earlier Incarnations of Connection 1192 The PAWS mechanism protects against errors due to sequence number 1193 wrap-around on high-speed connection. Segments from an earlier 1194 incarnation of the same connection are also a potential cause of 1195 old duplicate errors. In both cases, the TCP mechanisms to 1196 prevent such errors depend upon the enforcement of a maximum 1197 segment lifetime (MSL) by the Internet (IP) layer (see Appendix of 1198 RFC-1185 for a detailed discussion). Unlike the case of sequence 1199 space wrap-around, the MSL required to prevent old duplicate 1200 errors from earlier incarnations does not depend upon the transfer 1201 rate. If the IP layer enforces the recommended 2 minute MSL of 1202 TCP, and if the TCP rules are followed, TCP connections will be 1203 safe from earlier incarnations, no matter how high the network 1204 speed. Thus, the PAWS mechanism is not required for this case. 1206 We may still ask whether the PAWS mechanism can provide additional 1207 security against old duplicates from earlier connections, allowing 1208 us to relax the enforcement of MSL by the IP layer. Appendix B 1209 explores this question, showing that further assumptions and/or 1210 mechanisms are required, beyond those of PAWS. This is not part 1211 of the current extension. 1213 5. CONCLUSIONS AND ACKNOWLEDGMENTS 1215 This memo presented a set of extensions to TCP to provide efficient 1216 operation over large-bandwidth*delay-product paths and reliable 1217 operation over very high-speed paths. These extensions are designed 1218 to provide compatible interworking with TCP's that do not implement 1219 the extensions. 1221 These mechanisms are implemented using new TCP options for scaled 1222 windows and timestamps. The timestamps are used for two distinct 1223 mechanisms: RTTM (Round Trip Time Measurement) and PAWS (Protect 1224 Against Wrapped Sequences). 1226 The Window Scale option was originally suggested by Mike St. Johns of 1227 USAF/DCA. The present form of the option was suggested by Mike 1228 Karels of UC Berkeley in response to a more cumbersome scheme defined 1229 by Van Jacobson. Lixia Zhang helped formulate the PAWS mechanism 1230 description in RFC-1185. 1232 Finally, much of this work originated as the result of discussions 1233 within the End-to-End Task Force on the theoretical limitations of 1234 transport protocols in general and TCP in particular. Task force 1235 members and other on the end2end-interest list have made valuable 1236 contributions by pointing out flaws in the algorithms and the 1237 documentation. Continued discussion and development since the 1238 publication of RFC-1323 originally occurred in the IETF TCP Large 1239 Windows Working Group, later on in the End-to-End Taks Force, and 1240 most recently in the IETF TCP Maintance Working Group. The authors 1241 are grateful for all these contributions. 1243 6. SECURITY CONSIDERATIONS 1245 Security issues are not discussed in this memo. 1247 7. REFERENCES 1249 Normative References 1251 [Mogul90] Mojul, J. and Deering, S., "Path MTU Discovery", 1252 RFC-1191, November 1990. 1254 [Postel81] Postel, J., "Transmission Control Protocol - DARPA 1255 Internet Program Protocol Specification", RFC-793, DARPA, 1256 September 1981. 1258 Informative References 1260 [Allman99] Allman, M., Paxson, V., Stevens, W., "TCP Congestion 1261 Control", RFC-2581, NASA Glenn/Sterling Software, ACIRI / ICSI, 1262 April 1999. 1264 [Borman99] Borman, D., Deering, S., and Hinden, R, "IPv6 1265 Jumbograms" RFC-2675, August 1999. 1267 [Braden89] Braden, R., editor, "Requirements for Internet Hosts -- 1268 Communication Layers", RFC-1122, October, 1989 1270 [Floyd00] Floyd, S., Mahdavi, J., Mathis, M., Podolsky, M., "An 1271 Extension to the Selective Acknowledgement (SACK) Option for TCP", 1272 RFC-2883, July 2000. 1274 [Blanton03] Blanton, E., Allman, M., Fall, K., Wang, L., "A 1275 Conservative Selective Acknowledgment (SACK)-based Loss Recovery 1276 Algorithm for TCP", RFC-3517, April 2003. 1278 [Garlick77] Garlick, L., R. Rom, and J. Postel, "Issues in 1279 Reliable Host-to-Host Protocols", Proc. Second Berkeley Workshop 1280 on Distributed Data Management and Computer Networks, May 1977. 1282 [Hamming77] Hamming, R., "Digital Filters", ISBN 0-13-212571-4, 1283 Prentice Hall, Englewood Cliffs, N.J., 1977. 1285 [Heffner07] Heffner, J., Mathis, M., and Chandler, B., "IPv4 1286 Reassembly Errors at High Data Rates" RFC-4963, PSC, July 2007. 1288 [Jacobson88a] Jacobson, V., "Congestion Avoidance and Control", 1289 SIGCOMM '88, Stanford, CA., August 1988. 1291 [Jacobson88b] Jacobson, V., and R. Braden, "TCP Extensions for 1292 Long-Delay Paths", RFC-1072, LBL and USC/Information Sciences 1293 Institute, October 1988. 1295 [Jacobson90a] Jacobson, V., "4BSD Header Prediction", ACM 1296 Computer Communication Review, April 1990. 1298 [Jacobson90b] Jacobson, V., Braden, R., and Zhang, L., "TCP 1299 Extension for High-Speed Paths", RFC-1185, LBL and USC/Information 1300 Sciences Institute, October 1990. 1302 [Jacobson90c] Jacobson, V., "Modified TCP congestion avoidance 1303 algorithm", Message to end2end-interest mailing list, April 1990. 1305 [Jacobson92d] Jacobson, V., Braden, R., and Borman, D., "TCP 1306 Extension for High Performance", RFC-1323, LBL, USC/Information 1307 Sciences Institute and Cray Research, May 1992. 1309 [Jain86] Jain, R., "Divergence of Timeout Algorithms for Packet 1310 Retransmissions", Proc. Fifth Phoenix Conf. on Comp. and Comm., 1311 Scottsdale, Arizona, March 1986. 1313 [Karn87] Karn, P. and C. Partridge, "Estimating Round-Trip Times 1314 in Reliable Transport Protocols", Proc. SIGCOMM '87, Stowe, VT, 1315 August 1987. 1317 [Martin03] Martin, D., "[Tsvwg] RFC 1323.bis" Message to tsvwg 1318 mailing list, September 30, 2003. 1320 [Mathis96] Mathis, M., Mahdavi, J., Floyd, S., and Romanow, A., 1321 "TCP Selective Acknowledgment Options", RFC-2018, October, 1996. 1323 [McKenzie89] McKenzie, A., "A Problem with the TCP Big Window 1324 Option", RFC-1110, BBN STC, August 1989. 1326 [Nagle84] Nagle, J., "Congestion Control in IP/TCP 1327 Internetworks", RFC-896, FACC, January 1984. 1329 [Postel83] Postel, J., "The TCP Maximum Segment Size and Related 1330 Topics", RFC-879, ISI, November 1983. 1332 [Watson81] Watson, R., "Timer-based Mechanisms in Reliable 1333 Transport Protocol Connection Management", Computer Networks, Vol. 1334 5, 1981. 1336 [Zhang86] Zhang, L., "Why TCP Timers Don't Work Well", Proc. 1337 SIGCOMM '86, Stowe, Vt., August 1986. 1339 APPENDIX A: IMPLEMENTATION SUGGESTIONS 1341 TCP Option Layout 1343 The following layouts are recommended for sending options on 1344 non-SYN segments, to achieve maximum feasible alignment of 1345 32-bit and 64-bit machines. 1347 +--------+--------+--------+--------+ 1348 | NOP | NOP | TSopt | 10 | 1349 +--------+--------+--------+--------+ 1350 | TSval timestamp | 1351 +--------+--------+--------+--------+ 1352 | TSecr timestamp | 1353 +--------+--------+--------+--------+ 1355 Interaction with the TCP Urgent Pointer 1357 The TCP Urgent pointer, like the TCP window, is a 16 bit value. 1358 Some of the original discussion for the TCP Window Scale option 1359 included proposals to increase the Urgent pointer to 32 bits. 1360 As it turns out, this is unnecessary. There are two 1361 observations that should be made: 1363 (1) With IP Version 4, the largest amount of TCP data that can 1364 be sent in a single packet is 65495 bytes (64K - 1 - size 1365 of fixed IP and TCP headers). 1367 (2) Updates to the urgent pointer while the user is in "urgent 1368 mode" are invisible to the user. 1370 This means that if the Urgent Pointer points beyond the end of 1371 the TCP data in the current packet, then the user will remain in 1372 urgent mode until the next TCP packet arrives. That packet will 1373 update the urgent pointer to a new offset, and the user will 1374 never have left urgent mode. 1376 Thus, to properly implement the Urgent Pointer, the sending TCP 1377 only has to check for overflow of the 16 bit Urgent Pointer 1378 field before filling it in. If it does overflow, than a value 1379 of 65535 should be inserted into the Urgent Pointer. 1381 The same technique applies to IP Version 6, except in the case 1382 of IPv6 Jumbograms. When IPv6 Jumbograms are supported, 1383 RFC-2675 [Borman99] requires additional steps for dealing with 1384 the Urgent Pointer, these are described in section 5.2 of 1385 RFC-2675. 1387 TCP Options and MSS 1389 There has been some confusion as to what value should be filled 1390 in the TCP MSS option when using TCP options. RFC-879 1391 [Postel83] stated: 1393 The MSS counts only data octets in the segment, it does not 1394 count the TCP header or the IP header. 1396 which is unclear about what to do about TCP options. RFC-1122 1397 [Braden89] attempted to clarify this in section 4.2.2.6, but 1398 there still seems to be confusion. 1400 So, the MSS value to be sent in an MSS option should be equal to 1401 the effective MTU minus the fixed IP and TCP headers. Since 1402 both IP and TCP options are ignored when calculating the value 1403 for the MSS option, if there are any IP or TCP options to be 1404 sent in a packet, then the sender must decrease the size of the 1405 TCP data accordingly. The reason for this can be seen in the 1406 following table: 1408 +--------------------+--------------------+ 1409 | MSS is adjusted | MSS isn't adjusted | 1410 | to include options | to include options | 1411 +----------------+--------------------+--------------------+ 1412 | Sender adjusts | Packets are too | Packets are the | 1413 | length for | short | correct length | 1414 | options | | | 1415 +----------------+--------------------+--------------------+ 1416 | Sender doesn't | Packets are the | Packets are too | 1417 | adjust length | correct length | long. | 1418 | for options | | | 1419 +----------------+--------------------+--------------------+ 1421 Since the goal is to not send IP datagrams that have to be 1422 fragmented, and packets sent with the constraints in the lower 1423 right of this grid will cause IP fragmentation, the only way to 1424 guarantee that this doesn't happen is for the data sender to 1425 decrease the TCP data length by the size of the IP and TCP 1426 options. And since the sender will be adjusting the TCP data 1427 length when sending IP and TCP options, there is no need to 1428 include the IP and TCP option lengths in the MSS value. 1430 APPENDIX B: DUPLICATES FROM EARLIER CONNECTION INCARNATIONS 1432 There are two cases to be considered: (1) a system crashing (and 1433 losing connection state) and restarting, and (2) the same connection 1434 being closed and reopened without a loss of host state. These will 1435 be described in the following two sections. 1437 B.1 System Crash with Loss of State 1439 TCP's quiet time of one MSL upon system startup handles the loss 1440 of connection state in a system crash/restart. For an 1441 explanation, see for example "When to Keep Quiet" in the TCP 1442 protocol specification [Postel81]. The MSL that is required here 1443 does not depend upon the transfer speed. The current TCP MSL of 2 1444 minutes seems acceptable as an operational compromise, as many 1445 host systems take this long to boot after a crash. 1447 However, the timestamp option may be used to ease the MSL 1448 requirements (or to provide additional security against data 1449 corruption). If timestamps are being used and if the timestamp 1450 clock can be guaranteed to be monotonic over a system 1451 crash/restart, i.e., if the first value of the sender's timestamp 1452 clock after a crash/restart can be guaranteed to be greater than 1453 the last value before the restart, then a quiet time will be 1454 unnecessary. 1456 To dispense totally with the quiet time would require that the 1457 host clock be synchronized to a time source that is stable over 1458 the crash/restart period, with an accuracy of one timestamp clock 1459 tick or better. We can back off from this strict requirement to 1460 take advantage of approximate clock synchronization. Suppose that 1461 the clock is always re-synchronized to within N timestamp clock 1462 ticks and that booting (extended with a quiet time, if necessary) 1463 takes more than N ticks. This will guarantee monotonicity of the 1464 timestamps, which can then be used to reject old duplicates even 1465 without an enforced MSL. 1467 B.2 Closing and Reopening a Connection 1469 When a TCP connection is closed, a delay of 2*MSL in TIME-WAIT 1470 state ties up the socket pair for 4 minutes (see Section 3.5 of 1471 [Postel81]. Applications built upon TCP that close one connection 1472 and open a new one (e.g., an FTP data transfer connection using 1473 Stream mode) must choose a new socket pair each time. The TIME- 1474 WAIT delay serves two different purposes: 1476 (a) Implement the full-duplex reliable close handshake of TCP. 1478 The proper time to delay the final close step is not really 1479 related to the MSL; it depends instead upon the RTO for the 1480 FIN segments and therefore upon the RTT of the path. (It 1481 could be argued that the side that is sending a FIN knows 1482 what degree of reliability it needs, and therefore it should 1483 be able to determine the length of the TIME-WAIT delay for 1484 the FIN's recipient. This could be accomplished with an 1485 appropriate TCP option in FIN segments.) 1487 Although there is no formal upper-bound on RTT, common 1488 network engineering practice makes an RTT greater than 1 1489 minute very unlikely. Thus, the 4 minute delay in TIME-WAIT 1490 state works satisfactorily to provide a reliable full-duplex 1491 TCP close. Note again that this is independent of MSL 1492 enforcement and network speed. 1494 The TIME-WAIT state could cause an indirect performance 1495 problem if an application needed to repeatedly close one 1496 connection and open another at a very high frequency, since 1497 the number of available TCP ports on a host is less than 1498 2**16. However, high network speeds are not the major 1499 contributor to this problem; the RTT is the limiting factor 1500 in how quickly connections can be opened and closed. 1501 Therefore, this problem will be no worse at high transfer 1502 speeds. 1504 (b) Allow old duplicate segments to expire. 1506 To replace this function of TIME-WAIT state, a mechanism 1507 would have to operate across connections. PAWS is defined 1508 strictly within a single connection; the last timestamp is 1509 TS.Recent is kept in the connection control block, and 1510 discarded when a connection is closed. 1512 An additional mechanism could be added to the TCP, a per-host 1513 cache of the last timestamp received from any connection. 1514 This value could then be used in the PAWS mechanism to reject 1515 old duplicate segments from earlier incarnations of the 1516 connection, if the timestamp clock can be guaranteed to have 1517 ticked at least once since the old connection was open. This 1518 would require that the TIME-WAIT delay plus the RTT together 1519 must be at least one tick of the sender's timestamp clock. 1520 Such an extension is not part of the proposal of this RFC. 1522 Note that this is a variant on the mechanism proposed by 1523 Garlick, Rom, and Postel [Garlick77], which required each 1524 host to maintain connection records containing the highest 1525 sequence numbers on every connection. Using timestamps 1526 instead, it is only necessary to keep one quantity per remote 1527 host, regardless of the number of simultaneous connections to 1528 that host. 1530 APPENDIX C: CHANGES FROM RFC-1072, RFC-1185, RFC-1323 1532 The protocol extensions defined in RFC-1323 document differ in 1533 several important ways from those defined in RFC-1072 and RFC-1185. 1535 (a) SACK has been split off into a separate document, RFC-2018 1536 [Mathis96]. 1538 (b) The detailed rules for sending timestamp replies (see Section 1539 3.4) differ in important ways. The earlier rules could result 1540 in an under-estimate of the RTT in certain cases (packets 1541 dropped or out of order). 1543 (c) The same value TS.Recent is now shared by the two distinct 1544 mechanisms RTTM and PAWS. This simplification became possible 1545 because of change (b). 1547 (d) An ambiguity in RFC-1185 was resolved in favor of putting 1548 timestamps on ACK as well as data segments. This supports the 1549 symmetry of the underlying TCP protocol. 1551 (e) The echo and echo reply options of RFC-1072 were combined into a 1552 single Timestamps option, to reflect the symmetry and to 1553 simplify processing. 1555 (f) The problem of outdated timestamps on long-idle connections, 1556 discussed in Section 4.2.2, was realized and resolved. 1558 (g) RFC-1185 recommended that header prediction take precedence over 1559 the timestamp check. Based upon some scepticism about the 1560 probabilistic arguments given in Section 4.2.4, it was decided 1561 to recommend that the timestamp check be performed first. 1563 (h) The spec was modified so that the extended options will be sent 1564 on segments only when they are received in the 1565 corresponding segments. This provides the most 1566 conservative possible conditions for interoperation with 1567 implementations without the extensions. 1569 In addition to these substantive changes, the present RFC attempts to 1570 specify the algorithms unambiguously by presenting modifications to 1571 the Event Processing rules of RFC-793; see Appendix F. 1573 There are additional changes in this document from RFC-1323. These 1574 changes are: 1576 (a) The description of which TSecr values can be used to update the 1577 measured RTT has been clarified. Specifically, with Timestamps, 1578 the Karn algorithm [Karn87] is disabled. The Karn algorithm 1579 disables all RTT measurements during retransmission, since it is 1580 ambiguous whether the ACK is is for the original packet, or the 1581 retransmitted packet. With Timestamps, that ambiguity is 1582 removed since the TSecr in the ACK will contain the TSval from 1583 which ever data packet made it to the destination. 1585 (b) In RFC-1323, section 3.4, step (2) of the algorithm to control 1586 which timestamp is echoed was incorrect in two regards: 1588 (1) It failed to update TSrecent for a retransmitted segment 1589 that resulted from a lost ACK. 1591 (2) It failed if SEG.LEN = 0. 1593 In the new algorithm, the case of SEG.TSval = TSrecent is 1594 included for consistency with the PAWS test. 1596 (c) One correction was made to the Event Processing Summary in 1597 Appendix F. In SEND CALL/ESTABLISHED STATE, RCV.WND is used to 1598 fill in the SEG.WND value, not SND.WND. 1600 (d) New pseudo-code summary has been added in Appendix E. 1602 (e) Appendix A has been expanded with information about the TCP MSS 1603 option and the TCP Urgent Pointer. 1605 (f) It is now recommended that Timestamps options be included RST 1606 packets if the incoming packet contained a Timestamps option. 1608 (g) RST packets are explicitly excluded from PAWS processing. 1610 (h) Snd.TSoffset and Snd.TSclock variables have been added. 1611 Snd.TSoffset is the sum of my.TSclock and Snd.TSoffset. This 1612 allows the starting points for timestamps to be randomized on a 1613 per-connection basis. Setting Snd.TSoffset to zero yields the 1614 same results as RFC-1323. 1616 APPENDIX D: SUMMARY OF NOTATION 1618 The following notation has been used in this document. 1620 Options 1622 WSopt: TCP Window Scale Option 1623 TSopt: TCP Timestamps Option 1625 Option Fields 1627 shift.cnt: Window scale byte in WSopt. 1628 TSval: 32-bit Timestamp Value field in TSopt. 1629 TSecr: 32-bit Timestamp Reply field in TSopt. 1631 Option Fields in Current Segment 1633 SEG.TSval: TSval field from TSopt in current segment. 1634 SEG.TSecr: TSecr field from TSopt in current segment. 1635 SEG.WSopt: 8-bit value in WSopt 1637 Clock Values 1639 my.TSclock: System Wide Local source of 32-bit timestamp values 1640 my.TSclock.rate: Period of my.TSclock (1 ms to 1 sec). 1641 Snd.TSoffset: A offset for randomizing Snd.TSclock 1642 Snd.TSclock: my.TSclock + Snd.TSoffset 1644 Per-Connection State Variables 1646 TS.Recent: Latest received Timestamp 1647 Last.ACK.sent: Last ACK field sent 1649 Snd.TS.OK: 1-bit flag 1650 Snd.WS.OK: 1-bit flag 1652 Rcv.Wind.Scale: Receive window scale power 1653 Snd.Wind.Scale: Send window scale power 1655 Start.Time: Snd.TSclock value when segment being 1656 timed was sent (used by pre-1323 code). 1658 Procedure 1660 Update_SRTT( m ) Procedure to update the smoothed RTT and RTT 1661 variance estimates, using the rules of 1662 [Jacobson88a], given m, a new RTT measurement. 1664 APPENDIX E: PSEUDO-CODE SUMMARY 1666 Create new TCB => { 1667 Rcv.wind.scale = 1668 MIN( 14, MAX( 0, floor(log2(receive buffer space)) - 15 ) ); 1669 Snd.wind.scale = 0; 1670 Last.ACK.sent = 0; 1671 Snd.TS.OK = Snd.WS.OK = FALSE; 1672 Snd.TSoffset = random 32 bit value 1673 } 1675 Send initial {SYN} segment => { 1677 SEG.WND = MIN( RCV.WND, 65535 ); 1678 Include in segment: TSopt(TSval=Snd.TSclock, TCecr=0); 1679 Include in segment: WSopt = Rcv.wind.scale; 1680 } 1682 Send {SYN, ACK} segment => { 1684 SEG.ACK = Last.ACK.sent = RCV.NXT; 1685 SEG.WND = MIN( RCV.WND, 65535 ); 1686 if (Snd.TS.OK) then 1687 Include in segment: TSopt(TSval=Snd.TSclock, TSecr=TS.Recent); 1688 if (Snd.WS.OK) then 1689 Include in segment: WSopt = Rcv.wind.scale; 1690 } 1692 Receive {SYN} or {SYN,ACK} segment => { 1694 if (Segment contains TSopt) then { 1695 TS.Recent = SEG.TSval; 1696 Snd.TS.OK = TRUE; 1697 if (is {SYN,ACK} segment) then 1698 Update_SRTT( 1699 (Snd.TSclock - SEG.TSecr)/my.TSclock.rate ) ; 1700 } 1702 if (Segment contains WSopt) then { 1703 Snd.wind.scale = SEG.WSopt; 1704 Snd.WS.OK = TRUE; 1705 if (the ACK bit is not set, and Rcv.wind.scale has not been 1706 initialized by the user) then 1707 Rcv.wind.scale = Snd.wind.scale; 1708 } 1709 else 1710 Rcv.wind.scale = Snd.wind.scale = 0; 1712 } 1714 Send non-SYN segment => { 1716 SEG.ACK = Last.ACK.sent = RCV.NXT; 1717 SEG.WND = MIN( RCV.WND >> Rcv.wind.scale, 65535 ); 1718 if (Snd.TS.OK) then 1719 Include in segment: TSopt(TSval=Snd.TSclock, TSecr=TS.Recent); 1720 } 1722 Receive non-SYN segment in (state >= ESTABLISHED) => { 1724 Window = (SEG.WND << Snd.wind.scale); 1725 /* Use 32-bit 'Window' instead of 16-bit 'SEG.WND' 1726 * in rest of processing. 1727 */ 1729 if (Segment contains TSopt) then { 1730 if (SEG.TSval < TS.Recent && Idle less than 24 days) then { 1731 if (Send.TS.OK AND (NOT RST) ) then { 1732 /* Timestamp too old => 1733 * segment is unacceptable. 1734 */ 1735 Send ACK segment; 1736 Discard segment and return; 1737 } 1738 } 1739 else { 1740 if (SEG.SEQ =< Last.ACK.sent) then 1741 TS.Recent = SEG.TSval; 1742 } 1743 } 1745 if (SEG.ACK > SND.UNA) then { 1746 /* (At least part of) first segment in 1747 * retransmission queue has been ACKd 1748 */ 1749 if (Segment contains TSopt) then 1750 Update_SRTT( 1751 (Snd.TSclock - SEG.TSecr)/my.TSclock.rate); 1752 else 1753 Update_SRTT( /* for compatibility */ 1754 (Snd.TSclock - Start.Time)/my.TSclock.rate); 1755 } 1756 } 1758 APPENDIX F: EVENT PROCESSING SUMMARY 1760 Event Processing 1762 OPEN Call 1764 ... 1765 An initial send sequence number (ISS) is selected. Send a SYN 1766 segment of the form: 1768 1770 ... 1772 SEND Call 1774 CLOSED STATE (i.e., TCB does not exist) 1776 ... 1778 LISTEN STATE 1780 If the foreign socket is specified, then change the connection 1781 from passive to active, select an ISS. Send a SYN segment 1782 containing the options: and 1783 . Set SND.UNA to ISS, SND.NXT to ISS+1. 1784 Enter SYN-SENT state. ... 1786 SYN-SENT STATE 1787 SYN-RECEIVED STATE 1789 ... 1791 ESTABLISHED STATE 1792 CLOSE-WAIT STATE 1794 Segmentize the buffer and send it with a piggybacked 1795 acknowledgment (acknowledgment value = RCV.NXT). ... 1797 If the urgent flag is set ... 1799 If the Snd.TS.OK flag is set, then include the TCP Timestamps 1800 option in each data segment. 1802 Scale the receive window for transmission in the segment header: 1804 SEG.WND = (RCV.WND >> Rcv.Wind.Scale). 1806 SEGMENT ARRIVES 1808 ... 1810 If the state is LISTEN then 1812 first check for an RST 1814 ... 1816 second check for an ACK 1818 ... 1820 third check for a SYN 1822 if the SYN bit is set, check the security. If the ... 1824 ... 1826 If the SEG.PRC is less than the TCB.PRC then continue. 1828 Check for a Window Scale option (WSopt); if one is found, save 1829 SEG.WSopt in Snd.Wind.Scale and set Snd.WS.OK flag on. 1830 Otherwise, set both Snd.Wind.Scale and Rcv.Wind.Scale to zero 1831 and clear Snd.WS.OK flag. 1833 Check for a TSopt option; if one is found, save SEG.TSval in the 1834 variable TS.Recent and turn on the Snd.TS.OK bit. 1836 Set RCV.NXT to SEG.SEQ+1, IRS is set to SEG.SEQ and any other 1837 control or text should be queued for processing later. ISS 1838 should be selected and a SYN segment sent of the form: 1840 1842 If the Snd.WS.OK bit is on, include a WSopt option 1843 in this segment. If the Snd.TS.OK bit is 1844 on, include a TSopt in this 1845 segment. Last.ACK.sent is set to RCV.NXT. 1847 SND.NXT is set to ISS+1 and SND.UNA to ISS. The connection 1848 state should be changed to SYN-RECEIVED. Note that any other 1849 incoming control or data (combined with SYN) will be processed 1850 in the SYN-RECEIVED state, but processing of SYN and ACK should 1851 not be repeated. If the listen was not fully specified (i.e., 1852 the foreign socket was not fully specified), then the 1853 unspecified fields should be filled in now. 1855 fourth other text or control 1856 ... 1858 If the state is SYN-SENT then 1860 first check the ACK bit 1862 ... 1864 fourth check the SYN bit 1866 ... 1868 If the SYN bit is on and the security/compartment and precedence 1869 are acceptable then, RCV.NXT is set to SEG.SEQ+1, IRS is set to 1870 SEG.SEQ, and any acknowledgements on the retransmission queue 1871 which are thereby acknowledged should be removed. 1873 Check for a Window Scale option (WSopt); if is found, save 1874 SEG.WSopt in Snd.Wind.Scale; otherwise, set both Snd.Wind.Scale 1875 and Rcv.Wind.Scale to zero. 1877 Check for a TSopt option; if one is found, save SEG.TSval in 1878 variable TS.Recent and turn on the Snd.TS.OK bit in the 1879 connection control block. If the ACK bit is set, use 1880 Snd.TSclock - SEG.TSecr as the initial RTT estimate. 1882 If SND.UNA > ISS (our SYN has been ACKed), change the connection 1883 state to ESTABLISHED, form an ACK segment: 1885 1887 and send it. If the Snd.Echo.OK bit is on, include a TSopt 1888 option in this ACK segment. 1889 Last.ACK.sent is set to RCV.NXT. 1891 Data or controls which were queued for transmission may be 1892 included. If there are other controls or text in the segment 1893 then continue processing at the sixth step below where the URG 1894 bit is checked, otherwise return. 1896 Otherwise enter SYN-RECEIVED, form a SYN,ACK segment: 1898 1900 and send it. If the Snd.Echo.OK bit is on, include a TSopt 1901 option in this segment. If 1902 the Snd.WS.OK bit is on, include a WSopt option 1903 in this segment. Last.ACK.sent is set to 1904 RCV.NXT. 1906 If there are other controls or text in the segment, queue them 1907 for processing after the ESTABLISHED state has been reached, 1908 return. 1910 fifth, if neither of the SYN or RST bits is set then drop the 1911 segment and return. 1913 Otherwise, 1915 First, check sequence number 1917 SYN-RECEIVED STATE 1918 ESTABLISHED STATE 1919 FIN-WAIT-1 STATE 1920 FIN-WAIT-2 STATE 1921 CLOSE-WAIT STATE 1922 CLOSING STATE 1923 LAST-ACK STATE 1924 TIME-WAIT STATE 1926 Segments are processed in sequence. Initial tests on arrival 1927 are used to discard old duplicates, but further processing is 1928 done in SEG.SEQ order. If a segment's contents straddle the 1929 boundary between old and new, only the new parts should be 1930 processed. 1932 Rescale the received window field: 1934 TrueWindow = SEG.WND << Snd.Wind.Scale, 1936 and use "TrueWindow" in place of SEG.WND in the following steps. 1938 Check whether the segment contains a Timestamps option and bit 1939 Snd.TS.OK is on. If so: 1941 If SEG.TSval < TS.Recent and the RST bit is off, then test 1942 whether connection has been idle less than 24 days; if all are 1943 true, then the segment is not acceptable; follow steps below 1944 for an unacceptable segment. 1946 If SEG.SEQ is equal to Last.ACK.sent, then save SEG.ECopt in 1947 variable TS.Recent. 1949 There are four cases for the acceptability test for an incoming 1950 segment: 1952 ... 1954 If an incoming segment is not acceptable, an acknowledgment 1955 should be sent in reply (unless the RST bit is set, if so drop 1956 the segment and return): 1958 1960 Last.ACK.sent is set to SEG.ACK of the acknowledgment. If the 1961 Snd.Echo.OK bit is on, include the Timestamps option 1962 in this ACK segment. Set 1963 Last.ACK.sent to SEG.ACK and send the ACK segment. After 1964 sending the acknowledgment, drop the unacceptable segment and 1965 return. 1967 ... 1969 fifth check the ACK field. 1971 if the ACK bit is off drop the segment and return. 1973 if the ACK bit is on 1975 ... 1977 ESTABLISHED STATE 1979 If SND.UNA < SEG.ACK =< SND.NXT then, set SND.UNA <- SEG.ACK. 1980 Also compute a new estimate of round-trip time. If Snd.TS.OK 1981 bit is on, use Snd.TSclock - SEG.TSecr; otherwise use the 1982 elapsed time since the first segment in the retransmission 1983 queue was sent. Any segments on the retransmission queue 1984 which are thereby entirely acknowledged... 1986 ... 1988 Seventh, process the segment text. 1990 ESTABLISHED STATE 1991 FIN-WAIT-1 STATE 1992 FIN-WAIT-2 STATE 1994 ... 1996 Send an acknowledgment of the form: 1998 2000 If the Snd.TS.OK bit is on, include Timestamps option 2001 in this ACK segment. Set 2002 Last.ACK.sent to SEG.ACK of the acknowledgment, and send it. 2003 This acknowledgment should be piggy-backed on a segment being 2004 transmitted if possible without incurring undue delay. 2006 ... 2008 APPENDIX G: Timestamps Edge Cases 2010 While the rules layed out for when to calculate RTTM produce the 2011 correct results most of the time, there are some edge cases where an 2012 incorrect RTTM can be calculated. All of these situations involve 2013 the loss of packets. It is felt that these scenarios are rare, and 2014 that if they should happen, they will cause a single RTTM measurement 2015 to be inflated, which mitigates its effects on RTO calculations. 2017 [Martin03] cites two similar cases when the returning ACK is lost, 2018 and before the retransmission timer fires, another returning packet 2019 arrives, which ACKs the data. In this case, the RTTM calculated will 2020 be inflated: 2022 clock 2023 tc=1 -------------------> 2025 tc=2 (lost) <---- 2026 (RTTM would have been 1) 2028 (receive window opens, window update is sent) 2029 tc=5 <---- 2030 (RTTM is calculated at 4) 2032 One thing to note about this situation is that it is somewhat bounded 2033 by RTO + RTT, limiting how far off the RTTM calculation will be. 2034 While more complex scenarios can be constructed that produce larger 2035 inflations (e.g., retransmissions are lost), those scenarios involve 2036 multiple packet losses, and the connection will have other more 2037 serious operational problems than using an inflated RTTM in the RTO 2038 calculation. ------------- 2040 Authors' Addresses 2042 David Borman 2043 Wind River Systems 2044 Mendota Heights, MN 55120 2046 Phone: (651) 454-3052 2047 Email: david.borman@windriver.com 2048 Bob Braden 2049 University of Southern California 2050 Information Sciences Institute 2051 4676 Admiralty Way 2052 Marina del Rey, CA 90292 2054 Phone: (310) 448-9173 2055 EMail: Braden@ISI.EDU 2057 Van Jacobson 2058 Packet Design 2059 2465 Latham Street 2060 Mountain View, CA 94040 2062 EMail: van@packetdesign.com 2064 Full Copyright Statement 2066 Copyright (C) The IETF Trust (2008). 2068 This document is subject to the rights, licenses and restrictions 2069 contained in BCP 78, and except as set forth therein, the authors 2070 retain all their rights. 2072 This document and the information contained herein are provided on an 2073 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 2074 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 2075 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 2076 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 2077 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2078 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2080 Intellectual Property 2082 The IETF takes no position regarding the validity or scope of any 2083 Intellectual Property Rights or other rights that might be claimed to 2084 pertain to the implementation or use of the technology described in 2085 this document or the extent to which any license under such rights 2086 might or might not be available; nor does it represent that it has 2087 made any independent effort to identify any such rights. Information 2088 on the procedures with respect to rights in RFC documents can be 2089 found in BCP 78 and BCP 79. 2091 Copies of IPR disclosures made to the IETF Secretariat and any 2092 assurances of licenses to be made available, or the result of an 2093 attempt made to obtain a general license or permission for the use of 2094 such proprietary rights by implementers or users of this 2095 specification can be obtained from the IETF on-line IPR repository at 2096 http://www.ietf.org/ipr. 2098 The IETF invites any interested party to bring to its attention any 2099 copyrights, patents or patent applications, or other proprietary 2100 rights that may cover technology that may be required to implement 2101 this standard. Please address the information to the IETF at ietf- 2102 ipr@ietf.org.