RFC-61

by Darius Kazemi, Mar 2 2019

In 2019 I'm reading one RFC a day in chronological order starting from the very first one. More on this project here. There is a table of contents for all my RFC posts.

Another shot at interprocess communication

RFC-61 is titled “A Note on Interprocess Communication in a Resource Sharing Computer Network”, authored July 17th, 1970 by Dave Walden of BBN.

After a long career in computing and management, Walden has taken to researching various aspects of computing history. I have already written here about the history of BBN that he co-edited (I'm partway through and it's great). He contacted me early on in this project to offer valuable contextual information from his point of view as someone involved in the IMP/ARPANET project at BBN, for which I am grateful.

The technical content

This document is a draft of a study Walden is in the process of writing at BBN. The paper tackles “inter-process communication” on a network, which is the same thing that the host-host protocol and NCP combination proposed by Crocker et al had been attempting to solve. Specifically the study is trying to lay out a standard by which all computers on a network can invoke programs and move data around, rather than an ad-hoc system that would be different for every single pair of computers on the network. The ideas herein would never be fully implemented as they are laid out but certainly influenced the development of other such schemes.

The document makes reference to the host-host paper that Carr, Crocker, and Cerf proposed at the 1970 Spring Joint Computer Conference just a few months prior.

Here for the first time in an RFC we get a clear definition of “monitor” and “process” in their operating system context. In full:

The model time-sharing system has two pieces: the monitor and the processes. The monitor performs several functions, including switching control from process to process as appropriate (e.g., when a process has used “enough” time or when an interrupt occurs), managing core and the swapping medium [memory], controlling the passing of control from one process to another (i.e., protection mechanisms), creating processes, caring for sleeping processes, etc.

The processes perform most of the functions normally thought of as being supervisor functions in a time-sharing system (system processes) as well as the normal user functions (user processes). A typical system process is the disc handler or the file system. For efficiency reasons it may be useful to think of system processes as being locked in core.

A process can talk to the monitor and ask it to do the following things:

The actual commands are a little more wonky than this. A SEND is actually a request to another process to “SEND something to me” so it operates logically backwards from how you might assume. But all the above functionality is there even if the grammar is weird.

The paper then lays out how this kind of communication could happen at a single physical computer. The examples are very clear.

The next section generalizes this communication to communications between a local host and a remote host (so, over the network).

I really like this image that Walden paints of what a networked computer might look like in an abstract sense:

Consider first a simple configuration of processes distributed around the points of a star. At each point of the star there is an autonomous time-sharing system. A rather large, smart computer system, called the Network Controller, exists at the center of the star. No processes can run in this center system, but rather it should be thought of as an extension of the monitor of each time-sharing system in the network.

So the computer has many processes on it, and every process talks to a special computer system (called the NCP in other RFCs), and that computer system really ought to be thought of as part of the core operating system itself. This Network Controller acts as a broker between all the processes on the computer and the rest of the network. Walden makes the claim that

if the Network Controller is able to perform the operations SEND, RECEIVE, SEND FROM ANY, RECEIVE ANY, and UNIQUE and that if all of the monitors in all of the time-sharing systems in the network do not perform these operations themselves but rather ask the Network Controller to perform these operations for them, then we have solved the problem of interprocess communication between remote processes. We have no further change to make. [emphasis mine]

Next he says that somewhere on the computer is a table of unmatched SEND and RECEIVE requests (or RECEIVE ANY requests that haven't gotten anything yet). This table of unmatched pairs lets a computer listen for outstanding messages it hasn't yet received.

The last big piece is that the UNIQUE number function must provide numbers that are unique across the network. This is handled by giving out unique blocks of numbers to each computer to parcel out on their end as needed.

Because this is a BBN paper, and BBN designed and implemented the IMP (recall: basically a proto-router), the IMP is considered of great importance. The IMP is hardly even mentioned in RFCs by the various west coast entities. It's fully “black boxed” to everyone except for the people who invented it. But BBN knows what is in the black box and thus has some things to say about it.

In the scheme put forward by this RFC, in the ARPANET context, the IMP itself will host the NCP rather than the host. This is a new proposal; prior to this RFC the idea was that the Host would be the sole arbiter of interprocess communications. It seems to me that main reason for the IMP role in this is so that there is some central source of unique numbers that is still “neutral”. That way it's not just some Host machine at UCLA doling out number ranges to the other computers but a more neutral party in the network. The other reason for putting the NCP software on the IMP is that the IMP is known hardware and software. You only need to write the NCP once for the IMP system. Since every host has the same type of IMP installed on site, you no longer have to write a new NCP for every new kind of computer you connect to the network.

Analysis

This paper is long but, in my opinion, well worth reading (or perhaps just read its final edition, linked in the “Further reading” section below). To me, this is by far the clearest elucidation in the RFC series to date of how processes can talk to each other over the network (and there have been many attempts!).

Here is a photo of a few pages of this RFC that I took at the Computer History Museum's warehouse.

Four handsomely typewritten pages fanned out on a desk.

You might not be impressed with what you see here but after combing through dozens and dozens of these documents, there is something uniquely beautiful about any BBN document I come across. For example, note that the headings are written in an entirely different type face from the body of the document (compare the “T” in “A MODEL FOR A TIME-SHARING” with the “T” that begins several body paragraphs). There is italicized and bolded text. You'll have to trust me on this but the physical paper quality is really nice. According to Walden himself in one of our email correspondences, BBN had an illustration department, an editor, and a secretary that did excellent work when it came to corporate document preparation and publication.

Further reading

This RFC is an early draft of a paper that would eventually be published in April 1972 in Communications of the ACM and is fairly heavily cited by other papers. The full paper is hosted by Walden at his web site.

Walden has a short memoir here.

Here is The Nucleus of a Multiprogramming System, the 1970 paper by Per Brinch Hansen cited in the RFC.

How to follow this blog

You can subscribe to this blog's RSS feed or if you're on a federated ActivityPub social network like Mastodon or Pleroma you can search for the user “@365-rfcs@write.as” and follow it there.

About me

I'm Darius Kazemi. I'm a Mozilla Fellow and I do a lot of work on the decentralized web with both ActivityPub and the Dat Project.