DCN Local-Network Protocols
also
- std-44
Extracted elements (29)
A minimum switching threshold of 100 milliseconds is used so routes are only changed when a new path is shorter by at least that margin. On very low-delay links this causes the routing algorithm to degenerate to min-hop rather than min-delay, suppressing transient loops from normal propagation-delay variations.
Clock corrections within ±128 milliseconds are applied by slewing (gradually adding a fraction of CLK.DELTA each ADJUST-INTERVAL) rather than stepping, ensuring the apparent clock is always monotonically increasing. Larger corrections are applied as immediate steps with HOLD set to suppress timestamp-based delay calculations during the unstable interval.
Routing is based on minimum roundtrip delay, similar to the algorithm formerly used in the ARPANET. Each neighbor's advertised delay to a host is added to the measured roundtrip delay to that neighbor; if the sum is less than the current Host Table entry by at least the switching threshold, the route is updated. This avoids a central routing authority.
The DCN design philosophy incorporates complete functionality in every host, which can serve simultaneously as a packet switch, gateway, and service host. When Fuzzballs are connected via arbitrary serial, parallel, and contention-bus interfaces, they self-organize into a minimum-delay-routed network without a central leader, contrasting with ARPANET's leader-based approach.
The DCN supports up to 256 hosts per local net using 8-bit host IDs. Subnet capability is provided for class-B nets by treating the third octet of the Internet address as a subnet number, and for class-A nets by using the third octet (ARPANET logical-host field) for routing between DCN local nets, enabling multi-net topologies without modifying the Internet address structure.
The HELLO interval is set to 16 times the expected roundtrip time for the longest packet on a given link. For 1200-bps asynchronous links with 256-octet packets this yields a maximum interval of ~30 seconds. The 120-second TTL ensures at least four HELLO messages from every neighbor before a host is declared down.
ARPANET IMPs and gateways, as well as broadcast nets, may forward a HELLO message back to its originator unchanged. The DCN HELLO process detects this loop condition (PKT.SOURCE equals LOCAL-ADDRESS) and handles it specially: on broadcast links it is allowed and roundtrip delay is set to zero; on point-to-point links it is treated as an error. This allows monitoring connectivity through foreign systems.
For routing beyond neighbor nets, additional static entries can be configured in the Net Table, including a wildcard default-gateway entry. For ARPANET routing, a selected local-net host runs a GGP/EGP Gateway process that dynamically maintains the Net Table as part of GGP/EGP protocol interactions with other gateways.
When connecting a DCN host to an ARPANET IMP, Gateway, or Port Expander via ARPANET 1822 Local or Distant Host interfaces, a 96-bit 1822 leader (per BBN Report 1822) must be prepended before the Internet datagram. When connecting two DCN hosts directly via 1822, no leader is used and the frame contains only the Internet datagram.
Clock offset in the Host Table is only updated when the length of the last transmitted HELLO packet equals the length of the received HELLO packet. This ensures the roundtrip delay computation—which depends on packet length matching for accurate propagation timing—is valid before updating time synchronization state.
HELLO messages are carried as IP datagrams using IP protocol number 63, which is described as a reserved protocol number for this purpose.
Loop suppression in OUTPUT-PACKET: when copying Host Table delay values into the outgoing HELLO message, if an entry's PORT-ID matches the current HELLO process's PID (indicating the best path back to the sender goes through this same link), MAXDELAY is substituted for the actual delay to prevent routing loops.
The Host Table TTL field is initialized to 120 seconds on each update and decremented once per second. When it reaches zero, the virtual host is declared down and a hold-down cycle begins by resetting TTL to HOLD-DOWN-INTERVAL (120 s) and setting Delay to MAXDELAY. Updates are ignored during the hold-down period to allow bad-news propagation and prevent routing loops.
The IP TTL field in forwarded datagrams is set to 30 seconds (decremented once per second or per hop). If the measured roundtrip delay to a host exceeds 30 seconds (MAXDELAY), that virtual host is declared down. This ensures datagrams cannot live in the net longer than the maximum path delay.
The Net Table must be terminated by a special entry with all Net fields set to zero. If this entry's Hops field is less than 255, its Gateway ID is used for all nets not explicitly listed. If Hops is 255, all unlisted nets appear unreachable.
Host IDs (HIDs) are 8-bit values derived from a specified octet of the Internet address (typically the fourth octet for class-B/C nets, the third for class-A) by subtracting ADDRESS-OFFSET. This one-to-one mapping between Internet addresses and HIDs enables indexed Host Table lookup without additional address resolution.
Roundtrip delay is computed using a timestamp echo mechanism: when a HELLO is received, the receiver stores (PKT.Time - current_time) in state variable HLO.TSP; on the next outgoing HELLO, PKT.TSP is set to (HLO.TSP + current_time). The sender receiving its own timestamp computes delay as (current_time - PKT.TSP). This technique is independent of clock offsets between hosts and tolerates lost HELLO messages.
The HOLD counter suppresses roundtrip delay calculations after a clock reset. It is set to HOLD-INTERVAL (at least as long as the maximum HELLO-INTERVAL of any HELLO process) and decremented at 1 Hz. While HOLD is nonzero, PKT.TSP is forced to zero on outgoing HELLO messages and delay computations from received packets are abandoned.
The HOST process (HOS) runs once per second to decrement HOST-TABLE.TTL for every entry. When TTL reaches zero and Delay is less than MAXDELAY (host was up), it initiates a hold-down cycle by setting Delay to MAXDELAY and TTL to HOLD-DOWN-INTERVAL. It also periodically calls UPDATE for the local host's own entries with zero delay and offset to keep self-routing current.
The Host Table has one entry per virtual host indexed by host ID, containing: Name (RAD50), Port ID (net-output process for shortest path), Delay (roundtrip in ms), Offset (logical clock difference in ms), Local Leader (outgoing packet construction), Update Timestamp, and TTL (seconds until host declared down). All fields except Name are updated by the HELLO routing process.
The Net Table contains one entry per reachable or neighbor net, including fields for Net Name (RAD50), Net number (class A/B/C), Gateway ID (host ID of first gateway), Hops, Index (GGP/EGP routing matrix), and Gateway Leader. The table is terminated by an entry with all Net fields zero; if its Hops field is less than 255, its Gateway ID serves as the default gateway for all unlisted nets.
The timekeeping system maintains three clocks: a physical clock (hardware oscillator), an apparent clock (CLK.CLOCK, 48-bit fixed-point running at 1000 Hz, reset at midnight UT), and an actual clock (the time provided by an outside reference). CLK.DELTA is a 48-bit correction factor slewed into CLK.CLOCK by the ADJUST-CLOCK event.
Host Table entries are updated by four rules upon receipt of a valid HELLO: (1) update if the link's PID matches the entry's Port ID; (2) update if the calculated delay is less than the stored delay by at least MINDELAY (100 ms switching threshold); (3) for foreign-net links, update only the gateway entry using roundtrip delay directly; (4) do nothing if none of the above apply or if the host is in hold-down (TTL nonzero after going down).
The HELLO INPUT-PACKET event processes incoming HELLO messages: (1) discard if looped on non-broadcast link; (2) set KEEP-ALIVE; (3) compute raw delay/offset via timestamp echo; (4) detect new neighbor and force hold-down; (5) if PKT.NHOSTS is zero (neighbor on different net), call ROUTE then UPDATE; if nonzero, iterate over all host entries adding neighbor delay/offset and call UPDATE for each.
DDCMP links (DEC DMV11/DMR11) use the DDCMP frame: SYN SYN SOH (24 bits) | Count (14 bits) | Flag (2 bits) | Resp (8 bits) | Seq (8 bits) | Adr (8 bits) | CRC1 (16 bits) | Data | CRC2 (16 bits). The Internet datagram is placed in the Data field as-is with no stuffing; error detection and retransmission are handled by the DDCMP interface hardware.
Ethernet links use the frame: Dest Addr (48 bits) | Srce Addr (48 bits) | Type (16 bits) | Data | CRC (32 bits). The Type field is 0x0800 for IP datagrams or 0x0806 for ARP datagrams. ARP is used to map between Ethernet and Internet addresses. The Internet datagram is placed in the Data field.
HDLC links use the frame: Flag (01111110) | Addr (00000000) | Ctrl (00000000) | Data | CRC | Flag (01111110). Bits are transmitted low-order first per octet. Zero-bit stuffing is applied (a 0 is inserted after five consecutive 1 bits). Addr and Ctrl fields are unused and the checksum is ignored; the Internet datagram is placed in the Data field.
Serial links with program-interrupt interfaces use character-stuffing framing: async links begin with DLE-STX and end with DLE-ETX; sync links prefix SYN-SYN before the DLE-STX. Within the data portion, each DLE byte is escaped as DLE-DLE. Time-fill uses DEL between frames or DLE-DEL within data. No checksum is transmitted.
The HELLO message is carried as an IP datagram using reserved protocol number 63. It has a fixed area (Checksum, Date 16-bit, Time 32-bit, Timestamp 16-bit, Offset 8-bit, Hosts-count 8-bit) followed by a host area (pairs of 16-bit Delay and 16-bit Offset for each Host Table entry). All word fields are byte-swapped relative to standard PDP11 representation. Only intra-net HELLO messages include the host area.