previous | contents | next

Section 5 ½ Networks 401

to provide remote terminal access to a centralized computing facility. Because of the local economics of leased common-carrier lines (telephone calls between different islands were charged at long-distance rates), an alternative interconnection approach was sought. The technology selected was packet switching via radio broadcast channels.

Two radio channels-a random-access channel for user-to-computer communication and a broadcast channel for computer-to-user communication-tie the remote terminals to the central site. A "Menehune" (Hawaiian for imp, hence Interface Message Processor, or IMP) receives the random-access channel packets for assembly for the Host. Packets are one-half (40 characters) or a whole (80 characters) terminal line in length. Individual terminals broadcast on the random-access channel whenever a line-terminating character is typed by the user. The error-check character in the packet is used not only to detect random-bit errors but also to detect errors in multiple simultaneous transmissions, which, with a high probability, will not produce a legal packet whose bits and error-check character match. If a terminal does not receive a positive ACK within a specified time, the terminal will retransmit the packet. Since the packet may not be acknowledged because of contention on the random-access channel, the terminals wait a randomly selected period before retransmitting to avoid endless contention for the random-access channel. The ALOHA Network is thus a contention network.

The Host returns information via the broadcast channel, to which all terminals are listening. Chapter 25 summarizes the design decisions and experiences with the ALOHA Network. Suggestions for improving the efficiency of the random-access channel are also considered. The random-access channel becomes clogged in high-traffic situations, since all packets are garbled due to contention and no packets are received intact. It has been calculated that the channel capacity (maximum throughput) of useful information is 1/2e, or 0.184, for a pure ALOHA technique. A slotted ALOHA technique for satellite channels has been proposed in which transmission can be started only at discrete intervals. The channel capacity then rises to 1/e, or 0.368.

Chapter 25 also suggests that the random-access and broadcast channels be combined. This not only saves radio hardware but also allows terminals to listen to the random-access channel and postpone transmission if the channel is busy. This may increase throughput by a factor of 3 to 5. This single-broadcast channel concept is employed in the ETHERNET.


With the advent of cheap minicomputers, terminals, and intelligent terminals, there are more and more situations where a local network is required for intercommunication, resource sharing, and so forth. Further, because of the mobility of individuals and organizations, such a network has to be very flexible and easily modifiable.

The ETHERNET was evolved to solve these problems. It consists of stations interconnected with a passive broadcast medium, the ether. Based on the ALOHA Network packet-switching technology, computer network stations broadcast into the ether. All stations listen and the desired destination picks off the packet by recognizing its unique address. If the channel is in use, stations do not broadcast. Contention is detected by comparing what was placed on the ether to what the station hears from the ether. (Hence the ETHERNET is also a contention network.) If there is a mismatch, the station can abort the packet and try again later. This prevents the ALOHA Network's lengthy time out for lack of positive acknowledgment. Further, contentions are limited to a small window following the completion of the previous packet. Thus, in the limit for small packets, the channel capacity is that of the slotted ALOHA technique. For longer packets, channel capacity approaches 1.0, since contentions are so short.

In the case of high network load, the random retransmission time is lengthened to automatically adapt to congestion. It should be noted that the ETHERNET is only a line protocol, in that packets have only a high probability of successful delivery. Subnet- and Host-level protocols can be built on top of the ETHERNET protocol by the use of concepts such as positive acknowledgment on receipt of a packet. However, the ETHERNET does provide routing and flow-control functions which traditionally have appeared only at the higher levels of protocols.


As our dependency on computers grows, network technology will be even more important than it is today. Indeed, with the advent of the cheap microprocessor, structures that were once designed as a single logical entity (e.g., the disk controller) are actually a network of several microprocessors.



Aupperle [1973]; Doll [1974]; Everett, Zracket, and Benington [1957]; Falk and McQuillan [1977]; Greene and Pooch [1977]; Hargraves [1974]; IBM [1974]; Kleinrock and Naylor [1974]; Kleinrock, Naylor, and Opderbeck [1976]; Knight [1972]; McCalley and Barrett [1978]; McQuillan, Crowther, Cosell, Walden, and Heart [1972]; Roberts and Wessler [1970]; Schwartz [1977].

previous | contents | next