Minimum cost mirror sites using network coding: Replication vs. coding at the source nodes
| Autor: | Aditya Ramamoorthy, Muriel Medard, Shurui Huang |
|---|---|
| Přispěvatelé: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Medard, Muriel |
| Rok vydání: | 2009 |
| Předmět: |
FOS: Computer and information sciences
Optimization problem Multicast Computer science business.industry Computer Science - Information Theory Information Theory (cs.IT) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Library and Information Sciences 01 natural sciences Upper and lower bounds Computer Science Applications 010201 computation theory & mathematics Linear network coding Distributed data store 0202 electrical engineering electronic engineering information engineering business Information Systems Computer network Coding (social sciences) |
| Zdroj: | arXiv |
| DOI: | 10.48550/arxiv.0910.2263 |
| Popis: | September 27, 2010 Content distribution over networks is often achieved by using mirror sites that hold copies of files or portions thereof to avoid congestion and delay issues arising from excessive demands to a single location. Accordingly, there are distributed storage solutions that divide the file into pieces and place copies of the pieces (replication) or coded versions of the pieces (coding) at multiple source nodes. We consider a network which uses network coding for multicasting the file. There is a set of source nodes that contains either subsets or coded versions of the pieces of the file. The cost of a given storage solution is defined as the sum of the storage cost and the cost of the flows required to support the multicast. Our interest is in finding the storage capacities and flows at minimum combined cost. We formulate the corresponding optimization problems by using the theory of information measures. In particular, we show that when there are two source nodes, there is no loss in considering subset sources. For three source nodes, we derive a tight upper bound on the cost gap between the coded and uncoded cases. We also present algorithms for determining the content of the source nodes. National Science Foundation (U.S.) (Grant CNS-0721453) National Science Foundation (U.S.) (Grant CCF-1018148) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|