Efficient universal recovery in broadcast networks
Authors:
- 1 September 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1542-1549
Abstract
Consider a connected broadcast network of N nodes that all wish to recover k desired packets. Each node begins with a subset of the desired packets and broadcasts messages to its neighbors. In a previous paper we established necessary and sufficient conditions on the number of transmissions from each node required for universal recovery (in which each node recovers all k packets). However, these conditions are numerous and cumbersome. The present paper gives a series of relatively simple conditions for universal recovery that apply when the number of packets is large and the distribution of packets among the nodes is well behaved. Our first result, which applies to any fixed network topology, uses only simple cuts in the network to characterize a set of transmission strategies such that for any ε >; 0 these strategies require at most kε transmissions above the minimum required for universal recovery. For certain topologies including nonsingular d-regular d-connected networks, we explicitly construct transmission strategies that achieve universal recovery while using at most N transmissions above the minimum even when the total number of required transmissions is very large. These explicit constructions essentially resolve the problem completely for many canonical networks (e.g. cliques, rings, grids on tori, etc.).Keywords
This publication has 16 references indexed in Scilit:
- On coding for cooperative data exchange2010
- On source transmission over deterministic relay networks2010
- On the Rank of Random Sparse MatricesCombinatorics, Probability and Computing, 2009
- The rank of random graphsRandom Structures & Algorithms, 2008
- Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clientsIEEE Transactions on Information Theory, 2006
- A Network Coding Approach to Energy Efficient Broadcasting: From Theory to Practice2006
- Polynomial Time Algorithms for Multicast Network Code ConstructionIEEE Transactions on Information Theory, 2005
- Linear network codingIEEE Transactions on Information Theory, 2003
- Random Graphs2001
- Network information flowIEEE Transactions on Information Theory, 2000