Stochastic network utility maximization and wireless scheduling

Layering As optimization Decomposition (LAD) has offered a first-principled, top-down approach to derive, rather than just describe, network architectures. Incorporating stochastic network dynamics is one of the main directions to refine the approach and extend its applicability. In this chapter, we survey the latest results on Stochastic Network Utility Maximization (SNUM) across session, packet, channel, and topology levels. Developing simple yet effective distributed algorithms is another challenge often faced in LAD, such as scheduling algorithms for SNUM in wireless networks. We provide a taxonomy of the results on wireless scheduling and highlight the recent progress on understanding and reducing communication complexity of scheduling algorithms. Introduction The papers by Kelly et al. presented an innovative idea on network resource allocation – Network Utility Maximization (NUM) – that has led to many research activities since. In the basic NUM approach, an optimization problem is formulated where the variables are the source rates constrained by link capacities and the objective function captures design goals: where the source rate vector x is the set of optimization variables, one for each of the sources indexed by i, the {0, 1} routing matrix R and link capacity vector c are constants, and Ui(·) is the utility function of source i. Decomposing the above problem into several sub-problems enables a distributed algorithm to be developed elegantly, where each of the links and sources controls its local variable, such as link price or source rate, based on local observables, such as link load or path price.