Distributed utility maximization for network coding based multicasting

A shortest path approach

Yunnan Wu, Sun-Yuan Kung

Research output: Contribution to journalArticle

52 Citations (Scopus)

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

Fingerprint

Multicasting
Network coding
Cost functions
Throughput
Decomposition
Recovery
Economics
Costs

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Computer Networks and Communications

Cite this

@article{4554319c9e6e490ead1ab29a0405fadc,
title = "Distributed utility maximization for network coding based multicasting: A shortest path approach",
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.",
author = "Yunnan Wu and Sun-Yuan Kung",
year = "2006",
month = "8",
day = "1",
doi = "https://doi.org/10.1109/JSAC.2006.879356",
language = "English (US)",
volume = "24",
pages = "1475--1488",
journal = "IEEE Journal on Selected Areas in Communications",
issn = "0733-8716",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "8",

}

Distributed utility maximization for network coding based multicasting : A shortest path approach. / Wu, Yunnan; Kung, Sun-Yuan.

In: IEEE Journal on Selected Areas in Communications, Vol. 24, No. 8, 1665002, 01.08.2006, p. 1475-1488.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Distributed utility maximization for network coding based multicasting

T2 - A shortest path approach

AU - Wu, Yunnan

AU - Kung, Sun-Yuan

PY - 2006/8/1

Y1 - 2006/8/1

N2 - 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.

AB - 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.

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

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

U2 - https://doi.org/10.1109/JSAC.2006.879356

DO - https://doi.org/10.1109/JSAC.2006.879356

M3 - Article

VL - 24

SP - 1475

EP - 1488

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

SN - 0733-8716

IS - 8

M1 - 1665002

ER -