[_cd8_]<pup>puppaper.dm!1>Pup3.bravo

The preceding section has outlined some of the important properties of the Pup architecture and the internetworking issues it addresses. What follows is a more detailed description of the present design of the four major layers in the system.

An individual network moves network-specific packets among hosts; the addressing schemes, error characteristics, maximum packet sizes, and other attributes of networks vary greatly. An internetwork packet transport mechanism, however, moves Pups between hosts. The level 0 code which transforms a network into an internet packet transport mechanism is called a network driver.

A machine connected to a single network, therefore, has one level 0 network driver; a gateway has one driver for each directly-connected network. Only the driver knows about the peculiarities of a network’s hardware interface and low-level protocol.

The interface between levels 0 and 1 is very simple. Level 1 passes down a Pup and a network-specific host address, and the driver encapsulates the Pup and does its best to deliver it to the specified host. When a Pup arrives at a host, the driver decapsulates it and passes it up to level 1; if for any reason the Pup looks suspicious (as determined by network-specific error checking), the driver discards it.

Every packet transport mechanism must be able to accept a maximum-size Pup; if the actual network cannot directly encapsulate a packet of that size for transmission, the driver must include some form of intranetwork fragmentation.

A network driver may also be asked to broadcast a packet to all other hosts on that net. On some networks this is straightforward; on others it may require use of a reverse-path forwarding algorithm [Dalal & Metcalfe, 1978] or brute-force replication of the packet to each destination.

The transport mechanisms don’t have to be perfectly reliable, but they should be successful most of the time—a packet loss rate of less than 1 percent is usually acceptable. A network operating for a short time in a degraded mode with a higher loss rate is harmless, so long as the probability is low that Pups will transit more than one net that is in this condition. However, if a network’s inherent error characteristics are unfavorable, the driver should take steps to improve its performance, perhaps by incorporating a network-specific low-level acknowledgment and retransmission protocol.

Ethernet. Local Ethernet facilities can very easily serve as transport mechanisms for Pups: a Pup fits in an Ethernet packet with only a few additional words of encapsulation (see figure 2), and requires no fragmentation. These systems have good reliability, high speed, and can send broadcast packets [Metcalfe & Boggs, 1976; Shoch & Hupp, 1979; Shoch, 1979b].

MCA. The Multiprocessor Communications Adapter (MCA), a parallel TDM bus, serves as a local network tying together a limited number of Nova computers [Data General, 1971]. It has good reliability and requires no fragmentation, but does not support broadcast packets. Broadcasts are accomplished by the brute-force method—sending a copy of a broadcast packet to each of the possible hosts.

Arpanet. To cover longer distances, Pups can be routed through the Arpanet; the format for encapsulating a Pup in an Arpanet message is shown in figure 2. (Note that Arpanet Pup transport is based on Host-IMP protocol messages, not on Host-Host protocol streams.) Because the standard maximum Pup length is less than that of an Arpanet message, the driver itself need not fragment Pups; however, the Arpanet does perform network-specific fragmentation internally: one ‘‘message’’ containing a Pup may become multiple ‘‘packets’’ within the Arpanet. Furthermore, the Arpanet provides increased reliability through the use of its own internal acknowledgment and retransmission protocols. The Arpanet does not presently support broadcast packets; rather than sending packets to all possible Arpanet hosts, the network driver does not implement broadcasts at all.

Leased line store-and-forward network. More frequently, different local networks are interconnected over long distances through the use of a private store-and-forward network constructed using leased telephone circuits. Similar in spirit to the Arpanet, this system is used to connect internetwork gateways. Unlike the Arpanet, the system does not use separate packet switches (IMPs), but instead switches packets through the hosts themselves—that is, the connected hosts include network-specific drivers that implement a store-and-forward network. This network has its own adaptive routing procedure, independent of the internetwork routing. The system is fairly reliable and does not require low-level acknowledgments. At present, the network drivers do not fragment Pups, but they do promote small packets to the front of transmission queues at intermediate points to help improve performance for interactive traffic.

