Queue-proportional rate allocation with per-link information in multihop networks

Bin Li, R. Srikant

Research output: Contribution to journalConference articlepeer-review

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 uid 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.

Original languageEnglish (US)
Pages (from-to)97-108
Number of pages12
JournalPerformance Evaluation Review
Volume43
Issue number1
DOIs
StatePublished - Jun 24 2015
EventACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015

Keywords

  • Fluid limit analysis
  • Low-complexity scheduler design
  • Lyapunov functions
  • Maximum throughput
  • Multihop wireless networks
  • Resource allocation

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Queue-proportional rate allocation with per-link information in multihop networks'. Together they form a unique fingerprint.

Cite this