Topics In Performance Modeling Of IEEE 802.11 Wireless Local Area Networks

Abstract

This thesis is concerned with analytical modeling of Wireless Local Area Networks (WLANs) that are based on IEEE 802.11 Distributed Coordination Function (DCF). Such networks are popularly known as WiFi networks. We have developed accurate analytical models for the following three network scenarios: (S1) A single cell WLAN with homogeneous nodes and Poisson packet arrivals, (S2) A multi-cell WLAN (a) with saturated nodes, or (b) with TCP-controlled long-lived downloads, and (S3) A multi-cell WLAN with TCP-controlled short-lived downloads. Our analytical models are simple Markovian abstractions that capture the detailed network behavior in the considered scenarios. The insights provided by our analytical models led to two applications: (i) a faster “model-based'” simulator, and (ii) a distributed channel assignment algorithm. We also study the stability of the network through our Markov models.

For scenario (S1), we develop a new approach as compared to the existing literature. We apply a “State Dependent Attempt Rate'” (SDAR) approximation to reduce a single cell WLAN with non-saturated nodes to a coupled queue system. We provide a sufficient condition under which the joint queue length Markov chain is positive recurrent. For the case when the arrival rates into the queues are equal we propose a technique to reduce the state space of the coupled queue system. In addition, when the buffer size of the queues are finite and equal we propose an iterative method to estimate the stationary distribution of the reduced state process. Our iterative method yields accurate predictions for important performance measures, namely, “throughput'”, “collision probability” and “packet delay”. We replace the detailed implementation of the MAC layer in NS-2 with the SDAR contention model, thus yielding a ``model-based'' simulator at the MAC layer. We demonstrate that the SDAR model of contention provides an accurate model for the detailed CSMA/CA protocol in scenario (S1). In addition, since the SDAR model removes much of the details at the MAC layer we obtain speed-ups of 1.55-5.4 depending on the arrival rates and the number of nodes in the single cell WLAN.

For scenario (S2), we consider a restricted network setting where a so-called “Pairwise Binary Dependence” (PBD) condition holds. We develop a first-cut scalable “cell-level” model by applying the PBD condition. Unlike a node- or link-level model, the complexity of our cell-level model increases with the number of cells rather than with the number of nodes/links. We demonstrate the accuracy of our cell-level model via NS-2 simulations. We show that, as the “access intensity” of every cell goes to infinity the aggregate network throughput is maximized. This remarkable property of CSMA, namely, “maximization of aggregate network throughput in a distributed manner” has been proved recently by Durvy et al. (TIT, March, 2009) for an infinite linear chain of nodes. We prove it for multi-cell WLANs with arbitrary cell topology (under the PBD condition). Based on this insight provided by our analytical model we propose a distributed channel assignment algorithm.

For scenario (S3), we consider the same restricted network setting as for scenario (S2). For Poisson flow arrivals and i.i.d. exponentially distributed flow sizes we model a multi-cell WLAN as a network of processor-sharing queues with state-dependent service rates. The state-dependent service rates are obtained by applying the model for scenario (S2) and taking the access intensities to infinity. We demonstrate the accuracy of our model via NS-2 simulations. We also demonstrate the inaccuracy of the service model proposed in the recent work by Bonald et al. (SIGMETRICS 2008) and identify the implicit assumption in their model which leads to this inaccuracy. We call our service model which accurately characterizes the service process in a multi-cell WLAN (under the PBD condition) “DCF scheduling” and study the “stability region” of DCF scheduling for small networks with single or multiple overlapping “contention domains”.