THE ALOHA SYSTEM—Another alternative for computer
`communications*
`
`by NORMAN ABRAMSON
`
`University of Hawaii
`Honolulu, Hawaii
`
`INTRODUCTION
`
`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(cid:173)
`TEM—under development as part of that research
`program1 and discuss some advantages of radio com(cid:173)
`munications over conventional wire communications
`for interactive users of a large computer system. Al(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`space Research (SRMA) under Contract Number F44620-69-C-
`0030, a Project THEMIS award.
`
`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(cid:173)
`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(cid:173)
`munications are preferable
`to conventional wire
`communications.
`The reasons for widespread use of wire communica(cid:173)
`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(cid:173)
`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(cid:173)
`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
`
`281
`
`Dish
`Exhibit 1048, Page 1
`
`

`
`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(cid:173)
`puter system comes in a sequence of bursts with ex(cid:173)
`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(cid:173)
`centration may alleviate this difficulty to some extent.
`When efficient data concentration is not feasible how(cid:173)
`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(cid:173)
`ments of data communications for time-shared systems
`and voice communications is the asymmetric nature
`of the communications required for the user of inter(cid:173)
`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(cid:173)
`tion for computers and voice communication. In addi(cid:173)
`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(cid:173)
`connects. Meaningful statistics on both of these prob(cid:173)
`lems are difficult to obtain and vary from location to
`location, but there is little doubt that in many loca(cid:173)
`tions the reliability of wire communications is well be(cid:173)
`low that of the remainder of the computer-communica(cid:173)
`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
`
`CENTRAL
`
`COMPUTER
`
`IBM
`
`360/63
`
`<h
`
`HP 2115 A
`
`TRANSMIT
`
`DATA
`
`MODEM
`
`RECEIVE
`
`DATA
`
`MODEM
`
`TRANSMnrTER
`
`RECEIVER
`
`CONSOLE
`
`No. 1
`
`CONSOLE
`
`No. 2
`
`* *v
`^^*
`
`CONSOLE
`
`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 I MP (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 T HE 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(cid:173)
`HUNE to the consoles provides no problems. Since
`the transmitter can be controlled and buffering per(cid:173)
`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(cid:173)
`HUNE however are not capable of being multiplexed
`in such a direct manner. If standard orthogonal multi(cid:173)
`plexing techniques (such as frequency or time multi(cid:173)
`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-
`
`Dish
`Exhibit 1048, Page 2
`
`

`
`soles such a scheme will lead to the same sort of in(cid:173)
`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-
`
`uMr
`
`I 0_ n
`
`n
`
`uHr 2
`
`user k
`
`a
`n nr
`
`n
`
`nnn nrin
`repetitions U^
`
`interference
`
`n n
`
`time
`
`Figure 2—ALOHA communication multiplexing
`
`THE ALOHA SYSTEM
`
`283
`
`ment for simple communication equipment at the con(cid:173)
`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(cid:173)
`ceived without error it is acknowledged by the MENE(cid:173)
`HUNE. After transmitting a packet the transmitting
`console waits a given amount of time for an acknowl(cid:173)
`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(cid:173)
`seconds; of this total 29 milliseconds will be needed for
`transmission of the 704 bits and the remainder for re(cid:173)
`ceiver synchronization. Note the overlap of two packets
`from different consoles in Figure 2. For analysis pur(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`fere with each other we must make sure the retransmission delays
`in the two consoles are different.
`
`Dish
`Exhibit 1048, Page 3
`
`

`
`284
`
`Fall Joint Computer Conference, 1970
`
`channel even though the users are geographically dis(cid:173)
`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(cid:173)
`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 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
`
`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(cid:173)
`sages into the available channel space perfectly with
`absolutely no space between messages we would have
`
`rr = l.
`
`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(cid:173)
`nential. This assumption, of course, is only an approxi(cid:173)
`mation to the true arrival time distribution. Indeed,
`
`because of the retransmissions, it is strictly speaking
`not even mathematically consistent. If the retrans(cid:173)
`mission delay is large compared to r, however, and the
`number of retransmissions is not too large this assump(cid:173)
`tion will be reasonably close to the true distribution.
`Moreover, computer simulations of this channel indi(cid:173)
`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(cid:173)
`sage packets or retransmissions) in a time interval T
`is exp(-RT).
`Using this assumption we can calculate the prob(cid:173)
`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
`
`[ l - e x p ( - 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
`
`fl[l-exp(-2flr)]
`
`so that we have
`
`R=r+R[l-
`
`exp(-2#T)]
`
`or
`
`rT = Rre~iRT.
`
`(2)
`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.
`
`.10
`.05
`channel utilization rr
`
`Figure 3—Channel utilization vs channel traffic
`
`Dish
`Exhibit 1048, Page 4
`
`

`
`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 T HE ALOHA SYSTEM we may use this result
`to calculate the maximum number of interactive users
`the system can support.
`Setting
`
`TT = kXr = l/2e
`
`we solve for the maximum number of active users
`
`&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
`
`&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(cid:173)
`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(cid:173)
`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.
`
`THE ALOHA SYSTEM
`
`285
`
`communication
`
`REFERENCES
`1 N ABRAMSON et al
`SYSTEM
`1969 annual report THE ALOHA
`University of Hawaii Honolulu Hawaii January 1970
`2 M M GOLD L L SELWYN
`interest
`Real time computer communications and the public
`Proceedings of the Fall Joint Computer Conference
`pp 1473-1478 AFIPS Press 1968
`3 R M FANO
`The MAC system: The computer utility approach
`I E EE 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 K E M E NY 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
`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 B I N D ER
`SYSTEM:
`in THE ALOHA
`Multiplexing
`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 P E T E R S ON
`Cyclic codes for error detection
`Proceedings I RE 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 T R I P A T HI
`Simulation of a random access discrete address communication
`system
`ALOHA SYSTEM Technical Note 70-1 University of
`Hawaii Honolulu Hawaii April 1970
`
`communications
`
`ALOHA
`
`Dish
`Exhibit 1048, Page 5
`
`

`
`Dish
`Exhibit 1048, Page 6