CS Paper Radar

Exponential Backoff: Meta-Stability and Implicit Admission Control

Richard Combes, Fabien Mathieu, Thomas Bonald

cs.NI cs.IT ·submitted 2026-09-29 09:08 UTC · v1
code/data

Abstract

We analyze exponential backoff, an algorithm used to share a single communication channel in a distributed manner between several users, in a similar way as many networking standards such as 802.11. We demonstrate that this algorithm has a meta-stable behavior, in the sense that the system oscillates over long time-scales between meta-stable configurations where only a subset of the sources effectively access the channel. In other words, meta-stability creates a form of implicit admission control. We provide both theoretical tools and numerical experiments to understand this phenomenon further. Our experiments are fully reproducible and the code is publicly available as a Python package available at https://pypi.org/project/slotted-aloha-simulator/.

Comment
25 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Self-Adaptive Threshold ALOHA

cs.NI ·2026-09-13 ·Ahsen Topbas, Aimin Li, Elif Tugce Ceran
benchmark similarity 0.59
Abstract · 5 pages, 3 figures

We propose Self-Adaptive Threshold ALOHA (SATA), a distributed random-access policy to minimize the Age of Information (AoI). SATA uses 1-bit broadcast feedback and requires no explicit coordination or message passing among nodes. {We show that this minimal feedback is sufficient for each node to perfectly track the number of active users and adjust its access probabilities accordingly.} For any initial network state, SATA converges to a collision-free TDMA steady state in finite time whenever the age threshold satisfies $Γ\geq n$, where $n$ is the network size. We derive closed-form expressions for the long-term average AoI and throughput in steady state, and establish that, for $Γ=n$, the expected transient duration scales as $O(n\log n)$. Simulation results confirm that SATA closely approaches TDMA performance across a wide range of network sizes, significantly outperforming Slotted ALOHA, Threshold ALOHA, and 1-persistent Threshold Slotted ALOHA. Notably, the performance gap between SATA and the benchmark random-access policies becomes more pronounced as network size grows.

0.34

Is Collision-Free Backoff Worth It in Wi-Fi?

cs.NI ·2026-09-03 ·Mohammad Yousefi, Francesc Wilhelmi, Boris Bellalta
similarity 0.57
Abstract · 8 pages, 5 figures, 3 tables. Submitted to the 17th IFIP Wireless and Mobile Networking Conference (WMNC 2026)

The Distributed Coordination Function (DCF)---the underlying channel access protocol in Wi-Fi, based on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) and Binary Exponential Backoff (BEB)---is simple and effective, but its performance can degrade with increasing contention due to collisions. Collision-free backoff algorithms replace randomization with deterministic channel access, potentially improving efficiency and predictability. But are collision-free methods, with all their implications in terms of protocol design, sufficient to improve Wi-Fi performance under realistic non-full-buffer traffic with both uplink and downlink transmissions? We investigate this question by comparing three collision-free algorithms, CSMA/ECA (ECA), CSMA/E2CA (E2CA), and deterministic backoff (DetBO), with standard and single-stage BEB. Using system-level simulations, we evaluate full-buffer traffic, non-full-buffer ON/OFF traffic with both uplink and downlink transmissions, and coexistence with legacy BEB stations. Under full-buffer traffic, collision-free operation provides only modest throughput gains, up to 6.3\%. With non-full-buffer traffic, delay is governed primarily by the contention window (CW) rather than by collision avoidance, and collision-free access can even degrade performance under downlink-heavy traffic. Stations fall back to a random backoff at least 93\% of the time, so a collision-free schedule rarely forms outside the AP.

0.27

Multi-connectivity in Wireless Access

cs.NI ·2026-11-17 ·Danny De Vleeschauwer, Chia-Yu Chang, Koen De Schepper, Lutz Ewe, Simone Bolettieri
similarity 0.54
Abstract

