Achieving minimum-cost multicast: A decentralized approach based on network coding

Desmond S. Lun, Niranjan Ratnakar, Ralf Koetter, Muriel Médard, Ebad Ahmed, Hyunjoo Lee

Research output: Contribution to journalConference articlepeer-review

204 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1608-1617
Number of pages10
JournalProceedings - IEEE INFOCOM
StatePublished - 2005
Externally publishedYes
EventIEEE INFOCOM 2005 - Miami, FL, United States
Duration: Mar 13 2005Mar 17 2005

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Achieving minimum-cost multicast: A decentralized approach based on network coding'. Together they form a unique fingerprint.

Cite this