Abstract
We study the fundamental problem of utilization of the channel shared by stations competing to transmit packets on the channel. In their turn, packets are continuously injected into stations' queues by an adversary at a rate at most ρ packets per round. The aim of the distributed medium access control algorithms is to successfully transmit packets and maintain system stability (bounded queues). We further restrain algorithms by introducing an upper bound k on the allowed number of active stations in any given round. We construct adaptive and full sensing protocols with optimal throughput 1 and almost optimal throughput 1−ϵ (for any positive ϵ), respectively, in a constant-restrained channel. On the opposite side, we show that restricted protocols based on schedules known in advance suffer from a substantial drop of throughput, at most [Formula presented]. We compare our algorithms experimentally with well-known backoff protocols.
Original language | English (US) |
---|---|
Article number | 103463 |
Journal | Journal of Computer and System Sciences |
Volume | 138 |
DOIs | |
State | Published - Dec 2023 |
Keywords
- Adversarial queueing
- Contention resolution
- Multiple-access channel
- Restrained channel
- Stability
- Throughput
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics