RFC 528

RFC 528: SOFTWARE CHECKSUMMING IN THE IMP AND NETWORK RELIABILITY 💖

Okay bestie, let's start with the header 🎀 This one is from the Network Working Group, written by J. McQuillan of BBN-NET, with NIC number 17164, dated 20 June 1973. The header doesn't list a category, and it doesn't say it obsoletes or updates anything, so there's nothing to chase there ✨

---

So the ARPA Network has been growing for a few years, and the more we ran the IMP subnetwork, the more reliability went from "kinda important" to "wow, this is a big deal and also super complicated" 😭 This note walks through some changes recently made to the IMP and TIP programs for that. They're mechanically pretty small and they don't affect Host operation at all, but they're logically a big deal, so we explain how the new IMP and TIP programs work in a lot of detail. Host people, pay special attention to sections 4 and 5, because you might want to change your own programs or how you operate things 👀

1. A Changing View of Network Reliability 🦋

Our idea of the Network has glowed up as the Network itself got bigger 🌸 At first, everyone assumed the only parts that could mess up were the communications circuits, and the modem interfaces in the IMPs had a CRC checksum to catch "almost all" of those errors. Everything else, like Host interfaces, IMP processors, memories, and interfaces, was considered error-free. We had to rethink that after actually running the thing. Remote diagnosis is the struggle: we get reports from Host people about lost RFNMs and lost Host-Host protocol allocate messages, weird transient behavior inside an IMP, and crashes where a whole IMP goes down and maybe takes adjacent IMPs with it 💀 These things are rare, which makes them hard to link to other failures or to a particular fix. Honestly, it's often impossible to tell a software failure from a hardware one 🙈

When we tried to post-mortem crashes, we sometimes found the IMP program had incorrect instructions, sometimes with just one or two bits picked up or dropped. Memory errors can explain almost any failure, including crashes and data errors that cause all sorts of other chaos. Like, if the address of a message changes in transit, one Host thinks its message got lost and another Host gets an extra message 😵 These errors fall into two classes: errors in Host messages, whether in the control information or the data, and errors in inter-IMP messages, mainly routing update messages. Over the last few years it became clearer that these errors were happening, but it was hard to guess where, why, and how often 🧐

The earliest one of these was found in 1971. The Harvard IMP kept crashing in some unknown way and took all the other IMPs down with it. It turned out its memory was faulty, and sometimes the routing messages read out of memory by the modem output interfaces were all zeroes. Neighboring IMPs read that as the Harvard IMP having zero delay to every destination, which meant it was the best route to everywhere! 😱 Once that info spread, the whole network was a total mess. The fix was to generate a software checksum for each routing message before one IMP sent it, and check it after the other IMP received it. This software checksum works alongside the circuit's hardware checksum, checks the modem interfaces and memories at each IMP, and protects IMPs from bad routing information. It doesn't cost much, because the messages only get exchanged every 2/3 of a second ✨

Early 1973 was rough 😩 In the first few months we had a lot of trouble with the reliability of some IMPs, especially the ones in the Washington area. Calling in Honeywell field engineers the normal way didn't clear up several of these stubborn failures, so an escalation of BBN involvement was needed to find the exact causes. During much of February and March, one or more staff members were at various sites where hardware problems were suspected 🫶 The first thing we learned was that the operational IMP program didn't give enough diagnostic information when failures happened, and the available test programs didn't detect errors often enough to be worth using. The errors showed up at pretty low frequency, anywhere from once every few hours to once every few days, while messages flow at a rate of once a second or faster. So we decided to make the operational IMP program keep running when it can and report more information about hardware errors it detects, instead of keeping failing IMPs off the network for days at a time 💅

We had two independent goals with the IMP program changes: make the software less vulnerable to hardware failures, and have it isolate the failures and report them to the NCC. The technique we chose was generating a software checksum on all packets as they go out over a line. We suspected the Washington-area hardware failures were happening between IMPs, which means the packets were correct before they were sent. So a memory-to-memory software checksum, similar to the technique installed two years earlier for routing messages only, should be able to catch these errors 🔥 On March 13, a new version of the IMP program with software checksum code was released. When a packet has an incorrect checksum, it gets discarded and a copy of the data is sent to the NCC. The previous IMP retransmits the packet, since no acknowledgment comes back 🌈

Here's a partial list of the hardware problems that software checksums uncovered and that were later fixed, bestie:

• One modem interface at the Aberdeen IMP dropped several bits from several successive words while transferring data into memory.
• One modem interface at the Belvoir IMP picked one or two bits in a single word while transferring data into memory.
• One modem interface at the ETAC TIP dropped the first word while transferring data out of memory.
• A region in memory at the Utah IMP changed the low order two bits in some words on an irregular basis.

Each of these problems caused two or three detected errors per day 😤 There were other problems the software checksum didn't detect, like dropped interrupts. That set of problems may be explained by the electronics of the high-speed DMC on 316 IMPs. The first three machines cited above are 316 IMPs with 3 modem interfaces, and they're the only such machines in the network. The third interface sits in a separate drawer, and the total bus length seems to be too long for the driving electronics in the original design. We're investigating various ways to fix these problems, and we've already had some success 🎉

