rfc891.txt

RFC 相关的技术文档

         --- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fixed        |           Checksum            |
Area         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |             Date              |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |                               |
             +              Time             +
             |                               |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |           Timestamp           |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |     Offset    |   Hosts (n)   |
         --- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Host         |          Delay Host 0         |
Area         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |         Offset Host 0         |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            ...                             ...
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |         Delay Host n-1        |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |         Offset Host n-1       |
         --- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

               Figure 3. HELLO Message Format

     There are two HELLO message formats, depending on the length of
the message.  One format, sent by a DCN host to another host on the
same local net, includes both the fixed and host areas shown above.
The second format, sent in all other cases, includes only the fixed
area.

     Note that all word fields shown are byte-swapped with respect to
the ordinary PDP11 representation.  The "Checksum" field contains a
checksum covering the fields indicated.  The "Date" and "Time" fields
are filled in with the local date and time of origination.  The
"Timestamp" field is used in the computation of the roundtrip delay
(see below).  The "Offset" field contains the offset of the block af
Internet addresses used by the local net.  The "Delay Host n" and
"Offset Host n" fields represent a copy of the corresponding entries
of the Host Table as they exist at the time of origination.  The
"Hosts (n)" field contains the number of entries in this table.

2.2.  Roundtrip Delay Calculations

     Periodically, each DCN physical host sends a HELLO message to its
neighbor on each of the communication links common to both of them.
For each of these links the sender keeps a set of state variables,
including a copy of the source-address field of the last HELLO message
received.  

DCN Local-Network Protocols                                         Page 7
D.L. Mills


When constructing a HELLO message the sender sets the
destination-address field to this state variable and the
source-address field to its own address.  It then fills in the "Date"
and "Time" fields from its logical clock and the "Timestamp" field
from another state variable.  It finally copies the "Delay" and
"Offset" values from its Host Table into the message.

     A host receiving a HELLO message discards it if the format is bad
or the checksum fails.  If valid, it initializes a link state variable
to show that the link is up.  Each time a HELLO message is transmitted
this state variable is decremented.  If it decrements to zero the link
is declared down.

     The host then checks if the source-address field matches the
state variable containing the last address stored.  If not, the link
has been switched to a new host, so the state variables are flushed
and the link forced into a recovery state.  The host then checks if
the destination-address field matches its own address.  If so, the
message has been looped (legal only in the case of a broadcast net)
and the roundtrip delay information is corrected.  The host and net
areas are ignored in this case.  If not, the host and net areas of the
message are processed to update the Host and Net Tables.

     Roundtrip delay calculations are performed in the following way.
The link input/output processes assigned each link maintain an
internal state variable which is updated as each HELLO message is
received and transmitted.  When a HELLO message is received this
variable takes the value of the "Time" field minus the current
time-of-day.  When the next HELLO message is transmitted, the value
assigned the "Timestamp" field is computed as the low-order 16-bits of
this variable plus the current time-of-day.  The value of this
variable is forced to zero if either the link is down of the system
logical clock has been reset since the last HELLO message was
received.

     If a HELLO message is received with zero "Timestamp" field, no
processing other than filling in the internal state variable.
Otherwise, the roundtrip delay is computed as the low-order 16-bits of
the current time-of-day minus the value of this field.  In order to
assure the highest accuracy, the calculation is performed only if the
length of the last transmitted HELLO message (in octets) matches the
length of the received HELLO message.

     The above technique renders the calculation independent of the
clock offsets and intervals between HELLO messages at either host,
protects against errors that might occur due to lost HELLO messages
and works even when a neighbor host simply forwards the HELLO message
back to the originator without modifying it.  The latter behavior,
typical of ARPANET IMPs and gateways, as well as broadcast nets, relies
on the loop-detection mechanism so that correct calculations can be
made and, furthermore, that spurious host updates can be avoided.


DCN Local-Network Protocols                                         Page 8
D.L. Mills


2.3.  Host Updates

     When a HELLO message arrives which results in a valid roundtrip
delay calculation, a host update process is performed.  This consists
of adding the roundtrip delay to each of the "Delay Host n" entries in
the HELLO message in turn and comparing each of these calculated
delays to the "Host Delay" field of the corresponding Host Table
entry.  Each entry is then updated according to the following rules:

1.  If the link connects to another DCN host on the same net and the
    port ID (PID) of the link output process matches the "Port ID"
    field of the entry, then update the entry.

2.  If the link connects to another DCN host on the same net, the PID
    of the link output process does not match the "Port ID" field and the
    calculated delay is less than the "Host Delay" field by at least a
    specified switching threshold (currently 100 milliseconds), then
    update the entry. 

3.  If the link connects to a foreign net and is assigned a host ID
    corresponding to the entry, then update the entry.  In this case
    only, use as the calculated delay the roundtrip delay.
    
4.  If none of the above conditions are met, or if the virtual host
    has been declared down and the "TTL" field contains a nonzero
    value, then no update is performed.

     The update process consists of replacing the "Delay" field with
the calculated delay, the "Port ID" field with the PID of the link
output process, the "Update Timestamp" field with the current time of
day and the "TTL" field by a specified value (currently 120) in
seconds.  If the calculated delay exceeds a specified maximum interval
(currently 30 seconds), the virtual host is declared down by setting
the corresponding "Delay" field to the maximum and the remaining
fields as before.  For the purposes of delay calculations values less
than a specified minimum (currently 100 milliseconds) are rounded up
to that minimum.

     The "Offset" field is also replaced during the update process.
