Movatterモバイル変換

Network Working Group                                   D.L.  MillsRequest for Comments:  891                              December 1983DCN Local-Network ProtocolsThis RFC is a description of the protocol used in the DCN localnetworks to maintain connectivity, routing, and timekeepinginformation.  These procedures may be of interest to designers andimplementers of other networks.1.  Introduction     This document describes the local-net architecture and protocolsof the Distributed Computer Network (DCN), a family of local netsbased on Internet technology and an implementation of PDP11-basedsoftware called the Fuzzball.  DCN local nets have been in operationfor about three years and now include clones in the USA, UK, Norwayand West Germany.  They typically include a number of PDP11 or LSI-11Fuzzballs, one of which is elected a gateway, and often include otherInternet-compatible hosts as well.     The DCN local-net protocols are intended to provide connectivity,routing and timekeeping functions for a set of randomly connectedpersonal computers and service hosts.  The design philosophy guidingthe Fuzzball implementation is to incorporate complete functionalityin every host, which can serve as a packet switch, gateway and servicehost all at the same time.  When a set of Fuzzballs are connectedtogether using a haphazard collection of serial, parallel andcontention-bus interfaces, they organize themselves into a networkwith routing based on minimum delay.     The purpose of this document is to describe the local-netprotocols used by the DCN to maintain connectivity, routing andtimekeeping functions.  The document is an extensive revision andexpansion ofSection 4.2 of [1] and is divided into two parts, thefirst of which is an informal description of the architecture,together with explanatory remarks.  The second part consists of asemi-formal specification of the entities and protocols used todetermine connectivity, establish routing and maintain clocksynchronization and is designed to aid in the implementation of cohortsystems.  The link-level coding is described in the appendix.2.  Narrative Description     The DCN architecture is designed for local nets of up to 256hosts and gateways using the Internet Protocol (IP) and clientprotocols.  It provides adaptive routing and clock synchronizationfunctions in an arbitrary topology including point-to-point links andmultipoint bus systems.  It is intended for use in connecting personalcomputers to each other and to service machines, gateways and otherhosts of the Internet community.  However, it is not intended for usein large, complex networks and does not support the sophisticatedrouting and control algorithms of, for example, the ARPANET.     A brief description of the process and addressing structure usedin the DCN may be useful in the following.  A DCN physical host is aPDP11-compatible processor which supports a number of cooperatingsequential processes, each of

DCN Local-Network Protocols                                         Page 2D.L. Millswhich is given a unique 8-bit identifier called its port ID.  EveryDCN physical host contains one or more internet processes, each ofwhich supports a virtual host given a unique 8-bit identifier calledits host ID.     Each virtual host can support multiple internet protocols,connections and, in addition, a virtual clock.  Each physical hostcontains a physical clock which can operate at an arbitrary rate and,in addition, a 32-bit logical clock which operates at 1000 Hz and isassumed to be reset each day at 0000 hours UT.  Not all physical hostsimplement the full 32-bit precision; however, in such cases theresolution of the logical clock may be somewhat less.     There is a one-to-one correspondence between Internet addressesand host IDs.  The host ID is formed from a specified octet of theInternet address to which is added a specified offset.  The octetnumber and offset are selected at configuration time and must be thesame for all DCN hosts sharing the local net.  For class-B and class-Cnets normally the fourth octet is used in this way for routing withinthe local net.  In the case of class-B nets, the third octet isconsidered part of the net number by DCN hosts; therefore, this octetcan be used for routing between DCN local nets.  For class-A netsnormally the third octet (ARPANET logical-host field) is used forrouting where necessary.     Each DCN physical host is identified by a host ID for the purposeof detecting loops in routing updates, which establish theminimum-delay paths between the virtual hosts.  By convention, thephysical host ID is assigned as the host ID of one of its virtualhosts.  A link to a neighbor net is associated with a special virtualhost, called a gateway, which is assigned a unique host ID.     The links connecting the various physical hosts together and toforeign nets can be distributed in arbitrary ways, so long as the netremains fully connected.  If full connectivity is lost, due to a linkor host fault, the virtual hosts in each of the surviving segments cancontinue to operate with each other and, once connectivity isrestored, with all of them.     Datagram routing is determined entirely by internet address -there is no local leader as in the ARPANET.  Each physical hostcontains two tables, the Host Table, which is used to determine theoutgoing link to each other local-net host, and the Net Table, whichis used to determine the outgoing host (gateway) to each other net.The Host Table contains estimates of roundtrip delay and logical-clockoffset for all virtual hosts in the net and is indexed by host ID.For the purpose of computing these estimates the delay and offset ofeach virtual host relative to the physical host in which it resides isassumed zero.  The single exception to this is a special virtual hostassociated with an NBS radio time-code receiver, where the offset iscomputed relative to the broadcast time.     The Net Table contains an entry for every neighbor net that maybe connected to the local net and, in addition, certain other netsthat are not

DCN Local-Network Protocols                                         Page 3D.L. Millsneighbors.  Each entry contains the net number, as well as the host IDof the local-net gateway to that net.  The routing function simplylooks up the net number in the Net Table, finds the host ID of thegateway and retrieves the port ID of the net-output process from theHost Table.  Other information is included in the Host Table and NetTable as described below.     The delay and offset estimates are updated by HELLO messagesexchanged on the links connecting physical-host neighbors.  The HELLOmessages are exchanged frequently, but not so as to materially degradethe throughput of the link for ordinary data messages.  A HELLOmessage contains a copy of the delay and offset information from theHost Table of the sender, as well as information to compute theroundtrip delay and logical-clock offset of the receiver relative tothe sender.     The routing algorithm is similar to that (formerly) used in theARPANET and other places in that the roundtrip (biased) delay estimatecalculated to a neighbor is added to each of the delay estimates givenin its HELLO message and compared with the corresponding delayestimates in the Host Table.  If a delay computed in this way is lessthan the delay already in the Host Table, the routing to thecorresponding virtual host is changed accordingly.  The detailedoperation of this algorithm, which includes provisions for hostup-down logic and loop suppression, is summarized in a later section.     DCN local nets are self-configuring for all hosts and neighbornets; that is, the routing algorithms will find minimum-delay pathsbetween all hosts and gateways to neighbor nets.  In addition,timekeeping information can be exchanged using special HELLO messagesbetween neighboring DCN local nets.  For routing beyond neighbor netsadditional entries can be configured in the Net Tables as required.In addition, a special entry can be configured in the Net Tables whichspecifies the host ID of the gateway to all nets not explicitlyincluded in the table.     For routing via the ARPANET and its reachable nets a selectedlocal-net host is equipped with an IMP interface and configured with aGGP/EGP Gateway process.  This process maintains the Net Table of thelocal host, including ARPANET leaders, dynamically as part of theGGP/EGP protocol interactions with other ARPANET gateways.  GGP/EGPprotocol interactions are possibly with non-ARPANET gateways as well.     The portable virtual-host structure used in the DCN encourages arather loose interpretation of addressing.  In order to minimizeconfusion in the following, the term "host ID" will be applied only tovirtual hosts, while "host number" will be applied to the physicalhost, called generically the DCN host.2.1.  Net and Host Tables     There are two tables in every DCN host which control routing ofInternet Protocol (IP) datagrams: the Net Table and the Host Table.The Net Table is used to determine the host ID of the gateway on theroute to a foreign net,

