PaperlayerView exact revision on arXiv

Source-linked AI summary

Back-of-the-Envelope Computation of Throughput Distributions in CSMA Wireless Networks

S. C. Liew, C. Kai, J. Leung, B. Wong

arXiv:0712.1854v1cs.NIcs.PF

TL;DR

The paper addresses fast throughput-distribution computation for CSMA networks with non-all-inclusive carrier sensing. It introduces BoE and explains it through an interacting-telegraph-process model, reporting very accurate 802.11 results and several structural properties of ideal CSMA networks.

  • Problem

    Existing textbook methods largely assume all-inclusive carrier sensing, while non-all-inclusive CSMA networks are difficult to analyze accurately.

  • Method

    The paper combines a contention-graph-based BoE computation with an interacting on-off telegraph-process model for ideal CSMA networks.

  • Results

    BoE is reported as highly accurate for 802.11 networks and yields time reversibility, distributional insensitivity, and Markov-random-field system-state probabilities in the theory.

  • Takeaways & Limitations

    BoE enables rapid hand computation and quick identification of network problems, while the theoretical framework supports understanding CSMA link interactions.

  • Takeaways & Limitations

    The paper focuses on networks without hidden nodes, and its ideal link model is analytical rather than an implementation blueprint.

Abstract

from arXiv · show

This work started out with our accidental 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, because for many network configurations, very accurate results can be obtained within minutes, if not seconds, by simple hand computation. BoE beats prior methods in terms of both speed and accuracy. While the computation procedure of BoE is simple, explaining why it works is by no means trivial. Indeed the majority of our investigative efforts have been devoted to the construction of a theory to explain BoE. This paper models an ideal CSMA network as a set of interacting on-off telegraph processes. In developing the theory, we discovered a number of analytical techniques and observations that have eluded prior research, such as that the carrier-sensing interactions among links in an ideal CSMA network result in a system state evolution that is time-reversible; and that the probability distribution of the system state is insensitive to the distributions of the "on" and "off" durations given their means, and is a Markov random field. We believe these theoretical frameworks are useful not just for explaining BoE, but could also be a foundation for a fundamental understanding of how links in CSMA networks interact. Last but not least, because of their basic nature, we surmise that some of the techniques and results developed in this paper may be applicable to not just CSMA networks, but also to other physical and engineering systems consisting of entities interacting with each other in time and space.

1. INTRODUCTION

The paper introduces BoE, a fast hand-computation method for throughput distributions in non-all-inclusive CSMA networks, and develops theory explaining its accuracy. The theory identifies time reversibility, distributional insensitivity, and Markov-random-field structure in ideal CSMA networks.

  • Motivation: Non-all-inclusive carrier sensing makes existing throughput methods difficult to extend because not all links can sense each other.Prior analytical methods are described as less accurate than the simpler method presented here.
  • Theoretical foundation: The paper models ideal CSMA networks as interacting on-off processes to explain the experimentally discovered BoE pattern.The paper develops the theory after simulation and real-network observations.
  • BoE method: BoE computes throughput distributions for modest networks within minutes or seconds using simple hand computation.The method is based on contention-graph structure and normalized throughput distributions.
  • BoE method: (1 0 0.5 0.5) is a rapidly approximated normalized throughput distribution for the example network.The cited passage presents this distribution as an example of the method’s quick computation.
  • Theoretical foundation: The theory establishes time reversibility, insensitivity to duration distributions given their means, and a Markov random field for system-state probabilities.These properties are presented as analytical observations underlying the paper’s explanation of BoE.
  • Implications: BoE can provide quick identification of network problems, while the theory also supports understanding CSMA’s distributed resource allocation.The paper presents these as practical and conceptual implications of the method.

2. BASIC BOE COMPUTATION AND EXPERIMENTAL CONFIRMATION

