Dr. Lawrence G. Roberts
ALOHA PACKET SYSTEM WITH AND WITHOUT
SLOTS AND CAPTURE*
Telenet Communications Corporation
Dr. Lawrence G. Roberts
FM receivers will track the strongest of many signals if the power of the next to strongest is down by 1.5- 3 db, a spec. called the capture ratio. Two major factors affect the power received; the 1/ r ² distance factor and random individual power variations. The distance factor is major whereas the individual power levels are usually less than 1.5 - 3 db. Since variation will help guarantee that one signal is captured and since individual variations will probably not help much, we will look only at distance variation.
Assuming the receiver is surrounded by an equal density population of consoles within a circle of radius R, the only consoles which can interfere with a given station at radius r, are the stations within the circle of radius ß ¯½ r.
Define: γ = The total bit rate being transmitted by all stations as a fraction of the total bandwidth.
σ = The actual bit rate fraction being received correctly.
q = Probability of a packet being received correctly
Thus: σ = γq
To compute q for the average station given a transmit rate γ is the task.
There are two cases, asynchronous and synchronous. In both cases we assume a Poisson point process for the totality of stations wanting to start packets of length T seconds at random time with a rate λ γ/T. Thus, the probability of no conflict within a time (mT) is:
However, if only a fraction k of the stations are in the proper position to prohibit your being captured, the poisson rate is reduced by k. At a given radius r, the interfacing stations are those in the area πr²/β whereas the total area is πR². Thus, the fraction of stations which would cause conflict is the area ratio. Thus:
The number of stations at any radius r increases linearly with as the circumference increases. The probability density is therefore:
Now, to compute the average q we must integrate the product p(r) q(r) over r out to R√β and p(r)qo from R√βR, since here all stations interfere.
Having found the average q, the σ = γq relationship will give us σ:
Note that this is the linear combination of two solutions, the solution for no capture (when β=0) and the solution for full capture, where one packet is always received correctly.
Now it is necessary to look separately at the asynchronous and synchronous cases to determine m.
A given packet will come into conflict with packets starting within a period 2T since each packet has length T.
Thus, as was derived by University of Hawaii, m=2.
Packets are always put into slots. Each station keeps a clock which counts off slot times and is resynchronized by observing other packets. The slots must have a slightly longer T to prevent errors but this factor will be considered later. The period of packet starting times giving rise to a transmission in a given slot is just the previous slot time. Thus, the Poisson period is T (m=l).
Note that these two formulas are identical under the following substitutions:
Thus, slot solutions are good for both, keeping in mind that for asynchronous channel use the rates are 1/2 that of the synchronous case. That is, for any given channel bandwidth and capture ratio the peak rate achievable, or the rate at a given delay (dependent on ?/s) will be only half as good in the asynchronous case as if slots are defined. Slot padding will mean some of this advantage is lost but unless the slots become twice the packet size the slot technique is significantly better.
Other Population Densities
If the population density of stations is not uniform within a circle, the next most realistic ground based case is that of a long narrow strip of land or a circular situation with population density decreasing with radius (like most cities). Both cases result in the same distribution, so consider the long strip of land:
Therefore, the solution is identical except that √β is substituted for β, improving the situation since the capture ratio required for a given performance can be twice that of the previous case.
The worst case is typified by a satellite situation where all stations are almost equidistant from each other (via the satellite). In the satellite case capture can be presumed impossible (β=0), unless capture ratios considerably better than 1.5 db can be achieved (1.5 db = the power ratio of the extreme case)
Maximum s for SlotsExcept for the unrealizable case where the capture ratio = 0 (β = ∞) in which the maximum σ =1 at γ=∞, there is a true maxima for σ.
The delay encountered by a packet is initially the channel and packet transmission delay assuming no conflict. Call this delay A. Next, if one or more retransmissions occur, each takes some time R from transmission to subsequent retransmission. Since there are (γ/σ) total transmissions on the average, the total delay is: on the average, the total delay is:
Satellite Delay For a satellite the initial delay, A, is the up-down satellite delay (C = .27 sec) plus the packet time, T.
A = C + T
Retransmission occurs after seeing your own down signal being in conflict, and waiting randomly over 10 packet times to avoid direct reconf1ict.
Typical times for a 50 KB channel, 1400 bit packets are:
Ground Ratio Delay Here the propagation delay, C, is much less but the same rule holds for A.
A = C + T
The retransmission can only occur after acknowledgment. However, this can always be sent within one packet time (ave = 1/2 T). Two transmission delays occur, however, and a random wait over 9 packet times is assumed.
Typical time for 50 KB, 1400 bit packets at distances under l00 miles are:
When σ is pushed to the maximum for any variant, the system is dynamically unstable, as it is if γ is somehow pushed beyond the second solution of the σ,γequation. Thus, an operating point must be chosen below the maximum σ point, which is dynamically stable and has a reasonable delay. A convenient point to pick, both for operation and for discussing the capacity of the system, is the point where q = 1/2 and γ =20. This means the delay is fixed if comparisons between variants are considered and that for actual use there are only two transmissions on the average. This also constrains the maximum delay which can grow quickly if (1-q) gets closer to unity.
where m = 1 for slots and m = 2 for asynchronous
For satellite operation, each station knows its delay to the satellite and the padding can be minimal unless very high bandwidths are used. For UHF radio with a 25 mile radius the padding is negligible at 50 KB, 10% at 500 KB, and 50% at 5 MB for 1200 bit packets. This is assuming no delay correction computation as with satellites. Beyond 5 MB either delay correction must be incorporated or the asynchronous system used if 1200 bit packets are still desired. Of course, it is at this same bandwidth that multiple receivers begin to help sort out the conflicts --- so delay correction may be unnecessary to achieve a consistently high channel utilization.
For satellite use, slots will improve the capacity by a factor of two to .347. For ground radio, a good FM receiver would permit a further improvement to 60% of the full bandwidth. The delay in this case is only eight packet times. Slots clearly need not be used at very low channel utilizations since the asynchronous system will work just as well at low rates. Thus, the resynchronization of the slot clock is not a problem. If no packets come by the clock drifts, no harm is done -- we just have the asynchronous case.
*Editor's note: This paper was originally distributed informally as ARPA Satellite System Note 8 on June 26, 1972. The paper is an important one and since its initial limited distribution, the paper has been frequently referenced in the open literature, but the paper itself has been unavailable in the open literature. Publication here is meant to correct the previous gap in the literature.
As the paper was originally distributed only to other researchers intimately familiar with the area covered by the paper, the paper makes few concessions to the reader along the lines of introductory or tutorial material. Therefore, a bit of background material follows.
ALOHA packet systems were originally described by Abramson ("The ALOHA System--Another Alternative for Computer Communication," Proceedings of the AFIPS Fall joint Computer Conference, Vol. 37, 1970, pp. 281-285). In an ALOHA a single broadcast channel is shared by a number of communicating devices. In the version originally described by Abramson, every device transmits its packets independent of any other device or any specific time. That is, the device transmits the whole packet at a random point in time; the device then times out for receiving an acknowledgment. If an acknowledgment is not received, it is assumed that a collision occured with a packet transmitted by some other device and the packet is retransmitted after a random additional waiting time (to avoid repeated collisions). Under a certain set of assumptions, Abramson showed that the effective capacity of such a channel is 1/(2e).
Roberts in the present paper investigates methods of increasing the effective channel capacity of such a channel. One method he proposes to gain in capacity is to consider the channel to be slotted into segments of time whose duration is equal to the packet transmission time, and to require the devices to begin a packet transmission at the beginning of a time slot. Another method Roberts proposes to gain in capacity is to take advantage of the fact that even though packets from two devices collide in the channel (i.e., they are transmitted so they pass through the channel at overlapping times), it may be possible for the receiver(s) to "capture" the signal of one of the transmitters, and thus correctly receive one of the conflicting packets, if one of the transmitters has a sufficiently greater signal than the other. Roberts considers the cases of both satellite and ground radio channels.
(Some of the text for the above background material was abstracted from "On the Capacity of Slotted ALOHA Networks and Some Design Problems," Israel Gitman, IEEE Transactions on Communications, Vol. COM-23, No.3, March 1975.)
Computer Communication review
A Quarterly Publication of the Special Interest Group on Data Communication
April 1975 Volume 5 Number 2
1 L. G. Roberts, "Multiple Computer Networks and Intercomputer Communication," ACM Symposium on Operating System Principles, October 1967. (First description of the ARPANET)
Copyright © 2001 Dr. Lawrence G. Roberts