pith. sign in

arxiv: 2604.12400 · v1 · submitted 2026-04-14 · 💻 cs.NI

Throughput Characterization of Wireless CSMA Networks With Arbitrary Sensing and Interference Topologies

Xinghua Sun , Wenhai Lin , Ruike Zhou This is my paper

Pith reviewed 2026-05-10 14:37 UTC · model grok-4.3

classification 💻 cs.NI
keywords CSMA networksthroughput analysissensing graphMarkov renewal processwireless networksarbitrary topologieshidden terminalIEEE 802.11
0
0 comments X

The pith

A new framework produces explicit throughput expressions for CSMA networks with arbitrary sensing and interference topologies, without assuming zero propagation delay.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a method to derive closed-form throughput values in wireless CSMA networks where links interact through complex, arbitrary sensing and interference patterns. It does so by converting the sensing graph into an equivalent multi-channel structure based on its clique properties and then tracking the system with a discrete-time Markov renewal process. This captures global couplings among links even when propagation delays are present. The approach matters for practical networks because it supports accurate performance prediction and access-parameter tuning in dense deployments and topologies that include hidden terminals or exposed terminals. Simulations in the paper indicate the resulting expressions outperform earlier models when link behaviors are strongly interdependent.

Core claim

By exploiting the clique structure of the sensing graph, the original CSMA network transforms into an equivalent multi-channel network whose dynamics are fully described by a discrete-time Markov renewal process; this yields explicit throughput expressions that hold for arbitrary interference topologies and nonzero propagation delays.

What carries the argument

The clique-based transformation of the sensing graph into an equivalent multi-channel network, whose state evolution is captured by a discrete-time Markov renewal process.

If this is right

  • Throughput expressions become available for representative cases such as multi-BSS IEEE 802.11 networks with universal frequency reuse and ad-hoc topologies that exhibit hidden-terminal, exposed-terminal, or flow-in-the-middle effects.
  • The effect of access parameters on network performance can be evaluated analytically rather than through exhaustive simulation.
  • In dense deployments where link couplings are strong, the model supplies more accurate throughput estimates than prior analytical methods.
  • The framework removes the zero-propagation-delay restriction that has limited earlier CSMA analysis.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Protocol designers could plug measured sensing graphs directly into the formulas to select backoff parameters that maximize aggregate throughput.
  • The same clique-to-multi-channel reduction might apply to other random-access schemes whose contention relations can be represented by graphs.
  • If the transformation scales to time-varying topologies, it would enable online throughput prediction in mobile ad-hoc settings.
  • The approach isolates the sensing graph as the primary determinant of capacity, suggesting that topology control algorithms could target clique minimization to improve performance.

Load-bearing premise

The clique structure of the sensing graph always allows an exact, lossless mapping to a multi-channel network whose Markov renewal dynamics capture every global coupling among links.

What would settle it

Measured throughputs in a physical testbed or detailed simulation of a CSMA network with arbitrary sensing and interference graphs and nonzero propagation delays that deviate substantially from the framework's explicit formulas would falsify the claim of exact characterization.

Figures

Figures reproduced from arXiv: 2604.12400 by Ruike Zhou, Wenhai Lin, Xinghua Sun.