BoE reduces throughput computation to counting maximum independent sets in a contention graph, then compares the resulting distributions with simulations and real-network experiments. The reported results show close agreement for the tested 802.11 topologies.

  • Computation procedure: BoE draws the contention graph, identifies maximal independent sets, and retains only the maximum independent sets (MIS).An MIS is an independent set with maximum cardinality.
  • Computation procedure: A link’s normalized throughput equals the number of retained MIS containing it divided by the total number of retained MIS.The normalized values can then be converted to throughput in bits per second.
  • Scope: Counting MIS is NP-complete, so BoE is manageable for small networks but can become unwieldy for large ones.The paper specifically identifies small 802.11 networks within a building as a manageable setting.
  • Worked example: For the example network, the retained MIS produce normalized throughputs of (1 0 0.5 0.5).The example first identifies three maximal independent sets and then retains two MIS.
  • Experimental confirmation: BoE was reported as highly accurate against NS2 simulations across multiple network topologies and UDP and TCP sessions.The simulations used typical 802.11b parameters.
  • Experimental confirmation: Real-network measurements on two 802.11a topologies matched BoE predictions well, though imperfect link isolation made measured distributions less extreme.The experiments used four laptop link pairs and reported an isolated-link throughput of around 29Mbps.

3. EXPLANING BOE

The paper explains BoE by idealizing CSMA as interacting telegraph processes and showing why system time concentrates on equally likely MIS states. Initial exponential assumptions simplify the analysis, while later theory addresses their removal.

  • Core propositions: BoE assumes that the system spends most of its time in MIS and that MIS states are approximately equally likely.These are the two propositions identified as the essential underpinnings of steps 1–4.
  • Core propositions: Step 3 approximates zero time in non-MIS states, while step 4 uses equal likelihood of MIS states to compute normalized throughputs.The two BoE steps directly encode the two propositions.
  • Modeling rationale: Ignoring collisions makes computed throughput optimistic, while continuous countdown preserves carrier-sensing interactions without simultaneous countdown ties.The paper uses this modeling choice to isolate carrier-sensing effects.
  • Idealization: The preliminary model assumes negligible countdown collisions, negligible countdown time relative to transmission time, and exponential countdown and transmission durations.The assumptions enable a continuous-time Markov-chain treatment.
  • Idealization: Under continuous countdown and transmission times, each isolated link is an on-off telegraph process, and the network becomes a set of interacting telegraph processes.Transmission is represented by on and countdown by off.
  • Idealization: The ideal link model distinguishes transmission, active-countdown, and frozen-countdown states according to carrier-sensing input and remaining times.A frozen countdown occurs when another sensed link is transmitting.

1 We are not advocating reducing the timeslot size in implementation,

The paper models an ideal link with continuous countdown and transmission processes, while emphasizing that this analytical model is not an implementation blueprint.

  • Scope: The ideal link model is analytical and is not intended as an implementation blueprint.The paper explicitly notes that the model may not be practically viable.
  • Ideal link model: The ideal link model represents a link through alternating countdown and transmission behavior.During transmission, residual transmission time decreases; during active countdown, residual countdown time decreases, while frozen countdown leaves both unchanged.
  • State transitions: The link state evolves through event-triggered transitions mapped to four pseudocode segments.The event-driven module freezes neighboring active countdowns when a link begins transmission and resumes them when appropriate.
  • Ideal network model: The ideal network model is formed by interconnecting individual ideal-link modules.The connected modules represent how links jointly evolve in the network.

2 Throughout this paper, we assume all links have the same countdown