DCN Local-Network Protocols                                         Page 4D.L. Millswhile the Host Table is used to determine the link, with respect tothe DCN host, on the route to a virtual host.  The Host Table ismaintained dynamically using updates generated by periodic HELLOmessages.  The Net Table is fixed at configuration time for all DCNhosts except those that support a GGP/EGP Gateway process.  In thesecases the Net Table is updated as part of the gateway operations.  Inaddition, 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 thenet and the "Hops" field the number of hops to it.  The remainingfields are used only by the GGP/EGP Gateway process and include the"Index" field, which contains an index into the routing matrix.  andthe "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 isterminated by a special entry with all "Net" fields set to zero.  Ifthe "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 tableappear unreachable.     The Host Table format is shown in Figure 2.

DCN Local-Network Protocols                                         Page 5D.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 itshost ID.  The "Name" field contains a short (RAD50) name forconvenient reference.  The "Port ID" field contains the port ID of thenet-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 ofthis host and the logical clock of the local host.  The "Local Leader"field contains information used to construct the local leader of theoutgoing packet, for those nets that require it.  The "UpdateTimestamp" field contains the logical clock value when the entry waslast updated and the "TTL" field the time (in seconds) remaining untilthe virtual host is declared down.     All fields except the "Name" field are filled in as part of therouting update process, which is initiated upon arrival of a HELLOmessage from a neighboring DCN host.  This message takes the form ofan IP datagram carrying the reserved protocol number 63 and a datafield as shown in Figure 3.

DCN Local-Network Protocols                                         Page 6D.L. Mills                        1                   0              5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0         --- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+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 ofthe message.  One format, sent by a DCN host to another host on thesame local net, includes both the fixed and host areas shown above.The second format, sent in all other cases, includes only the fixedarea.     Note that all word fields shown are byte-swapped with respect tothe ordinary PDP11 representation.  The "Checksum" field contains achecksum covering the fields indicated.  The "Date" and "Time" fieldsare 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 afInternet addresses used by the local net.  The "Delay Host n" and"Offset Host n" fields represent a copy of the corresponding entriesof 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 itsneighbor 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 messagereceived.

DCN Local-Network Protocols                                         Page 7D.L. MillsWhen constructing a HELLO message the sender sets thedestination-address field to this state variable and thesource-address field to its own address.  It then fills in the "Date"and "Time" fields from its logical clock and the "Timestamp" fieldfrom 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 bador the checksum fails.  If valid, it initializes a link state variableto show that the link is up.  Each time a HELLO message is transmittedthis state variable is decremented.  If it decrements to zero the linkis declared down.     The host then checks if the source-address field matches thestate variable containing the last address stored.  If not, the linkhas been switched to a new host, so the state variables are flushedand the link forced into a recovery state.  The host then checks ifthe destination-address field matches its own address.  If so, themessage has been looped (legal only in the case of a broadcast net)and the roundtrip delay information is corrected.  The host and netareas are ignored in this case.  If not, the host and net areas of themessage 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 aninternal state variable which is updated as each HELLO message isreceived and transmitted.  When a HELLO message is received thisvariable takes the value of the "Time" field minus the currenttime-of-day.  When the next HELLO message is transmitted, the valueassigned the "Timestamp" field is computed as the low-order 16-bits ofthis variable plus the current time-of-day.  The value of thisvariable is forced to zero if either the link is down of the systemlogical clock has been reset since the last HELLO message wasreceived.     If a HELLO message is received with zero "Timestamp" field, noprocessing other than filling in the internal state variable.Otherwise, the roundtrip delay is computed as the low-order 16-bits ofthe current time-of-day minus the value of this field.  In order toassure the highest accuracy, the calculation is performed only if thelength of the last transmitted HELLO message (in octets) matches thelength of the received HELLO message.     The above technique renders the calculation independent of theclock offsets and intervals between HELLO messages at either host,protects against errors that might occur due to lost HELLO messagesand works even when a neighbor host simply forwards the HELLO messageback to the originator without modifying it.  The latter behavior,typical of ARPANET IMPs and gateways, as well as broadcast nets, relieson the loop-detection mechanism so that correct calculations can bemade and, furthermore, that spurious host updates can be avoided.

DCN Local-Network Protocols                                         Page 8D.L. Mills2.3.  Host Updates     When a HELLO message arrives which results in a valid roundtripdelay calculation, a host update process is performed.  This consistsof adding the roundtrip delay to each of the "Delay Host n" entries inthe HELLO message in turn and comparing each of these calculateddelays to the "Host Delay" field of the corresponding Host Tableentry.  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 withthe calculated delay, the "Port ID" field with the PID of the linkoutput process, the "Update Timestamp" field with the current time ofday and the "TTL" field by a specified value (currently 120) inseconds.  If the calculated delay exceeds a specified maximum interval(currently 30 seconds), the virtual host is declared down by settingthe corresponding "Delay" field to the maximum and the remainingfields as before.  For the purposes of delay calculations values lessthan a specified minimum (currently 100 milliseconds) are rounded upto that minimum.     The "Offset" field is also replaced during the update process.When the HELLO message arrives, The value of the current logical clockis subtracted from the "Time" field and the difference added toone-half the roundtrip delay.  The resulting sum, which represents theoffset of the local clock to the clock of the sender, is added to thecorresponding "Offset" field of the HELLO message and the sum replacesthe "Offset" field of the Host Table.  Thus, the "Offset" field in theHost Table for a particular virtual host is replaced only if that hostis up and on the minimum-delay path to the DCN host.     The purpose of the switching threshold in (2) above and theminimum delay specification in the update process is to avoidunnecessary switching between links and transient loops which canoccur due to normal variations in propagation delays.  The purpose ofthe "TTL" field test in (4) above is to ensure consistency by purgingall paths to a virtual host when that virtual host goes down.

