A Caltech Library Service

Minimum-cost multicast over coded packet networks

Lun, Desmond S. and Ratnakar, Niranjan and Médard, Muriel and Koetter, Ralf and Karger, David R. and Ho, Tracey and Ahmed, Ebad and Zhao, Fang (2006) Minimum-cost multicast over coded packet networks. IEEE Transactions on Information Theory, 52 (6). pp. 2608-2623. ISSN 0018-9448. doi:10.1109/TIT.2006.874523.

See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received March 31, 2005; revised February 13, 2006. [Posted online: 2006-06-05] This work was supported by the National Science Foundation under Grants CCR-0093349, CCR-0325496, and CCR-0325673; by the Army Research Office through University of California subaward S0176938; by the Office of Naval Research under Grant N00014-05-1-0197; and by the Vodafone Foundation. The material in this paper was presented in part at the International Symposium on Information Theory and Its Applications, Parma, Italy, October 2004; in part at IEEE INFOCOM, Miami, FL, March 2005; in part at the First Workshop on Network Coding, Theory, and Applications, Riva del Garda, Italy, April 2005; and in part at the International Zurich Seminar on Communications, Zurich, Switzerland, February 2006. The authors would like to thank R. Srikant for helpful discussions and suggestions and Hyunjoo Lee for her work on the simulation software.
Subject Keywords:Ad hoc networks, communication networks, distributed algorithms, dynamic multicast groups, multicast, network coding, network optimization, wireless networks
Issue or Number:6
Record Number:CaltechAUTHORS:LUNieeetit06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6107
Deposited By: Archive Administrator
Deposited On:17 Nov 2006
Last Modified:08 Nov 2021 20:31

Repository Staff Only: item control page