TY - GEN

T1 - Alternative decompositions and distributed algorithms for network utility maximization

AU - Palomar, Daniel P.

AU - Chiang, Mung

PY - 2005/12/1

Y1 - 2005/12/1

N2 - Network utility maximization problems provide an important approach to conduct network resource management such as power and rate allocation. In the existing literature, distributed implementations are typically achieved by the means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements which 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 in a systematic way how to apply these decomposition techniques to network utility maximization problems. The presentation is based on a general network optimization model that unifies existing works, and then is particularized to two concrete examples of recent interest: generalized water-filling algorithms and wireless cellular downlink power control. We can thus obtain a variety of distributed algorithms with different characteristics to suit the needs of specific applications. Both primal and dual decomposition techniques are considered at many different hierarchy levels, leading to a range of choices of hybrid, multi-level, primal/dual decomposition schemes. Each particular combination provides a different distributed algorithm for resource allocation. The choice of decomposition method and distributed algorithm for a particular problem depends on factors such as the amount of signalling required for proper coordination, asymmetry of computational load, and speed of convergence.

AB - Network utility maximization problems provide an important approach to conduct network resource management such as power and rate allocation. In the existing literature, distributed implementations are typically achieved by the means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements which 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 in a systematic way how to apply these decomposition techniques to network utility maximization problems. The presentation is based on a general network optimization model that unifies existing works, and then is particularized to two concrete examples of recent interest: generalized water-filling algorithms and wireless cellular downlink power control. We can thus obtain a variety of distributed algorithms with different characteristics to suit the needs of specific applications. Both primal and dual decomposition techniques are considered at many different hierarchy levels, leading to a range of choices of hybrid, multi-level, primal/dual decomposition schemes. Each particular combination provides a different distributed algorithm for resource allocation. The choice of decomposition method and distributed algorithm for a particular problem depends on factors such as the amount of signalling required for proper coordination, asymmetry of computational load, and speed of convergence.

UR - http://www.scopus.com/inward/record.url?scp=33747236200&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33747236200&partnerID=8YFLogxK

U2 - 10.1109/GLOCOM.2005.1578224

DO - 10.1109/GLOCOM.2005.1578224

M3 - Conference contribution

AN - SCOPUS:33747236200

SN - 0780394143

SN - 9780780394148

T3 - GLOBECOM - IEEE Global Telecommunications Conference

SP - 2563

EP - 2568

BT - GLOBECOM'05

T2 - GLOBECOM'05: IEEE Global Telecommunications Conference, 2005

Y2 - 28 November 2005 through 2 December 2005

ER -