RFC 823

DARPA Internet gateway

📅 published September 1982, from ietf

📜 RFC 823: THE DARPA INTERNET GATEWAY 🌸

okay bestie, let's get into it ✨ this one is an RFC, which is the Internet's official spec drama, and it's written by Robert Hinden and Alan Sheltzer from Bolt Beranek and Newman Inc. 🎀 (that's BBN, in Cambridge, Massachusetts). It was prepared for the Defense Advanced Research Projects Agency, aka DARPA 🫶, and it's dated September 1982 🍓

The main tea ☕ is that this RFC obsoletes IEN-30 and IEN-109 💀, so those older documents are officially replaced. It doesn't update anything else. This is a status report that describes the Internet Gateway as it was in September 1982 🦋 It has detailed message formats and gateway procedures, BUT it's not an implementation specification, so those details can still change 🙈

Status of This Memo 💜

This memo is a status report on the Internet Gateway that BBN built. It describes the gateway as of September 1982. It has detailed descriptions of message formats and gateway procedures, however it is not an implementation specification, and those details are subject to change.

Table of Contents 🧚

     1   INTRODUCTION.......................................... 1
     2   BACKGROUND............................................ 2
     3   FORWARDING INTERNET DATAGRAMS......................... 5
     3.1   Input............................................... 5
     3.2   IP Header Checks.................................... 6
     3.3   Routing............................................. 7
     3.4   Redirects........................................... 9
     3.5   Fragmentation....................................... 9
     3.6   Header Rebuild..................................... 10
     3.7   Output............................................. 10
     4   PROTOCOLS SUPPORTED BY THE GATEWAY................... 12
     4.1   Cross-Net Debugging Protocol....................... 12
     4.2   Host Monitoring Protocol........................... 12
     4.3   ICMP............................................... 14
     4.4   Gateway-to-Gateway Protocol........................ 14
     4.4.1   Determining Connectivity to Networks............. 14
     4.4.2   Determining Connectivity to Neighbors............ 16
     4.4.3   Exchanging Routing Information................... 17
     4.4.4   Computing Routes................................. 19
     4.4.5   Non-Routing Gateways............................. 22
     4.4.6   Adding New Neighbors and Networks................ 23
     4.5   Exterior Gateway Protocol.......................... 24
     5   GATEWAY SOFTWARE..................................... 26
     5.1   Software Structure................................. 26
     5.1.1   Device Drivers................................... 27
     5.1.2   Network Software................................. 27
     5.1.3   Shared Gateway Software.......................... 29
     5.2   Gateway Processes.................................. 29
     5.2.1   Network Processes................................ 29
     5.2.2   GGP Process...................................... 30
     5.2.3   HMP Process...................................... 31
     APPENDIX A. GGP Message Formats.......................... 32
     APPENDIX B. Information Maintained by Gateways........... 39
     APPENDIX C. GGP Events and Responses..................... 41
     REFERENCES............................................... 43

1. INTRODUCTION ✨

okay so this section is the setup 💅 It explains the design of the Internet gateway used in the DARPA Internet program. The gateway design was first written up in IEN-30, "Gateway Routing: An Implementation Specification" [2], and then updated in IEN-109, "How to Build a Gateway" [3]. This document reflects changes made to both the internet protocols and the gateway design since those documents came out, and it supersedes both IEN-30 and IEN-109 🎀

Credit where it's due 🫶 The gateway is based on the work of a lot of people, and special shoutouts go to V. Strazisar, M. Brescia, E. Rosen, and J. Haverty 🌈

The gateway's main job is to route internet datagrams to their destination networks ✨ Those datagrams are generated and processed the way RFC 791, "Internet Protocol - DARPA Internet Program Protocol Specification" [1] describes 💜 This doc covers how the gateway forwards datagrams, the routing algorithm and protocol it uses to route them, and the software structure of the current gateway. The current gateway is written in macro-11 assembly language and runs on the DEC PDP-11 or LSI-11 16-bit processor 👑 very retro, very iconic 💀

2. BACKGROUND 🦋

the gateway system has been through a bunch of changes since it started, and it's still evolving as research goes on in the Internet community 🌸 This document describes the implementation as of mid-1982.

The earliest gateway software was built using the BCPL language and the ELF operating system 🧚 Later it moved to the MOS operating system for better performance. Then in late 1981, the team started building a totally new gateway implementation 💖 The main reason was that they needed something built for an operational communications facility, not the research testbed environment that came with the BCPL version. Also, everyone agreed that the complexity and buffering needs of future gateway setups were way beyond what the PDP-11/LSI-11 and BCPL architecture could handle 😭 So the new version also had a second goal: be super space-efficient, which leaves room for buffers and for extra stuff like monitoring that an operational environment needs 🍓

