Evolutionary approaches toward practical network coding

There have been numerous studies showing various benefits of network coding. However, in order to have network coding widely deployed in real networks, it is also important to show that the amount of overhead incurred by network coding can be kept minimal and eventually be outweighed by the benefits network coding provides. Owing to the mathematical operations required, network coding necessarily incurs some additional cost such as computational overhead or transmission delay, and as a practical matter, the cost of special hardware and/or software for network coding. While most network coding solutions assume that the coding operations are performed at all nodes, it is often possible to achieve the network coding advantage for multicast by coding only at a subset of nodes. However, determining a minimal set of the nodes where coding is required is NP-hard, as is its close approximation; hence there are only a few existing approaches each with certain limitations. In this thesis, we develop an evolutionary approach toward a practical multicast protocol that achieves the full benefit of network coding in terms of throughput, while performing coding operations only when required at as few nodes as possible. We show that our approach operates in a very efficient and practical manner such that it is distributed over the network both spatially and temporally, yielding a sufficiently good solution, which is at least as good as those obtained by existing centralized approaches but often turns out to be much superior in practice. We broaden the application areas of our evolutionary approach by generalizing it in several ways. First, we show that a generalized version of our approach can effectively reveal the possible tradeoff between the costs of network coding and link usage, enabling more informed decisions on where to deploy network coding. Also, we demonstrate that our approach can be applied to investigate many important but, because of the lack of appropriate tools, largely unanswered questions arising in practical scenarios based on heterogeneous wireless ad hoc networks and fault-tolerant optical networks.

Department dc:contributor.department

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

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Kim, Minkyu, 1976-

Advisor dc:contributor.advisor

• Muriel Médard and Una-May O'Reilly.

• 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/45876

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/45876