Network coding

In the network coding problem, there are k commodities each with an associated message Mi, a set of sources that know Mi and a set of sinks that request Mi. Each edge in the graph may transmit any function of the messages. These functions define a network coding solution. We explore three topics related to network coding. First, for a model in which the messages and the symbols transmitted on edges are all from the same alphabet [sigma], we prove lower bounds on [the absolute value of sigma]. In one case, we prove [the absolute value of sigma] needs to be doubly-exponential in the size of the network. We also show that it is NP-hard to determine the smallest alphabet size admitting a solution. We then explore the types of functions that admit solutions. In a linear solution over a finite field F the symbol transmitted over each edge is a linear combination of the messages. We show that determining if there exists a linear solution is NP-hard for many classes of network coding problems. As a corollary, we obtain a solvable instance of the network coding problem that does not admit a linear solution over any field F. We then define a model of network coding in which messages are chosen from one alphabet, [gamma], and edges transmit symbols from another alphabet, [sigma]. In this model, we define the rate of a solution as log [gamma absolute value]/ log [sigma absolute value]. We then explore techniques to upper bound the maximum achievable rate for instances defined on directed and undirected graphs. We present a network coding instance in an undirected graph in which the maximum achievable rate is strictly smaller than the sparsity of the graph.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2005

Author dc:creator

• Lehman, April Rasala, 1977-

Advisor dc:contributor.advisor

• Madhu Sudan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/30162

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/30162