`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.
`
`* 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
`
`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-
`
`are preferable
`munications
`communications.
`
`to conventional wire
`
`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}: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 seme fundamental differences
`
`PETITIONERS 1066-0001
`|PR2016-OO758
`
`PETITIONERS 1066-0001
`IPR2016-00758
`
`
`
`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—cg, 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
`
` CENTRAL
`
`COMPUTER
`
`Figure l—THE ALOHA SYSTEM
`
`(Figure 1).
`interface computer
`channel via a small
`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.4r7 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-
`
`PETITIONERS 1066-0002
`|PR2016—OO758
`
`PETITIONERS 1066-0002
`IPR2016-00758
`
`
`
`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 16 active consoles in the ALOHA random
`access communication system.
`We define r as the duration of a packet. In THE
`ALOHA SYSTEM 1 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
`
`* 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 diflerent.
`
`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 band.
`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 is”
`2~32 z 10~9.
`
`Since error detection is a trivial operation to implement,10
`the use of such a code is consistent with the require—
`
`mrlllDrh-D-
`
`[J
`
`I
`
`b F
`
`igure 2—ALOHA communication multiplexing
`
`W,
`
`PETITIONERS 1066-0003
`|PR2016—OO758
`
`PETITIONERS 1066-0003
`IPR2016-00758
`
`
`
`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=k)\
`
`where r is the average number of message packets per
`unit time from the 10 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
`
`because of the retransmissions, it is strictly speaking
`not even mathematically consistent. If the retrans—
`mission delay is large compared to 7, 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
`7- or less seconds
`before or 1' 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)].
`
`(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
`
`RD — exp(——2Rr)]
`
`so that we have
`
`r1=1.
`
`or
`
`R =r+R[1 — exp(—-2R-r)]
`
`Accordingly we refer to W 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 16 active
`users. Then if there are any retransmissions we must
`have R> r. We define R'r as the channel trafiic 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 R1 as a function of the
`channel utilization, M.
`times of the point
`Now assume the interarrival
`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,
`
`1‘1 = 1316—21".
`
`(2)
`
`Equation (2) is the relationship we seek between the
`channel utilization 1‘1 and the channel
`traffic RT. In
`
`Figure 3 we plot R1- versus r7.
`
`chunml
`traffic
`
`RT
`
`.IO
`.05
`channel utillzoflon rr
`
`.55
`
`Joe
`
`Figure 3—Channel utilization vs channel traffic
`
`PETITIONERS 1066-0004
`|PR2016—OO758
`
`PETITIONERS 1066-0004
`IPR2016-00758
`
`
`
`THE ALOHA SYSTEM 285
`
`Note from Figure 3 that the channel utilization
`reaches a maximum value of 1/26=0.186. For
`this
`value of r1 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 can support.
`Setting
`
`rr = low = 1/2e
`
`‘we solve for the maximum number of active users
`
`km” = (2ek7)—1.
`
`A conservative estimate of A 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 1' equal to 34 milliseconds we get
`
`km“ = 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
`the operation of THE ALOHA
`The analysis of
`SYSTEM random access scheme provided above has
`been checked by two separate simulations of the sys-
`tem.12r 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.
`
`REFERENCES
`1 N ABRAMSON et a1
`1969 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 V012 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 N0 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 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
`11 H H J LIAO
`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
`
`PETITIONERS 1066-0005
`|PR2016-OO758
`
`PETITIONERS 1066-0005
`IPR2016-00758
`
`