Minimum-cost multicast over coded packet networks

By Desmond S. Lun, Niranjan Ratnakar, Muriel Médard, Ralf Koetter, David R Karger, T. Ho, Ebad Ahmed, Fang Zhao. IEEE Transactions on Information Theory, 2005

447 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/c7ed2c8a511e59138419aba12d0b6271af2abcda

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures (2007, methodology): “On the topic of rate control for network coding based multicast, different decompositions have been obtained in [85], [152], [153], [6], [158], [15].”
A Random Linear Network Coding Approach to Multicast (2006, methodology): “[13], [21], has used random linear network coding as a component of the solution.”
Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications (2007, background): “…AND NEW ALGORITHM) been obtained in [20] –[24], on the topic of joint congestion control and random access, different decompositions have been obtained in [25], [26], and on the topic of rate control for network coding based multicast, different decompositions have been obtained in [27]–[32].”
Full length article: On coding for reliable communication over packet networks (2008, unknown): “treated in [ 21 ], [22], [23], [24], [25], [26], [27].”