Delay analysis of interval-searching contention resolution algorithms
Jian-Cheng Huang, Thomas Berger · IEEE Transactions on Information Theory · 1985
The intelligent design of a random multiple-access communication system involves analyzing the tradeoffs among throughput rate, transmission delay, and stability subject to additional restrictions imposed by distributed processing requirements. Interval-searching contention resolution algorithms have been found to achieve high throughput, and simulations have shown that they also possess short average delay. A general approach to the delay analysis of interval-searching contention resolution is proposed based on solving an integral equation for the distribution of a quantity called the transmission lag. For a certain multibit feedback algorithm, this analytical technique leads to exact determination of the throughput-delay characteristic. For the celebrated "0.487" algorithm, the method yields upper and lower bounds to the curve of expected delay versus throughput that are in close agreement with simulation results.