path: root/doc/rfc/rfc635.txt

Network Working Group                                        Vinton G. Cerf
Request for Comments: 635                               Stanford University
NIC: 30489

                  An Assessment of ARPANET Protocols

                          
ABSTRACT

This paper presents some theoretical and practical
motivations for the redesign of the ARPANET communication
protocols. Issues concerning multipacket messages,
Host retransmission, duplicate detection, sequencing,
and acknowledgment are discussed. Simplifications
to the IMP/IMP protocol are proposed on the assumption
that new Host level protocols are adopted. Familiarity
with the current protocol designs is probably necessary
since many of the arguments refer to details in the
present protocol design.

                               [Page 0]

RFC  635           An Assessment of ARPANET Protocols              May 1974

Introduction.

     The history of the Advanced Research Project Agency resource
sharing computer network (ARPANET) [6] is in many ways a history of
the study, development, and implementation of protocols. During the
early development of the network many important concepts were dis-
covered and introduced into the protocol design effort. Protocol
layering (functional separation of different levels of network trans-
mission), the notion of bilateral rendezvous to set up Host-to-Host
connections [l,2], and the definition of a Network Virtual Terminal
to aid in the specification of a Terminal-to-Host protocol [3,14] are
all examples of important early ideas. The tasks facing the ARPANET
design teams were often unclear, and frequently required agreements
which had never been contemplated before (e.g., common protocols to
permit different operating systems and hardware to communicate). The
success of the effort, seen in retrospect, is astonishing, and much
credit is due to those who were willing to commit themselves to the job
of putting the ARPANET together.

     Over the intervening five years since the ARPANET was first begun,
we have learned a great deal about the design and behavior of the proto-
cols in use. The Imp-to-Imp protocol [4] has undergone continuous re-
vision, and the HOST/IMP interface specification [5] has been modified
slightly. In retrospect and in the light of experience, it seems
reasonable to reconsider some of the aspects of the designs and implemen-
tations currently in use. Furthermore, the rapid development of national

                               [Page 1]

RFC  635           An Assessment of ARPANET Protocols              May 1974


computer network projects around the world emphasizes the need for
international cooperation in the design of communication protocols so
that international connections can be accomplished.

     This paper deals with the motivations for the redesign of the
HOST-to-HOST, IMP-to-IMP, and HOST/IMP communication protocols in the
ARPANET. Analyses of theoretical throughput and delay available from
existing protocols, and a discussion of some weaknesses in them, are
included.

     The basic conclusions reached in this report are:

     a) Multipacket message facilities can be eliminated without loss
        of potential throughput, and with a concurrent simplification of
        IMP software. [8]  

     b) Ordering by the destination IMP of messages delivered to a destina-
        tion HOST can lead to a lockup condition similar to the reassembly
        lockup experienced in an earlier version of the IMP protocol in
        connection with multipacket message reassembly [7]. Hosts must
        order arriving messages anyway, so the IMP need not do it.

     c) HOST/IMP protocol could be changed to allow arbitrarily long
        messages to be sent from HOST to IMP, as long as the destination
        IMP need not reassemble or re-order the arriving packets before
        delivery to the HOST.

     d) Host level retransmission, positive end-to-end acknowledgments,
        error detection, duplicate detection, and message ordering, can
        eliminate the need for many of these features in the IMP/IMP
        protocol, and the Request for next Message (RFNM) facility in the
        present HOST/IMP protocol.

                               [Page 2]

RFC  635           An Assessment of ARPANET Protocols              May 1974


     e) The flow control mechanism in the current HOST-HOST protocol can
        lose synchronization owing to message loss or duplication.

     f) Host level connections should be full duplex.

     g) The need for a separate HOST/HOST control connection can be
        eliminated by carrying control information in the header of each
        Host transmission.
             
Throughput Considerations.

     In spite of the fact that the IMP subnet can deliver up to 80 kb/sec
between pairs of Hosts^, virtually no application using Host software
has achieved this figure. An experiment between Tinker and McClellan
Air Force Bases in 1971 achieved burst rates as high as 40 kb/sec, but
this was achieved by the use of a non-standard Host/Host protocol which
transmitted data over multiple logical connections, and which used Host
level re-assembly and acknowledgement to achieve reliable, ordered trans-
mission ^^. The following analysis shows that the current Host/Host
protocol cannot offer more than 40 kb/sec on a single connection owing
to message format overhead, and that this figure drops hyperbolically
if the communicating Hosts are separated by several IMPs.

     The single major reason for the distance (hop) dependent behavior
