Chapter: Data Networks
A well-known procedure for evaluation of the stability of the ALOHA channel considers a finite or infinite population of N terminals.
For the case of a finite population an additional assumption is that each terminal has a buffer of length one to store the last packet, which may need retransmission. No new packets arrives in the same terminal as long a one packet is waiting for retransmission.
The local behaviour of such a terminal is modelled by a tri-state Markov chain.
The global behaviour of the entire slotted ALOHA network is also modelled by means of a finite or infinite Markov chain. The state of the network represents the number of terminals m in the state R at the start of the time slot. This is also called the system 'backlog'. With a population of N terminals, we have N + 1 states. During a time slot, i (i = j + k) packets are transmitted whenever j terminals in the O state and k terminals in the R-state change into the T-state at the same time. The probability of a transition into another state may be obtained from the probability distribution of j and k and the capture probability Cj+k that one of the j + k packets survives the collision. Here, k is a binomial random variable. For an infinite population j is Poisson, in a finite population j is binomial.
For a given backlog, j and k are independent.
Figure: Markov model for number of terminals in backlog. Population size N.
Calculations based on the above Markov model take into account that the system backlog m and the probability of successful transmission are statistically correlated: With a high system backlog, frequent retransmissions occur (if Pr > P0), and collisions are very likely. Hence, the probability of success generally reduces with increasing system backlog (if Ck < Cm for k > m), which may lead to saturation or instability of the network if terminals in backlog employ (too) short retransmission waiting times (too high Pr). If the number of terminals N is finite, the network may become bi-stable, i.e., the network oscillates between low and high backlog states.
average number of packets in backlog average delay = ------------------------------------- throughput
With an infinite population of users and a fixed retransmission back-off parameter, the ALOHA system is always unstable, unless capture occurs.
|Figure: Markov model for number of packets in backlog. Backgrounds: Greenish: negative drift; reddish: positive drift|
It can be shown that
|Figure: Bistability area for a network with N =100 users without capture (orange) and with imperfect capture (green) (capture ratio z = 10) in mobile channels.|
The above figure gives the region for P0 and Pr where the network with 100 terminals is bistable. A conservative receiver threshold of 10 dB (z = 10) is considered, so these results may be somewhat pessimistic. The bistability area for ALOHA without capture was computed first by Onozato and Noguchi. Areas mapping the stability of a slotted ALOHA network with capture were derived for the case that the population of terminals is divided into a group transmitting at high power and a group transmitting a low power.
Van der Plas and Linnartz estimated the area of bistability by trial and error with the technique used to obtain drift curves. A uniform spatial distribution, shadowing (6 dB) and Rayleigh fading are considered. When receiver capture occurs, the mobile network exhibits bistability at substantially higher packet traffic loads, even for a pessimistic receiver threshold of 10 dB (z = 10).
It appears that the network is always stable, irrespective of the retransmission probability Pr, if Pr < P0,max, with roughly P0,max = 2 . 10-3. This agrees with the observation by Ghez, Verdu and Schwartz, that for
|packet arrival rates||<||the limit of the capture probability for collisions with infinitely many signals||,|
the channel is stable if the probability of capture is independent from slot to slot. However, this may be a strong assumption if the retransmission waiting time is small. If packets are retransmitted from the same location, they are received with the same power, as the initial transmission attempt. If the same set of data packets collide again with the same powers for all signals involved, interference is likely to cause packet loss during all successive collisions.
Controlling the Retransmission back-off
|See the collision resolution animation and the exercise.|
Various schemes exist to ensure stability and to resolve collisions
As an alternative, other spatial distributions can considered. This allows more realistic modelling of the packet traffic very close to the central receiver. Simulations reveal that in such case, the system may suffer much more from instability effects than in the case that some signals are received with very large power.
Figure: Expected number of (re-) transmission attempts needed, as a function of terminal location|
For details see Cellular ALOHA Networks.