This document describes that new gateway 💅 It has several mechanisms for operations work and is written in assembly language for maximum space-efficiency, but otherwise it's basically the same architecture as the older research-oriented versions 🎀

One result of recent research is the idea that gateways should be treated as elements of a gateway system, where the gateways act together as a loosely-coupled packet-switching communications system 🔥 For maintainability and operability, it's easiest to build a system like this in a homogeneous way, where all the gateways sit under a single authority and control, which is how other network implementations usually do it ✨

To make a system architecture that allows multiple sets of gateways, with each set under single control but all acting together as one composite Internet System, new protocols needed to be developed 🌈 Protocols like the "Exterior Gateway Protocol" will show up in later releases of the gateway implementation 🦋

The team also expects more changes to the gateway architecture and implementation to support new capabilities, like large numbers of networks, access control, and other requirements the Internet research community has proposed 💜 This document is a snapshot of the current implementation, not a specification 🫶

3. FORWARDING INTERNET DATAGRAMS 🌸

this section explains how the gateway forwards datagrams between networks 💅 A host that wants an IP datagram to reach a host on another network has to send the datagram to a gateway so it can be forwarded. Before the datagram goes into the network, the host attaches a local network header containing the address of the gateway 🧚

3.1. Input ✨

When a gateway gets a message, it checks the message's local network header for possible errors and does any actions required by the host-to-network protocol 🔥 That processing includes things like verifying the local network header checksum or generating a local network acknowledgment message. If the header says the message contains an Internet datagram, the datagram gets passed to the Internet header check routine. Every other message that doesn't pass these tests gets discarded 💀

3.2. IP Header Checks 🎀

The Internet header check routine runs a bunch of validity tests on the IP header 💖 Datagrams that fail these tests get discarded, which causes an HMP trap to be sent to the Internet Network Operations Center (INOC) [7] 😭 These checks are currently performed:

  • Proper IP Version Number
  • Valid IP Header Length ( >= 20 bytes)
  • Valid IP Message Length
  • Valid IP Header Checksum
  • Non-Zero Time to Live field

After a datagram passes those checks, its Internet destination address is examined to see if the datagram is addressed to the gateway 👑 Each of the gateway's internet addresses (one for each network interface) is checked against the destination address in the datagram. If there's no match, the datagram goes to the forwarding routine 🦋

If the datagram IS addressed to the gateway itself, the IP options in the IP header get processed 🌈 Right now, the gateway supports these IP options:

  • NOP
  • End of Option List
  • Loose Source and Record Route
  • Strict Source and Record Route

Next, the datagram gets processed according to the protocol in the IP header. If the gateway doesn't support that protocol, it replies with an ICMP error message and discards the datagram 💅 The gateway does not support IP reassembly, so fragmented datagrams that are addressed to the gateway get discarded 🙈

3.3. Routing 🍓

The gateway MUST make a routing decision for all datagrams that are to be forwarded 💜 The routing algorithm gives the gateway two pieces of info: 1) the network interface that should be used to send the datagram, and 2) the destination address that should go in the datagram's local network header 🫶

The gateway keeps a dynamic Routing Table with an entry for each reachable network 🧚 Each entry has a network number and either the address of the neighbor gateway on the shortest route to that network, or an indication that the gateway is directly connected to the network. A neighbor gateway is one that shares a common network with this gateway 🌸 The distance metric used to figure out which neighbor is closest is the "number of hops," where a gateway is

considered to be zero hops from its directly connected networks 🧚, one hop away from a network that's reachable through one other gateway 💅, and so on, bestie. 🌸 The Gateway-to-Gateway Protocol (GGP) is what keeps the Routing Table updated (see Section 4.4 for all the deets on GGP) 💖

The gateway tries to match the destination network address in the IP header of the datagram it's forwarding against a network in its Routing Table 👀. If there's no match, the gateway drops the datagram and sends an ICMP Destination Unreachable message back to the IP source 💀. If it does find an entry for the network, it uses the network address of the neighbor gateway entry as the local network destination address of the datagram 🎀. BUT, if the final destination network is one the gateway is directly connected to, the destination address in the local network header gets created from the destination address in the IP header of the datagram ✨.

3.4 Redirects

Okay, so if the routing procedure decides that an IP datagram has to go back out the same network interface it was read in on 🔄, that tells us this gateway is not on the shortest path to the IP final destination 🙈. Still, the datagram gets forwarded to the next address the routing procedure chose anyway 💁‍♀️. If the datagram is not using the IP Source Route Option, AND the IP source network of the datagram is the same as the network of the next gateway the routing procedure picked 😤, an ICMP Redirect message gets sent to the IP source host. That message tells the host that another gateway should be used to send traffic to the final IP destination 🦋.

