Chapter: Data Networks
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.
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.
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.
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 (ln + 1 = ln = 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.
One defines a session as the time interval between two successive moments n1 and n2 ( n1 < n2) such that for some packet ln1 = 1 and ln2 = 0 for the first time. The expected length of a session depends on the number K of packets transmitted in slot n1. Such a session is called a session of multiplicity K.
References on Stack Algorithms