Packet Radio network. On an experimental basis, the ARPA Packet Radio network [Kahn et al., 1978] has been used to carry traffic among local networks in the San Francisco Bay area. The Packet Radio network was integrated into the system by building a suitable level 0 network driver [Shoch & Stewart, 1979]. The system provides good reliability; but due to the relatively small maximum packet size (232 bytes), the driver must perform fragmentation and reassembly (see figure 2). Though using a broadcast medium, the Packet Radio protocols do not support broadcast packets. In this case, the low-level driver includes a procedure to periodically identify Packet Radio hosts that might be running Pup software; when asked to broadcast a packet, the driver sends copies of it to all such hosts.

To date we have not used any public packet-switched networks, such as Telenet, as packet transport mechanisms. These systems usually provide only a virtual circuit interface (X.25) that requires a user to pay for functionality that may not be needed. Compared to our existing leased line network, a Telenet-based packet transport mechanism would not be cost-effective except under conditions of very light traffic volume. We would prefer to use a service that provided simple, unreliable datagrams; if there were an appropriate interface, we could dismantle our leased line store-and-forward network.

The transport control field is used for two purposes: as a scratch area for use by gateways, and as a way for source processes to tell the internet how to handle the packet. (Other networks call this the ‘‘facilities’’ or ‘‘options’’ field.) The hop count subfield is incremented each time the packet is forwarded by a gateway. If this ever overflows, the packet is presumed to be travelling in a loop and is discarded. A trace bit is specified, for potential use in monitoring the path taken by a packet.

The Pup type is assigned by the source process for interpretation by the destination process and defines the format of the Pup contents. The 256 possible types are divided into two groups. Some types are registered and have a single meaning across all protocols; Pups generated or interpreted within the internet (e.g., by gateways) have types assigned in this space. Interpretation of the remaining unregistered types is strictly a matter of agreement between the source and destination processes.

The Pup identifier is used by most protocols to hold a sequence number. Its presence in the internetwork header is to permit a response generated within the internet (e.g., error or trace information) to identify the Pup that triggered it in a manner that does not depend on knowledge of the higher-level protocols used by the end processes.

Pups contain two addresses: a source port and a destination port. These hierarchical addresses include an 8-bit network number, an 8-bit host number, and a 32-bit socket number. Hosts are expected to know their own host addresses, to discover their network numbers by locating a gateway and asking for this information, and to assign socket numbers in some systematic way not legislated by the internet protocol.

There are some important conventions associated with the use of network addresses. A distinguished value of the network number field refers to ‘‘this network’’ without identifying it. Such a capability is necessary for host initialization (since most hosts have no permanent local storage and consequently no a priori knowledge of the connected network number), and to permit communication to take place within a degenerate internet consisting of an unidentified local network with no gateways. A distinguished value of the destination host address is used to request a broadcast. Certain values of the socket number field refer, by convention, to ‘‘well-known sockets’’ associated with standard, widely-used services, as is done in the Arpanet.

The data field contains up to 532 data bytes. The selection of a standard maximum packet length must reflect many considerations: error rates, buffer requirements, and needs of specific applications. A reasonable value might range anywhere from 100 to 4000 bytes. In practice, much of the internet traffic consists of packets containing individual ‘‘pages’’ of 512 bytes each, reflecting the quantization of memory in most of our computers. But just carrying the data is not enough, since the packet should accommodate higher-level protocol overhead and some identifying information as well. Allowing 20 additional bytes for such purposes, we arrive at 532 bytes as the maximum size of the data field (a somewhat unconventional value in that it is not a power of two). Thus, there may be between 0 and 532 content bytes in a Pup, so its total length will range from 22 to 554 bytes. Pups longer than 554 bytes are not prohibited and may be carried by some networks, but no internetwork gateway is required to handle larger ones.

