TY - GEN

T1 - Resource allocation over network dynamics without timescale separation

AU - Proutiere, Alexandre

AU - Yi, Yung

AU - Tian, Lan

AU - Chiang, Mung

PY - 2010/6/15

Y1 - 2010/6/15

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

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

UR - http://www.scopus.com/inward/record.url?scp=77953308006&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77953308006&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2010.5462201

DO - 10.1109/INFCOM.2010.5462201

M3 - Conference contribution

AN - SCOPUS:77953308006

SN - 9781424458363

T3 - Proceedings - IEEE INFOCOM

BT - 2010 Proceedings IEEE INFOCOM

T2 - IEEE INFOCOM 2010

Y2 - 14 March 2010 through 19 March 2010

ER -