of Host/Host throughput is the "message-at-a-time" Host/Host
protocol. This means that, on a given connection between processes in
______________________________
^  Unpublished measurement experiments at UCLA run by R. Kahn and V.
   Cerf confirmed this.
^^ Unpublished measurement data obtained by V. Cerf at the ARPA Network
   Measurement Center, UCLA.

                               [Page 3]

RFC  635           An Assessment of ARPANET Protocols              May 1974


the Hosts, only a single message ranging from 0-8063 bits of data can
be outstanding at any moment. When the Host/Host protocol was originally
designed, the IMPs provided up to 256 simplex 1ogical links between pairs
of Hosts. If a message was sent over a link (there was a one to one
relationship between a link and a connection), the link was blocked until
a RFNM was received from the destination IMP indicating that the message
had been delivered to the Host. Of course, the mechanism was protected
by a time-out in case the RFNM failed to appear.

    The IMP protocol has since been changed considerably and now permits
up to n messages^ to be outstanding between pairs of IMPs, regardless
of the links used and regardless of which Hosts are communicating.

    This last point means that there can be some interference among Hosts
connected to the same IMP if the Hosts are communicating with the same
destination IMP.

    The Host/Host protocol has not been changed to take advantage of the
possibility of multiple messages and is unable to achieve maximum possible
throughput. In figure 1, the time behavior of a multipacket message is
shown as it passes through several IMPs from source to destination.


        ------------------------------------
IMP(0)  | pkt(0) | pkt(1) | ... | pkt(m-1) |
        ------------------------------------
        |        | ------------------------------------
IMP(1)  |        | | pkt(0) | pkt(1) | ... | pkt(m-1) |
        |        | ------------------------------------
        |        | |                    :
        |        | |                    :
        |        | |        ------------------------------------
IMP(h-1)|        | |        | pkt(0) | pkt(1) | ... | pkt(m-1) |
        |<------>| |<-      ------------------------------------
            \     \
             \     `---> propagation delay from IMPO to IMPl
              `-->  packet transmission delay

Packet handling by h IMPs for an m-packet message 

                    Figure 1
______________________________
^ currently four, this limit being imposed by IMP buffer space.

                               [Page 4]

RFC  635           An Assessment of ARPANET Protocols              May 1974


Figure 1 is naive in several ways. First, it does not show any
interfering traffic, nor have any packets gotten out of order or been
routed on alternate paths. Second, all packets are assumed to be the
same maximum size. Furthermore, the figure does not show the transmission
delay to and from the Hosts. Thus, the results of the analysis will be
slightly optimistic.

    The logical connection between Hosts will be busy only for m packet
times out of h+m-l packet times. The source IMP will be busy for m
packet transmission times sending the message to a neighboring IMP. The
last bit of the first packet will arrive at the destination IMP after h
packet transmission times (not counting propagation delay) and the re-
maining m-1 packets will complete arrival after m-l packet transmission
times. The source Host will be permitted to transmit another message
after it receives a RFNM from the destination IMP. The RFNM is actually
sent after the message has been reassembled, the first packet has been
delivered, and the destination IMP has sufficient free buffer space for
another maximum length multipacket message.^ Thus a new transmission
cannot occur until h+m-1 packet times, at least, so the fraction of busy
time is just m/(h+m-l).

    The actual bandwidth between IMPs is reduced from 50 kb^^ to 40 kb
by overhead bits needed for Host/Host, IMP/IMP control. IMPs send periodic
routing messages to all their neighbors (every .640 seconds)^^^ and these
consume further bandwidth. We can estimate the nominal fraction of 50 kb/sec
bandwidth available from source to destination IMP and multiply this by the
fractional busy time per connection to obtain an optimistic bound on maximum
throughput per connection.
______________________________
^  If after 1 second no space is available, the RFNM is sent anyway.
^^ Some IMPs have 230 kb/sec lines, or 9.6 kb/sec, but most have 50 kb/sec.
^^^This interval is a function of line speed and load and may be as low as 128 ms.

                               [Page 5]

