Distributed utility maximization for network coding based multicasting: A shortest path approach

Yunnan Wu, Sun Yuan Kung

Research output: Contribution to journalArticle

52 Scopus citations

Abstract

One central issue in practically deploying network coding is the adaptive and economic allocation of network resource. We cast this as an optimization, where the net-utility-the difference between a utility derived from the attainable multicast throughput and the total cost of resource provisioning-is maximized. By employing the MAX of flows characterization of the admissible rate region for multicasting, this paper gives a novel reformulation of the optimization problem, which has a separable structure. The Lagrangian relaxation method is applied to decompose the problem into subproblems involving one destination each. Our specific formulation of the primal problem results in two key properties. First, the resulting subproblem after decomposition amounts to the problem of finding a shortest path from the source to each destination. Second, assuming the net-utility function is strictly concave, our proposed method enables a near-optimal primal variable to be uniquely recovered from a near-optimal dual variable. A numerical robustness analysis of the primal recovery method is also conducted. For ill-conditioned problems that arise, for instance, when the cost functions are linear, we propose to use the proximal method, which solves a sequence of well-conditioned problems obtained from the original problem by adding quadratic regularization terms. Furthermore, the simulation results confirm the numerical robustness of the proposed algorithms. Finally, the proximal method and the dual subgradient method can be naturally extended to provide an effective solution for applications with multiple multicast sessions.

Original languageEnglish (US)
Article number1665002
Pages (from-to)1475-1488
Number of pages14
JournalIEEE Journal on Selected Areas in Communications
Volume24
Issue number8
DOIs
StatePublished - Aug 1 2006

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Keywords

  • Distributed optimization
  • Dual
  • Multicast
  • Network coding
  • Shortest path
  • Subgradient

Fingerprint Dive into the research topics of 'Distributed utility maximization for network coding based multicasting: A shortest path approach'. Together they form a unique fingerprint.

  • Cite this