{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/46325"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/46325","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Network coding for speedup in switches","abstract":"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).","abstract_html":"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).","abstract_has_math":false,"creators":["Kim, MinJi, M. Eng. Massachusetts Institute of Technology"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Muriel Médard."],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007","date_published":"2007","updated_at":"2026-07-22T22:20:56Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/46325","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Muriel Médard."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Kim, MinJi, M. Eng. Massachusetts Institute of Technology"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-07-06T20:24:55Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-07-06T20:24:55Z"]},{"key":"dc:date.issued","label":"Date","values":["2007"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/46325"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2007.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Includes bibliographical references (p. 69-71)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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)."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Network coding for speedup in switches"]}]}],"canonical_facts":{"dc:contributor.advisor":["Muriel Médard."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Kim, MinJi, M. Eng. Massachusetts Institute of Technology"],"dc:date.accessioned":["2009-07-06T20:24:55Z"],"dc:date.available":["2009-07-06T20:24:55Z"],"dc:date.issued":["2007"],"dc:description":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2007.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Includes bibliographical references (p. 69-71)."],"dc:description.abstract":["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)."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/46325"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Network coding for speedup in switches"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:56Z"}