RFC  635           An Assessment of ARPANET Protocols              May 1974


Analysis of Expected Throughput Bounds.

    Let T be the number of bits of text to be transmitted by a Host
whose natural word length is W bits. The Host/Host message format
includes a 32 bit leader followed by a 40 bit prefix, followed by the
text to be sent. We will assume that a sending Host will transmit an
integral number of its words, including the 72 bits preceding the text
of the message. Furthermore, the Host/IMP interface appends a one bit
to each message, followed by as many zeroes as are needed to make the
ensemble an integral number of 16 bit IMP words (the IMP is a Honeywell
316 or 516 computer).

    The total number of bits in a Host message whose text contains T
bits is given by equation 1.
    
          M(T,W) = B1 (T) + B2 (T,W) + B3(T,W)                   (1)
          where B1(T)     = T + 72

                B2(T,W)   = - B1(T) mod W

                B3(T,W) = 1 + (-B1(T) - B2(T,W) - 1) mod 16

    B1(T) is the number of bits in the Host message including leader,
prefix, and text. B2(T,W) is the number of bits needed to make B1(T)
an integral number of Host words, and B3(T,W) is the number of bits needed
to make the total an integral number of 16 bit IMP words.

    The M(T, W) bits are converted to packets in the following
way. The 32 bit leader is removed and the remaining words are divided
into packets containing no more than 1008 bits of data, each preceded
by an 96 bit header which includes the data from the 32 bit leader. When
these packets are transmitted to a neighboring IMP, they are enclosed

                               [Page 6]

RFC  635           An Assessment of ARPANET Protocols              May 1974


in a line control envelope consisting of 48 bits of control octets and
a 24 bit cyclic checksum. We can compute the number of bits required
to carry all the packets as follows:

              P(T,W) =( (M(T,W)-33)/1008 + 1 ) x 168 + M(T,W) - 32       (2)

    The line transmission efficiency when transmitting T bits of Host
text is given by.

          LTE(T,W) = T/P(T,W)                                    (3)

    The expected fraction of time a logical link, which is H hops long,
can be busy carrying a Host message of T text bits is given by

                            P(T,W)
        EBF(T,W,H) = _____________________________
                     H*min[P(T,W) , 1176]+ max [P(T,W)-1176 ,0]          (4)

EBF(T,W,H) is a refinement of the fraction computed earlier (m/(m+h-1)).

    The numerator of EBF(T,W,H) is just the number of bits which must be
transmitted from the source IMP. The denominator uses the min and max
functions to deal with the case that a message is less than a full single
packet in length. In any case, it takes H hops to deliver the first
packet, and the remaining bits follow this packet until the entire message
has arrived at the destination IMP. (Note that DLE may be doubled on the
line so that this calculation assumes 'DLE' never sent as data.)

    The routing messages require 1024 bits of text and 136 bits of packet
header and line control, and are sent by each IMP to all its adjacent
neighbors every .640 seconds. The bandwidth required for routing messages
is thus (1160)/.640 = 1.8 kb/sec.

    Thus the bandwidth which can be expected for Host messages containing
T text bits, sent over H hops, is expressed in equation (5) below.

    B(T,W,H) = EBF(T,W,H) x LTE(T,W) x (50-1.8) kb/sec           (5)

    B(T,W,H) ignores a number of complicating factors:

                               [Page 7]

RFC  635           An Assessment of ARPANET Protocols              May 1974


    a) delay for sending RFNM and implicit space reservation for
       multipacket messages to source IMP.

    b) propagation delays between Host/IMP and IMP/IMP

    c) queueing delays at intermediate IMPs

    d) retransmission delays
    Nevertheless, B(T,W,H) offers an optimistic estimate of the bandwidth
    that can be expected using the current ARPANET Host/Host protocol.

        There is an implicit assumption that packets of a multipacket message
    are not sent over alternate routes (e.g., two 50 kb/sec paths). Since
    alternate routing in the IMP subnet is used to avoid congested areas
    and not to improve bandwidth, this assumption is probably valid for the
    low traffic densities presently found in the ARPANET.

        B(T,W,H) has been plotted in figure 2 for a 32 bit Host (W=32), and
    a range of message text lengths and Hops. As can be seen, the effect
    of single message at a time transmission on a single logical connection
    is very marked for longer and longer hops. The curves would be even
    lower in the case of a satellite channel owing to the long propagation
    delay (1/4 second up and down) for both the message and the returning RFNM.

                               [Page 8]


