Fundamentals of the Backoff Process in 802.11
Jeong-woo Cho, Yuming Jiang · 2009
This paper discovers fundamental principles of the backoff process that governs the performance of IEEE 802.11. We first establish that the so-called mean field technique, which spins off a fixed point equation, is mathematically valid for use in performance analysis of 802.11. On the basis of this, succinct equations describing the backoff distribution as a function of the collision probability γ are derived, which also shed light on a controversy in the field. In addition, the observation that the entropy of the backoff process in 802.11 increases with the number of nodes leads us to see through a Poissonian character inherent in 802.11. However, it is also found that the collision effect between nodes prevails over the Poissonian aggregation effect in spite of its tendency to increase with the number of nodes. Based on these findings, we formulate the principle about the inter-transmission probability that lays a foundation for the short-term fairness analysis. Another principle discovered upon regular variation theory is that the per-packet backoff has a truncated Pareto-type tail distribution with an exponent of (log γ)/log m (m is the multiplicative factor). This reveals that the backoff process is heavy-tailed in the strict sense for m 2 γ> 1, essentially due to collision. Moreover, we identify the long-range dependence in 802.11 and show that the inter-transmission probability undergoes a dramatic change at γ0 = 1/m 2 and falls into two qualitatively distinct categories: either approximately Gaussian or Lévy α-stable distribution with α ∈ (1, 2) entailing infinite variances, leaning tendency, and directional unfairness.