| 1 |
<pre>Network Working Group R. Braden |
| 2 |
Request for Comments: 1379 ISI |
| 3 |
November 1992 |
| 4 |
|
| 5 |
|
| 6 |
<span class="h1">Extending TCP for Transactions -- Concepts</span> |
| 7 |
|
| 8 |
Status of This Memo |
| 9 |
|
| 10 |
This memo provides information for the Internet community. It does |
| 11 |
not specify an Internet standard. Distribution of this memo is |
| 12 |
unlimited. |
| 13 |
|
| 14 |
Abstract |
| 15 |
|
| 16 |
This memo discusses extension of TCP to provide transaction-oriented |
| 17 |
service, without altering its virtual-circuit operation. This |
| 18 |
extension would fill the large gap between connection-oriented TCP |
| 19 |
and datagram-based UDP, allowing TCP to efficiently perform many |
| 20 |
applications for which UDP is currently used. A separate memo |
| 21 |
contains a detailed functional specification for this proposed |
| 22 |
extension. |
| 23 |
|
| 24 |
This work was supported in part by the National Science Foundation |
| 25 |
under Grant Number NCR-8922231. |
| 26 |
|
| 27 |
TABLE OF CONTENTS |
| 28 |
|
| 29 |
<a href="#section-1">1</a>. INTRODUCTION .................................................. <a href="#page-2">2</a> |
| 30 |
<a href="#section-2">2</a>. TRANSACTIONS USING STANDARD TCP ............................... <a href="#page-3">3</a> |
| 31 |
<a href="#section-3">3</a>. BYPASSING THE 3-WAY HANDSHAKE ................................. <a href="#page-6">6</a> |
| 32 |
<a href="#section-3.1">3.1</a> Concept of TAO ........................................... <a href="#page-6">6</a> |
| 33 |
<a href="#section-3.2">3.2</a> Cache Initialization ..................................... <a href="#page-10">10</a> |
| 34 |
<a href="#section-3.3">3.3</a> Accepting <SYN,ACK> Segments ............................. <a href="#page-11">11</a> |
| 35 |
<a href="#section-4">4</a>. SHORTENING TIME-WAIT STATE .................................... <a href="#page-13">13</a> |
| 36 |
<a href="#section-5">5</a>. CHOOSING A MONOTONIC SEQUENCE ................................. <a href="#page-15">15</a> |
| 37 |
<a href="#section-5.1">5.1</a> Cached Timestamps ........................................ <a href="#page-16">16</a> |
| 38 |
<a href="#section-5.2">5.2</a> Current TCP Sequence Numbers ............................. <a href="#page-18">18</a> |
| 39 |
<a href="#section-5.3">5.3</a> 64-bit Sequence Numbers .................................. <a href="#page-20">20</a> |
| 40 |
<a href="#section-5.4">5.4</a> Connection Counts ........................................ <a href="#page-20">20</a> |
| 41 |
<a href="#section-5.5">5.5</a> Conclusions .............................................. <a href="#page-21">21</a> |
| 42 |
<a href="#section-6">6</a>. CONNECTION STATES ............................................. <a href="#page-24">24</a> |
| 43 |
<a href="#section-7">7</a>. CONCLUSIONS AND ACKNOWLEDGMENTS ............................... <a href="#page-32">32</a> |
| 44 |
APPENDIX A: TIME-WAIT STATE AND THE 2-PACKET EXCHANGE ............ <a href="#page-34">34</a> |
| 45 |
REFERENCES ....................................................... <a href="#page-37">37</a> |
| 46 |
Security Considerations .......................................... <a href="#page-38">38</a> |
| 47 |
Author's Address ................................................. <a href="#page-38">38</a> |
| 48 |
|
| 49 |
|
| 50 |
|
| 51 |
|
| 52 |
<span class="grey">Braden [Page 1]</span></pre> |
| 53 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span> |
| 54 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 55 |
|
| 56 |
|
| 57 |
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. INTRODUCTION</span> |
| 58 |
|
| 59 |
The TCP protocol [<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>] implements a virtual-circuit transport |
| 60 |
service that provides reliable and ordered data delivery over a |
| 61 |
full-duplex connection. Under the virtual circuit model, the life of |
| 62 |
a connection is divided into three distinct phases: (1) opening the |
| 63 |
connection to create a full-duplex byte stream; (2) transferring data |
| 64 |
in one or both directions over this stream; and (3) closing the |
| 65 |
connection. Remote login and file transfer are examples of |
| 66 |
applications that are well suited to virtual-circuit service. |
| 67 |
|
| 68 |
Distributed applications, which are becoming increasingly numerous |
| 69 |
and sophisticated in the Internet, tend to use a transaction-oriented |
| 70 |
rather than a virtual circuit style of communication. Currently, a |
| 71 |
transaction-oriented Internet application must choose to suffer the |
| 72 |
overhead of opening and closing TCP connections or else build an |
| 73 |
application-specific transport mechanism on top of the connectionless |
| 74 |
transport protocol UDP. Greater convenience, uniformity, and |
| 75 |
efficiency would result from widely-available kernel implementations |
| 76 |
of a transport protocol supporting a transaction service model [RFC- |
| 77 |
955]. |
| 78 |
|
| 79 |
The transaction service model has the following features: |
| 80 |
|
| 81 |
* The fundamental interaction is a request followed by a response. |
| 82 |
|
| 83 |
* An explicit open or close phase would impose excessive overhead. |
| 84 |
|
| 85 |
* At-most-once semantics is required; that is, a transaction must |
| 86 |
not be "replayed" by a duplicate request packet. |
| 87 |
|
| 88 |
* In favorable circumstances, a reliable request/response |
| 89 |
handshake can be performed with exactly one packet in each |
| 90 |
direction. |
| 91 |
|
| 92 |
* The minimum transaction latency for a client is RTT + SPT, where |
| 93 |
RTT is the round-trip time and SPT is the server processing |
| 94 |
time. |
| 95 |
|
| 96 |
We use the term "transaction transport protocol" for a transport- |
| 97 |
layer protocol that follows this model [<a href="./rfc955" title=""Towards a Transport Service Transaction Protocol"">RFC-955</a>]. |
| 98 |
|
| 99 |
The Internet architecture allows an arbitrary collection of transport |
| 100 |
protocols to be defined on top of the minimal end-to-end datagram |
| 101 |
service provided by IP [<a href="#ref-Clark88" title=""The Design Philosophy of the Internet Protocols"">Clark88</a>]. In practice, however, production |
| 102 |
systems implement only TCP and UDP at the transport layer. It has |
| 103 |
proven difficult to leverage a new transport protocol into place, to |
| 104 |
be widely enough available to be useful for application builders. |
| 105 |
|
| 106 |
|
| 107 |
|
| 108 |
<span class="grey">Braden [Page 2]</span></pre> |
| 109 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span> |
| 110 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 111 |
|
| 112 |
|
| 113 |
This memo explores an alternative approach to providing a transaction |
| 114 |
transport protocol: extending TCP to implement the transaction |
| 115 |
service model, while continuing to support the virtual circuit model. |
| 116 |
Each transaction will then be a single instance of a TCP connection. |
| 117 |
The proposed transaction extension is effectively implementable |
| 118 |
within current TCPs and operating systems, and it should also scale |
| 119 |
to the much faster networks, interfaces, and CPUs of the future. |
| 120 |
|
| 121 |
The present memo explains the theory behind the extension, in |
| 122 |
somewhat exquisite detail. Despite the length and complexity of this |
| 123 |
memo, the TCP extensions required for transactions are in fact quite |
| 124 |
limited and simple. Another memo [<a href="#ref-TTCP-FS" title=""Transaction TCP -- Functional Specification"">TTCP-FS</a>] provides a self-contained |
| 125 |
functional specification of the extensions. |
| 126 |
|
| 127 |
<a href="#section-2">Section 2</a> of this memo describes the limitations of standard TCP for |
| 128 |
transaction processing, to motivate the extensions. Sections <a href="#section-3">3</a>, <a href="#section-4">4</a>, |
| 129 |
and 5 explore the fundamental extensions that are required for |
| 130 |
transactions. <a href="#section-6">Section 6</a> discusses the changes required in the TCP |
| 131 |
connection state diagram. Finally, <a href="#section-7">Section 7</a> presents conclusions |
| 132 |
and acknowledgments. Familiarity with the standard TCP protocol |
| 133 |
[<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>] is assumed. |
| 134 |
|
| 135 |
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. TRANSACTIONS USING STANDARD TCP</span> |
| 136 |
|
| 137 |
Reliable transfer of data depends upon sequence numbers. Before data |
| 138 |
transfer can begin, both parties must "synchronize" the connection, |
| 139 |
i.e, agree on common sequence numbers. The synchronization procedure |
| 140 |
must preserve at-most-once semantics, i.e., be free from replay |
| 141 |
hazards due to duplicate packets. The TCP developers adopted a |
| 142 |
synchronization mechanism known as the 3-way handshake. |
| 143 |
|
| 144 |
Consider a simple transaction in which client host A sends a single- |
| 145 |
segment request to server host B, and B returns a single-segment |
| 146 |
response. Many current TCP implementations use at least ten segments |
| 147 |
(i.e., packets) for this sequence: three for the 3-way handshake |
| 148 |
opening the connection, four to send and acknowledge the request and |
| 149 |
response data, and three for TCP's full-duplex data-conserving close |
| 150 |
sequence. These ten segments represent a high relative overhead for |
| 151 |
two data-bearing segments. However, a more important consideration |
| 152 |
is the transaction latency seen by the client: 2*RTT + SPT, larger |
| 153 |
than the minimum by one RTT. As CPU and network speeds increase, the |
| 154 |
relative significance of this extra transaction latency also |
| 155 |
increases. |
| 156 |
|
| 157 |
Proposed transaction transport protocols have typically used a |
| 158 |
"timer-based" approach to connection synchronization [<a href="#ref-Birrell84" title=""Implementing Remote Procedure Calls"">Birrell84</a>]. In |
| 159 |
this approach, once end-to-end connection state is established in the |
| 160 |
client and server hosts, a subset of this state is maintained for |
| 161 |
|
| 162 |
|
| 163 |
|
| 164 |
<span class="grey">Braden [Page 3]</span></pre> |
| 165 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span> |
| 166 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 167 |
|
| 168 |
|
| 169 |
some period of time. A new request before the expiration of this |
| 170 |
timeout period can then reestablish the full state without an |
| 171 |
explicit handshake. Watson pointed out that the timer-based approach |
| 172 |
of his Delta-T protocol [<a href="#ref-Watson81" title=""Timer-based Mechanisms in Reliable Transport Protocol Connection Management"">Watson81</a>] would encompass both virtual |
| 173 |
circuits and transactions. However, the TCP group adopted the 3-way |
| 174 |
handshake (because of uncertainty about the robustness of enforcing |
| 175 |
the packet lifetime bounds required by Delta-T, within a general |
| 176 |
Internet environment). More recently, Liskov, Shrira, and Wroclawski |
| 177 |
[<a href="#ref-Liskov90" title=""Efficient At-Most-Once Messages Based on Synchronized Clocks"">Liskov90</a>] have proposed a different timer-based approach to |
| 178 |
connection synchronization, requiring loosely-synchronized clocks in |
| 179 |
the hosts. |
| 180 |
|
| 181 |
The technique proposed in this memo, suggested by Clark [<a href="#ref-Clark89" title="Private communication">Clark89</a>], |
| 182 |
depends upon cacheing of connection state but not upon clocks or |
| 183 |
timers; it is described in <a href="#section-3">Section 3</a> below. Garlick, Rom, and Postel |
| 184 |
also proposed a connection synchronization mechanism using cached |
| 185 |
state [<a href="#ref-Garlick77" title=""Issues in Reliable Host-to-Host Protocols"">Garlick77</a>]. Their scheme required each host to maintain |
| 186 |
connection records containing the highest sequence number on each |
| 187 |
connection. The technique suggested here retains only per-host |
| 188 |
state, not per-connection state. |
| 189 |
|
| 190 |
During TCP development, it was suggested that TCP could support |
| 191 |
transactions with data segments containing both SYN and FIN bits. |
| 192 |
(These "Kamikaze" segments were not supported as a service; they were |
| 193 |
used mainly to crash other experimental TCPs!) To illustrate this |
| 194 |
idea, Figure 1 shows a plausible application of the current TCP rules |
| 195 |
to create a minimal transaction. (In fact, some minor adjustments in |
| 196 |
the standard TCP spec would be required to make Figure 1 fully legal |
| 197 |
[<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>]). |
| 198 |
|
| 199 |
Figure 1, like many of the examples shown in this memo, uses an |
| 200 |
abbreviated form to illustrate segment sequences. For clarity and |
| 201 |
brevity, it omits explicit sequence and acknowledgment numbers, |
| 202 |
assuming that these will follow the well-known TCP rules. The |
| 203 |
notation "ACK(x)" implies a cumulative acknowledgment for the control |
| 204 |
bit or data "x" and everything preceding "x" in the sequence space. |
| 205 |
The referent of "x" should be clear from the context. Also, host A |
| 206 |
will always be the client and host B will be the server in these |
| 207 |
diagrams. |
| 208 |
|
| 209 |
The first three segments in Figure 1 implement the standard TCP |
| 210 |
three-way handshake. If segment #1 had been an old duplicate, the |
| 211 |
client side would have sent an RST (Reset) bit in segment #3, |
| 212 |
terminating the sequence. The request data included on the initial |
| 213 |
SYN segment cannot be delivered to user B until segment #3 completes |
| 214 |
the 3-way handshake. Loading control bits onto the segments has |
| 215 |
reduced the total number of segments to 5, but the client still |
| 216 |
observes a transaction latency of 2*RTT + SPT. The 3-way handshake |
| 217 |
|
| 218 |
|
| 219 |
|
| 220 |
<span class="grey">Braden [Page 4]</span></pre> |
| 221 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span> |
| 222 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 223 |
|
| 224 |
|
| 225 |
thus precludes high-performance transaction processing. |
| 226 |
|
| 227 |
|
| 228 |
TCP A (Client) TCP B (Server) |
| 229 |
_______________ ______________ |
| 230 |
|
| 231 |
CLOSED LISTEN |
| 232 |
|
| 233 |
(Client sends request) |
| 234 |
1. SYN-SENT --> <SYN,data1,FIN> --> SYN-RCVD |
| 235 |
(data1 queued) |
| 236 |
|
| 237 |
2. ESTABLISHED <-- <SYN,ACK(SYN)> <-- SYN-RCVD |
| 238 |
|
| 239 |
|
| 240 |
3. FIN-WAIT-1 --> <ACK(SYN),FIN> --> CLOSE-WAIT |
| 241 |
(data1 to server) |
| 242 |
|
| 243 |
(Server sends reply) |
| 244 |
4. TIME-WAIT <-- <ACK(FIN),data2,FIN> <-- LAST-ACK |
| 245 |
(data2 to client) |
| 246 |
|
| 247 |
5. TIME-WAIT --> <ACK(FIN)> --> CLOSED |
| 248 |
|
| 249 |
(timeout) |
| 250 |
CLOSED |
| 251 |
|
| 252 |
Figure 1: Transaction Sequence: <a href="./rfc793">RFC-793</a> TCP |
| 253 |
|
| 254 |
|
| 255 |
The TCP close sequence also poses a performance problem for |
| 256 |
transactions: one or both end(s) of a closed connection must remain |
| 257 |
in "TIME-WAIT" state until a 4 minute timeout has expired [<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>]. |
| 258 |
The same connection (defined by the host and port numbers at both |
| 259 |
ends) cannot be reopened until this delay has expired. Because of |
| 260 |
TIME-WAIT state, a client program should choose a new local port |
| 261 |
number (i.e., a different connection) for each successive |
| 262 |
transaction. However, the TCP port field of 16 bits (less the |
| 263 |
"well-known" port space) provides only 64512 available user ports. |
| 264 |
This limits the total rate of transactions between any pair of hosts |
| 265 |
to a maximum of 64512/240 = 268 per second. This is much too low a |
| 266 |
rate for low-delay paths, e.g., high-speed LANs. A high rate of |
| 267 |
short connections (i.e., transactions) could also lead to excessive |
| 268 |
consumption of kernel memory by connection control blocks in TIME- |
| 269 |
WAIT state. |
| 270 |
|
| 271 |
In summary, to perform efficient transaction processing in TCP, we |
| 272 |
need to suppress the 3-way handshake and to shorten TIME-WAIT state. |
| 273 |
|
| 274 |
|
| 275 |
|
| 276 |
<span class="grey">Braden [Page 5]</span></pre> |
| 277 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span> |
| 278 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 279 |
|
| 280 |
|
| 281 |
Protocol mechanisms to accomplish these two goals are discussed in |
| 282 |
Sections <a href="#section-3">3</a> and <a href="#section-4">4</a>, respectively. Both require the choice of a |
| 283 |
monotonic sequence-like space; <a href="#section-5">Section 5</a> analyzes the choices and |
| 284 |
makes a selection for this space. Finally, the TCP connection state |
| 285 |
machine must be extended as described in <a href="#section-6">Section 6</a>. |
| 286 |
|
| 287 |
Transaction processing in TCP raises some other protocol issues, |
| 288 |
which are discussed in the functional specification memo [<a href="#ref-TTCP-FS" title=""Transaction TCP -- Functional Specification"">TTCP-FS</a>]. |
| 289 |
These include: |
| 290 |
|
| 291 |
(1) augmenting the user interface for transactions, |
| 292 |
|
| 293 |
(2) delaying acknowledgment segments to allow maximum piggy-backing |
| 294 |
of control bits with data, |
| 295 |
|
| 296 |
(3) measuring the retransmission timeout time (RTO) on very short |
| 297 |
connections, and |
| 298 |
|
| 299 |
(4) providing an initial server window. |
| 300 |
|
| 301 |
A recently proposed set of enhancements [<a href="./rfc1323" title="D.">RFC-1323</a>] defines a TCP |
| 302 |
Timestamps option that carries two 32-bit timestamp values. The |
| 303 |
Timestamps option is used to accurately measure round-trip time |
| 304 |
(RTT). The same option is also used in a procedure known as "PAWS" |
| 305 |
(Protect Againsts Wrapped Sequence) to prevent erroneous data |
| 306 |
delivery due to a combination of old duplicate segments and sequence |
| 307 |
number reuse at very high bandwidths. The particular approach to |
| 308 |
transactions chosen in this memo does not require the <a href="./rfc1323">RFC-1323</a> |
| 309 |
enhancements; however, they are important and should be implemented |
| 310 |
in every TCP, with or without the transaction extensions described |
| 311 |
here. |
| 312 |
|
| 313 |
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. BYPASSING THE 3-WAY HANDSHAKE</span> |
| 314 |
|
| 315 |
To avoid 3-way handshakes for transactions, we introduce a new |
| 316 |
mechanism for validating initial SYN segments, i.e., for enforcing |
| 317 |
at-most-once semantics without a 3-way handshake. We refer to this |
| 318 |
as the TCP Accelerated Open, or TAO, mechanism. |
| 319 |
|
| 320 |
3.1 Concept of TAO |
| 321 |
|
| 322 |
The basis of TAO is this: a TCP uses cached per-host information |
| 323 |
to immediately validate new SYNs [<a href="#ref-Clark89" title="Private communication">Clark89</a>]. If this validation |
| 324 |
fails, e.g., because there is no current cached state or the |
| 325 |
segment is an old duplicate, the procedure falls back to a normal |
| 326 |
3-way handshake to validate the SYN. Thus, bypassing a 3-way |
| 327 |
handshake is considered to be an optional optimization. |
| 328 |
|
| 329 |
|
| 330 |
|
| 331 |
|
| 332 |
<span class="grey">Braden [Page 6]</span></pre> |
| 333 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span> |
| 334 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 335 |
|
| 336 |
|
| 337 |
The proposed TAO mechanism uses a finite sequence-like space of |
| 338 |
values that increase monotonically with successive transactions |
| 339 |
(connections) between a given (client, server) host pair. Call |
| 340 |
this monotonic space M, and let each initial SYN segment carry an |
| 341 |
M value SEG.M. If M is not the existing sequence (SEG.SEQ) field, |
| 342 |
SEG.M may be carried in a TCP option. |
| 343 |
|
| 344 |
When host B receives from host A an initial SYN segment containing |
| 345 |
a new value SEG.M, host B compares this against cache.M[A], the |
| 346 |
latest M value that B has cached for host A. This comparison is |
| 347 |
the "TAO test". Because the M values are monotonically |
| 348 |
increasing, SEG.M > cache.M[A] implies that the SYN must be new |
| 349 |
and can be accepted immediately. If not, a normal 3-way handshake |
| 350 |
is performed to validate the initial SYN segment. Figure 2 |
| 351 |
illustrates the TAO mechanism; cached M values are shown enclosed |
| 352 |
in square brackets. The M values generated by host A satisfy |
| 353 |
x0 < x1, and the M values generated by host B satisfy y0 < y1. |
| 354 |
|
| 355 |
An appropriate choice for the M value space is discussed in |
| 356 |
<a href="#section-5">Section 5</a>. M values are drawn from a finite number space, so |
| 357 |
inequalities must be defined in the usual way for sequence numbers |
| 358 |
[<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>]. The M space must not wrap so quickly that an old |
| 359 |
duplicate SYN will be erroneously accepted. We assume that some |
| 360 |
maximum segment lifetime (MSL) is enforced by the IP layer. |
| 361 |
|
| 362 |
___<u>T</u><u>C</u><u>P</u>_<u>A</u>_____ ___<u>T</u><u>C</u><u>P</u>_<u>B</u>_____ |
| 363 |
|
| 364 |
cache.M[B] cache.M[A] |
| 365 |
V V |
| 366 |
|
| 367 |
[ y0 ] [ x0 ] |
| 368 |
|
| 369 |
1. --> <SYN,data1,M=x1> --> ( (x1 > x0) => |
| 370 |
data1 -> user_B; |
| 371 |
cache.M[A]= x1) |
| 372 |
|
| 373 |
[ y0 ] [ x1 ] |
| 374 |
2. <-- <SYN,ACK(data1),data2,M=y1> <-- |
| 375 |
|
| 376 |
(data2 -> user_A, |
| 377 |
cache.M[B]= y1) |
| 378 |
|
| 379 |
[ y1 ] [ x1 ] |
| 380 |
... (etc.) ... |
| 381 |
|
| 382 |
|
| 383 |
Figure 2. TAO: Three-Way Handshake is Bypassed |
| 384 |
|
| 385 |
|
| 386 |
|
| 387 |
|
| 388 |
<span class="grey">Braden [Page 7]</span></pre> |
| 389 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span> |
| 390 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 391 |
|
| 392 |
|
| 393 |
Figure 2 shows the simplest case: each side has cached the latest |
| 394 |
M value of the other, and the SEG.M value in the client's SYN |
| 395 |
segment is greater than the value in the cache at the server host. |
| 396 |
As a result, B can accept the client A's request data1 immediately |
| 397 |
and pass it to the server application. B's reply data2 is shown |
| 398 |
piggybacked on the <SYN,ACK> segment. As a result of this 2-way |
| 399 |
exchange, the cached M values are updated at both sites; the |
| 400 |
client side becomes relevant only if the client/server roles |
| 401 |
reverse. Validation of the <SYN,ACK> segment at host A is |
| 402 |
discussed later. |
| 403 |
|
| 404 |
Figure 3 shows the TAO test failing but the consequent 3-way |
| 405 |
handshake succeeding. B updates its cache with the value x2 >= x1 |
| 406 |
when the initial SYN is known to be valid. |
| 407 |
|
| 408 |
|
| 409 |
<u>T</u><u>C</u><u>P</u>_<u>A</u> <u>T</u><u>C</u><u>P</u>_<u>B</u> |
| 410 |
|
| 411 |
cache.M[B] cache.M[A] |
| 412 |
V V |
| 413 |
|
| 414 |
[ y0 ] [ x0 ] |
| 415 |
1. --> <SYN,data1,M=x1> --> ( (x1 <= x0) => |
| 416 |
data1 queued; |
| 417 |
3-way handshake) |
| 418 |
|
| 419 |
[ y0 ] [ x0 ] |
| 420 |
2. <-- <SYN,ACK(SYN),M=y1> <-- |
| 421 |
(cache.M[B]= y1) |
| 422 |
|
| 423 |
[ y1 ] [ x0 ] |
| 424 |
3. --> <ACK(SYN),M=x2> --> (Handshake OK => |
| 425 |
data1->user_B, |
| 426 |
cache.M[A]= x2) |
| 427 |
|
| 428 |
[ y1 ] [ x2 ] |
| 429 |
... (etc.) ... |
| 430 |
|
| 431 |
Figure 3. TAO Test Fails but 3-Way Handshake Succeeds. |
| 432 |
|
| 433 |
There are several possible causes for a TAO test failure on a |
| 434 |
legitimate new SYN segment (not an old duplicate). |
| 435 |
|
| 436 |
(1) There may be no cached M value for this particular client |
| 437 |
host. |
| 438 |
|
| 439 |
(2) The SYN may be the one of a set of nearly-simultaneous SYNs |
| 440 |
for different connections but from the same host, which |
| 441 |
|
| 442 |
|
| 443 |
|
| 444 |
<span class="grey">Braden [Page 8]</span></pre> |
| 445 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span> |
| 446 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 447 |
|
| 448 |
|
| 449 |
arrived out of order. |
| 450 |
|
| 451 |
(3) The finite M space may have wrapped around between successive |
| 452 |
transactions from the same client. |
| 453 |
|
| 454 |
(4) The M values may advance too slowly for closely-spaced |
| 455 |
transactions. |
| 456 |
|
| 457 |
None of these TAO failures will cause a lockout, because the |
| 458 |
resulting 3-way handshake will succeed. Note that the first |
| 459 |
transaction between a given host pair will always require a 3-way |
| 460 |
handshake; subsequent transactions can take advantage of TAO. |
| 461 |
|
| 462 |
The per-host cache required by TAO is highly desirable for other |
| 463 |
reasons, e.g., to retain the measured round trip time and MTU for |
| 464 |
a given remote host. Furthermore, a host should already have a |
| 465 |
per-host routing cache [<a href="#ref-HR-COMM" title=""Requirements for Internet Hosts -- Communication Layers"">HR-COMM</a>] that should be easily extensible |
| 466 |
for this purpose. |
| 467 |
|
| 468 |
Figure 4 illustrates a complete TCP transaction sequence using the |
| 469 |
TAO mechanism. Bypassing the 3-way handshake leads to new |
| 470 |
connection states; Figure 4 shows three of them, "SYN-SENT*", |
| 471 |
"CLOSE-WAIT*", and "LAST-ACK*". Explanation of these states is |
| 472 |
deferred to <a href="#section-6">Section 6</a>. |
| 473 |
|
| 474 |
|
| 475 |
TCP A (Client) TCP B (Server) |
| 476 |
_______________ ______________ |
| 477 |
|
| 478 |
CLOSED LISTEN |
| 479 |
|
| 480 |
1. SYN-SENT* --> <SYN,data1,FIN,M=x1> --> CLOSE-WAIT* |
| 481 |
(TAO test OK=> |
| 482 |
data1->user_B) |
| 483 |
|
| 484 |
<-- <SYN,ACK(FIN),data2,FIN,M=y1> <-- LAST-ACK* |
| 485 |
2. TIME-WAIT |
| 486 |
(data2->user_A) |
| 487 |
|
| 488 |
|
| 489 |
3. TIME-WAIT --> <ACK(FIN),M=x2> --> CLOSED |
| 490 |
|
| 491 |
(timeout) |
| 492 |
CLOSED |
| 493 |
|
| 494 |
|
| 495 |
Figure 4: Minimal Transaction Sequence Using TAO |
| 496 |
|
| 497 |
|
| 498 |
|
| 499 |
|
| 500 |
<span class="grey">Braden [Page 9]</span></pre> |
| 501 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span> |
| 502 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 503 |
|
| 504 |
|
| 505 |
3.2 Cache Initialization |
| 506 |
|
| 507 |
The first connection between hosts A and B will find no cached |
| 508 |
state at one or both ends, so both M caches must be initialized. |
| 509 |
This requires that the first transaction carry a specially marked |
| 510 |
SEG.M value, which we call SEG.M.NEW. Receiving a SEG.M.NEW value |
| 511 |
in an initial SYN segment, B will cache this value and send its |
| 512 |
own M back to initialize A's cache. When a host crashes and |
| 513 |
restarts, all its cached M values cache.M[*] must be invalidated |
| 514 |
in order to force a re-synchronization of the caches at both ends. |
| 515 |
|
| 516 |
This cache synchronization procedure is illustrated in Figure 5, |
| 517 |
where client host A has crashed and restarted with its cache |
| 518 |
entries undefined, as indicated by "??". Since cache.TS[B] is |
| 519 |
undefined, A sends a SEG.M.NEW value instead of SEG.M in the <SYN> |
| 520 |
segment of its first transaction request to B. Receiving this |
| 521 |
SEG.M.NEW, the server host B invalidates cache.TS[A] and performs |
| 522 |
a 3-way handshake. SEG.M in segment #2 updates A's cache, and |
| 523 |
when the handshake completes successfully, B updates its cached M |
| 524 |
value to x2 >= x1. |
| 525 |
|
| 526 |
|
| 527 |
<u>T</u><u>C</u><u>P</u>_<u>A</u> <u>T</u><u>C</u><u>P</u>_<u>B</u> |
| 528 |
|
| 529 |
cache.M[B] cache.M[A] |
| 530 |
V V |
| 531 |
[ ?? ] [ x0 ] |
| 532 |
|
| 533 |
1. --> <SYN,data1,M.NEW=x1> --> (invalidate cache; |
| 534 |
queue data1; |
| 535 |
[ ?? ] 3-way handshake) |
| 536 |
|
| 537 |
[ ?? ] |
| 538 |
2. <-- <SYN,ACK(SYN),M=y1> <-- |
| 539 |
(cache.M[B]= y1) |
| 540 |
|
| 541 |
[ y1 ] [ ?? ] |
| 542 |
|
| 543 |
3. --> <ACK(SYN),M=x2> --> data1->user_B, |
| 544 |
cache.M[A]= x2) |
| 545 |
|
| 546 |
[ y1 ] [ x2 ] |
| 547 |
... (etc.) ... |
| 548 |
|
| 549 |
Figure 5. Client Host Crashed |
| 550 |
|
| 551 |
|
| 552 |
Suppose that the 3-way handshake failed, presumably because |
| 553 |
|
| 554 |
|
| 555 |
|
| 556 |
<span class="grey">Braden [Page 10]</span></pre> |
| 557 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span> |
| 558 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 559 |
|
| 560 |
|
| 561 |
segment #1 was an old duplicate. Then segment #3 from host A |
| 562 |
would be an RST segment, with the result that both side's caches |
| 563 |
would be left undefined. |
| 564 |
|
| 565 |
Figure 6 shows the procedure when the server crashes and restarts. |
| 566 |
Upon receiving a <SYN> segment from a host for which it has no |
| 567 |
cached M value, B initiates a 3-way handshake to validate the |
| 568 |
request and sends its own M value to A. Again the result is to |
| 569 |
update cached M values on both sides. |
| 570 |
|
| 571 |
|
| 572 |
<u>T</u><u>C</u><u>P</u>_<u>A</u> <u>T</u><u>C</u><u>P</u>_<u>B</u> |
| 573 |
|
| 574 |
cache.M[B] cache.M[A] |
| 575 |
V V |
| 576 |
[ y0 ] [ ?? ] |
| 577 |
|
| 578 |
1. --> <SYN,data1,M=x1> --> (data1 queued; |
| 579 |
3-way handshake) |
| 580 |
|
| 581 |
[ y0 ] [ ?? ] |
| 582 |
2. <-- <SYN,ACK(SYN),M=y1> <-- |
| 583 |
(cache.M[B]= y1) |
| 584 |
|
| 585 |
[ y1 ] [ ?? ] |
| 586 |
3. --> <ACK(SYN),M=x2> --> (data1->user_B, |
| 587 |
cache.M[A]= x2) |
| 588 |
|
| 589 |
[ y1 ] [ x2 ] |
| 590 |
... (etc.) ... |
| 591 |
|
| 592 |
|
| 593 |
Figure 6. Server Host Crashed |
| 594 |
|
| 595 |
|
| 596 |
3.3 Accepting <SYN,ACK> Segments |
| 597 |
|
| 598 |
Transactions introduce a new hazard of erroneously accepting an |
| 599 |
old duplicate <SYN,ACK> segment. To be acceptable, a <SYN,ACK> |
| 600 |
segment must arrive in SYN-SENT state, and its ACK field must |
| 601 |
acknowledge something that was sent. In current TCPs the |
| 602 |
effective send window in SYN-SENT state is exactly one octet, and |
| 603 |
an acceptable <SYN,ACK> must exactly ACK this one octet. The |
| 604 |
clock-driven selection of Initial Sequence Number (ISN) makes an |
| 605 |
erroneous acceptance exceedingly unlikely. An old duplicate SYN |
| 606 |
could be accepted erroneously only if successive connection |
| 607 |
attempts occurred more often than once every 4 microseconds, or if |
| 608 |
the segment lifetime exceeded the 4 hour wraparound time for ISN |
| 609 |
|
| 610 |
|
| 611 |
|
| 612 |
<span class="grey">Braden [Page 11]</span></pre> |
| 613 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span> |
| 614 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 615 |
|
| 616 |
|
| 617 |
selection. |
| 618 |
|
| 619 |
However, when TCP is used for transactions, data sent with the |
| 620 |
initial SYN increases the range of sequence numbers that have been |
| 621 |
sent. This increases the danger of accepting an old duplicate |
| 622 |
<SYN,ACK> segment, and the consequences are more serious. In the |
| 623 |
example in Figure 7, segments 1-3 form a normal transaction |
| 624 |
sequence, and segment 4 begins a new transaction (incarnation) for |
| 625 |
the same connection. Segment #5 is a duplicate of segment #2 from |
| 626 |
the preceding transaction. Although the new transaction has a |
| 627 |
larger ISN, the previous ACK value 402 falls into the new range |
| 628 |
[200,700) of sequence numbers that have been sent, so segment #5 |
| 629 |
could be erroneously accepted and passed to the client as the |
| 630 |
response to the new request. |
| 631 |
|
| 632 |
<u>T</u><u>C</u><u>P</u>_<u>A</u> <u>T</u><u>C</u><u>P</u>_<u>B</u> |
| 633 |
|
| 634 |
CLOSED LISTEN |
| 635 |
|
| 636 |
1. --> <seq=100,SYN,data=300,FIN,M=x1> --> (TAO test OK) |
| 637 |
|
| 638 |
|
| 639 |
2. <-- <seq=800,ack=402,SYN,data=350,FIN,M=y1> <-- |
| 640 |
|
| 641 |
|
| 642 |
3. TIME-WAIT --> <ACK(FIN)> --> CLOSED |
| 643 |
(short timeout) |
| 644 |
CLOSED |
| 645 |
|
| 646 |
(New Request) |
| 647 |
4. --> <seq=200,SYN,data=500,FIN,M=x2> --> ... |
| 648 |
|
| 649 |
(Duplicate of segment #2) |
| 650 |
5. <-- <seq=800,ack=402,SYN,data=300,FIN,M=y1> <--... |
| 651 |
(Acceptable!!) |
| 652 |
|
| 653 |
|
| 654 |
Figure 7: Old Duplicate <SYN,ACK> Causing Error |
| 655 |
|
| 656 |
|
| 657 |
Unfortunately, we cannot simply use TAO on the client side to |
| 658 |
detect and reject old duplicate <SYN,ACK> segments. A TAO test at |
| 659 |
the client might fail for a valid <SYN,ACK> segment, due to out- |
| 660 |
of-order delivery, and this could result in permanent non-delivery |
| 661 |
of a valid transaction reply. |
| 662 |
|
| 663 |
Instead, we include a second M value, an echo of the client's M |
| 664 |
value from the initial <SYN> segment, in the <SYN,ACK> segment. A |
| 665 |
|
| 666 |
|
| 667 |
|
| 668 |
<span class="grey">Braden [Page 12]</span></pre> |
| 669 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span> |
| 670 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 671 |
|
| 672 |
|
| 673 |
specially-marked M value, SEG.M.ECHO, is used for this purpose. |
| 674 |
The client knows the value it sent in the initial <SYN> and can |
| 675 |
therefore positively validate the <SYN,ACK> using the echoed |
| 676 |
value. This is illustrated in Figure 12, which is the same as |
| 677 |
Figure 4 with the addition of the echoed value on the <SYN,ACK> |
| 678 |
segment #2. |
| 679 |
|
| 680 |
It should be noted that TCP allows a simultaneous open sequence in |
| 681 |
which both sides send and receive an initial <SYN> (see Figure 8 |
| 682 |
of [<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>]. In this case, the TAO test must be performed on |
| 683 |
both sides to preserve the symmetry. See [<a href="#ref-TTCP-FS" title=""Transaction TCP -- Functional Specification"">TTCP-FS</a>] for an |
| 684 |
example. |
| 685 |
|
| 686 |
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. SHORTENING TIME-WAIT STATE</span> |
| 687 |
|
| 688 |
Once a transaction has been initiated for a particular connection |
| 689 |
(pair of ports) between a given host pair, a new transaction for the |
| 690 |
same connection cannot take place for a time that is at least: |
| 691 |
|
| 692 |
RTT + SPT + TIME-WAIT_delay |
| 693 |
|
| 694 |
Since the client host can cycle among the 64512 available port |
| 695 |
numbers, an upper bound on the transaction rate between a particular |
| 696 |
host pair is: |
| 697 |
|
| 698 |
[<a id="ref-1">1</a>] TRmax = 64512 /(RTT + TIME-WAIT_Delay) |
| 699 |
|
| 700 |
in transactions per second (Tps), where we assumed SPT is negligible. |
| 701 |
We must reduce TIME-WAIT_Delay to support high-rate TCP transaction |
| 702 |
processing. |
| 703 |
|
| 704 |
TIME-WAIT state performs two functions: (1) supporting the full- |
| 705 |
duplex reliable close of TCP, and (2) allowing old duplicate segments |
| 706 |
from an earlier connection incarnation to expire before they can |
| 707 |
cause an error (see Appendix to [<a href="./rfc1185" title=""TCP Extension for High-Speed Paths"">RFC-1185</a>]). The first function |
| 708 |
impacts the application model of a TCP connection, which we would not |
| 709 |
want to change. The second is part of the fundamental machinery of |
| 710 |
TCP reliable delivery; to safely truncate TIME-WAIT state, we must |
| 711 |
provide another means to exclude duplicate packets from earlier |
| 712 |
incarnations of the connection. |
| 713 |
|
| 714 |
To minimize the delay in TIME-WAIT state while performing both |
| 715 |
functions, we propose to set the TIME-WAIT delay to: |
| 716 |
|
| 717 |
[<a id="ref-2">2</a>] TIME-WAIT_Delay = max( K*RTO, U ) |
| 718 |
|
| 719 |
where U and K are constants and RTO is the dynamically-determined |
| 720 |
retransmission timeout, the measured RTT plus an allowance for the |
| 721 |
|
| 722 |
|
| 723 |
|
| 724 |
<span class="grey">Braden [Page 13]</span></pre> |
| 725 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span> |
| 726 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 727 |
|
| 728 |
|
| 729 |
RTT variance [<a href="#ref-Jacobson88" title=""Congestion Avoidance and Control"">Jacobson88</a>]. We choose K large enough so that there is |
| 730 |
high probability of the close completing successfully if at all |
| 731 |
possible; K = 8 seems reasonable. This takes care of the first |
| 732 |
function of TIME-WAIT state. |
| 733 |
|
| 734 |
In a real implementation, there may be a minimum RTO value Tr, |
| 735 |
corresponding to the precision of RTO calculation. For example, in |
| 736 |
the popular BSD implementation of TCP, the minimum RTO is Tr = 0.5 |
| 737 |
second. Assuming K = 8 and U = 0, Eqns [<a href="#ref-1">1</a>] and [<a href="#ref-2">2</a>] impose an upper |
| 738 |
limit of TRmax = 16K Tps on the transaction rate of these |
| 739 |
implementations. |
| 740 |
|
| 741 |
It is possible to have many short connections only if RTO is very |
| 742 |
small, in which case the TIME-WAIT delay [<a href="#ref-2">2</a>] reduces to U. To |
| 743 |
accelerate the close sequence, we need to reduce U below the MSL |
| 744 |
enforced by the IP layer, without introducing a hazard from old |
| 745 |
duplicate segments. For this purpose, we introduce another monotonic |
| 746 |
number sequence; call it X. X values are required to be monotonic |
| 747 |
between successive connection incarnations; depending upon the choice |
| 748 |
of the X space (see <a href="#section-5">Section 5</a>), X values may also increase during a |
| 749 |
connection. A value from the X space is to be carried in every |
| 750 |
segment, and a segment is rejected if it is received with an X value |
| 751 |
smaller than the largest X value received. This mechanism does not |
| 752 |
use a cache; the largest X value is maintained in the TCP connection |
| 753 |
control block (TCB) for each connection. |
| 754 |
|
| 755 |
The value of U depends upon the choice for the X space, discussed in |
| 756 |
the next section. If X is time-like, U can be set to twice the time |
| 757 |
granularity (i.e, twice the minimum "tick" time) of X. The TIME-WAIT |
| 758 |
delay will then ensure that current X values do not overlap the X |
| 759 |
values of earlier incarnations of the same connection. Another |
| 760 |
consequence of time-like X values is the possibility that an open but |
| 761 |
idle connection might allow the X value to wrap its sign bit, |
| 762 |
resulting in a lockup of the connection. To prevent this, a 24-day |
| 763 |
idle timer on each open connection could bypass the X check on the |
| 764 |
first segment following the idle period, for example. In practice, |
| 765 |
many implementations have keep-alive mechanisms that prevent such |
| 766 |
long idle periods [<a href="./rfc1323" title="D.">RFC-1323</a>]. |
| 767 |
|
| 768 |
Referring back to Figure 4, our proposed transaction extension |
| 769 |
results in a minimum exchange of 3 packets. Segment #3, the final |
| 770 |
ACK segment, does not increase transaction latency, but in |
| 771 |
combination with the TIME-WAIT delay of K*RTO it ensures that the |
| 772 |
server side of the connection will be closed before a new transaction |
| 773 |
is issued for this same pair of ports. It also provides an RTT |
| 774 |
measurement for the server. |
| 775 |
|
| 776 |
We may ask whether it would be possible to further reduce the TIME- |
| 777 |
|
| 778 |
|
| 779 |
|
| 780 |
<span class="grey">Braden [Page 14]</span></pre> |
| 781 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span> |
| 782 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 783 |
|
| 784 |
|
| 785 |
WAIT delay. We might set K to zero; alternatively, we might allow |
| 786 |
the client TCP to start a new transaction request while the |
| 787 |
connection was still in TIME-WAIT state, with the new initial SYN |
| 788 |
acting as an implied acknowledgment of the previous FIN. <a href="#appendix-A">Appendix A</a> |
| 789 |
summarizes the issues raised by these alternatives, which we call |
| 790 |
"truncating" TIME-WAIT state, and suggests some possible solutions. |
| 791 |
Further study would be required, but these solutions appear to bend |
| 792 |
the theory and/or implementations of the TCP protocol farther than we |
| 793 |
wish to bend them. |
| 794 |
|
| 795 |
We therefore propose using formula [<a href="#ref-2">2</a>] with K=8 and retaining the |
| 796 |
final ACK(FIN) transmission. To raise the transaction rate, |
| 797 |
therefore, we require small values of RTO and U. |
| 798 |
|
| 799 |
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. CHOOSING A MONOTONIC SEQUENCE</span> |
| 800 |
|
| 801 |
For simplicity, we want the monotonic sequence X used for shortening |
| 802 |
TIME-WAIT state to be identical to the monotonic sequence M for |
| 803 |
bypassing the 3-way handshake. Calling the common space M, we will |
| 804 |
send an M value SEG.M in each TCP segment. Upon receipt of an |
| 805 |
initial SYN segment, SEG.M will be compared with a per-host cached |
| 806 |
value to authenticate the SYN without a 3-way handshake; this is the |
| 807 |
TAO mechanism. Upon receipt of a non-SYN segment, SEG.M will be |
| 808 |
compared with the current value in the connection control block and |
| 809 |
used to discard old duplicates. |
| 810 |
|
| 811 |
Note that the situation with TIME-WAIT state differs from that of |
| 812 |
bypassing 3-way handshakes in two ways: (a) TIME-WAIT requires |
| 813 |
duplicate detection on every segment vs. only on SYN segments, and |
| 814 |
(b) TIME-WAIT applies to a single connection vs. being global across |
| 815 |
all connections. This section discusses possible choices for the |
| 816 |
common monotonic sequence. |
| 817 |
|
| 818 |
The SEG.M values must satisfy the following requirements. |
| 819 |
|
| 820 |
* The values must be monotonic; this requirement is defined more |
| 821 |
precisely below. |
| 822 |
|
| 823 |
* Their granularity must be fine-grained enough to support a high |
| 824 |
rate of transaction processing; the M clock must "tick" at least |
| 825 |
once between successive transactions. |
| 826 |
|
| 827 |
* Their range (wrap-around time) must be great enough to allow a |
| 828 |
realistic MSL to be enforced by the network. |
| 829 |
|
| 830 |
The TCP spec calls for an MSL of 120 secs. Since much of the |
| 831 |
Internet does not carefully enforce this limit, it would be safer to |
| 832 |
have an MSL at least an order of magnitude larger. We set as an |
| 833 |
|
| 834 |
|
| 835 |
|
| 836 |
<span class="grey">Braden [Page 15]</span></pre> |
| 837 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span> |
| 838 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 839 |
|
| 840 |
|
| 841 |
objective an MSL of at least 2000 seconds. If there were no TIME- |
| 842 |
WAIT delay, the ultimate limit on transaction rate would be set by |
| 843 |
speed-of-light delays in the network and by the latency of host |
| 844 |
operating systems. As the bottleneck problems with interfacing CPUs |
| 845 |
to gigabit LANs are solved, we can imagine transaction durations as |
| 846 |
short as 1 microsecond. Therefore, we set an ultimate performance |
| 847 |
goal of TRmax at least 10**6 Tps. |
| 848 |
|
| 849 |
A particular connection between hosts A and B is identified by the |
| 850 |
local and remote TCP "sockets", i.e., by the quadruplet: {A, B, |
| 851 |
Port.A, Port.B}. Imagine that each host keeps a count CC of the |
| 852 |
number of TCP connections it has initiated. We can use this CC |
| 853 |
number to distinguish different incarnations of the same connection. |
| 854 |
Then a particular SEG.M value may be labeled implicitly by 6 |
| 855 |
quantities: {A, B, Port.A, Port.B, CC, n}, where n is the byte offset |
| 856 |
of that segment within the connection incarnation. |
| 857 |
|
| 858 |
To bypass the 3-way handshake, we require thgt SEG.M values on |
| 859 |
successive SYN segments from a host A to a host B be monotone |
| 860 |
increasing. If CC' > CC, then we require that: |
| 861 |
|
| 862 |
SEG.M(A,B,Port.A,Port.B,CC',0) > SEG.M(A,B,Port.A,Port.B,CC,0) |
| 863 |
|
| 864 |
for any legal values of Port.A and Port.B. |
| 865 |
|
| 866 |
To delete old duplicates (allowing TIME-WAIT state to be shortened), |
| 867 |
we require that SEG.M values be disjoint across different |
| 868 |
incarnations of the same connection. If CC' > CC then |
| 869 |
|
| 870 |
SEG.M(A,B,Port.A,Port.B,CC',n') > SEG.M(A,B,Port.A,Port.B,CC,n), |
| 871 |
|
| 872 |
for any non-negative integers n and n'. |
| 873 |
|
| 874 |
We now consider four different choices for the common monotonic |
| 875 |
space: <a href="./rfc1323">RFC-1323</a> timestamps, TCP sequence numbers, the connection |
| 876 |
count, and 64-bit TCP sequence numbers. The results are summarized |
| 877 |
in Table I. |
| 878 |
|
| 879 |
5.1 Cached Timestamps |
| 880 |
|
| 881 |
The PAWS mechanism [<a href="./rfc1323" title="D.">RFC-1323</a>] uses TCP "timestamps" as |
| 882 |
monotonically increasing integers in order to throw out old |
| 883 |
duplicate segments within the same incarnation. Jacobson |
| 884 |
suggested the cacheing of these timestamps for bypassing 3-way |
| 885 |
handshakes [<a href="#ref-Jacobson90" title="private communication">Jacobson90</a>], i.e., that TCP timestamps be used for our |
| 886 |
common monotonic space M. This idea is attractive since it would |
| 887 |
allow the same timestamp options to be used for RTTM, PAWS, and |
| 888 |
transactions. |
| 889 |
|
| 890 |
|
| 891 |
|
| 892 |
<span class="grey">Braden [Page 16]</span></pre> |
| 893 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span> |
| 894 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 895 |
|
| 896 |
|
| 897 |
To obtain at-most-once service, the criterion for immediate |
| 898 |
acceptance of a SYN must be that SEG.M is strictly greater than |
| 899 |
the cached M value. That is, to be useful for bypassing 3-way |
| 900 |
handshakes, the timestamp clock must tick at least once between |
| 901 |
any two successive transactions between the same pair of hosts |
| 902 |
(even if different ports are used). Hence, the timestamp clock |
| 903 |
rate would determine TRmax, the maximum possible transaction rate. |
| 904 |
|
| 905 |
Unfortunately, the timestamp clock frequency called for by <a href="./rfc1323">RFC-</a> |
| 906 |
<a href="./rfc1323">1323</a>, in the range 1 sec to 1 ms, is much too slow for |
| 907 |
transactions. The TCP timestamp period was chosen to be |
| 908 |
comparable to the fundamental interval for computing and |
| 909 |
scheduling retransmission timeouts; this is generally in the range |
| 910 |
of 1 sec. to 1 ms., and in many operating systems, much closer to |
| 911 |
1 second. Although it would be possible to increase the timestamp |
| 912 |
clock frequency by several orders of magnitude, to do so would |
| 913 |
make implementation more difficult, and on some systems |
| 914 |
excessively expensive. |
| 915 |
|
| 916 |
The wraparound time for TCP timestamps, at least 24 days, causes |
| 917 |
no problem for transactions. |
| 918 |
|
| 919 |
The PAWS mechanism uses TCP timestamps to protect against old |
| 920 |
duplicate non-SYN segments from the same incarnation [<a href="./rfc1323" title="D.">RFC-1323</a>]. |
| 921 |
It can also be used to protect against old duplicate data segments |
| 922 |
from earlier incarnations (and therefore allow shortening of |
| 923 |
TIME-WAIT state) if we can ensure that the timestamp clock ticks |
| 924 |
at least once between the end of one incarnation and the beginning |
| 925 |
of the next. This can be achieved by setting U = 2 seconds, i.e., |
| 926 |
to twice the maximum timestamp clock period. This value in |
| 927 |
formula [<a href="#ref-2">2</a>] leads to an upper bound TRmax = 32K Tps between a host |
| 928 |
pair. However, as pointed out above, old duplicate SYN detection |
| 929 |
using timestamps leads to a smaller transaction rate bound, 1 Tps, |
| 930 |
which is unacceptable. In addition, the timestamp approach is |
| 931 |
imperfect; it allows old ACK segments to enter the new connection |
| 932 |
where they can cause a disconnect. This happens because old |
| 933 |
duplicate ACKs that arrive during TIME-WAIT state generate new |
| 934 |
ACKs with the current timestamp [<a href="./rfc1337" title=""TIME-WAIT Assassination Hazards in TCP"">RFC-1337</a>]. |
| 935 |
|
| 936 |
We therefore conclude that timestamps are not adequate as the |
| 937 |
monotonic space M; see Table I. However, they may still be useful |
| 938 |
to effectively extend some other monotonic number space, just as |
| 939 |
they are used in PAWS to extend the TCP sequence number space. |
| 940 |
This is discussed below. |
| 941 |
|
| 942 |
|
| 943 |
|
| 944 |
|
| 945 |
|
| 946 |
|
| 947 |
|
| 948 |
<span class="grey">Braden [Page 17]</span></pre> |
| 949 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span> |
| 950 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 951 |
|
| 952 |
|
| 953 |
5.2 Current TCP Sequence Numbers |
| 954 |
|
| 955 |
It is useful to understand why the existing 32-bit TCP sequence |
| 956 |
numbers do not form an appropriate monotonic space for |
| 957 |
transactions. |
| 958 |
|
| 959 |
The sequence number sent in an initial SYN is called the Initial |
| 960 |
Sequence Number or ISN. According to the TCP specification, an |
| 961 |
ISN is to be selected using: |
| 962 |
|
| 963 |
[<a id="ref-3">3</a>] ISN = (R*T) mod 2**32 |
| 964 |
|
| 965 |
where T is the real time in seconds (from an arbitrary origin, |
| 966 |
fixed when the system is started) and R is a constant, currently |
| 967 |
250 KBps. These ISN values form a monotonic time sequence that |
| 968 |
wraps in 4.55 hours = 16380 seconds and has a granularity of 4 |
| 969 |
usecs. For transaction rates up to roughly 250K Tps, the ISN |
| 970 |
value calculated by formula [<a href="#ref-3">3</a>] will be monotonic and could be |
| 971 |
used for bypassing the 3-way handshake. |
| 972 |
|
| 973 |
However, TCP sequence numbers (alone) could not be used to shorten |
| 974 |
TIME-WAIT state, because there are several ways that overlap of |
| 975 |
the sequence space of successive incarnations can occur (as |
| 976 |
described in Appendix to [<a href="./rfc1185" title=""TCP Extension for High-Speed Paths"">RFC-1185</a>]). One way is a "fast |
| 977 |
connection", with a transfer rate greater than R; another is a |
| 978 |
"long" connection, with a duration of approximately 4.55 hours. |
| 979 |
TIME-WAIT delay is necessary to protect against these cases. With |
| 980 |
the official delay of 240 seconds, formula [<a href="#ref-1">1</a>] implies a upper |
| 981 |
bound (as RTT -> 0) of TRmax = 268 Tps; with our target MSL of |
| 982 |
2000 sec, TRmax = 32 Tps. These values are unacceptably low. |
| 983 |
|
| 984 |
To improve this transaction rate, we could use TCP timestamps to |
| 985 |
effectively extend the range of the TCP sequence numbers. |
| 986 |
Timestamps would guard against sequence number wrap-around and |
| 987 |
thereby allow us to increase R in [<a href="#ref-3">3</a>] to exceed the maximum |
| 988 |
possible transfer rate. Then sequence numbers for successive |
| 989 |
incarnations could not overlap. Timestamps would also provide |
| 990 |
safety with an MSL as large as 24 days. We could then set U = 0 |
| 991 |
in the TIME-WAIT delay calculation [<a href="#ref-2">2</a>]. For example, R = 10**9 |
| 992 |
Bps leads to TRmax <= 10**9 Tps. See 2(b) in Table I. These |
| 993 |
values would more than satisfy our objectives. |
| 994 |
|
| 995 |
We should make clear how this proposal, sequence numbers plus |
| 996 |
timestamps, differs from the timestamps alone discussed (and |
| 997 |
rejected) in the previous section. The difference lies in what is |
| 998 |
cached and tested for TAO; the proposal here is to cache and test |
| 999 |
BOTH the latest TCP sequence number and the latest TCP timestamp. |
| 1000 |
In effect, we are proposing to use timestamps to logically extend |
| 1001 |
|
| 1002 |
|
| 1003 |
|
| 1004 |
<span class="grey">Braden [Page 18]</span></pre> |
| 1005 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span> |
| 1006 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1007 |
|
| 1008 |
|
| 1009 |
the sequence space to 64 bits. Another alternative, presented in |
| 1010 |
the next section, is to directly expand the TCP sequence space to |
| 1011 |
64 bits. |
| 1012 |
|
| 1013 |
Unfortunately, the proposed solution (TCP sequence numbers plus |
| 1014 |
timestamps) based on equation [<a href="#ref-3">3</a>] would be difficult or impossible |
| 1015 |
to implement on many systems, which base their TCP implementation |
| 1016 |
upon a very low granularity software clock, typically O(1 sec). |
| 1017 |
To adapt the procedure to a system with a low granularity software |
| 1018 |
clock, suppose that we calculate the ISN as: |
| 1019 |
|
| 1020 |
[<a id="ref-4">4</a>] ISN = ( R*Ts*floor(T/Ts) + q*CC) mod 2**32 |
| 1021 |
|
| 1022 |
where Ts is the time per tick of the software clock, CC is the |
| 1023 |
connection count, and q is a constant. That is, the ISN is |
| 1024 |
incremented by the constant R*Ts once every clock tick and by the |
| 1025 |
constant q for every new connection. We need to choose q to |
| 1026 |
obtain the required monotonicity. |
| 1027 |
|
| 1028 |
For monotonicity of the ISN's themselves, q=1 suffices. However, |
| 1029 |
monotonicity during the entire connection requires q = R*Ts. This |
| 1030 |
value of q can be deduced as follows. Let S(T, CC, n) be the |
| 1031 |
sequence number for byte offset n in a connection with number CC |
| 1032 |
at time T: |
| 1033 |
|
| 1034 |
S(T, CC, n) = (R*Ts*floor(T/Ts) + q*CC + n) mod 2**32. |
| 1035 |
|
| 1036 |
For any T1 > T2, we require that: S(T2, CC+1, 0) - S(T1, CC, n) > |
| 1037 |
0 for all n. Since R is assumed to be an upper bound on the |
| 1038 |
transfer rate, we can write down: |
| 1039 |
|
| 1040 |
R > n/(T2 - T1), or T2/Ts - T1/Ts > n/(R*Ts) |
| 1041 |
|
| 1042 |
Using the relationship: floor(x)-floor(y) > x-y-1 and a little |
| 1043 |
algebra leads to the conclusion that using q = R*Ts creates the |
| 1044 |
required monotonic number sequence. Therefore, we consider: |
| 1045 |
|
| 1046 |
[<a id="ref-5">5</a>] ISN = R*Ts*(floor(T/Ts) + CC) mod 2**32 |
| 1047 |
|
| 1048 |
(which is the algorithm used for ISN selection by BSD TCP). |
| 1049 |
|
| 1050 |
For error-free operation, the sequence numbers generated by [<a href="#ref-5">5</a>] |
| 1051 |
must not wrap the sign bit in less than MSL seconds. Since CC |
| 1052 |
cannot increase faster than TRmax, the safe condition is: |
| 1053 |
|
| 1054 |
R* (1 + Ts*TRmax) * MSL < 2**31. |
| 1055 |
|
| 1056 |
We are interested in the case: Ts*TRmax >> 1, so this relationship |
| 1057 |
|
| 1058 |
|
| 1059 |
|
| 1060 |
<span class="grey">Braden [Page 19]</span></pre> |
| 1061 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span> |
| 1062 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1063 |
|
| 1064 |
|
| 1065 |
reduces to: |
| 1066 |
|
| 1067 |
[<a id="ref-6">6</a>] R * Ts * TRmax * MSL < 2**31. |
| 1068 |
|
| 1069 |
This shows a direct trade-off among the maximum effective |
| 1070 |
bandwidth R, the maximum transaction rate TRmax, and the maximum |
| 1071 |
segment lifetime MSL. For reasonable limiting values of R, Ts, |
| 1072 |
and MSL, formula [<a href="#ref-6">6</a>] leads to a very low value of TRmax. For |
| 1073 |
example, with MSL= 2000 secs, R=10**9 Bps, and Ts = 0.5 sec, TRmax |
| 1074 |
< 2*10**-3 Tps. |
| 1075 |
|
| 1076 |
To ease the situation, we could supplement sequence numbers with |
| 1077 |
timestamps. This would allow an effective MSL of 2 seconds in |
| 1078 |
[<a href="#ref-6">6</a>], since longer times would be protected by differing |
| 1079 |
timestamps. Then TRmax < 2**30/(R*Ts). The actual enforced MSL |
| 1080 |
would be increased to 24 days. Unfortunately, TRmax would still |
| 1081 |
be too small, since we want to support transfer rates up to R ~ |
| 1082 |
10**9 Bps. Ts = 0.5 sec would imply TRmax ~ 2 Tps. On many |
| 1083 |
systems, it appears infeasible to decrease Ts enough to obtain an |
| 1084 |
acceptable TRmax using this approach. |
| 1085 |
|
| 1086 |
5.3 64-bit TCP Sequence Numbers |
| 1087 |
|
| 1088 |
Another possibility would be to simply increase the TCP sequence |
| 1089 |
space to 64 bits as suggested in [<a href="./rfc1263" title=""TCP Extensions Considered Harmful"">RFC-1263</a>]. We would also |
| 1090 |
increase the R value for clock-driven ISN selection, beyond the |
| 1091 |
fastest transfer rate of which the host is capable. A reasonable |
| 1092 |
upper limit might be R = 10**9 Bps. As noted above, in a |
| 1093 |
practical implementation we would use: |
| 1094 |
|
| 1095 |
ISN = R*Ts*( floor(T/Ts) + CC) mod 2**64 |
| 1096 |
|
| 1097 |
leading to: |
| 1098 |
|
| 1099 |
R*(1 + Ts * TRmax) * MSL < 2**63 |
| 1100 |
|
| 1101 |
For example, suppose that R = 10**9 Bps, Ts = 0.5, and MSL = 16K |
| 1102 |
secs (4.4 hrs); then this result implies that TRmax < 10**6 Tps. |
| 1103 |
We see that adding 32 bits to the sequence space has provided |
| 1104 |
feasible values for transaction processing. |
| 1105 |
|
| 1106 |
5.4 Connection Counts |
| 1107 |
|
| 1108 |
The Connection Count CC is well suited to be the monotonic |
| 1109 |
sequence M, since it "ticks" exactly once for each new connection |
| 1110 |
incarnation and is constant within a single incarnation. Thus, it |
| 1111 |
perfectly separates segments from different incarnations of the |
| 1112 |
same connection and would allow U = 0 in the TIME-WAIT state delay |
| 1113 |
|
| 1114 |
|
| 1115 |
|
| 1116 |
<span class="grey">Braden [Page 20]</span></pre> |
| 1117 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span> |
| 1118 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1119 |
|
| 1120 |
|
| 1121 |
formula [<a href="#ref-2">2</a>]. (Strictly, U cannot be reduced below 1/R = 4 usec, |
| 1122 |
as noted in <a href="#section-4">Section 4</a>. However, this is of little practical |
| 1123 |
consequence until the ultimate limits on TRmax are approached). |
| 1124 |
|
| 1125 |
Assume that CC is a 32-bit number. To prevent wrap-around in the |
| 1126 |
sign bit of CC in less than MSL seconds requires that: |
| 1127 |
|
| 1128 |
TRmax * MSL < 2**31 |
| 1129 |
|
| 1130 |
For example, if MSL = 2000 seconds then TRmax < 10**6 Tp. These |
| 1131 |
are acceptable limits for transaction processing. However, if |
| 1132 |
they are not, we could augment CC with TCP timestamps to obtain |
| 1133 |
very far-out limits, as discussed below. |
| 1134 |
|
| 1135 |
It would be an implementation choice at the client whether CC is |
| 1136 |
global for all destinations or private to each destination host |
| 1137 |
(and maintained in the per-host cache). In the latter case, the |
| 1138 |
last CC value assigned for each remote host could also be |
| 1139 |
maintained in the per-host cache. Since there is not typically a |
| 1140 |
large amount of parallelism in the network connection of a host, |
| 1141 |
there should be little difference in the performance of these two |
| 1142 |
different approaches, and the single global CC value is certainly |
| 1143 |
simpler. |
| 1144 |
|
| 1145 |
To augment CC with TCP timestamps, we would bypass a 3-way |
| 1146 |
handshake if both SEG.CC > cache.CC[A] and SEG.TSval >= |
| 1147 |
cache.TS[A]. The timestamp check would detect a SYN older than 2 |
| 1148 |
seconds, so that the effective wrap-around requirement would be: |
| 1149 |
|
| 1150 |
TRmax * 2 < 2**31 |
| 1151 |
|
| 1152 |
i.e., TRmax < 10**9 Tps. The required MSL would be raised to 24 |
| 1153 |
days. Using timestamps in this way, we could reduce the size of |
| 1154 |
CC. For example, suppose CC were 16 bits. Then the wrap-around |
| 1155 |
condition TRmax * 2 < 2**15 implies that TRmax is 16K. |
| 1156 |
|
| 1157 |
Finally, note that using CC to delete old duplicates from earlier |
| 1158 |
incarnations would not obviate the need for the time-stamp-based |
| 1159 |
PAWS mechanism to prevent errors within a single incarnation due |
| 1160 |
to wrapping the 32-bit TCP sequence space at very high transfer |
| 1161 |
rates. |
| 1162 |
|
| 1163 |
5.5 Conclusions |
| 1164 |
|
| 1165 |
The alternatives for monotonic sequence are summarized in Table I. |
| 1166 |
We see that there are two feasible choices for the monotonic |
| 1167 |
space: the connection count and 64-bit sequence numbers. Of these |
| 1168 |
two, we believe that the simpler is the connection count. |
| 1169 |
|
| 1170 |
|
| 1171 |
|
| 1172 |
<span class="grey">Braden [Page 21]</span></pre> |
| 1173 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span> |
| 1174 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1175 |
|
| 1176 |
|
| 1177 |
Implementation of 64-bit sequence numbers would require |
| 1178 |
negotiation of a new header format and expansion of all variables |
| 1179 |
and calculations on the sequence space. CC can be carried in an |
| 1180 |
option and need be examined only once per packet. |
| 1181 |
|
| 1182 |
We propose to use a simple 32-bit connection count CC, without |
| 1183 |
augmentation with timestamps, for the transaction extension. This |
| 1184 |
choice has the advantages of simplicity and directness. Its |
| 1185 |
drawback is that it adds a third sequence-like space (in addition |
| 1186 |
to the TCP sequence number and the TCP timestamp) to each TCP |
| 1187 |
header and to the main line of packet processing. However, the |
| 1188 |
additional code is in fact very modest. |
| 1189 |
|
| 1190 |
We now have a general outline of the proposed TCP extensions for |
| 1191 |
transactions. |
| 1192 |
|
| 1193 |
o A host maintains a 32-bit global connection counter variable CC. |
| 1194 |
|
| 1195 |
o The sender's current CC value is carried in an option in every |
| 1196 |
TCP segment. |
| 1197 |
|
| 1198 |
o CC values are cached per host, and the TAO mechanism is used to |
| 1199 |
bypass the 3-way handshake when possible. |
| 1200 |
|
| 1201 |
o In non-SYN segments, the CC value is used to reject duplicates |
| 1202 |
from earlier incarnations. This allows TIME-WAIT state delay to |
| 1203 |
be reduced to K*RTO (i.e., U=0 in Eq. [<a href="#ref-2">2</a>]). |
| 1204 |
|
| 1205 |
|
| 1206 |
|
| 1207 |
|
| 1208 |
|
| 1209 |
|
| 1210 |
|
| 1211 |
|
| 1212 |
|
| 1213 |
|
| 1214 |
|
| 1215 |
|
| 1216 |
|
| 1217 |
|
| 1218 |
|
| 1219 |
|
| 1220 |
|
| 1221 |
|
| 1222 |
|
| 1223 |
|
| 1224 |
|
| 1225 |
|
| 1226 |
|
| 1227 |
|
| 1228 |
<span class="grey">Braden [Page 22]</span></pre> |
| 1229 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span> |
| 1230 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1231 |
|
| 1232 |
|
| 1233 |
TABLE I: Summary of Monotonic Sequences |
| 1234 |
|
| 1235 |
APPROACH TRmax (Tps) Required MSL COMMENTS |
| 1236 |
__________________________________________________________________ |
| 1237 |
|
| 1238 |
1. Timestamp & PAWS 1 24 days TRmax is |
| 1239 |
too small |
| 1240 |
__________________________________________________________________ |
| 1241 |
|
| 1242 |
2. Current TCP Sequence Numbers |
| 1243 |
|
| 1244 |
(a) clock-driven |
| 1245 |
ISN: eq. [<a href="#ref-3">3</a>] 268 240 secs TRmax & MSL |
| 1246 |
too small |
| 1247 |
|
| 1248 |
(b) Timestamps& clock- |
| 1249 |
driven ISN [<a href="#ref-3">3</a>] & 10**9 24 days Hard to |
| 1250 |
R=10**9 implement |
| 1251 |
|
| 1252 |
(c) Timestamps & c-dr |
| 1253 |
ISN: eq. [<a href="#ref-4">4</a>] 2**30/(R*Ts) 24 days TRmax too |
| 1254 |
small. |
| 1255 |
__________________________________________________________________ |
| 1256 |
|
| 1257 |
3. 64-bit TCP Sequence Numbers |
| 1258 |
|
| 1259 |
2**63/(MSL*R*Ts) MSL Significant |
| 1260 |
TCP change |
| 1261 |
e.g., R=10**9 Bps, |
| 1262 |
MSL = 4.4 hrs, |
| 1263 |
Ts = 0.5 sec=> |
| 1264 |
TRmax = 10**6 |
| 1265 |
__________________________________________________________________ |
| 1266 |
|
| 1267 |
4. Connection Counts |
| 1268 |
|
| 1269 |
(a) no timestamps 2**31/MSL MSL 3rd sequence |
| 1270 |
e.g., MSL=2000 sec space |
| 1271 |
TRmax = 10**6 |
| 1272 |
|
| 1273 |
(b) with timestamps 2**30 24 days (ditto) |
| 1274 |
and PAWS |
| 1275 |
__________________________________________________________________ |
| 1276 |
|
| 1277 |
|
| 1278 |
|
| 1279 |
|
| 1280 |
|
| 1281 |
|
| 1282 |
|
| 1283 |
|
| 1284 |
<span class="grey">Braden [Page 23]</span></pre> |
| 1285 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span> |
| 1286 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1287 |
|
| 1288 |
|
| 1289 |
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. CONNECTION STATES</span> |
| 1290 |
|
| 1291 |
TCP has always allowed a connection to be half-closed. TAO makes a |
| 1292 |
significant addition to TCP semantics by allowing a connection to be |
| 1293 |
half-synchronized, i.e., to be open for data transfer in one |
| 1294 |
direction before the other direction has been opened. Thus, the |
| 1295 |
passive end of a connection (which receives an initial SYN) can |
| 1296 |
accept data and even a FIN bit before its own SYN has been |
| 1297 |
acknowledged. This SYN, data, and FIN may arrive on a single segment |
| 1298 |
(as in Figure 4), or on multiple segments; packetization makes no |
| 1299 |
difference to the logic of the finite-state machine (FSM) defining |
| 1300 |
transitions among connection states. |
| 1301 |
|
| 1302 |
Half-synchronized connections have several consequences. |
| 1303 |
|
| 1304 |
(a) The passive end must provide an implied initial data window in |
| 1305 |
order to accept data. The minimum size of this implied window |
| 1306 |
is a parameter in the specification; we suggest 4K bytes. |
| 1307 |
|
| 1308 |
(b) New connection states and transitions are introduced into the |
| 1309 |
TCP FSM at both ends of the connection. At the active end, new |
| 1310 |
states are required to piggy-back the FIN on the initial SYN |
| 1311 |
segment. At the passive end, new states are required for a |
| 1312 |
half-synchronized connection. |
| 1313 |
|
| 1314 |
This section develops the resulting FSM description of a TCP |
| 1315 |
connection as a conventional state/transition diagram. To develop a |
| 1316 |
complete FSM, we take a constructive approach, as follows: (1) write |
| 1317 |
down all possible events; (2) write down the precedence rules that |
| 1318 |
govern the order in which events may occur; (3) construct the |
| 1319 |
resulting FSM; and (4) augment it to support TAO. In principle, we |
| 1320 |
do this separately for the active and passive ends; however, the |
| 1321 |
symmetry of TCP results in the two FSMs being almost entirely |
| 1322 |
coincident. |
| 1323 |
|
| 1324 |
Figure 8 lists all possible state transitions for a TCP connection in |
| 1325 |
the absence of TAO, as elementary events and corresponding actions. |
| 1326 |
Each transition is labeled with a letter. Transitions a-g are used |
| 1327 |
by the active side, and c-i are used by the passive side. Without |
| 1328 |
TAO, transition "c" (event "rcv ACK(SYN)") synchronizes the |
| 1329 |
connection, allowing data to be accepted for the user. |
| 1330 |
|
| 1331 |
By definition, the first transition for an active (or passive) side |
| 1332 |
must be "a" (or "i", respectively). During a single instance of a |
| 1333 |
connection, the active side will progress through some permutation of |
| 1334 |
the complete sequence of transitions {a b c d e f } or the sequence |
| 1335 |
{a b c d e f g}. The set of possible permutations is determined by |
| 1336 |
precedence rules governing the order in which transitions can occur. |
| 1337 |
|
| 1338 |
|
| 1339 |
|
| 1340 |
<span class="grey">Braden [Page 24]</span></pre> |
| 1341 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-25" ></span> |
| 1342 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1343 |
|
| 1344 |
|
| 1345 |
Label Event / Action |
| 1346 |
_____ ________________________ |
| 1347 |
a OPEN / snd SYN |
| 1348 |
|
| 1349 |
b rcv SYN [No TAO]/ snd ACK(SYN) |
| 1350 |
|
| 1351 |
c rcv ACK(SYN) / |
| 1352 |
|
| 1353 |
d CLOSE / snd FIN |
| 1354 |
|
| 1355 |
e rcv FIN / snd ACK(FIN) |
| 1356 |
|
| 1357 |
f rcv ACK(FIN) / |
| 1358 |
|
| 1359 |
g timeout=2MSL / delete TCB |
| 1360 |
___________________________________________________ |
| 1361 |
h passive OPEN / create TCB |
| 1362 |
|
| 1363 |
i rcv SYN [No TAO]/ snd SYN, ACK(SYN) |
| 1364 |
___________________________________________________ |
| 1365 |
|
| 1366 |
Figure 8. Basic TCP Connection Transitions |
| 1367 |
|
| 1368 |
|
| 1369 |
Using the notation "<." to mean "must precede", the precedence rules |
| 1370 |
are: |
| 1371 |
|
| 1372 |
(1) Logical ordering: must open connection before closing it: |
| 1373 |
|
| 1374 |
b <. e |
| 1375 |
|
| 1376 |
(2) Causality -- cannot receive ACK(x) before x has been sent: |
| 1377 |
|
| 1378 |
a <. c and i <. c and d <. f |
| 1379 |
|
| 1380 |
(3) Acknowledgments are cumulative |
| 1381 |
|
| 1382 |
c <. f |
| 1383 |
|
| 1384 |
(4) First packet in each direction must contain a SYN. |
| 1385 |
|
| 1386 |
b <. c and b <. f |
| 1387 |
|
| 1388 |
(5) TIME-WAIT state |
| 1389 |
|
| 1390 |
Whenever d precedes e in the sequence, g must be the last |
| 1391 |
transition. |
| 1392 |
|
| 1393 |
|
| 1394 |
|
| 1395 |
|
| 1396 |
<span class="grey">Braden [Page 25]</span></pre> |
| 1397 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-26" ></span> |
| 1398 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1399 |
|
| 1400 |
|
| 1401 |
Applying these rules, we can enumerate all possible permutations of |
| 1402 |
the events and summarize them in a state transition diagram. Figure |
| 1403 |
9 shows the result, with boxes representing the states and directed |
| 1404 |
arcs representing the transitions. |
| 1405 |
|
| 1406 |
________ ________ |
| 1407 |
| | h | | |
| 1408 |
| CLOSED |--------->| LISTEN | |
| 1409 |
|________| |________| |
| 1410 |
| | |
| 1411 |
| a | i |
| 1412 |
____V____ ____V___ ________ |
| 1413 |
| | b | | e | | |
| 1414 |
| |--------->| |-------------->| | |
| 1415 |
|________| |________| |________| |
| 1416 |
/ / | / | |
| 1417 |
/ / | c d / | c |
| 1418 |
/ / __V_____ | ____V___ |
| 1419 |
/ / | | e | | | |
| 1420 |
d | d / | |------------>| | |
| 1421 |
| | |________| | |________| |
| 1422 |
| | | | | |
| 1423 |
| | | ___V____ | |
| 1424 |
| | | | | | |
| 1425 |
| | | | | | |
| 1426 |
| | | |________| | |
| 1427 |
| | | | | |
| 1428 |
____V___ ______V_ | ________ | | |
| 1429 |
| | b | | e | | | | | |
| 1430 |
| |------->| |--------->| | | | |
| 1431 |
|________| |________| | |________| | | |
| 1432 |
| / | | | |
| 1433 |
c | / d c | c | d | |
| 1434 |
| / | | | |
| 1435 |
_V___V__ ____V___ V_____V_ |
| 1436 |
| | e | | | | |
| 1437 |
| |---->| | | | |
| 1438 |
|________| |________| |________| |
| 1439 |
| | | |
| 1440 |
| f | f | f |
| 1441 |
____V___ ____V___ ___V____ |
| 1442 |
| | e | TIME- | g | | |
| 1443 |
| |---->| WAIT |-->| CLOSED | |
| 1444 |
|________| |________| |________| |
| 1445 |
|
| 1446 |
|
| 1447 |
Figure 9: Basic State Diagram |
| 1448 |
|
| 1449 |
|
| 1450 |
|
| 1451 |
|
| 1452 |
<span class="grey">Braden [Page 26]</span></pre> |
| 1453 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-27" ></span> |
| 1454 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1455 |
|
| 1456 |
|
| 1457 |
Although Figure 9 gives a correct representation of the possible |
| 1458 |
event sequences, it is not quite correct for the actions, which do |
| 1459 |
not compose as shown. In particular, once a control bit X has been |
| 1460 |
sent, it must continue to be sent until ACK(X) is received. This |
| 1461 |
requires new transitions with modified actions, shown in the |
| 1462 |
following list. We use the labeling convention that transitions with |
| 1463 |
the same event part all have the same letter, with different numbers |
| 1464 |
of primes to indicate different actions. |
| 1465 |
|
| 1466 |
Label Event / Action |
| 1467 |
_____ _______________________________________ |
| 1468 |
b' (=i) rcv SYN [No TAO] / snd SYN,ACK(SYN) |
| 1469 |
b'' rcv SYN [No TAO] / snd SYN,FIN,ACK(SYN) |
| 1470 |
d' CLOSE / snd SYN,FIN |
| 1471 |
e' rcv FIN / snd FIN,ACK(FIN) |
| 1472 |
e'' rcv FIN / snd SYN,FIN,ACK(FIN) |
| 1473 |
|
| 1474 |
|
| 1475 |
Figure 10 shows the state diagram of Figure 9, with the modified |
| 1476 |
transitions and with the states used by standard TCP [<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>] |
| 1477 |
identified. Those states that do not occur in standard TCP are |
| 1478 |
numbered 1-5. |
| 1479 |
|
| 1480 |
Standard TCP has another implied restriction: a FIN bit cannot be |
| 1481 |
recognized before the connection has been synchronized, i.e., c <. e. |
| 1482 |
This eliminates from standard TCP the states 1, 2, and 5 shown in |
| 1483 |
Figure 10. States 3 and 4 are needed if a FIN is to be piggy-backed |
| 1484 |
on a SYN segment (note that the states shown in Figure 1 are actually |
| 1485 |
wrong; the states shown as SYN-SENT and ESTABLISHED are really states |
| 1486 |
3 and 4). In the absence of piggybacking the FIN bit, Figure 10 |
| 1487 |
reduces to the standard TCP state diagram [<a href="#ref-STD-007" title=""Transmission Control Protocol - DARPA Internet Program Protocol Specification"">STD-007</a>]. |
| 1488 |
|
| 1489 |
The FSM described in Figure 10 is intended to be applied |
| 1490 |
cumulatively; that is, parsing a single packet header may lead to |
| 1491 |
more than one transition. For example, the standard TCP state |
| 1492 |
diagram includes a direct transition from SYN-SENT to ESTABLISHED: |
| 1493 |
|
| 1494 |
rcv SYN,ACK(SYN) / snd ACK(SYN). |
| 1495 |
|
| 1496 |
This is transition b followed immediately by c. |
| 1497 |
|
| 1498 |
|
| 1499 |
|
| 1500 |
|
| 1501 |
|
| 1502 |
|
| 1503 |
|
| 1504 |
|
| 1505 |
|
| 1506 |
|
| 1507 |
|
| 1508 |
<span class="grey">Braden [Page 27]</span></pre> |
| 1509 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-28" ></span> |
| 1510 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1511 |
|
| 1512 |
|
| 1513 |
________ ________ |
| 1514 |
| | h | | |
| 1515 |
| CLOSED |--------->| LISTEN | |
| 1516 |
|________| |________| |
| 1517 |
| | |
| 1518 |
| a | i |
| 1519 |
____V____ ____V___ ________ |
| 1520 |
| SYN- | b' | SYN- | e' | | |
| 1521 |
| SENT |--------->|RECEIVED|-------------->| 1 | |
| 1522 |
|________| |________| |________| |
| 1523 |
/ / | | | |
| 1524 |
d'/ d'/ | c d' | c | |
| 1525 |
/ / __V_____ | _V______ |
| 1526 |
/ / |ESTAB- | e | | CLOSE- | |
| 1527 |
| / | LISHED|------------|-->| WAIT | |
| 1528 |
| | |________| | |________| |
| 1529 |
| | | | | |
| 1530 |
| | | _____V__ | |
| 1531 |
| | | | | | |
| 1532 |
| | | | 2 | | |
| 1533 |
| | | |________| | |
| 1534 |
| | | | | |
| 1535 |
____V___ ______V_ | ________ | | |
| 1536 |
| | b'' | |e''' | | | | | |
| 1537 |
| 3 |------->| 4 |--------->| 5 | | | |
| 1538 |
|________| |________| | |________| | | |
| 1539 |
| / | | | |
| 1540 |
c | / d c | c | d | |
| 1541 |
| / | | | |
| 1542 |
_V___V__ ____V___ V_____V_ |
| 1543 |
| FIN- | e'' | | | LAST- | |
| 1544 |
| WAIT-1|---->|CLOSING | | ACK | |
| 1545 |
|________| |________| |________| |
| 1546 |
| | | |
| 1547 |
| f | f | f |
| 1548 |
____V___ ____V___ ___V____ |
| 1549 |
| FIN- | e | TIME- | g | | |
| 1550 |
| WAIT-2|---->| WAIT |-->| CLOSED | |
| 1551 |
|________| |________| |________| |
| 1552 |
|
| 1553 |
|
| 1554 |
Figure 10: Basic State Diagram -- Correct Actions |
| 1555 |
|
| 1556 |
|
| 1557 |
Next we introduce TAO. If the TAO test succeeds, the connection |
| 1558 |
becomes half-synchronized. This requires a new set of states, |
| 1559 |
mirroring the states of Figure 10, beginning with acceptance of a SYN |
| 1560 |
(transition "b" or "i"), and ending when ACK(SYN) arrives (transition |
| 1561 |
|
| 1562 |
|
| 1563 |
|
| 1564 |
<span class="grey">Braden [Page 28]</span></pre> |
| 1565 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-29" ></span> |
| 1566 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1567 |
|
| 1568 |
|
| 1569 |
"c"). Figure 11 shows the result of augmenting Figure 10 with the |
| 1570 |
additional states for TAO. The transitions are defined in the |
| 1571 |
following table: |
| 1572 |
|
| 1573 |
Key for Figure 11: Complete State Diagram with TAO |
| 1574 |
|
| 1575 |
|
| 1576 |
Label Event / Action |
| 1577 |
_____ ________________________ |
| 1578 |
|
| 1579 |
a OPEN / create TCB, snd SYN |
| 1580 |
b' rcv SYN [no TAO]/ snd SYN,ACK(SYN) |
| 1581 |
b'' rcv SYN [no TAO]/ snd SYN,FIN,ACK(SYN) |
| 1582 |
c rcv ACK(SYN) / |
| 1583 |
d CLOSE / snd FIN |
| 1584 |
d' CLOSE / snd SYN,FIN |
| 1585 |
e rcv FIN / snd ACK(FIN) |
| 1586 |
e' rcv FIN / snd SYN,ACK(FIN) |
| 1587 |
e'' rcv FIN / snd FIN,ACK(FIN) |
| 1588 |
e''' rcv FIN / snd SYN,FIN,ACK(FIN) |
| 1589 |
f rcv ACK(FIN) / |
| 1590 |
g timeout=2MSL / delete TCB |
| 1591 |
h passive OPEN / create TCB |
| 1592 |
i (= b') rcv SYN [no TAO]/ snd SYN,ACK(SYN) |
| 1593 |
j rcv SYN [TAO OK] / snd SYN,ACK(SYN) |
| 1594 |
k rcv SYN [TAO OK] / snd SYN,FIN,ACK(SYN) |
| 1595 |
|
| 1596 |
|
| 1597 |
|
| 1598 |
Each new state in Figure 11 bears a very simple relationship to a |
| 1599 |
standard TCP state. We indicate this by naming the new state with |
| 1600 |
the standard state name followed by a star. States SYN-SENT* and |
| 1601 |
SYN-RECEIVED* differ from the corresponding unstarred states in |
| 1602 |
recording the fact that a FIN has been sent. The other new states |
| 1603 |
with starred names differ from the corresponding unstarred states in |
| 1604 |
being half-synchronized (hence, a SYN bit needs to be transmitted). |
| 1605 |
|
| 1606 |
The state diagram of Figure 11 is more general than required for |
| 1607 |
transaction processing. In particular, it handles simultaneous |
| 1608 |
connection synchronization from both sides, allowing one or both |
| 1609 |
sides to bypass the 3-way handshake. It includes other transitions |
| 1610 |
that are unlikely in normal transaction processing, for example, the |
| 1611 |
server sending a FIN before it receives a FIN from the client |
| 1612 |
(ESTABLISHED* -> FIN-WAIT-1* in Figure 11). |
| 1613 |
|
| 1614 |
|
| 1615 |
|
| 1616 |
|
| 1617 |
|
| 1618 |
|
| 1619 |
|
| 1620 |
<span class="grey">Braden [Page 29]</span></pre> |
| 1621 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-30" ></span> |
| 1622 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1623 |
|
| 1624 |
|
| 1625 |
________ ________ |
| 1626 |
| | h | | |
| 1627 |
| CLOSED |--------------->| LISTEN | |
| 1628 |
|________| |________| |
| 1629 |
| / | |
| 1630 |
a| / i | j |
| 1631 |
| / | |
| 1632 |
| / _V______ ________ |
| 1633 |
| j | |ESTAB- | e' | CLOSE- | |
| 1634 |
| /---------|----->| LISHED*|------------>| WAIT*| |
| 1635 |
| / | |________| |________| |
| 1636 |
| / | | | | | |
| 1637 |
| / | |d' | c d' | | c |
| 1638 |
____V___ / ______V_ | _V______ | _V______ |
| 1639 |
| SYN- | b' | SYN- | c | |ESTAB- | e | | CLOSE- | |
| 1640 |
| SENT |------>|RECEIVED|-----|-->| LISHED|----------|->| WAIT | |
| 1641 |
|________| |________| | |________| | |________| |
| 1642 |
| | | | | | |
| 1643 |
| | | | ___V____ | |
| 1644 |
| | | | | LAST- | | |
| 1645 |
| d' | d' | d' | d | ACK* | | |
| 1646 |
| | | | |________| | |
| 1647 |
| | | | | | |
| 1648 |
| | ______V_ | ________ |c |d |
| 1649 |
| k | | FIN- | | e''' | | | | |
| 1650 |
| /------|-->| WAIT-1*|---|------>|CLOSING*| | | |
| 1651 |
| / | |________| | |________| | | |
| 1652 |
| / | | | | | | |
| 1653 |
| / | | c | | c | | |
| 1654 |
____V___ / ____V___ V_____V_ ____V___ V____V__ |
| 1655 |
| SYN- | b'' | SYN- | c | FIN- | e'' | | | LAST- | |
| 1656 |
| SENT* |----->|RECEIVD*|---->| WAIT-1 |---->|CLOSING | | ACK | |
| 1657 |
|________| |________| |________| |________| |________| |
| 1658 |
| | | |
| 1659 |
| f | f | f |
| 1660 |
___V____ ____V___ ___V____ |
| 1661 |
| FIN- | e |TIME- | g | | |
| 1662 |
| WAIT-2 |---->| WAIT |-->| CLOSED | |
| 1663 |
|________| |________| |________| |
| 1664 |
|
| 1665 |
Figure 11: Complete State Diagram with TAO |
| 1666 |
|
| 1667 |
|
| 1668 |
|
| 1669 |
The relationship between starred and unstarred states is very |
| 1670 |
regular. As a result, the state extensions can be implemented very |
| 1671 |
simply using the standard TCP FSM with the addition of two "hidden" |
| 1672 |
boolean flags, as described in the functional specification memo |
| 1673 |
|
| 1674 |
|
| 1675 |
|
| 1676 |
<span class="grey">Braden [Page 30]</span></pre> |
| 1677 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-31" ></span> |
| 1678 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1679 |
|
| 1680 |
|
| 1681 |
[<a href="#ref-TTCP-FS" title=""Transaction TCP -- Functional Specification"">TTCP-FS</a>]. |
| 1682 |
|
| 1683 |
As an example of the application of Figure 11, consider the minimal |
| 1684 |
transaction shown in Figure 12. |
| 1685 |
|
| 1686 |
|
| 1687 |
TCP A (Client) TCP B (Server) |
| 1688 |
_______________ ______________ |
| 1689 |
|
| 1690 |
CLOSED LISTEN |
| 1691 |
|
| 1692 |
1. SYN-SENT* --> <SYN,data1,FIN,CC=x1> --> CLOSE-WAIT* |
| 1693 |
(TAO test OK=> |
| 1694 |
data1->user_B) |
| 1695 |
|
| 1696 |
LAST-ACK* |
| 1697 |
<-- <SYN,ACK(FIN),data2,FIN,CC=y1,CC.ECHO=x1> <-- |
| 1698 |
2. TIME-WAIT |
| 1699 |
(TAO test OK, |
| 1700 |
data2->user_A) |
| 1701 |
|
| 1702 |
|
| 1703 |
3. TIME-WAIT --> <ACK(FIN),CC=x2> --> CLOSED |
| 1704 |
|
| 1705 |
(timeout) |
| 1706 |
CLOSED |
| 1707 |
|
| 1708 |
|
| 1709 |
Figure 12: Minimal Transaction Sequence |
| 1710 |
|
| 1711 |
Sending segment #1 leaves the client end in SYN-SENT* state, which |
| 1712 |
differs from SYN-SENT state in recording the fact that a FIN has been |
| 1713 |
sent. At the server end, passing the TAO test enters ESTABLISHED* |
| 1714 |
state, which passes the data to the user as in ESTABLISHED state and |
| 1715 |
also records the fact that the connection is half synchronized. Then |
| 1716 |
the server processes the FIN bit of segment #1, moving to CLOSE-WAIT* |
| 1717 |
state. |
| 1718 |
|
| 1719 |
Moving to CLOSE-WAIT* state should cause the server to send a segment |
| 1720 |
containing SYN and ACK(FIN). However, transmission of this segment |
| 1721 |
is deferred so the server can piggyback the response data and FIN on |
| 1722 |
the same segment, unless a timeout occurs first. When the server |
| 1723 |
does send segment #2 containing the response data2 and a FIN, the |
| 1724 |
connection advances from CLOSE-WAIT* to LAST-ACK* state; the |
| 1725 |
connection is still half-synchronized from B's viewpoint. |
| 1726 |
|
| 1727 |
Processing segment #2 at the client again results in multiple |
| 1728 |
transitions: |
| 1729 |
|
| 1730 |
|
| 1731 |
|
| 1732 |
<span class="grey">Braden [Page 31]</span></pre> |
| 1733 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-32" ></span> |
| 1734 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1735 |
|
| 1736 |
|
| 1737 |
SYN-SENT* -> FIN-WAIT-1* -> CLOSING* -> CLOSING -> TIME-WAIT |
| 1738 |
|
| 1739 |
These correspond respectively to receiving a SYN, a FIN, an ACK for |
| 1740 |
A's SYN, and an ACK for A's FIN. |
| 1741 |
|
| 1742 |
Figure 13 shows a slightly more complex example, a transaction |
| 1743 |
sequence in which request and response data each require two |
| 1744 |
segments. This figure assumes that both client and server TCP are |
| 1745 |
well-behaved, so that e.g., the client sends the single segment #5 to |
| 1746 |
acknowledge both data segments #3 and #4. SEG.CC values are omitted |
| 1747 |
for clarity. |
| 1748 |
|
| 1749 |
|
| 1750 |
<u>T</u><u>C</u><u>P</u>_<u>A</u> <u>T</u><u>C</u><u>P</u>_<u>B</u> |
| 1751 |
|
| 1752 |
|
| 1753 |
1. SYN-SENT* --> <SYN,data1> --> ESTABLISHED* |
| 1754 |
(TAO OK, |
| 1755 |
data1-> user) |
| 1756 |
|
| 1757 |
2. SYN-SENT* --> <data2,FIN> --> CLOSE-WAIT* |
| 1758 |
(data2-> user) |
| 1759 |
|
| 1760 |
3. FIN-WAIT-2 <-- <SYN,ACK(FIN),data3> <-- CLOSE-WAIT* |
| 1761 |
(data3->user) |
| 1762 |
|
| 1763 |
4. TIME_WAIT <-- <ACK(FIN),data4,FIN> <-- LAST-ACK* |
| 1764 |
(data4->user) |
| 1765 |
|
| 1766 |
5. TIME-WAIT --> <ACK(FIN)> --> CLOSED |
| 1767 |
|
| 1768 |
|
| 1769 |
Figure 13. Multi-Packet Request/Response Transaction |
| 1770 |
|
| 1771 |
|
| 1772 |
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. CONCLUSIONS AND ACKNOWLEDGMENTS</span> |
| 1773 |
|
| 1774 |
TCP was designed to be a highly symmetric protocol. This symmetry is |
| 1775 |
evident in the piggy-backing of acknowledgments on data and in the |
| 1776 |
common header format for data segments and acknowledgments. On the |
| 1777 |
other hand, the examples and discussion in this memo are in general |
| 1778 |
highly unsymmetrical; the actions of a "client" are clearly |
| 1779 |
distinguished from those of a "server". To explain this apparent |
| 1780 |
discrepancy, we note the following. Even when TCP is used for |
| 1781 |
virtual circuit service, the data transfer phase is symmetrical but |
| 1782 |
the open and close phases are not. A minimal transaction, consisting |
| 1783 |
of one segment in each direction, compresses the open, data transfer, |
| 1784 |
and close phases together, and making the asymmetry of the open and |
| 1785 |
|
| 1786 |
|
| 1787 |
|
| 1788 |
<span class="grey">Braden [Page 32]</span></pre> |
| 1789 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-33" ></span> |
| 1790 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1791 |
|
| 1792 |
|
| 1793 |
close phases dominant. As request and response messages increase in |
| 1794 |
size, the virtual circuit model becomes increasingly relevant, and |
| 1795 |
symmetry again dominates. |
| 1796 |
|
| 1797 |
TCP's 3-way handshake precludes any performance gain from including |
| 1798 |
data on a SYN segment, while TCP's full-duplex data-conserving close |
| 1799 |
sequence ties up communication resources to the detriment of high- |
| 1800 |
speed transactions. Merely loading more control bits onto TCP data |
| 1801 |
segments does not provide efficient transaction service. To use TCP |
| 1802 |
as an effective transaction transport protocol requires bypassing the |
| 1803 |
3-way handshake and shortening the TIME-WAIT delay. This memo has |
| 1804 |
proposed a backwards-compatible TCP extension to accomplish both |
| 1805 |
goals. It is our hope that by building upon the current version of |
| 1806 |
TCP, we can give a boost to community acceptance of the new |
| 1807 |
facilities. Furthermore, the resulting protocol implementations will |
| 1808 |
retain the algorithms that have been developed for flow and |
| 1809 |
congestion control in TCP [<a href="#ref-Jacobson88" title=""Congestion Avoidance and Control"">Jacobson88</a>]. |
| 1810 |
|
| 1811 |
O'Malley and Peterson have recently recommended against backwards- |
| 1812 |
compatible extensions to TCP, and suggested instead a mechanism to |
| 1813 |
allow easy installation of alternative versions of a protocol [RFC- |
| 1814 |
1263]. While this is an interesting long-term approach, in the |
| 1815 |
shorter term we suggest that incremental extension of the current TCP |
| 1816 |
may be a more effective route. |
| 1817 |
|
| 1818 |
Besides the backward-compatible extension proposed here, there are |
| 1819 |
two other possible approaches to making efficient transaction |
| 1820 |
processing widely available in the Internet: (1) a new version of TCP |
| 1821 |
or (2) a new protocol specifically adapted to transactions. Since |
| 1822 |
current TCP "almost" supports transactions, we favor (1) over (2). A |
| 1823 |
new version of TCP that retained the semantics of STD-007 but used 64 |
| 1824 |
bit sequence numbers with the procedures and states described in |
| 1825 |
Sections <a href="#section-3">3</a>, <a href="#section-4">4</a>, and <a href="#section-6">6</a> of this memo would support transactions as well |
| 1826 |
as virtual circuits in a clean, coherent manner. |
| 1827 |
|
| 1828 |
A potential application of transaction-mode TCP might be SMTP. If |
| 1829 |
commands and responses are batched, in favorable cases complete SMTP |
| 1830 |
delivery operations on short messages could be performed with a |
| 1831 |
single minimal transaction; on the other hand, the body of a message |
| 1832 |
may be arbitrarily large. Using a TCP extended as in this memo could |
| 1833 |
significantly reduce the load on large mail hosts. |
| 1834 |
|
| 1835 |
This work began as an elaboration of the concept of TAO, due to Dave |
| 1836 |
Clark. I am grateful to him and to Van Jacobson, John Wroclawski, |
| 1837 |
Dave Borman, and other members of the End-to-End Research group for |
| 1838 |
helpful ideas and critiques during the long development of this work. |
| 1839 |
I also thank Liming Wei, who tested the initial implementation in Sun |
| 1840 |
OS. |
| 1841 |
|
| 1842 |
|
| 1843 |
|
| 1844 |
<span class="grey">Braden [Page 33]</span></pre> |
| 1845 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-34" ></span> |
| 1846 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1847 |
|
| 1848 |
|
| 1849 |
APPENDIX A -- TIME-WAIT STATE AND THE 2-PACKET EXCHANGE |
| 1850 |
|
| 1851 |
This appendix considers the implications of reducing TIME-WAIT state |
| 1852 |
delay below that given in formula [<a href="#ref-2">2</a>]. |
| 1853 |
|
| 1854 |
An immediate consequence of this would be the requirement for the |
| 1855 |
server host to accept an initial SYN for a connection in LAST-ACK |
| 1856 |
state. Without the transaction extensions, the arrival of a new |
| 1857 |
<SYN> in LAST-ACK state looks to TCP like a half-open connection, and |
| 1858 |
TCP's rules are designed to restore correspondence by destroying the |
| 1859 |
state (through sending a RST segment) at one end or the other. We |
| 1860 |
would need to thwart this action in the case of transactions. |
| 1861 |
|
| 1862 |
There are two different possible ways to further reduce TIME-WAIT |
| 1863 |
delay. |
| 1864 |
|
| 1865 |
(1) Explicit Truncation of TIME-WAIT state |
| 1866 |
|
| 1867 |
TIME-WAIT state could be explicitly truncated by accepting a new |
| 1868 |
sendto() request for a connection in TIME-WAIT state. |
| 1869 |
|
| 1870 |
This would allow the ACK(FIN) segment to be delayed and sent |
| 1871 |
only if a timeout occurs before a new request arrives. This |
| 1872 |
allows an ideal 2-segment exchange for closely-spaced |
| 1873 |
transactions, which would restore some symmetry to the |
| 1874 |
transaction exchange. However, explicit truncation would |
| 1875 |
represent a significant change in many implementations. |
| 1876 |
|
| 1877 |
It might be supposed that even greater symmetry would result if |
| 1878 |
the new request segment were a <SYN,ACK> that explicitly |
| 1879 |
acknowledges the previous reply, rather than a <SYN> that is |
| 1880 |
only an implicit acknowledgment. However, the new request |
| 1881 |
segment might arrive at B to find the server side in either |
| 1882 |
LAST-ACK or CLOSED state, depending upon whether the ACK(FIN) |
| 1883 |
had arrived. In CLOSED state, a <SYN,ACK> would not be |
| 1884 |
acceptable. Hence, if the client sent an initial <SYN,ACK> |
| 1885 |
instead of a <SYN> segment, there would be a race condition at |
| 1886 |
the server. |
| 1887 |
|
| 1888 |
(2) No TIME-WAIT delay |
| 1889 |
|
| 1890 |
TIME-WAIT delay could be removed entirely. This would imply |
| 1891 |
that the ACK(FIN) would always be sent (which does not of course |
| 1892 |
guarantee that it will be received). As a result, the arrival |
| 1893 |
of a new SYN in LAST-ACK state would be rare. |
| 1894 |
|
| 1895 |
This choice is much simpler to implement. Its drawback is that |
| 1896 |
the server will get a false failure report if the ACK(FIN) is |
| 1897 |
|
| 1898 |
|
| 1899 |
|
| 1900 |
<span class="grey">Braden [Page 34]</span></pre> |
| 1901 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-35" ></span> |
| 1902 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1903 |
|
| 1904 |
|
| 1905 |
lost. This may not matter in practice, but it does represent a |
| 1906 |
significant change of TCP semantics. It should be noted that |
| 1907 |
reliable delivery of the reply is not an issue. The client |
| 1908 |
enter TIME-WAIT state only after the entire reply, including the |
| 1909 |
FIN bit, has been received successfully. |
| 1910 |
|
| 1911 |
The server host B must be certain that a new request received in |
| 1912 |
LAST-ACK state is indeed a new SYN and not an old duplicate; |
| 1913 |
otherwise, B could falsely acknowledge a previous response that has |
| 1914 |
not in fact been delivered to A. If the TAO comparison succeeds, the |
| 1915 |
SYN must be new; however, the server has a dilemma if the TAO test |
| 1916 |
fails. |
| 1917 |
|
| 1918 |
In Figure A.1, for example, the reply segment from the first |
| 1919 |
transaction has been lost; since it has not been acknowledged, it is |
| 1920 |
still in B's retransmission queue. An old duplicate request, segment |
| 1921 |
#3, arrives at B and its TAO test fails. B is in the position of |
| 1922 |
having old state it cannot discard (the retransmission queue) and |
| 1923 |
needing to build new state to pursue a 3-way handshake to validate |
| 1924 |
the new SYN. If the 3-way handshake failed, it would need to restore |
| 1925 |
the earlier LAST-ACK* state. (Compare with Figure 15 "Old Duplicate |
| 1926 |
SYN Initiates a Reset on Two Passive Sockets" in STD-007). This |
| 1927 |
would be complex and difficult to accomplish in many implementations. |
| 1928 |
|
| 1929 |
|
| 1930 |
TCP A (Client) TCP B (Server) |
| 1931 |
_______________ ______________ |
| 1932 |
|
| 1933 |
CLOSED LISTEN |
| 1934 |
|
| 1935 |
|
| 1936 |
1. SYN-SENT* --> <SYN,data1,FIN> --> CLOSE-WAIT* |
| 1937 |
(TAO test OK; |
| 1938 |
data1->server) |
| 1939 |
|
| 1940 |
2. (lost) X<-- <SYN,ACK(FIN),data2,FIN> <-- LAST-ACK* |
| 1941 |
|
| 1942 |
(old duplicate) |
| 1943 |
3. ... <SYN,data3,FIN> --> LAST-ACK* |
| 1944 |
(TAO test fail; |
| 1945 |
3-way handshake?) |
| 1946 |
|
| 1947 |
Figure A.1: The Server's Dilemma |
| 1948 |
|
| 1949 |
|
| 1950 |
The only practical action A can taken when the TAO test fails on a |
| 1951 |
new SYN received in LAST-ACK state is to ignore the SYN, assuming it |
| 1952 |
is really an old duplicate. We must pursue the possible consequences |
| 1953 |
|
| 1954 |
|
| 1955 |
|
| 1956 |
<span class="grey">Braden [Page 35]</span></pre> |
| 1957 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-36" ></span> |
| 1958 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 1959 |
|
| 1960 |
|
| 1961 |
of this action. |
| 1962 |
|
| 1963 |
<a href="#section-3.1">Section 3.1</a> listed four possible reasons for failure of the TAO test |
| 1964 |
on a legitimate SYN segment: (1) no cached state, (2) out-of-order |
| 1965 |
delivery of SYNs, (3) wraparound of CCgen relative to the cached |
| 1966 |
value, or (4) the M values advance too slowly. We are assuming that |
| 1967 |
there is a cached CC value at B (otherwise, the SYN cannot be |
| 1968 |
acceptable in LAST-ACK state). Wrapping the CC space is very |
| 1969 |
unlikely and probably impossible; it is difficult to imagine |
| 1970 |
circumstances which would allow the new SYN to be delivered but not |
| 1971 |
the ACK(FIN), especially given the long wraparound time of CCgen. |
| 1972 |
|
| 1973 |
This leaves the problem of out-of-order delivery of two nearly- |
| 1974 |
concurrent SYNs for different ports. The second to be delivered may |
| 1975 |
have a lower CC option and thus be locked out. This can be solved by |
| 1976 |
using a new CCgen value for every retransmission of an initial SYN. |
| 1977 |
|
| 1978 |
Truncation of TIME-WAIT state and acceptance of a SYN in LAST-ACK |
| 1979 |
state should take place only if there is a cached CC value for the |
| 1980 |
remote host. Otherwise, a SYN arriving in LAST-ACK state is to be |
| 1981 |
processed by normal TCP rules, which will result in a RST segment |
| 1982 |
from either A or B. |
| 1983 |
|
| 1984 |
This discussion leads to a paradigm for rejecting old duplicate |
| 1985 |
segments that is different from TAO. This alternative scheme is |
| 1986 |
based upon the following: |
| 1987 |
|
| 1988 |
(a) Each retransmission of an initial SYN will have a new value of |
| 1989 |
CC, as described above. |
| 1990 |
|
| 1991 |
This provision takes care of reordered SYNs. |
| 1992 |
|
| 1993 |
(b) A host maintains a distinct CCgen value for each remote host. |
| 1994 |
This value could easily be maintained in the same cache used for |
| 1995 |
the received CC values, e.g., as cache.CCgen[]. |
| 1996 |
|
| 1997 |
Once the caches are primed, it should always be true that |
| 1998 |
cache.CCgen[B] on host A is equal to cache.CC[A] on host B, and |
| 1999 |
the next transaction from A will carry a CC value exactly 1 |
| 2000 |
greater. Thus, there is no problem of wraparound of the CC |
| 2001 |
value. |
| 2002 |
|
| 2003 |
(c) A new SYN is acceptable if its SEG.CC > cache.CC[client], |
| 2004 |
otherwise the SYN is ignored as an old duplicate. |
| 2005 |
|
| 2006 |
This alternative paradigm was not adopted because it would be a |
| 2007 |
somewhat greater perturbation of TCP rules, because it may not have |
| 2008 |
the robustness of TAO, and because all of its consequences may not be |
| 2009 |
|
| 2010 |
|
| 2011 |
|
| 2012 |
<span class="grey">Braden [Page 36]</span></pre> |
| 2013 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-37" ></span> |
| 2014 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 2015 |
|
| 2016 |
|
| 2017 |
understood. |
| 2018 |
|
| 2019 |
|
| 2020 |
REFERENCES |
| 2021 |
|
| 2022 |
[<a id="ref-Birrell84">Birrell84</a>] Birrell, A. and B. Nelson, "Implementing Remote |
| 2023 |
Procedure Calls", ACM TOCS, Vo. 2, No. 1, February 1984. |
| 2024 |
|
| 2025 |
[<a id="ref-Clark88">Clark88</a>] Clark, D., "The Design Philosophy of the Internet |
| 2026 |
Protocols", ACM SIGCOMM '88, Stanford, CA, August 1988. |
| 2027 |
|
| 2028 |
[<a id="ref-Clark89">Clark89</a>] Clark, D., Private communication, 1989. |
| 2029 |
|
| 2030 |
[<a id="ref-Garlick77">Garlick77</a>] Garlick, L., R. Rom, and J. Postel, "Issues in Reliable |
| 2031 |
Host-to-Host Protocols", Proc. Second Berkeley Workshop on |
| 2032 |
Distributed Data Management and Computer Networks, May 1977. |
| 2033 |
|
| 2034 |
[<a id="ref-HR-COMM">HR-COMM</a>] Braden, R., Ed., "Requirements for Internet Hosts -- |
| 2035 |
Communication Layers", STD-003, <a href="./rfc1122">RFC-1122</a>, October 1989. |
| 2036 |
|
| 2037 |
[<a id="ref-Jacobson88">Jacobson88</a>] Jacobson, V., "Congestion Avoidance and Control", |
| 2038 |
SIGCOMM '88, Stanford, CA., August 1988. |
| 2039 |
|
| 2040 |
[<a id="ref-Jacobson90">Jacobson90</a>] Jacobson, V., private communication, 1990. |
| 2041 |
|
| 2042 |
[<a id="ref-Liskov90">Liskov90</a>] Liskov, B., Shrira, L., and J. Wroclawski, "Efficient |
| 2043 |
At-Most-Once Messages Based on Synchronized Clocks", ACM SIGCOMM |
| 2044 |
'90, Philadelphia, PA, September 1990. |
| 2045 |
|
| 2046 |
[<a id="ref-RFC-955">RFC-955</a>] Braden, R., "Towards a Transport Service Transaction |
| 2047 |
Protocol", <a href="./rfc955">RFC-955</a>, September 1985. |
| 2048 |
|
| 2049 |
[<a id="ref-RFC-1185">RFC-1185</a>] Jacobson, V., Braden, R., and Zhang, L., "TCP Extension |
| 2050 |
for High-Speed Paths", <a href="./rfc1185">RFC-1185</a>, October 1990. |
| 2051 |
|
| 2052 |
[<a id="ref-RFC-1263">RFC-1263</a>] O'Malley, S. and L. Peterson, "TCP Extensions Considered |
| 2053 |
Harmful", <a href="./rfc1263">RFC-1263</a>, University of Arizona, October 1991. |
| 2054 |
|
| 2055 |
[<a id="ref-RFC-1323">RFC-1323</a>] Jacobson, V., Braden, R., and Borman, D., "TCP |
| 2056 |
Extensions for High Performance, <a href="./rfc1323">RFC-1323</a>, February 1991. |
| 2057 |
|
| 2058 |
[<a id="ref-RFC-1337">RFC-1337</a>] Braden, R., "TIME-WAIT Assassination Hazards in TCP", |
| 2059 |
<a href="./rfc1337">RFC-1337</a>, May 1992. |
| 2060 |
|
| 2061 |
[<a id="ref-STD-007">STD-007</a>] Postel, J., "Transmission Control Protocol - DARPA |
| 2062 |
Internet Program Protocol Specification", STD-007, <a href="./rfc793">RFC-793</a>, |
| 2063 |
September 1981. |
| 2064 |
|
| 2065 |
|
| 2066 |
|
| 2067 |
|
| 2068 |
<span class="grey">Braden [Page 37]</span></pre> |
| 2069 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-38" ></span> |
| 2070 |
<span class="grey"><a href="./rfc1379">RFC 1379</a> Transaction TCP -- Concepts November 1992</span> |
| 2071 |
|
| 2072 |
|
| 2073 |
[<a id="ref-TTCP-FS">TTCP-FS</a>] Braden, R., "Transaction TCP -- Functional |
| 2074 |
Specification", Work in Progress, September 1992. |
| 2075 |
|
| 2076 |
[<a id="ref-Watson81">Watson81</a>] Watson, R., "Timer-based Mechanisms in Reliable |
| 2077 |
Transport Protocol Connection Management", Computer Networks, Vol. |
| 2078 |
5, 1981. |
| 2079 |
|
| 2080 |
Security Considerations |
| 2081 |
|
| 2082 |
Security issues are not discussed in this memo. |
| 2083 |
|
| 2084 |
Author's Address |
| 2085 |
|
| 2086 |
Bob Braden |
| 2087 |
University of Southern California |
| 2088 |
Information Sciences Institute |
| 2089 |
4676 Admiralty Way |
| 2090 |
Marina del Rey, CA 90292 |
| 2091 |
|
| 2092 |
Phone: (310) 822-1511 |
| 2093 |
EMail: [email protected] |
| 2094 |
|
| 2095 |
|
| 2096 |
|
| 2097 |
|
| 2098 |
|
| 2099 |
|
| 2100 |
|
| 2101 |
|
| 2102 |
|
| 2103 |
|
| 2104 |
|
| 2105 |
|
| 2106 |
|
| 2107 |
|
| 2108 |
|
| 2109 |
|
| 2110 |
|
| 2111 |
|
| 2112 |
|
| 2113 |
|
| 2114 |
|
| 2115 |
|
| 2116 |
|
| 2117 |
|
| 2118 |
|
| 2119 |
|
| 2120 |
|
| 2121 |
|
| 2122 |
|
| 2123 |
|
| 2124 |
Braden [Page 38] |
| 2125 |
</pre> |