Collision-Resolution Algorithms and Random-Access Communications

摘要

The problem considered is the random-accessing by very many transmitters of a common receiver over a time-slotted collision-type channel with feedback. A collision-resolution algorithm (CRA) is a protocol for the transmission and retransmission of packets such that, after a collision, all transmitters eventually and simultaneously learn that all the colliding packets have been successfully retransmitted. Focus is placed on a CRA due to Capetanakis (the CCRA) and a slight modification thereof (the MCCRA). The fundamental (traffic-independent properties of the CCRA and MCCRA are derived by means of a recursive analysis, with emphasis on the mean and variance of the number of slots required to resolve a collision among N packets. These results are then used to analyze by a Markovian approach the performance of various random-access algorithms, built upon the CCRA and MCCRA, for the case of infinitely many identical sources generating Poisson traffic. The maximum stable throughput is determined for each random-access algorithm, and tight upper and lower bounds are developed for the delay-throughput characteristic of the 'obvious' random-access algorithm built upon the CCRA.