Resource allocation over network dynamics without timescale separation

Alexandre Proutiere, Yung Yi, Lan Tian, Mung Chiang

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

32 Scopus citations

Abstract

We consider a widely applicable model of resource allocation where two sequences of events are coupled: on continuous time axis (t), network dynamics evolve over time. On a discrete time axis [t], certain control laws update resource allocation variables according to some proposed algorithm. The algorithmic updates, together with exogenous events out of the algorithm's control, change the network dynamics, which in turn changes the trajectory of the algorithm, thus forming a loop that couples the two sequences of events. In between the algorithmic updates at [t - 1] and [t], the network dynamics continue evolve randomly as influenced by the previous variable settings at time [t - 1]. The standard way used to avoid the subsequent analytic difficulty is to assume the separation of timescales, which in turn unrealistically requires either slow network dynamics or high complexity algorithms. In this paper, we develop an approach that does not require separation of timescales. It based on the use of stochastic approximation algorithms with continuous-time controlled Markov noise. We prove convergence of these algorithms without assuming timescale separation. This approach is applied to develop simple algorithms that solve the problem of utility-optimal random access in multi-channel, multiradio wireless networks.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
DOIs
StatePublished - Jun 15 2010
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2010
CountryUnited States
CitySan Diego, CA
Period3/14/103/19/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Resource allocation over network dynamics without timescale separation'. Together they form a unique fingerprint.

Cite this