2. An End-to-End Software Checksum on Packets ✨

okay so that last experience, plus the earlier checksum on routing messages, proved that software checksums on every inter-IMP transmission are worth it 💅. So we're making them a permanent feature of the IMP system, AND we're extending the checksum to catch intra-IMP failures too 🔥. Here's how we get an end-to-end software checksum on packets with no time gaps where the packet goes unchecked 🦋:

      +--------+        +--------+        +---------+
      |  IMP  2|--------|3 IMP  4|--------|5  IMP   |
      |   1    |        |        |        |    6    |
      +---|----+        +--------+        +----|----+
          |                                    |
      +---|----+                          +----|----+
      |        |                          |         |
      |  Host  |                          |  Host   |
      +--------+                          +---------+

• A checksum is computed at the source IMP for each packet as it is received from the source Host. (interface 1)
• The checksum is verified at each intermediate IMP as it is received over the circuit from the previous IMP. (interfaces 3 and 5)
• If the checksum is in error, the packet is discarded, and the previous IMP retransmits the packet when it does not receive an acknowledgment. (interface 2 and 4)
• The previous IMP does not verify the checksum before the original transmission, to cut the number of checks in half. But when it must retransmit a packet it does verify the checksum. If it finds an error, it has detected an intra-IMP failure, and the packet is lost. If not, then the first transmission was lost due to an inter-IMP failure, a circuit error, or was simply refused by the adjacent IMP. The previous IMP holds a good copy of the packet, which it then retransmits. (interface 2 and 4)
• After the packet has successfully traversed several intermediate IMPs, it arrives at the destination IMP. The checksum is verified just before the packet is sent to the Host. (interface 6)

So the checksum covers the packet from the source IMP all the way to the destination IMP, with no gaps in time when the packet is unchecked 🫶. Any errors get reported to the NCC in full, with a copy of the packet in question 📋. This method hits both goals we set out earlier: the IMPs become more reliable and fault-tolerant, AND we get the maximum amount of diagnostic info for fault isolation 🧚. This expanded checksum logic was installed in the network on June 19 🎀.

One of the big questions about approaches like this is efficiency, and honestly it's a fair thing to ask 🙈. We managed to put the software checksum on all packets without greatly increasing the processing overhead in the IMP. The method involves one checksum calculation at each IMP that a packet travels through. We built a very fast checksum technique that takes only 2 msec per word. The program counts the words in a packet, then jumps to the right entry in a chain of add instructions. This gives a simple sum of the words in the packet, and the number of words in the packet gets added too, so missing or extra words of zero can be detected 🧮.

Now the cost: with this code in, the effective processor bandwidth of a 516 IMP drops by one-eighth for full-length store-and-forward packets, going from a megabit per second down to 875 kilobits per second 📉. In other words, the IMP can now connect to 17 full duplex 50 kilobit per second lines, where it used to handle 20 such lines without the checksum program 😭. We know this add checksum isn't very good at detecting errors, but it's as much as the IMP can afford to do in software 💀. And to be clear, the main goal of this change is to help with remote diagnosis of intermittent hardware failures 🔍.

3. Checksumming to Improve the Reliability of Routing 🛣️

Remember how we talked about how catastrophic it is for the whole Network when a single IMP starts spreading wrong routing info? Yeah, that 💀. The experience above came from one specific memory failure that hasn't come back in the last two years. But the problem is easy to see as a general one 🌍. And we actually had another network-wide failure recently, traced to a hardware error that produced bad routing messages, and this happened after we'd already put a software checksum on all inter-IMP transmissions 😳. The issue was a single broken instruction in the part of the IMP program that builds the routing message. So the routing messages from that IMP were random data, and the neighboring IMPs read them as real routing update info. Once that happened, traffic through the Network was completely disrupted, and no useful work could get done until the failed IMP was halted 🛑.

This kind of problem, where incorrect routing info gets into the Network, can happen in three ways:

• The routing message is changed in transmission. The inter-IMP checksum should catch this. The bad routing messages we saw in the Network had good checksums. 🤔
• The routing message is changed as it is constructed, say by a memory or processor failure, or before it is transmitted. This is what we termed above an intra-IMP failure.
• The routing program is incorrect for hardware or software reasons.

So we went after the last two kinds of problems by extending the software checksum idea 🧠. The routing program now builds a software checksum for the routing message as it builds the message, just like it would for a message coming from a Host. It's really important that this checksum refers to the intended contents of the routing message, not the actual contents. The program that generates the message builds its own checksum as it goes. It doesn't read back what's stored in the routing message area. Instead, it adds up the intended contents for each entry as it computes them 🧾. The process that sends out routing messages always verifies the checksum before transmitting them. This scheme should catch all intra-IMP failures ✅.