42 ||
   ||
40 |||
   |||
38 |||8
   1||78
36  12|78
    12||78
34  123|678
    123456 78
32  1 23456  78
    1 2 3456   78
30  1 2 3 45 6  7 8
    1  2 3 45  6  7 8
28  1  2  3 4 5  6  7 8
    1  2   3 4  5  6  7 8
26  1  2    3 4   5  6  7 8
     1  2    3  4   5  6  7 8
24   1   2    3  4    5  6  7  8
     1    2    3  4     5  6  7  8
22   1     2    3   4     5  6  7   8
     1      2     3   4     5   6  7   8
20    1      2      3   4      5   6  7    8
       1       2      3   4       5   6   7      8  (8 Packets, 7992 bits)
18     1        2       3   4         5   6      7  (7 Packets, 7000 bits)
        1         2       3    4         5       6  (6 Packets, 5976 bits)
16       1         2        3     4         5
          1         2           3     4          5  (5 Packets, 4984 bits)
14         1          2            3       4
            1           2             3          4  (4 Packets, 3960 bits)
12            1           2                3
                1           2                    3  (3 Packets, 2968 bits)
10                1             2
                    1                 2
8                                                2  (2 Packets, 1944 bits)
                            1
6
                                      1
4                                                1  (1 Packet, 952 bits)

2
   1    2    3    4    5    6    7    8    9    10

               Number of Hops
        
Single Link Source to Destination Host Throughput (32 bit word Host)
                          Figure 2

                               [Page 9]

RFC  635           An Assessment of ARPANET Protocols              May 1974


The Multipacket Message Issue.

    The original IMP system permitted only one message at a time on a
single link, and thus some means was needed to allow for higher bandwidth
than single packet messages could provide. This was achieved, to some
extent, by permitting up to eight packets in a single message.

    It was soon discovered, however, that a Host transmitting multipackets
on separate logical links could cause a lockup condition at the destination,
and was first described by R. Kahn and W. Crowther [7].^ Essentially,
inadequate space might exist at the destination to reassemble all multi-
packets in transit on several links. The condition was self-sustaining
if the Host continued transmission, although the destination could
discard unassembled multipackets after a time-out. The condition either
backed up into the rest of the network, or at best caused loss of
messages in the network.

    The solution to the multipacket reassembly lockup problem that was
eventually implemented required the source IMP to reserve reassembly
buffer space at the destination IMP before transmitting the multipacket.

    Actually, this problem is just a case of a more general problem which can
be caused by the destination IMP sequencing of messages delivered to the
Host.

Ordering of Messages.

    The IMP system guarantees that messages wi1l be delivered to a
destination Host in the same order that they left a source Host. This
service can cause a lockup similar to reassembly lockup if enough messages
arc in transit to the destination IMP. Single packet messages are sent
without prior reservation to the destination and, if space is available
for them, a RFNM is returned to the source IMP. In the event that no
______________________________
^ Kahn actually knew in 1967 that the condition could occur, but was unable
  to convince his colleagues until he actually locked up the network by using
  a message generator to flood the network in March, 1970.

                               [Page 10]

RFC  635           An Assessment of ARPANET Protocols              May 1974


room is available, an implicit reservation request is queued at the
destination IMP. When space is available, an allocation message is sent
to the source IMP which retransmits the single packet message. The
source IMP keeps a copy of the single packet message for retransmission
until it either receives a RFNM from the first copy transmitted or an
allocate message indicating that there is now room available for a
second copy to be accepted.^

This scheme can fail if either a given Host has too many messages
in transit, or if many Hosts, served by different IMPs, have too many
messages in transit for the same destination. This is so because the
destination IMP will accept packets which arrive out of order and buffers
them until they can be re-ordered for transmission to the destination
Host.

    Presently, a source IMP only permits up to four messages (regardless
of length) to be in transit for a given destination at a time. This
essentially reduces the probability of a lockup, but it is not zero,
since sufficient messages may be outstanding from different IMPs for the
same destination to cause a lockup.

    Such lockups are protected against as well, by timing out undelivered
