Abstract
The multi-accessing of a broadcast communication channel by independent sources is considered. Present accessing techniques suffer from long message delays, low throughput and/or congestion instabilities. The objective of this research, therefore, is to develop and analyze high speed, high throughput, stable, multi-accessing algorithms. Contention 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 certain sense. Furthermore, they have a maximum throughput of .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 TDMA protocol. Our work is directly applicable to packet switching broadcast networks, in which packets might contain data from such sources as computer, teletype terminals and vocoders. However, our results may also apply to more general systems, in which a central facility is accessible by a number of independent users. If the number of users that can be serviced simultaneously is less than the number that can demand service, the techniques developed here can be used to resolve the resulting contentions.