On the Queue-Overflow Probabilities of a Class of Distributed Scheduling Algorithms

Free registration required

Executive Summary

In this paper, the authors use large-deviations theory to characterize the asymptotic decay-rate of the queue-overflow probability for distributed wireless scheduling algorithms, as the overflow threshold approaches infinity. They consider ad-hoc wireless networks where each link interferes with a given set of other links, and they focus on a distributed scheduling algorithm called Q-SCHED, which is introduced by Gupta et al. First, they derive a lower bound on the asymptotic decay rate of the queue-overflow probability for Q-SCHED. Then present an upper bound on the decay rate for all possible algorithms operating on the same network. Finally, using these bounds, they conclude that, subject to a given constraint on the asymptotic decay rate of the queue-overflow probability, Q-SCHED can support a provable fraction of the offered loads achievable by any algorithms.

  • Format: PDF
  • Size: 261.7 KB