This book chapter introduces the use of Continuous Time Markov Networks (CTMN) to analytically capture the operation of Carrier Sense Multiple Access with Collision Avoidance (CSMA CA) networks. It is of tutorial nature, and it aims to be an introduction on this topic, providing a clear and easy-to-follow description. To illustrate how CTMN can be used, we introduce a set of representative and cutting-edge scenarios, such as Vehicular Ad-hoc Networks (VANETs), Power Line Communication networks and multiple overlapping Wireless Local Area Networks (WLANs). For each scenario, we describe the specific CTMN, obtain its stationary distribution and compute the throughput achieved by each node in the network. Taking the per-node throughput as reference, we discuss how the complex interactions between nodes using CSMA CA have an impact on system performance.
The use of CTMN models for the analysis of CSMA CA networks was originally developed in @cite_8 and further extended in the context of IEEE 802.11 networks in @cite_5 @cite_2 @cite_6 @cite_1 , among others. Although the modeling of the IEEE 802.11 backoff mechanism is less detailed than in the work of Bianchi @cite_12 , it offers greater versatility in modeling a broad range of topologies. Moreover, experimental results in @cite_6 @cite_15 demonstrate that CTMN models, while idealized, provide remarkably accurate throughput estimates for actual IEEE 802.11 systems.
@cite_8 @cite_1 @cite_6 @cite_2 @cite_5 @cite_15 @cite_12
1975726216 2033020629 2146115135 2096448929
Analysis of the 802.11 CSMA CA mechanism has received considerable attention recently. Bianchi presented an analytic model under a saturated traffic assumption. Bianchi's model is accurate, but typical network conditions are nonsaturated and heterogeneous. We present an extension of his model to a nonsaturated environment. The model's predictions, validated against simulation, accurately capture many interesting features of nonsaturated operation. For example, the model predicts that peak throughput occurs prior to saturation. Our model allows stations to have different traffic arrival rates, enabling us to address the question of fairness between competing flows. Although we use a specific arrival process, it encompasses a wide range of interesting traffic types including, in particular, VoIP. Analytical models of IEEE 802.11-based WLANs are invariably based on approximations, such as the well-known mean-field approximations proposed by Bianchi for saturated nodes. In this paper, we provide a new approach for modeling the situation when the nodes are not saturated. We study a State Dependent Attempt Rate (SDAR) approximation to model M queues (one queue per node) served by the CSMA CA protocol as standardized in the IEEE 802.11 DCF. The approximation is that, when n of the M queues are non-empty, the attempt probability of the n non-empty nodes is given by the long-term attempt probability of n saturated nodes as provided by Bianchi's model. This yields a coupled queue system. When packets arrive to the M queues according to independent Poisson processes, we provide an exact model for the coupled queue system with SDAR service. The main contribution of this paper is to provide an analysis of the coupled queue process by studying a lower dimensional process and by introducing a certain conditional independence approximation. We show that the numerical results obtained from our finite buffer analysis are in excellent agreement with the corresponding results obtained from ns-2 simulations. We replace the CSMA CA protocol as implemented in the ns-2 simulator with the SDAR service model to show that the SDAR approximation provides an accurate model for the CSMA CA protocol. We also report the simulation speed-ups thus obtained by our model-based simulation. This paper presents a stochastic geometry model for the performance analysis and the planning of dense IEEE 802.11 networks. This model allows one to propose heuristic formulas for various properties of such networks like the probability for users to be covered, the probability for access points to be granted access to the channel or the average long term throughput provided to end-users. The main merit of this model is to take the effect of interferences and that of CSMA into account within this dense network context. This analytic model, which is based on Matern point processes, is partly validated against simulation. It is then used to assess various properties of such networks. We show for instance how the long term throughput obtained by end-users behaves when the access point density increases. We also briefly show how to use this model for the planning of managed networks and for the economic modeling of unplanned networks. This work started out with our discovery of a pattern of throughput distributions among links in IEEE 802.11 networks from experimental results. This pattern gives rise to an easy computation method, which we term back-of-the-envelop (BoE) computation. For many network configurations, very accurate results can be obtained by BoE within minutes, if not seconds, by simple hand computation. This allows us to make shortcuts in performance evaluation, bypassing complicated stochastic analysis. To explain BoE, we construct a theory based on the model of an “ideal CSMA network” (ICN). The BoE computation method emerges from ICN when we take the limit c → 0, where c is the ratio of the mean backoff countdown time to the mean transmission time in the CSMA protocol. Importantly, we derive a new mathematical result: the link throughputs of ICN are insensitive to the distributions of the backoff countdown time and transmission time (packet duration) given the ratio of their means c. This insensitivity result explains why BoE works so well for practical 802.11 networks, in which the backoff countdown process is one that has memory, and in which the packet size can be arbitrarily distributed. Our results indicate that BoE is a good approximation technique for modest-size networks such as those typically seen in 802.11 deployments. Beyond explaining BoE, the theoretical framework of ICN is also a foundation for fundamental understanding of very-large-scale CSMA networks. In particular, ICN is similar to the Ising model in statistical physics used to explain phenomena arising out of the interactions of a large number of entities. Many new research directions arise out of the ICN model.