THE ALOHA SYSTEM—Another alternative for computer
`communications*
`
`by NORMAN ABRAMSON
`
`University of Hawaii
`Honolulu, Hawaii
`
`INTRODUCTION
`
`In September 1968 the Uhiversity 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
`programs 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.
`
`* 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
`
`WIRE COMMUNICATIONS AND RADIO
`COMMUNICATIONS FOR COMPUTERS
`
`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
`
`

`

`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.' 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.' 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.
`
`THE ALOHA SYSTEM
`The central computer of THE ALOHA SYSTEM
`(an IBM 360/65) is linked to the radio communication
`
`ECaRRaLE
`xR1 J
`
` vi
`
` C0160LE
`TRANUNT
`
`CENTRAL
`
`COMPUTER
`
`yM
`
`]!0M
`
`IIP PIID. •
`
`DATA
`
`NCDEN
`
`RECEIVE
`
`DATA
`
`NDDEN
`
`TRA"WrrER
`
`RECEIVER
`
`N0. L
`
`CggOL[
`N,, w
`
`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.''' 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-
`
`

`

`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.' Thus if we assume all
`error patterns are equally likely the probability that a
`given error pattern will not be detected by the code isle
`2-82 10-9.
`Since error detection is a trivial operation to implement,''
`the use of such a code is. consistent with the require-
`
`Nor I
`
`2
`
`sum I.nnn nrtni n' (cid:9)
`tie. —¤
`
`Intafsnne*t (cid:9)
`npNitlom
`
`n
`
`Figure 2—ALOHA communication multiplexing
`
`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 -r 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." In the next section we compute the
`average number of active consoles which may 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
`
`• 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.
`
`

`

`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.
`
`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 A 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
`
`r=kA
`
`where r is the average number of message packets per
`unit time from the k active users. Let r 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
`
`"=I.
`
`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 . Rr as a function of the
`channel utilization, rr.
`Now assume the interarrival times of the point
`process defined 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,
`
`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 r or less seconds
`before or r or less seconds after the start of the given
`packet. Hence the probability that a given message
`packet or retransmission will be repeated is
`[1— exp(- 2Rr)]. (cid:9)
`(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[1— exp( -2Rr)]
`
`so that we have
`R=r+R[1— exp( -2Rr)]
`
`or
`
`(2)
`rr = Rre-aR*. (cid:9)
`Equation (2) is the relationship we seek between the
`channel utilization rr and the channel traffic Rr. In
`figure 3 we plot Rr versus rr.
`
`channel- .50
`traffic
`Rr (cid:9)
`
`.40
`.30
`.20
`.10
`
`.10 (cid:9)
`.05 (cid:9)
`channel utilization rr
`
`J5 (cid:9)
`
`.186
`
`Figure 3—Channel utilization vs channel traffic
`
`

`

`Note from Figure 3 that the channel utilization
`reaches a maximum value of 1/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=1/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 cant support.
`Setting
`
`rr = kAr =1/2e
`
``we solve for the maximum number of active users
`
`kma$ = (2eXr)—'.
`
`A conservative estimate of X would be 1/60 (seconds) —',
`corresponding to each active user sending a • message
`packet at an average rate of one every 60 seconds.
`With r equal to 34 milliseconds we get
`
`kmsx = 324. (cid:9)
`
`(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.'Q. 18 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.
`
`THE ALOHA SYSTEM 285
`
`1 N ABRAMSON et al
`1989 annual report THE ALOHA SYSTEM
`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 Volt No 1 January 1965
`4 L G ROBERTS
`Multiple computer networks and computer communication
`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]) STUBBS
`A study of multiaccess computer communications
`Proceedings of the Spring Joint Computer Conference'
`pp 491-504 AFIPS Press 1969
`7 Initial design for interface message processors for the ARPA
`computer network
`Report No 1763 Bolt Beranek and Newman Inc January
`1969
`8 R BINDER
`Multiplexing in THE ALOHA SYSTEM:
`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
`11HHJLIAO
`Random access discrete address multiplexing communications
`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 ALOHA
`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
`
`

`

`