messages at the destination and discarding them. The timeout is on the
order of tens of seconds. Even though the IMP subnet can recover from
such conditions, it is apparent that Hosts must be prepared to retransmit
messages occasionally to recover from message loss caused by deliberate
discarding of messages at the destination or by catastrophic failures in
which an IMP loses all its packets upon crashing.
______________________________
^ R. Kahn, L. Kleinrock, and H. Opderbeck point out that IMPs do not accept
  out-of-order packets, but do send allocates back for them. If room is also
  allocated for unreceived but anticipated in-order packets, no lockup will
  occur. If this step is omitted, then the implementation may fail.

                               [Page 11]

RFC  635           An Assessment of ARPANET Protocols              May 1974


Host Retransmission, Sequencing, and Duplicate Detection.

    The Host/Host protocol docs not provide for retransmission. If it
did, however, then this would require that the destination Host detect
duplicate transmissions and also verify sequencing of arriving messages
since the destination IMP cannot, in the current scheme, detect that a
Host has sent a duplicate message.

    If this line of reasoning is pursued, it becomes evident that
sequencing of messages by the destination IMP is redundant and could be
eliminated. Furthermore, with the elimination of ordering, multipacket
messages could also be eliminated so long as Hosts were permitted to
transmit a sufficient number of single packet messages to achieve maximum
potential bandwidth.

    Along with Host retransmission, it is necessary to introduce some
kind of end-to-end positive acknowledgment. The RFNM is currently sent
by the destination IMP to the source Host and is taken to mean that a
message has been successfully delivered to the destination Host (for
multipacket messages, the RFNM is sent after the first packet has been
delivered). It seems sensible to arrange a Host level acknowledgment
which confirms delivery. In this case, the RFNM could also be eliminated.

    One might use RFNM's optionally as a debugging tool, to be turned off
and on at will.

    Statistics taken from the ARPANET indicate that Host retransmission
would rarely be required on account of message loss, but this is partly
because of the retransmission and reservation facilities in the current
IMP system.

                               [Page 12]

RFC  635           An Assessment of ARPANET Protocols              May 1974


Flow Control.

    If all end-to-end retransmission, duplicate, detection, and sequencing
are performed by Hosts, then it is essential that the source and destina-
tion Hosts agree upon a maximum number of packets (or bits, octets, etc.)
that can be outstanding at one time. Otherwise, the destination Host
may experience lockup problems similar to those found now in the destination
IMP.

    The current Host/Host flow control scheme has several weaknesses.

    First, it requires that special control messages be sent on a control
connection which is distinct from the connection on which data is transmitted.

    Second, it is an incremental scheme in which the destination Host allocates
a certain number of bits and messages which may be sent by the source.

    Both source and destination Hosts decrement these counts as messages are
sent and received. To maintain throughput, the destination must periodi-
cally send allocations to the source to replenish its available buffer
space. Destinations with small amount of buffer space (e.g., Terminal
IMPs or TIPs) must do this fairly frequently and thus generate considerable
control traffic. Third, the loss of an allocation or the duplication of
one can cause loss of synchrony between source and destination.

    In an earlier paper [9], the author and R. Kahn propose a more robust
flow control scheme including ideas found in the French CYCLADES network
[10]. Essentially, the receiver allocates a window representing the span
of sequence numbers that the sender may transmit. Acknowledgments from
the receiver to the sender indicate the largest sequence number received
so far (implicitly acknowledging all those preceding), and also indicate
the .current width of the window. The sender immediately knows which sequence

                               [Page 13]

RFC  635           An Assessment of ARPANET Protocols              May 1974


numbers can be sent next. The scheme also allows for duplicate detection
and reordering of messages.

    Acknowledgment and flow control information' is sent "piggy-back"
with data flowing in the reverse direction of a full duplex logical
connection so that a separate control connection is not needed for this
purpose. For example, a message is sent with sequence number M and
length L in octets. The receiver will respond with acknowledgment of
sequence number M+L and window size W. The sequence number of each
message is the sequence number of the previous message plus its length
in octets.

    The receiver can vary the size of W without any serious adverse
effect, and can survive the receipt of duplicates or the loss of messages
due to the retransmission and duplicate detection permitted by the scheme.

    The sender is not permitted to transmit a message whose sequence number