DCN Local-Network Protocols                                         Page 9D.L. Mills     In addition to the updates performed as HELLO messages arrive, eachvirtual host in a DCN host also performs a periodic update of its ownHost Table entry.  The update procedure is identical to the above,except that the calculated delay and offset are taken as zero.  Atleast one of the virtual hosts in a DCN host must have the same hostID as the host number assigned the DCN host itself and all must beassigned the same net number.  Other than these, there are norestrictions on the number or addresses of internet processes residentin a single DCN host.     It should be appreciated that virtual hosts are truly portableand can migrate about the net, should such a requirement arise.  Thehost update protocols described here insure that the routingprocedures always converge to the minimum-delay paths via operationallinks and DCN hosts.  In the case of broadcast nets such as Ethernets,the procedures are modified slightly as described below.  In this casethe HELLO messages are used to determine routing from the variousEthernet hosts to destinations off the cable, as well as to providetime synchronization.2.4.  Timeouts     The "TTL" field in every Host Table entry is decremented once asecond in normal operation.  Thus, if following a host update anotherupdate is not received within an interval corresponding to the valueinitialized in that field, it decrements to zero, at which point thevirtual host is declared down and the Host Table entry set asdescribed above.  The 120-second interval used currently provides forat least four HELLO messages to be generated by every neighbor onevery link during that interval, since the maximum delay between HELLOmessages is 30 seconds on the lowest-speed link (1200 bps).  Thus, ifno HELLO messages are lost, the maximum number of links between anyvirtual host and any other is four.     The "TTL" field is initialized at 120 seconds when an updateoccurs and when the virtual host is declared down.  During theinterval this field decrements to zero immediately after beingdeclared down, updates are ignored.  This provides a decent intervalfor the bad news to propagate throughout the net and for the HostTables in all DCN hosts to reflect the fact.  Thus, the formation ofrouting 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 pointwhere it is forwarded, whichever comes first.  The value usedcurrently for this purpose is 30, so that an IP datagram can live inthe net no longer than that number of seconds.  This is thus themaximum delay allowed on any path between two virtual hosts.  If thismaximum delay is exceeded in calculating the roundtrip delay for aHost Table entry, the corresponding virtual host will be declareddown.

DCN Local-Network Protocols                                        Page 10D.L. Mills     The interval between HELLO messages on any link depends on thedata rate supported by the link.  As a general rule, this interval isset at 16 times the expected roundtrip time for the longest packet tobe sent on that link.  For 1200-bps asynchronous transmission andpacket lengths to 256 octets, this corresponds to a maximum HELLOmessage interval of about 30 seconds.     Although the roundtrip delay calculation, upon which the routingprocess depends, is relatively insensitive to net traffic andcongestion, stochastic variations in the calculated values ordinarilyoccur due to coding (bit or character stuffing) and mediumperturbations.  In order to suppress loops and needless path changes aminimum switching threshold is incorporated into the routing mechanism(see above).  The interval used for this threshold, as well as for theminimum delay on any path, is 100 milliseconds.3.  Formal Specification     The following sections provide a formal framework which describethe DCN HELLO protocol.  This protocol is run between neighboring DCNhosts that share a common point-to-point link and provides automaticconnectivity determination, routing and timekeeping functions.     The descriptions to follow are organized as follows: First asummary of data structures describes the global variables and packetformats.  Then three processes which implement the protocol aredescribed: the CLOCK, HELLO and HOST processes.  The description ofthese processes is organized into sections that describe (1) the localvariables used by that process, (2) the parameters and constants and(3) the events that initiate processing together with the proceduresthey evoke.  In the case of variables a distinction is made betweenstate variables, which retain their contents between procedure calls,and temporaries, which have a lifetime extending only while theprocess is running.  Except as noted below, the initial contents ofstate variables are unimportant.3.1.  Data Structures3.1.1.  Global VariablesADDRESS    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    corresponding to 1972, bits 5-9 contain the day of the month and

DCN Local-Network Protocols                                        Page 11D.L. Mills    bits 10-14 contain the month, starting with one for January.DATE-VALID    This is a one-bit state variable used to indicate whether the    local date and time are synchronized with the master clock.  A    value of one indicates the local clock is not synchronized with    the master clock.  This variable is set to one initially and when    the local time-of-day rolls over past midnight.  It is set to zero    each time a valid date and time update has been received from the    master clock.DELAY    This is a 16-bit integer temporary variable which represents the    roundtrip delay in milliseconds to a host.HID    This is an eight-bit integer temporary variable containing the    host ID of some host on the local net.    There is a one-to-one correspondence between the Internet    addresses of local hosts and their HIDs.  The mapping between them    is selected on the basis of the octet number of the Internet    address.  For DCN hosts it is the fourth octet, while for hosts    directly connected to a class-A ARPANET IMP or gateway, it is the    third octet (logical-host field).  The contents of this octet are    to be added to ADDRESS-OFFSET to form the HID associated    with the address.HOLD    This is an eight-bit counter state variable indicating whether    timestamps are valid or not.  While HOLD is nonzero, timestamps    should be considered invalid.  When set to some nonzero value, the    counter decrements to zero at a 1-Hz rate.  Its initial value is    zero.HOST-TABLE    This is a table of NHOSTS entries indexed by host ID (HID).  There    is one entry for each host in the local net.  Each entry has the    following format:    HOST-TABLE.DELAY        This is a 16-bit field containing the computed roundtrip delay        in milliseconds to host HID.    HOST-TABLE.OFFSET        This is a 16-bit field containing the computed signed offset        in milliseconds which must be added to the local apparent        clock to agree with the apparent clock of host HID.    HOST-TABLE.PID        This is an eight-bit field containing the PID of the net-output        process selected by the routing algorithm to forward packets        to host HID.