3.5 Fragmentation

The datagram gets passed to the fragmentation routine after the routing decision has been made 📦. If the next network the datagram has to pass through has a maximum message size that's smaller than the datagram, the datagram must be fragmented 🧩. Fragmentation is done according to the algorithm described in the Internet Protocol Specification [1] 📖. Certain IP options must be copied into the IP header of all fragments, and others appear only in the first fragment, according to the IP specification 🫶. If a datagram must be fragmented but the Don't fragment bit is set, the datagram is discarded and an ICMP error message is sent to the IP source of the datagram 🚫.

3.6 Header Rebuild

Next, the datagram (or the fragments of the original datagram, if fragmentation was needed) gets passed to a routine that rebuilds the Internet header 🛠️. The Time to Live field is decremented by one, and the IP checksum is recomputed 🔢.

Now the local network header gets built 🏗️. Using the information from its routing procedure, the gateway chooses the network interface it considers proper to send the datagram out of, and builds the destination address in the local network header 🎯.

3.7 Output

The datagram is now enqueued on an output queue for delivery towards its destination 📬. There's a limit enforced on the size of the output queue for each network interface, so that a slow network doesn't unfairly use up all of the gateway's buffers 🐢🚫. If a datagram can't be enqueued because of the output queue length limit, it gets dropped and an HMP trap is sent to the INOC 🚨. These traps, and others of a similar nature, are used by operational personnel to monitor the operations of the gateways 👩‍💻✨.

4 PROTOCOLS SUPPORTED BY THE GATEWAY

A bunch of protocols are supported by the gateway for dynamic routing, monitoring, debugging, and error reporting 🌈. They're described below 👇.

4.1 Cross-Net Debugging Protocol

The Cross-Net Debugging Protocol (XNET) [8] is used to load the gateway and to examine and deposit data 🧰. The gateway supports the following XNET op-codes:

  • NOP
  • Debug
  • End Debug
  • Deposit
  • Examine
  • Create Process

4.2 Host Monitoring Protocol

The Host Monitoring Protocol (HMP) [6] is used to collect measurements and status information from the gateways 📊. Exceptional conditions in the gateways are reported in HMP traps 🚩. The status of a gateway's interfaces, neighbors, and the networks it can reach are reported in the HMP status message 🛰️.

Two types of gateway statistics, the Host Traffic Matrix and the gateway throughput, are currently defined by the HMP 🔥. The Host Traffic Matrix records the number of datagrams that pass through the gateway with a given IP source, destination, and protocol number 🗂️. The gateway throughput message collects a number of important counters kept by the gateway 🔢. The current gateway reports the following values:

  • Datagrams dropped because destination net unreachable
  • Datagrams dropped because destination host unreachable
  • Per Interface:
    • Datagrams received with IP errors
    • Datagrams received for this gateway
    • Datagrams received to be forwarded
    • Datagrams looped
    • Bytes received
    • Datagrams sent, originating at this gateway
    • Datagrams sent to destination hosts
    • Datagrams dropped due to flow control limitations
    • Datagrams dropped due to full queue
    • Bytes sent
  • Per Neighbor:
    • Routing updates sent to
    • Routing updates received from
    • Datagrams sent, originating here
    • Datagrams forwarded to
    • Datagrams dropped due to flow control limitations
    • Datagrams dropped due to full queue
    • Bytes sent

4.3 ICMP

The gateway will generate the following ICMP messages under appropriate circumstances, as defined by the ICMP specification [4] 🎀:

  • Echo Reply
  • Destination Unreachable
  • Source Quench
  • Redirect
  • Time Exceeded
  • Parameter Problem
  • Information Reply

4.4 Gateway-to-Gateway Protocol

The gateway uses the Gateway-to-Gateway Protocol (GGP) to determine connectivity to networks and neighbor gateways 🤝. It's also used in the implementation of a dynamic, shortest-path routing algorithm 🗺️. The current GGP message formats (for release 1003 of the gateway software) are presented in Appendix A 📑.

4.4.1 Determining Connectivity to Networks

When a gateway starts running, it assumes that all its neighbor gateways are "down" 😱, that it is disconnected from the networks it's attached to 🔌, and that the distance reported in routing updates from each neighbor to each network is "infinity" ♾️.

