Personal Distributed Computing: The Alto and Ethernet Software

3. Communication

In order not to lose the ability of time-sharing systems to support shar­ing of information and physical resources in moving to personal com­puting, it was necessary to develop communication facilities far beyond the state of the art in 1973. The Ethernet provided the hard­ware base for this development. A great deal of work also went into the software.

The first generation of Alto communication software, called Pup for PARC Universal Packet [4], is based on ideas developed for the Arpanet in the late 1960s [33], with changes to correct known prob­lems. Pup was originally designed by Bob Metcalfe, and implemented by him together with David Boggs and Ed Taft.

The model for communication was structured in four levels:

1. 
   Level 0: Transport—various mechanisms for transporting a data­gram from one machine to another: Ethernet, Arpanet, leased telephone lines, etc.
   
2. 
   Level 1: Internet datagrams
   
3. 
   Level 2: Inter-process communication primitives—byte system protocol (BSP), rendezvous/termination protocol, routing table protocol, etc.
   
4. 
   Level 3: Data structuring conventions—file transfer protocol (FTP), remote terminal protocol (Telnet), mail transfer protocol (MTP), etc.
   

Internet datagrams are the common coin, decoupling higher levels from the details of the packet transport mechanism. Unlike other sys­tems based on local networks, such as the Cambridge ring [36] or the Apollo domain system [31], the Alto system takes no advantage of the special properties of the Ethernet. Instead, all clients of the communi­cation facilities use Internet datagrams, which present the same inter­face whether the data travels over the Ethernet, over a telephone line, or through a dozen different transport mechanisms. Pup thus treats a transport mechanism just as the Arpanet treats an IMP-to-IMP tele­phone line; the role of the IMP is played by a gateway that routes each datagram onto a transport mechanism that is expected to take it closer to its destination.

A major difference from the Arpanet is that Pup offers no guar­antee that a datagram accepted by the network will be delivered. When congestion occurs, it is relieved by discarding datagrams. This design reflects the expectation that most datagrams will travel over lightly loaded local networks; when links become congested, clients of the network may get disproportionately degraded service.

The main level 2 mechanism is the byte stream protocol, which provides a reliable full-duplex byte stream connection between two processes. It turns out to be fairly hard to use this kind of connection, since it is complicated to set up and take down, and has problems when unusual conditions occur. As in the Arpanet, however, this was of little concern, since the main customers for it are the level 3 file transfer and remote terminal services. These are normally provided by programs called FTP and Chat, invoked by users or their command scripts from the Executive command line processor [25]. FTP was writ­ten by David Boggs, Chat by Bob Sproull. There is also an FTP library package that programs can call directly to transfer files; this is used by the Laurel mail-reading program, and (in an abbreviated version) by many applications that send files to the printer.

Pup byte streams have fairly good performance. They are capable of transferring about 0.3 MBits/second between two Altos, using datagrams with 512 data bytes plus a few dozen bytes of overhead. This is an order of magnitude better than the performance exhibited by a typi­cal byte stream implementation on a comparable machine. The differ­ence is due to the simplicity of the Pup protocols and the efficient implementation.

Other important network services in the Alto system were booting a machine and collecting reports from diagnostic programs. These used Internet datagrams directly rather than a level 2 protocol, as did one rather successful application, the Woodstock File System [50] de­scribed in section 4. But with these few exceptions, users and applications relied on FTP and Chat for communication services.

The only truly distributed program built in the Alto system other than the Pup Internet router is the Worm [42], which searches for idle machines into which it can replicate itself. It isn’t entirely clear why more attempts were not made to take advantage of the 150 Altos or 50 Dorados available at PARC. Part of the reason is probably the difficulty of building distributed programs; this was not alleviated by RPC until 1982 (see following material). The lack of a true network-wide file sys­tem before 1984 was probably another factor.

The Xerox 8000 network products use an outgrowth of Pup called Xerox Network System or XNS [60]. XNS adds one important level 3 protocol, the Courier remote procedure call protocol designed by Jim White. Courier defines a standard way of representing a procedure call, with its argument passing and result returning, between two ma­chines. In other words, it includes conventions for identifying the pro­cedure to be called, encoding various types of argument (integers, strings, arrays, records, etc.), and reporting successful completion or an exceptional result. Courier uses XNS byte streams to transport its data.

At about the same time, as part of the development of Cedar, An­drew Birrell and Bruce Nelson in CSL developed a remote procedure call mechanism that uses Internet datagrams directly [2]. They also built a stub generator that automatically constructs the necessary pro­gram to convert a local procedure call into a remote one, and a location mechanism based on Grapevine (see section 4.3) to link a caller to a remote procedure. Like Courier, Cedar RPC uses a Mesa interface as the basic building block for defin­ing remote procedures. Unlike Courier, Cedar RPC is fast: Two Dorados using Cedar RPC can execute a null remote procedure call in about a millisecond. Earlier work by Nelson indicates that further optimiza­tion can probably reduce this to about 200 microseconds; currently Ce­dar RPC has no clients that are limited by the performance.

The goal of Cedar RPC was to make it possible to build distributed programs without being a communications wizard. A number of suc­cessful weekend projects have demonstrated that the goal was reached. An unexpected byproduct was independent implementations of the same RPC mechanism in Lisp, Smalltalk, and C for the 8088; all these clients found it easier to implement the Cedar RPC than to design a more specialized mechanism for their own needs.