Queues with random back-offs (Q742451)

The paper under review studies a broad class of queueing models with random state-dependent vacation periods. This class of models arises in the analysis of queue-based back-off algorithms in wireless random access networks. The paper under review considers an \(\mathrm{M}/\mathrm{G}/1\) queue with vacations. The server of this queueing system can be active or inactive. When active, customers are served with generally distributed service times having finite second moment. The service times are assumed to be independent of the interarrival and vacation times. Immediately after the service completion that leaves \(i\) customers behind, the server becomes inactive with probability \(\psi(i)\), \(\psi(0)=1\). When the server is inactive, no customer is served and the server is said to be on vacation. The server becomes active after random time depending on the number of waiting customers at the beginning of the vacation period and the number of customers arriving during the vacation period, but it does not depend on future arrivals. The paper first presents exact queue-length and delay results for some specific cases and derives stochastic bounds for a richer set of scenarios. On the basis of this, together with stochastic relations between systems with different vacation disciplines, the paper examines the scaled queue-length and delay in a heavy-traffic regime, and demonstrates a sharp trichotomy, depending on how the activation rate and vacation probability behave as functions of queue-length. In particular, the effect of the vacation periods may either (i) completely vanish in heavy traffic conditions, (ii) contribute an additional term to the queue-length and delays of similar magnitude, or (iii) give rise to an order-of-magnitude increase.