rfc619.txt

RFC 相关的技术文档

Network Working Group                                          W. Naylor
Request for Comment: 619                                    H. Opderbeck
NIC 21990                                                       UCLA-NMC
                                                           March 7, 1974


                  Mean Round-Trip Times in the ARPANET


In one of our current measurement projects we are interested in the
average values of important network parameters.  For this purpose we
collect data on the network activity over seven consecutive days.  This
data collection is only interrupted by down-time or maintenance of
either the net or our collecting facility (the "late" Sigma-7 or, in
future, the 360/91 at CCN).

The insight gained from the analysis of this data has been reported in
Network Measurement Group Note 18 (NIC 20793):

    L.  Kleinrock and W. Naylor
    "On Measured Behavior of the ARPA Network"

This paper will be presented at the NCC '74 in Chicago.

In this RFC we want to report the mean round-trip times (or delays) that
were observed during these week-long measurements since we think these
figures are of general interest to the ARPA community.  Let us first
define the term "round trip time" as it is used by the statistics
gathering program in the IMPs.  When a message is sent from a source
HOST to a destination HOST, the following events, among others, can be
distinguished (T(i) is the time of event i):

  T(1): The message is passed from the user program to the NCP in the
        source HOST

  T(2): The proper entry is made in the pending packet table (PPT) for
        single packet messages or the pending leader table (PLT) for
        multiple packet messages after the first packet is received by
        the source IMP

  T(3): The first packet of the message is put on the proper output
        queue in the source IMP (at this time the input of the second
        packet is initiated)

  T(4): The message is put on the HOST-output queue in the destination
        IMP (at this time the reassembly of the message is complete)

  T(5): The RFNM is sent from the destination IMP to the source IMP



Naylor & Opderbeck                                              [Page 1]

RFC 619           Mean Round-Trip Times in the ARPANET        March 1974


  T(6): The RFNM arrives at the source IMP

  T(7): The RFNM is accepted by the source HOST

The time intervals T(i)-T(i-1) are mainly due to the following delays
and waiting times:

  T(2)-T(1): -HOST processing delay
             -HOST-IMP transmission delay for the 32-bit leader
             -Waiting time for a message number to become free (only
              four messages can simultaneously be transmitted between
              any pair of source IMP - destination IMP)
             -Waiting time for a buffer to become free (there must be
              more than three buffers on the "free buffer list")
             -HOST-IMP transmission delay for the first packet
             -Waiting time for an entry in the PPT or PLT to become
              available (there are eight entries in the PPT and twelve
              in the PLT table)

  T(3)-T(2): -Waiting time for a store-and-forward (S/F) buffer to
              become free (the maximum number of S/F-buffers is 20).
             -Waiting time for a logical ACK-channel to become free
              (there are 8 logical ACK-channels for each physical
              channel).
             -For multiple packet messages, waiting time until the
              ALLOCATE is received (unless an allocation from a previous
              multiple-packet message still exists; such an allocation
              is returned in the RFNM and expires after 125 msec)

  T(4)-T(3): -Queuing delay, transmission delay, and propagation delay
              in all the IMPs and lines in the path from source IMP to
              destination IMP
             -Possibly retransmission delay due to transmission errors
              or lack of buffer space (for multiple packet messages the
              delays for the individual packets overlap)

  T(5)-T(4): -Queuing delay in the destination IMP
             -IMP-HOST transmission delay for the first packet
             -For multiple-packet messages, waiting time for reassembly
              buffers to become free to piggy-back an ALLOCATE on the
              RFNM (if this waiting time exceeds one second then the
              RFNM is sent without the ALLOCATE)

  T(6)-T(5): -Queuing delay, transmission delay, and propagation delay
              for the RFNM in all the IMPs and lines in the path from
              destination IMP to source IMP





Naylor & Opderbeck                                              [Page 2]

RFC 619           Mean Round-Trip Times in the ARPANET        March 1974


  T(7)-T(6): -Queuing delay for the RFNM in the source IMP
             -IMP-HOST transmission delay for the RFNM

IMP processing delays are not included in this table since they are
usually very small.  Also, some of the abovementioned waiting times
reduce to zero in many cases, e.g. the waiting time for a message number
to become available and the waiting time for a buffer to become free.

If the source and destination HOSTs are attached to the same IMP, this
table can be simplified as follows:

  T(2)-T(1):  as before
  T(3)-T(2):  for multiple packet messages: waiting time until
              reassembly space becomes available (there are up to 66
              reassembly buffers)
  T(4)-T(3):  for multiple packet messages: HOST-IMP transmission delay
              for packets 2,3,...
  T(5)-T(4):  as before
  T(6)-T(5):  0
  T(7)-T(6):  as before

Up to now we have neglected the possibility that a single packet message
is rejected at the destination IMP because of lack of reassembly space.
If this occurs, the single packet message is treated as a request for
buffer space allocation and the time interval T(3)-T(2) increased by the
waiting time until the corresponding "ALLOCATE" is received.

The round trip time (RTT) is now defined as the time interval T(6)-T(2).
Note that the RTT for multiple packet messages does include the waiting
time until the ALLOCATE is received.  It does, however, not include the
source HOST processing delay (i.e. delays in the NCP), the HOST-IMP
transmission delay, and the waiting time until a message number becomes
available.  Note also, that the RFNM is sent after the first packet of a
multiple packet message has been received by the destination HOST.

