into TCB.CCrecv of the TCB.
RECEIVING <ACK> SEGMENT IN SYN-RECEIVED STATE
R3.1:If a segment contains a CC option whose SEG.CC differs
from TCB.CCrecv, then the segment is unacceptable and is
dropped.
R3.2:Otherwise, a 3-way handshake has completed successfully at
the server side. If the segment contains a CC option and
if cache.CC[fh] is zero, then cache.CC[fh] is replaced by
TCB.CCrecv.
RECEIVING OTHER SEGMENT
R4: Any other segment received with a CC option is
unacceptable if SEG.CC differs from TCB.CCrecv. However,
a RST segment is exempted from this test.
OPEN REQUEST
To allow truncation of TIME-WAIT state, the following changes
are made in the state diagram for OPEN requests (see Figure
10):
O1.1:A new passive open request is allowed in any of the
states: LAST-ACK, LAST-ACK*, CLOSING, CLOSING*, or TIME-
WAIT. This causes a transition to the corresponding I-
state (see Figure 10), which retains the previous state,
including the retransmission queue and timer.
O1.2 A new active open request is allowed in TIME-WAIT or
LISTEN-TW state, if the elapsed time since the current
connection opened is less than MSL. The result is to
delete the old TCB and create a new one, send a new SYN
segment, and enter SYN-SENT or SYN-SENT* state (depending
upon whether or not the SYN segment contains a FIN bit).
Finally, T/TCP has a provision to improve performance for the case
of a client that "sprays" transactions rapidly using many
different server hosts and/or ports. If TCB.CCrecv in the TCB is
non-zero (and still assuming that the connection duration is less
than MSL), then the TIME-WAIT delay may be set to min(K*RTO,
2*MSL). Here RTO is the measured retransmission timeout time and
the constant K is currently specified to be 8.
3.5 User Interface
STD-007 defines a prototype user interface ("transport service")
that implements the virtual circuit service model [STD-007,
Section 3.8]. One addition to this interface in required for
transaction processing: a new Boolean flag "end-of-file" (EOF),
added to the SEND call. A generic SEND call becomes:
Send
Format: SEND (local connection name, buffer address,
byte count, PUSH flag, URGENT flag, EOF flag [,timeout])
The following text would be added to the description of SEND in
[STD-007]:
If the EOF (End-Of-File) flag is set, any remaining queued
data is pushed and the connection is closed. Just as with the
CLOSE call, all data being sent is delivered reliably before
the close takes effect, and data may continue to be received
on the connection after completion of the SEND call.
Figure 8A shows a skeleton sequence of user calls by which a
client could initiate a transaction. The SEND call initiates a
transaction request to the foreign socket (host and port)
specified in the passive OPEN call. The predicate "recv_EOF"
tests whether or not a FIN has been received on the connection;
this might be implemented using the STATUS command of [STD-007],
or it might be implemented by some operating-system-dependent
mechanism. When recv_EOF returns TRUE, the connection has been
completely closed and the client end of the connection is in
TIME-WAIT state.
__________________________________________________________________
| |
| |
| OPEN(local_port, foreign_socket, PASSIVE) -> conn_name; |
| |
| SEND(conn_name, request_buffer, length, |
| PUSH=YES, URG=NO, EOF=YES); |
| |
| while (not recv_EOF(conn_name)) { |
| |
| RECEIVE(conn_name, reply_buffer, length) -> count; |
| |
| <Process reply_buffer.> |
| } |
| |
| |
| Figure 8A: Client Side User Interface |
|__________________________________________________________________|
If a client is going to send a rapid series of such requests to
the same foreign_socket, it should use the same local_port for
all. This will allow truncation of TIME-WAIT state. Otherwise,
it could leave local_port wild, allowing TCP to choose successive
local ports for each call, realizing that each transaction may
leave behind a significant control block overhead in the kernel.
Figure 8B shows a basic sequence of server calls. The server
application waits for a request to arrive and then reads and
processes it until a FIN arrives (recv_EOF returns TRUE). At this
time, the connection is half-closed. The SEND call used to return
the reply completes the close in the other direction. It should
be noted that the use of SEND(... EOF=YES) in Figure 4B instead of
a SEND, CLOSE sequence is only an optimization; it allows
piggybacking the FIN in order to minimize the number of segments.
It should have little effect on transaction latency.
__________________________________________________________________
| |
| |
| OPEN(local_port, ANY_SOCKET, PASSIVE) -> conn_name; |
| |
| <Wait for connection to open.> |
| |
| STATUS(conn_name) -> foreign_socket |
| |
| while (not recv_EOF(conn_name)) { |
| |
| RECEIVE(conn_name, request_buffer, length) -> count; |
| |
| <Process request_buffer.> |
| } |
| |
| <Compute reply and store into reply_buffer.> |
| |
| SEND(conn_name, reply_buffer, length, |
| PUSH=YES, URG=NO, EOF=YES); |
| |
| |
| Figure 8B: Server Side User Interface |
|__________________________________________________________________|
4. IMPLEMENTATION ISSUES
4.1 RFC-1323 Extensions
A recently-proposed set of TCP enhancements [RFC-1323] defines a
Timestamps option, which carries two 32-bit timestamp values.
This option is used to accurately measure round-trip time (RTT).
The same option is also used in a procedure known as "PAWS"
(Protect Against Wrapped Sequence) to prevent erroneous data
delivery due to a combination of old duplicate segments and
sequence number reuse at very high bandwidths. The approach to
transactions specified in this memo is independent of the RFC-1323
enhancements, but implementation of RFC-1323 is desirable for all
TCP's.
The RFC-1323 extensions share several common implementation issues
with the T/TCP extensions. Both require that TCP headers carry
options. Accommodating options in TCP headers requires changes in
the way that the maximum segment size is determined, to prevent
inadvertent IP fragmentation. Both require some additional state
variable in the TCB, which may or may not cause implementation
difficulties.
4.2 Minimal Packet Sequence
Most TCP implementations will require some small modifications to
allow the minimal packet sequence for a transaction shown in
Figure 2.
Many TCP implementations contain a mechanism to delay
acknowledgments of some subset of the data segments, to cut down
on the number of acknowledgment segments and to allow piggybacking
on the reverse data flow (typically character echoes). To obtain
minimal packet exchanges for transactions, it is necessary to
delay the acknowledgment of some control bits, in an analogous
manner. In particular, the <SYN,ACK> segment that is to be sent
in ESTABLISHED* or CLOSE-WAIT* state should be delayed. Note that
the amount of delay is determined by the minimum RTO at the
transmitter; it is a parameter of the communication protocol,
independent of the application. We propose to use the same delay
parameter (and if possible, the same mechanism) that is used for
delaying data acknowledgments.
To get the FIN piggy-backed on the reply data (segment #3 in
Figure 2), thos implementations that have an implied PUSH=YES on
all SEND calls will need to augment the user interface so that
PUSH=NO can be set for transactions.
4.3 RTT Measurement
Transactions introduce new issues into the problem of measuring
round trip times [Jacobson88].
(a) With the minimal 3-segment exchange, there can be exactly one
RTT measurement in each direction for each transaction.
Since dynamic estimation of RTT cannot take place within a
single transaction, it must take place across successive
transactions. Therefore, cacheing the measured RTT and RTT
variance values is essential for transaction processing; in
normal virtual circuit communication, such cacheing is only
desirable.
(b) At the completion of a transaction, the values for RTT and
RTT variance that are retained in the cache must be some
average of previous values with the values measured during
the transaction that is completing. This raises the question
of the time constant for this average; quite different
dynamic considerations hold for transactions than for file
transfers, for example.
(c) An RTT measurement by the client will yield the value:
T = RTT + min(SPT, ATO),
where SPT (server processing time) was defined in the
introduction, and ATO is the timeout period for sending a
delayed ACK. Thus, the measured RTT includes SPT, which may
be arbitrarily variable; however, the resulting variability
of the measured T cannot exceed ATO. (In a popular TCP
implementation, for example, ATO = 200ms, so that the
variance of SPT makes a relatively small contribution to the
variance of RTT.)
(d) Transactions sample the RTT at random times, which are
determined by the client and the server applications rather
than by the network dynamics. When there are long pauses
between transactions, cached path properties will be poor
predictors of current values in the network.
Thus, the dynamics of RTT measurement for transactions differ from
those for virtual circuits. RTT measurements should work
correctly for very short connections but reduce to the current TCP
algorithms for long-lasting connections. Further study is this
issue is needed.
4.4 Cache Implementation
This extension requires a per-host cache of connection counts.
This cache may also contain values of the smoothed RTT, RTT
variance, congestion avoidance threshold, and MSS values.
Depending upon the implementation details, it may be simplest to
build a new cache for these values; another possibility is to use
the routing cache that should already be included in the host
[RFC-1122].
Implementation of the cache may be simplified because it is
consulted only when a connection is established; thereafter, the
CC values relevant to the connection are kept in the TCB. This
means that a cache entry may be safely reused during the lifetime
of a connection, avoiding the need for locking.
4.5 CPU Performance
TCP implementations are customarily optimized for streaming of
data at high speeds, not for opening or closing connections.
Jacobson's Header Prediction algorithm [Jacobson90] handles the
simple common cases of in-sequence data and ACK segments when
streaming data. To provide good performance for transactions, an
implementation might be able to do an analogous "header
prediction" specifically for the minimal request and the response
segments.
The overhead of UDP provides a lower bound on the overhead of
TCP-based transaction processing. It will probably not be
possible to reach this bound for TCP transactions, since opening a
TCP connection involves creating a significant amount of state
that is not required by UDP.
McKenney and Dove [McKenney92] have pointed out that transaction
processing applications of TCP can stress the performance of the
demultiplexing algorithm, i.e., the algorithm used to look up the
TCB when a segment arrives. They advocate the use of hash-table
techniques rather than a linear search. The effect of
demultiplexing on performance may become especially acute for a
transaction client using the extended TCP described here, due to
TCB's left in TIME-WAIT state. A high rate of transactions from a
given client will leave a large number of TCB's in TIME-WAIT
state, until their timeout expires. If the TCP implementation
uses a linear search for demultiplexing, all of these control
blocks must be traversed in order to discover that the new
association does not exist. In this circumstance, performance of
a hash table lookup should not degrade severely due to
transactions.
4.6 Pre-SYN Queue
Suppose that segment #1 in Figure 4 is lost in the network; when
segment #2 arrives in LISTEN state, it will be ignored by the TCP
rules (see [STD-007] p.66, "fourth other text and control"), and
must be retransmitted. It would be possible for the server side
to queue any ACK-less data segments received in LISTEN state and
to "replay" the segments in this queue when a SYN segment does
arrive. A data segment received with an ACK bit, which is the
normal case for existing TCP's, would still a generate RST
segment.
Note that queueing segments in LISTEN state is different from
queueing out-of-order segments after the connection is
synchronized. In LISTEN state, the sequence number corresponding
to the left window edge is not yet known, so that the segment
cannot be trimmed to fit within the window before it is queued.
In fact, no processing should be done on a queued segment while
the connection is still in LISTEN state. Therefore, a new "pre-
SYN queue" would be needed. A timeout would be required, to flush
the Pre-SYN Queue in case a SYN segment was not received.
Although implementation of a pre-SYN queue is not difficult in BSD
TCP, its limited contribution to throughput probably does not
justify the effort.
6. ACKNOWLEDGMENTS
I am very grateful to Dave Clark for pointing out bugs in RFC-1379
and for helping me to clarify the model. I also wish to thank Greg
Minshall, whose probing questions led to further elucidation of the
issues in T/TCP.
7. REFERENCES
[Jacobson88] Jacobson, V., "Congestion Avoidance and Control", ACM
SIGCOMM '88, Stanford, CA, August 1988.
[Jacobson90] Jacobson, V., "4BSD Header Prediction", Comp Comm
Review, v. 20, no. 2, April 1990.
[McKenney92] McKenney, P., and K. Dove, "Efficient Demultiplexing
of Incoming TCP Packets", ACM SIGCOMM '92, Baltimore, MD, October
1992.
[RFC-1122] Braden, R., Ed., "Requirements for Internet Hosts --
Communications Layers", STD-3, RFC-1122, USC/Information Sciences
Institute, October 1989.
[RFC-1323] Jacobson, V., Braden, R., and D. Borman, "TCP Extensions
for High Performance, RFC-1323, LBL, USC/Information Sciences
Institute, Cray Research, February 1991.
[RFC-1379] Braden, R., "Transaction TCP -- Concepts", RFC-1379,
USC/Information Sciences Institute, September 1992.
[ShankarLee93] Shankar, A. and D. Lee, "Modulo-N Incarnation
Numbers for Cache-Based Transport Protocols", Report CS-TR-3046/
UIMACS-TR-93-24, University of Maryland, March 1993.
[STD-007] Postel, J., "Transmission Control Protocol - DARPA
Internet Program Protocol Specification", STD-007, RFC-793,
USC/Information Sciences Institute, September 1981.
APPENDIX A. ALGORITHM SUMMARY
This appendix summarizes the additional processing rules introduced
by T/TCP. We define the following symbols:
Options
CC(SEG.CC): TCP Connection Count (CC) Option
CC.NEW(SEG.CC): TCP CC.NEW option
CC.ECHO(SEG.CC): TCP CC.ECHO option
Here SEG.CC is option value in segment.
Per-Connection State Variables in TCB
CCsend: CC value to be sent in segments
CCrecv: CC value to be received in segments
Elapsed: Duration of connection
Global Variables:
CCgen: CC generator variable
cache.CC[fh]: Cache entry: Last CC value received.
cache.CCsent[fh]: Cache entry: Last CC value sent.
PSEUDO-CODE SUMMARY:
Passive OPEN => {
Create new TCB;
}
Active OPEN => {
<Create new TCB>
CCrecv = 0;
CCsend = CCgen;
If (CCgen == 0xffffffff) then Set CCgen = 1;
else Set CCgen = CCgen + 1.
<Send initial {SYN} segment (see below)>
}
Send initial {SYN} segment => {
If (cache.CCsent[fh] == 0 OR CCsend < cache.CCsent[fh] ) then {
Include CC.NEW(CCsend) option in segment;
Set cache.CCsent[fh] = 0;
}
else {
Include CC(CCsend) option in segment;
Set cache.CCsent[fh] = CCsend;
}
}
Send {SYN,ACK} segment => {
If (CCrecv != 0) then
Include CC(CCsend), CC.ECHO(CCrecv) options in segment.
}
Receive {SYN} segment in LISTEN, SYN-SENT, or SYN-SENT* state => {
If state == LISTEN then {
CCrecv = 0;
CCsend = CCgen;
If (CCgen == 0xffffffff) then Set CCgen = 1;
else Set CCgen = CCgen + 1.
}
If (Segment contains CC option OR
Segment contains CC.NEW option) then
Set CCrecv = SEG.CC.
if (Segment contains CC option AND
cache.CC[fh] != 0 AND
SEG.CC > cache.CC[fh] ) then { /* TAO Test OK */
Set cache.CC[fh] = CCrecv;
<Mark connection half-synchronized>
<Process data and/or FIN and return>
}
If (Segment does not contain CC option) then
Set cache.CC[fh] = 0;
<Do normal TCP processing and return>.
}
Receive {SYN} segment in LISTEN-TW, LISTEN-LA, LISTEN-LA*, LISTEN-CL,
or LISTEN-CL* state => {
If ( (Segment contains CC option AND CCrecv != 0 ) then {
If (state = LISTEN-TW AND Elapsed > MSL ) then
<Send RST, drop segment, and return>.
if (SEG.CC > CCrecv ) then {
<Implicitly ACK FIN and data in retransmission queue>;
<Close and delete TCB>;
<Reprocess segment>.
/* Expect to match new TCB
* in LISTEN state.
*/
}
}
else
<Drop segment>.
}
Receive {SYN,ACK} segment => {
if (Segment contains CC.ECHO option AND
SEG.CC != CCsend) then
<Send a reset and discard segment>.
if (Segment contains CC option) then {
Set CCrecv = SEG.CC.
if (cache.CC[fh] is undefined) then
Set cache.CC[fh] = CCrecv.
}
}
Send non-SYN segment => {
if (CCrecv != 0 OR
(cache.CCsent[fh] != 0 AND
state is SYN-SENT or SYN-SENT*)) then
Include CC(CCsend) option in segment.
}
Receive non-SYN segment in SYN-RECEIVED state => {
if (Segment contains CC option AND RST bit is off) {
if (SEG.CC != CCrecv) then
<Segment is unacceptable; drop it and send an
ACK segment, as in normal TCP processing>.
if (cache.CC[fh] is undefined) then
Set cache.CC[fh] = CCrecv.
}
}
Receive non-SYN segment in (state >= ESTABLISHED) => {
if (Segment contains CC option AND RST bit is off) {
if (SEG.CC != CCrecv) then
<Segment is unacceptable; drop it and send an
ACK segment, as in normal TCP processing>.
}
}
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