DCN Local-Network Protocols                                        Page 12D.L. Mills HOST-TABLE.TTL     This is an eight-bit field used as a time-to-live indicator.     It is decremented by the HOST process once each second and     initialized to a chosen value when a HELLO message is     received. The table is initialized with the HOST-TABLE.DELAY     field set to  MAXDELAY for all entries.  The contents of the     other fields are unimportant.LOCAL-ADDRESS    This is a 32-bit bit-string state variable used to contain the    local host Internet address.NET-TABLE    This is a table of NNETS entries with the following format:    NET-TABLE.HID        This is an eight-bit field containing the host ID of the        pseudo-process to forward packets to the NET-TABLE.NET net.    NET-TABLE.NET        This is a 24-bit field containing an Internet class-A (eight        bits), class-B (16 bits) or class-C (24 bits) net number.        Note that the actual field width for class-B net numbers is 24        bits in order to provide a subnet capability, in which the        high-order eight bits of the 16-bit host address is        interpreted as the subnet number.    The table is constructed at configuration time and must include an    entry for every net that is a potential neighbor.  A neighbor net    is defined as a net containing a host that can be directly    connected to a host on the local net.  The entry for such a net is    initialized with NET-TABLE.NET set to the neighbor net number and    NET-TABLE.HID set to an arbitrary vitual-host ID not assigned any    other local-net virtual host.    The remaining entries in NET-TABLE are initialized at initial-boot    time with the NET-TABLE.NET fields set to zero and the    NET-TABLE.HID fields set to a configuration-selected host ID to be    used to forward packets to all nets other than neighbor nets.  In    the case where a gateway module is included in the local host    configuration, the GGP and/or EGP protocols will be used to    maintain these entries;  while, in the case where no gateway    module is included, only one such entry is required.OFFSET    This is a 16-bit signed integer temporary variable which    represents the offset in milliseconds to be added to the apparent    clock time to yield the apparent clock time of the neighbor host.3.1.2.  ParametersADDRESS-OFFSET    This is an integer which represents the value of the Internet    address field corresponding to the first host in HOST-TABLE.

DCN Local-Network Protocols                                        Page 13D.L. MillsNHOSTS    This is an integer which defines the number of entries in HOST-TABLE.NNETS    This is an integer which defines the number of entries in MET-TABLE.3.1.3.  HELLO Packet FieldsPKT.ADDRESS-OFFSET    This eight-bit is copied from ADDRESS-OFFSET by the sender.PKT.DATESTAMP    Bits 0-14 of this 16-bit field are copied from DATE by the sender,    while bit 15 is copied from DATE-VALID.PKT.DATE-VALID    This one-bit field is bit 15 of PKT.DATESTAMP.PKT.DESTINATION    This 32-bit field is part of the IP header.  It is copied from    HLO.NEIGHBOR-ADDRESS by the sender.PKT.HOST-TABLE    This is a table of PKT.NHOSTS entries, each entry of which    consists of two fields.  The entries are indexed by host ID and    have the following format:    PKT.HOST-TABLE.DELAY        This 16-bit field is copied from the corresponding HOST-TABLE.DELAY        field by the sender.    PKT.HOST-TABLE.OFFSET        This 16-bit field is copied from the corresponding HOST-TABLE.OFFSET        field by the sender.PKT.LENGTH    This 16-bit field is part of the IP header.  It is set by the sender to    the number of octets in the packet.PKT.NHOSTS    This eight-bit field is copied from NHOST by the sender.PKT.SOURCE    This 16-bit field is part of the IP header.  It is copied from    LOCAL-ADDRESS by the sender.PKT.TIMESTAMP    This 32-bit field contains the apparent time the packet was transmitted    in milliseconds past midnight UT.

DCN Local-Network Protocols                                        Page 14D.L. MillsPKT.TSP    This 16-bit field contains a variable used in roundtrip delay    calculations.3.2 CLOCK Process (CLK)     The timekeeping system maintains three clocks: (1) the physicalclock, which is determined by a hardware oscillator/counter; (2) theapparent clock, which maintains the time-of-day used by clientprocesses and (3) the actual clock, which represents the time-of-dayprovided by an outside reference.  The apparent and actual clocks aremaintained as 48-bit quantities with 32 bits of significance availableto client processes.  These clocks run at a rate of 1000 Hz and arereset at midnight UT.     The CLOCK process consists of a set of state variables along witha set of procedures that are called as the result of hardwareinterrupts and client requests.  An interval timer is assumedlogically separate from the local clock mechanism, although both couldbe derived from the same timing source.3.2.1.  Local VariablesCLK.CLOCK    This is a 48-bit fixed-point state variable used to represent the    apparent time-of-day.  The decimal point is to the right of bit 16    (numbering from the right at bit 0).  Bit 16 increments at a rate    equivalent to 1000 Hz independent of the hardware clock.  (In the    case of programmable-clock hardware the value of CLK.CLOCK must be    corrected as described below.)CLK.COUNT    This is a hardware register that increments at rate R.  It can be    represented by a simple line clock, which causes interrupts at the    line-frequency rate, or by a programmable clock, which contains a 16-bit    register that is programmed to count at a 1000-Hz rate and causes an    interrupt on overflow.  The register is considered a fixed-point variable    with decimal point to the right of bit 0.CLK.DELTA    This is a 48-bit signed fixed-point state variable used to represent the    increment to be added to CLK.CLOCK to yield the actual time-of-day.  The    decimal point is to the right of bit 16.3.2.3.  ParametersADJUST-FRACTION    This is an integer which defines the shift count used to compute a    fraction that is used as a multiplier of CLK.DELTA to correct CLK.CLOCK    once each clock-adjust interval.  A value of seven is suggested.

