Movatterモバイル変換

Network Working Group                                        Vinton G. CerfRequest for Comments: 635                               Stanford UniversityNIC: 30489                  An Assessment of ARPANET ProtocolsABSTRACTThis paper presents some theoretical and practicalmotivations for the redesign of the ARPANET communicationprotocols. Issues concerning multipacket messages,Host retransmission, duplicate detection, sequencing,and acknowledgment are discussed. Simplificationsto the IMP/IMP protocol are proposed on the assumptionthat new Host level protocols are adopted. Familiaritywith the current protocol designs is probably necessarysince many of the arguments refer to details in thepresent protocol design.                               [Page 0]

RFC  635           An Assessment of ARPANET Protocols              May 1974Introduction.     The history of the Advanced Research Project Agency resourcesharing computer network (ARPANET) [6] is in many ways a history ofthe study, development, and implementation of protocols. During theearly development of the network many important concepts were dis-covered and introduced into the protocol design effort. Protocollayering (functional separation of different levels of network trans-mission), the notion of bilateral rendezvous to set up Host-to-Hostconnections [l,2], and the definition of a Network Virtual Terminalto aid in the specification of a Terminal-to-Host protocol [3,14] areall examples of important early ideas. The tasks facing the ARPANETdesign teams were often unclear, and frequently required agreementswhich had never been contemplated before (e.g., common protocols topermit different operating systems and hardware to communicate). Thesuccess of the effort, seen in retrospect, is astonishing, and muchcredit is due to those who were willing to commit themselves to the jobof 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 modifiedslightly. In retrospect and in the light of experience, it seemsreasonable 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 1974computer network projects around the world emphasizes the need forinternational cooperation in the design of communication protocols sothat international connections can be accomplished.     This paper deals with the motivations for the redesign of theHOST-to-HOST, IMP-to-IMP, and HOST/IMP communication protocols in theARPANET. Analyses of theoretical throughput and delay available fromexisting protocols, and a discussion of some weaknesses in them, areincluded.     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/secbetween pairs of Hosts^, virtually no application using Host softwarehas achieved this figure. An experiment between Tinker and McClellanAir Force Bases in 1971 achieved burst rates as high as 40 kb/sec, butthis was achieved by the use of a non-standard Host/Host protocol whichtransmitted data over multiple logical connections, and which used Hostlevel re-assembly and acknowledgement to achieve reliable, ordered trans-mission ^^. The following analysis shows that the current Host/Hostprotocol cannot offer more than 40 kb/sec on a single connection owingto message format overhead, and that this figure drops hyperbolicallyif the communicating Hosts are separated by several IMPs.     The single major reason for the distance (hop) dependent behaviorof Host/Host throughput is the "message-at-a-time" Host/Hostprotocol. 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 1974the Hosts, only a single message ranging from 0-8063 bits of data canbe outstanding at any moment. When the Host/Host protocol was originallydesigned, the IMPs provided up to 256 simplex 1ogical links between pairsof Hosts. If a message was sent over a link (there was a one to onerelationship between a link and a connection), the link was blocked untila RFNM was received from the destination IMP indicating that the messagehad been delivered to the Host. Of course, the mechanism was protectedby a time-out in case the RFNM failed to appear.    The IMP protocol has since been changed considerably and now permitsup to n messages^ to be outstanding between pairs of IMPs, regardlessof the links used and regardless of which Hosts are communicating.    This last point means that there can be some interference among Hostsconnected to the same IMP if the Hosts are communicating with the samedestination IMP.    The Host/Host protocol has not been changed to take advantage of thepossibility of multiple messages and is unable to achieve maximum possiblethroughput. In figure 1, the time behavior of a multipacket message isshown 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 delayPacket 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 1974Figure 1 is naive in several ways. First, it does not show anyinterfering traffic, nor have any packets gotten out of order or beenrouted on alternate paths. Second, all packets are assumed to be thesame maximum size. Furthermore, the figure does not show the transmissiondelay to and from the Hosts. Thus, the results of the analysis will beslightly optimistic.    The logical connection between Hosts will be busy only for m packettimes out of h+m-l packet times. The source IMP will be busy for mpacket transmission times sending the message to a neighboring IMP. Thelast bit of the first packet will arrive at the destination IMP after hpacket transmission times (not counting propagation delay) and the re-maining m-1 packets will complete arrival after m-l packet transmissiontimes. The source Host will be permitted to transmit another messageafter it receives a RFNM from the destination IMP. The RFNM is actuallysent after the message has been reassembled, the first packet has beendelivered, and the destination IMP has sufficient free buffer space foranother maximum length multipacket message.^ Thus a new transmissioncannot occur until h+m-1 packet times, at least, so the fraction of busytime is just m/(h+m-l).    The actual bandwidth between IMPs is reduced from 50 kb^^ to 40 kbby overhead bits needed for Host/Host, IMP/IMP control. IMPs send periodicrouting messages to all their neighbors (every .640 seconds)^^^ and theseconsume further bandwidth. We can estimate the nominal fraction of 50 kb/secbandwidth available from source to destination IMP and multiply this by thefractional busy time per connection to obtain an optimistic bound on maximumthroughput 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 1974Analysis of Expected Throughput Bounds.    Let T be the number of bits of text to be transmitted by a Hostwhose natural word length is W bits. The Host/Host message formatincludes a 32 bit leader followed by a 40 bit prefix, followed by thetext to be sent. We will assume that a sending Host will transmit anintegral number of its words, including the 72 bits preceding the textof the message. Furthermore, the Host/IMP interface appends a one bitto each message, followed by as many zeroes as are needed to make theensemble an integral number of 16 bit IMP words (the IMP is a Honeywell316 or 516 computer).    The total number of bits in a Host message whose text contains Tbits 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 neededto make the total an integral number of 16 bit IMP words.    The M(T, W) bits are converted to packets in the followingway. The 32 bit leader is removed and the remaining words are dividedinto packets containing no more than 1008 bits of data, each precededby an 96 bit header which includes the data from the 32 bit leader. Whenthese packets are transmitted to a neighboring IMP, they are enclosed                               [Page 6]

