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

Yunnan Wu, Sun Yuan Kung

Research output: Contribution to journalArticlepeer-review

53 Scopus citations


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
Issue number8
StatePublished - Aug 2006

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


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


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