DCN Local-Network Protocols                                        Page 15D.L. MillsADJUST-INTERVAL    This is an integer which defines the clock-adjust interval in    milliseconds.  A value of 500 (one-half second) is suggested for    the line clock and 4000 (four seconds) for the 1000-Hz clock.CLOCK-TICK    This is a fixed-point integer which defines the increment in    milliseconds to be added to CLK.CLOCK as the result of a clock    tick.  The decimal point is to the right of bit 16.  In the case    of a line-clock interrupt, the value of CLOCK-TICK should be    16.66666 (60 Hz) or 20.00000 (50 Hz).  In the case of a 1000-Hz    programmable-clock overflow, the value should be 65536.00000.HOLD-INTERVAL    This is an integer which defines the number of seconds that HOLD will    count down after CLK.CLOCK has been reset.  The resulting interval must be    at least as long as the maximum HELLO-INTERVAL used by any HELLO process.3.2.3.  Events and ProceduresINCREMENT-CLOCK Event    This event is evoked as the result of a tick interrupt, in the case of a    line clock, or a counter overflow, in the case of the 1000-Hz clock.  It    causes the logical clock to be incremented by the value of CLOCK-TICK.    1.  Add the value of CLOCK-TICK to CLK.CLOCK.ADJUST-CLOCK Event    This event is evoked once every ADJUST-INTERVAL milliseconds to slew the    apparent clock time to the actual clock time as set by the SET-CLOCK    procedure.  This is done by subtracting a fraction of the correction    factor CLK.DELTA from the value of CLK.DELTA and adding the same fraction    to CLK.CLOCK.  This continues until either the next SET-CLOCK call or    CLK.DELTA has been reduced to zero.    The suggested values for ADJUST-INTERVAL and ADJUST-FRACTION    represent a maximum slew rate of less than +-2 milliseconds per    second, in the case of 1000-Hz clock.  The action is to smooth    noisy clock corrections received from neighboring systems to    obtain a high-quality local reference, while insuring the apparent    clock time is always monotonically increasing.    1.  Shift the 48-bit value of CLK.DELTA arithmetically ADJUST-FRACTION        bits to the right, discarding bits from the right and saving the        result in a temporary variable F.  Assuming the decimal point of F to        be positioned to the right of bit 16 and sign-extending as necessary,        subtract F from CLK.DELTA and add F to CLK.CLOCK.

DCN Local-Network Protocols                                        Page 16D.L. MillsDECREMENT-HOLD Event    This event is evoked once per second to decrement the value of HOLD.    1.  If the value of HOLD is zero, do nothing;  otherwise, decrement its        value.READ-CLOCK Procedure    This procedure is called by a client process.  It returns the apparent    time-of-day computed as the integer part of the sum CLK.CLOCK plus    CLK.COUNT.  Note that the precision of the value returned is limited to    +-1 millisecond, so that client processes must expect the apparent    time to "run backward" occasionally due to drift corrections.  When    this happens the backward step will never be greater than one    millisecond and will never occur more often than twice per second.    1.  In the case of line clocks CLK.COUNT is always zero, while in        the case of programmable clocks the hardware must be        interrogated to extract the value of CLK.COUNT.  If following        interrogation a counter-overflow condition is evident, add        CLOCK-TICK to CLK.CLOCK and interrogate the hardware again.    2.  When the value of CLK.COUNT has been determined compute the sum        CLK.COUNT + CLK.CLOCK.  If this sum exceeds the number of        milliseconds in 24 hours (86,400,000), reduce CLK.CLOCK by        86,400,000, set HOLD-INTERVAL -> HOLD, set CLOCK-VALID (bit 15        of DATE) to one, roll over DATE to the next calendar day and        start over.  If not, return the integer part of the sum as the        apparent time-of-day.        The CLOCK-VALID bit is set to insure that a master-clock update is        received at least once per day.  Note that, in the case of        uncompensated crystal oscillators of the type commonly used as the        1000-Hz time base, a drift of several parts per million can be        expected, which would result in a time drift of several tenths of a        second per day, if not corrected.SET-CLOCK Procedure    This procedure is called by a client process.  It sets a time-of-day    correction factor in milliseconds.  The argument represents a 32-bit    signed fixed-point quantity with decimal point to the right of bit    0 that is to be added to CLK.CLOCK so that READ-CLOCK subsequently    returns the actual time-of-day.    1.  If the correction factor is in the range -2**(16-ADJUST-FRACTION) to        +2**(16-ADJUST-FRACTION) - 1 (about +-128 milliseconds with the        suggested value of ADJUST-FRACTION), the value of the argument        replaces CLK.DELTA and the procedure is complete.  If not, add the        value of the sign-extended argument to CLK.CLOCK and set CLK.DELTA to        zero.  In addition, set HOLD-INTERVAL -> HOLD, since this        represents a relatively large step-change in apparent time.        The value of HOLD represents the remaining number of seconds        in which timestamps should be considered invalid and is used        by the HELLO process to suppress roundtrip delay calculations        which might involve invalid timestamps.

DCN Local-Network Protocols                                        Page 17D.L. Mills3.3.  HELLO Process     The HELLO process maintains clock synchronization with a neighborHELLO process using the HELLO protocol.  It also participates in therouting algorithm.  There is one HELLO process and one set of localstate variables for each link connecting the host to one of itsneighbors.3.3.1.  Local variablesHLO.BROADCAST    This is a one-bit switch state variable.  When set to zero a    point-to-point link is assumed.  When set to one a broadcast (e.g.    Ethernet) link is assumed.HLO.KEEP-ALIVE    This is an eight-bit counter state variable used to indicate whether the    link is up.  It is initialized with a value of zero.HLO.LENGTH    This is a 16-bit integer state variable used to record the length in    octets of the last HELLO message sent.HLO.NEIGHBOR-ADDRESS    This is a 32-bit integer state variable used to contain the neighbor host    Internet address.HLO.PID    This is an eight-bit integer state variable used to identify the    net-output process associated with this HELLO process.  It is initialized    by the kernel when the process is created and remains unchanged    thereafter.HLO.POLL    This is a one-bit switch state variable.  When set the HELLO process    spontaneously sends HELLO messages.  When not set the HELLO process    responds to HELLO messages, but does not send them spontaneously.HLO.TIMESTAMP    This is a 32-bit integer temporary variable used to record the time of    arrival of a HELLO message.HLO.TSP    This is a 16-bit signed integer state variable used in roundtrip delay    calculations.