RFC  635           An Assessment of ARPANET Protocols              May 1974in a line control envelope consisting of 48 bits of control octets anda 24 bit cyclic checksum. We can compute the number of bits requiredto 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 Hosttext 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 betransmitted from the source IMP. The denominator uses the min and maxfunctions to deal with the case that a message is less than a full singlepacket in length. In any case, it takes H hops to deliver the firstpacket, and the remaining bits follow this packet until the entire messagehas arrived at the destination IMP. (Note that DLE may be doubled on theline so that this calculation assumes 'DLE' never sent as data.)    The routing messages require 1024 bits of text and 136 bits of packetheader and line control, and are sent by each IMP to all its adjacentneighbors every .640 seconds. The bandwidth required for routing messagesis thus (1160)/.640 = 1.8 kb/sec.    Thus the bandwidth which can be expected for Host messages containingT 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||7836  12|78    12||7834  123|678    123456 7832  1 2345678    1 2 3456   7830  1 2 3 45 67 8    1  2 3 45  6  7 828  12  3 4 5  6  7 8    1  2   3 4  5  6  7 826  12    3 4   5  6  7 8     1  2    3  4   5  6  7 824   1 2    3  4    5  6  7  8     1    2    3  4     5  6  7  822   1   2    3   4     5  6  7   8     1      2     3   4     5   6  7   820    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                 28                                                2(2 Packets, 1944 bits)                            16                                      14                                                1(1 Packet, 952 bits)2   1    2    3    4    5    6    7    8    9    10               Number of HopsSingle Link Source to Destination Host Throughput (32 bit word Host)                          Figure 2                               [Page 9]

