Delay Analysis of Aloha Network

This paper provides a queueing analysis for the slotted Aloha network. We assume the use of an exponential backoff protocol. Most prior work on slotted Aloha focuses on the analysis of its saturation throughput. Good saturation throughput, however, does not automatically translate to good delay performance for the end users. For example, it is well-known that the maximum possible throughput of slotted Aloha with a large number of nodes is e^-1 =0.3679 . Prior work showed that binary backoff factor of r = 2 can achieve a saturation throughput of 0.3466, which is very close to the e^-1. However, this paper shows that if mean queuing delay is to be bounded, then the offered load must be below 0.2158, a drastic 41% drop from e^-1. Fortunately, setting r= 1.3757 allows us to achieve bounded-mean-delay throughput of 0.3545, less than 4% lower than e^-1. A general conclusion is that the backoff factor r may significantly affect the queuing delay performance. Our analysis provides a framework to set system parameters properly.