Distributed control of coded networks

The introduction of network coding has the potential to revolutionize the way people operate networks. For the benefits of network coding to be realized, distributed solutions are needed for various network problems. In this work, we look at three aspects of distributed control of coded networks. The first one is distributed algorithms for establishing minimum-cost multicast connections in coded networks. The subgraph optimization problem can be viewed as an linear optimization problem, and we look at algorithms that solve this problem for both static and dynamic multicasts. For static multicast, we present decentralized dual subgradient algorithms to find the min-cost subgraph. Due to the special structure of the network coding problem, we can recover a feasible primal solution after each iteration, and also derive theoretical bounds on the convergence rate in both the dual and the primal spaces. In addition, we propose heuristics to further improve our algorithm, and demonstrate through simulations that the distributed algorithm converges to the optimal subgraph quickly and is robust against network topology changes. For dynamic multicast, we introduce two types of rearrangements, link rearrangement and code rearrangement, to characterize disturbances to users. We present algorithms to solve the online network coding problem, and demonstrate through simulations that the algorithms can adapt to changing demands of the multicast group while minimizing disturbances to existing users.

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

2010

Author dc:creator

• Zhao, Fang, Ph. D. Massachusetts Institute of Technology

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/57776

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/57776