THE ALOHA SYSTEM—Another alternative for computer communications* - PDF Document

Presentation Transcript

  1. THE ALOHA SYSTEM—Another alternative for computer communications* by NORMAN ABRAMSON University of Hawaii Honolulu, Hawaii INTRODUCTION WIRE COMMUNICATIONS AND RADIO COMMUNICATIONS FOR COMPUTERS In September 1968 the University of Hawaii began work on a research program to investigate the use of radio communications for computer-computer and console-computer links. In this report we describe a remote-access computer system—THE ALOHA SYS- TEM—under development as part of that research program1 and discuss some advantages of radio com- munications over conventional wire communications for interactive users of a large computer system. Al- though THE ALOHA SYSTEM research program is composed of a large number of research projects, in this report we shall be concerned primarily with a novel form of random-access radio communications developed for use within THE ALOHA SYSTEM. The University of Hawaii is composed of a main campus in Manoa Valley near Honolulu, a four year college in Hilo, Hawaii and five two year community colleges on the islands of Oahu, Kauai, Maui and Hawaii. In addition, the University operates a number of research institutes with operating units distributed throughout the state within a radius of 200 miles from Honolulu. The computing center on the main campus operates an IBM 360/65 with a 750 K byte core memory and several of the other University units operate smaller machines. A time-sharing system UHTSS/2, written in XPL and developed as a joint project of the Univer- sity Computer Center and THE ALOHA SYSTEM under the direction of W. W. Peterson is now operating. THE ALOHA SYSTEM plans to link interactive com- puter users and remote-access input-output devices away from the main campus to the central computer via UHF radio communication channels. At the present time conventional methods of remote access to a large information processing system are limited to wire communications—either leased lines or dial-up telephone connections. In some situations these alternatives provide adequate capabilities for the de- signer of a computer-communication system. In other situations however the limitations imposed by wire communications restrict the usefulness of remote access computing.2 The goal of THE ALOHA SYSTEM is to provide another alternative for the system designer and to determine those situations where radio com- munications are preferable to conventional wire communications. The reasons for widespread use of wire communica- tions in present day computer-communication systems are not hard to see. Where dial-up telephones and leased lines are available they can provide inexpensive and moderately reliable communications using an existing and well developed technology.3,4 For short distances the expense of wire communications for most applica- tions is not great. Nevertheless there are a number of characteristics of wire communications which can serve as drawbacks in the transmission of binary data. The connect time for dial-up lines may be too long for some applications; data rates on such lines are fixed and limited. Leased lines may sometimes be obtained at a variety of data rates, but at a premium cost. For communication links over large distances (say 100 miles) the cost of com- munication for an interactive user on an alphanumeric console can easily exceed the cost of computation.5 Finally we note that in many parts of the world a reliable high quality wire communication network is not available and the use of radio communications for data transmission is the only alternative. There are of course some fundamental differences * THE ALOHA SYSTEM is supported by the Office of Aero- space Research (SRMA) under Contract Number F44620-69-C- 0030, a Project THEMIS award. 281

  2. 282 Fall Joint Computer Conference, 1970 between the data transmitted in an interactive time- shared computer system and the voice signals for which the telephone system is designed.6 First among these differences is the burst nature of the communication from a user console to the computer and back. The typical 110 baud console may be used at an average data rate of from 1 to 10 baud over a dial-up or leased line capable of transmitting at a rate of from 2400 to 9600 baud. Data transmitted in a time-shared com- puter system comes in a sequence of bursts with ex- tremely long periods of silence between the bursts. If several interactive consoles can be placed in close proximity to each other, multiplexing and data con- centration may alleviate this difficulty to some extent. When efficient data concentration is not feasible how- ever the user of an alphanumeric console connected by a leased line may find his major costs arising from communication rather than computation, while the communication system used is operated at less than 1 percent of its capacity. Another fundamental difference between the require- ments of data communications for time-shared systems and voice communications is the asymmetric nature of the communications required for the user of inter- active alphanumeric consoles. Statistical analyses of existing systems indicate that the average amount of data transmitted from the central system to the user may be as much as an order of magnitude greater than the amount transmitted from the user to the central system.6 For wire communications it is usually not possible to arrange for different capacity channels in the two directions so that this asymmetry is a further factor in the inefficient use of the wire communication channel. The reliability requirements of data communications constitute another difference between data communica- tion for computers and voice communication. In addi- tion to errors in binary data caused by random and burst noise, the dial-up channel can produce connection problems—e.g., busy signals, wrong numbers and dis- connects. Meaningful statistics on both of these prob- lems are difficult to obtain and vary from location to location, but there is little doubt that in many loca- tions the reliability of wire communications is well be- low that of the remainder of the computer-communica- tion system. Furthermore, since wire communications are usually obtained from the common carriers this portion of the overall computer-communication system is the only portion not under direct control of the system designer. CONSOLE No. 1 CONSOLE TRANSMIT No. 2 DATA CENTRAL TRANSMnrTER MODEM COMPUTER <h HP 2115 A RECEIVE RECEIVER * * v ^^* DATA IBM 360/63 CONSOLE MODEM No. k Figure 1—THE ALOHA SYSTEM channel via a small interface computer (Figure 1). Much of the design of this multiplexor is based on the design of the Interface Message Processors (IMP's) used in the ARPA computer net.4-7 The result is a Hawaiian version of the IMP (taking into account the use of radio communications and other differences) which has been dubbed the MENEHUNE (a legendary Hawaiian elf). The HP 2115A computer has been selected for use as the MENEHUNE. It has a 16-bit word size, a cycle time of 2 microseconds and an 8K- word core storage capacity. Although THE ALOHA SYSTEM will also be linked to remote-access input- output devices and small satellite computers through the MENEHUNE, in this paper we shall be concerned with a random access method of multiplexing a large number of low data rate consoles into the MENEHUNE through a single radio communication channel. THE ALOHA SYSTEM has been assigned two 100 KHZ channels at 407.350 MHZ and 413.475 MHZ. One of these channels has been assigned for data from the MENEHUNE to the remote consoles and the other for data from the consoles to the MENEHUNE. Each of these channels will operate at a rate of 24,000 baud. The communication channel from the MENE- HUNE to the consoles provides no problems. Since the transmitter can be controlled and buffering per- formed by the MENEHUNE at the Computer Center, messages from the different consoles can be ordered in a queue according to any given priority scheme and transmitted sequentially. Messages from the remote consoles to the MENE- HUNE however are not capable of being multiplexed in such a direct manner. If standard orthogonal multi- plexing techniques (such as frequency or time multi- plexing) are employed we must divide the channel from the consoles to the MENEHUNE into a large number of low speed channels and assign one to each console, whether it is active or not. Because of the fact that at any given time only a fraction of the total number of consoles in the system will be active and because of the burst nature of the data from the con- THE ALOHA SYSTEM The central computer of THE ALOHA SYSTEM (an IBM 360/65) is linked to the radio communication

  3. THE ALOHA SYSTEM 283 ment for simple communication equipment at the con- soles. The possibility of using the same code for error correction at the MENEHUNE will be considered for a later version of THE ALOHA SYSTEM. The random access method employed by THE ALOHA SYSTEM is based on the use of this error detecting code. Each user at a console transmits packets to the MENEHUNE over the same high data rate channel in a completely unsynchronized (from one user to another) manner. If and only if a packet is re- ceived without error it is acknowledged by the MENE- HUNE. After transmitting a packet the transmitting console waits a given amount of time for an acknowl- edgment; if none is received the packet is retransmitted. This process is repeated until a successful transmission and acknowledgment occurs or until the process is terminated by the user's console. A transmitted packet can be received incorrectly because of two different types of errors; (1) random noise errors and (2) errors caused by interference with a packet transmitted by another console. The first type of error is not expected to be a serious problem. The second type of error, that caused by interference, will be of importance only when a large number of users are trying to use the channel at the same time. Interference errors will limit the number of users and the amount of data which can be transmitted over this random access channel. In Figure 2 we indicate a sequence of packets as transmitted by k active consoles in the ALOHA random access communication system. We define T as the duration of a packet. In THE ALOHA SYSTEM r will be equal to about 34 milli- seconds; of this total 29 milliseconds will be needed for transmission of the 704 bits and the remainder for re- ceiver synchronization. Note the overlap of two packets from different consoles in Figure 2. For analysis pur- poses we make the pessimistic assumption that when an overlap occurs neither packet is received without error and both packets are therefore retransmitted.* Clearly as the number of active consoles increases the number of interferences and hence the number of re- transmissions increases until the channel clogs up with repeated packets.11 In the next section we compute the average number of active consoles which may be sup- ported by the transmission scheme described above. Note how the random access communication scheme of THE ALOHA SYSTEM takes advantage of the nature of the radio communication channels as opposed to wire communications. Using 'the radio channel as we have described each user may access the same soles such a scheme will lead to the same sort of in- efficiencies found in a wire communication system. This problem may be partly alleviated by a system of central control and channel assignment (such as in a telephone switching net) or by a variety of polling techniques. Any of these methods will tend to make the communication equipment at the consoles more complex and will not solve the most important problem of the communication inefficiency caused by the burst nature of the data from an active console. Since we expect to have many remote consoles it is important to minimize the complexity of the communication equipment at each console. In the next section we describe a method of random access communications which allows each console in THE ALOHA SYSTEM to use a common high speed data channel without the necessity of central control or synchronization. Information to and from the MENEHUNE in THE ALOHA SYSTEM is transmitted in the form of "packets," where each packet corresponds to a single message in the system.8 Packets will have a fixed length of 80 8-bit characters plus 32 identification and control bits and 32 parity bits; thus each packet will consist of 704 bits and will last for 29 milliseconds at a data rate of 24,000 baud. The parity bits in each packet will be used for a cyclic error detecting code.9 Thus if we assume all error patterns are equally likely the probability that a given error pattern will not be detected by the code is10 2~32^10-9. Since error detection is a trivial operation to implement,10 the use of such a code is consistent with the require- n uMr I 0_ n a n uHr 2 n nr user k n n time nnn nrin repetitions U^ * In order that the retransmitted packets not continue to inter- fere with each other we must make sure the retransmission delays in the two consoles are different. interference Figure 2—ALOHA communication multiplexing

  4. 284 Fall Joint Computer Conference, 1970 channel even though the users are geographically dis- persed. The random access communication method used in THE ALOHA SYSTEM may thus be thought of as a form of data concentration for use with geo- graphically scattered users. because of the retransmissions, it is strictly speaking not even mathematically consistent. If the retrans- mission delay is large compared to r, however, and the number of retransmissions is not too large this assump- tion will be reasonably close to the true distribution. Moreover, computer simulations of this channel indi- cate that the final results are not sensitive to this distribution. Under the exponential assumption the probability that there will be no events (starts of mes- sage packets or retransmissions) in a time interval T is exp(-RT). Using this assumption we can calculate the prob- ability that a given message packet or retransmission will need to be retransmitted because of interference with another message packet or retransmission. The first packet will overlap with another packet if there exists at least one other start point T or less seconds before or T or less seconds after the start of the given packet. Hence the probability that a given message packet or retransmission will be repeated is RANDOM ACCESS RADIO COMMUNICATIONS We may define a random point process for each of the k active users by focusing our attention on the starting times of the packets sent by each user. We shall find it useful to make a distinction between those packets transmitting a given message from a console for the first time and those packets transmitted as repetitions of a message. We shall refer to packets of the first type as message packets and to the second type as repetitions. Let X be the average rate of occurrence of message packets from a single active user and assume this rate is identical from user to user. Then the random point process consisting of the starting times of message packets from all the active users has an average rate of occurrence of [l-exp(-2#r)]. (1) Finally we use (1) to relate R, the average number of message packets plus retransmissions per unit time to r, the average number of message packets per unit time. Using (1) the average number of retransmissions per unit time is given by r = k\ where r is the average number of message packets per unit time from the k active users. Let T be the duration of each packet. Then if we were able to pack the mes- sages into the available channel space perfectly with absolutely no space between messages we would have fl[l-exp(-2flr)] so that we have R=r+R[l- exp(-2#T)] rr = l. or rT = Rre~iRT. (2) Accordingly we refer to rr as the channel utilization. Note that the channel utilization is proportional to k, the number of active users. Our objective in this section is to determine the maximum value of the channel utilization, and thus the maximum value of k, which this random access data communication channel can support. Define R as the average number of message packets plus retransmissions per unit time from the k active users. Then if there are any retransmissions we must have R>r. We define Rr as the channel traffic since this quantity represents the average number of message packets plus retransmissions per uni ttime multiplied by the duration of each packet or retransmission. In this section we shall calculate RT as a function of the channel utilization, rr. Now assume the interarrival times of the point process denned by the start times of all the message packets plus retransmissions are independent and expo- nential. This assumption, of course, is only an approxi- mation to the true arrival time distribution. Indeed, Equation (2) is the relationship we seek between the channel utilization rr and the channel traffic RT. In Figure 3 we plot Rr versus rr. .05 channel utilization rr .10 Figure 3—Channel utilization vs channel traffic

  5. THE ALOHA SYSTEM 285 Note from Figure 3 that the channel utilization reaches a maximum value of l/2e=0.186. For this value of rr the channel traffic is equal to 0.5. The traffic on the channel becomes unstable at rr =l/2e and the average number of retransmissions becomes unbounded. Thus we may speak of this value of the channel utilization as the capacity of this random access data channel. Because of the random access feature the channel capacity is reduced to roughly one sixth of its value if we were able to fill the channel with a continuous stream of uninterrupted data. For THE ALOHA SYSTEM we may use this result to calculate the maximum number of interactive users the system can support. Setting REFERENCES 1 N ABRAMSON et al 1969 annual report THE ALOHA University of Hawaii Honolulu Hawaii January 1970 2 M M GOLD L L SELWYN Real time computer communications and the public interest Proceedings of the Fall Joint Computer Conference pp 1473-1478 AFIPS Press 1968 3 R M FANO The MAC system: The computer utility approach IEEE Spectrum Vol 2 No 1 January 1965 4 L G ROBERTS Multiple computer networks and computer ARPA report Washington D C June 1967 5 J G KEMENY T E KURTZ Dartmouth time-sharing Science Vol 162 No 3850 p 223 October 1968 6 P E JACKSON C D STUBBS A study of multiaccess computer Proceedings of the Spring Joint Computer Conference pp 491-504 AFIPS Press 1969 7 Initial design for interface message processors for the computer network Report No 1763 Bolt Beranek and Newman Inc January 1969 8 R BINDER Multiplexing in THE ALOHA MENEHUNE-KEIKI design considerations ALOHA SYSTEM Technical Report B69-3 University of Hawaii Honolulu Hawaii November 1969 9 W W PETERSON E J WELDON JR Error-correcting codes—Second edition John Wiley & Sons New York New York 1970 10 D T BROWN W W PETERSON Cyclic codes for error detection Proceedings IRE Vol 49 pp 228-235 1961 11 H H J LIAO Random access discrete address multiplexing for THE ALOHA SYSTEM ALOHA SYSTEM Technical Note 69-8 University of Hawaii Honolulu Hawaii August 1969 12 W H BORTELS Simulation of interference of packets in THE SYSTEM ALOHA SYSTEM Technical Report B70-2 University of Hawaii Honolulu Hawaii March 1970 13 P TRIPATHI Simulation of a random access discrete address communication system ALOHA SYSTEM Technical Note 70-1 University of Hawaii Honolulu Hawaii April 1970 SYSTEM communication communications TT = kXr = l/2e we solve for the maximum number of active users ARPA &max=(2eXT)-1. A conservative estimate of X would be 1/60 (seconds)-1, corresponding to each active user sending a message packet at an average rate of one every 60 seconds. With T equal to 34 milliseconds we get SYSTEM: &max = 324. (3) Note that this value includes only the number of active users who can use the communication channel simultaneously. In contrast to usual frequency or time multiplexing methods while a user is not active he con- sumes no channel capacity so that the total number of users of the system can be considerably greater than indicated by (3). The analysis of the operation of THE ALOHA SYSTEM random access scheme provided above has been checked by two separate simulations of the sys- tem.12-13 Agreement with the analysis is excellent for values of the channel utilization less than 0.15. For larger values the system tends to become unstable as one would expect from Figure 3. communications ALOHA