CSMA using Statistical Physics toward Throughput and Utility Optimal CSMA

Se-Young Yun, Jinwoo Shin, Yung Yi

Abstract

Carrier Sense Multiple Access (CSMA) is a fundamental distributed protocol for managing wireless network contention. While theoretically capable of achieving optimal throughput and utility, traditional CSMA algorithms rely on Markov Chain Monte Carlo (MCMC) methods that suffer from exponentially slow convergence due to "mixing time" bottlenecks. This paper introduces two algorithms, BAS and BUM, which leverage the Bethe approximation from statistical physics to achieve polynomial-time convergence. Notably, the BAS algorithm requires only a single iteration for stability problems. Numerical results demonstrate that these methods provide high accuracy and significantly faster adaptation than prior MCMC-based approaches.

Introduction

In wireless networks, resolving contentions in a fully distributed fashion is critical for scalability. CSMA-based algorithms have gained significant attention because they can be tuned to guarantee optimality in terms of stability (scheduling) and system-wide utility (congestion control). However, the practical implementation of these optimal parameters has historically been hindered by the use of MCMC techniques.

MCMC-based approaches rely on iterative "simulation-and-update" loops. The primary bottleneck is the mixing time: the time required for the network to reach a steady state before parameters can be updated. In large or complex topologies, this mixing time grows exponentially with the number of links, rendering the system unable to adapt to rapid changes in traffic or network structure. This paper proposes a shift from simulation-based methods to a deterministic approximation framework derived from statistical physics.

Methodology: The Bethe Approximation

The authors reframe the CSMA network as a Markov Random Field (MRF), a graphical model where links are represented as vertices and interference constraints as edges. In this context, service rates correspond to "marginal probabilities" of the MRF.

To avoid the exponential delays of MCMC, the authors utilize the Bethe Free Energy (BFE) function to approximate the system's state. By solving the BFE equations directly, the algorithms become independent of the Markov chain's mixing time. The research introduces two primary distributed algorithms:

  1. BAS (Bethe Algorithm for Stability): Aimed at matching service rates to arrival rates. The authors discovered that for CSMA, higher-order marginals are determined by first-order marginals. This allows for a closed-form solution where each link calculates its transmission intensity using only one round of message passing with immediate neighbors.
  2. BUM (Bethe Utility Maximization): Aimed at balancing throughput and fairness. This two-phase approach first uses a distributed gradient-projection algorithm to find target service rates that maximize a utility function (such as $\alpha$-fairness). It then employs the BAS algorithm to set the transmission intensities required to reach those targets.

Evaluation and Results

The algorithms were evaluated using various simulated interference graph topologies, including complete graphs, rings, grids, and trees. Because the Bethe approximation is mathematically exact on tree topologies, the algorithms provide perfect solutions in those cases.

Key Findings:

  • Convergence Speed: In comparative simulations, the BUM algorithm converged within 1,000 iterations, whereas conventional MCMC-based schemes failed to reach a steady state even after 10,000 iterations.
  • Accuracy: On loopy graphs (grids and complete graphs), the "Bethe error" was remarkably small, typically staying within 20% of the target rate. This represents a highly favorable trade-off given the orders-of-magnitude increase in speed.
  • Utility Performance: The total network utility achieved by BUM was nearly identical to the theoretical maximum calculated by centralized, non-distributed methods.

Conclusion and Future Work

By leveraging the Bethe approximation, this work provides a path toward wireless networks that are both optimal and highly adaptive. The BAS and BUM algorithms replace slow, simulation-heavy processes with efficient, polynomial-time calculations.

While the approximation is robust, future research may focus on bounding errors in extremely dense "interference jungles" or using BAS as an "offline" pre-processor to provide high-quality starting points for traditional algorithms. This hybrid approach could combine the rapid convergence of statistical physics with the eventual exactness of MCMC methods.

Summary updated

Abstract

CSMA (Carrier Sense Multiple Access), which resolves contentions over wireless networks in a fully distributed fashion, has recently gained a lot of attentions since it has been proved that appropriate control of CSMA parameters guarantees optimality in terms of stability (i.e., scheduling) and system- wide utility (i.e., scheduling and congestion control). Most CSMA-based algorithms rely on the popular MCMC (Markov Chain Monte Carlo) technique, which enables one to find optimal CSMA parameters through iterative loops of `simulation-and-update'. However, such a simulation-based approach often becomes a major cause of exponentially slow convergence, being poorly adaptive to flow/topology changes. In this paper, we develop distributed iterative algorithms which produce approximate solutions with convergence in polynomial time for both stability and utility maximization problems. In particular, for the stability problem, the proposed distributed algorithm requires, somewhat surprisingly, only one iteration among links. Our approach is motivated by the Bethe approximation (introduced by Yedidia, Freeman and Weiss in 2005) allowing us to express approximate solutions via a certain non-linear system with polynomial size. Our polynomial convergence guarantee comes from directly solving the non-linear system in a distributed manner, rather than multiple simulation-and-update loops in existing algorithms. We provide numerical results to show that the algorithm produces highly accurate solutions and converges much faster than the prior ones.
BibTeX
@article{yun2015csma,
  author = {Se-Young Yun and Jinwoo Shin and Yung Yi},
  title = {{CSMA using Statistical Physics toward Throughput and Utility Optimal CSMA}},
  journal = {IEEE Trans. Information Theory},
  year = {2015},
  url = {https://openreview.net/forum?id=WAKQOQub2q},
}
Figure