would exceed the sum of the last sequence number acknowledged plus the
current window size, W, modulo the maximum sequence number plus one.
Arbitrary Message Lengths.

    Until now, it has been implicit that multipacket messages are unneces-
sary for maintaining high throughput, as long as sufficient packets can
be sent to fill the delay pipeline from source to destination Host. If
the IMP system were programmed with knowledge of the Host/Host protocol
so that it could create a properly formatted Host/Host header for each
packet it transmits, given the initial header of an arbitrarily long
message, then packets could be delivered out of order to the destination
Host, so long as each correctly identified the range of sequence numbers
contained in each packet. Since each octet of a message has an implicit
sequence number, this would not be difficult to compute. An idea similar

                               [Page 14]

RFC  635           An Assessment of ARPANET Protocols              May 1974


to this is found in the Very Distant Host Reliable Transmission Package:
[appendix F, 5] in the current ARPANET, except in this case, a Host must
know about IMP packet format. It is debatable whether this would be a
good idea, since changes in Host/Host protocol would require changes in
IMP programming, but if it were implemented, then Hosts could send
arbitrarily long messages. The destination Host would receive a collec-
tion of single packet messages which it would then sequence as if they
had been sent that way by the source Host in the first place.

    Simplex versus Full-Duplex Logical Connections
The present Host/Host protocol implements simplex connections. The
usage over the last five years seems to indicate that most often, two
simplex connections are set up to act as a full duplex connection.

    If Host level acknowledgments and flow control are implemented, then it
is natural for them to be carried in the reverse direction of a full
duplex logical connection. Furthermore, terminal to Host connections
are necessarily full-duplex to allow for data to move in both directions.

    Finally, by embedding control in the headers of returning traffic on the
full duplex connection, the need for a separate control connection could
be eliminated.

Connection Set-up.

The current Host/Host protocol uses control messages sent on a
special control connection to establish new connections,. The procedure
is called the Initial Connection Protocol or ICP [11]. The protocol is
symmetric and requires that information be exchanged by both Hosts as
to the names of the sockets at either end of the connection. This
exchange precedes any flow of data. Other control messages are exchanged
which determine the buffer space available at the receiver.

                               [Page 15]

RFC  635           An Assessment of ARPANET Protocols              May 1974


    A proposal by D. Walden [12] suggests that this is largely unnecessary,
as long as both sides can simultaneously send data identifying the source
and destination sockets (Walden calls them Ports) along with the text of
the messages.

    A post office analogy is useful to describe what is intended. The
source Host writes a letter and encloses it in an envelope addressed to
the destination port with a return port address. Either the destination
port is willing to receive or it is not (e.g. it may not even be known
to the destination Host). In the former case, the letter is acknowledged
in the usual fashion. In the latter case, the letter is not acknowledged
(port unprepared to receive), or it is rejected ("address unknown").

    Since port addresses may be dynamically assigned to processes in a
destination Host, it will probably be necessary to include a formal con-
trol exchange which indicates to the sender that a receive port is being
closed, and the sender would be expected to acknowledge this. Similarly,
the sender may end a transmission with the indication that the send port
is being closed and the receiver would similarly acknowledge. Since
Hosts do the sequencing, there can be no confusion as to when the closure
is to take place. The rejection of an initial transmission can be made
to look like the closure of the destination port so that the number of
distinct control messages can be kept to a minimum. This method is
similar to the one currently used in the ARPANET, but could be carried
out via control bits in the Host level messages and thus eliminate the
need for a special control connection.

                               [Page 16]

RFC  635           An Assessment of ARPANET Protocols              May 1974


Summary.

    Arguments have been presented in this paper which show that multi-
packet reassembly is not the best vehicle for achieving high throughput
from Host to Host. The elimination of IMP reassembly as well as message
sequencing by the destination IMP can permit considerable simplification
of the IMP protocols, while simultaneously placing the. burden of buffering,
duplicate detection, and sequencing of messages on the Hosts which have
the buffer space for this purpose.

    Arbitrarily long messages could be sent by Hosts, at the expense of
IMP knowledge of Host protocol. Eliminating the ordering requirement
at the destination IMP also eliminates serious potential lockup conditions.

    Host level positive acknowledgments can eliminate the erroneous use
