Request for Comments: 675 Yogen Dalal
NIC: 2 Carl Sunshine
INWG: 72 December 1974
SPECIFICATION OF INTERNET TRANSMISSION CONTROL PROGRAM
December 1974 Version
1. INTRODUCTION
This document describes the functions to be performed by the
internetwork Transmission Control Program [TCP] and its interface to
programs or users that require its services. Several basic
assumptions are made about process to process communication and these
are listed here without further justification. The interested reader
is referred to [CEKA74, TOML74, BELS74, DALA74, SUNS74] for further
discussion.
The authors would like to acknowledge the contributions of R.
Tomlinson (three way handshake and Initial Sequence Number
Selection), D. Belsnes, J. Burchfiel, M. Galland, R. Kahn, D. Lloyd,
W. Plummer, and J. Postel all of whose good ideas and counsel have
had a beneficial effect (we hope) on this protocol design. In the
early phases of the design work, R. Metcalfe, A. McKenzie, H.
Zimmerman, G. LeLann, and M. Elie were most helpful in explicating
the various issues to be resolved. Of course, we remain responsible
for the remaining errors and misstatements which no doubt lurk in the
nooks and crannies of the text.
Processes are viewed as the active elements of all HOST computers in
a network. Even terminals and files or other I/O media are viewed as
communicating through the use of processes. Thus, all network
communication is viewed as inter-process communication.
Since a process may need to distinguish among several communication
streams between itself and another process [or processes], we imagine
that each process may have a number of PORTs through which it
communicates with the ports of other processes.
Since port names are selected independently by each operating system,
TCP, or user, they may not be unique. To provide for unique names at
each TCP, we concatenate a NETWORK identifier, and a TCP identifier
with a port name to create a SOCKET name which will be unique
throughout all networks connected together.
A pair of sockets form a CONNECTION which can be used to carry data
in either direction [i.e. full duplex]. The connection is uniquely
identified by the <local socket, foreign socket> address pair, and
the same local socket can participate in multiple connections to
different foreign sockets [see Section 2.2].
Processes exchange finite length LETTERS as a way of communicating;
thus, letter boundaries are significant. However, the length of a
letter may be such that it must be broken into FRAGMENTS before it
can be transmitted to its destination. We assume that the fragments
will normally be reassembled into a letter before being passed to the
receiving process. Throughout this document, it is legitimate to
assume that a fragment contains all or a part of a letter, but that a
fragment never contains parts of more than one letter.
We specifically assume that fragments are transmitted from Host to
Host through means of a PACKET SWITCHING NETWORK [PSN] [ROWE70,
POUZ73]. This assumption is probably unnecessary, since a circuit
switched network could also be used, but for concreteness, we
explicitly assume that the hosts are connected to one or more PACKET
SWITCHES [PS] of a PSN [HEKA7O, POUZ74, SCWI71].
Processes make use of the TCP by handing it letters. The TCP breaks
these into fragments, if necessary, and then embeds each fragment in
an INTERNETWORK PACKET. Each internetwork packet is in turn embedded
in a LOCAL PACKET suitable for transmission from the host to one of
its serving PS. The packet switches may perform further formatting or
other operations to achieve the delivery of the local packet to the
destination Host.
The term LOCAL PACKET is used generically here to mean the formatted
bit string exchanged between a host and a packet switch. The format
of bit strings exchanged between the packet switches in a PSN will
generally not be of concern to us. If an internetwork packet is
destined for a TCP in a foreign PSN, the packet is routed to a
GATEWAY which connects the origin PSN with an intermediate or the
destination PSN. Routing of internetwork packets to the GATEWAY may
be the responsibility of the source TCP or the local PSN, depending
upon the PSN Implementation.
One model of TCP operation is to imagine that there is a basic
GATEWAY associated with each TCP which provides an interface to the
local network. This basic GATEWAY performs routing and packet
reformatting or embedding, and may also implement congestion and
error control between the TCP and GATEWAYS at or intermediate to the
destination TCP.
At a GATEWAY between networks, the internetwork packet is unwrapped
from its local packet format and examined to determine through which
network the internetwork packet should travel next. The internetwork
packet is then wrapped in a local packet format suitable to the next
network and passed on to a new packet switch.
A GATEWAY is permitted to break up the fragment carried by an
internetwork packet into smaller fragments if this is necessary for
transmission through the next network. To do this, the GATEWAY
produces a set of internetwork packets, each carrying a new fragment.
The packet format is designed so that the destination TCP may treat
fragments created by the source TCP or by intermediate GATEWAYS
nearly identically.
The TCP is responsible for regulating the flow of internetwork
packets to and from the processes it serves, as a way of preventing
its host from becoming saturated or overloaded with traffic. The TCP
is also responsible for retransmitting unacknowledged packets, and
for detecting duplicates. A consequence of this error
detection/retransmission scheme is that the order of letters received
on a given connection is also maintained [CEKA74, SUNS74]. To perform
these functions, the TCP opens and closes connections between ports
as described in Section 4.3. The TCP performs retransmission,
duplicate detection, sequencing, and flow control on all
communication among the processes it serves.
2. The TCP INTERFACE to the USER
2.1 The TCP as a POST OFFICE
The TCP acts in many ways like a postal service since it provides a
way for processes to exchange letters with each other. It sometimes
happens that a process may offer some service, but not know in
advance what its correspondents' addresses are. The analogy can be
drawn with a mail order house which opens a post office box which can
accept mail from any source. Unlike the post box, however, once a
letter from a particular correspondent arrives, a port becomes
specific to the correspondent until the owner of the port declares
otherwise.
In addition to acting like a postal service, the TCP insures end-to-
end acknowledgment, error correction, duplicate detection,
sequencing, and flow control.
2.2 Sockets and Addressing
We have borrowed the term SOCKET from the ARPANET terminology
[CACR70, MCKE73]. In general, a socket is the concatenation of a
NETWORK identifier, TCP identifier, and PORT identifier. A CONNECTION
is fully specified by the pair of SOCKETS at each end since the same
local socket may participate in many connections to different foreign
sockets.
Once the connections is specified in the OPEN command [see section
2.3.2], the TCP supplies a [short] Local Connection Name by which the
user refers to the connection in subsequent commands. In particular
this facilitates using connections with initially unspecified foreign
sockets.
TCP's are free to associate ports with processes however they choose.
However, several basic concepts seem necessary in an implementation.
There must be well known sockets [WKS] which the TCP associates only
with the "appropriate" processes by some means. We envision that
processes may "own" sockets, and that processes can only initiate
connections on the sockets they own [means for implementing ownership
is a local issue, but we envision a Request Port user call, or a
method of uniquely allocating a group of ports to a given process,
e.g. by associating the high order bits of a port name with a given
process.]
Once initiated, a connection may be passed to another process that
does not own the local socket [e.g. from logger to service process].
Strictly speaking this is a reconnection issue which might be more
elegantly handled by a general reconnection protocol as discussed in
section 3.3. To simplify passing a connection within a single TCP,
such "invisible" switches may be allowed as in TENEX systems.
Of course, each connection is associated with exactly one process,
and any attempt to reference that connection by another process will
be signaled as an error by the TCP. This prevents stealing data from
or inserting data into another process' data stream.
A connection is initiated by the rendezvous of an arriving
internetwork packet and a waiting Transmission Control Block [TCB]
created by a user OPEN, SEND, INTERPUPT, or RECEIVE call [see section
2.3]. The matching of local and foreign socket identifiers determines
when a successful connection has been initiated. The connection
becomes established when sequence numbers have been synchronized in
both directions as described in section 4.3.2.
It is possible to specify a socket only partially by setting the PORT
identifier to zero or setting both the TCP and PORT identifiers to
zero. A socket of all zero is called UNSPECIFIED. The purpose behind
unspecified sockets is to provide a sort of "general delivery"
facility [useful for logger type processes with well known sockets].
There are bounds on the degree of unspecificity of socket
identifiers. TCB's must have fully specified local sockets, although
the foreign socket may be fully or partly unspecified. Arriving
packets must have fully specified sockets.
We employ the following notation:
x.y.z = fully specified socket with x=net, y=TCP, z=port
x.y.u = as above, but unspecified port
x.u.u = as above, but unspecified TCP and port
u.u.u = completely unspecified
with respect to implementation, u = 0 [zero]
We illustrate the principles of matching by giving all cases of
incoming packets which match with existing TCB's. Generally, both
the local (foreign) socket of the TCB and the foreign (local) socket
of the packet must match.
TCB local TCB foreign Packet local Packet foreign
(a) a.b.c e.f.g e.f.g a.b.c
(b) a.b.c e.f.u e.f.g a.b.c
(c) a.b.c e.u.u e.f.g a.b.c
(d) a.b.c u.u.u e.f.g a.b.c
There are no other legal combinations of socket identifiers which
match. Case (d) is typical of the ARPANET well known socket idea in
which the well known socket (a.b.c) LISTENS for a connection from
any (u.u.u) socket. Cases (b) and (c) can be used to restrict
matching to a particular TCP or net.
2.3 TCP USER CALLS
2.3.1 A Note on Style
The following sections functionally define the USER/TCP interface.
The notation used is similar to most procedure or function calls in
high level languages, but this usage is not meant to rule out trap
type service calls [e.g. SVC's, UUO's, EMT's,...].
The user calls described below specify the basic functions the TCP
will perform to support interprocess communication. Individual
implementations should define their own exact format, and may
provide combinations or subsets of the basic functions in single
calls. In particular, some implementations may wish to automatically
OPEN a connection on the first SEND, RECEIVE, or INTERRUPT issued by
the user for a given connection.
In providing interprocess communication facilities, the TCP must not
only accept commands, but also return information to the processes
it serves. This communication consists of:
(a) general information about a connection [interrupts, remote
close, binding of unspecified foreign socket].
(b) replies to specific user commands indicating success or various
types of failure.
Although the means for signaling user processes and the exact format
of replies will vary from one implementation to another, it would
promote common understanding and testing if a common set of codes
were adopted. Such a set of Event Codes is described in section 2.4.
With respect to error messages, references to "local" and "foreign"
are ambiguous unless it is known whether these refer to the world as
seen by the sender or receiver of the error message. The authors
attempted several different approaches and finally settled on the
convention that these references would be as seen by the receiver of
the message.
2.3.2 OPEN CONNECTION
Format: OPEN(local port, foreign socket [, timeout])
We assume that the local TCP is aware of the identity of the
processes it serves and will check the authority of the process to
use the connection specified. Depending upon the implementation of
the TCP, the source network and TCP identifiers will either be
supplied by the TCP or by the processes that serve it [e.g. the
program which interfaces the TCP to its packet switch or the packet
switch itself]. These considerations are the result of concern about
security, to the extent that no TCP be able to masquerade as another
one, and so on. Similarly, no process can masquerade as another
without the collusion of the TCP.
If no foreign socket is specified [i.e. the foreign socket parameter
is 0 or not present], then this constitutes a LISTENING local socket
which can accept communication from any foreign socket. Provision is
also made for partial specification of foreign sockets as described
in section 2.2.
If the specified connection is already OPEN, an error is returned,
otherwise a full-duplex transmission control block [TCB] is created
and partially filled in with data from the OPEN command parameters.
The TCB format is described in more detail in section 4.2.2.
No network traffic is generated by the OPEN command. The first SEND
or INTERRUPT by the local user or the foreign user will cause the TCP
to synchronize the connection.
The timeout, if present, permits the caller to set up a timeout for
all letters transmitted on the connection. If a letter is not
successfully transmitted within the timeout period, the user is
notified and may ignore the condition [TCP will continue trying to
transmit] or direct the TCP to close the connection. The present
global default is 30 seconds, and connections which are set up
without specifying another timeout will retransmit every letter for
at least 30 seconds before notifying the user. The retransmission
rate may vary, and is the responsibility of the TCP and not the user.
Most likely, it will be related to the measured time for responses to
return from letters sent.
Depending on the TCP implementation, either a local connection name
will be returned to the user by the TCP, or the user will specify
this local connection name (in which case another parameter is needed
in the call). The local connection name can then be used as a short
hand term for the connection defined by the <local socket, foreign
socket> pair.
Responses from the TCP which may occur as a result of this call are
detailed in section 2.4.
2.3.3 SEND LETTER
Format: SEND(local connection name, buffer address, byte count, EOL
flag [, timeout])
This call causes the data contained in the indicated user buffer to
be sent on the indicated connection. If the connection has not been
opened, the SEND is considered an error. Some implementations may
allow users to SEND first, in which case an automatic OPEN would be
done. If the calling process is not authorized to use this
connection, an error is returned.
If the EOL flag is set, the data is the End Of a Letter, and the EOL
bit will be set in the last packet created from the buffer. If the
EOL f1ag is not set, subsequent SEND's will appear as part of the
same letter. This extended letter facility should be used sparingly
because some TCP's may delay processing packets until an entire
letter is received.
If no foreign socket was specified in the OPEN, but the connection is
established [e.g. because a listening connection has become specific
due to a foreign letter arriving for the local port] then the
designated letter is sent to the implied foreign socket. In general,
users who make use of OPEN with an unspecified foreign socket can
make use of SEND without ever explicitly knowing the foreign socket
address.
However, if a SEND is attempted before the foreign socket becomes
specified, an error will be returned. Users can use the STATUS call
to determine the status of the connection. In some implementations
the TCP may notify the user when an unspecified socket is bound.
If the timeout is specified, then the current default timeout for
this connection is changed to the new one. This can affect not only
all letters sent including and after this one, but also those which
have not yet been sent, since the timeout is kept in the TCB and not
associated with each letter sent. Of course, a time is maintained for
each internetwork packet formed so as to determine how long each of
these has been on the retransmission queue.
In the simplest implementation, SEND would not return control to the
sending process until either the transmission was complete or the
timeout had been exceeded. This simple method is highly subject to
deadlocks and is not recommended. [For example both sides of the
connection try to do SEND's before doing any RECEIVE's.] A more
sophisticated implementation would return immediately to allow the
process to run concurrently with network I/O, and, furthermore, to
allow multiple SENDs to be in progress concurrently. Multiple SENDs
are served in first come, first served order, so the TCP will queue
those it cannot service immediately.
NOTA BENE: In order for the process to distinguish among error or
success indications for different letters, the buffer address should
be returned along with the coded response to the SEND request. We
will offer an example event code format in section 2.4, showing the
information which should be returned to the calling process.
The semantics of the INTERRUPT call are described later, but this
call can have an effect on letters which have been given to the TCP
but not yet sent. In particular, all such letters are flushed by the
source TCP. Thus one of the responses to a SEND may be "flushed due
to interrupt."
Responses from the TCP which may occur as a result of this call are
detailed in section 2.4.
2.3.4 RECEIVE LETTER
Format: RECEIVE(local connection name, buffer address, byte count)
This command allocates a receiving buffer associated with the
specified connection. If no OPEN precedes this command or the calling
process is not authorized to use this connection, an error is
returned.
In the simplest implementation, control would not return to the
calling program until either a letter was received, or some error
occurred, but this scheme is highly subject to deadlocks [see section
2.3.3]. A more sophisticated implementation would permit several
RECEIVE's to be outstanding at once, These would be filled as letters
arrive. This strategy permits increased throughput, at the cost of a
more elaborate scheme [possibly asynchronous] to notify the calling
program that a letter has been received.
If insufficient buffer space is given to reassemble a complete
letter, an indication that the buffer holds a partial letter will be
given; the buffer will be filled with as much data as it can hold.
The remaining parts of a partly delivered letter will be placed in
buffers as they are made available via successive RECEIVES. If a
number of RECEIVES are outstanding, they may be filled with parts of
a single long letter or with at most one letter each. The event codes
associated with each RECEIVE will indicate what is contained in the
buffer.
To distinguish among several outstanding RECEIVES, and to take care
of the case that a letter is smaller than the buffer supplied, the
event code is accompanied by both a buffer pointer and a byte count
indicating the actual length of the letter received.
The semantics of the INTERRUPT system call are discussed later, but
this call can have an effect on outstanding RECEIVES. When the TCP
receives an INTERRUPT, it will flush all data currently queued up
awaiting receipt by the receiving process. If no data is waiting, but
several buffers have been made available by anticipatory RECEIVE
commands, these buffers are returned to the process with an error
indicating that any data that might have been placed in those buffers
has been flushed. This enables the receiving process to synchronize
its RECEIVES with the interrupt. That is, the process can distinguish
between RECEIVES issued before the receipt of the INTERRUPT and these
issued afterwards.
Responses from the TCP which may occur as a result of this call are
detailed in section 2.4.
2.3.5 CLOSE CONNECTION
Format: CLOSE(local connection name)
This command causes the connection specified to be closed. If the
connection is not open or the calling process is not authorized to
use this connection, an error is returned. Any unfilled receive
buffers or pending send buffers will be returned to the user with
event codes indicating they were aborted due to the CLOSE. Users
should wait for event codes for each SEND before closing the
connection if they wish to be certain that all letters were
successfully delivered.
The user may CLOSE the connection at any time on his own initiative,
or in response to various prompts from the TCP [remote close
executed, transmission timeout exceeded, destination inaccessible].
Because closing a connection requires communication with the foreign
TCP, connections may remain in the closing state for a short time.
Attempts to reopen the connection before the TCP replies to the CLOSE
command will result in errors.
Responses from the TCP which may occur as a result of this call are
detailed in section 2.4.
2.3.6 INTERRUPT
Format: INTERRUPT(local connection name)
A special control signal is sent to the destination indicating an
interrupt condition. This facility can be used to simulate "break"
signals from terminals or error or completion codes from I/O devices,
for example. The semantics of this signal to the receiving process
are unspecified. The receiving TCP will signal the interrupt to the
receiving process immediately upon receipt, and will also flush any
outstanding letters waiting to be delivered. Since it is possib1e to
tell where in the letter stream this command was invoked, it is
possible for the receiving TCP to flush only preceding data. The
sending TCP will flush any letters pending transmission, returning a
special error code to indicate the flush.
If the connection is not open or the calling process is not
authorized to use this connection, an error is returned.
Responses from the TCP which may occur as a result of this call are
detailed in section 2.4.
2.3.7 STATUS
Format: STATUS(local connection name)
This command returns a data block containing the following
information:
local socket, foreign socket, local connection name, receive window,
send window, connection state, number of letters awaiting
acknowledgment, number of letters pending receipt [including partial
ones], default transmission timeout
Depending on the state of the connection, some of this information
may not be available or meaningful. If the calling process is not
authorized to use this connection, an error is returned. This
prevents unauthorized processes from gaining information about a
connection.
Responses from the TCP which may occur as a result of this call are
detailed in section 2.4.
2.4 TCP TO USER MESSAGES
2.4.1 TYPE CODES
All messages include a type code which identifies the type of user
call to which the message applies. Types are:
0 - General message, does not apply to a particular user call
1 - Applies to OPEN
2 - Applies to CLOSE
3 - Applies to INTERRUPT
10 - Applies to SEND
20 - Applies to RECEIVE
30 - Applies to STATUS
2.4.2 MESSAGE FORMAT [notional]
All messages include the following three fields:
Type code
Local connection name
Event code
For message types 0-3 [General, Open, Close, Interrupt] only these
three fields are necessary.
For message type 10 [Send] one additional field is necessary:
Buffer address
For message type 20 [Receive] three additional fields are necessary:
Buffer address
Byte count
End-of-letter flag
For message type 30 [status] additional data might include;
Local socket, foreign socket
Send window [measures buffer space at foreign TCP]
Receive window [measures buffer space at local TCP]
Connection state [see section 4.3.6]
Number of letters awaiting acknowledgment
Number of letters awaiting receipt
Retransmission timeout
2.4.3 EVENT CODES
The event code specifies the particular event that the TCP wishes to
communicate to the user.
In addition to the event code, three flags may be useful to classify
the event into major categories and facilitate event processing by
the user:
E flag: set if event is an error
L/F flag: indicates whether event was generated by Local TCP, or
Foreign TCP or network
P/T flag: indicates whether the event is Permanent or Temporary
[retry may succeed]
Events are encoded into 8 bits with the high order bits set to
indicate the state of the E, L/F, and P/T flags, respectively.
Events specified so far are listed below with their codes and flag
settings. A * means a flag does not apply or can take both values for
this event. Additional events may be defined in the course of
experimentation.
0 0** general success
1 ELP connection illegal for this process
2 OF* unspecified foreign socket has become bound
3 ELP connection not open
4 ELT no room for TCB
5 ELT foreign socket unspecified
6 ELP connection already open
EFP unacceptable SYN [or SYN/ACK] arrived at foreign
TCP. Note: This is not a misprint, the local meaning is different
from foreign.
7 EFP connection does not exist at foreign TCP
8 EFT foreign TCP inaccessible [may have subcases]
9 ELT retransmission timeout
10 E*P buffer flushed due to interrupt
11 OF* interrupt to user
12 **P connection closing
13 E** general error
14 E*P connection reset
Possible events for each message type are as follows:
Type 0[general]: 2,11,12,14
Type 1[open]: 0,1,4,6,13
Type 2[close]: 0,1,3,13
Type 3[interrupt]: 0,1,3,5,7,8,9,12,13
Type 10[send]: 0,1,3,5,7,8,9,10,11,12,13
Type 20[receive]: 0,1,3,10,12,13
Type 30[status]: 0,1,13
Note that events 6(foreign), 7, 8 are generated at the foreign TCP or
in the network[s], and these same codes are used in the error field
of the internet packet [see section 4.2.1].
3. HIGHER LEVEL PROTOCOLS
3.1 INTRODUCTION
It is envisioned that the TCP will be able to support higher level
protocols efficiently. It should be easy to interface existing
ARPANET protocols like TELNET and FTP to the TCP.
3.2 WELL KNOWN SOCKETS
At some point, a set of well known 24 bit port numbers must be
picked. The type of service associated with the well known ports
might include:
(a) Logger
(b) FTP (File transfer protocol)
(c) RJE (Remote job entry)
(d) Host status
(e) TTY Test
(f) HELP - descriptive, interactive system documentation
WE RESERVE WELL KNOWN SOCKET 0 (24 bits of 0) for global messages
destined for a particular TCP but not related to any particular
connection. We imagine that this socket would be used for unusual TCP
synchronization (e.g. RESET ALL) or for testing purposes (e.g.
sending letters to TRASHCAN or ECHO). This does not conflict with the
usage that if a socket is 0, it is unspecified, since no user can
SEND, CLOSE, or INTERRUPT on socket 0.
3.3 RECONNECTION PROTOCOL (RCP)
Port identifiers fall into two categories: permanent and transient.
For example, a Logger process is generally assigned a port identifier
that is fixed and well known. Transient processes will in general
have ID's which are dynamically assigned.
In the distributed processing environment of the network, two
processes that don't have well known port identifiers may often wish
to communicate. This can be achieved with the help of a well known
process using a reconnection protocol. Such a protocol is briefly
outlined using the communication facilities provided by the TCP. It
essentially provides a mechanism by which port identifiers are
exchanged in order to establish a connection between a pair of
sockets.
Such a protoco1 can be used to achieve the dynamic establishment of
new connections in order to have multiple processes solving a problem
cooperatively, or to provide a user process access to a server
process via a logger, when the logger's end of the connection can not
be invisibly passed to the server process.
A paper on this subject by R. Schantz [SCHA74] discusses some of the
issues associated with reconnection, and some of the ideas contained
therein went into the design of the protocol outlined below.
In the ARPANET, a protocol was implemented which would allow a
process to connect to a well known socket, thus making an implicit
request for service, and then be switched to another socket so that
the well known socket could be freed for use by others. Since sockets
in our TCP are permitted to have connections with more than one
foreign socket, this facility may not be explicitly needed (i.e.
connections <A,B> and <A,C> are distinguishable).
However. the well known socket may be in one network and the actual
service socket(s) may be in another network (or at least in another
TCP). Thus, the invisible switching of a connection from one port to
another within a TCP may not be sufficient as an "Initial Connection
Protocol". We imagine that a process wishes to use socket N1.T1.Q to
access well known socket N2.T2.P. However, the process associated
with socket N2.T2.P will actually start up a new process somewhere
which will use N3.T3.S as its server socket. The N(i) and T(i) may be
distinct or the same. The user will send to N2.T2.P the relevant user
information such as user name, password, and account. The server will
start up the server process and send to N1.T1.Q the actual service
socket ldentif1er: N3.T3.S. The connection (N1.TI.Q,N2.T2.P) can then
be closed, and the user can do a RECEIVE on (N1.T1.Q,N3.T3.S). The
serving process can SEND on (N3.T3.S,N1.T1.Q). There are many
variations on this scheme, some involving the user process doing a
RECEIVE on a different socket (e.g. (N1.T1.X,U.U.U)) with the server
doing SEND on (N3.T3.S,N1.T1.X). Without showing all the detail of
synchronization of sequence numbers and the like, we can illustrate
the exchange as shown below.
USER SERVER
1. RECEIVE(N2.T2.P,U.U.U)
1. SEND (N1.T1.Q,N2.T2.P)==>
<== 2. SEND(N2.T2.P,N1.T1.Q)
With "N3.T3.S" as data
2. RECEIVE(N1.T1.Q,N2.T2.P)
3. CLOSE(N1.T1.Q,N2.T2.P)==>
<:= 3. CLOSE(N2.T2.P,N1.T1.Q)
4. RECEIVE(N1.T1.Q,N3.T3.S)
<== 4. SEND(N3.T3.S,N1.T1.Q)
At this point, a connection is open between N1.T1.Q and N3.T3.S. A
variation might be to have the user do an extra RECEIVE on
(N1.T1.X,U.U.U) and have the data "N1.T1.X" be sent in the first user
SEND. Then, the server can start up the real serving process and do a
SEND on (N3.T3.S,N1.T1.X) without having to send the "N3.T3.S" data
to the user. Or perhaps both server and receiver exchange this data,
to assure security of the ultimate connection (i.e. some wild process
might try to connect to N1.T1.X if it is merely RECEIVING on foreign
socket U.U.U.).
We do not propose any specific reconnection protocol here, but leave
this to further deliberation, since it is really a user level
protocol issue.
4. TCP IMPLEMENTATION
4.1 INTRODUCTION
Conceptually, the TCP is made up of several processes. Some of these
deal with USER/TCP commands, and others with packets arriving from
the network. The TCP also has an internal measurement facility which
can be activated remotely.
Any particular TCP could be viewed in a number of ways. It could be
implemented as an independent process, servicing many user processes.
It could be viewed as a set of re-entrant library routines which
share a common interface to the local PSN, and common buffer storage.
It could even be viewed as a set of processes, some handling the
user, some the input of packets from the net, and some the output of
packets to the net.
4.2 TCP DATA STRUCTURES
4.2.1 INTERNETWORK PACKET FONMAT
8 bits: Internet information
2 bits: Reserved for local PSN use
2 bits: Header format (11 in binary)
4 bits: Protocol version number
8 bits: Header length in octets (32 is the current value)
16 bits: Length of text in octets
32 bits: Packet sequence number
32 bits: Acknowledgment number (i.e. sequence number of next octet
expected).
16 bits: Window size (in octets)
16 bits: Control Information
Listed from high to low order:
SYN: Request to synchronize sending sequence numbers
ACK: There is a valid acknowledgment in the 32 bit ACK field
FIN: Sender will stop SENDing and RECEIVEing on this connection
DSN: The sender has stopped using sequence numbers and wants to
initiate a new sequence number for sending.
EOS: This packet is the end of a segment and therefore has a
checksum in the 16 bit checksum field. If this bit is not set, the
16 bit checksum field is to be ignored. The bit is usually set,
but if fragmentation at a GATEWAY occurs, the packets preceding
the last one will not have checksums, and the last packet will
have the checksum for the entire original fragment (segment) as it
was calculated by the sending TCP.
EOL: This packet contains the last fragment of a letter. The EOS
bit will always be set in this case.
INT: The sender wants to INTERRUPT on this connection.
XXX: six (6) unused control bits
OD: three (3) bits of control dispatch:
000: Null (the control octet contents should be ignored}
001: Event Code is present in the control octet. These were
defined in section 2.4.3.
010: Special Functions
011: Reject (codes as yet undefined)
1XX: Unused
8 bits: Control Data Octet
If CD is 000 then this octet is to be ignored.
If CD is 001, this octet contains event codes defined in section
2.4.3
If CD is 010, this octet contains a special function code as
defined below:
0: RESET all connections between Source and Destination TCPs
l: RESET the specific connection referenced in this packet
2: ECHO return packet to sender with the special function code
ECHOR (Echo Reply).
3: QUERY Query status of connection referenced in this packet
4: STATUS Reply to QUERY with requested status.
5: ECHOR Echo Reply
6: TRASH Discard packet without acknowledgment
>6: Unused
Note: Special function packets not pertaining to a particular
connection [RESET all, ECHO, ECHOR, and TRASH] are normally
sent using socket zero as described in section 3.2.
If CD is 01l, this octet contains an as yet undefined REJECT code.
If CD is 1XX, this octet is undefined.
4 bits: Length of destination network address in 4 bit units (current
value is 1)
4 bits: Destination network address
1010-1111 are addresses of ARPANET, UCL, CYCLADES, NPL, CADC, and
EPSS respectively.
16 bits: Destination TCP address
8 bits: Padding
4 bits: length of source network address in 4 bit units (current
value is 1)
4 bits: source network address (as for destination address)
16 bits: Source TCP address
24 bits: Destination port address
24 bits: Source port address
16 bits: Checksum (if EOS bit is set)
4.2.2 TRANSMISSION CONTROL BLOCK
It is highly likely that any implementation will include shared data
structures among parts of the TCP and some asynchronous means of
signaling users when letters have been delivered.
One typical data structure is the Transmission Control Block (TCB)
which is created and maintained during the lifetime of a given
connection. The TCB contains the following information (field sizes
are notional only and may vary from one implementation to another):
16 bits: Local connection name
48 bits: Local socket
48 bits: Foreign socket
16 bits: Receive window size in octets
32 bits: Receive left window edge (next sequence number expected)
16 bits: Receive packet buffer size of TCB (may be less than
window)
16 bits: Send window size in octets
32 bits: Send left window edge (earliest unacknowledged octet)
32 bits: Next packet sequence number
16 bits: Send packet buffer size of TCB (may be less than window)
8 bits: Connection state
E/C - 1 if TCP has been synchronized at least once (i.e. has
been established, else O, meaning it is closed; this bit is
reset after FINS are exchanged and the user has done a CLOSE).
The bit is not reset if the connection is only desynchronized
on send or receive or both directions.
SS - SYNCed on send side (if set) else desynchronized
SR - SYNCed on receive side (if set, else desynchronized)
16 bits: Special flags
S1 - SYN sent if set
S2 - SYN verified if set
R - SYN received if set
Y - FIN sent if set
C - CLOSE from local user received if set
U - Foreign socket unspecified if set
SDS - Send side DSN sent if set
SDV - Send side DSN verified if set
RDR - Receive side DSN received if set
Initially, all bits are off [no pun intended] (i.e. SS, SR, E/C, S1,
S2, R, F, C, SDS, SDV, RDR =0). When R is set, so is SR. When S1 and
S2 are both set, so is SS. SR is reset when RDR is set. SS is reset
when both SDS and SDV are set. These bits are used to keep track of
connection state and to aid in arriving packet processing (e.g. Can
sequence number be validated? Only if SR is set.).
16 bits: Retransmission timeout (in eighths of a second#]
16 bits: Head of Send buffer queue [buffers SENT from user to TCP,
but not packetized]
16 bits: Tail of Send buffer queue
16 bits: Pointer to last octet packetized in partially packetized
buffer (refers to the buffer at the head of the queue)
16 bits: Head of Send packet queue
16 bits: Tail of Send packet queue
16 bits: Head of Packetized buffer Queue
16 bits: Tail of Packetized buffer queue
16 bits: Head of Retransmit packet queue
16 bits: Tail of Retransmit packet queue
16 bits: Head of Receive buffer queue [queue of buffers given by user
to RECEIVE letters, but unfilled]
16 bits: Tail of Receive buffer queue
16 bits: Head of Receive packet queue
16 bits: Tail of receive packet queue
16 bits: Pointer to last contiguous receive packet
16 bits: Pointer to last octet filled in partly filled buffer
16 bits: Pointer to next octet to read from partly emptied packet
[Note: The above two pointers refer to the head of the receive
buffer and receive packet queues respectively]
16 bits: Forward TCB pointer
16 bits: Backward TCB pointer
4.3 CONNECTION MANAGEMENT
4.3.1 INITIAL SEQUENCE NUMBER SELECTION
The protocol places no restriction on a particular connection being
used over and over again. New instances of a connection will be
referred to as incarnations of the connection. The problem that
arises owing to this is, "how does the TCP identify duplicate packets
from previous incarnations of the connection?". This problem becomes
harmfully apparent if the connection is being opened and closed in
quick succession, or if the connection breaks with loss of memory and
is then reestablished.
The essence of the solution [TOML74] is that the initial sequence
number [ISN] must be chosen so that a particular sequence number can
never refer to an "o1d" octet, Once the connection is established the
sequencing mechanism provided by the TCP filters out duplicates.
For an association to be established or initialized, the two TCP's
must synchronize on each other's initial sequence numbers. Hence the
solution requires a suitable mechanism for picking an initial
sequence number [ISN], and a slightly involved handshake to exchange
the ISN's. A "three way handshake" is necessary because sequence
numbers are not tied to a global clock in the network, and TCP's may
have different mechanisms for picking the ISN's. The receiver of the
first SYN has no way of knowing whether the packet was an old delayed
one or not, unless it remembers the last sequence number used on the
connection which is not always possible, and so it must ask the
sender to verify this SYN.
The "three way handshake" and the advantages of a "clock-driven"
scheme are discussed in [TOML74]. More on the subject, and algorithms
for implementing the clock-driven scheme can be found in [DALA74].
4.3.2 ESTABLISHING A CONNECTION
The "three way handshake" is essentially a unidirectional attempt to
establish the connection, i.e. there is an initiator and a responder.
The TCP's should however be able to establish the connection even if
a simultaneous attempt is made by both TCP's to establish the
connection. Simultaneous attempts are treated like "collisions" in
"Aloha" systems and these conflicts are resolved into unidirectional
attempts to establish the connection. This scheme was adopted because
(i) Connections will normally have a passive and an active end,
and so the mechanism should in most cases be as simple as
possible.
(ii) It is easy to implement as special cases do not have to be
accounted for.
The example below indicates what a three way handshake between TCP's
A and B looks like
A B
--> <SEQ x><SYN> -->
<-- <SEQ y><SYN, ACK x+l> <--
--> <SEQ x+1><ACK y+l><DATA BYTES> -->
The receiver of a "SYN" is able to determine whether the "SYN" was
real (and not an old duplicate) when a positive "ACK" is returned for
the receiver's "SYN,ACK" in response to the "SYN". The sender of a
"SYN" gets verification on receipt of a "SYN,ACK" whose "ACK" part
references the sequence number proposed in the original "SYN" [pun
intended]. If the TCP is in the state where it is waiting for a
response to its SYN, but gets a SYN instead, then it always thinks
this is a collision and goes into the state prior to having sent the
SYN, i.e. it forgets that it had sent a SYN. The TCP will try to
establish the connection again after some time, unless it has to
respond to an arriving SYN. Even if the wait times in the two TCPs
are the same, the varying delays in network transmission will usually
be adequate to avoid a collision on the next cycle of attempts to
send SYN.
When establishing a connection, the state of the TCP is represented
by 3 bits --
S1 S2 R
S1 = 1 -- SYN sent
S2 = 1 -- My SYN verified
R = 1 -- SYN received
Some examples of attempts to establish the connection are now shown.
The state of the connection is indicated when a change occurs. We
specifically do not show the cases in which connection
synchronization is carried out with packets containing both SYN and
data. We do this to simplify the explanation, but we do not rule out
an implementation which is capable of dealing with data arriving in
the first packet (it has to be stored temporarily without
acknowledgment or delivery to the user until the arriving SYN has
been verified).
The "three way handshake" now looks like --
A B
------------ ------------
S1 S2 R S1 S2 R
0 0 0 0 0 0
--> <SEQ x><SYN> -->
1 0 0 0 0 1
<-- <SEQ y><SYN, ACK x+l> <--
1 1 1 1 0 1
--> <SEQ x+1><ACK y+1>(DATA OCTETS) -->
1 1 1 1 1 1
The scenario for a simultaneous attempt to establish the connection
without the arrival of any delayed duplicates is --
A B
------------ ------------
S1 S2 R S1 S2 R
0 0 0 0 0 0
(M1) 1 0 0 --> <SEQ x><SYN> ...
(M2) 0 0 0 <-- <SEQ y><SYN) <-- 1 0 0
(M1) B returns no SYN sent --> 0 0 0
(M1) 1 0 0 --> <SEQ z><SYN> * --> 0 0 1
(M3) 1 1 1 <-- <SEQ y+1><SYN,ACK z+1> <-- 1 0 1
(M4) 1 1 1 --> <SEQ z+1><ACK y+1><DATA> --> 1 1 1
Note: "..." means that a message does not arrive, but is delayed
in the network. State changes are upon arrival or upon departure
of a given message, as the case may be. Packets containing the SYN
or INT or DSN bits implicitly contain a "dummy" data octet which
is never delivered to the user, but which causes the packet
sequence numbers to be incremented by 1 even if no real data is
sent. This permits the acknowledgment of these controls without
acknowledging receipt of any data which might also have been
carried in the packet. A packet containing a FIN bit has a dummy
octet following the last octet of data (if any) in the packet.
* Once in state 000 sender selects new ISN z when attempting to
establish the connection again.
4.3.3 HALF-OPEN CONNECTIONS
An established connection is said to be a "half-open" connection if
one of the TCP's has closed the connection at its end without the
knowledge of the other, or if the two ends of the connection have
become desynchronized owing to a crash that resulted in loss of
memory. Such connections will automatically become reset if an
attempt is made to send data in either direction. However, half-open
connections are expected to be unusual, and the recovery procedure is
somewhat involved.
If one end of the connection no longer exists, then any attempt by
the other user to send any data on it will result in the sender
receiving the event code "Connection does not exist at foreign TCP".
Such an error message should indicate to the user process that
something is wrong and it is expected to CLOSE the connection.
Assume that two user processes A and B are communicating with one
another when a crash occurs causing loss of memory to B's TCP.
Depending on the operating system supporting B's TCP, it is likely
that some error recovery mechanism exists. When the TCP is up again B
is likely to start again from the beginning or from a recovery point.
As a result B will probably try to OPEN the connection again or try
to SEND on the connection it believes open. In the latter case 1t
receives the error message "connection not open" from the local TCP.
In an attempt to establish the connection B's TCP will send a packet
containing SYN. A's TCP thinks that the connection is already
established and so will respond with the error "unacceptable SYN (or
SYN/ACK) arrived at foreign TCP". B's TCP knows that this refers to
the SYN it just sent out, and so should reset the connection and
inform the user process of this fact.
It may happen that B is passive and only wants to receive data. In
this case A's data will not reach B because the TCP at B thinks the
connection is not established. As a result A'S TCP will timeout and
send a QRY to B's TCP. B's TCP will send STATUS saying the connection
is not synched. A's TCP will treat this as if an implicit CLOSE had
occurred and tell the user process, A, that the connection is
closing. A is expected to respond with a CLOSE command to his TCP.
However, A's TCP does not send a FIN to B's TCP, since it would not
be accepted anyway on the unsynced connection. Eventually A will try