DCN Local-Network Protocols                                        Page 18D.L. Mills3.3.2.  ParametersHELLO-INTERVAL    This is an integer which defines the interval in seconds between HELLO    messages.  It ranges from about eight to a maximum of 30 seconds,    depending on line speed.HOLD-DOWN-INTERVAL    This is an integer which defines the interval in seconds a host will be    considered up following receipt of a HELLO message indicating that    host is up.  A value of 120 is suggested.KEEP-ALIVE-INTERVAL    This is an integer which defines the interval, in units of    HELLO-INTERVAL, that a HELLO process will consider the link up.  A    value of four is suggested.MAXDELAY    This is an integer which defines the maximum roundtrip delay in    seconds on a path to any reachable host.  A value of 30 is suggested.MINDELAY    This is an integer which defines the minimum switching threshold in    milliseconds below which routes will not be changed.  A value of 100 is    suggested.3.3.3.  Events and ProceduresINPUT-PACKET Event    When a packet arrives the net-input process first sets HLO.TIMESTAMP to    the value returned by the READ-CLOCK procedure, then checks the    packet for valid local leader, IP header format and checksum.  If    the protocol field in the IP header indicates a HELLO message, the    packet is passed to the HELLO process.  If any errors are found    the packet is dropped.    The HELLO process first checks the packet for valid HELLO header format    and checksum.  If any errors are found the packet is dropped.  Otherwise,    it proceeds as follows:    1.  If PKT.SOURCE is equal to LOCAL-ADDRESS, then the line to the        neighbor host is looped.  If this is a broadcast link        (HLO.BROADCAST is set to one), then ignore this nicety;  if        not, this is considered an error and further processing is        abandoned.  Note that, in special configurations involving        other systems (e.g.  ARPANET IMPs and gateways) it may be        useful to use looped HELLO to monitor connectivity.  The DCN        implementation provides this feature, but is not described here.    2.  Set KEEP-ALIVE-INTERVAL -> HLO.KEEP-ALIVE.  This indicates the        maximum number of HELLO intervals the HLO.TSP field is        considered valid.

DCN Local-Network Protocols                                        Page 19D.L. Mills    3.  Set PKT.TIMESTAMP - HLO.TIMESTAMP -> HLO.TSP.  This is part of the        roundtrip delay calculation.  The value of HLO.TSP will be        updated and returned to the neighbor in the next HELLO message        transmitted.  Next, compute the raw roundtrip delay and offset:        HLO.TIMESTAMP - PKT.TSP -> DELAY and HLO.TSP + DELAY/2 -> OFFSET.        Note:  in the case of a broadcast link (HLO.BROADCAST set to one) set        DELAY to zero.    4.  Perform this step only in the case of non-broadcast links        (HLO.BROADCAST set to zero).  If PKT.SOURCE is not equal to        HLO.NEIGHBOR-ADDRESS, then a new neighbor has appeared on this        link. Set PKT.SOURCE -> HLO.NEIGHBOR ADDRESS, MAXDELAY ->        DELAY and proceed to the next step.  This will force the line        to be declared down and result in a hold-down cycle.        Otherwise, if either PKT.TSP is zero or HOLD is nonzero, then        the DELAY calculation is invalid and further processing is        abandoned.  Note that a hold-down cycle is forced in any        case if a new neighbor is recognized.    5.  If processing reaches this point the DELAY and OFFSET        variables can be assumed valid as well as the remaining data        in the packet.  First, if DELAY < MINDELAY, set MINDELAY ->        DELAY.  This avoids needless path switching when the        difference in delays is not significant and has the effect        that on low-delay links the routing algorithm degenerates to        min-hop rather than min-delay.  Then set HLO.PID -> PID.  There are        two cases:        Case 1:  PKT.NHOSTS is zero.            This will be the case when the neighbor host has just come up or            is on a different net or subnet.  Set NEIGHBOR-ADDRESS -> ADDRESS            and call the ROUTE procedure, which will return the host            ID.  Then call the UPDATE procedure.  In the case of            errors, do nothing but return.        Case 2:  PKT.NHOSTS is nonzero.            This is the case when the neighbor host is on the same net or            subnet.  First, save the values of DELAY and OFFSET in temporary            variables F and G.  Then, for each value of HID from zero to            NHOSTS-1 consider the corresponding PKT.HOSTS-TABLE entry and do            the following:  Set F + PKT.HOST-TABLE.DELAY -> DELAY and            G + PKT.HOST-TABLE.OFFSET -> OFFSET and call the UPDATE procedure.            This completes processing.        ROUTE Procedure            This procedure returns the host ID in HID of the host represented            by the global variable ADDRESS.    1.  First, determine if the host represented by ADDRESS is on the same        local net as LOCAL-ADDRESS.  For the purposes of this        comparison bits 0-7 and 16-31 are compared for class-A nets        and bits 8-31 are compared for class-B and class-C nets.  This        provides for a subnet capability, where the bits 0-7 and 16-23        (class-A) or 8-15 (class-B) are used as a subnet number.

DCN Local-Network Protocols                                        Page 20D.L. Mills        Case 1:  The host is on the same net or subnet.            Extract the address field of ADDRESS, subtract ADDRESS-OFFSET and            store the result in HID.  If 0 <= HID < NHOSTS, the procedure            completes normally;  otherwise it terminates in an error            condition.        Case 2:  The host is not on the same net or subnet.            Search the NET-TABLE for a match of the net fields of            LOCAL-ADDRESS and NET-TABLE.NET.  If found set            NET-TABLE.HID -> HID and return normally.  If the NET-TABLE.NET            field is zero, indicating the last entry in the table, set            HET-TABLE.HID -> HID and return normally.  Note that, in the case            of hosts including GGP/EGP gateway modules, if no match is found            the procedure terminates in an error condition.UPDATE Procedure    This procedure updates the entry of HOST-TABLE indicated by HID using    three global variables:  DELAY, OFFSET and PID.  Its purpose is to update    the HOST-TABLE entry corresponding to host ID HID.  In the following all    references are to this entry.    1.  If PID is not equal to HOST-TABLE.PID, the route to host HID is not        via the net-output process associated with this HELLO process.  In        this case, if DELAY + MINDELAY > HOST-TABLE.DELAY, the path is longer        than one already in HOST-TABLE, so the procedure does nothing.    2.  This step is reached only if either the route to host HID is via the        net-output process associated with this HELLO process or the newly        reported path to this host is shorter by at least MINDELAY.        There are two cases:        Case 1:  HOST-TABLE.DELAY < MAXDELAY.            The existing path to host HID is up and this is a point-to-point            link (HLO.BROADCAST is set to zero).  If DELAY < MAXDELAY the            newly reported path is also up.  Proceed to the next step.            Otherwise, initiate a hold-down cycle by setting            MAXDELAY -> HOST-TABLE.DELAY and            HOLD-DOWN-INTERVAL -> HOST-TABLE.TTL and return.        Case 2:  HOST-TABLE.DELAY >= MAXDELAY.            The existing path to host HID is down.  If DELAY < MAXDELAY and            HOST-TABLE.TTL is zero, the hold-down period has expired and the            newly reported path has just come up.  Proceed to the next step.            Otherwise simply return.    3.  In this step the HOST-DELAY entry is updated.  Set        DELAY -> HOST-TABLE.DELAY, HOLD-DOWN-INTERVAL -> HOST-TABLE.TTL and        HLO.PID -> HOST-TABLE.PID.

