RFC 891

DCN Local-Network Protocols

📅 published December 1983, from ietf

Network Working Group, RFC 891, by D.L. Mills, December 1983 💖

DCN Local-Network Protocols ✨

Okay bestie, the RFC's own header says this is RFC 891 by D.L. Mills, dated December 1983. The part of the document I have doesn't list a category, or anything it obsoletes or updates, so I'm not going to guess 🙈

This RFC describes the protocol the DCN local networks use to keep connectivity, routing, and timekeeping info in check 🦋 It's written so designers and implementers of other networks can get something out of it too 💅

1. Introduction ✨

Okay so this doc explains the local-net architecture and protocols of the Distributed Computer Network (DCN) 🌈 It's a whole family of local nets built on Internet technology, and it runs on PDP11-based software called the Fuzzball 🧚 DCN local nets have been around for about three years, and now there are clones in the USA, UK, Norway, and West Germany 🌍 They usually have a bunch of PDP11 or LSI-11 Fuzzballs, and one of them gets elected as a gateway 👑 They often have other Internet-compatible hosts hanging out too 🫶

The DCN local-net protocols are built for connectivity, routing, and timekeeping across a bunch of randomly connected personal computers and service hosts 💜 The big design idea behind the Fuzzball is that every host gets full functionality ✨ That means one box can be a packet switch, a gateway, and a service host all at once. Iconic, honestly 💅 When a bunch of Fuzzballs are hooked up with a haphazard mix of serial, parallel, and contention-bus interfaces, they sort themselves into a network that routes by minimum delay 🔥

This document is about the local-net protocols the DCN uses to keep connectivity, routing, and timekeeping going. It's an extensive revision and expansion of Section 4.2 of [1] 🎀 It's split into two parts. The first part is an informal description of the architecture, plus some explanatory notes. The second part is a semi-formal spec of the entities and protocols that figure out connectivity, set up routing, and keep clocks in sync. It's meant to help people implement cohort systems 🌸 The link-level coding lives in the appendix 📎

2. Narrative Description ✨

The DCN architecture is made for local nets with up to 256 hosts and gateways, using the Internet Protocol (IP) and client protocols 🦋 It gives you adaptive routing and clock synchronization in an arbitrary topology, including point-to-point links and multipoint bus systems 🌈 It's meant for hooking personal computers up to each other, plus service machines, gateways, and other hosts in the Internet community 💖 It is not meant for big, complex networks, though, and it doesn't do the fancy routing and control algorithms of something like the ARPANET 🙈

Here's a quick rundown of the process and addressing structure in the DCN, which will help with what comes next 💅 A DCN physical host is a PDP11-compatible processor running a bunch of cooperating sequential processes. Each one gets a unique 8-bit identifier called its port ID 🧚 Every DCN physical host has one or more internet processes, and each of those supports a virtual host with its own unique 8-bit identifier called its host ID ✨

Each virtual host can handle multiple internet protocols and connections, and also has a virtual clock ⭐ Each physical host has a physical clock that can run at any arbitrary rate. It also has a 32-bit logical clock that ticks at 1000 Hz and is assumed to reset every day at 0000 hours UT 🕛 Not every physical host does the full 32-bit precision, so on those the logical clock might be a bit less precise 🫶

There's a one-to-one correspondence between Internet addresses and host IDs 💜 The host ID is made from a specified octet of the Internet address, plus a specified offset. The octet number and the offset are picked at configuration time, and they must be the same for all DCN hosts on the local net 🔥 For class-B and class-C nets, the fourth octet is normally used this way for routing inside the local net. For class-B nets, though, DCN hosts treat the third octet as part of the net number, so that octet can be used for routing between DCN local nets 🌸 For class-A nets, the third octet (the ARPANET logical-host field) is normally used for routing where it's needed 🦋

Each DCN physical host is identified by a host ID so it can detect loops in routing updates. Those updates work out the minimum-delay paths between the virtual hosts 🧚 By convention, the physical host ID is just the host ID of one of its virtual hosts 💅 A link to a neighbor net is linked to a special virtual host called a gateway, which gets its own unique host ID 👑

The links that connect the physical hosts to each other and to foreign nets can be laid out in arbitrary ways, as long as the net stays fully connected 🌈 If full connectivity gets lost because of a link or host fault, the virtual hosts in each surviving segment can keep working with each other. And once connectivity comes back, they can work with all of each other again 🎀

Datagram routing is decided entirely by internet address. There's no local leader like in the ARPANET 🙅‍♀️ Each physical host has two tables. The Host Table tells it which outgoing link to use to reach each other local-net host. The Net Table tells it which outgoing host (gateway) to use to reach each other net 💖 The Host Table holds estimates of roundtrip delay and logical-clock offset for every virtual host on the net, and it's indexed by host ID ✨ To work out those estimates, the delay and offset of each virtual host relative to the physical host it lives in are assumed to be zero. The one exception is a special virtual host tied to an NBS radio time-code receiver, where the offset gets computed relative to the broadcast time 📻

