Achieving minimum-cost multicast: a decentralized approach based on network coding
Achieving minimum-cost multicast: a decentralized approach based on network coding
复制标题
DOI：
10.1109/infcom.2005.1498443
复制
发表时间：
2005-03
期刊：
影响因子：
--
通讯作者：
D. Lun;Niranjan Ratnakar;R. Koetter;M. Médard;E. Ahmed;Hyunjoo Lee
中科院分区：
文献类型：
--
作者：
D. Lun;Niranjan Ratnakar;R. Koetter;M. Médard;E. Ahmed;Hyunjoo Lee
我们提出了在使用编码的网络中计算最小代价子图以建立多播连接的分散算法。这些算法与现有的用于构造网络代码的分散方案相结合，构成了实现最小成本多播的完全分散的方法。我们的方法与主流的基于有向Steiner树问题的近似算法的方法形成了鲜明的对比，有向Steiner树问题的近似算法是次优的，并且通常假设集中计算具有完整的网络知识。我们还扩展了有向点对点链路网络中固定速率组播的基本问题，并考虑了弹性速率需求的情况以及无线网络中的最小能量组播问题。
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.