Achieving minimum-cost multicast: a decentralized approach based on network coding
Top Cited Papers
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3 (0743166X) , 1608-1617
- https://doi.org/10.1109/infcom.2005.1498443
Abstract
We present decentralized algorithms that compute minimum-cost subgraphs for establishing multicast connections in networks that use coding. These algorithms, coupled with existing decentralized schemes for constructing network codes, constitute a fully decentralized approach for achieving minimum-cost multicast. Our approach is in sharp contrast to the prevailing approach based on approximation algorithms for the directed Steiner tree problem, which is suboptimal and generally assumes centralized computation with full network knowledge. We also give extensions beyond the basic problem of fixed-rate multicast in networks with directed point-to-point links, and consider the case of elastic rate demand as well as the problem of minimum-energy multicast in wireless networks.Keywords
This publication has 16 references indexed in Scilit:
- On coding for reliable communication over packet networksPhysical Communication, 2008
- On the utility of network coding in dynamic environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Minimum-energy multicast in mobile ad hoc networks using network codingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- The Mathematics of Internet Congestion ControlPublished by Springer Nature ,2004
- Constructing minimum-energy broadcast trees in wireless ad hoc networksPublished by Association for Computing Machinery (ACM) ,2002
- Energy-Efficient Broadcast and Multicast Trees in Wireless NetworksMobile Networks and Applications, 2002
- Inferring link weights using end-to-end measurementsPublished by Association for Computing Machinery (ACM) ,2002
- A Partitioned ∈-Relaxation Algorithm for Separable Convex Network Flow ProblemsComputational Optimization and Applications, 1999
- An $\epsilon$-Relaxation Method for Separable Convex Cost Network Flow ProblemsSIAM Journal on Optimization, 1997
- Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programsOperations Research Letters, 1996