Stochastic network utility maximization and wireless scheduling

Yung Yi, Mung Chiang

Research output: Chapter in Book/Report/Conference proceedingChapter


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.

Original languageEnglish (US)
Title of host publicationNext-Generation Internet
Subtitle of host publicationArchitectures and Protocols
PublisherCambridge University Press
Number of pages35
ISBN (Electronic)9780511920950
ISBN (Print)9780521113687
StatePublished - Jan 1 2008

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Stochastic network utility maximization and wireless scheduling'. Together they form a unique fingerprint.

Cite this