ARPANET IMPs and the 1822 Host Interface

The first four ARPANET nodes went into service at the end of 1969, and the machine installed at each site was not a computer in the usual sense. It was a switching computer with no users, no file system, and no application software: a Honeywell minicomputer with core memory, leased telephone lines on one side and one or more host machines on the other. Bolt Beranek and Newman called it an Interface Message Processor, and the name states the design decision. The network was to be built out of identical switches that knew nothing about the programs using them.

That separation is the reason the ARPANET could attach machines from different manufacturers without a common operating system. A host did not implement routing, did not know the topology, and did not know how many hops separated it from its correspondent. It handed a block of bytes to its local IMP with a destination written on the front and received acknowledgements from that same IMP. Everything between the two IMPs was the subnet’s business.

What the host was allowed to assume

The contract between host and IMP was written down as a specification with a number: BBN Report 1822, whose title is a description of the interface rather than of the network. The document fixed the electrical interface, the signalling on the local line, and the exact format of the messages exchanged across it. Its authority was such that the interface itself became known as “the 1822”, a name shared by a port, a cable, and a protocol.

The protocol is a message protocol, not a stream. A host composes a message of at most 8,096 bits including its leader, which is 1,012 bytes; the 32-bit leader carries a destination, a link number identifying which logical channel on the destination host the message belongs to, a message type, and a checksum over the leader itself. The payload follows and is not checksummed by the subnet, a decision that pushed end-to-end integrity onto the hosts and later became one of the arguments for the end-to-end principle.

Message types distinguished ordinary data from control: a host declaring itself up or down, the IMP reporting that a host had gone down, an error report carrying no payload, and the assignment message by which a host learned its own address at startup. A host did not configure its number; it asked, and the IMP answered. That single design choice removed an entire class of misconfiguration from the network’s operation.

The RFNM as the only flow control

The interesting part of the 1822 protocol is not the header but the pacing rule. After a host sends a message on a link, it may not send another on that link until the destination IMP returns a Request For Next Message. The RFNM is generated when the message has been delivered to the destination host, not when it left the source, so the rule is an end-to-end acknowledgement expressed at the subnet boundary.

The consequence is a window of exactly one message per link. For interactive traffic this is unremarkable: a terminal line’s message and its echo are small, and one message in flight keeps the round trip occupied without wasting capacity. For bulk transfer it is a severe limit. A host that wants to keep a 50 kbit/s line busy must use several links in parallel, because a single link stalls for one full path delay after every message. The ARPANET’s answer, adopted by host software rather than by the interface, was to open multiple links between the same pair of hosts and stripe data across them.

#include <stddef.h>
#include <string.h>

/* One-message window per link, as enforced by the 1822 interface. */
struct link_state {
    unsigned char pending[1012];  /* leader plus payload, max message size */
    size_t        pending_len;
    int           in_flight;      /* set on send, cleared by RFNM */
};

/* Returns 0 when the message may be handed to the interface, -1 for a bad
   length, -2 when the link is still waiting for its RFNM. */
int link_prepare(struct link_state *lk, const void *msg, size_t len)
{
    if (len == 0 || len > sizeof lk->pending)
        return -1;
    if (lk->in_flight)
        return -2;
    memcpy(lk->pending, msg, len);
    lk->pending_len = len;
    lk->in_flight = 1;
    return 0;
}

/* Called when the destination IMP returns an RFNM for this link. */
void link_rfnm(struct link_state *lk)
{
    lk->in_flight = 0;
}

The refusal in link_prepare is the whole protocol. A host that ignores it and queues a second message in its own buffer is not violating the interface, but it is holding data the interface has not accepted, so the responsibility for retrying stays with the host.

Why the switch had to be a computer

An IMP was a stored-program machine running a real-time executive, and that was a deliberate rejection of an alternative design. A hardwired switch built from logic could have forwarded messages faster and cost less per port, but it could not have run an adaptive routing algorithm, could not have collected statistics, and could not have been reprogrammed in the field. The ARPANET’s routing was revised repeatedly during the 1970s, and each revision was a software change distributed to the installed IMPs.

The original routing scheme was a distributed shortest-path computation in which each IMP exchanged delay estimates with its neighbours and relaxed distances toward the destination, the same family of algorithm later standardised as RIP. It had the failure mode that family always has: after a link failure, distances counted upward slowly, and messages looped between neighbours while the estimate converged. The replacement, developed in the late 1970s, flooded link-state information and computed shortest paths from a complete map, trading bandwidth on every link for convergence that did not depend on hop-by-hop gossip. The distance-vector habit that produced the first scheme is examined, along with its successor, in Path Vectors, Policy, and Why BGP Does Not Minimize Anything.

The executive that ran on an IMP was written for a machine with a small core memory and no virtual memory, so its buffers were statically allocated and its queue depths were fixed at configuration time. That produced a characteristic failure: an IMP whose outgoing line was congested had no way to grow a queue, and once the queue for a line filled, the IMP dropped the message and reported the drop rather than slowing the hosts feeding it. The hosts had no lever to pull, because the RFNM window bounded messages per link but not messages per host, and a host with many links open could still present more traffic than an IMP’s buffers could hold. This asymmetry, the subnet enforcing a limit per link while the load arrives per host, is the reason later protocols moved pacing to the endpoints and made it depend on observed path behaviour rather than on a fixed per-link window.

The switch also had to survive partial failure. An IMP with no path to a destination returned an error message rather than dropping the message silently, and a host that received that error could retry or report it. This is the origin of a habit that persists: the network reports failure at the point where it knows, and the endpoint decides what to do.

The boundary that did not survive

The 1822 interface assumed one host per port and a small, fixed number of hosts per IMP, with a destination field wide enough for one network’s IMP and host numbers. It assumed the subnet was a single administrative entity with a known topology. It assumed a message, not a stream, and it assumed the host would not send faster than the subnet could absorb because the window of one made that impossible.

Each assumption failed within a decade. Hosts multiplied and wanted many concurrent conversations, which the link-number space could accommodate but the one-message window could not. Separate networks with different technologies wanted to interconnect, which required an address space larger than an IMP number and a host number. And once several networks were joined, no single administrative entity knew the topology, so routing had to become hierarchical and policy-driven rather than a shortest-path computation over a known map. The first two failures produced NCP and then TCP/IP, traced in NCP and the Limits That Forced TCP/IP and The TCP/IP Split and the End-to-End Argument.

The protocol that replaced the 1822 boundary was NCP, which kept the subnet’s message interface and added host-to-host connections on top. What survived from the IMP design is the layering itself: a subnet that forwards without understanding, and endpoints that own reliability, ordering, and the meaning of the bytes.