The gateway first figures out the state of its connectivity to the networks it's physically attached to 🔍. The gateway's connection to a network is declared up if it can send and receive internet datagrams on its interface to that network ✅. Note that the method the gateway uses to determine its connectivity to a network is network-dependent 🧠. In some networks, the host-to-network protocol determines whether or not datagrams can be sent and received on the host interface. In these networks, the gateway simply checks status information provided by the protocol to determine if it can communicate with the network 📶. In other networks, where the host-to-network protocols are less sophisticated, it may be necessary for the gateway to send datagrams to itself to determine if it can communicate with the network 🔁. In these networks, the gateways periodically poll the network using GGP network interface status messages [Appendix A] to determine if the network interface is operational 🩺.

The gateway has two rules relevant to computing distances to networks 📏: 1) if the gateway can send and receive traffic on its network interface, its distance to the network is zero; 2) if it cannot send and receive traffic on the interface, its distance to the network is "infinity." Note that if a gateway's network interface isn't working, it may still be able to send traffic to the network on an alternate route via one of its neighbor gateways 🛣️.

4.4.2 Determining Connectivity to Neighbors

The gateway determines connectivity to neighbors using a "K out of N" algorithm 🎲. Every 15 seconds, the gateway sends GGP Echo messages [Appendix A] to each of its neighbors ⏰. The neighbors respond by sending GGP echo replies. If there is no reply to K out of N (current values are K=3 and N=4) echo messages sent to a neighbor, the neighbor is declared down 📉. If a neighbor is down and J out of M (current values are J=2 and M=4) echo replies are received, the neighbor is declared to be up 📈. The values of J, K, M, N and the time interval are operational parameters which can be adjusted as required 🎛️.

4.4.3 Exchanging Routing Information

The gateway sends routing information in GGP Routing Update messages 📨. The gateway receives and transmits routing information reliably, using sequence-numbered messages and a retransmission and acknowledgment scheme as explained below 🔐. For each neighbor, the gateway remembers the Receive Sequence Number, R, that it received in the most recent routing update from that neighbor 🧾. This value is initialized with the sequence number in the first Routing Update received from a neighbor after that neighbor's status is set to "up" 🌱. On receipt of a routing update from a neighbor, the gateway subtracts the Receive Sequence Number, R, from the sequence number in the routing update, S. If this value (S-R) is greater than or equal to zero, then the gateway accepts the routing update, sends an acknowledgment (see Appendix A) to the neighbor containing the sequence number S, and replaces the Receive Sequence Number, R, with S ✅. If this value (S-R) is less than zero, the gateway rejects the routing update and sends a negative acknowledgment [Appendix A] to the neighbor with sequence number R 🙅‍♀️.

The gateway has a Send Sequence Number, N, for sending routing updates to all of its neighbors 📤. This sequence number can be initialized to any value 🎲. The Send Sequence Number is incremented each time a new routing update is created. On

So when a gateway gets an ack for a routing update, it subtracts the acknowledged number A from its Send Sequence Number N. If N-A isn't zero, then it's an old update getting acked 🫠. The gateway keeps re-sending the most recent routing update to whichever neighbor sent that ack. If N-A is zero, the update is officially acked ✅. Only the most recent update has to get acked. If a second update shows up before the first one is acked, only the second one has to be acked 💅

Negative acks are their own little drama 😤 If a gateway gets one, it subtracts the negatively acked number A from its Send Sequence Number N. If that result (N-A) is less than zero, the gateway swaps N for A+1 and re-sends the routing update to all of its neighbors. If (N-A) is greater than or equal to zero, it keeps re-sending the update using sequence number N. To keep sequence numbers correct at every gateway, routing updates must go to all neighbors whenever the Send Sequence Number changes, even if the routing info itself stayed the same 🔢✨

The gateway keeps re-sending routing updates on a timer until they're acked, and it also re-sends whenever its Send Sequence Number changes. It only sends routing updates to neighbors that are in the "up" state 🦋

4.4.4 Computing Routes

A routing update is basically a list of the networks you can reach through this gateway, plus the distance in "number of hops" to each one 🗺️ A gateway only includes a network in an update if it thinks it's as close as, or closer to, that network than the neighbor receiving the update. Networks can be internet class A, B, or C addresses 💖

Here's how a gateway processes incoming routing info 🧠 It keeps an N x K distance matrix, where N is the number of networks and K is the number of neighbor gateways. Each entry, dm(I,J), is the distance to network I from neighbor J, as reported in the most recent routing update from neighbor J. The gateway also has a vector showing the connectivity between itself and each neighbor gateway. Those values get worked out the way we talked about above (see Section 4.4.2, Determining Connectivity to Neighbors). The Jth entry of that vector, the connectivity between the gateway and the Jth neighbor, is written d(J) 🌸

When a gateway gets a routing update from the Jth neighbor, it copies that update into the matching row of the distance matrix, then updates its routes. It works out a minimum distance vector, which holds the smallest distance from the gateway to each network. The Ith entry of that vector, MinD(I), is:

MinD(I) = minimum over all neighbors of d(J) + dm(I,J)

Here d(J) is the distance between the gateway and the Jth neighbor, and dm(I,J) is the distance from the Jth neighbor to the Ith network. If the Ith network is attached to the gateway, and the gateway can send and receive traffic on that network interface (see Section 4.4.2), then the gateway sets the Ith entry of the minimum distance vector to zero 🎯

Using that minimum distance vector, the gateway builds a list of which neighbor gateways to send traffic through for each network. The entry for a given network holds one of the neighbors that's the minimum distance away from that network 🛣️

After updating its routes, the gateway works out the new routing updates to send to its neighbors. It only reports a network to a neighbor if it's as close to that network, or closer, than the neighbor is. For each network I, the update includes the network's address and the minimum distance to it, which is MinD(I) 📮

Last step: deciding whether to send updates at all 🤔 The gateway sends new updates to its neighbors only if every one of the following three conditions occurs:

  1. One of the gateway's interfaces changes state.
  2. One of the gateway's neighbor gateways changes state.
  3. The gateway receives a routing update from a neighbor that's different from the update it previously got from that same neighbor.

It only sends these updates to neighbors that are currently in the "up" state 💅

The gateway also asks for routing updates from neighbors that are in the "up" state but haven't sent it one yet. To ask, it sets the appropriate bit in the routing update it's sending (see [Appendix A]). And if a gateway gets a routing update from a neighbor with that request bit set, it sends that neighbor its most recent routing update 🙌

4.4.5 Non-Routing Gateways

A Non-routing Gateway (NRG) is a gateway that forwards internet traffic but doesn't implement the GGP routing algorithm 🚦 The networks behind a Non-routing Gateway are known ahead of time to Routing Gateways. There can be one or more of these networks, and they're all considered directly connected to the Non-routing Gateway 🧩 A Routing Gateway will forward a datagram to a Non-routing Gateway if the datagram is addressed to a network behind it. Routing Gateways don't currently send Redirects for Non-routing Gateways 🙈

Here's the tea 🍵 If there are both a Routing Gateway path and a Non-routing Gateway path, and they're the same number of hops from the destination network, a Routing Gateway will always pick the other Routing Gateway. The Non-routing Gateway path only gets used when the Routing Gateway path is down. Once the Routing Gateway path comes back up, it gets used again 🔁

4.4.6 Adding New Neighbors and Networks

Gateways dynamically add routing info about new neighbors and new networks to their tables 🌈 Each gateway keeps a list of neighbor gateway addresses. When a routing update comes in, the gateway searches that list for the Internet source address of the update message. If that source address isn't in the list, the gateway adds it and sets the neighbor's connectivity status to "down." Routing updates aren't accepted from neighbors until the GGP polling mechanism has determined that the neighbor is up 🕵️‍♀️

This way of adding new neighbors means that one gateway in each pair of neighbor gateways must have the neighbor's address configured in its tables. The newest gateway can be given a complete list of neighbors, so you don't have to re-configure the older gateways every time a new gateway gets installed 🎀

Gateways learn about new networks in a few steps 📚 Each gateway has a list of all the networks it currently keeps routing info for. When a routing update arrives and it contains info about a new network, the gateway adds that network to its list. Next, the gateway adds the new network to its distance matrix. The distance matrix is the matrix of distances (number of hops) to networks, as reported in routing updates from the neighbor gateways. The gateway sets the distance to every new network to "infinity," then computes new routes and new routing updates just like we outlined above ✨

4.5 Exterior Gateway Protocol

The Exterior Gateway Protocol (EGP) lets other gateways and gateway systems pass routing info to the DARPA Internet gateways 🌍 Thanks to EGP, the user can see all the networks and gateways as one total Internet system, even though the "exterior" gateways are disjoint and might use a routing algorithm that's different from, and not compatible with, the one used by the "interior" gateways 🫶 The important elements of EGP are:

  • Neighbor Acquisition: the procedure a gateway uses to request that it become a neighbor of another gateway. This is used when a gateway wants to become a neighbor of another so it can pass routing information. It includes the capability to accept or refuse the request.
  • Neighbor Up/Down: the procedure a gateway uses to decide whether another gateway is up or down.
  • Network Reachability Information: the facility used to pass routing and neighbor information between gateways.
  • Gateway Going Down: the ability of a gateway to tell other gateways that it's going down and no longer has any routes to any other networks. This lets a gateway go down in an orderly way without disrupting the rest of the Internet system 👋