The Net Table has an entry for every neighbor net that might connect to the local net, plus some other nets that aren't neighbors 🌸 Each entry has the net number and the host ID of the local-net gateway to that net. Routing just looks up the net number in the Net Table, finds the gateway's host ID, and then pulls the port ID of the net-output process out of the Host Table 🧚 Other info goes into the Host and Net Tables too, as described below 💅

The delay and offset estimates get updated by HELLO messages swapped over the links between physical-host neighbors ⭐ HELLO messages go out frequently, but not so often that they noticeably hurt the link's throughput for normal data messages 🫶 A HELLO message carries a copy of the sender's delay and offset info from its Host Table, along with what's needed to work out the roundtrip delay and logical-clock offset of the receiver relative to the sender 💜

The routing algorithm is a lot like the one the ARPANET used to use (and some other places too) 🔥 The roundtrip (biased) delay estimate to a neighbor gets added to each delay estimate in its HELLO message, and that sum gets compared with the matching delay estimates in the Host Table. If the computed delay is less than what's already in the Host Table, routing to that virtual host gets updated to match 🌈 The detailed workings, including host up-down logic and loop suppression, get summarized in a later section 🎀

DCN local nets configure themselves for all hosts and neighbor nets. In other words, the routing algorithms will find minimum-delay paths between all hosts and gateways to neighbor nets 🦋 Timekeeping info can also be swapped with special HELLO messages between neighboring DCN local nets ⏰ For routing past neighbor nets, you can configure extra entries in the Net Tables as needed 🌸 And there's a special entry you can set in the Net Tables that names the host ID of the gateway to all nets not explicitly listed in the table 💖

For routing over the ARPANET and the nets it can reach, a chosen local-net host gets an IMP interface and is set up with a GGP/EGP Gateway process 🧚 That process keeps the local host's Net Table up to date, including ARPANET leaders, as part of GGP/EGP protocol exchanges with other ARPANET gateways 💅 GGP/EGP protocol exchanges might also happen with non-ARPANET gateways 🌈

The portable virtual-host structure in the DCN encourages a pretty loose take on addressing 🙈 To keep things clear, the term "host ID" only gets used for virtual hosts, and "host number" is used for the physical host, which is generically called the DCN host ✨

2.1. Net and Host Tables ✨

Every DCN host has two tables that control how Internet Protocol (IP) datagrams get routed: the Net Table and the Host Table 💜 The Net Table tells you the host ID of the gateway on the route to a foreign net. The Host Table tells you the link, from the DCN host's point of view, on the route to a virtual host 🦋 The Host Table is updated dynamically using updates made by periodic HELLO messages 🔥 The Net Table is fixed at configuration time on every DCN host, except the ones running a GGP/EGP Gateway process. On those, the Net Table gets updated as part of gateway operations 🌸 On top of that, operator commands can change entries in either table 👑

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

Okay so the "Net Name" field is a short RAD50 name for the net 🧚 The "Net" fields hold the class A/B/C net number 💖 The "Gateway ID" field has the host ID of the first gateway to the net, and the "Hops" field says how many hops it is to get there 🌈 The remaining fields are only used by the GGP/EGP Gateway process. The "Index" field holds an index into the routing matrix, and the "Gateway Leader" field holds the (byte-swapped) local-net leader for the gateway on a neighbor net 🫶

The Net Table has an indefinite number of entries, and it ends with a special entry where all the "Net" fields are set to zero ⭐ If the "Hops" field of that terminating entry is less than 255, then the "Gateway ID" in that entry gets used for all nets not in the table 🦋 If the "Hops" field is 255, then all nets not explicitly mentioned in the table

...and to everyone else, those hosts just appear unreachable, bestie 🙈 no cap, it's giving ghosted.

Okay so the Host Table format is shown in Figure 2 ✨

                    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, bestie 💖 The Name field holds a short (RAD50) name so people can reference it easily 🎀 The Port ID field has the port ID of the net-output process on the shortest path to this virtual host, and the Delay field has the measured roundtrip delay to it. The Offset field is the difference between the logical clock of this host and the logical clock of the local host ⏰ The Local Leader field holds info used to build the local leader of the outgoing packet, for those nets that need it 🧚 The Update Timestamp field is the logical clock value from the last time the entry got updated, and the TTL field is the time (in seconds) left until the virtual host is declared down 💀

All the fields except Name get filled in during the routing update process, which kicks off when a HELLO message shows up from a neighboring DCN host 🦋 This message is an IP datagram carrying the reserved protocol number 63, plus a data field that looks like Figure 3 👑

                    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, and which one you get depends on how long the message is 🫶 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 💅