of the RFNM for this purpose, and permit a more robust protocol which
need not depend upon perfect performance without message loss by the
IMP subnet.

    Full duplex logical connections between ports in Hosts are more
natural than the simplex connections presently used, and facilitate the
elimination of the special control connection required in the current
Host protocol.
Unresolved Problems and Issues.

    Even if a source and destination Host have adequate buffer space to
permit a large number of messages (or packets, or octets) to be outstanding
between them, the IMP subnet must have a way of combating congestion
which may result from too rapid influx of data from a source Host, or
from momentary congestion owing to the confluence of excessive traffic
heading, in the same direction, possibly to the same destination. Alternate

                               [Page 17]

RFC  635           An Assessment of ARPANET Protocols              May 1974


routing strategies can help, but not completely solve the problem. One
possibility is to insist that source Hosts monitor actual throughput
achieved over the last few seconds (milliseconds?) and adjust output
rate accordingly. Destination Hosts can monitor this throughput as well,
and adjust the receive buffer space it allocates to the sender to reduce
unnecessary retransmissions. The IMPs can simply discard traffic which
cannot be buffered, knowing that the source will retransmit. IMPs
which discard packets to eliminate congestion could even send short
warning messages to source or destination (or both) to stimulate adjust-
ment. This is a very sticky problem and involves issues such as payment
by Hosts for retransmission. Most strategies in use today involve
limiting, a priori, the amount of data which a source Host is allowed
to send (e.g., isarhythmic network proposed by Davies [13]; maximum of
n messages allowed by ARPANET IMPs). Measurement of throughput
achieved by source and destination Hosts may be a good strategy in any
case since it serves as a measure of qua1ity of service provided by the
packet switchtng network.

    In the ARPANET, the TELNET protocol [14] for terminal to Host com-
munication has needed some way of signalling the Host in which the serving
process resides that any accumulated data should be discarded up to the
point of the "interrupt signal." This facility permits a remote user
to abort or recapture control from an uncooperative serving process
which has stopped accepting data. The current scheme involves the use
of a special interrupt signal sent on the control connection, but there
is a problem of synchronizing the interrupt request with the data in the
pipeline. This signal could be carried in the control field of a Host
message and would participate in the sequence numbering of the data, thus

                               [Page 18]

RFC  635           An Assessment of ARPANET Protocols              May 1974


providing for synchronization. Since the Host operating system would
process the message header before passing the data to the receiving port,
the interrupt could bypass processing by the receiving process and thus
provide the desired interrupt-like effect.

    There are undoubtedly many other problems and issues which could
not be mentioned in the scope of this paper, and the author would be
pleased if these and the preceding commentary will stimulate discussion
and thus further the general understanding of protocol requirements for
distributed computer networks.

Acknowledgments:

Throughput and delay analysis: some of the basic ideas in this
analysis are due to J. McQuillan (Bolt, Beranek, and Newman). Single
packet re-ordering lockup: first called to the author's attention by
P. Higginson (University 6f London). Host-Host Protocol Design:
developed largely under the auspices of the International Network Working
Group (IFIP TC6.1), and the author especially acknowledges contributions
by R. Kahn, R. Metcalfe, L. Pouzin and H. Zimmerman, as well as S. Crocker,
A. McKenzie, and R. Scantlebury. Numerous omissions and misstatements
were detected by R. Kahn, L. Kleinrock and H. Opderbeck.

    The author is grateful for the support of the Defense Advanced
Research Projects Agency under contract DAHC-15-73C-0435.

                               [Page 19]

RFC  635           An Assessment of ARPANET Protocols              May 1974


                              References
1.  McKenzie, A. "HOST/HOST Protocol for the ARPA Network," Current Network
    Protocols, Network Information Center, Stanford Research Institute,
    Menlo Park, California, January 1972 (NIC8246).

2.  Carr, S. and S. Crocker, V. Cerf, "HOST-HOST Communication Protocol
    in the ARPA Network, AFIPS 1970, SJCC Proceedings, Vol. 36, Atlantic
    City, AFIPS Press, New Jersey, pp. 589-597 [somewhat out of date].

