The Stack Algorithm for Collision Resolution

The stack algorithm is a decentralized Medium Access Protocol. While the ALOHA system becomes unstable under certain conditions, several collision resolution algorithms have been proposed that remain stable. One of these algorithms is the Stack Algorithm. It was invented by the Prof. Boris Tsybakov and his research group (see his interview).

Stack Algorithms always use a "slotted" channel, i.e., the time axis is divided into slots and any packet transmission starts at the beginning of a slot and finishes at the end of the same slot. Similar to slotted ALOHA, a terminal that generates a new user packet during a slot, transmits in the next slot. A packet capturing the receiver in slot n leaves the system at t = n + 1. All terminals with packets that fail to capture the receiver use a stack algorithm. For that purpose, each user terminal that still has a backlogged packet for transmission listens to the return channel at the end of a slot to decide what has to be done in the next slot.

Several versions of the algorithm exists. One stack algorithm uses ternary feedback: Each terminal can a posteriori distinguish perfectly between an "idle" slot, a slot with "capture" and a slot with "conflict".

Each packet transmitted in a slot without capturing the receiver is either retained in the terminal buffer (with probability r) or retransmitted in the next slot (with probability 1 - r). Parameter r is the same for all terminals and is called the "splitting parameter". Associated with the message buffer is a stack counter. The system is slotted, i.e., the time axis is divided into slots and any packet transmission starts at the beginning of a slot and finishes at the end of the same slot. which changes from slot to slot according to a set of rules. Generally, the stack counter increases when a conflict is observed in a slot and decreases when a slot is idle. Any packet that captures the receiver leaves the system.

Virtual Stack

This algorithm is called the stack algorithm because terminals in backlog, i.e., with their stack counter being one or more, have to wait till all ongoing collisions are resolved before they can retransmit. In this sense the algorithm has last-in first-out (LIFO or stack) queueing properties.

Modifications to the random access scheme to obtain a fairer first-in first-out property inevitably suffer from instability. The LIFO behaviour appears necessary to ensure that terminals restrain from too rapid retransmissions if the backlog happens to become large.

The stack is a virtual one. No entity in the network has full knowledge of the contents of the stack. Terminals know their own counter position, but only have probabilistic knowledge on the occupation of the stack depths. The base station does not know which stack levels are occupied.

Example of Stack Counter Rules

A packet transmitted in slot n for the first time (i.e., this packet was generated in slot n - 1) has l_n = 0.
When l_n = 0, this packet will be transmitted in slot n. When l_n > 0, the packet is not transmitted in slot n.
When l_n = 0 and a conflict is reported in slot n, then l_(n+1)= 1 with probability r and l_{(n + 1)} = 0 with probability 1 - r.
When l_n > 0 and a capture is reported in slot n, then l_{(n + 1)} = l_n .
When l_n > 0 for a packet and slot n is reported idle, then l_(n+1) = l_n - 1. (move down)
When l_n > 0 and a conflict is reported in slot n, then l_(n+1) = l_n + 1. (move up)

Except when the probability of capture is large, it is near-optimum to choose r = 1/2.

The corresponding terminal protocol is illustrated below. Note that if capture occurs, the feedback from the base station must of course indicate which packet captured the receiver.

Figure: Terminal behaviour for Stack Algorithm.

Collision Resolution Delay

Papers on the stack algorithm mostly address a multi-access channel with a large (possibly infinite) number of distributed terminals that send data packets to a central receiver. Packets arrive according to a temporal Poisson process with mean arrival rate lambda packets per second.

The definition of expected delay in stack applies to an arbitrary member of the ensemble of packets offered to the system. It is taken here as the expectation of the time interval elapsed between (the beginning of) the first transmission attempt of a packet and (the beginning of) its successful transmission. The stack algorithm has similarities with last-in/first-out systems and branching processes: a packet colliding in slot n that moves into the stack at slot n + 1 can be retransmitted (successfully or not) only after all other packets that stayed in the channel (l_n + 1 = l_n = 0) have left the system, together with all new packets arriving during the period of their transmission.

Retransmissions in a Stack Algorithm

Figure: Sample of operation of a stack algorithm versus time. Compared to a classical ALOHA network, each terminal adapts its behavior according to feedback messages.
Vertical axis: depth of packet in stack.
Horizontal axis: time (discretized into slot durations)
Black dot: packet.

Step by step explanation

One defines a session as the time interval between two successive moments n₁ and n₂ ( n₁ < n₂) such that for some packet l_n1 = 1 and l_n2 = 0 for the first time. The expected length of a session depends on the number K of packets transmitted in slot n₁. Such a session is called a session of multiplicity K.

Example: CDMA Packet Network with Stack Access

The stack algorithm can be used with DS-CDMA spread spectrum transmission in wireless packet-data networks. The throughput and delay performance depend on the spread factor and the receiver capture performance, but presumably small spread factors perform best.

Selected References on Stack Algorithms

JPL's Wireless Communication Reference Website

Chapter: Data Networks Section: Random Access