On the delay in a multiple-access system with large propagation delay

The effect that large propagation delay has on the problem of network access is explored for the infinite population model with success-idle-collision feedback information, where the feedback information suffers a large propagation delay N. A simple lower bound is given on the probability that a packet is not successfully transmitted within N/2 time units (not including the forward propagation delay), where N is the station-to-station propagation delay. The bound implies a lower bound on the mean access delay. We also display an algorithm for which the transmission delay is within a factor of three of the lower bound, for moderate traffic loads and asymptotically large propagation delay. Index Terms--Multiple access, large propagation delay, random access, collision resolution.