A complete description of EGP can be found in IEN-209, the "Exterior Gateway Protocol" [10] 📖

5 GATEWAY SOFTWARE 💻

The DARPA Internet Gateway runs under the MOS operating system [9], which provides facilities for:

  • Multiple processes
  • Interprocess communication
  • Buffer management
  • Asynchronous input/output
  • Shareable real-time clock

There's a MOS process for each network the gateway is directly connected to. A data structure called a NETBLOCK holds the variables of interest for each network, plus pointers to local network routines. Network processes run common gateway code, while network-specific functions get dispatched to the routines the NETBLOCK points to. There are also processes for gateway functions that need their own timing, such as GGP and HMP 🧁

5.1 Software Structure

Conceptually, the gateway software can be divided into three parts: MOS Device Drivers, Network software, and Shared Gateway software 🌷

5.1.1 Device Drivers

Okay so the gateway has this whole set of routines for every kind of hardware interface 💅 Each device type gets its own routines for sending and receiving data, covering initialization, initiation, and interruption on both the transmit and receive sides 🔧. Here are the device types it supports:

a)  ACC LSI-11 1822
b)  DEC IMP11a 1822
c)  ACC LHDH 1822
d)  ACC VDH11E
e)  ACC VDH11C
f)  Proteon Ring Network
g)  RSRE HDLC
h)  Interlan Ethernet
i)  BBN Fibernet
j)  ACC XQ/CP X.25 **
k)  ACC XQ/CP HDH  **
** Planned, not yet supported. 🚧

5.1.2. Network Software

Okay, so every connected network gets a set of eight routines that handle its local network stuff 🌐 Here's what each one does, bestie:

Up.net    Perform  local  network  initialization  such   as
          flapping the 1822 ready line.

Sg.net    Handle specific  local  network  timing  functions
          such as timing out 1822 Destination Deads.

Rc.net    A message  has  been  received  from  the  network
          interface.  Check for any input errors.

Wc.net    A message has  been  transmitted  to  the  network
          interface.  Check for any output errors.

Rs.net    Set up a buffer (or buffers) to  receive  messages
          on the network interface.

Ws.net    Transmit a message to the network interface.

Hc.net    Check the local network  header  of  the  received
          message.    Perform  any  local  network  protocol
          tasks.

Hb.net    Rebuild the local network header.

There are network routines for these types of networks, and yes, the letters in the parentheses are the device drivers each one uses 🦋

o  Arpanet (a,b,c,k)
o  Satnet (d,e,k)
o  Proteon Ring Network (f)
o  Packet Radio Network (a,b,c)
o  Rsre HDLC Null Network (g)
o  Ethernet (h)
o  Fibernet (i)
o  Telenet X.25 (j) **
** Planned, not yet supported. 🚧

Note: the letters in parentheses point to the device drivers used for each type of network, as described in the previous section 🧚

5.1.3. Shared Gateway Software

The internet processing for a datagram is handled by one shared chunk of code that all the network processes use 🫶 This code can check the IP header, do IP fragmentation, calculate the IP checksum, forward a datagram, and run the routing, monitoring, and error reporting protocols. Main character code, honestly 👑

5.2. Gateway Processes

5.2.1. Network Processes

When the gateway starts up, each network process calls its local network initialization routine and its read start routine ✨ The read start routine sets up two buffers, each sized for the maximum network size, to receive datagrams. After that, the network process just waits for an input complete signal from the network device driver 👀

When a message comes in, the MOS Operating System signals the right network process with an input complete signal 💌 That process wakes up and runs the net read complete routine. Once the message is processed, it goes back to waiting for more input.

The net read complete routine is the major message processing loop in the gateway, and it's giving main character energy 🔥 When a message has been received, it does all of this, in order:

  • Call Local Network Read Complete Routine
  • Start more reads
  • Check local Network Header
  • Check Internet header
  • Check if datagram is for the gateway
  • Forward the datagram if necessary
  • Send ICMP error message if necessary

5.2.2. GGP Process

The GGP process periodically sends GGP echos to each of the gateway's neighbors to check neighbor connectivity 🏓 It also sends interface status messages addressed to itself to check network connectivity. Whenever needed, it sends out routing updates too 📮 The details of the algorithms the GGP process currently implements are in Section 4.4, Gateway-to-Gateway Protocol, and in Appendix C 📚

5.2.3. HMP Process

The HMP process handles timer-based gateway statistics collection and the periodic sending of traps 📊🌸

APPENDIX A. GGP Message Formats ✨

Heads up, bestie: the GGP protocol is going through big changes right now to add the Exterior Gateway Protocol facility 🚧 That's the thing that lets gateways in other systems swap routing information with the gateways described in this document 🌈