Quick vibe check: all the word fields shown are byte-swapped compared to the ordinary PDP11 representation 🙈 The Checksum field holds a checksum covering the fields indicated. The Date and Time fields get filled in with the local date and time of origination. The Timestamp field is used when computing the roundtrip delay (see below) ⭐ The Offset field holds the offset of the block of Internet addresses used by the local net. The Delay Host n and Offset Host n fields are a copy of the matching entries in the Host Table as they existed at the time of origination 🌈 And the Hosts (n) field holds the number of entries in this table.

2.2. Roundtrip Delay Calculations

Every so often, each DCN physical host sends a HELLO message to its neighbor on each communication link they share 🔥 For each of these links, the sender keeps a set of state variables, including a copy of the source-address field from the last HELLO message it received.

When it builds a HELLO message, the sender sets the destination-address field to that state variable and the source-address field to its own address 💖 Then it fills in the Date and Time fields from its logical clock, and the Timestamp field from another state variable. Finally, it copies the Delay and Offset values from its Host Table into the message 🧚

A host that receives a HELLO message throws it away if the format is bad or the checksum fails 🗑️ If the message is valid, the host sets a link state variable to show that the link is up. Every time a HELLO message is transmitted, this state variable gets decremented. If it hits zero, the link is declared down 💀

Next, the host checks whether the source-address field matches the state variable holding the last address stored. If it doesn't match, the link has been switched to a new host, so the state variables get flushed and the link is forced into a recovery state 🦋 Then the host checks whether the destination-address field matches its own address. If it does, the message has looped around (which is only legal on a broadcast net), and the roundtrip delay information gets corrected. In that case, the host and net areas are ignored 🙈 If it doesn't match, the host and net areas of the message get processed to update the Host and Net Tables ✨

Here's how the roundtrip delay calculations go 💅 The link input/output processes assigned to each link keep an internal state variable that gets updated as each HELLO message is received and transmitted. When a HELLO message comes in, this variable takes the value of the Time field minus the current time-of-day. When the next HELLO message goes out, the value assigned to the Timestamp field is the low-order 16-bits of this variable plus the current time-of-day. This variable is forced to zero if either the link is down or the system logical clock has been reset since the last HELLO message was received 🌸

If a HELLO message comes in with a zero Timestamp field, there's 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 that field. For the highest accuracy, the calculation only happens if the length of the last transmitted HELLO message (in octets) matches the length of the received HELLO message 🎀

This technique is so clean, bestie 😭 It makes the calculation independent of the clock offsets and of the intervals between HELLO messages at either host. It also protects against errors that might happen because of lost HELLO messages, and it works even when a neighbor host simply forwards the HELLO message back to the originator without changing it. That last behavior is typical of ARPANET IMPs and gateways, as well as broadcast nets, and it relies on the loop-detection mechanism so the correct calculations can be made and spurious host updates can be avoided 👑

2.3. Host Updates

When a HELLO message arrives and results in a valid roundtrip delay calculation, a host update process runs 🌈 This adds the roundtrip delay to each of the Delay Host n entries in the HELLO message, one at a time, and compares each calculated delay to the Host Delay field of the matching Host Table entry. Then each entry gets updated according to these 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 the roundtrip delay as the calculated 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 replaces 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 with a specified value (currently 120) in seconds ⏰ If the calculated delay goes over a specified maximum interval (currently 30 seconds), the virtual host is declared down by setting the matching Delay field to the maximum, and the remaining fields get handled as before 💀 For delay calculations, any value below a specified minimum (currently 100 milliseconds) gets rounded up to that minimum ✨

The Offset field gets replaced during the update process too 🦋 When the HELLO message arrives, the value of the current logical clock is subtracted from the Time field, and that difference gets 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 matching Offset field of the HELLO message, and the sum replaces the Offset field of the Host Table. So the Offset field in the Host Table for a particular virtual host only gets replaced if that host is up and on the minimum-delay path to the DCN host 🌸

The whole point of the switching threshold in (2) and the minimum delay in the update process is to avoid pointless switching between links and transient loops, which can happen because of normal variations in propagation delays 🙈 The point of the TTL field test in (4) is to keep things consistent by purging all paths to a virtual host when that virtual host goes down 🫶

On top of the updates that happen as HELLO messages arrive, each virtual host in a DCN host also does a periodic update of its own Host Table entry 💅 The update procedure is identical to the one above, except the calculated delay and offset are taken as zero. At least one of the virtual hosts in a DCN host has to have the same host ID as the host number assigned to the DCN host itself, and all of them have to be assigned the same net number 👑 Other than that, there are no restrictions on the number or addresses of internet processes living in a single DCN host 🧚

Virtual hosts are truly portable, so they can migrate around the net if that ever becomes necessary 🌈 The host update protocols described here make sure the routing procedures always converge to the minimum-delay paths through operational links and DCN hosts ✨ On broadcast nets such as Ethernets, the procedures get modified a little, as described below. In that case, the HELLO messages are used to determine routing from the various Ethernet hosts to destinations off the cable, and also to provide time synchronization 🎀

