Networking from a network coding perspective

Network coding generalizes network operation beyond traditional routing, or store-and-forward, approaches, allowing for mathematical operations across data streams within a network. This thesis considers a number of theoretical and practical networking issues from network coding perspectives. We describe a new distributed randomized coding approach to multi-source multicast network scenarios, in which one or more, possibly correlated, sources transmit common information to one or more receivers. This approach substantially widens the scope of applicability of network coding to three new areas. Firstly, we show that it achieves robust network operation in a decentralized fashion, approaching optimal capacity with error probability decreasing exponentially in the length of the codes. Secondly, in the area of network security, we show how to extend this approach to obtain a low-overhead scheme for detecting the presence of faulty or malicious nodes exhibiting Byzantine (arbitrary) behavior. Thirdly, we show that this approach compresses information where necessary in a network, giving error bounds in terms of network parameters. Another area of our work develops an information theoretic framework for network management for recovery from non-ergodic link failures, based on the very general network coding concept of network behavior as a code. This provides a way to quantify essential management information as that needed to switch among di®erent codes (behaviors) for di®erent failure scenarios. We compare two di®erent recovery approaches, and give bounds, many of which are tight, on management requirements for various network connection problems in terms of network parameters.

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

2004

Author dc:creator

• Ho, Tracey, 1976-

Advisor dc:contributor.advisor

• Muriel Médard.

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

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/87910