This paper investigates whether or not multi-connectivity, in which a User Equipment (UE) can simultaneously connect to multiple Access Points (APs), can offer a better Quality of Experience (QoE) to the users. Intuitively, multi-connectivity should offer a smoother bit rate (possibly at the expense of the average bit rate being slightly lower), so that adaptive applications can better determine at which throughput to send without introducing queueing latency. We mainly concentrate on how to share the resources of the APs amongst the UEs, modelling the lower layers via spectral efficiency and the higher layers via utility and its fluctuation. We explore various policies for resource allocation. Our results demonstrate that from the application point of view multi-connectivity is beneficial and show how to tune the parameters of the policies to obtain the best trade-off between average utility and its fluctuation.

0.27

Contention Resolution with a Fast-but-Fickle Channel

cs.DC ·2026-11-09 ·Umesh Biswas, Vini Chaudhary, Shafqat Hasan, Maxwell Young
theory similarity 0.52
Abstract

The contention-resolution problem studies how $n$ devices share a communication channel without centralized coordination. Classical models typically assume a single continuously available channel and focus on minimizing total completion time. However, modern wireless systems increasingly rely on shared spectrum, where access may be abruptly revoked by incumbent users. Motivated by this setting, we study contention resolution with two channels: a reliable slow channel and a faster channel that can be intermittently disabled by unpredictable eviction periods. Moving a batch of packets from the slow channel to the fast channel incurs a unit cost, while evictions from the fast channel impose a larger per-packet penalty. Our goal is to achieve asymptotically optimal latency while minimizing switching overhead relative to an optimal offline algorithm that knows the eviction schedule. We present Randomized Adaptive Channel Exploitation (RACE), a randomized algorithm that exploits the fast channel when available while maintaining progress on the slow channel during disruptions. When the fast channel has rate $ρ\in \bigl[Ω(\log n), O(\sqrt n)\bigr]$ and a sufficiently large constant-factor resource augmentation, RACE achieves an $O(1)$ competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is $O(ρ+\sqrt{n/m})$, where $m \geq 1$ is the number of fast-channel availability intervals used by OPT. We also prove a worst-case $Ω(\sqrt n)$ switching-cost competitive ratio for latency-competitive randomized algorithms, and a separate $Ω(ρ)$ switching-cost competitive-ratio lower bound. These lower bounds hold even with fixed constant-factor augmentation on both channels.

0.31

Analysis and Optimization of Age of Information in Large-Scale Random Access Networks

cs.NI ·2026-10-20 ·Yueqi Chen, Siqi Fan, Zhuoyi Zhao, I-Hong Hou, Igor Kadota
similarity 0.51
Abstract · 8 pages, 1 figure, 2 tables

We consider a large-scale network where multiple nodes transmit time-sensitive information via a shared channel to a wireless base station using a Carrier-Sense Multiple Access (CSMA) protocol. In this network, packet transmissions from different nodes are interdependent, making it challenging to analyze and optimize information freshness, captured by the Age of Information (AoI) metric. In this paper, we develop a tractable analytical framework for analyzing and optimizing the AoI. By combining mean-field approximation with first return time and renewal reward analysis, the proposed approach provides a fast, tractable, and accurate AoI approximation that explicitly accounts for carrier sensing, enabling us to quickly find the network parameters that minimize AoI. Since the framework is built on a finite-state Markov representation of the CSMA protocol, it applies to a broad class of Random Access systems. As a concrete example, we study age-threshold CSMA protocols and derive closed-form or efficiently computable AoI approximations under different protocol settings. We validate the proposed AoI analysis via extensive simulations, demonstrating a tight agreement between analysis and simulation.

0.28

Value-Based Massive Access through Goal-Oriented Irregular Repetition Slotted ALOHA

cs.NI cs.MA ·2026-09-17 ·Pietro Talli, Andrea Munari, Federico Mason, Federico Chiariotti, Andrea Zanella
similarity 0.51
Abstract