RFC  635           An Assessment of ARPANET Protocols              May 1974The Multipacket Message Issue.    The original IMP system permitted only one message at a time on asingle link, and thus some means was needed to allow for higher bandwidththan single packet messages could provide. This was achieved, to someextent, by permitting up to eight packets in a single message.    It was soon discovered, however, that a Host transmitting multipacketson 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-sustainingif the Host continued transmission, although the destination coulddiscard unassembled multipackets after a time-out. The condition eitherbacked up into the rest of the network, or at best caused loss ofmessages in the network.    The solution to the multipacket reassembly lockup problem that waseventually implemented required the source IMP to reserve reassemblybuffer space at the destination IMP before transmitting the multipacket.    Actually, this problem is just a case of a more general problem which canbe caused by the destination IMP sequencing of messages delivered to theHost.Ordering of Messages.    The IMP system guarantees that messages wi1l be delivered to adestination Host in the same order that they left a source Host. Thisservice can cause a lockup similar to reassembly lockup if enough messagesarc in transit to the destination IMP. Single packet messages are sentwithout prior reservation to the destination and, if space is availablefor 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 1974room is available, an implicit reservation request is queued at thedestination IMP. When space is available, an allocation message is sentto the source IMP which retransmits the single packet message. Thesource IMP keeps a copy of the single packet message for retransmissionuntil it either receives a RFNM from the first copy transmitted or anallocate message indicating that there is now room available for asecond copy to be accepted.^This scheme can fail if either a given Host has too many messagesin transit, or if many Hosts, served by different IMPs, have too manymessages in transit for the same destination. This is so because thedestination IMP will accept packets which arrive out of order and buffersthem until they can be re-ordered for transmission to the destinationHost.    Presently, a source IMP only permits up to four messages (regardlessof length) to be in transit for a given destination at a time. Thisessentially reduces the probability of a lockup, but it is not zero,since sufficient messages may be outstanding from different IMPs for thesame destination to cause a lockup.    Such lockups are protected against as well, by timing out undeliveredmessages at the destination and discarding them. The timeout is on theorder of tens of seconds. Even though the IMP subnet can recover fromsuch conditions, it is apparent that Hosts must be prepared to retransmitmessages occasionally to recover from message loss caused by deliberatediscarding of messages at the destination or by catastrophic failures inwhich 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 1974Host Retransmission, Sequencing, and Duplicate Detection.    The Host/Host protocol docs not provide for retransmission. If itdid, however, then this would require that the destination Host detectduplicate transmissions and also verify sequencing of arriving messagessince the destination IMP cannot, in the current scheme, detect that aHost has sent a duplicate message.    If this line of reasoning is pursued, it becomes evident thatsequencing of messages by the destination IMP is redundant and could beeliminated. Furthermore, with the elimination of ordering, multipacketmessages could also be eliminated so long as Hosts were permitted totransmit a sufficient number of single packet messages to achieve maximumpotential bandwidth.    Along with Host retransmission, it is necessary to introduce somekind of end-to-end positive acknowledgment. The RFNM is currently sentby the destination IMP to the source Host and is taken to mean that amessage has been successfully delivered to the destination Host (formultipacket messages, the RFNM is sent after the first packet has beendelivered). It seems sensible to arrange a Host level acknowledgmentwhich confirms delivery. In this case, the RFNM could also be eliminated.    One might use RFNM's optionally as a debugging tool, to be turned offand on at will.    Statistics taken from the ARPANET indicate that Host retransmissionwould rarely be required on account of message loss, but this is partlybecause of the retransmission and reservation facilities in the currentIMP system.                               [Page 12]

RFC  635           An Assessment of ARPANET Protocols              May 1974Flow Control.    If all end-to-end retransmission, duplicate, detection, and sequencingare 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 Hostmay experience lockup problems similar to those found now in the destinationIMP.    The current Host/Host flow control scheme has several weaknesses.    First, it requires that special control messages be sent on a controlconnection which is distinct from the connection on which data is transmitted.    Second, it is an incremental scheme in which the destination Host allocatesa certain number of bits and messages which may be sent by the source.    Both source and destination Hosts decrement these counts as messages aresent and received. To maintain throughput, the destination must periodi-cally send allocations to the source to replenish its available bufferspace. Destinations with small amount of buffer space (e.g., TerminalIMPs or TIPs) must do this fairly frequently and thus generate considerablecontrol traffic. Third, the loss of an allocation or the duplication ofone can cause loss of synchrony between source and destination.    In an earlier paper [9], the author and R. Kahn propose a more robustflow control scheme including ideas found in the French CYCLADES network[10]. Essentially, the receiver allocates a window representing the spanof sequence numbers that the sender may transmit. Acknowledgments fromthe receiver to the sender indicate the largest sequence number receivedso far (implicitly acknowledging all those preceding), and also indicatethe .current width of the window. The sender immediately knows which sequence                               [Page 13]