DCN Local-Network Protocols                                        Page 21D.L. Mills    4.  For precise timekeeping, the offset can be considered valid only if        the length of the last HELLO packet transmitted is equal to        the length of the last one received.  Thus, if HLO.LENGTH        equal to PKT.LENGTH, set OFFSET -> HOST-TABLE.OFFSET;        otherwise, leave this field alone. Finally, if HID is equal to        CLOCK-HID and bit 15 (the DATE-VALID bit)        of DATE is zero, set PKT.DATESTAMP -> DATE and call the SET-CLOCK        procedure of the CLOCK process with argument HLO.TIMESTAMP.OUTPUT-PACKET Event    This event is evoked once every HELLO-INTERVAL seconds.  It determines if    a HELLO message is to be transmitted, transmits it and updates state    variables.    1.  If HLO.KEEP-ALIVE is nonzero decrement its value.    2.  If HLO.POLL is zero and HLO.KEEP-ALIVE is zero, do not send a HELLO        message.  If either is nonzero initialize the packet fields as        follows:  LOCAL-ADDRESS -> PKT.SOURCE,        HLO.NEIGHBOR-ADDRESS -> PKT.DESTINATION and DATE -> PKT.DATESTAMP.        Note:  PKT.DESTINATION is set to zero if this is a broadcast link        (HLO.BROADCAST set to one).  Also, note that bit 15 of DATE is the        DATE-VALID bit.  If this bit is one the receiver will not update its        master clock from the information in the transmitted packet.        This is significant only if the sending host is on the        least-delay path to the master clock.  Set PKT.TIMESTAMP to        the value returned from the READ-CLOCK procedure.  If        HLO.KEEP-ALIVE is zero or HOLD is nonzero, set PKT.TSP to        zero;  otherwise, set PKT.TIMESTAMP + HLO.TSP -> PKT.TSP.    3.  Determine if the neighbor is on the same net or subnet.  If the        neighbor is on a different net set PKT.NHOSTS to zero and        proceed with the next step.  Otherwise, set NHOSTS ->        PKT.NHOSTS and for each value of HID from zero to PKT.HOSTS-1        copy the HOST-TABLE.DELAY and HOST-TABLE.OFFSET fields of the        corresponding HOST-TABLE entry in order into the packet.  For        each entry copied test if the HOST-TABLE.PID field matches the        HLO.PID of the HELLO process.  If so, a potential routing loop        is possible.  In this case use MAXDELAY for the delay field in        the packet instead.    4.  Finally, set HLO.LENGTH to the number of octets in the packet        and send the packet.3.4.  HOST Process (HOS)     This process maintains the routing tables.  It is activated once persecond to scan HOST-TABLE and decrement the HOST-TABLE.TTL field of eachentry.  It also performs housekeeping functions.

DCN Local-Network Protocols                                        Page 22D.L. Mills3.4.1.  Local variablesHOS.PID    This is an eight-bit integer used to identify the HOST process.  It is    initialized by the kernel when the process is created and remains    unchanged thereafter.HOS.HID    This is an eight-bit temporary variable.3.4.2.  Events and ProceduresSCAN Event    This event is evoked once each second to scan the HOST-TABLE and perform    housekeeping functions.    1.  For each value of a temporary variable F from zero to NHOSTS-1 do the        following:  Set LOCAL-ADDRESS -> ADDRESS and call the ROUTE        procedure, which will return the host ID HID.  If F is equal        to HID, then set both DELAY and OFFSET to zero, HOS.PID -> PID        and call the UPDATE procedure.  This will cause all packets        received with the local address to be routed to this process.        If HOST-TABLE.TTL is zero skip this step.  Otherwise, decrement        HOST-TABLE.TTL by one.  If the result is nonzero skip the        remainder of this step.  Otherwise, If HOST-TABLE.DELAY <MAXDELAY set        HOLDOFF-INTERVAL -> HOST-TABLE.TTL and MAXDELAY -> HOST-TABLE.DELAY.        The effect of this step is to declare a hold-down cycle when a host        goes down.4.  References1.  Mills, D.L.Final Report on Internet Research, ARPA Packet Switching    Program.  Technical Report TSLAB 82-7, COMSAT Laboratories,    December 1982.

