Minimum-Cost Multicast over Coded Packet Networks

Simple item page
dc.creatorLun, Desmond S.
dc.creatorRatnakar, Niranjan
dc.creatorMedard, Muriel
dc.creatorKoetter, Ralf
dc.creatorKarger, David R.
dc.creatorHo, Tracey
dc.creatorAhmed, Ebad
dc.creatorZhao, Fang
dc.date2005-03-24
dc.date2006-01-31
dc.date.accessioned2026-07-07T08:17:46Z
dc.date.available2026-07-07T08:17:46Z
dc.descriptionWe 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.
dc.description17 pages, 6 figures; to appear in IEEE Transactions on Information Theory (special issue on Networking and Information Theory); revised version, with major changes
dc.identifierhttps://arxiv.org/abs/cs/0503064
dc.identifierhttp://arxiv.org/abs/cs/0503064
dc.identifierIEEE Trans. Inform. Theory, vol. 52, no. 6, pp. 2608-2623, June 2006
dc.identifierdoi:10.1109/TIT.2006.874523
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/134205
dc.subjectInformation Theory
dc.subjectNetworking and Internet Architecture
dc.titleMinimum-Cost Multicast over Coded Packet Networks
dc.typetext

Files

Collections

arXiv