Each GGP message is an Internet header followed by one of the messages explained below 💜 The values in the Internet header for a GGP message are (in decimal):

Version                  4.

IHL                      Internet header length in 32-bit words.

Type of Service          0.

Total Length             Length of Internet header  and  data  in
                         octets.

ID, Flags,
Fragment Offset          0.

Time to Live             Time to live in seconds.  This field  is
                         decremented   at   least  once  by  each
                         machine that processes the datagram.

Protocol                 Gateway Protocol = 3.

Header Checksum          The 16 bit one's complement of the one's
                         complement  sum  of  all 16-bit words in
                         the header.  For computing the checksum,
                         the checksum field should be zero.

Source Address           The address of the  gateway's  interface
                         from which the message is sent.

Destination Address      The address of the gateway to which  the
                         message is sent.

ROUTING UPDATE

 0                   1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!Gateway Type   !  unused (0)   !                 ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!     Sequence Number           !                 ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!  need-update  !  n-distances  !                 ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!  distance 1   !   n1-dist     !                 ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!   net11       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;   bytes
!   net12       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ;   bytes
                                 .
                                 .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!   net1n1      !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; n1 nets at
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;   dist 1
                                 .                      ...
                                 .                  ; ndist groups
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                  ;    of nets
!  distance n   !   nn-dist     !                  ; 2 bytes
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!   netn1       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;   bytes
!   netn2       !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; 1, 2 or 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;   bytes
                            .
                            .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
!   netnnn      !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!  ; nn nets at
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+  ;  dist n

Here's the field breakdown for the routing update, and it's lowkey a lot but so worth it 🧠

Gateway Type             12 (decimal)

Sequence Number          The  16-bit  sequence  number  used   to
                         identify routing updates.

need-update              An 8-bit field.  This byte is set  to  1
                         if the source gateway requests a routing
                         update from the destination gateway, and
                         set to 0 if not.

n-distances              An   8-bit   field.    The   number   of
                         distance-groups reported in this update.
                         Each  distance-group   consists   of   a
                         distance  value  and  a  number of nets,
                         followed by the actual net numbers which
                         are reachable at that distance.  Not all
                         distances need be reported.

distance 1               hop count (or  other  distance  measure)
                         which applies to this distance-group.

n1-dist                  number of nets  which  are  reported  in
                         this distance-group.

net11                    1, 2, or 3 bytes for the  first  net  at
                         distance "distance 1".

net12                    second net

...

net1n1                   etc.

ACKNOWLEDGMENT or NEGATIVE ACKNOWLEDGMENT

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway Type  |  Unused       |        Sequence number        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Here's how the ACK fields work, periodt 💖

Gateway Type             Acknowledgments are  type  2.   Negative
                         acknowledgments are type 10.

Sequence Number          The  16-bit  sequence  number  that  the
                         gateway  is  acknowledging or negatively
                         acknowledging.

GGP ECHO and ECHO REPLY

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Gateway Type  |            Unused                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

And the echo fields, which are giving simple but iconic 🦋

Gateway Type             8 for echo message; 0 for echo reply.

Source Address           In an echo message, this is the  address
                         of  the  gateway  on the same network as
                         the neighbor to which it is sending  the
                         echo message.  In an echo reply message,
                         the source and destination addresses are
                         simply  reversed,  and  the remainder is
                         returned unchanged.
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    ! Gateway Type  !                  unused                       !
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Gateway Type             9

    Source Address
    Destination Address      The address  of  the  gateway's  network
                             interface.   The  gateway  can  send Net
                             Interface Status messages to  itself  to
                             determine  if  it  is  able  to send and
                             receive   traffic   on    its    network
                             interface.

Okay so the Network Interface Status message is basically the gateway texting itself to check if its own network interface is working 📱🫶 The layout above is the vibe, and the Gateway Type is always 9 for this one 🔥. Both the Source Address and the Destination Address are the address of the gateway's network interface, so it's literally sending a message to itself, and if it can send and receive that message it knows its interface is healthy ✨ no cap, it's the ultimate self-check 💅

APPENDIX B. Information Maintained by Gateways 🧚

Okay bestie, to run the shortest-path routing algorithm 🛣️, gateways must maintain information about their connectivity to networks and to other gateways. This section breaks down everything each gateway keeps track of 📋. It can all be organized into the following tables and variables, so let's go 💜

  • Number of Networks

The number of networks for which the gateway maintains routing information and to which it can forward traffic.

  • Number of Neighbors

The number of neighbor gateways with which the gateway exchanges routing information.

  • Gateway Addresses

The addresses of the gateway's network interfaces.

  • Neighbor Gateway Addresses

