Movatterモバイル変換
[0]ホーム
[RFC Home] [TEXT|PDF|HTML] [Tracker] [IPR] [Info page]
UNKNOWN
Network Working Group H. OpderbeckRequest for Comments: #632 UCLA-NMCNIC # 30239 20 May 1974Throughput Degradations for Single Packet MessagesThe transmission of digitized speech over the ARPANET represents a newdimension in the use of packet switching systems. The throughput anddelay requirements for this newly emerging application area are quitedifferent from the throughput and delay requirements for interactive useor file transfers. In particular, we need to achieve a high throughputfor small messages since long messages result in long source delays tofill the large buffers. Therefore we are currently studying thethroughput limits for single-packet messages. We realize that up to nowlittle attempt was made to optimize throughput for low delay traffic.It was nevertheless surprising for us to find out that the observedthroughput for single-packet messages is in many cases only about onefourth of what one would expect. In what follows we are going toexplain why this happens and what could be done to correct thissituation.On April 1, 1974, we sent, using the IMP message generator, single-packet messages at the highest possible rate ("RFNM-driven") from theMOFFET-IMP to the SRI-IMP. There are two three-hop paths from MOFFET toSRI, one of them involving two 230.4 kbs circuits. Since there washardly any interfering traffic we expected an average round-trip delayof not more than 100 msec. Assuming that there are, on an average, 3messages in transmission between MOFFET and SRI and assuming a messagelength of about 1000 bits this should result in a throughout of morethan 30 kbs. The observed through was, however, less than 8 kbs. Arepetition of the experiment showed the same result. A more detailedanalysis of the collected data revealed that an average number of 3.5messages were simultaneously in transmission between MOFFET and SRI.The throughput degradation could therefore not have been due tointerfering traffic between these two sites. Also the channelutilization for all channels that were involved in the transmission wasless than 40 percent. The observed mean round-trip times between MOFFETand SRI, however, were about 500 msec. Since these large round-triptimes were obviously not due to physical limitations, we studied theflow control mechanism for single-packet messages and were able to comeup with an explanation for this undesirable behavior.When a single-packet message arrives at the destination IMP out of order(i.e., the logically preceding message has not yet arrived there) it isnot accepted by the destination IMP. It is rather treated as a requestfor the allocation of one reassembly buffer. The corresponding ALLOCATEOpderbeck [Page 1]
RFC 632 Throughput Degradations for Single Packet Messages May 1974is then sent back to the source IMP only after the RFNM for the previousmessage has been processed. We therefore may have the followingsequence of events: 1 MSG(i) sent from SOURCE-IMP (message i is sent from the source IMP to the destination IMP). 2 MSG(i+1) sent from SOURCE-IMP. 3 MSG(i+1) arrives at DEST-IMP (due to an alternate path or a line error, message (i+1) arrives at the destination IMP out of order; it is treated as a request for one reassembly buffer allocation and then discarded). 4 MSG(i) arrives at DEST-IMP (message i arrives at the destination IMP; it is put on the proper HOST output queue). 5 RFNM(i) sent from DEST-IMP (after message i has been accepted by the destination HOST the RFNM is sent to the source IMP). 6 ALL(i+1) sent from DEST-IMP (only after the RFNM for message i has been processed can the ALLOCATE for message i + 1 be sent). 7 RFNM(i) arrives at SOURCE-IMP. 8 ALL(i+1) arrives at SOURCE-IMP. 9 MSG(i+1) arrives at DEST-IMP (now message i+1 is put on the proper HOST output queue.) 10 RFNM(i+1) sent form DEST-IMP. 11 RFNM(i+1) arrives at SOURCE-IMP.Note that the round-trip time for message i+1 is the time intervalbetween event 2 and event 11. Therefore the round-trip time for messagei+1 is more than twice as large as it would have been if it had arrivedin order, other conditions being unchanged. Therefore a line error willin many cases not only delay the message in error but also the nextsingle-packet message if this message follows the preceding messagewithin 125 msec, the error retransmission timeout interval. Also, afaster, alternate path to the destination IMP can actually slow down thetransmission since it causes messages to arrive there out of order.Opderbeck [Page 2]
RFC 632 Throughput Degradations for Single Packet Messages May 1974This situation becomes even worse when we consider RFNM-driven single-packet message traffic. Table 1 shows a possible sequence of events.We again assume that message i+1 reaches the destination IMP beforemessage i. SOURCE IMP DESTINATION IMP MSG(i) sent MSG(i+1) sent MSG(i+2) sent MSG(i+1) arr MSG(i+3) sent MSG(i) arr RFNM(i) sent ALL(i+1) sent MSG(i+2) arr MSG(i+3) arr RFNM(i) arr MSG(i+4) sent ALL(i+1) arr MSG(i+4) arr MSG(i+1) sent MSG(i+1) arr RFNM(i+1) sent RFNM(i+1) arr ALL(i+2) sent MSG(i+5) sent ALL(i+2) arr MSG(i+5) arr MSG(i+2) sent MSG(i+2) arr RFNM(i+2) sent RFNM(i+2) arr ALL(i+3) sent MSG(i+6) sent ALL(i+3) arr MSG(i+6) arr MSG(i+3) sent MSG(i+3) arr RFNM(i+3) sent RFNM(i+3) arr ALL(i+4) ent MSG(i+7) sent ALL(i+4) arr MSG(i+7) arr MSG(i+4) sent MSG(i+4) arr RFNM(i+4) sent RFNM(i+4) arr ALL(i+5) MSG(i+8) sent ALL(i+5) arr MSG(i+5) sent Table 1. Retransmission Pattern for the Current Flow Control Scheme(Since the traffic is RFNM-driven, the arrival of RFNM i, i+1, ... isfollowed by the sending of message i+4, i+5, ...)Opderbeck [Page 3]
RFC 632 Throughput Degradations for Single Packet Messages May 1974The most interesting fact about this sequence of events is that thearrival of message i+1 before message i at the destination IMP causesnot only messages i+1 but all future messages to be retransmitted--though we do not assume that any of the future messages arrive out oforder. The table also shows that the round-trip times for message i+4and all future messages is more than four times as large as it would bewithout these undesirable retransmissions. It is also noteworthy that,once this retransmission pattern has established itself, there is almostno way the system can recover from this condition other thaninterrupting the input stream at the source IMP. A single arrival outof order of any of the later user or control messages, for instance,will not change this retransmission pattern. The normal flow ofsingle-packet messages will only reestablish itself if, for example,message i+4, i+5, and i+6 are simultaneously delayed for several hundredmilliseconds such that messages i+1, i+2, and i+3 can be retransmittedin the meantime. The probability of occurrence of such an event is,however, extremely small. Therefore one can consider the system asbeing trapped in this undesirable retransmission condition. The"normal" flow of messages, on the other hand, represents only thetransient behavior of the system since there is always a finiteprobability that two message arrive out of order due to transmissionerrors.As mentioned before, the system can only recover from this throughput(and delay) degradation if the input stream of single-packet messages isinterrupted. In case of speech transmission, however, this might notoccur for a long time. Therefore speech transmission systems would inmany cases have to work with only one fourth of the expected single-packet bandwidth. Since this is clearly an unacceptable condition welooked for a modification of the current flow control scheme whichcorrects this situation. In what follows we describe two methods thatcould be used to avoid the undesirable retransmission of messages.Recall that a single-packet message is rejected at destination IMP andlater retransmitted if the RFNM for the preceding message has not yetbeen sent to the source IMP. This is mainly done to prevent theoccurrence of reassembly lockup conditions [1]. Therefore the problemcannot be solved by simply accepting all single-packet messages withoutadditional measures to prevent deadlocks. This could lead to areassembly lockup if a large number of single-packet messages fromseveral source IMPs arrives at their common destination IMP out oforder. In this case the destination IMP might not be able to acceptthose messages that are in order because of the lack of reassemblybuffers. As a result the system is deadlocked. Any solution of thethroughput degradation problem must guarantee that all messages thatarrive in order can be accepted by the destination IMP.Opderbeck [Page 4]
RFC 632 Throughput Degradations for Single Packet Messages May 1974One way to achieve this goal is to reject single-packet messages thatarrive out of order only if the buffer requirement(s) of the precedingmessages(s) is not known. In the previous examples we have seen thatthe destination IMP continuously rejected messages although it knew thebuffer requirements for the messages that had to be delivered first. Asthe buffer requirements become known, the necessary number of bufferscan be set aside and future single-packet messages can be acceptedwithout the danger of deadlock. Therefore the undesirable retransmissionpattern cannot establish itself. Table 2 shows the sequence of eventsfor this policy if message i+1 arrives before message i at thedestination IMP. SOURCE IMP DESTINATION IMP MSG (i) sent MSG(i+1) sent MSG(i+2) sent MSG(i+1) arr. (rejected) MSG(i+3) sent MSG(i) arr. (HOST output) RFNM(i) sent ALL (i+1) sent MSG(i+2) arr (stored) MSG(i+3) arr (stored) RFNM(i) arr MSG(i+4) sent ALL(i+1) arr MSG(i+4) arr (stored) MSG(i+1) sent MSG(i+1) arr (HOST output) RFNM(i+1) sent RFNM(i+1) arr RFNM(i+2) sent MSG(i+5) sent RFNM(i+3) sent RFNM(i+4) sent Table 2. Sequence of Events for Modified Flow Control SchemeNote that in this modified scheme only one message, message i+1, isretransmitted. In view of the fact that the IMPs have plenty ofreassembly buffer space it is, however, desirable to avoid this oneretransmission, too. This is particularly important for thetransmission of speech which depends on a steady flow of data and willbe disrupted by a sudden large delay. Therefore we suggest a secondmethod to solve the throughput degradation problem which, in most cases,will not require any retransmissions.Opderbeck [Page 5]
RFC 632 Throughput Degradations for Single Packet Messages May 1974Suppose all single-packet messages are initially accepted (or stored).Currently single-packet messages that arrive out of order are rejectedbecause of the possibility of a deadlock. But let us take a closer lookat the situation where all single-packet messages are accepted (orstored) such that there is no reassembly buffer available for messagesthat have to be delivered to their HOST(s) next. This is not really alockup condition because the source IMPs keep a copy of all single-packet messages for which a RFNM has not yet been received. Thereforeany single-packet message, which arrived out of order but was acceptedby the destination IMP nevertheless, can be deleted later without themessage being lost. The destination IMP only has to send an ALLOCATEfor each deleted single-packet message to the corresponding source IMPwhen reassembly buffer space is available. This can also be consideredas deferred rejection. But now a retransmission is only necessary ifthe destination IMP is really running out of reassembly buffers. Inthis case, the physical limitations of the system are reached and wecannot hope to gain large throughput increases by means of protocolchanges.It is our intention to pursue this issue with the IMP development groupat BBN in the future. They agree that the two solutions we suggestwould improve the situation. However, they can think of alternativesolutions.I acknowledge the help of Bill Naylor and Joe Katz in performing theexperiments which led to the discovery of the throughput degradation.References: [1] Kleinrock, L. and H. Opderbeck. "On a Possible Lockup condition in the IMP Subnet Due to Message Sequencing", RFC #626. [ This RFC was put into machine readable form for entry ] [ into the online RFC archives by Alex McKenzie with ] [ support from GTE, formerly BBN Corp. 11/99 ]Opderbeck [Page 6]
[8]ページ先頭