2.4. Timeouts

The TTL field in every Host Table entry gets decremented once a second in normal operation 🔥 So if, after a host update, another update doesn't arrive within the interval corresponding to the value initialized in that field, the field decrements to zero, at which point the

okay so the virtual host gets declared down and its Host Table entry gets set like we said above 🫶. The 120-second interval we use right now gives every neighbor on every link at least four HELLO messages in that window, because the longest gap between HELLO messages is 30 seconds on the slowest link (1200 bps) 🐢. So if no HELLO messages get lost, the most links between any virtual host and any other is four. Four hops, bestie, that's it 💅

The TTL field starts at 120 seconds whenever an update happens and whenever the virtual host gets declared down 🕰️. While it counts down to zero after that declaration, any updates just get ignored 🙅‍♀️. This gives the bad news a decent amount of time to spread through the whole net, so every DCN host's Host Table can catch up with the fact. That's how routing loops get prevented, and it's giving protection 🛡️✨

The IP forwarding procedures say the time-to-live field in the IP header gets decremented once per second, or at each point where the datagram is forwarded, whichever happens first ⏳. The value we use right now is 30, so an IP datagram can only live in the net for that many seconds. That makes 30 seconds the longest delay allowed on any path between two virtual hosts 🧚. If that maximum delay gets exceeded while calculating the roundtrip delay for a Host Table entry, the matching virtual host gets declared down 💀

The gap between HELLO messages on any link depends on the data rate that link supports 📶. As a general rule, the interval is set to 16 times the expected roundtrip time for the longest packet that will be sent on that link 🌸. For 1200-bps asynchronous transmission with packets up to 256 octets, that works out to a maximum HELLO message interval of about 30 seconds 🍓

Roundtrip delay calculations are pretty chill about net traffic and congestion, but the numbers still wiggle around a bit because of coding (bit or character stuffing) and medium perturbations 🌈. To stop loops and pointless path changes, the routing mechanism has a minimum switching threshold (see above) 🎀. The interval for that threshold, and also the minimum delay on any path, is 100 milliseconds ⭐

3. Formal Specification ✨

3.1. Data Structures

3.1.1. Global Variables

ADDRESS This is a 32-bit bit-string temporary variable used to hold an Internet address 🌷

CLOCK-HID This is an eight-bit integer state variable used to hold the host ID of the local-net host that will be the master clock 👑. It gets set to the right value based on how the net is configured.

DATE This is a 16-bit bit-string state variable holding the date in RT-11 format 📅. Bits 0-4 hold the year, with zero meaning 1972. Bits 5-9 hold the day of the month, and bits 10-14 hold the month, starting at one for January.

DATE-VALID This is a one-bit state variable that tells you whether the local date and time are synchronized with the master clock 🕛. A value of one means the local clock is not synchronized with the master clock. It's set to one at the start and whenever the local time-of-day rolls over past midnight. It gets set to zero each time a valid date and time update arrives from the master clock.

DELAY This is a 16-bit integer temporary variable that holds the roundtrip delay in milliseconds to a host ⏱️

HID This is an eight-bit integer temporary variable holding the host ID of some host on the local net 🆔

There's a one-to-one match between the Internet addresses of local hosts and their HIDs 💕. The mapping is picked based on the octet number of the Internet address. For DCN hosts it's the fourth octet. For hosts directly connected to a class-A ARPANET IMP or gateway, it's the third octet (the logical-host field). The contents of that octet get added to ADDRESS-OFFSET to form the HID for that address.

HOLD This is an eight-bit counter state variable that says whether timestamps are valid 🚫. While HOLD is nonzero, timestamps should be considered invalid. When it's set to some nonzero value, the counter ticks down 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's one entry for each host on the local net 🗂️. Each entry has this format:

HOST-TABLE.DELAY This is a 16-bit field holding the computed roundtrip delay in milliseconds to host HID 🐌

HOST-TABLE.OFFSET This is a 16-bit field holding the computed signed offset in milliseconds that has to be added to the local apparent clock so it agrees with the apparent clock of host HID ✨

HOST-TABLE.PID This is an eight-bit field holding the PID of the net-output process that the routing algorithm picked to forward packets to host HID 🎯

HOST-TABLE.TTL This is an eight-bit field used as a time-to-live indicator ⏰. The HOST process decrements it once each second, and it's initialized to a chosen value when a HELLO message is received. The table starts with HOST-TABLE.DELAY set to MAXDELAY for all entries. The contents of the other fields don't matter.

LOCAL-ADDRESS This is a 32-bit bit-string state variable holding the local host's Internet address 🏠

NET-TABLE This is a table of NNETS entries with this format 🗺️