The paper defines network states from transmitting links, derives their transition structure and probabilities, and uses those probabilities to compute normalized and practical throughputs. Under small countdown overhead, maximum independent sets dominate and become equiprobable, motivating the BoE approximation.

  • State representation: Each link has an abbreviated state indicating whether it is transmitting, and the global state records all links’ abbreviated states.A zero-valued link can be actively counting down or frozen depending on neighboring transmitting links.
  • State connectivity: Two feasible states are connected exactly when one adds or removes a single transmitting link, so their Hamming distance is 1.The state with fewer transmitting links is called the left state, and the one with more is the right state.
  • Throughput computation: The normalized throughput of each link is obtained from the fraction of time the network occupies states in which that link transmits.The paper applies this state-probability calculation to the example network before converting normalized values to bps.
  • Transition probabilities: With exponential countdown and transmission times, connected left-to-right transitions occur at rate 1/E[T_cd], while reverse transitions occur at rate 1/E[T_tr].The resulting continuous-time Markov process is time-reversible, enabling detailed balance.
  • State probabilities: All feasible states with the same number of transmitting links have the same probability.The probability of a state in the n-transmitter subset is expressed using the normalization term B_n and the countdown-overhead parameter c.
  • Relation to prior methods: Equation (4) remains valid when countdown processes retain memory after leaving frozen states, unlike the Poisson-attempt assumption used in prior analytical work.The paper states that prior methods are less accurate than the simpler method presented here.
  • BoE approximation: When c approaches 0, only maximum independent sets retain nonzero probability, and all maximum independent sets are equiprobable.The paper notes that c = 0.186 for 802.11b and justifies ignoring nonmaximum maximal independent sets as an approximation even when c is not very small.
  • Engineering conversion: The bps conversion multiplies normalized throughputs by the raw throughput of one isolated link.This may underestimate throughput because countdowns can overlap, while ignoring collisions may overestimate it; the effects oppose each other.

4. INSENSITIVITY TO COUNTDOWN TIME AND TRANSMISSION TIME DISTRIBUTIONS

The paper establishes that ideal CSMA networks retain the state-probability formula despite non-exponential countdown and transmission times. It explains this through time reversibility, invariant residual-time behavior, and an equivalent Markov random field characterization.

  • Time reversibility: The ideal CSMA state process is non-Markovian but time-reversible, allowing detailed-balance reasoning for average transition rates.The paper defines transition rates from long-run transition counts and state occupancy rather than instantaneous Markov rates.
  • Residual-time invariance: Under the invariant residual-time property, connected-state transition-rate ratios satisfy p_s's/p_s's = c, enabling correspondence with the state-probability formula.The property concerns residual countdown and transmission times at other links’ transition epochs.
  • Markov random field: Formula (4) can also be derived when the state distribution is a Markov random field, providing an alternative route to the same result.Theorem 2 gives an if-and-only-if characterization using the local-neighborhood factorization of state probabilities.
  • Alternative proofs: A continuous-state-space analysis independently proves insensitivity and makes the invariant residual-time property a corollary rather than a required premise.The paper also presents an alternative mixture-of-gamma-distributions approach in an appendix.

5. IMPLICATIONS AND APPLICATIONS OF BOE

BoE reveals how topology and countdown parameters shape long-term throughput, while exposing starvation and temporal effects that local or average throughput measures can miss.

  • Global optimality and local starvation/unfairness: 802.11b simulations match BoE well at c = 0.186, with the system spending almost all its time among maximum-throughput MIS states.The greedy CSMA protocol therefore achieves the highest global throughput in this case, although local starvation or unfairness may remain.
  • Resource allocation: Under ideal CSMA, the forms of countdown and transmission-time distributions are immaterial for resource allocation once their mean ratio is fixed.The optimization therefore has L degrees of freedom through the c_i parameters, or L − 1 when a minimum countdown constraint is imposed.
  • Small change in topology leads to large change in throughput distribution: Link throughput can change sharply after adding a distant link because small topology changes can alter the set of maximum independent sets.The paper notes that identifying MIS is NP-complete, so this sensitivity may make the complexity difficult to avoid.
  • IMPLICATIONS AND APPLICATIONS OF BOE: BoE computation is quick for modest-size networks, with results obtainable in minutes or seconds by simple hand computation.The method is presented as a practical way to identify network problems and devise remedies.
  • Island States: BoE reports long-term averages, so networks can still exhibit temporal starvation when high-distance MIS states behave like isolated islands.In topology 7, two MIS have Hamming distance 6, allowing three links to remain starved for a long duration despite normalized throughput 0.5.
  • Networks with hidden nodes: The analysis focuses on networks without hidden nodes, and extension to hidden-node networks remains an open subject.A hidden-node-free network can be designed using the cited design principle.

