Debian Codegraph @

rfc1379.html

raw
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 &lt;SYN,ACK&gt; 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="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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="&quot;Towards a Transport Service Transaction Protocol&quot;">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="&quot;The Design Philosophy of the Internet Protocols&quot;">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="&quot;Transaction TCP -- Functional Specification&quot;">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="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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="&quot;Implementing Remote Procedure Calls&quot;">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="&quot;Timer-based Mechanisms in Reliable Transport Protocol Connection Management&quot;">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="&quot;Efficient At-Most-Once Messages Based on Synchronized Clocks&quot;">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="&quot;Issues in Reliable Host-to-Host Protocols&quot;">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="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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 --&gt; &lt;SYN,data1,FIN&gt; --&gt; SYN-RCVD
235 (data1 queued)
236
237 2. ESTABLISHED &lt;-- &lt;SYN,ACK(SYN)&gt; &lt;-- SYN-RCVD
238
239
240 3. FIN-WAIT-1 --&gt; &lt;ACK(SYN),FIN&gt; --&gt; CLOSE-WAIT
241 (data1 to server)
242
243 (Server sends reply)
244 4. TIME-WAIT &lt;-- &lt;ACK(FIN),data2,FIN&gt; &lt;-- LAST-ACK
245 (data2 to client)
246
247 5. TIME-WAIT --&gt; &lt;ACK(FIN)&gt; --&gt; 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="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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="&quot;Transaction TCP -- Functional Specification&quot;">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 &gt; 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 &lt; x1, and the M values generated by host B satisfy y0 &lt; 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="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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. --&gt; &lt;SYN,data1,M=x1&gt; --&gt; ( (x1 &gt; x0) =&gt;
370 data1 -&gt; user_B;
371 cache.M[A]= x1)
372
373 [ y0 ] [ x1 ]
374 2. &lt;-- &lt;SYN,ACK(data1),data2,M=y1&gt; &lt;--
375
376 (data2 -&gt; 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 &lt;SYN,ACK&gt; 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 &lt;SYN,ACK&gt; 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 &gt;= 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. --&gt; &lt;SYN,data1,M=x1&gt; --&gt; ( (x1 &lt;= x0) =&gt;
416 data1 queued;
417 3-way handshake)
418
419 [ y0 ] [ x0 ]
420 2. &lt;-- &lt;SYN,ACK(SYN),M=y1&gt; &lt;--
421 (cache.M[B]= y1)
422
423 [ y1 ] [ x0 ]
424 3. --&gt; &lt;ACK(SYN),M=x2&gt; --&gt; (Handshake OK =&gt;
425 data1-&gt;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="&quot;Requirements for Internet Hosts -- Communication Layers&quot;">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* --&gt; &lt;SYN,data1,FIN,M=x1&gt; --&gt; CLOSE-WAIT*
481 (TAO test OK=&gt;
482 data1-&gt;user_B)
483
484 &lt;-- &lt;SYN,ACK(FIN),data2,FIN,M=y1&gt; &lt;-- LAST-ACK*
485 2. TIME-WAIT
486 (data2-&gt;user_A)
487
488
489 3. TIME-WAIT --&gt; &lt;ACK(FIN),M=x2&gt; --&gt; 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 &lt;SYN&gt;
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 &gt;= 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. --&gt; &lt;SYN,data1,M.NEW=x1&gt; --&gt; (invalidate cache;
534 queue data1;
535 [ ?? ] 3-way handshake)
536
537 [ ?? ]
538 2. &lt;-- &lt;SYN,ACK(SYN),M=y1&gt; &lt;--
539 (cache.M[B]= y1)
540
541 [ y1 ] [ ?? ]
542
543 3. --&gt; &lt;ACK(SYN),M=x2&gt; --&gt; data1-&gt;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 &lt;SYN&gt; 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. --&gt; &lt;SYN,data1,M=x1&gt; --&gt; (data1 queued;
579 3-way handshake)
580
581 [ y0 ] [ ?? ]
582 2. &lt;-- &lt;SYN,ACK(SYN),M=y1&gt; &lt;--
583 (cache.M[B]= y1)
584
585 [ y1 ] [ ?? ]
586 3. --&gt; &lt;ACK(SYN),M=x2&gt; --&gt; (data1-&gt;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 &lt;SYN,ACK&gt; Segments
597
598 Transactions introduce a new hazard of erroneously accepting an
599 old duplicate &lt;SYN,ACK&gt; segment. To be acceptable, a &lt;SYN,ACK&gt;
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 &lt;SYN,ACK&gt; 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 &lt;SYN,ACK&gt; 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. --&gt; &lt;seq=100,SYN,data=300,FIN,M=x1&gt; --&gt; (TAO test OK)
637
638
639 2. &lt;-- &lt;seq=800,ack=402,SYN,data=350,FIN,M=y1&gt; &lt;--
640
641
642 3. TIME-WAIT --&gt; &lt;ACK(FIN)&gt; --&gt; CLOSED
643 (short timeout)
644 CLOSED
645
646 (New Request)
647 4. --&gt; &lt;seq=200,SYN,data=500,FIN,M=x2&gt; --&gt; ...
648
649 (Duplicate of segment #2)
650 5. &lt;-- &lt;seq=800,ack=402,SYN,data=300,FIN,M=y1&gt; &lt;--...
651 (Acceptable!!)
652
653
654 Figure 7: Old Duplicate &lt;SYN,ACK&gt; Causing Error
655
656
657 Unfortunately, we cannot simply use TAO on the client side to
658 detect and reject old duplicate &lt;SYN,ACK&gt; segments. A TAO test at
659 the client might fail for a valid &lt;SYN,ACK&gt; 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 &lt;SYN&gt; segment, in the &lt;SYN,ACK&gt; 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 &lt;SYN&gt; and can
675 therefore positively validate the &lt;SYN,ACK&gt; 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 &lt;SYN,ACK&gt;
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 &lt;SYN&gt; (see Figure 8
682 of [<a href="#ref-STD-007" title="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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="&quot;Transaction TCP -- Functional Specification&quot;">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="&quot;TCP Extension for High-Speed Paths&quot;">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="&quot;Congestion Avoidance and Control&quot;">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' &gt; CC, then we require that:
861
862 SEG.M(A,B,Port.A,Port.B,CC',0) &gt; 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' &gt; CC then
869
870 SEG.M(A,B,Port.A,Port.B,CC',n') &gt; 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="&quot;TIME-WAIT Assassination Hazards in TCP&quot;">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="&quot;TCP Extension for High-Speed Paths&quot;">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 -&gt; 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 &lt;= 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 &gt; T2, we require that: S(T2, CC+1, 0) - S(T1, CC, n) &gt;
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 &gt; n/(T2 - T1), or T2/Ts - T1/Ts &gt; n/(R*Ts)
1041
1042 Using the relationship: floor(x)-floor(y) &gt; 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 &lt; 2**31.
1055
1056 We are interested in the case: Ts*TRmax &gt;&gt; 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 &lt; 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 &lt; 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 &lt; 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="&quot;TCP Extensions Considered Harmful&quot;">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 &lt; 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 &lt; 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 &lt; 2**31
1129
1130 For example, if MSL = 2000 seconds then TRmax &lt; 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 &gt; cache.CC[A] and SEG.TSval &gt;=
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 &lt; 2**31
1151
1152 i.e., TRmax &lt; 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 &lt; 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 &amp; 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 &amp; MSL
1246 too small
1247
1248 (b) Timestamps&amp; clock-
1249 driven ISN [<a href="#ref-3">3</a>] &amp; 10**9 24 days Hard to
1250 R=10**9 implement
1251
1252 (c) Timestamps &amp; 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=&gt;
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 "&lt;." to mean "must precede", the precedence rules
1370 are:
1371
1372 (1) Logical ordering: must open connection before closing it:
1373
1374 b &lt;. e
1375
1376 (2) Causality -- cannot receive ACK(x) before x has been sent:
1377
1378 a &lt;. c and i &lt;. c and d &lt;. f
1379
1380 (3) Acknowledgments are cumulative
1381
1382 c &lt;. f
1383
1384 (4) First packet in each direction must contain a SYN.
1385
1386 b &lt;. c and b &lt;. 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 |---------&gt;| LISTEN |
1409 |________| |________|
1410 | |
1411 | a | i
1412 ____V____ ____V___ ________
1413 | | b | | e | |
1414 | |---------&gt;| |--------------&gt;| |
1415 |________| |________| |________|
1416 / / | / |
1417 / / | c d / | c
1418 / / __V_____ | ____V___
1419 / / | | e | | |
1420 d | d / | |------------&gt;| |
1421 | | |________| | |________|
1422 | | | | |
1423 | | | ___V____ |
1424 | | | | | |
1425 | | | | | |
1426 | | | |________| |
1427 | | | | |
1428 ____V___ ______V_ | ________ | |
1429 | | b | | e | | | | |
1430 | |-------&gt;| |---------&gt;| | | |
1431 |________| |________| | |________| | |
1432 | / | | |
1433 c | / d c | c | d |
1434 | / | | |
1435 _V___V__ ____V___ V_____V_
1436 | | e | | | |
1437 | |----&gt;| | | |
1438 |________| |________| |________|
1439 | | |
1440 | f | f | f
1441 ____V___ ____V___ ___V____
1442 | | e | TIME- | g | |
1443 | |----&gt;| WAIT |--&gt;| 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="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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 &lt;. 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="&quot;Transmission Control Protocol - DARPA Internet Program Protocol Specification&quot;">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 |---------&gt;| LISTEN |
1516 |________| |________|
1517 | |
1518 | a | i
1519 ____V____ ____V___ ________
1520 | SYN- | b' | SYN- | e' | |
1521 | SENT |---------&gt;|RECEIVED|--------------&gt;| 1 |
1522 |________| |________| |________|
1523 / / | | |
1524 d'/ d'/ | c d' | c |
1525 / / __V_____ | _V______
1526 / / |ESTAB- | e | | CLOSE- |
1527 | / | LISHED|------------|--&gt;| WAIT |
1528 | | |________| | |________|
1529 | | | | |
1530 | | | _____V__ |
1531 | | | | | |
1532 | | | | 2 | |
1533 | | | |________| |
1534 | | | | |
1535 ____V___ ______V_ | ________ | |
1536 | | b'' | |e''' | | | | |
1537 | 3 |-------&gt;| 4 |---------&gt;| 5 | | |
1538 |________| |________| | |________| | |
1539 | / | | |
1540 c | / d c | c | d |
1541 | / | | |
1542 _V___V__ ____V___ V_____V_
1543 | FIN- | e'' | | | LAST- |
1544 | WAIT-1|----&gt;|CLOSING | | ACK |
1545 |________| |________| |________|
1546 | | |
1547 | f | f | f
1548 ____V___ ____V___ ___V____
1549 | FIN- | e | TIME- | g | |
1550 | WAIT-2|----&gt;| WAIT |--&gt;| 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* -&gt; 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 |---------------&gt;| LISTEN |
1628 |________| |________|
1629 | / |
1630 a| / i | j
1631 | / |
1632 | / _V______ ________
1633 | j | |ESTAB- | e' | CLOSE- |
1634 | /---------|-----&gt;| LISHED*|------------&gt;| WAIT*|
1635 | / | |________| |________|
1636 | / | | | | |
1637 | / | |d' | c d' | | c
1638 ____V___ / ______V_ | _V______ | _V______
1639 | SYN- | b' | SYN- | c | |ESTAB- | e | | CLOSE- |
1640 | SENT |------&gt;|RECEIVED|-----|--&gt;| LISHED|----------|-&gt;| WAIT |
1641 |________| |________| | |________| | |________|
1642 | | | | | |
1643 | | | | ___V____ |
1644 | | | | | LAST- | |
1645 | d' | d' | d' | d | ACK* | |
1646 | | | | |________| |
1647 | | | | | |
1648 | | ______V_ | ________ |c |d
1649 | k | | FIN- | | e''' | | | |
1650 | /------|--&gt;| WAIT-1*|---|------&gt;|CLOSING*| | |
1651 | / | |________| | |________| | |
1652 | / | | | | | |
1653 | / | | c | | c | |
1654 ____V___ / ____V___ V_____V_ ____V___ V____V__
1655 | SYN- | b'' | SYN- | c | FIN- | e'' | | | LAST- |
1656 | SENT* |-----&gt;|RECEIVD*|----&gt;| WAIT-1 |----&gt;|CLOSING | | ACK |
1657 |________| |________| |________| |________| |________|
1658 | | |
1659 | f | f | f
1660 ___V____ ____V___ ___V____
1661 | FIN- | e |TIME- | g | |
1662 | WAIT-2 |----&gt;| WAIT |--&gt;| 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="&quot;Transaction TCP -- Functional Specification&quot;">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* --&gt; &lt;SYN,data1,FIN,CC=x1&gt; --&gt; CLOSE-WAIT*
1693 (TAO test OK=&gt;
1694 data1-&gt;user_B)
1695
1696 LAST-ACK*
1697 &lt;-- &lt;SYN,ACK(FIN),data2,FIN,CC=y1,CC.ECHO=x1&gt; &lt;--
1698 2. TIME-WAIT
1699 (TAO test OK,
1700 data2-&gt;user_A)
1701
1702
1703 3. TIME-WAIT --&gt; &lt;ACK(FIN),CC=x2&gt; --&gt; 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* -&gt; FIN-WAIT-1* -&gt; CLOSING* -&gt; CLOSING -&gt; 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* --&gt; &lt;SYN,data1&gt; --&gt; ESTABLISHED*
1754 (TAO OK,
1755 data1-&gt; user)
1756
1757 2. SYN-SENT* --&gt; &lt;data2,FIN&gt; --&gt; CLOSE-WAIT*
1758 (data2-&gt; user)
1759
1760 3. FIN-WAIT-2 &lt;-- &lt;SYN,ACK(FIN),data3&gt; &lt;-- CLOSE-WAIT*
1761 (data3-&gt;user)
1762
1763 4. TIME_WAIT &lt;-- &lt;ACK(FIN),data4,FIN&gt; &lt;-- LAST-ACK*
1764 (data4-&gt;user)
1765
1766 5. TIME-WAIT --&gt; &lt;ACK(FIN)&gt; --&gt; 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="&quot;Congestion Avoidance and Control&quot;">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 &lt;SYN&gt; 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 &lt;SYN,ACK&gt; that explicitly
1879 acknowledges the previous reply, rather than a &lt;SYN&gt; 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 &lt;SYN,ACK&gt; would not be
1884 acceptable. Hence, if the client sent an initial &lt;SYN,ACK&gt;
1885 instead of a &lt;SYN&gt; 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* --&gt; &lt;SYN,data1,FIN&gt; --&gt; CLOSE-WAIT*
1937 (TAO test OK;
1938 data1-&gt;server)
1939
1940 2. (lost) X&lt;-- &lt;SYN,ACK(FIN),data2,FIN&gt; &lt;-- LAST-ACK*
1941
1942 (old duplicate)
1943 3. ... &lt;SYN,data3,FIN&gt; --&gt; 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 &gt; 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>