NET-TABLE.HID This is an eight-bit field holding the host ID of the pseudo-process used to forward packets to the NET-TABLE.NET net.

NET-TABLE.NET This is a 24-bit field holding an Internet class-A (eight bits), class-B (16 bits) or class-C (24 bits) net number 💫. Heads up: the real field width for class-B net numbers is 24 bits, so that subnet capability works. The high-order eight bits of the 16-bit host address are read as the subnet number.

The table gets built at configuration time and has to include an entry for every net that could be a neighbor 🤝. A neighbor net is a net containing a host that can connect directly to a host on the local net. Each entry for one of those nets starts with NET-TABLE.NET set to the neighbor net number, and NET-TABLE.HID set to an arbitrary vitual-host ID that no other local-net virtual host is using.

The remaining entries in NET-TABLE get set at initial boot time. Their NET-TABLE.NET fields are set to zero, and their NET-TABLE.HID fields are set to a configuration-selected host ID that forwards packets to all nets other than neighbor nets 🚀. If a gateway module is included in the local host configuration, the GGP and/or EGP protocols maintain these entries. If no gateway module is included, only one such entry is needed.

OFFSET This is a 16-bit signed integer temporary variable holding the offset in milliseconds that gets added to the apparent clock time to get the apparent clock time of the neighbor host 🌙

3.1.2. Parameters

ADDRESS-OFFSET This is an integer holding the value of the Internet address field that matches the first host in HOST-TABLE 🔢

NHOSTS This is an integer that defines how many entries are in HOST-TABLE 📋

NNETS This is an integer that defines how many entries are in MET-TABLE 🎀

3.1.3. HELLO Packet Fields

PKT.ADDRESS-OFFSET This eight-bit field gets copied from ADDRESS-OFFSET by the sender 💌

PKT.DATESTAMP Bits 0-14 of this 16-bit field get copied from DATE by the sender, and bit 15 gets 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. The sender copies it from HLO.NEIGHBOR-ADDRESS 📮

PKT.HOST-TABLE This is a table of PKT.NHOSTS entries, and each entry has two fields. The entries are indexed by host ID and have this format 🧩

PKT.HOST-TABLE.DELAY This 16-bit field gets copied from the matching HOST-TABLE.DELAY field by the sender ⏱️

PKT.HOST-TABLE.OFFSET This 16-bit field gets copied from the matching HOST-TABLE.OFFSET field by the sender ✨

PKT.LENGTH This 16-bit field is part of the IP header. The sender sets it to the number of octets in the packet 📏

PKT.NHOSTS This eight-bit field gets copied from NHOST by the sender 🔁

PKT.SOURCE This 16-bit field is part of the IP header. The sender copies it from LOCAL-ADDRESS 📍

PKT.TIMESTAMP This 32-bit field holds the apparent time the packet was transmitted, in milliseconds past midnight UT ⏳

PKT.TSP This 16-bit field holds a variable used in roundtrip delay calculations 🧮

3.2 CLOCK Process (CLK)

The timekeeping system keeps track of three clocks 🕰️: (1) the physical clock, which a hardware oscillator/counter determines; (2) the apparent clock, which keeps the time-of-day that client processes use; and (3) the actual clock, which holds the time-of-day from an outside reference. The apparent and actual clocks are kept as 48-bit quantities, and 32 bits of significance are available to client processes. These clocks run at 1000 Hz and get reset at midnight UT 🌟

The CLOCK process is a set of state variables plus a set of procedures. Those procedures get called when hardware interrupts happen or when client requests come in 📞. An interval timer is assumed to be logically separate from the local clock mechanism, even though both could come from the same timing source.

3.2.1. Local Variables

