Distributed queue-length based algorithms for optimal end4o-end throughput allocation and stability in multi-hop random access networks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a model of wireless network with random (slotted-Aloha-type) access and with multi-hop flow routes. The goal is to devise distributed strategies for optimal utility-based end-to-end throughput allocation and queueing stability. We consider a class of queue back-pressure random - Access algorithms (QBRA), where actual queue lengths of the flows (in each node's close neighborhood) are used to determine nodes' channel access probabilities. This is in contrast to previously proposed algorithms, which are purely optimization-based and oblivious of actual queues. QBRA is also substantially different from much studied "MaxWeight" type scheduling algorithms, also using back-pressurE. For the model with infinite backlog at each flow source, we show that QBRA, combined with simple congestion control local to each source, leads to optimal end-to-end throughput allocation, within the network saturation throughput region achievable by a random access. ( o end-to-end message passing is required.) This scheme generalizes for the case of additional, minimum flow rate constraints. For the model with stochastic exogenous arrivals, we show that QBRA ensures stability of the queues as long as nominal loads of the nodes are within the saturation throughput region. Simulation comparison of QBRA and (queue oblivious) optimization-based random access algorithms, shows that QBRA performs better in terms of end-to-end delays.

Original languageEnglish (US)
Title of host publication45th Annual Allerton Conference on Communication, Control, and Computing 2007
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages1260-1267
Number of pages8
ISBN (Electronic)9781605600864
StatePublished - Jan 1 2007
Externally publishedYes
Event45th Annual Allerton Conference on Communication, Control, and Computing 2007 - Monticello, United States
Duration: Sep 26 2007Sep 28 2007

Publication series

Name45th Annual Allerton Conference on Communication, Control, and Computing 2007
Volume2

Other

Other45th Annual Allerton Conference on Communication, Control, and Computing 2007
CountryUnited States
CityMonticello
Period9/26/079/28/07

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Distributed queue-length based algorithms for optimal end4o-end throughput allocation and stability in multi-hop random access networks'. Together they form a unique fingerprint.

Cite this