The address of each neighbor gateway's network interface that is on the same network as this gateway.

  • Neighbor Connectivity Vector

A vector of the connectivity between this gateway and each of its neighbors.

  • Distance Matrix

A matrix of the routing updates received from the neighbor gateways.

  • Minimum Distance Vector

A vector containing the minimum distance to each network.

  • Routing Updates from Non-Routing Gateways

The routing updates that would have been received from each non-routing neighbor gateway which does not participate in this routing strategy.

  • Routing Table

A table containing, for each network, a list of the neighbor gateways on a minimum-distance route to the network.

  • Send Sequence Number

The sequence number that will be used to send the next routing update.

  • Receive Sequence Numbers

The sequence numbers that the gateway received in the last routing update from each of its neighbors.

  • Received Acknowledgment Vector

A vector indicating whether or not each neighbor has acknowledged the sequence number in the most recent routing update sent.

APPENDIX C. GGP Events and Responses 💖

Here's the tea 🍵: this is the list of GGP events that can happen at a gateway, plus how the gateway reacts to each one. All the variables and tables it mentions are the ones we just covered in Appendix B, so no surprises 🦋

  • Connectivity to an attached network changes.
    • a. Update the Minimum Distance Vector.
    • b. Recompute the Routing Updates.
    • c. Recompute the Routing Table.
    • d. If any routing update has changed, send the new routing updates to the neighbors.
  • Connectivity to a neighbor gateway changes.
    • a. Update the Neighbor Connectivity Vector.
    • b. Recompute the Minimum Distance Vector.
    • c. Recompute the Routing Updates.
    • d. Recompute the Routing Table.
    • e. If any routing update has changed, send the new routing updates to the neighbors.
  • A Routing Update message is received.
    • a. Compare the Internet source address of the Routing Update message to the Neighbor Addresses. If the address is not on the list, add it to the list of Neighbor Addresses, increment the Number of Neighbors, and set the Receive Sequence Number for this neighbor to the sequence number in the Routing Update message.
    • b. Compare the Receive Sequence Number for this neighbor to the sequence number in the Routing Update message to determine whether or not to accept this message. If the message is rejected, send a Negative Acknowledgment message. If the message is accepted, send an Acknowledgment message and proceed with the following steps.
    • c. Compare the networks reported in the Routing Update message to the Number of Networks. If new networks are reported, enter them in the network vectors, increase the number of networks, and expand the Distance Matrix to account for the new networks.
    • d. Copy the routing update received into the appropriate row of the Distance Matrix.
    • e. Recompute the Minimum Distance Vector.
    • f. Recompute the Routing Updates.
    • g. Recompute the Routing Table.
    • h. If any routing update has changed, send the new routing updates to the neighbors.
  • An Acknowledgment message is received.

Compare the sequence number in the message to the Send Sequence Number. If the Send Sequence Number is acknowledged, update the entry in the Received Acknowledgment Vector for the neighbor that sent the acknowledgment.

  • A Negative Acknowledgment message is received.

Compare the sequence number in the message to the Send Sequence Number. If necessary, replace the Send Sequence Number, and retransmit the routing updates.

REFERENCES 📚

[1] Postel, J. (ed.), "Internet Protocol - DARPA Internet Program Protocol Specification," RFC 791, USC/Information Sciences Institute, September 1981.

[2] Strazisar, V., "Gateway Routing: An Implementation Specification," IEN-30, Bolt Beranek and Newman Inc., August 1979.

[3] Strazisar, V., "How to Build a Gateway," IEN-109, Bolt Beranek and Newman Inc., August 1979.

[4] Postel, J., "Internet Control Message Protocol - DARPA Internet Program Protocol Specification," RFC 792, USC/Information Sciences Institute, September 1981.

[5] Postel, J., "Assigned Numbers," RFC 790, USC/Information Sciences Institute, September 1981.

[6] Littauer, B., Huang, A., Hinden, R., "A Host Monitoring Protocol," IEN-197, Bolt Beranek and Newman Inc., September 1981.

[7] Santos, P., Chalstrom, H., Linn, J., Herman, J., "Architecture of a Network Monitoring, Control and Management System," Proc. of the 5th Int. Conference on Computer Communication, October 1980.

[8] Haverty, J., "XNET Formats for Internet Protocol Version 4," IEN-158, Bolt Beranek and Newman Inc., October 1980.

[9] Mathis, J., Klemba, K., Poggio, "TIU Notebook- Volume 2, Software Documentation," SRI, May 1979.

[10] Rosen, E., "Exterior Gateway Protocol," IEN-209, Bolt Beranek and Newman Inc., August 1982.

📦 where this page comes from