CLK.CLOCK This is a 48-bit fixed-point state variable used to represent the apparent time-of-day 🕐. The decimal point sits to the right of bit 16 (numbering from the right, starting at bit 0). Bit 16 increments at a rate equivalent to 1000 Hz, independent of the hardware clock. (With 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 a simple line clock, which causes interrupts at the line-frequency rate, or a programmable clock, which has a 16-bit register programmed to count at a 1000-Hz rate and causes an interrupt on overflow. The register is treated as a fixed-point variable with the decimal point to the right of bit 0.

CLK.DELTA 💖 okay so this one is a 48-bit signed fixed-point state variable (very precise, bestie 🤓) that stores the increment you add to CLK.CLOCK to get the actual time-of-day. The decimal point sits to the right of bit 16 🧚

3.2.3. Parameters 🎀

ADJUST-FRACTION This is an integer that sets the shift count used to compute a fraction. That fraction is a multiplier for CLK.DELTA, used to correct CLK.CLOCK once each clock-adjust interval. A value of seven is suggested ✨

ADJUST-INTERVAL This is an integer that sets 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 that sets the increment in milliseconds added to CLK.CLOCK on each clock tick. The decimal point is to the right of bit 16 🍓 For a line-clock interrupt, the value of CLOCK-TICK SHOULD be 16.66666 (60 Hz) or 20.00000 (50 Hz). For a 1000-Hz programmable-clock overflow, the value SHOULD be 65536.00000 💅

HOLD-INTERVAL This is an integer that sets how many seconds HOLD counts 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 Procedures 🦋

INCREMENT-CLOCK Event This event is evoked as the result of a tick interrupt (line clock) or a counter overflow (1000-Hz clock). It makes the logical clock go up 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 over to the actual clock time that SET-CLOCK set 🌸 It does this by subtracting a fraction of the correction factor CLK.DELTA from CLK.DELTA, and adding that same fraction to CLK.CLOCK. It keeps going until either the next SET-CLOCK call comes in or CLK.DELTA has been reduced to zero 🧚

The suggested values for ADJUST-INTERVAL and ADJUST-FRACTION give a maximum slew rate of less than +-2 milliseconds per second for the 1000-Hz clock. The whole point is to smooth out noisy clock corrections from neighboring systems so you get 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 save the result in a temporary variable F. Treat the decimal point of F as sitting to the right of bit 16, sign-extend as necessary, then subtract F from CLK.DELTA and add F to CLK.CLOCK ✨

DECREMENT-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 A client process calls this procedure, and it returns the apparent time-of-day. That's the integer part of CLK.CLOCK plus CLK.COUNT 💖 Heads up: the precision of the returned value is limited to +-1 millisecond, so client processes MUST expect the apparent time to "run backward" every now and then because of drift corrections 😭 When that happens, the backward step is never bigger than one millisecond and never happens more than twice per second 🙈

  1. For line clocks, CLK.COUNT is always zero. For programmable clocks, the hardware MUST be interrogated to pull out the value of CLK.COUNT. If a counter-overflow condition shows up after that interrogation, add CLOCK-TICK to CLK.CLOCK and interrogate the hardware again 🎀
  2. Once CLK.COUNT has been determined, compute the sum CLK.COUNT + CLK.CLOCK. If that sum is bigger than the number of milliseconds in 24 hours (86,400,000), then reduce CLK.CLOCK by 86,400,000, set HOLD-INTERVAL -> HOLD, set CLOCK-VALID (bit 15 of DATE) to one, roll DATE over 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 gets set so a master-clock update is received at least once per day. Also note that uncompensated crystal oscillators, the kind commonly used as the 1000-Hz time base, can be expected to drift by several parts per million. Without correction, that works out to a time drift of several tenths of a second per day 💀

SET-CLOCK Procedure A client process calls this procedure to set a time-of-day correction factor in milliseconds 🍓 The argument is a 32-bit signed fixed-point quantity with the decimal point to the right of bit 0. It gets added to CLK.CLOCK so that READ-CLOCK returns the actual time-of-day from then on 🦋

  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 ADJUST-FRACTION), the value of the argument replaces CLK.DELTA and the procedure is done 💅 If not, add the value of the sign-extended argument to CLK.CLOCK and set CLK.DELTA to zero. On top of that, set HOLD-INTERVAL -> HOLD, since this is a relatively large step-change in apparent time 🔥 The value of HOLD is the number of seconds left in which timestamps SHOULD be considered invalid. The HELLO process uses it to stop roundtrip delay calculations that might involve invalid timestamps 🙈

3.3. HELLO Process 🧚

The HELLO process keeps clock synchronization going with a neighbor HELLO process, using the HELLO protocol 🫶 It also takes part in the routing algorithm ✨ There's one HELLO process, and one set of local state variables, for each link connecting the host to one of its neighbors 💖

3.3.1. Local variables 🎀

HLO.BROADCAST This is a one-bit switch state variable. When it's set to zero, a point-to-point link is assumed. When it's set to one, a broadcast (e.g. Ethernet) link is assumed 🌸

HLO.KEEP-ALIVE This is an eight-bit counter state variable that shows whether the link is up. It starts out with a value of zero 🦋

HLO.LENGTH This is a 16-bit integer state variable that records the length in octets of the last HELLO message sent 🍓

HLO.NEIGHBOR-ADDRESS This is a 32-bit integer state variable that holds the neighbor host Internet address 🌈

HLO.PID This is an eight-bit integer state variable that identifies the net-output process linked to this HELLO process. The kernel sets it when the process is created, and it stays the same after that 👑

HLO.POLL This is a one-bit switch state variable. When it's set, the HELLO process spontaneously sends HELLO messages. When it's not set, the HELLO process responds to HELLO messages but doesn't send them spontaneously 💅

HLO.TIMESTAMP This is a 32-bit integer temporary variable that records the time a HELLO message arrived ⏰

HLO.TSP This is a 16-bit signed integer state variable used in roundtrip delay calculations 🧚