RFC  635           An Assessment of ARPANET Protocols              May 1974numbers can be sent next. The scheme also allows for duplicate detectionand reordering of messages.    Acknowledgment and flow control information' is sent "piggy-back"with data flowing in the reverse direction of a full duplex logicalconnection so that a separate control connection is not needed for thispurpose. For example, a message is sent with sequence number M andlength L in octets. The receiver will respond with acknowledgment ofsequence number M+L and window size W. The sequence number of eachmessage is the sequence number of the previous message plus its lengthin octets.    The receiver can vary the size of W without any serious adverseeffect, and can survive the receipt of duplicates or the loss of messagesdue to the retransmission and duplicate detection permitted by the scheme.    The sender is not permitted to transmit a message whose sequence numberwould exceed the sum of the last sequence number acknowledged plus thecurrent 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 canbe sent to fill the delay pipeline from source to destination Host. Ifthe IMP system were programmed with knowledge of the Host/Host protocolso that it could create a properly formatted Host/Host header for eachpacket it transmits, given the initial header of an arbitrarily longmessage, then packets could be delivered out of order to the destinationHost, so long as each correctly identified the range of sequence numberscontained in each packet. Since each octet of a message has an implicitsequence number, this would not be difficult to compute. An idea similar                               [Page 14]

RFC  635           An Assessment of ARPANET Protocols              May 1974to this is found in the Very Distant Host Reliable Transmission Package:[appendix F, 5] in the current ARPANET, except in this case, a Host mustknow about IMP packet format. It is debatable whether this would be agood idea, since changes in Host/Host protocol would require changes inIMP programming, but if it were implemented, then Hosts could sendarbitrarily long messages. The destination Host would receive a collec-tion of single packet messages which it would then sequence as if theyhad been sent that way by the source Host in the first place.    Simplex versus Full-Duplex Logical ConnectionsThe present Host/Host protocol implements simplex connections. Theusage over the last five years seems to indicate that most often, twosimplex connections are set up to act as a full duplex connection.    If Host level acknowledgments and flow control are implemented, then itis natural for them to be carried in the reverse direction of a fullduplex logical connection. Furthermore, terminal to Host connectionsare necessarily full-duplex to allow for data to move in both directions.    Finally, by embedding control in the headers of returning traffic on thefull duplex connection, the need for a separate control connection couldbe eliminated.Connection Set-up.The current Host/Host protocol uses control messages sent on aspecial control connection to establish new connections,. The procedureis called the Initial Connection Protocol or ICP [11]. The protocol issymmetric and requires that information be exchanged by both Hosts asto the names of the sockets at either end of the connection. Thisexchange precedes any flow of data. Other control messages are exchangedwhich 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 sourceand destination sockets (Walden calls them Ports) along with the text ofthe messages.    A post office analogy is useful to describe what is intended. Thesource Host writes a letter and encloses it in an envelope addressed tothe destination port with a return port address. Either the destinationport is willing to receive or it is not (e.g. it may not even be knownto the destination Host). In the former case, the letter is acknowledgedin 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 adestination Host, it will probably be necessary to include a formal con-trol exchange which indicates to the sender that a receive port is beingclosed, and the sender would be expected to acknowledge this. Similarly,the sender may end a transmission with the indication that the send portis being closed and the receiver would similarly acknowledge. SinceHosts do the sequencing, there can be no confusion as to when the closureis to take place. The rejection of an initial transmission can be madeto look like the closure of the destination port so that the number ofdistinct control messages can be kept to a minimum. This method issimilar to the one currently used in the ARPANET, but could be carriedout via control bits in the Host level messages and thus eliminate theneed for a special control connection.                               [Page 16]