When the HELLO message arrives, The value of the current logical clock
is subtracted from the "Time" field and the difference added to
one-half the roundtrip delay.  The resulting sum, which represents the
offset of the local clock to the clock of the sender, is added to the
corresponding "Offset" field of the HELLO message and the sum replaces
the "Offset" field of the Host Table.  Thus, the "Offset" field in the
Host Table for a particular virtual host is replaced only if that host
is up and on the minimum-delay path to the DCN host.

     The purpose of the switching threshold in (2) above and the
minimum delay specification in the update process is to avoid
unnecessary switching between links and transient loops which can
occur due to normal variations in propagation delays.  The purpose of
the "TTL" field test in (4) above is to ensure consistency by purging
all paths to a virtual host when that virtual host goes down.

DCN Local-Network Protocols                                         Page 9
D.L. Mills


     In addition to the updates performed as HELLO messages arrive, each
virtual host in a DCN host also performs a periodic update of its own
Host Table entry.  The update procedure is identical to the above,
except that the calculated delay and offset are taken as zero.  At
least one of the virtual hosts in a DCN host must have the same host
ID as the host number assigned the DCN host itself and all must be
assigned the same net number.  Other than these, there are no
restrictions on the number or addresses of internet processes resident
in a single DCN host.

     It should be appreciated that virtual hosts are truly portable
and can migrate about the net, should such a requirement arise.  The
host update protocols described here insure that the routing
procedures always converge to the minimum-delay paths via operational
links and DCN hosts.  In the case of broadcast nets such as Ethernets,
the procedures are modified slightly as described below.  In this case
the HELLO messages are used to determine routing from the various
Ethernet hosts to destinations off the cable, as well as to provide
time synchronization.

2.4.  Timeouts

     The "TTL" field in every Host Table entry is decremented once a
second in normal operation.  Thus, if following a host update another
update is not received within an interval corresponding to the value
initialized in that field, it decrements to zero, at which point the
virtual host is declared down and the Host Table entry set as
described above.  The 120-second interval used currently provides for
at least four HELLO messages to be generated by every neighbor on
every link during that interval, since the maximum delay between HELLO
messages is 30 seconds on the lowest-speed link (1200 bps).  Thus, if
no HELLO messages are lost, the maximum number of links between any
virtual host and any other is four.

     The "TTL" field is initialized at 120 seconds when an update
occurs and when the virtual host is declared down.  During the
interval this field decrements to zero immediately after being
declared down, updates are ignored.  This provides a decent interval
for the bad news to propagate throughout the net and for the Host
Tables in all DCN hosts to reflect the fact.  Thus, the formation of
routing loops is prevented.

     The IP datagram forwarding procedures call for decrementing the
"time-to-live" field in the IP header once per second or at each point
where it is forwarded, whichever comes first.  The value used
currently for this purpose is 30, so that an IP datagram can live in
the net no longer than that number of seconds.  This is thus the
maximum delay allowed on any path between two virtual hosts.  If this
maximum delay is exceeded in calculating the roundtrip delay for a
Host Table entry, the corresponding virtual host will be declared
down.


DCN Local-Network Protocols                                        Page 10
D.L. Mills

     The interval between HELLO messages on any link depends on the
data rate supported by the link.  As a general rule, this interval is
set at 16 times the expected roundtrip time for the longest packet to
be sent on that link.  For 1200-bps asynchronous transmission and
packet lengths to 256 octets, this corresponds to a maximum HELLO
message interval of about 30 seconds. 

     Although the roundtrip delay calculation, upon which the routing
process depends, is relatively insensitive to net traffic and
congestion, stochastic variations in the calculated values ordinarily
occur due to coding (bit or character stuffing) and medium
perturbations.  In order to suppress loops and needless path changes a
minimum switching threshold is incorporated into the routing mechanism
(see above).  The interval used for this threshold, as well as for the
minimum delay on any path, is 100 milliseconds.

3.  Formal Specification

     The following sections provide a formal framework which describe
the DCN HELLO protocol.  This protocol is run between neighboring DCN
hosts that share a common point-to-point link and provides automatic
connectivity determination, routing and timekeeping functions.

     The descriptions to follow are organized as follows: First a
summary of data structures describes the global variables and packet
formats.  Then three processes which implement the protocol are
described: the CLOCK, HELLO and HOST processes.  The description of
these processes is organized into sections that describe (1) the local
variables used by that process, (2) the parameters and constants and
(3) the events that initiate processing together with the procedures
they evoke.  In the case of variables a distinction is made between
state variables, which retain their contents between procedure calls,
and temporaries, which have a lifetime extending only while the
process is running.  Except as noted below, the initial contents of
state variables are unimportant.

3.1.  Data Structures

3.1.1.  Global Variables

ADDRESS
    This is a 32-bit bit-string temporary variable used to contain an
    Internet address.
    

CLOCK-HID
    This is an eight-bit integer state variable used to contain the
    host ID of the local-net host to be used as the master clock.  It
    is initialized to the appropriate value depending upon the net
    configuration. 
    
DATE
    This is a 16-bit bit-string state variable used to contain the
    date in RT-11 format.  Bits 0-4 contain the year, with zero