On the capacity of infinite population multiple access protocols

Publisher Website
Google Scholar
Abstract
We present bounds on the maximum channel utilization (with finite average delay) of synchronous multiple access communications protocols serving an infinite population of homogeneous stations. Messages arrive to the system as a series of independent Bernoulli trials in discrete time, with probability p of an arrival at each arrival point (the Poisson limit is explicitly included) and are then randomly distributed among the stations. Pippenger showed that the channel utilization cannot exceed\xi_{p}, where\xi_{l}=1and\lim_{p \rightarrow 0} \xi_{p} \approx 0.744. Using a "helpful genie" argument, we find the exact capacity for allp \geq 0.568(where we find optimal protocols that obey first-come first-served); for smaller values of p, we present an improved upper bound that decreases monotonically to\approx 0.6731in the Poisson limit asp \rightarrow 0.

This publication has 5 references indexed in Scilit: