rfc891.txt

RFC 相关的技术文档

Network Working Group                                   D.L.  Mills
Request for Comments:  891                              December 1983


                         DCN Local-Network Protocols

This RFC is a description of the protocol used in the DCN local
networks to maintain connectivity, routing, and timekeeping
information.  These procedures may be of interest to designers and
implementers of other networks.

1.  Introduction

     This document describes the local-net architecture and protocols
of the Distributed Computer Network (DCN), a family of local nets
based on Internet technology and an implementation of PDP11-based
software called the Fuzzball.  DCN local nets have been in operation
for about three years and now include clones in the USA, UK, Norway
and West Germany.  They typically include a number of PDP11 or LSI-11
Fuzzballs, one of which is elected a gateway, and often include other
Internet-compatible hosts as well.

     The DCN local-net protocols are intended to provide connectivity,
routing and timekeeping functions for a set of randomly connected
personal computers and service hosts.  The design philosophy guiding
the Fuzzball implementation is to incorporate complete functionality
in every host, which can serve as a packet switch, gateway and service
host all at the same time.  When a set of Fuzzballs are connected
together using a haphazard collection of serial, parallel and
contention-bus interfaces, they organize themselves into a network
with routing based on minimum delay.

     The purpose of this document is to describe the local-net
protocols used by the DCN to maintain connectivity, routing and
timekeeping functions.  The document is an extensive revision and
expansion of Section 4.2 of [1] and is divided into two parts, the
first of which is an informal description of the architecture,
together with explanatory remarks.  The second part consists of a
semi-formal specification of the entities and protocols used to
determine connectivity, establish routing and maintain clock
synchronization and is designed to aid in the implementation of cohort
systems.  The link-level coding is described in the appendix.

2.  Narrative Description

     The DCN architecture is designed for local nets of up to 256
hosts and gateways using the Internet Protocol (IP) and client
protocols.  It provides adaptive routing and clock synchronization
functions in an arbitrary topology including point-to-point links and
multipoint bus systems.  It is intended for use in connecting personal
computers to each other and to service machines, gateways and other
hosts of the Internet community.  However, it is not intended for use
in large, complex networks and does not support the sophisticated
routing and control algorithms of, for example, the ARPANET.

     A brief description of the process and addressing structure used
in the DCN may be useful in the following.  A DCN physical host is a
PDP11-compatible processor which supports a number of cooperating
sequential processes, each of

DCN Local-Network Protocols                                         Page 2
D.L. Mills

which is given a unique 8-bit identifier called its port ID.  Every
DCN physical host contains one or more internet processes, each of
which supports a virtual host given a unique 8-bit identifier called
its host ID.

     Each virtual host can support multiple internet protocols,
connections and, in addition, a virtual clock.  Each physical host
contains a physical clock which can operate at an arbitrary rate and,
in addition, a 32-bit logical clock which operates at 1000 Hz and is
assumed to be reset each day at 0000 hours UT.  Not all physical hosts
implement the full 32-bit precision; however, in such cases the
resolution of the logical clock may be somewhat less.

     There is a one-to-one correspondence between Internet addresses
and host IDs.  The host ID is formed from a specified octet of the
Internet address to which is added a specified offset.  The octet
number and offset are selected at configuration time and must be the
same for all DCN hosts sharing the local net.  For class-B and class-C
nets normally the fourth octet is used in this way for routing within
the local net.  In the case of class-B nets, the third octet is
considered part of the net number by DCN hosts; therefore, this octet
can be used for routing between DCN local nets.  For class-A nets
normally the third octet (ARPANET logical-host field) is used for
routing where necessary.

     Each DCN physical host is identified by a host ID for the purpose
of detecting loops in routing updates, which establish the
minimum-delay paths between the virtual hosts.  By convention, the
physical host ID is assigned as the host ID of one of its virtual
hosts.  A link to a neighbor net is associated with a special virtual
host, called a gateway, which is assigned a unique host ID.

     The links connecting the various physical hosts together and to
foreign nets can be distributed in arbitrary ways, so long as the net
remains fully connected.  If full connectivity is lost, due to a link
or host fault, the virtual hosts in each of the surviving segments can
continue to operate with each other and, once connectivity is
restored, with all of them.

     Datagram routing is determined entirely by internet address -
there is no local leader as in the ARPANET.  Each physical host
contains two tables, the Host Table, which is used to determine the
outgoing link to each other local-net host, and the Net Table, which
is used to determine the outgoing host (gateway) to each other net.
The Host Table contains estimates of roundtrip delay and logical-clock
offset for all virtual hosts in the net and is indexed by host ID.
For the purpose of computing these estimates the delay and offset of
each virtual host relative to the physical host in which it resides is
assumed zero.  The single exception to this is a special virtual host
associated with an NBS radio time-code receiver, where the offset is
computed relative to the broadcast time.

     The Net Table contains an entry for every neighbor net that may
be connected to the local net and, in addition, certain other nets
that are not

DCN Local-Network Protocols                                         Page 3
D.L. Mills

neighbors.  Each entry contains the net number, as well as the host ID
of the local-net gateway to that net.  The routing function simply
looks up the net number in the Net Table, finds the host ID of the
gateway and retrieves the port ID of the net-output process from the
Host Table.  Other information is included in the Host Table and Net
Table as described below.

     The delay and offset estimates are updated by HELLO messages
