Minimum-Cost Multicast over Coded Packet Networks

MaRDI QIDQ3547302zbMATH OpenFDO

Authors Desmond S. Lun, Niranjan Ratnakar, Muriel Médard, R. Kötter, Tracey Ho, Ebad Ahmed, Fang Zhao, David R. Karger

Publication date 21 December 2008

Full work available at URL https://arxiv.org/abs/cs/0503064

zbMATH Keywords

distributed algorithmscommunication networkswireless networksnetwork codingnetwork optimizationmulticastAd hoc networksdynamic multicast groups

Mathematics Subject Classification ID

Communication theory (94A05) Circuits, networks (94C99) Communication networks in operations research (90B18)

Abstract: 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.

Recommendations

• Min-Cost Selfish Multicast With Network Coding
• Optimal-constrained multicast sub-graph over coded packet networks
• A Random Linear Network Coding Approach to Multicast
• Linear network coding
• Network information flow

Cited in

(8)

• scientific article; zbMATH DE number 5455150 (Why is no real title available?)
• Wiretapping Based on Node Corruption over Secure Network Coding: Analysis and Optimization
• Optimal-constrained multicast sub-graph over coded packet networks
• Robust optimization for minimizing energy consumption of multicast transmissions in coded wireless packet networks under distance uncertainty
• Minimum-energy wireless real-time multicast by joint network coding and scheduling optimization
• scientific article; zbMATH DE number 1532270 (Why is no real title available?)
• Min-Cost Selfish Multicast With Network Coding
• A robust optimization approach for multicast network coding under uncertain link costs

This page was built for publication: Minimum-Cost Multicast over Coded Packet Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3547302)