A Unified Analytical Framework of Aloha and CSMA

　

Aloha and Carrier Sense Multiple Access (CSMA) are two representative random-access protocols. Despite their simplicity in concept, the performance analysis of Aloha and CSMA networks has long been known as notoriously difficult. Numerous models and analytical approaches have been proposed in the past four decades. Yet how to integrate them into a coherent theory remains an open challenge.

In our recent work [Dai'12]-[Dai'13], a unified theoretical framework for throughput, delay, and stability analysis of Aloha and CSMA was established. It not only facilitaes the characterization of stable regions, but also enables the optimization of various network performance metrics. A wide range of performance limits, including the maximum network throughput, the minimum first and second moments of access delay, and the maximum network sum rate, can be characterized within the proposed analytical framework.

As we pointed out in [Dai'12]-[Dai'13], a random-access network can be regarded as a multi-queue-single-server system, and the key to performance analysis lies in proper characterization of the service time distribution, which is difficult to obtain with either each node's queue completely ignored or interactions among nodes' queues taken into full consideration. To reduce the modeling complexity, we demonstrated in [Dai'12]-[Dai'13] that a scalable node-centric model can be established by treating each node's queue as an independent queueing system with identically distributed service time, which consists of two parts: 1) state characterization of each individual head-of-line (HOL) packet; and 2) characterization of network steady-state points based on the fixed-point equations of limiting probability of successful transmission of HOL packets. The proposed modeling methodology has been successfully applied to various random-access networks, and shown to be accurate. In most scenarios, the network steady-state points can be obtained as explicit functions of key system parameters such as the number of nodes and the backoff window size/transmission probability of each node, based on which the optimal network performance can further be characterized.

Note that a key assumption in [Dai'12] and [Dai'13] is that a packet stays in the queue until it is successfully transmitted. In practical random-access networks, however, a packet may be discarded if it reaches the maximum number of transmission attempts. [Sun-Dai'16] further extended the analytical framework to include a retry limit M and studied the effect of M on the optimal network performance including the maximum network throughput and the minimum mean access delay. The analysis provides direct guidance on performance optimization of practical CSMA networks such as IEEE 802.11 networks.