Network Utility Maximization: Advances and Applications
Network Utility Maximization (NUM) significantly extends the classical
network flow problem and provides an emerging framework to design a
variety of resource allocation algorithms, such as TCP congestion control,
and to understand layering as optimization decomposition. This talk
presents a summary of selected recent advances on open issues in the NUM
framework. We present new distributed algorithms that converge to the
globally optimal rate allocation for NUM problems with nonconcave utility
functions representing inelastic flows, with coupled utility functions
representing interference effects or hybrid social-selfish utilities, and
with rate-reliability tradeoff through adaptive channel coding in the
physical layer. We also discuss the equilibrium properties of co-existence
of heterogeneous congestion control protocols, correspondence of different
decompositions of a generalized NUM problem to different layering
architectures, and remaining open issues on NUM.
These recent results substantially expand the scope of the basic
version of NUM, which is a classical monotropic program, by utilizing
interesting mathematical theories such as distributed subgradient
algorithms based on subdifferential calculus, Poincare-Hopf theorem in
differential topology, and Positivstellensatz in real algebraic geometry.
The power of such mathematics enables us to rigorously understand Internet
protocols and design new algorithms for communication systems such as
broadband access networks.
This talk is based on several preprints co-authored with A. R.
Calderbank,
M. Fazel, P. Hande, J. W. Lee, S. H. Low, D. Palomar, A. Tang, J. Wang at
Princeton and Caltech.