(b) New connection states and transitions are introduced into the
TCP FSM at both ends of the connection. At the active end, new
states are required to piggy-back the FIN on the initial SYN
segment. At the passive end, new states are required for a
half-synchronized connection.
This section develops the resulting FSM description of a TCP
connection as a conventional state/transition diagram. To develop a
complete FSM, we take a constructive approach, as follows: (1) write
down all possible events; (2) write down the precedence rules that
govern the order in which events may occur; (3) construct the
resulting FSM; and (4) augment it to support TAO. In principle, we
do this separately for the active and passive ends; however, the
symmetry of TCP results in the two FSMs being almost entirely
coincident.
Figure 8 lists all possible state transitions for a TCP connection in
the absence of TAO, as elementary events and corresponding actions.
Each transition is labeled with a letter. Transitions a-g are used
by the active side, and c-i are used by the passive side. Without
TAO, transition "c" (event "rcv ACK(SYN)") synchronizes the
connection, allowing data to be accepted for the user.
By definition, the first transition for an active (or passive) side
must be "a" (or "i", respectively). During a single instance of a
connection, the active side will progress through some permutation of
the complete sequence of transitions {a b c d e f } or the sequence
{a b c d e f g}. The set of possible permutations is determined by
precedence rules governing the order in which transitions can occur.
Label Event / Action
_____ ________________________
a OPEN / snd SYN
b rcv SYN [No TAO]/ snd ACK(SYN)
c rcv ACK(SYN) /
d CLOSE / snd FIN
e rcv FIN / snd ACK(FIN)
f rcv ACK(FIN) /
g timeout=2MSL / delete TCB
___________________________________________________
h passive OPEN / create TCB
i rcv SYN [No TAO]/ snd SYN, ACK(SYN)
___________________________________________________
Figure 8. Basic TCP Connection Transitions
Using the notation "<." to mean "must precede", the precedence rules
are:
(1) Logical ordering: must open connection before closing it:
b <. e
(2) Causality -- cannot receive ACK(x) before x has been sent:
a <. c and i <. c and d <. f
(3) Acknowledgments are cumulative
c <. f
(4) First packet in each direction must contain a SYN.
b <. c and b <. f
(5) TIME-WAIT state
Whenever d precedes e in the sequence, g must be the last
transition.
Applying these rules, we can enumerate all possible permutations of
the events and summarize them in a state transition diagram. Figure
9 shows the result, with boxes representing the states and directed
arcs representing the transitions.
________ ________
| | h | |
| CLOSED |--------->| LISTEN |
|________| |________|
| |
| a | i
____V____ ____V___ ________
| | b | | e | |
| |--------->| |-------------->| |
|________| |________| |________|
/ / | / |
/ / | c d / | c
/ / __V_____ | ____V___
/ / | | e | | |
d | d / | |------------>| |
| | |________| | |________|
| | | | |
| | | ___V____ |
| | | | | |
| | | | | |
| | | |________| |
| | | | |
____V___ ______V_ | ________ | |
| | b | | e | | | | |
| |------->| |--------->| | | |
|________| |________| | |________| | |
| / | | |
c | / d c | c | d |
| / | | |
_V___V__ ____V___ V_____V_
| | e | | | |
| |---->| | | |
|________| |________| |________|
| | |
| f | f | f
____V___ ____V___ ___V____
| | e | TIME- | g | |
| |---->| WAIT |-->| CLOSED |
|________| |________| |________|
Figure 9: Basic State Diagram
Although Figure 9 gives a correct representation of the possible
event sequences, it is not quite correct for the actions, which do
not compose as shown. In particular, once a control bit X has been
sent, it must continue to be sent until ACK(X) is received. This
requires new transitions with modified actions, shown in the
following list. We use the labeling convention that transitions with
the same event part all have the same letter, with different numbers
of primes to indicate different actions.
Label Event / Action
_____ _______________________________________
b' (=i) rcv SYN [No TAO] / snd SYN,ACK(SYN)
b'' rcv SYN [No TAO] / snd SYN,FIN,ACK(SYN)
d' CLOSE / snd SYN,FIN
e' rcv FIN / snd FIN,ACK(FIN)
e'' rcv FIN / snd SYN,FIN,ACK(FIN)
Figure 10 shows the state diagram of Figure 9, with the modified
transitions and with the states used by standard TCP [STD-007]
identified. Those states that do not occur in standard TCP are
numbered 1-5.
Standard TCP has another implied restriction: a FIN bit cannot be
recognized before the connection has been synchronized, i.e., c <. e.
This eliminates from standard TCP the states 1, 2, and 5 shown in
Figure 10. States 3 and 4 are needed if a FIN is to be piggy-backed
on a SYN segment (note that the states shown in Figure 1 are actually
wrong; the states shown as SYN-SENT and ESTABLISHED are really states
3 and 4). In the absence of piggybacking the FIN bit, Figure 10
reduces to the standard TCP state diagram [STD-007].
The FSM described in Figure 10 is intended to be applied
cumulatively; that is, parsing a single packet header may lead to
more than one transition. For example, the standard TCP state
diagram includes a direct transition from SYN-SENT to ESTABLISHED:
rcv SYN,ACK(SYN) / snd ACK(SYN).
This is transition b followed immediately by c.
________ ________
| | h | |
| CLOSED |--------->| LISTEN |
|________| |________|
| |
| a | i
____V____ ____V___ ________
| SYN- | b' | SYN- | e' | |
| SENT |--------->|RECEIVED|-------------->| 1 |
|________| |________| |________|
/ / | | |
d'/ d'/ | c d' | c |
/ / __V_____ | _V______
/ / |ESTAB- | e | | CLOSE- |
| / | LISHED|------------|-->| WAIT |
| | |________| | |________|
| | | | |
| | | _____V__ |
| | | | | |
| | | | 2 | |
| | | |________| |
| | | | |
____V___ ______V_ | ________ | |
| | b'' | |e''' | | | | |
| 3 |------->| 4 |--------->| 5 | | |
|________| |________| | |________| | |
| / | | |
c | / d c | c | d |
| / | | |
_V___V__ ____V___ V_____V_
| FIN- | e'' | | | LAST- |
| WAIT-1|---->|CLOSING | | ACK |
|________| |________| |________|
| | |
| f | f | f
____V___ ____V___ ___V____
| FIN- | e | TIME- | g | |
| WAIT-2|---->| WAIT |-->| CLOSED |
|________| |________| |________|
Figure 10: Basic State Diagram -- Correct Actions
Next we introduce TAO. If the TAO test succeeds, the connection
becomes half-synchronized. This requires a new set of states,
mirroring the states of Figure 10, beginning with acceptance of a SYN
(transition "b" or "i"), and ending when ACK(SYN) arrives (transition
"c"). Figure 11 shows the result of augmenting Figure 10 with the
additional states for TAO. The transitions are defined in the
following table:
Key for Figure 11: Complete State Diagram with TAO
Label Event / Action
_____ ________________________
a OPEN / create TCB, snd SYN
b' rcv SYN [no TAO]/ snd SYN,ACK(SYN)
b'' rcv SYN [no TAO]/ snd SYN,FIN,ACK(SYN)
c rcv ACK(SYN) /
d CLOSE / snd FIN
d' CLOSE / snd SYN,FIN
e rcv FIN / snd ACK(FIN)
e' rcv FIN / snd SYN,ACK(FIN)
e'' rcv FIN / snd FIN,ACK(FIN)
e''' rcv FIN / snd SYN,FIN,ACK(FIN)
f rcv ACK(FIN) /
g timeout=2MSL / delete TCB
h passive OPEN / create TCB
i (= b') rcv SYN [no TAO]/ snd SYN,ACK(SYN)
j rcv SYN [TAO OK] / snd SYN,ACK(SYN)
k rcv SYN [TAO OK] / snd SYN,FIN,ACK(SYN)
Each new state in Figure 11 bears a very simple relationship to a
standard TCP state. We indicate this by naming the new state with
the standard state name followed by a star. States SYN-SENT* and
SYN-RECEIVED* differ from the corresponding unstarred states in
recording the fact that a FIN has been sent. The other new states
with starred names differ from the corresponding unstarred states in
being half-synchronized (hence, a SYN bit needs to be transmitted).
The state diagram of Figure 11 is more general than required for
transaction processing. In particular, it handles simultaneous
connection synchronization from both sides, allowing one or both
sides to bypass the 3-way handshake. It includes other transitions
that are unlikely in normal transaction processing, for example, the
server sending a FIN before it receives a FIN from the client
(ESTABLISHED* -> FIN-WAIT-1* in Figure 11).
________ ________
| | h | |
| CLOSED |--------------->| LISTEN |
|________| |________|
| / |
a| / i | j
| / |
| / _V______ ________
| j | |ESTAB- | e' | CLOSE- |
| /---------|----->| LISHED*|------------>| WAIT*|
| / | |________| |________|
| / | | | | |
| / | |d' | c d' | | c
____V___ / ______V_ | _V______ | _V______
| SYN- | b' | SYN- | c | |ESTAB- | e | | CLOSE- |
| SENT |------>|RECEIVED|-----|-->| LISHED|----------|->| WAIT |
|________| |________| | |________| | |________|
| | | | | |
| | | | ___V____ |
| | | | | LAST- | |
| d' | d' | d' | d | ACK* | |
| | | | |________| |
| | | | | |
| | ______V_ | ________ |c |d
| k | | FIN- | | e''' | | | |
| /------|-->| WAIT-1*|---|------>|CLOSING*| | |
| / | |________| | |________| | |
| / | | | | | |
| / | | c | | c | |
____V___ / ____V___ V_____V_ ____V___ V____V__
| SYN- | b'' | SYN- | c | FIN- | e'' | | | LAST- |
| SENT* |----->|RECEIVD*|---->| WAIT-1 |---->|CLOSING | | ACK |
|________| |________| |________| |________| |________|
| | |
| f | f | f
___V____ ____V___ ___V____
| FIN- | e |TIME- | g | |
| WAIT-2 |---->| WAIT |-->| CLOSED |
|________| |________| |________|
Figure 11: Complete State Diagram with TAO
The relationship between starred and unstarred states is very
regular. As a result, the state extensions can be implemented very
simply using the standard TCP FSM with the addition of two "hidden"
boolean flags, as described in the functional specification memo
[TTCP-FS].
As an example of the application of Figure 11, consider the minimal
transaction shown in Figure 12.
TCP A (Client) TCP B (Server)
_______________ ______________
CLOSED LISTEN
1. SYN-SENT* --> <SYN,data1,FIN,CC=x1> --> CLOSE-WAIT*
(TAO test OK=>
data1->user_B)
LAST-ACK*
<-- <SYN,ACK(FIN),data2,FIN,CC=y1,CC.ECHO=x1> <--
2. TIME-WAIT
(TAO test OK,
data2->user_A)
3. TIME-WAIT --> <ACK(FIN),CC=x2> --> CLOSED
(timeout)
CLOSED
Figure 12: Minimal Transaction Sequence
Sending segment #1 leaves the client end in SYN-SENT* state, which
differs from SYN-SENT state in recording the fact that a FIN has been
sent. At the server end, passing the TAO test enters ESTABLISHED*
state, which passes the data to the user as in ESTABLISHED state and
also records the fact that the connection is half synchronized. Then
the server processes the FIN bit of segment #1, moving to CLOSE-WAIT*
state.
Moving to CLOSE-WAIT* state should cause the server to send a segment
containing SYN and ACK(FIN). However, transmission of this segment
is deferred so the server can piggyback the response data and FIN on
the same segment, unless a timeout occurs first. When the server
does send segment #2 containing the response data2 and a FIN, the
connection advances from CLOSE-WAIT* to LAST-ACK* state; the
connection is still half-synchronized from B's viewpoint.
Processing segment #2 at the client again results in multiple
transitions:
SYN-SENT* -> FIN-WAIT-1* -> CLOSING* -> CLOSING -> TIME-WAIT
These correspond respectively to receiving a SYN, a FIN, an ACK for
A's SYN, and an ACK for A's FIN.
Figure 13 shows a slightly more complex example, a transaction
sequence in which request and response data each require two
segments. This figure assumes that both client and server TCP are
well-behaved, so that e.g., the client sends the single segment #5 to
acknowledge both data segments #3 and #4. SEG.CC values are omitted
for clarity.
_T_C_P__A _T_C_P__B
1. SYN-SENT* --> <SYN,data1> --> ESTABLISHED*
(TAO OK,
data1-> user)
2. SYN-SENT* --> <data2,FIN> --> CLOSE-WAIT*
(data2-> user)
3. FIN-WAIT-2 <-- <SYN,ACK(FIN),data3> <-- CLOSE-WAIT*
(data3->user)
4. TIME_WAIT <-- <ACK(FIN),data4,FIN> <-- LAST-ACK*
(data4->user)
5. TIME-WAIT --> <ACK(FIN)> --> CLOSED
Figure 13. Multi-Packet Request/Response Transaction
7. CONCLUSIONS AND ACKNOWLEDGMENTS
TCP was designed to be a highly symmetric protocol. This symmetry is
evident in the piggy-backing of acknowledgments on data and in the
common header format for data segments and acknowledgments. On the
other hand, the examples and discussion in this memo are in general
highly unsymmetrical; the actions of a "client" are clearly
distinguished from those of a "server". To explain this apparent
discrepancy, we note the following. Even when TCP is used for
virtual circuit service, the data transfer phase is symmetrical but
the open and close phases are not. A minimal transaction, consisting
of one segment in each direction, compresses the open, data transfer,
and close phases together, and making the asymmetry of the open and
close phases dominant. As request and response messages increase in
size, the virtual circuit model becomes increasingly relevant, and
symmetry again dominates.
TCP's 3-way handshake precludes any performance gain from including
data on a SYN segment, while TCP's full-duplex data-conserving close
sequence ties up communication resources to the detriment of high-
speed transactions. Merely loading more control bits onto TCP data
segments does not provide efficient transaction service. To use TCP
as an effective transaction transport protocol requires bypassing the
3-way handshake and shortening the TIME-WAIT delay. This memo has
proposed a backwards-compatible TCP extension to accomplish both
goals. It is our hope that by building upon the current version of
TCP, we can give a boost to community acceptance of the new
facilities. Furthermore, the resulting protocol implementations will
retain the algorithms that have been developed for flow and
congestion control in TCP [Jacobson88].
O'Malley and Peterson have recently recommended against backwards-
compatible extensions to TCP, and suggested instead a mechanism to
allow easy installation of alternative versions of a protocol [RFC-
1263]. While this is an interesting long-term approach, in the
shorter term we suggest that incremental extension of the current TCP
may be a more effective route.
Besides the backward-compatible extension proposed here, there are
two other possible approaches to making efficient transaction
processing widely available in the Internet: (1) a new version of TCP
or (2) a new protocol specifically adapted to transactions. Since
current TCP "almost" supports transactions, we favor (1) over (2). A
new version of TCP that retained the semantics of STD-007 but used 64
bit sequence numbers with the procedures and states described in
Sections 3, 4, and 6 of this memo would support transactions as well
as virtual circuits in a clean, coherent manner.
A potential application of transaction-mode TCP might be SMTP. If
commands and responses are batched, in favorable cases complete SMTP
delivery operations on short messages could be performed with a
single minimal transaction; on the other hand, the body of a message
may be arbitrarily large. Using a TCP extended as in this memo could
significantly reduce the load on large mail hosts.
This work began as an elaboration of the concept of TAO, due to Dave
Clark. I am grateful to him and to Van Jacobson, John Wroclawski,
Dave Borman, and other members of the End-to-End Research group for
helpful ideas and critiques during the long development of this work.
I also thank Liming Wei, who tested the initial implementation in Sun
OS.
APPENDIX A -- TIME-WAIT STATE AND THE 2-PACKET EXCHANGE
This appendix considers the implications of reducing TIME-WAIT state
delay below that given in formula [2].
An immediate consequence of this would be the requirement for the
server host to accept an initial SYN for a connection in LAST-ACK
state. Without the transaction extensions, the arrival of a new
<SYN> in LAST-ACK state looks to TCP like a half-open connection, and
TCP's rules are designed to restore correspondence by destroying the
state (through sending a RST segment) at one end or the other. We
would need to thwart this action in the case of transactions.
There are two different possible ways to further reduce TIME-WAIT
delay.
(1) Explicit Truncation of TIME-WAIT state
TIME-WAIT state could be explicitly truncated by accepting a new
sendto() request for a connection in TIME-WAIT state.
This would allow the ACK(FIN) segment to be delayed and sent
only if a timeout occurs before a new request arrives. This
allows an ideal 2-segment exchange for closely-spaced
transactions, which would restore some symmetry to the
transaction exchange. However, explicit truncation would
represent a significant change in many implementations.
It might be supposed that even greater symmetry would result if
the new request segment were a <SYN,ACK> that explicitly
acknowledges the previous reply, rather than a <SYN> that is
only an implicit acknowledgment. However, the new request
segment might arrive at B to find the server side in either
LAST-ACK or CLOSED state, depending upon whether the ACK(FIN)
had arrived. In CLOSED state, a <SYN,ACK> would not be
acceptable. Hence, if the client sent an initial <SYN,ACK>
instead of a <SYN> segment, there would be a race condition at
the server.
(2) No TIME-WAIT delay
TIME-WAIT delay could be removed entirely. This would imply
that the ACK(FIN) would always be sent (which does not of course
guarantee that it will be received). As a result, the arrival
of a new SYN in LAST-ACK state would be rare.
This choice is much simpler to implement. Its drawback is that
the server will get a false failure report if the ACK(FIN) is
lost. This may not matter in practice, but it does represent a
significant change of TCP semantics. It should be noted that
reliable delivery of the reply is not an issue. The client
enter TIME-WAIT state only after the entire reply, including the
FIN bit, has been received successfully.
The server host B must be certain that a new request received in
LAST-ACK state is indeed a new SYN and not an old duplicate;
otherwise, B could falsely acknowledge a previous response that has
not in fact been delivered to A. If the TAO comparison succeeds, the
SYN must be new; however, the server has a dilemma if the TAO test
fails.
In Figure A.1, for example, the reply segment from the first
transaction has been lost; since it has not been acknowledged, it is
still in B's retransmission queue. An old duplicate request, segment
#3, arrives at B and its TAO test fails. B is in the position of
having old state it cannot discard (the retransmission queue) and
needing to build new state to pursue a 3-way handshake to validate
the new SYN. If the 3-way handshake failed, it would need to restore
the earlier LAST-ACK* state. (Compare with Figure 15 "Old Duplicate
SYN Initiates a Reset on Two Passive Sockets" in STD-007). This
would be complex and difficult to accomplish in many implementations.
TCP A (Client) TCP B (Server)
_______________ ______________
CLOSED LISTEN
1. SYN-SENT* --> <SYN,data1,FIN> --> CLOSE-WAIT*
(TAO test OK;
data1->server)
2. (lost) X<-- <SYN,ACK(FIN),data2,FIN> <-- LAST-ACK*
(old duplicate)
3. ... <SYN,data3,FIN> --> LAST-ACK*
(TAO test fail;
3-way handshake?)
Figure A.1: The Server's Dilemma
The only practical action A can taken when the TAO test fails on a
new SYN received in LAST-ACK state is to ignore the SYN, assuming it
is really an old duplicate. We must pursue the possible consequences
of this action.
Section 3.1 listed four possible reasons for failure of the TAO test
on a legitimate SYN segment: (1) no cached state, (2) out-of-order
delivery of SYNs, (3) wraparound of CCgen relative to the cached
value, or (4) the M values advance too slowly. We are assuming that
there is a cached CC value at B (otherwise, the SYN cannot be
acceptable in LAST-ACK state). Wrapping the CC space is very
unlikely and probably impossible; it is difficult to imagine
circumstances which would allow the new SYN to be delivered but not
the ACK(FIN), especially given the long wraparound time of CCgen.
This leaves the problem of out-of-order delivery of two nearly-
concurrent SYNs for different ports. The second to be delivered may
have a lower CC option and thus be locked out. This can be solved by
using a new CCgen value for every retransmission of an initial SYN.
Truncation of TIME-WAIT state and acceptance of a SYN in LAST-ACK
state should take place only if there is a cached CC value for the
remote host. Otherwise, a SYN arriving in LAST-ACK state is to be
processed by normal TCP rules, which will result in a RST segment
from either A or B.
This discussion leads to a paradigm for rejecting old duplicate
segments that is different from TAO. This alternative scheme is
based upon the following:
(a) Each retransmission of an initial SYN will have a new value of
CC, as described above.
This provision takes care of reordered SYNs.
(b) A host maintains a distinct CCgen value for each remote host.
This value could easily be maintained in the same cache used for
the received CC values, e.g., as cache.CCgen[].
Once the caches are primed, it should always be true that
cache.CCgen[B] on host A is equal to cache.CC[A] on host B, and
the next transaction from A will carry a CC value exactly 1
greater. Thus, there is no problem of wraparound of the CC
value.
(c) A new SYN is acceptable if its SEG.CC > cache.CC[client],
otherwise the SYN is ignored as an old duplicate.
This alternative paradigm was not adopted because it would be a
somewhat greater perturbation of TCP rules, because it may not have
the robustness of TAO, and because all of its consequences may not be
understood.
REFERENCES
[Birrell84] Birrell, A. and B. Nelson, "Implementing Remote
Procedure Calls", ACM TOCS, Vo. 2, No. 1, February 1984.
[Clark88] Clark, D., "The Design Philosophy of the Internet
Protocols", ACM SIGCOMM '88, Stanford, CA, August 1988.
[Clark89] Clark, D., Private communication, 1989.
[Garlick77] Garlick, L., R. Rom, and J. Postel, "Issues in Reliable
Host-to-Host Protocols", Proc. Second Berkeley Workshop on
Distributed Data Management and Computer Networks, May 1977.
[HR-COMM] Braden, R., Ed., "Requirements for Internet Hosts --
Communication Layers", STD-003, RFC-1122, October 1989.
[Jacobson88] Jacobson, V., "Congestion Avoidance and Control",
SIGCOMM '88, Stanford, CA., August 1988.
[Jacobson90] Jacobson, V., private communication, 1990.
[Liskov90] Liskov, B., Shrira, L., and J. Wroclawski, "Efficient
At-Most-Once Messages Based on Synchronized Clocks", ACM SIGCOMM
'90, Philadelphia, PA, September 1990.
[RFC-955] Braden, R., "Towards a Transport Service Transaction
Protocol", RFC-955, September 1985.
[RFC-1185] Jacobson, V., Braden, R., and Zhang, L., "TCP Extension
for High-Speed Paths", RFC-1185, October 1990.
[RFC-1263] O'Malley, S. and L. Peterson, "TCP Extensions Considered
Harmful", RFC-1263, University of Arizona, October 1991.
[RFC-1323] Jacobson, V., Braden, R., and Borman, D., "TCP
Extensions for High Performance, RFC-1323, February 1991.
[RFC-1337] Braden, R., "TIME-WAIT Assassination Hazards in TCP",
RFC-1337, May 1992.
[STD-007] Postel, J., "Transmission Control Protocol - DARPA
Internet Program Protocol Specification", STD-007, RFC-793,
September 1981.
[TTCP-FS] Braden, R., "Transaction TCP -- Functional
Specification", Work in Progress, September 1992.
[Watson81] Watson, R., "Timer-based Mechanisms in Reliable
Transport Protocol Connection Management", Computer Networks, Vol.
5, 1981.
Security Considerations
Security issues are not discussed in this memo.
Author's Address
Bob Braden
University of Southern California
Information Sciences Institute
4676 Admiralty Way
Marina del Rey, CA 90292
Phone: (310) 822-1511
EMail: Braden@ISI.EDU