Queue-Proportional Rate Allocation with Per-Link Information in Multihop Networks

Bin Li, R. SrikantACM SIGMETRICS Performance Evaluation Review 2015 · DOI

Abstract

The backpressure scheduling algorithm for multihop wireless networks is known to be throughput optimal, but it requires each node to maintain per-destination queues. Recently, a clever generalization of processor sharing has been proposed which is also throughput optimal, but which only uses per-link queues. Here we propose another algorithm called Queue Proportional Rate Allocation (QPRA) which also only uses per-link queues, and allocates service rates to links in proportion to their queue-lengths and employs the Serve-In-Random-Order (SIRO) discipline within each link. Through fluid limit techniques and using a novel Lyapunov function, we show that the QPRA achieves the maximum throughput. We demonstrate an advantage of QPRA by showing that, for the so-called primary interference model, it is able to develop a low-complexity scheduling scheme which approximates QPRA and achieves a constant fraction of the maximum throughput region, independent of network size.
BibTeX
@article{li2015queue,
  author = {Bin Li and R. Srikant},
  title = {{Queue-Proportional Rate Allocation with Per-Link Information in Multihop Networks}},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2015},
  doi = {10.1145/2796314.2745864},
}

Loading related content...

Figure