The optional software checksum is used for complete end-to-end coverage—it is computed as close to the source of the data and checked as close to the ultimate destination as is possible. This checksum protects a Pup when it isn’t covered by some network-specific technique, such as when it is sitting in a gateway’s memory or passing through a parallel I/O path. Most networks employ some sort of error checking on the serial parts of the channel, but parallel data paths in the interface and the I/O system often are not checked.

The checksum algorithm is intended to be straightforward to implement in software; it also allows incremental updating so that intermediate agents which modify a packet (gateways updating the hop count field, for example) can quickly update the checksum rather than recomputing it. The checksum may (but need not) be checked anywhere along a Pup’s route in order to monitor the internet’s integrity.

Accompanying the packet format defined at level 1 are the protocols for internetwork routing. Each host, whether or not it is a gateway, executes a routing procedure on every outgoing Pup, as illustrated in figure 4. This procedure decides, as a function of the Pup destination port field, upon which directly-connected network the Pup is to be transmitted (if there is more than one choice), and it yields an immediate destination host which is the address on that network of either the ultimate destination or some gateway believed to be closer to the destination. Each routing step employs the same algorithm based on local routing information, and each Pup is routed independently.

Routing information is maintained in a manner very similar to the Arpanet-style adaptive procedures [McQuillan, 1974]. The initial metric used for selecting routes is the ‘‘hop count’’—the number of intermediate networks between source and destination. The protocol for updating the routing tables involves exchanging Pups with neighboring gateways and rests logically at level 2 of the protocol hierarchy. This is an example of a connectionless protocol which doesn’t require perfectly reliable transmission for correct operation. Changes in internetwork topology may cause different gateways’ routing tables to become momentarily inconsistent, but the algorithm is stable in that the routing tables rapidly converge to a consistent state and remain that way until another change in topology occurs.

A host which is not a gateway still implements a portion of this level 2 routing update protocol: it initially obtains an internetwork routing table from a gateway on its directly-connected network, and it obtains updated information periodically. If there is more than one gateway providing connections to other networks, the host can merge their routing tables and thus be able to select the best route for packets directed to any network.

These protocols generally fall into two categories: those in which a connection is established for a sustained exchange of packets, and those in which individual packets are exchanged on a connectionless basis. Connection-style protocols usually transport data very reliably, and transparently.

EFTP: the Easy File Transfer Protocol. This is a very simple protocol for sending files. Each data Pup gives rise to an immediate acknowledgment, and there is at most one Pup outstanding at a time. This protocol is an indirect descendent of the one outlined in [Metcalfe & Boggs, 1976]. Its simplicity makes this piece of communication mechanism easy to include under conditions of very limited resources. For example, we have implemented a complete EFTP receiver in 256 words of assembly language, for use in a network-based bootstrap and down-line loading process.

Rendezvous & Termination Protocol (RTP). This is a general means to initiate, manage, and terminate connections in a reliable fashion [Sunshine & Dalal, 1978]. In normal use, an RTP user initiates a connection by communicating with a well-known socket at some server. That server will spawn a new port to actually provide the service, and the RTP will establish contact with this port. It employs a non-reusable connection identifier to distinguish among multiple instantiations of the same connection and to cope with delayed packets without making assumptions about maximum packet lifetimes. RTP also synchronizes Pup identifiers for use in managing the connection.

Byte Stream Protocol (BSP). This is a relatively sophisticated protocol for supporting reliable, sequenced streams of data. It provides for multiple outstanding packets from the source, and uses a moving window flow control procedure. User processes can place mark bytes in the stream to identify logical boundaries and can send out-of-band interrupt signals. RTP and BSP combined perform a function similar to that of the TCP, with which they share a certain degree of common ancestry [Cerf & Kahn, 1974; Postel, 1980].

Connectionless protocols do not attempt to maintain any long-term state; they usually don’t guarantee reliability, but leave it up to the designer to construct the most suitable system. Their simplicity and ease of implementation make them extremely useful.