DCN Local-Network Protocols                                        Page 23D.L. MillsAppendix A.  Link-Level Packet FormatsA.1.  Serial Links Using Program-Interrupt Interfaces     Following is a description of the frame format used onasynchronous and synchronous serial links with program-interruptinterfaces such as the DEC DLV11 and DPV11.  This format providestransparency coding for all messages, including HELLO messages, butdoes not provide error detection or retransmission functions.  It isdesigned to be easily implemented and compatible as far as possiblewith standard industry protocols.     The protocol is serial-by-bit, with the same interpretation onthe order of transmission as standard asynchronous and synchronousinterface devices; that is, the low-order bit of each octet istransmitted first.  The data portion of the frame consists of oneInternet datagram encoded according to a "character-stuffing"transparency convention:1.  The frame begins with the two-octet sequence DLE-STX, in the case of    asynchronous links, or the four-octet sequence SYN-SYN-DLE-STX, in the    case of synchronous links.  The data portion is transmitted next,    encoded as described below, followed by the two-octet sequence    DLE-ETX.  No checksum is transmitted or expected.  If it is    necessary for any reason to transmit time-fill other than in the    data portion, the DEL (all ones) is used.2.  Within the data portion of the frame the transmit buffer is    scanned for a DLE.  Each DLE found causes the sequence DLE-DLE to    be transmitted.  If it is necessary for some reason for the    transmitter to insert time-fill within the data portion, the    sequence DLE-DEL is used.3.  While scanning the data stream within the data portion of the    frame the sequence DLE-DLE is found, a single DLE is inserted in    the receive buffer.  If the sequence DLE-ETX is found, the buffer    is passed on for processing. The sequence DLE-DEL is discarded.    Any other two-octet sequence beginning with DLE and ending with    other than DLE, ETX or DEL is considered a protocol error    (see note below).     Note: In the case of synchronous links using program-interruptinterfaces such as the DPV11, for example, a slightly modifiedprotocol is suggested when both ends of the link concur.  Theseinterfaces typically provide a parameter register which can be loadedwith a code used both to detect the receiver synchronizing pattern andfor time-fill when the transmit buffer register cannot be serviced intime for the next character.     The parameter register must be loaded with the SYN code for thisprotocol to work properly.  However, should it be necessary totransmit time-fill, a single SYN will be transmitted, rather than theDLE-DEL sequence specified.  Disruptions due to these events can beminimized by use of the following rules:

DCN Local-Network Protocols                                        Page 24D.L. Mills1.  If the transmitter senses a time-fill condition (usually by a    control bit assigned for this purpose) between frames or    immediately following transmission of a DLE, the condition is ignored.2.  If the transmitter senses a time-fill condition at other times it sends    the sequence DLE-CAN.3.  If the receiver finds a SYN either between frames or immediately    following DLE, the SYN is discarded without affecting sequence    decoding.4.  If the receiver finds the sequence DLE-CAN in the data portion, it    discards the sequence and the immediately preceding octet.     These rules will work in cases where a single SYN has beeninserted by the transmitter and even when a SYN has been inserted inthe DLE-CAN sequence.  If an overrun (lost data) condition is sensedat the receiver, the appropriate action is to return to theinitial-synchronization state.  This should also be the action if anycode other than STX is found following the initial DLE.  or if anycode other than DLE, ETX, DEL or CAN is found following a DLE in thedata portion.A.2.  Serial Links Using DDCMP Devices     Following is a description of the frame format used on DEC DDCMP linkswith DMA interfaces such as the DEC DMV11 and DMR11.  These interfacesimplement the DEC DDCMP protocol, which includes error detection andretransmission capabilities.  The DDCMP frame format is as follows:+-------------+-----+-----+-----+-----+-----+------+------+------+| SYN SYN SOH |Count|Flag |Resp | Seq | Adr | CRC1 | Data | CRC2 |+-------------+-----+-----+-----+-----+-----+------+------+------+bits   24       14     2     8     8     8     16     ...16With respect to this diagram, each octet is transmitted starting from theleftmost octet, with the bits of each octet transmitted low-order bit first.The contents of all fields except the "Data" field are managed by theinterface.  The Internet datagram is placed in this field as-is, with nocharacter or bit stuffing (the extent of this field is indicated by theinterface in the "Count" field.A.3.  Serial Links Using HDLC Devices     Following is a description of the frame format used on HDLC links withprogram-interrupt interfaces such as the DEC DPV11.        +--------+--------+--------+--------+--------+--------+        |  Flag  |  Addr  |  Ctrl  |  Data  |  CRC   |  Flag  |        +--------+--------+--------+--------+--------+--------+coding   01111110 00000000 00000000 xxxxxxxx cccccccc 01111110

DCN Local-Network Protocols                                        Page 25D.L. MillsWith respect to this diagram, each octet is transmitted starting fromthe leftmost octet, with the bits of each octet transmitted low-orderbit first.  The code xxxxxxxx represents the data portion and ccccccccrepresents the checksum.  The bits between the "Flag" fields areencoded with a bit-stuffing convention in which a zero bit is stuffedfollowing a string of five one bits.  The "Addr" and "Ctrl" fields arenot used and the checksum is ignored.  The Internet datagram is placedin the "Data" field, which must be a multiple of eight bits in length.A.4.  ARPANET 1822 Links Using Local or Distant Host Interfaces     Following is a description of the frame format used with ARPANET1822 Local or Distant Host interfaces.These interfaces can be usedto connect a DCN host to an ARPANET IMP, Gateway or Port Expander orto connect two DCN hosts together.  When used to connect a DCN host toan ARPANET IMP, Gateway or Port Expander, a 96-bit 1822 leader isprepended ahead of the Internet datagram.  The coding of this leaderis as described in BBN Report 1822.  When used to connect two DCNhosts together, no leader is used and the frame contains only theInternet datagram.A.5.  ARPANET 1822 Links Using HDH Interfaces     Following is a description of the frame format used with ARPANET1822 HDH interfaces.These interfaces can be used to connect a DCNhost to an ARPANET IMP or Gateway or to connect two DCN hoststogether.  In either case, the frame format is as described inAppendix J of BBN Report 1822.A.6.  X.25 LAPB Links Using RSRE Interfaces     Following is a description of the frame format used on X.25 LAPBlinks with the Royal Signals and Radar Establishment interfaces.These interfaces implement the X.25 Link Access Protocol - Balanced(LAPB), also known as the frame-level protocol, using a frame formatsimilar to that described under A.3 above.  Internet datagrams areplaced in the data portion of I frames and encoded with thebit-stuffing procedure described in A.3.  There is no packet-levelformat used with these interfaces.A.7.  Ethernet Links     Following is a description of the frame format used on Ethernet links.        +-----------+-----------+------+------+-----+        | Dest Addr | Srce Addr | Type | Data | CRC |        +-----------+-----------+------+------+-----+bits          48          48       16     ...32With respect to this diagram, each field is transmitted starting fromthe leftmost field, with the bits of each field transmitted low-orderbit first.  The "Dest Addr" and "Srce Addr" contain 48-bit Ethernetaddresses, while the "Type" field contains the assigned value for IPdatagrams (0800 hex) or for

DCN Local-Network Protocols                                        Page 26D.L. MillsARP datagrams (0806 hex).  The Internet datagram is placed in the"Data" field and followed by the 32-bit checksum.  The AddressResolution Protocol (ARP) is used to establish the mapping betweenEthernet address and Internet addresses.