Bounded-Mean-Delay Throughput and Nonstarvation Conditions in Aloha Network

摘要

Prior investigations on the Aloha network have primarily focused on its system throughput. Good system throughput, however, does not automatically translate to good delay performance for the end users. Neither is fairness guaranteed: Some users may starve, while others hog the system. This paper establishes the conditions for bounded mean queuing delay and nonstarved operation of the slotted Aloha network. We focus on the performance when collisions of packets are resolved using an exponential backoff protocol. For a nonsaturated network, we find that bounded mean delay and nonstarved operation can be guaranteed only if the offered load is limited to below a quantity called "safe bounded mean-delay (SBMD) throughput." The SBMD throughput can be much lower than the saturation system throughput if the backoff factor r in the exponential backoff algorithm is not properly set. For example, it is well known that the maximum throughput of the Aloha network is e -1 = 0.3679. However, for r = 2, a value assumed in many prior investigations, the SBMD throughput is only 0.2158, a drastic penalty of 41% relative to 0.3679. Fortunately, using r = 1.3757 allows us to obtain an SBMD throughput of 0.3545, less than 4% away from 0.3679. A general conclusion is that the system parameters can significantly affect the delay and fairness performance of the Aloha network. This paper provides the analytical framework and expressions for tuning r and other system parameters to achieve good delay and nonstarved operation.