A tutorial on decomposition methods for network utility maximization
Top Cited Papers
- 31 July 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 24 (8) , 1439-1451
- https://doi.org/10.1109/jsac.2006.879350
Abstract
A systematic understanding of the decomposability structures in network utility maximization is key to both resource allocation and functionality allocation. It helps us obtain the most appropriate distributed algorithm for a given network resource allocation problem, and quantifies the comparison across architectural alternatives of modularized network design. Decomposition theory naturally provides the mathematical language to build an analytic foundation for the design of modularized and distributed control of networks. In this tutorial paper, we first review the basics of convexity, Lagrange duality, distributed subgradient method, Jacobi and Gauss-Seidel iterations, and implication of different time scales of variable updates. Then, we introduce primal, dual, indirect, partial, and hierarchical decompositions, focusing on network utility maximization problem formulations and the meanings of primal and dual decompositions in terms of network architectures. Finally, we present recent examples on: systematic search for alternative decompositions; decoupling techniques for coupled objective functions; and decoupling techniques for coupled constraint sets that are not readily decomposableKeywords
This publication has 17 references indexed in Scilit:
- A tutorial on cross-layer optimization in wireless networksIEEE Journal on Selected Areas in Communications, 2006
- An introduction to convex optimization for communications and signal processingIEEE Journal on Selected Areas in Communications, 2006
- Jointly optimal congestion and contention control based on network utility maximizationIEEE Communications Letters, 2006
- Price-based distributed algorithms for rate-reliability tradeoff in network utility maximizationIEEE Journal on Selected Areas in Communications, 2006
- Cross-Layer Congestion Control, Routing and Scheduling Design in Ad Hoc Wireless NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Cross-layer rate control for end-to-end proportional fairness in wireless networks with random accessPublished by Association for Computing Machinery (ACM) ,2005
- The Mathematics of Internet Congestion ControlPublished by Springer Nature ,2004
- A duality model of TCP and queue management algorithmsIEEE/ACM Transactions on Networking, 2003
- Rate control for communication networks: shadow prices, proportional fairness and stabilityJournal of the Operational Research Society, 1998
- Minimization Methods for Non-Differentiable FunctionsPublished by Springer Nature ,1985