Network coding for speedup in switches

Network coding, which allows mixing of data at intermediate network nodes, is known to increase the throughput of networks. In particular, it is known that linear network coding in a crossbar switch can sustain traffic patterns that cannot be served if network coding were not allowed. Thus, network coding leads to a larger rate region in a multicast crossbar switch. This thesis quantities the gain in rate region in a multicast crossbar switch in terms of speedup. We present a graph theoretic upper bound on speedup needed to achieve 100% throughput in a multicast switch using network coding. By bounding speedup, we show the equivalence between network coding and speedup in multicast switches - i.e. network coding, which is usually implemented using software, can in many cases substitute speedup, which is often achieved by adding extra switch fabrics. This bound is based on an approach to network coding problems called the "enhanced conflict graph". We show that the "imperfection ratio" of the enhanced conflict graph gives an upper bound on speedup. In particular, we apply this result to K x N switches with traffic patterns consisting of unicasts and broadcasts only to obtain an upper bound of min(2K-1/K, 2N/N+1).

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

2007

Author dc:creator

• Kim, MinJi, M. Eng. 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/46325

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/46325