Tree algorithms for packet broadcast channels

TLDR

Broadcast channels accessed by independent sources suffer from long delays, low throughput, and congestion instabilities. The authors propose a new class of high‑speed, high‑throughput, stable multiaccess algorithms. They introduce contention‑resolving tree algorithms and analyze them under specific probabilistic source models. These algorithms are proven stable, achieve a maximum throughput of 0.430 packets/slot, exhibit good delay properties, and adapt to conventional TDMA under heavy traffic.

Abstract

The multiaccessing of a broadcast communication channel by independent sources is considered. Previous accessing techniques suffer from long message delays, low throughput, and/or congestion instabilities. A new class of high-speed, high-throughput, stable, multiaccessing algorithms is presented. Contentions resolving tree algorithms are introduced, and they are analyzed for specific probabilistic source models. It is shown that these algorithms are stable (in that all moments of delay exist) and are optimal in a certain sense. Furthermore, they have a maximum throughput of 0.430 packets/slot and have good delay properties. It is also shown that, under heavy traffic, the optimally controlled tree algorithm adaptively changes to the conventional time-division multiple access protocol.