TY - JOUR
T1 - Alternative distributed algorithms for network utility maximization
T2 - Framework and applications
AU - Palomar, Daniel P.
AU - Chiang, Mung
N1 - Funding Information:
Manuscript received December 21, 2005; revised July 13, 2006. Recommended by Associate Editor I. Paschalidis. This work was supported in part by the Fulbright Program and the Ministry of Education and Science of Spain; in part by the United States National Science Foundation Grants CCF-0448012, CNS-0417607, and CNS-0427677; and in part by the National Science Foundation of China under Grant 60702081. Part of this paper was presented at IEEE INFOCOM, Barcelona, Spain, April 2006.
PY - 2007/12
Y1 - 2007/12
N2 - Network utility maximization (NUM) problem formulations provide an important approach to conduct network resource allocation and to view layering as optimization decomposition. In the existing literature, distributed implementations are typically achieved by means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements that, thus far, have not been fully exploited, such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents a systematic framework to exploit alternative decomposition structures as a way to obtain different distributed algorithms, each with a different tradeoff among convergence speed, message passing amount and asymmetry, and distributed computation architecture. Several specific applications are considered to illustrate the proposed framework, including resource-constrained and direct-control rate allocation, and rate allocation among QoS classes with multipath routing. For each of these applications, the associated generalized NUM formulation is first presented, followed by the development of novel alternative decompositions and numerical experiments on the resulting new distributed algorithms. A systematic enumeration and comparison of alternative vertical decompositions in the future will help complete a mathematical theory of network architectures.
AB - Network utility maximization (NUM) problem formulations provide an important approach to conduct network resource allocation and to view layering as optimization decomposition. In the existing literature, distributed implementations are typically achieved by means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements that, thus far, have not been fully exploited, such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents a systematic framework to exploit alternative decomposition structures as a way to obtain different distributed algorithms, each with a different tradeoff among convergence speed, message passing amount and asymmetry, and distributed computation architecture. Several specific applications are considered to illustrate the proposed framework, including resource-constrained and direct-control rate allocation, and rate allocation among QoS classes with multipath routing. For each of these applications, the associated generalized NUM formulation is first presented, followed by the development of novel alternative decompositions and numerical experiments on the resulting new distributed algorithms. A systematic enumeration and comparison of alternative vertical decompositions in the future will help complete a mathematical theory of network architectures.
KW - Congestion control
KW - Distributed algorithm
KW - Mathematical programming/optimization
KW - Network control by pricing
KW - Network utility maximization (NUM)
KW - Rate control
KW - Resource allocation
UR - http://www.scopus.com/inward/record.url?scp=38149002839&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149002839&partnerID=8YFLogxK
U2 - 10.1109/TAC.2007.910665
DO - 10.1109/TAC.2007.910665
M3 - Article
AN - SCOPUS:38149002839
SN - 0018-9286
VL - 52
SP - 2254
EP - 2269
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 12
ER -