RFC  635           An Assessment of ARPANET Protocols              May 1974Summary.    Arguments have been presented in this paper which show that multi-packet reassembly is not the best vehicle for achieving high throughputfrom Host to Host. The elimination of IMP reassembly as well as messagesequencing by the destination IMP can permit considerable simplificationof the IMP protocols, while simultaneously placing the. burden of buffering,duplicate detection, and sequencing of messages on the Hosts which havethe buffer space for this purpose.    Arbitrarily long messages could be sent by Hosts, at the expense ofIMP knowledge of Host protocol. Eliminating the ordering requirementat the destination IMP also eliminates serious potential lockup conditions.    Host level positive acknowledgments can eliminate the erroneous useof the RFNM for this purpose, and permit a more robust protocol whichneed not depend upon perfect performance without message loss by theIMP subnet.    Full duplex logical connections between ports in Hosts are morenatural than the simplex connections presently used, and facilitate theelimination of the special control connection required in the currentHost protocol.Unresolved Problems and Issues.    Even if a source and destination Host have adequate buffer space topermit a large number of messages (or packets, or octets) to be outstandingbetween them, the IMP subnet must have a way of combating congestionwhich may result from too rapid influx of data from a source Host, orfrom momentary congestion owing to the confluence of excessive trafficheading, in the same direction, possibly to the same destination. Alternate                               [Page 17]

RFC  635           An Assessment of ARPANET Protocols              May 1974routing strategies can help, but not completely solve the problem. Onepossibility is to insist that source Hosts monitor actual throughputachieved over the last few seconds (milliseconds?) and adjust outputrate accordingly. Destination Hosts can monitor this throughput as well,and adjust the receive buffer space it allocates to the sender to reduceunnecessary retransmissions. The IMPs can simply discard traffic whichcannot be buffered, knowing that the source will retransmit. IMPswhich discard packets to eliminate congestion could even send shortwarning messages to source or destination (or both) to stimulate adjust-ment. This is a very sticky problem and involves issues such as paymentby Hosts for retransmission. Most strategies in use today involvelimiting, a priori, the amount of data which a source Host is allowedto send (e.g., isarhythmic network proposed by Davies [13]; maximum ofn messages allowed by ARPANET IMPs). Measurement of throughputachieved by source and destination Hosts may be a good strategy in anycase since it serves as a measure of qua1ity of service provided by thepacket 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 servingprocess resides that any accumulated data should be discarded up to thepoint of the "interrupt signal." This facility permits a remote userto abort or recapture control from an uncooperative serving processwhich has stopped accepting data. The current scheme involves the useof a special interrupt signal sent on the control connection, but thereis a problem of synchronizing the interrupt request with the data in thepipeline. This signal could be carried in the control field of a Hostmessage and would participate in the sequence numbering of the data, thus                               [Page 18]

RFC  635           An Assessment of ARPANET Protocols              May 1974providing for synchronization. Since the Host operating system wouldprocess the message header before passing the data to the receiving port,the interrupt could bypass processing by the receiving process and thusprovide the desired interrupt-like effect.    There are undoubtedly many other problems and issues which couldnot be mentioned in the scope of this paper, and the author would bepleased if these and the preceding commentary will stimulate discussionand thus further the general understanding of protocol requirements fordistributed computer networks.Acknowledgments:Throughput and delay analysis: some of the basic ideas in thisanalysis are due to J. McQuillan (Bolt, Beranek, and Newman). Singlepacket re-ordering lockup: first called to the author's attention byP. Higginson (University 6f London). Host-Host Protocol Design:developed largely under the auspices of the International Network WorkingGroup (IFIP TC6.1), and the author especially acknowledges contributionsby R. Kahn, R. Metcalfe, L. Pouzin and H. Zimmerman, as well as S. Crocker,A. McKenzie, and R. Scantlebury. Numerous omissions and misstatementswere detected by R. Kahn, L. Kleinrock and H. Opderbeck.    The author is grateful for the support of the Defense AdvancedResearch Projects Agency under contract DAHC-15-73C-0435.                               [Page 19]

RFC  635           An Assessment of ARPANET Protocols              May 1974                              References1.  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 197410.  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 textB] 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 superscriptasterisks 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 ofunderscore 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 "Bsubscript digit" with "Bdigit"F] Forumla [2] page seven: I have rewritten this to eliminatehorizontal line (division symbol).G] Quarter symbol: page eight (last line) had a special symbol which Ihave replaced with "1/4"H] Marginal notes: I have preserved formulae notes from pagesix. Others have been discarded.I] Page numbers: I have left two blank lines after page header. Pagefooter is incomplete  but has the form [Page 9] or [Page 99]. RFCs in the archive havesome special character  between the footer and header (ASCII formfeed?). I was unable toenter this character.J] Reference 9: I have included page numbers since this paper is nowpublished.K] Figure 2 on page nine originally contained continuous curves inheavy pencil, redrawn in ASCII.