Distributed Utility Maximization for Network Coding Based Multicasting: A Critical Cut Approach

Yunnan Wu; Mung  Chiang; Sun-Yuan  Kung

2nd International ICST Workshop on Network Coding, Theory, and Applications

Research Article

Distributed Utility Maximization for Network Coding Based Multicasting: A Critical Cut Approach

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2006.1666491,
    author={Yunnan Wu and Mung  Chiang and Sun-Yuan  Kung},
    title={Distributed Utility Maximization for Network Coding Based Multicasting: A Critical Cut Approach},
    proceedings={2nd International ICST Workshop on Network Coding, Theory, and Applications},
    publisher={IEEE},
    proceedings_a={NETCOD},
    year={2006},
    month={8},
    keywords={},
    doi={10.1109/WIOPT.2006.1666491}
}

Yunnan Wu
Mung Chiang
Sun-Yuan Kung
Year: 2006
Distributed Utility Maximization for Network Coding Based Multicasting: A Critical Cut Approach
NETCOD
IEEE
DOI: 10.1109/WIOPT.2006.1666491

Yunnan Wu¹^,*, Mung Chiang²^,*, Sun-Yuan Kung³^,*

1: Microsoft Research, One Microsoft Way, Redmond, WA, 98052.
2: Dept. of Electrical Engineering, Princeton University, Princeton, NJ, 08544
3: Dept. of Electrical Engineering, Princeton University, Princeton, NJ, 08544.

*Contact email: yunnanwu@microsoft.com, chiangm@princeton.edu, kung@princeton.edu

Abstract

A central issue in practically deploying network coding in a shared network is the adaptive and efficient allocation of network resources. This issue can be formulated as an optimization problem of maximizing the net-utility — the difference between a utility derived from the attainable multicast throughput and the total cost of resource provisioning. We develop a primal-subgradient type distributed algorithm to solve this utility maximization problem. The effectiveness of the algorithm hinges upon two key properties we discovered: (1) the set of subgradients of the multicast capacity is the convex hull of the indicator vectors for the critical cuts, and (2) the complexity of finding such critical cuts can be reduced by exploiting the algebraic properties of linear network coding. The extension to multiple multicast sessions is also carried out. The effectiveness of the proposed algorithm is confirmed by simulations on an Internet Service Provider’s topology.

Published: 2006-08-07
Publisher: IEEE

: http://dx.doi.org/10.1109/WIOPT.2006.1666491