6. CONCLUSIONS

The paper presents BoE as a fast, accurate throughput-distribution method and develops an interacting-process theory that explains its behavior and exposes structural properties of ideal CSMA networks.

  • 6. CONCLUSIONS: BoE computes throughput distributions simply and quickly, and is verified to be highly accurate for 802.11 networks.The method is intended for practical computation among links in a CSMA network.
  • 6. CONCLUSIONS: The theory models an ideal CSMA network as interacting on-off telegraph processes whose off-state durations are affected by neighboring transmissions.A link is on while transmitting and otherwise off; neighboring activity freezes its residual off-state time.
  • 6. CONCLUSIONS: The system state is time-reversible, and its stationary distribution is a Markov random field.These properties concern a process that is generally non-Markovian in time.
  • 6. CONCLUSIONS: The paper presents the MRF result as a first identification of carrier-sensing interactions in a wireless network producing a Markov random field.The authors suggest that MRF techniques and results may support work beyond this paper.

APPENDIX A: PRIOR METHODS IN COMPARISON WITH BOE

Appendix A contrasts BoE with prior analytical approaches, showing why general non-all-inclusive carrier-sensing networks make state-based throughput derivations difficult and why BoE can be more accurate.

  • Prior methods: Prior methods use Markov-chain state descriptions that become formidable in non-all-inclusive networks because transitions depend heavily on the contention graph.The overall state must include transmission status, collision counts, remaining countdown times, and remaining transmission times.
  • BoE approach: BoE simplifies the analysis by treating remaining countdown and transmission times as continuous variables, reducing the state space and allowing collisions to be ignored initially.Collision effects can be incorporated later through a perturbation adjustment if necessary.
  • Ng and Liew method: Ng and Liew’s approximation estimates overlapping airtimes using local observations and inclusion-exclusion constraints.The method bounds airtime overlap through carrier-sensing relationships among neighboring links.
  • Comparison: For one example, the normalized throughput vector is (0.93, 0.08, 0.51, 0.51), and BoE is more accurate than NS2’s benchmark comparison.The prior method fails to produce a correct solution for the second topology shown in Fig. A1.

APPENDIX B: INSENSITIVITY PROOF USING CONTINUOUS STATE-STATE APPROACH

Appendix B establishes the stationary density of the continuous state and uses it to derive the insensitivity of the transmission-state distribution to countdown and transmission-time forms.

  • State representation: The continuous state includes each link’s transmission status together with its residual countdown and residual transmission times.The proof defines feasible realizations of this combined state before evaluating its density.
  • Stationary density: Theorem B1 gives the stationary probability density as a product involving the transmission-state probability and residual-time density factors.The factors are indexed by transmitting, active-countdown, and system-wide link sets.
  • Insensitivity: Integrating the continuous-state density over residual times yields the transmission-state distribution sP.This distribution is insensitive to the forms of the countdown and transmission-time densities.
  • Residual-time property: The same density implies independent residual countdown and transmission times across different links.A transition of one link therefore does not affect the residual times of other links under the stated result.
  • Proof strategy: The proof begins from the system balance equation and shows that the proposed stationary density satisfies it by matching left- and right-hand terms.The derivation matches terms individually for transitions associated with countdown and transmission events.

Derivation of Balance Equation (B2)