Figure 1
Figure 1. Figure 1: Representative topological scenarios in wireless CSMA net [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the sensing graph GS, the interference graph GI , and the equivalent multi-channel network. This limitation becomes increasingly pronounced in dense networks, where non-negligible propagation delay and syn￾chronous access attempts can substantially affect throughput. Moreover, many set-centric formulations are built on conflict￾graph abstractions or aligned sensing/interference assump￾tions… view at source ↗
Figure 3
Figure 3. Figure 3: States of the logical channels. time time Busy B Busy B Channel 1 begins starts at The -transition occurs The +1-transition occurs time Busy B Channel 2 begins starts at Channel 3 begins starts at [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Definition and calculation of D (i) j . B. Multi-Channel Model The channel dynamics of the equivalent multi-channel net￾work are modeled by a discrete-time Markov renewal process (X ,V ) = {(Xj , Vj ), j = 0, 1, . . .}, where Vj denotes the epoch of the j-th state transition and Xj denotes the network state immediately after that transition. The state Xj is defined as Xj =  X (1) j , X(2) j , . . . , X(N)… view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the calculation of the probability that a trans [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of link aggregation. an explicit function of both τ and q: λˆ 2 = τ q2 [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Total network throughput performance in a two-BSS network with () ({}) ({}) ({}) [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Illustration of ad-hoc scenarios. of multiple autonomous nodes that communicate directly with one another without centralized infrastructure. Due to the absence of coordinating entities such as APs, ad-hoc networks are more vulnerable to interference-related phenomena. In this subsection, we consider a representative topology that simul￾taneously exhibits the hidden-terminal problem, the exposed￾terminal p… view at source ↗
Figure 9
Figure 9. Figure 9: This topology simultaneously exhibits hidden-terminal, [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 9
Figure 9. Figure 9: Sensing graph and interference graph of an ad-hoc network with nine links. [PITH_FULL_IMAGE:figures/full_fig_p011_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Throughput performance of the ad-hoc network in Fig. 9 with [PITH_FULL_IMAGE:figures/full_fig_p011_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Total network throughput for the topology in Fig. 9, with [PITH_FULL_IMAGE:figures/full_fig_p011_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Coefficient matrix A in (29). [7] R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin, “Throughput analysis in multihop csma packet radio networks,” IEEE Transactions on Communications, vol. 35, no. 3, pp. 267–274, 1987. [8] X. Wang and K. Kar, “Throughput modelling and fairness issues in csma/ca based ad-hoc networks,” in Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communica… view at source ↗
read the original abstract

The performance analysis of wireless CSMA networks is notoriously difficult due to the intricate sensing and interference relationships among links. Even the fundamental problem of throughput characterization remains open when sensing and interference topologies are both arbitrary. In this paper, we develop a new analytical framework for throughput characterization in wireless CSMA networks with arbitrary sensing and interference topologies. The proposed framework yields explicit throughput expressions without relying on the commonly adopted zero-propagation-delay assumption. The key idea is to exploit the clique structure of the sensing graph to transform the original CSMA network into an equivalent multi-channel network, and then model its dynamics through a discrete-time Markov renewal process. In this way, the framework explicitly captures global coupling among links and enables analytical evaluation of how access parameters affect network performance. The proposed analysis is applied to several representative CSMA scenarios, including networks with multi-BSS IEEE 802.11 networks with universal frequency reuse, and ad-hoc topologies exhibiting hidden-terminal, exposed-terminal, and flow-in-the-middle effects. Simulation results show that, in dense deployments and in scenarios with strong coupling among link behaviors, the proposed model significantly outperforms existing analytical approaches in throughput estimation and enables more accurate determination of access parameters.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to develop an analytical framework for throughput characterization of wireless CSMA networks under arbitrary sensing and interference topologies. It transforms the network into an equivalent multi-channel system by exploiting maximal cliques in the sensing graph, then applies a discrete-time Markov renewal process to derive explicit throughput expressions without the zero-propagation-delay assumption. The framework is used to analyze multi-BSS 802.11 networks and ad-hoc topologies with hidden/exposed terminals and flow-in-the-middle effects, with simulations showing improved accuracy over prior methods in dense or strongly coupled scenarios.

Significance. If the central transformation is shown to be exact and lossless, the result would be significant: it would resolve an open problem in CSMA performance analysis by providing closed-form throughput expressions that capture global couplings for arbitrary topologies and enable direct evaluation of access-parameter effects, outperforming existing approximations especially in dense deployments.

major comments (2)
  1. [§3] §3 (Transformation to equivalent multi-channel network): the claim that grouping links by sensing cliques produces a lossless equivalent model whose Markov renewal states and transitions fully encode all interference-induced couplings must be proven for the case where an interference edge connects links belonging to distinct sensing cliques. If such cross-clique interference is not explicitly represented by additional state variables or transition probabilities, the resulting throughput expressions will omit certain collision and deferral events, undermining the assertion that all global couplings are captured without the zero-delay assumption.
  2. [§5] §5 (Application to flow-in-the-middle and hidden-terminal scenarios): the simulation comparisons report improved throughput estimation, but the paper must quantify the residual error attributable to any unmodeled cross-clique interference (e.g., via an ablation that disables the cross-clique handling). Without this, it is unclear whether the reported gains stem from the new framework or from other modeling choices.
minor comments (2)
  1. [Abstract] The abstract states that the framework 'yields explicit throughput expressions' yet provides no illustrative formula or reference to the final closed-form result; adding one compact example expression would improve readability.
  2. [§4] Notation for the renewal-process states (e.g., the definition of the multi-channel state vector) should be introduced earlier and used consistently when deriving the throughput formula.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below, providing explanations and indicating planned revisions where appropriate.

read point-by-point responses

  1. Referee: [§3] §3 (Transformation to equivalent multi-channel network): the claim that grouping links by sensing cliques produces a lossless equivalent model whose Markov renewal states and transitions fully encode all interference-induced couplings must be proven for the case where an interference edge connects links belonging to distinct sensing cliques. If such cross-clique interference is not explicitly represented by additional state variables or transition probabilities, the resulting throughput expressions will omit certain collision and deferral events, undermining the assertion that all global couplings are captured without the zero-delay assumption.

    Authors: The transformation is lossless because the maximal cliques of the sensing graph partition the carrier-sensing constraints into independent channels, ensuring that all intra-clique deferrals and mutual exclusions are captured by the channel occupancy states. Cross-clique interference edges from the separate interference graph are incorporated directly into the transition probabilities and success rates of the discrete-time Markov renewal process: when a transmission begins on one clique-channel, the probability of collision or deferral explicitly sums over all interfering links in other cliques. The renewal cycle durations and throughput expressions therefore account for every collision and deferral event induced by cross-clique interference. We will add a formal lemma in the revised §3 that proves equivalence of the resulting throughput formulas to the original network for arbitrary interference graphs, including the cross-clique case. revision: yes

  2. Referee: [§5] §5 (Application to flow-in-the-middle and hidden-terminal scenarios): the simulation comparisons report improved throughput estimation, but the paper must quantify the residual error attributable to any unmodeled cross-clique interference (e.g., via an ablation that disables the cross-clique handling). Without this, it is unclear whether the reported gains stem from the new framework or from other modeling choices.

    Authors: Our framework models cross-clique interference explicitly through the interference graph within the Markov renewal transitions, so there is no unmodeled component of this type. The observed accuracy improvements in dense and strongly coupled scenarios therefore arise from the clique-based global coupling capture and the removal of the zero-propagation-delay assumption. In the revision we will expand §5 with an analytical decomposition of the error sources and a direct comparison of throughput expressions with and without cross-clique terms, demonstrating that omitting them recovers the higher-error behavior of prior approximations. If an empirical ablation is still desired, we can add the corresponding simulation curves. revision: partial

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper constructs its framework by exploiting the clique structure of the sensing graph to create an equivalent multi-channel network and then applying a discrete-time Markov renewal process to derive explicit throughput expressions. This modeling step is presented as a novel transformation based on standard graph theory and renewal theory, independent of the target throughput results. No equations or steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the central claim remains a general analytical method applicable to arbitrary topologies and validated externally via simulations. The derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract does not enumerate free parameters, axioms, or invented entities; full manuscript details would be required to populate the ledger.

pith-pipeline@v0.9.0 · 5509 in / 1156 out tokens · 38574 ms · 2026-05-10T14:37:32.845041+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Packet switching in radio channels: Part i-carrier sense multiple-access modes and their throughput-delay characteristics,

    L. Kleinrock and F. Tobagi, “Packet switching in radio channels: Part i-carrier sense multiple-access modes and their throughput-delay characteristics,”IEEE Transactions on Communications, vol. 23, no. 12, pp. 1400–1416, 1975

    work page 1975

  2. [2]

    Performance Analysis of the IEEE 802.11 Distributed Coordination Function,

    G. Bianchi, “Performance Analysis of the IEEE 802.11 Distributed Coordination Function,”IEEE Journal on selected areas in communi- cations, vol. 18, no. 3, pp. 535–547, 2000

    work page 2000

  3. [3]

    Modeling the 802.11 dis- tributed coordination function in nonsaturated heterogeneous condi- tions,

    D. Malone, K. Duffy, and D. J. Leith, “Modeling the 802.11 dis- tributed coordination function in nonsaturated heterogeneous condi- tions,”IEEE/ACM Transactions on Networking, vol. 15, no. 1, pp. 159– 172, 2007

    work page 2007

  4. [4]

    Unsaturated throughput analysis of IEEE 802.11 in presence of non ideal trans- mission channel and capture effects,

    F. Daneshgaran, M. Laddomada, F. Mesiti, and M. Mondin, “Unsaturated throughput analysis of IEEE 802.11 in presence of non ideal trans- mission channel and capture effects,”IEEE Transactions on Wireless Communications, vol. 7, no. 4, pp. 1276–1286, 2008

    work page 2008

  5. [5]

    A unified analysis of IEEE 802.11 DCF networks: Stability, throughput, and delay,

    L. Dai and X. Sun, “A unified analysis of IEEE 802.11 DCF networks: Stability, throughput, and delay,”IEEE Transactions on Mobile Com- puting, vol. 12, no. 8, pp. 1558–1572, 2013

    work page 2013

  6. [6]

    Backoff design for IEEE 802.11 DCF networks: Fundamental tradeoff between throughput performance and delay,

    ——, “Backoff design for IEEE 802.11 DCF networks: Fundamental tradeoff between throughput performance and delay,”IEEE/ACM Trans- actions on Networking, vol. 23, no. 4, pp. 1196–1209, 2015. 14 A=   ρ1ρ2ρ3 − 1 τ g(1) · · · g(τ−1) ρ2 +g(τ) h(1) · · · h(τ−1) ρ3 +h(τ) ρ1ρ2(1−ρ 3) 0 0 0 0 0 1−ρ 3 0 ρ2 · · · 0 0 0 · · · 1−ρ 3 0 ... ... ... ... .....

    work page 2015

  7. [7]

    Throughput analysis in multihop csma packet radio networks,

    R. Boorstyn, A. Kershenbaum, B. Maglaris, and V . Sahin, “Throughput analysis in multihop csma packet radio networks,”IEEE Transactions on Communications, vol. 35, no. 3, pp. 267–274, 1987

    work page 1987

  8. [8]

    Throughput modelling and fairness issues in csma/ca based ad-hoc networks,

    X. Wang and K. Kar, “Throughput modelling and fairness issues in csma/ca based ad-hoc networks,” inProceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., vol. 1. Ieee, 2005, pp. 23–34

    work page 2005

  9. [9]

    On the fairness of large csma networks,

    M. Durvy, O. Dousse, and P. Thiran, “On the fairness of large csma networks,”IEEE Journal on Selected Areas in Communications, vol. 27, no. 7, pp. 1093–1104, 2009

    work page 2009

  10. [10]

    On the interactions between multiple overlapping wlans using channel bonding,

    B. Bellalta, A. Checco, A. Zocca, and J. Barcelo, “On the interactions between multiple overlapping wlans using channel bonding,”IEEE Transactions on Vehicular Technology, vol. 65, no. 2, pp. 796–812, 2015

    work page 2015

  11. [11]

    Analysis of dynamic channel bonding in dense networks of wlans,

    A. Faridi, B. Bellalta, and A. Checco, “Analysis of dynamic channel bonding in dense networks of wlans,”IEEE Transactions on Mobile Computing, vol. 16, no. 8, pp. 2118–2131, 2016

    work page 2016

  12. [12]

    Computing the saturation throughput for heterogeneous p-csma in a general wireless network,

    F. D. Tarzjani and B. Krishnamachari, “Computing the saturation throughput for heterogeneous p-csma in a general wireless network,” in2025 34th International Conference on Computer Communications and Networks (ICCCN). IEEE, 2025, pp. 1–7

    work page 2025

  13. [13]

    Back-of-the-envelope computation of throughput distributions in csma wireless networks,

    S. C. Liew, C. Kai, J. Leung, and B. Wong, “Back-of-the-envelope computation of throughput distributions in csma wireless networks,” in 2009 IEEE International Conference on Communications, 2009, pp. 1– 6

    work page 2009

  14. [14]

    Throughput analysis of ieee802. 11 multi- hop ad hoc networks,

    P. C. Ng and S. C. Liew, “Throughput analysis of ieee802. 11 multi- hop ad hoc networks,”IEEE/ACM Transactions on networking, vol. 15, no. 2, pp. 309–322, 2007

    work page 2007

  15. [15]

    Determining the end-to-end through- put capacity in multi-hop networks: methodology and applications,

    Y . Gao, D.-M. Chiu, and J. C. Lui, “Determining the end-to-end through- put capacity in multi-hop networks: methodology and applications,” in Proceedings of the joint international conference on Measurement and modeling of computer systems, 2006, pp. 39–50

    work page 2006

  16. [16]

    The achievable rate region of 802.11- scheduled multihop networks,

    A. Jindal and K. Psounis, “The achievable rate region of 802.11- scheduled multihop networks,”IEEE/ACM Transactions on Networking, vol. 17, no. 4, pp. 1118–1131, 2009

    work page 2009

  17. [18]

    Modeling media access in embedded two-flow topologies of multi-hop wireless networks,

    M. Garetto, J. Shi, and E. W. Knightly, “Modeling media access in embedded two-flow topologies of multi-hop wireless networks,” in Proceedings of the 11th annual international conference on Mobile computing and networking, 2005, pp. 200–214

    work page 2005

  18. [19]

    IEEE 802.11 saturation throughput analysis in the presence of hidden terminals,

    B.-J. Jang and M. L. Sichitiu, “IEEE 802.11 saturation throughput analysis in the presence of hidden terminals,”IEEE/ACM Transactions on Networking, vol. 20, no. 2, pp. 557–570, 2012

    work page 2012

  19. [20]

    Spatial reuse in IEEE 802.11ax WLANs,

    F. Wilhelmi, S. Barrachina-Mu ˜noz, C. Cano, I. Selinis, and B. Bellalta, “Spatial reuse in IEEE 802.11ax WLANs,”Computer Communications, vol. 170, pp. 65–83, 2021

    work page 2021

  20. [21]

    Performance analysis of the IEEE 802.11ax OBSS PD-based spatial reuse,

    L. Lanante and S. Roy, “Performance analysis of the IEEE 802.11ax OBSS PD-based spatial reuse,”IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 616–628, 2022

    work page 2022

  21. [22]

    Modeling per-flow throughput and capturing starvation in csma multi-hop wireless net- works,

    M. Garetto, T. Salonidis, and E. W. Knightly, “Modeling per-flow throughput and capturing starvation in csma multi-hop wireless net- works,”IEEE/ACM Transactions on Networking, vol. 16, no. 4, pp. 864–877, 2008

    work page 2008

  22. [23]

    Closed-form throughput expressions for csma networks with collisions and hidden terminals,

    B. Nardelli and E. W. Knightly, “Closed-form throughput expressions for csma networks with collisions and hidden terminals,” in2012 Proceedings IEEE INFOCOM. IEEE, 2012, pp. 2309–2317

    work page 2012

  23. [24]

    Towards performance modeling of ieee 802.11 based wireless networks: A unified framework and its applica- tions,

    K. Medepalli and F. A. Tobagi, “Towards performance modeling of ieee 802.11 based wireless networks: A unified framework and its applica- tions,” inProceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications. IEEE, 2006, pp. 1–12

    work page 2006

  24. [25]

    Algorithm 457: finding all cliques of an undirected graph,

    C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,”Commun. ACM, vol. 16, no. 9, p. 575–577, Sept

    work page

  25. [26]

    Available: https://doi.org/10.1145/362342.362367

    [Online]. Available: https://doi.org/10.1145/362342.362367

    work page doi:10.1145/362342.362367

  26. [27]

    Rethinking the ieee 802.11 e edca perfor- mance modeling methodology,

    I. Tinnirello and G. Bianchi, “Rethinking the ieee 802.11 e edca perfor- mance modeling methodology,”IEEE/ACM transactions on networking, vol. 18, no. 2, pp. 540–553, 2009

    work page 2009

  27. [28]

    Synchronous Multi-Link Access in IEEE 802.11 be: Modeling and Network Sum Rate Optimization,

    J. Zhang, Y . Gao, X. Sun, W. Zhan, P. Liu, and Z. Guo, “Synchronous Multi-Link Access in IEEE 802.11 be: Modeling and Network Sum Rate Optimization,” inProc. IEEE ICC, 2022, pp. 2309–2314

    work page 2022

  28. [29]

    Throughput optimization of multi-bss ieee 802.11 networks with universal frequency reuse,

    Y . Gao, L. Dai, and X. Hei, “Throughput optimization of multi-bss ieee 802.11 networks with universal frequency reuse,”IEEE Transactions on Communications, vol. 65, no. 8, pp. 3399–3414, 2017

    work page 2017

  29. [30]

    Arboricity and subgraph listing algorithms,

    N. Chiba and T. Nishizeki, “Arboricity and subgraph listing algorithms,” SIAM Journal on computing, vol. 14, no. 1, pp. 210–223, 1985

    work page 1985

  30. [31]

    Planar orientations with low out-degree and compaction of adjacency matrices,

    M. Chrobak and D. Eppstein, “Planar orientations with low out-degree and compaction of adjacency matrices,”Theoretical Computer Science, vol. 86, no. 2, pp. 243–266, 1991

    work page 1991