Alternative decompositions and distributed algorithms for network utility maximization

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.