The derivation formulates short-interval state evolution by separating jump events from ordinary countdown and transmission, then takes a derivative limit to obtain the balance equation (B2).

  • Equilibrium formulation: The state probability density at time t is analyzed at equilibrium through its limiting time evolution.The equilibrium condition is expressed as lim Δt→∞ dp(t,x)/dt = 0.
  • Short-interval evolution: During a short interval, state changes arise from countdown completions, transmission completions, or ordinary countdown and transmission without jumps.These contributions are represented by RC0, RT0, and CDTR.
  • Short-interval evolution: For a fixed state realization, the short-interval probability is decomposed into RT0, RC0, and CDTR contributions plus a vanishing-order remainder.The remainder satisfies o(Δt)/Δt → 0 as Δt → 0.
  • Transition conditions: A link finishing transmission within Δt must have residual transmission time in the interval (0, Δt) at the start of the interval.The analogous residual-time condition applies to countdown completion.
  • Balance equation: Substituting the short-interval transition expressions and taking the derivative limit yields the balance equation (B2).The derivation combines the component expressions before passing to the limit.

APPENDIX C: INSENSITIVITY PROOF USING “MIXTURE OF GAMMA DISTRIBTUTIONS” APPROACH

This appendix proves insensitivity by representing countdown and transmission times with gamma-distributed exponential stages and constructing a reversed process with the same equilibrium distribution.

  • Approach: The mixture-of-gamma approach is used to prove that the stationary transmission-state distribution is insensitive to countdown and transmission-time distributions.The appendix presents this limiting approach for the distributional insensitivity of P_s.
  • Gamma representation: Each countdown time has y exponential stages and each transmission time has z exponential stages, with means selected so their totals match the desired means.The extended state records the link status and remaining countdown or transmission stages.
  • Gamma case: Theorem C1 states that under gamma-distributed countdown and transmission times, the stationary distribution has the form determined by P_s and B in (4).The theorem identifies the stationary probability distribution of the extended process.
  • Reversed process: The reverse process uses transitions whose rates correspond to reversing countdown and transmission stage advances, while the forward process itself is not time-reversible in the illustrated state process.The proof checks the balance relation for connected states and compares forward and reverse transitions.
  • Reversed process: The proposed forward and reverse transition rates satisfy the equilibrium balance condition, so the same distribution serves as the equilibrium distribution for both processes.This follows by verifying the transition-rate relations for the three possible connected-state cases.

Mixtures of Gamma Distributions

Mixtures of gamma distributions extend the insensitivity result by randomizing the numbers of exponential stages while preserving the mean countdown and transmission durations.

  • Mixture construction: A new countdown stage count y and transmission stage count z is sampled from distributions P_Y(y) and P_Z(z).The resulting state records the sampled stage counts together with remaining stages and link status.
  • Mean preservation: The mixture distributions are constrained so their stage-count-weighted means equal the mean countdown and transmission times.The conditions are Σ_y P_Y(y)·y = E[T_cd]/d and Σ_z P_Z(z)·z = E[T_tr]/e, as represented in the supplied notation.
  • Insensitivity result: Theorem C2 states that the stationary distribution remains determined by P_s and B in (4) for these mixtures of gamma distributions.Thus the mixture construction preserves the stationary transmission-state distribution established for the gamma case.
  • Insensitivity result: Summing over possible stage counts and remaining stages recovers P_s in (4), matching the exponential-duration transmission-state distribution.For a fixed stage count, each remaining stage is equally likely under the construction described.

Approximating arbitrary distributions by taking limits on mixtures of gamma distributions

By concentrating mixture weights on large stage counts while holding mean durations fixed, the gamma mixtures approach deterministic and then arbitrary duration distributions without changing P_s.

  • Deterministic limit: For a fixed large stage count y, the conditional countdown-time variance tends to zero while its mean remains constant.The same limiting argument applies to transmission time as z becomes large.
  • Discrete distributions: Large stage counts map mixture components to concentrated duration distributions, providing an approximation for arbitrary discrete countdown and transmission-time distributions.Each stage-count distribution is mapped to a corresponding duration distribution.
  • Continuous distributions: Using sufficiently many possible stage counts provides an approximation for arbitrary continuous duration distributions.Under either discrete or continuous approximation, P_s in (4) remains valid by Theorem C2.
Loading 0712.1854v1…