Let us now turn to the presentation of the average round trip times as
they were measured during continuous seven-day periods in August and
December '73.  In August, an average number of 2935 messages/minute were
entering the ARPANET.  The overall mean round trip delay for all these
messages was 93 milliseconds (msec).  The corresponding numbers for
December were 2226 messages/minute and 200 msec.  An obvious question
that immediately arises is: why did the average round trip delay more
than double while the rate of incoming messages decreased?  The answer
to this question can be found in the large round trip delays for the
status reports that are sent from each IMP to the NCC.  Each IMP sends,
on the average, 2.29 status reports per minute to the NCC.  Since there





Naylor & Opderbeck                                              [Page 3]

RFC 619           Mean Round-Trip Times in the ARPANET        March 1974


were 45 sites connected to the net in December, a total of 103.05 status
reports per minute were sent to the NCC.  Thus 4.63 percent of all
messages that entered the net were status reports.

The average round trip delay for all these status reports in December
was 1.66 sec.  This number is five to ten times larger than the average
round-trip delay for status reports we observed in August.  It is not
yet clear what change in the collection of status reports caused this
increase.  One reason appears to be that the number of these reports was
doubled between August and December.  Since the large round-trip delays
of these status reports distort the overall picture somewhat, we are
going to present the December data - wherever appropriate - with and
without the effect of these delays.  (We should point out here that the
traffic/delay picture is distorted by the accumulated statistics
messages which were collected to produce this data.  We have, however,
ignored this effect since these measurement messages represent less than
0.3% of the total traffic.)  The overall mean round trip delay without
the status reports in December is 132 msec.  This value is still more
than 35 msec larger than the corresponding value for August.  However,
before we shall attempt to explain this difference we will first present
the measured data.

Table 1 shows the mean round trip delay as a function of the number of
hops over the minimum-hop path.  This minimum number of hops was
calculated from the (static) topology of the net as it existed in August
and December of last year.  The actual number of hops over which any
given message travels may, of course, be larger due to network
congestion, line failures or IMP failures.  In fact, for August we
observed a minimum mean path length of 3.24 while the actual measured
mean path length was 3.30; in December we observed 4.02 and 4.40,
respectively.  (See Network Measurement Group Note #18 for an
explanation of the computation of actual mean path length.)  As expected
we observe a sharp increase of the mean round trip delay as the minimum
number of hops is increased.  Note, however, that the mean round trip
delay is not a strictly increasing function of the minimum number of
hops.

Table 2 gives the mean round trip delay for messages from a given site.
The December data is presented with and without the large delays
incurred by the sending of status reports to the NCC.  Table 3 shows the
mean round trip delay for messages to a given site.  The largest round
trip delays, in December, were incurred by messages sent to the NCC-TIP
since these messages include all the status reports.

Table 4, finally, gives for each site the mean round trip delays to
those three destination IMP/TIP's to which the most messages were sent
during the seven-day measurement period in December.  Let us first say
few words about the traffic distribution which is dealt with in more



Naylor & Opderbeck                                              [Page 4]

RFC 619           Mean Round-Trip Times in the ARPANET        March 1974


detail in Network Measurement Group Note #18.  There are several sites
which like to use their IMP as a kind of local multiplexer (UTAH, MIT,
HARV, CMU, USCT, CCAT, XROX, HAWT, MIT2).  For these sites the most
favorite destination site is the source IMP itself.  For several other
sites the most favorite destination site is just one hop away (BBN,
AMES, AMST, NCCT,  RUTT).  Nobody will be surprised that for many sites
ISI (ILL, MTRT, ETAT, SDAT, ARPT, RMLT, LONT) or SRI (UCSB, RADT, NBST)
is the most favorite site.  There are several other sites (SDC, LL,
CASE, DOCT, BELV, ABRD, FNWT, LBL, NSAT, TYMT, MOFF, WPAT) which were
rather inactive in terms of generating traffic during the seven-day
measurement period in December.  Most of their messages were status
reports sent to the NCC.  (Those IMPs, for which the frequency of
messages to the NCC-TIP is less than 2.2 messages per minute, were down
for some time during the measurement period).

Let us now attempt to give a few explanations for the overall increase
in the mean round trip delay between August and December.  These
explanations may also help to understand the differences in the mean
round trip delays for any given source IMP-destination IMP pair as
observed in Table 4.

1.  Frequency of routing messages.  Routing messages are the major
    source of queuing delay in a very lightly loaded net.  In August, a
    routing message was sent every 640 msec.  Since a routing message is
    1160 bits long, 3.625 percent of the bandwidth of a 50 kbs circuit
    was used for the sending of routing messages.  For randomly arriving
    packets this corresponds to a mean queuing delay of 0.42 msec per
    hop.  Between August and December the frequency of sending routing
    messages was made dependent on line speed and line utilization.  As
    a result, routing messages are now sent on a 50 kbs circuit with
    zero load every 128 msec.  This corresponds to a line utilization of
    18.125 percent and a mean queuing delay of 2.10 msec.  The queuing
    delay due to routing messages in a very lightly loaded net in