Echo. A very simple protocol can be used to send test Pups to an echo server process, which will check them and send back a reply. Such servers are usually embedded in gateways and other server hosts, to aid in network monitoring and maintenance. The server is trivial to implement on top of the level 1 facilities.

Name lookup. Another server provides the mapping from string names of resources to internetwork addresses; this is accomplished by a single exchange of packets. This service is often addressed with a broadcast Pup, since it is used as the first step in locating resources. (The name lookup service itself, of course, must be located at a well-known address. To be useful, it must be widely available; therefore it is typically replicated at least once per network.)

Page-level file access. The Woodstock File Server (WFS), one of the family of file servers available on the internet, provides page-at-a-time access to a large file store [Swinehart et al., 1979]. The protocols used for this do not require establishment of a connection, but merely exchange request and response Pups that each carry both commands and file data. This arrangement supports random-access, transaction-oriented interactions of very high performance—frequently better than that obtained using local file storage, because the file server’s disks are much faster than those typically connected to personal computers.

Gateway monitoring and control. There is no single network control center, but individual gateways may be queried from a monitoring program run on any user machine. With suitable authentication, the user may assume remote control of the gateway so as to perform operations such as changing parameters and loading new versions of the software.

Other connectionless protocols are used to access a date and time server, an authentication server, and a mail check server integrated with an on-line message system. These protocols are designed to be as cheap as possible to implement (i.e., without connection overhead) so that such servers may be replicated extensively and accessed routinely without consuming excessive resources. For example, instances of some of these servers are present in all gateway hosts so as to maximize their availability.

Armed with a reasonable collection of data transport protocols at level 2, one can begin to evolve specific applications at level 3. These are supported by various function-oriented protocols [Crocker et al., 1972].

Telnet. Terminal access to remote hosts is provided with an internetwork Telnet protocol, which makes use of the combination of the Rendezvous & Termination Protocol (RTP) and the Byte Stream Protocol (BSP) at level 2. Using the notion of a virtual terminal, Telnet implementations map characteristics of actual terminals into a network-independent representation; a mark byte in the stream and an out-of-band interrupt, for example, are used to signal an ‘‘attention.’’ (This approach is a subset of the Arpanet Telnet protocol, without any of its options such as RCTE [Davidson, et al., 1977; Feinler & Postel, 1978].)

FTP. The RTP and BSP are again combined as the foundation for an internetwork File Transfer Protocol (FTP), supporting stream-oriented access to files. The underlying byte streams provide reliable communication, and the major task of FTP is to communicate commands and responses and to sort out different representations of data in different file systems. FTP implementations have been embedded within existing time-sharing systems, and also constitute the core of dedicated, high-capacity file servers.

Printing. Among the important shared resources in the internet are high-quality printing servers. Rather than using the fully developed BSP and FTP, the specialized task of sending unnamed, standard format document files to a printer makes use of the more restricted but much simpler EFTP.

CopyDisk. Given high-performance networks and simple gateways that can forward Pups among them efficiently, it is perfectly reasonable to copy entire disk packs through the internet. The CopyDisk protocol negotiates between the participating machines to ensure that the disks are compatible, and handles error recovery should something break down.

Remote graphics. Personal display-oriented computers such as the Alto can be used to provide a convivial front end for large programming systems such as Interlisp. The Alto Display protocol is used for exchanging descriptions of graphical structures as well as text; it is similar to the ARPA Network Graphics Protocol, but with extensions to support raster-scanned graphics [Sproull & Thomas, 1974; Teitelman, 1977; Sproull & Cohen, 1978].

As users create new applications, these systems tend to develop their own natural layering of function. Some may require new protocol designs in the existing hierarchy; the Pup architecture permits this degree of flexibility down to the level of the simple internetwork datagram. As we gain experience with new systems, common pieces of design will begin to emerge that might be of more general use; they will eventually find their way into an appropriate place in this hierarchy of communications protocols.