3.  Crocker, S. D., and J. Heafner, R. Metcalfe, J. Postel, "Function-
    Oriented Protocols for the ARPA Computer Network," AFIPS 1972 SJCC
    Proceedings, Vol. 40, Atlantic City. AFIPS Press, New Jersey,
    pp. 271-279.

4.  Heart, F. E., and R. E. Kahn, et al, "The Interface Message Processor
    for the ARPA Computer Network, AFIPS 1970 SJCC Proceedings, Vol. 36,
    Atlantic City, AFIPS Press, New Jersey, pp. 551-567.

5.  Bolt, Beranek and Newman, Inc., "Specification for the Interconnection
    of a Host and an IMP," BBN Report 1822, April 1973 (Revised).

6.  Roberts, L. and B. Wessler, "Computer Network Development to Achieve
    Resource Sharing," AFIPS 1970, SJCC Proceedings, Vol. 36, Atlantic City,
    AFIPS Press, New Jersey, pp. 543-549.

7.  Kahn, R. E. and W. Crowther, "Flow Control in a Resource Sharing
    Computer Network," Second Symposium on Problems in the Optimization of
    Data Communications Systems, Palo Alto, October 1971, p. 108-116
    [also IEEE Transactions on Communication, June 1972].

8.  Kahn, R. E., "Resource Sharing Communication Networks," IEEE
    Proceedings, Nov. 1972.

9.  Cerf, V. G. and R. E. Kahn, "A Protocol for Packet Network Inter-
    communication," IEEE Transactions on Communication, vol. COM-22
    No. 5, May 1974 p 637-641. 

                               [Page 20]

RFC  635           An Assessment of ARPANET Protocols              May 1974


10.  Pouzin, L., "Presentation and Major Design Aspects of the CYCLADES
     Computer Network," Data Networks: Analysis and Design, Third Data
     Communications Symposium, St. Petersburg, Florida, November 1973,
     pp. 80-87.

11.  Postel, J., "Official Initial Connection Protocol," Current Network
     Protocols, Network Information Center, Stanford Research Institute,
     Menlo Park, California, January 1972 (NIC 7101).

12.  Walden, D., 'A System for Interprocess Communication in a Resource
     Sharing Computer Network, Communications of the ACM, 15, 4, April 1972,
     pp. 221-230 (NIC 9926).

13.  Davies, D., "Communication Networks to Serve Rapid Response
     Computers," Information Processing 68, Proceedings of IFIP Congress
     1968, Vol. 2, Edinburgh, Scotland, 1968, North-Holland Publishing
     Co., Amsterdam, 1969, p. 650-658.

14.  McKenzie, A. "TELNET Protocol Specification," Current Network Protocols,
     Network Information Center, Stanford Research Institute, Menlo Park,
     California, August 1973 (NIC 18639, NIC 18638 - Revisions).

       [ This RFC was put into machine readable form for entry ]
       [ into the online RFC archives by Roger D. Moore, with  ]
       [ assistance from William M. Stewart on Figures 1 and 2,]
       [ 11/2006 ]

Notes by Roger D. Moore regarding copy and formatting changes:

A] Page numbers zero and one added to text

B] Paragraph indent in pages 1-3 is five; it is four spaces in pp 4++

C] All pen marked underlining from paper copy has been discarded.

D] Footnotes: The original text used a sequence of superscript
asterisks to mark a footnote.
I have replaced all of these with the character "^" which does not
 otherwise appear in the document. I have used a sequence of
underscore characters to
 to seperate text and notes at bottom of pages 3 4 5 10 11.

E] Formulae: On page six I have replaced symbols of the form "B
subscript digit" with "Bdigit"

F] Forumla [2] page seven: I have rewritten this to eliminate
horizontal line (division symbol).

G] Quarter symbol: page eight (last line) had a special symbol which I
have replaced with "1/4"

H] Marginal notes: I have preserved formulae notes from page
six. Others have been discarded.

I] Page numbers: I have left two blank lines after page header. Page
footer is incomplete
  but has the form [Page 9] or [Page 99]. RFCs in the archive have
some special character
  between the footer and header (ASCII formfeed?). I was unable to
enter this character.

J] Reference 9: I have included page numbers since this paper is now
published.

K] Figure 2 on page nine originally contained continuous curves in
heavy pencil, redrawn in ASCII.