JPL's Wireless Communication Reference Website

Chapter: Data Networks
Section: Random Access, ALOHA, Stability and collision resolution

with contributions by René van der Vleuten

Controlling the Retransmission back-off

The aloha protocol can become unstable is packets collide and their retransmissions collide again and again.
  See the collision resolution animation and the exercise.  

An adhoc approach: How to select a good Pr?

In a network, the packet arrival probability P0 and the retransmission backoff probability Pr determine the stability. The operator may not have a direct influence of the arrival process of new packets, but he may dicate a certain the retransmission behavior for all terminals.

For mobile channels, the range of the parameters where bistability occurs is relatively small: the transition through this area from a single (low-backlog) equilibrium into saturation occurs for relatively small increments of the packet generation probability P0. In contrast to this, since the bifurcation curve of the mobile net is almost parallel to the Pr-axis, a change in the retransmission probability will have less effect on the stability of the net. For a packet generation probability up to P0 = 0.002, even a persistent retransmission schedule (Pr = 1) leads to a stable network, at least in theory. In practice, high retransmission probabilities may be used, but certainly not larger than say 0.8.

Simulations indicated that reducing the probability of retransmission Pr has a positive effect on the network performance in saturated networks (increasing throughput, decreasing backlog and delay), but a negative effect in stable, unsaturated networks (lower throughput, increasing backlog and delay). In bistable nets, appropriate reduction of Pr can remove bistability, but this measure may not sufficiently relieve the backlog and packet delay: The curve suggests that a relatively drastic reduction of Pr may be required. Reducing Pr in a bistable network can result in a stable network, but with relatively high backlog.

By reducing the probability of retransmission, the effective time each terminal spends in the origination mode also reduces, which indirectly resulted in a low input traffic load. This would suggest that mobile channels might as well be managed by directly controlling the input traffic, for instance by limiting the number of terminals N that are allowed to be signed on simultaneously.

Dynamic control of Pr

The above Markov models do not reveal any insight in how one can dynamically adjust the retransmission back-off to stabilize the system. This is nonetheless a very popular method to ensure reliable operation of collision-type networks. As soon as the the base station estimates that the backlog grows beyond some limit, it instructs all terminals to increase their retransmission back-off, i.e., to reduce Pr.

Exercise

Is it sufficient to define a finite number of modes, each with a different Pr, to ensure stability in an ALOHA network without capture? Show that in such case the system is still unstable.

Optimal retransmission back-off control

There exists an optimal retransmission backoff control method for a controlled ALOHA system. It achieves maximal throughput, automatically adapts to changes in average traffic intensity or the number of active stations in the system, and applies to both pure and slotted ALOHA systems.

Optimal Collision Resolution

Improved schemes to resolved collisions also exist, e.g.,



JPL's Wireless Communication Reference Website © 1993, 1995.