Alternative distributed algorithms for network utility maximization: Framework and applications

Daniel P. Palomar, Mung Chiang

Research output: Contribution to journalArticle

190 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)2254-2269
Number of pages16
JournalIEEE Transactions on Automatic Control
Volume52
Issue number12
DOIs
StatePublished - Dec 1 2007

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Congestion control
  • Distributed algorithm
  • Mathematical programming/optimization
  • Network control by pricing
  • Network utility maximization (NUM)
  • Rate control
  • Resource allocation

Fingerprint Dive into the research topics of 'Alternative distributed algorithms for network utility maximization: Framework and applications'. Together they form a unique fingerprint.

  • Cite this