3.3.2. Parameters ✨

HELLO-INTERVAL This is an integer that sets the interval in seconds between HELLO messages. It ranges from about eight up to a maximum of 30 seconds, depending on line speed 🚀

HOLD-DOWN-INTERVAL This is an integer that sets the interval in seconds for which a host is considered up after it receives a HELLO message saying that host is up. A value of 120 is suggested 🌸

KEEP-ALIVE-INTERVAL This is an integer that sets the interval, in units of HELLO-INTERVAL, over which a HELLO process considers the link up. A value of four is suggested 💖

MAXDELAY This is an integer that sets the maximum roundtrip delay in seconds on a path to any reachable host. A value of 30 is suggested 🎀

MINDELAY This is an integer that sets the minimum switching threshold in milliseconds. Routes won't be changed below this threshold. A value of 100 is suggested 🫶

3.3.3. Events and Procedures 🦋

okay so when a packet lands 📦 the net-input process goes first and sets HLO.TIMESTAMP to whatever the READ-CLOCK procedure hands back 🕰️. Then it checks the packet for valid local leader, IP header format and checksum 🔍. If the protocol field in the IP header says it's a HELLO message, the packet gets passed to the HELLO process 💌. If any errors show up, the packet is dropped 🗑️ bye bye!

The HELLO process gets the first real look 👀. It checks the packet for valid HELLO header format and checksum, and if anything's off, the packet is dropped. Otherwise, it does the following:

  1. Looped line check 🔁 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. Keep-alive setup 💖 Set KEEP-ALIVE-INTERVAL -> HLO.KEEP-ALIVE. This indicates the maximum number of HELLO intervals the HLO.TSP field is considered valid.
  3. Delay math 🧮 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. New neighbor drama 🎭 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. Validation and PID check ✅ 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. Same net check 🏠 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.
    • 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. Is this a longer path? 🛣️ 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. Up or down? ⬆️⬇️ 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. Update the table 📝 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.
  4. Offset and clock vibes 🕰️ 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. Tick down ⏱️ If HLO.KEEP-ALIVE is nonzero, decrement its value.
  2. Should we send? 🤔 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. Same net or not? 🌐 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. Send it! 🚀 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 per second to scan HOST-TABLE and decrement the HOST-TABLE.TTL field of each entry. It also performs housekeeping functions 🧹

3.4.1. Local variables

HOS.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 Procedures

SCAN Event 🔍

This event is evoked once each second to scan the HOST-TABLE and perform housekeeping functions.

  1. Refresh the local entries 🌷 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. References 📚

  1. Mills, D.L. Final Report on Internet Research, ARPA Packet Switching Program. Technical Report TSLAB 82-7, COMSAT Laboratories, December 1982.

Following is a description of the frame format used on asynchronous and synchronous serial links with program-interrupt interfaces, such as the DEC DLV11 and DPV11. This format provides transparency coding for all messages, including HELLO messages, but does not provide error detection or retransmission functions. It is designed to be easily implemented and compatible as far as possible with standard industry protocols 🧃

The protocol is serial-by-bit, with the same interpretation on the order of transmission as standard asynchronous and synchronous interface devices; that is, the low-order bit of each octet is transmitted first. The data portion of the frame consists of one Internet datagram encoded according to a "character-stuffing" transparency convention:

  1. Okay so the frame kicks off with DLE-STX (two octets) on async links, or SYN-SYN-DLE-STX (four octets) on sync links 💖. Then comes the data portion, encoded as described below, and the whole thing wraps up with DLE-ETX (two octets) 🎀. No checksum gets sent or expected, so don't go looking for one 💅. If time-fill is ever needed somewhere other than the data portion, use DEL (all ones) 🫶.
  2. Inside the data portion, the transmit buffer gets scanned for DLE. Every DLE found gets sent as DLE-DLE ✨. If the transmitter has to sneak in time-fill inside the data portion for some reason, it uses DLE-DEL 🌸.
  3. When the receiver is scanning and finds DLE-DLE, it drops a single DLE into the receive buffer 🧚. If it finds DLE-ETX, the buffer gets passed on for processing 👑. DLE-DEL gets tossed 🙈. Any other two-octet sequence that starts with DLE and ends with something other than DLE, ETX or DEL counts as a protocol error (see note below) 💀.

Note: In the case of synchronous links using program-interrupt interfaces such as the DPV11, for example, a slightly modified protocol is suggested when both ends of the link agree 🤝. These interfaces usually have a parameter register that can be loaded with one code, which is used both to spot the receiver's synchronizing pattern and for time-fill when the transmit buffer register can't be serviced in time for the next character ⏱️.

