Minimum-Cost Multicast over Coded Packet Networks

zbMATH Open1317.94010arXivcs/0503064MaRDI QIDQ3547302FDOQ3547302

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

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.

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

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

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)

Cited In (8)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)