There's one more layer: the routing program itself can be checksummed to detect any changes in the code 🔐. The programs that copy in received routing messages, compute new routing tables, and send out routing messages each calculate the checksum of the code before running it. If a program finds a discrepancy in the checksum of the program it's about to run, it immediately requests a program reload from an adjacent IMP 🔄. These checksums cover the checksum computation itself, the routing program, and any constants it references. The point is to stop a hardware failure at one IMP from hurting the whole Network. The IMP gets stopped before it can do damage by spreading bad routing 🛡️. A version of the IMP program with this added routing protection was released on May 22 🎉.

In the first few months of 1973, there were several other efforts to improve Network reliability, on top of the software checksumming in the IMPs 🌸. While we were finding inter-IMP failures with the software checksum packets, we also started noticing a different problem: intra-IMP failures. Mostly these were memory problems, and they often hit the IMP program itself, not just the packets flowing through the IMP 😬. Our first attack on this was a PDP-1 program that verifies the running IMP and TIP programs at a site against the correct core images held at the PDP-1. The program talks to the IMP with DDT messages and prints out a list of discrepancies 📜. With it, we've already found memory failures at one site 🕵️‍♀️.

4. TIP Modifications ✨

The hardware trouble we started having in the first few months of 1973 hit Host-to-Host communication in two ways 😤. First, the intermittent modem interface failures, like the ones seen at Belvoir, Aberdeen, and ETAC, meant the network occasionally lost messages. The source IMP reports this loss to the transmitting Host with an "Incomplete Transmission" message, and then the Host has to decide whether to retransmit or do something else 🤷‍♀️. Second, the higher-than-normal rate of machine failures meant the network sometimes "partitioned," so there was no path between the two communicating Hosts. (Heads up: contrary to the original design, two sites are currently connected to the network by only a single path, and other similar connections are planned. For any such sites, any failure along the single path will be seen as a partition.) Since a TIP acts as a Host for its users, how well it holds up during these failures has a huge effect on user satisfaction 💖.

Before this, the TIP program "aborted" the user's connection whenever it got an Incomplete Transmission indication from the IMP program 😭. In March, the TIP program (along with the programs of several other Hosts) was changed to retransmit messages that came back with an Incomplete Transmission indication. Some Hosts, like MULTICs, had been doing this from the start 🙌. This change turned out to be pretty simple, and we urge other Hosts to consider adding some kind of error recovery software 💅. On the other hand, it didn't seem reasonable to keep trying to transmit when the program gets a "Destination Unreachable" indication. That could come from a network partition or from a failure at the destination site 🚧. The interactive user is, of course, free to try again manually 🫶.

Tape transfers are a different situation 📼. With TIPs that have the magnetic tape option, the user wants to start the process and then walk away until the transfer is done. Network partitions, even infrequent ones, can happen while tape transfers that run many hours are in progress 😱. So we made a significant change to the TIP magnetic tape option. We added a sequencing mechanism to the tape transfer protocol, which allows automatic recovery and continued transmission after most kinds of network transients 🔁. With this in effect, and assuming a tape is mounted at the "other end," a complete tape transfer can be done with a single command given at either end 🎞️. If the connection goes dead mid-transfer, the TIP magnetic tape software keeps trying to reopen the connection until it succeeds, then picks up the transfer right where it left off 💪. We also modified the TENEX program that talks to the TIP magnetic tape option, so that it stays compatible with these changes 🌈. All of these changes were installed in April 🌷.

5. Future Plans ✨

okay bestie, so the people behind this one had been thinking about the network reliability stuff we just went through, and they were cooking up the design for a brand new IMP called the High Speed Modular IMP 🔥. the way it's giving: the current IMP system and this new design effort are totally linked together, and they had already decided on a bunch of approaches for the new line of IMPs 💅

Here's the lineup:

• the IMP gets a hardware CRC checksum generator, which returns the checksum on a specified range of memory 🧮
• the IMP uses that generator to make and check an end-to-end checksum on messages. this one is way more comprehensive and better at catching errors than the current software checksum, so it insures a high degree of reliability for Host transmissions 🛡️💖
• the IMP also verifies a packet checksum at each hop, mainly for diagnostic info 🔍. this check is optional, and it only runs whenever the system has spare resources for it 🫶
• the code for the new IMP is read-only (which is impractical for the present 516 and 316 IMPs, ngl 💀). the program periodically checksums itself using the hardware CRC generator 🔐. the hope is that the program can be reloaded in segments if a code error gets detected, with no service interruption ✨
• finally, they were looking into an optional IMP-Host/Host-IMP checksum, which would complete the Host/Host end-to-end checksum 🎀. under this setup, the IMP and Host agree to verify the checksums on messages moving across the interface between them, and signalling mechanisms get set up to handle errors 🚨. with this in effect, two Hosts could be certain their messages were delivered error-free, or else they'd get notified of an error and could retransmit if they wanted 👑

More details on any of these IMP and IMP-Host interface changes will be published when appropriate 🦋

---

[This RFC was put into machine readable form for entry] [into the online RFC archives by Via Genie 12/1999] 🌸