The parameter register must be loaded with the SYN code for this protocol to work properly 🧠. Still, if time-fill is needed, a single SYN gets sent instead of the DLE-DEL sequence from above 🫧. To keep the hiccups from these moments to a minimum, follow these rules:

  1. If the transmitter senses a time-fill condition (usually through a control bit set aside for this) between frames, or right after sending a DLE, just ignore it 🙃.
  2. If the transmitter senses a time-fill condition at any other time, it sends the sequence DLE-CAN 🚫.
  3. If the receiver finds a SYN either between frames or right after a DLE, it discards the SYN without messing up the sequence decoding 🧹.
  4. If the receiver finds the sequence DLE-CAN in the data portion, it throws out that sequence and the octet right before it 🗑️.

These rules work when a single SYN has been inserted by the transmitter, and even when a SYN has been slipped into the DLE-CAN sequence 🦋. If the receiver senses an overrun (lost data) condition, the right move is to go back to the initial-synchronization state 🔄. That's also the move if any code other than STX shows up after the initial DLE, or if any code other than DLE, ETX, DEL or CAN shows up after a DLE in the data portion 😭.

Here's the frame format used on DEC DDCMP links with DMA interfaces, like the DEC DMV11 and DMR11 🎀. These interfaces implement the DEC DDCMP protocol, which comes with error detection and retransmission capabilities, so it's giving reliability 💪. The DDCMP frame format looks like this:

+-------------+-----+-----+-----+-----+-----+------+------+------+
| SYN SYN SOH |Count|Flag |Resp | Seq | Adr | CRC1 | Data | CRC2 |
+-------------+-----+-----+-----+-----+-----+------+------+------+
bits   24       14     2     8     8     8     16     ...    16

Reading this diagram, each octet gets transmitted starting from the leftmost octet, with the bits of each octet sent low-order bit first 🌈. The interface manages the contents of every field except the "Data" field 🛠️. The Internet datagram goes into that "Data" field as-is, with no character or bit stuffing, and the interface tells you how long the field is through the "Count" field (the extent of this field is indicated by the interface in the "Count" field. 💅

Here's the frame format used on HDLC links with program-interrupt interfaces, like the DEC DPV11 🌸.

    +--------+--------+--------+--------+--------+--------+
    |  Flag  |  Addr  |  Ctrl  |  Data  |  CRC   |  Flag  |
    +--------+--------+--------+--------+--------+--------+
coding   01111110 00000000 00000000 xxxxxxxx cccccccc 01111110

Same deal as before: each octet goes out starting from the leftmost one, with the bits sent low-order bit first ✨. The code xxxxxxxx stands for the data portion, and cccccccc stands for the checksum 🧩. The bits between the "Flag" fields use bit-stuffing, where a zero bit gets stuffed after a run of five one bits 0️⃣. The "Addr" and "Ctrl" fields aren't used, and the checksum gets ignored 🙈. The Internet datagram goes in the "Data" field, which must be a multiple of eight bits in length 💜.

Here's the frame format used with ARPANET 1822 Local or Distant Host interfaces 🚀. These can connect a DCN host to an ARPANET IMP, Gateway or Port Expander, or they can connect two DCN hosts together 🫶. When you hook a DCN host up to an IMP, Gateway or Port Expander, a 96-bit 1822 leader gets prepended ahead of the Internet datagram 📦. The coding for that leader is in BBN Report 1822 🧾. When two DCN hosts are linked directly, there's no leader at all, and the frame just holds the Internet datagram 💖.

Here's the frame format used with ARPANET 1822 HDH interfaces 🍓. These can connect a DCN host to an ARPANET IMP or Gateway, or connect two DCN hosts together 🤝. Either way, the frame format is exactly as described in Appendix J of BBN Report 1822 📚.

Here's the frame format used on X.25 LAPB links with the Royal Signals and Radar Establishment interfaces 📡. These interfaces implement the X.25 Link Access Protocol - Balanced (LAPB), which is also called the frame-level protocol 🧠. It uses a frame format that's similar to the one in A.3 above 🔁. Internet datagrams go in the data portion of I frames and get encoded with the bit-stuffing procedure from A.3 🫧. There's no packet-level format with these interfaces, so no extra layer to worry about 🙌.

Here's the frame format used on Ethernet links 🌐.

    +-----------+-----------+------+------+-----+
    | Dest Addr | Srce Addr | Type | Data | CRC |
    +-----------+-----------+------+------+-----+
bits          48          48       16     ...   32

Reading this diagram, each field gets transmitted starting from the leftmost field, with the bits of each field sent low-order bit first 🦋. "Dest Addr" and "Srce Addr" hold 48-bit Ethernet addresses 🪪. The "Type" field holds the assigned value for IP datagrams (0800 hex) or for ARP datagrams (0806 hex) 🔢. The Internet datagram goes in the "Data" field and is followed by the 32-bit checksum ✨. The Address Resolution Protocol (ARP) is what sets up the mapping between Ethernet addresses and Internet addresses, so it's the matchmaker of the whole setup 💕.

📦 where this page comes from