exchanged on the links connecting physical-host neighbors.  The HELLO
messages are exchanged frequently, but not so as to materially degrade
the throughput of the link for ordinary data messages.  A HELLO
message contains a copy of the delay and offset information from the
Host Table of the sender, as well as information to compute the
roundtrip delay and logical-clock offset of the receiver relative to
the sender.

     The routing algorithm is similar to that (formerly) used in the
ARPANET and other places in that the roundtrip (biased) delay estimate
calculated to a neighbor is added to each of the delay estimates given
in its HELLO message and compared with the corresponding delay
estimates in the Host Table.  If a delay computed in this way is less
than the delay already in the Host Table, the routing to the
corresponding virtual host is changed accordingly.  The detailed
operation of this algorithm, which includes provisions for host
up-down logic and loop suppression, is summarized in a later section.

     DCN local nets are self-configuring for all hosts and neighbor
nets; that is, the routing algorithms will find minimum-delay paths
between all hosts and gateways to neighbor nets.  In addition,
timekeeping information can be exchanged using special HELLO messages
between neighboring DCN local nets.  For routing beyond neighbor nets
additional entries can be configured in the Net Tables as required.
In addition, a special entry can be configured in the Net Tables which
specifies the host ID of the gateway to all nets not explicitly
included in the table.

     For routing via the ARPANET and its reachable nets a selected
local-net host is equipped with an IMP interface and configured with a
GGP/EGP Gateway process.  This process maintains the Net Table of the
local host, including ARPANET leaders, dynamically as part of the
GGP/EGP protocol interactions with other ARPANET gateways.  GGP/EGP
protocol interactions are possibly with non-ARPANET gateways as well.

     The portable virtual-host structure used in the DCN encourages a
rather loose interpretation of addressing.  In order to minimize
confusion in the following, the term "host ID" will be applied only to
virtual hosts, while "host number" will be applied to the physical
host, called generically the DCN host.

2.1.  Net and Host Tables

     There are two tables in every DCN host which control routing of
Internet Protocol (IP) datagrams: the Net Table and the Host Table.
The Net Table is used to determine the host ID of the gateway on the
route to a foreign net,

DCN Local-Network Protocols                                         Page 4
D.L. Mills


while the Host Table is used to determine the link, with respect to
the DCN host, on the route to a virtual host.  The Host Table is
maintained dynamically using updates generated by periodic HELLO
messages.  The Net Table is fixed at configuration time for all DCN
hosts except those that support a GGP/EGP Gateway process.  In these
cases the Net Table is updated as part of the gateway operations.  In
addition, entries in either table can be changed by operator commands.

     The Net Table format is shown in Figure 1.

                        1                   0 
              5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |           Net Name            |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |    Net(2)     |    Net(1)     |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |    Index      |    Net(3)     |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |     Hops      |  Gateway ID   |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |                               |
             |        Gateway Leader         |
             |                               |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                 Figure 1. Net Table Entry

     The "Net Name" field defines a short (RAD50) name for the net,
while the "Net" fields define the class A/B/C net number.  The
"Gateway ID" field contains the host ID of the first gateway to the
net and the "Hops" field the number of hops to it.  The remaining
fields are used only by the GGP/EGP Gateway process and include the
"Index" field, which contains an index into the routing matrix.  and
the "Gateway Leader" field, which contains the (byte-swapped)
local-net leader for the gateway on a neighbor net.

     The Net Table contains an indefinite number of entries and is
terminated by a special entry with all "Net" fields set to zero.  If
the "Hops" field of this entry is less than 255, the "Gateway ID"
field of this entry is used for all nets not in the table.  If the
"Hops" field is 255 all nets not explicitly mentioned in the table
appear unreachable.

     The Host Table format is shown in Figure 2.

DCN Local-Network Protocols                                         Page 5
D.L. Mills


                        1                   0 
              5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |             Name              |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |      TTL      |    Port ID    |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |             Delay             |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |             Offset            |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |                               |
             +                               +
             |          Local Leader         |
             +                               +
             |                               |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |                               |
             +        Update Timestamp       +
             |                               |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 2. Host Table Entry

     The ordinal position of each Host Table entry corresponds to its
host ID.  The "Name" field contains a short (RAD50) name for
convenient reference.  The "Port ID" field contains the port ID of the
net-output process on the shortest path to this virtual host and the
"Delay" field contains the measured roundtrip delay to it.  The
"Offset" field contains the difference between the logical clock of
this host and the logical clock of the local host.  The "Local Leader"
field contains information used to construct the local leader of the
outgoing packet, for those nets that require it.  The "Update
Timestamp" field contains the logical clock value when the entry was
last updated and the "TTL" field the time (in seconds) remaining until
the virtual host is declared down.

     All fields except the "Name" field are filled in as part of the
routing update process, which is initiated upon arrival of a HELLO
message from a neighboring DCN host.  This message takes the form of
an IP datagram carrying the reserved protocol number 63 and a data
field as shown in Figure 3.

DCN Local-Network Protocols                                         Page 6
D.L. Mills


                        1                   0 
              5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0