The goal-oriented communication paradigm is poised to enable novel real-time applications by easing the burden on communication networks while still delivering task-relevant information. However, efforts so far have focused on the encoding problem, while the design of medium access schemes is still in the early stages of development, especially when connectivity is to be provided to a massive number of devices, e.g., for remote monitoring. In this respect, existing goal-oriented approaches are often centralized or based on simplified underlying mechanisms, requiring unrealistic assumptions. In this work, we present the Goal-oriented Irregular Repetition Slotted ALOHA (GO-IRSA) scheme, which combines modern random access techniques with belief-based policies. GO-IRSA does not impose significant computing loads on the sensors or require frequent feedback, and it can reduce the average and worst-case error of the estimate of a distributed Wiener process by over 30% with respect to the optimal centralized solution in a network with thousands of sensors, and is robust to imperfect interference cancellation and inaccurate process knowledge.

0.26

Hidden in Rounds: Predicting the Time Cost of 802.11 Contention in Federated Learning

cs.LG cs.DC ·2026-09-11 ·Satwat Bashir, Tasos Dagiuklas
hot direction similarity 0.50
Abstract

Federated learning over IEEE~802.11 shares the wireless channel among clients that send model updates. We use ns-3 to measure the frame-delivery ratio and saturation throughput for different client densities and offered loads. A separate FedAvg trainer uses the frame-delivery ratio as a first-order proxy for the update-admission probability and uses an equation to estimate communication time. The method does not simulate the delivery of a complete model update or measure end-to-end training time. Across 720 evaluated runs with two datasets, two data partitions, six client densities, six offered loads, and five seeds, all runs reached their predefined target accuracy within the round budget. Rounds-to-target changed little with offered load, while communication time-to-target increased by about two orders of magnitude across the client-density range. A Bianchi-anchored estimator produced a mean absolute percentage error from $2.3\%$ to $10.2\%$ on held-out configurations. This error is measured against communication time constructed from the same round-duration equation, not against independently measured completion time. We also compare uniform participation with persistent heterogeneous participation. The study does not detect a statistically distinguishable excluded-class accuracy gap over five seeds, but the confidence intervals are wide. The results apply only to the evaluated configurations and do not provide a general convergence or fairness guarantee.

0.34

Channel-Token Attention for Reliable Dynamic Spectrum Access under Bursty Primary-User Traffic

cs.NI cs.LGeess.SP ·2026-08-24 ·Krishna Acharya, Dinanath Padhya, Utsab Dahal, Ashish Kandel, Binod Sapkota
similarity 0.50
Abstract · 9 pages, 4 figures, 2 tables

Dynamic spectrum access must coordinate secondary users under bursty primary-user activity while preserving packet reliability and delay. We present TACAN, a centralized policy that represents each channel as a token containing occupancy history and automatic-modulation-classification entropy; a context token supplies queue class, delay and user identity. A Transformer encoder is warm-started from an occupancy-greedy policy and refined with proximal policy optimization. The frozen policies were trained to maintain a channel assignment in every slot, including when queues were empty. We therefore replay them on held-out trajectories and distinguish standby assignment success from packet-present access and packet delivery. In a 20-channel network with 60 primary devices and 4 secondary users, TACAN achieves 92.53% +/- 0.47 packet-present access success, compared with 89.94% for Greedy and 83.53% for PPO+MLP. Its paired gain over Greedy is 2.59 points (parametric 95% CI 1.89-3.29), with wins in all five seeds; the exact two-sided sign-test value is 0.0625. The gain rises from 0.57 points at normal primary-user load to 7.67 points at extreme load. TACAN also reduces mean delivery delay from 1.208 to 1.123 slots and the conditional user-reliability gap from 9.69 to 3.15 points. Delivered packets per SU-slot remain arrival-limited (30.12% versus 30.11%), so no packet-throughput gain is claimed.

0.30