Queue-Proportional Rate Allocation with Per-Link Information in Multihop Networks
Lists
Only you see this
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...