{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/9627"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/9627","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Throughput analysis of input-queued packet switches : multicasting and speedup","abstract":"The widespread use of new applications such as voice/video streaming, the WWW, and the MBone has caused an increased demand for bandwidth in the Internet. In response to this, Internet backbone speeds have increased to several gigabits/sec, thus causing packet switches and routers to become potential bottlenecks of the network. There is also an increasing need to support services with different QoS requirements over a single integrated network. The support of such capabilities will require an even higher performance of packet switches and routers. Among several competing high-speed router architectures, those based on a cross­bar backplane have become the most widely used by the industry. Essentially, crossbar architectures come in two flavors: (1) The Output-queued Architecture, and (2) The Input-queued Architecture. Despite superior throughput and delay performance, the output-queued architecture is severely impacted by memory bandwidth constraints at high speeds. On the other hand, input-queued switches/routers do not suffer from this, but deliver a poor throughput and delay performance due to the so-called Head of Line (HOL) blocking problem. Therefore, a number of recent studies have focused on overcoming the limitations of input-queued switches through the use of \"speedup\" and clever packet scheduling algorithms. Research on designing efficient switches for multicast traffic is also of great interest currently, since multicast traffic is a growing proportion of Internet traffic. In this thesis, we revisit the analysis of input-queued switches. Our contribution consists of the use of a conceptual combinatorial model of \"balls and urns\" to for­mulate and analyze the behavior of input-queued switches both with and without speedup. We also analyze the throughput performance of multicast switches when the fanout is deterministic, and obtain precise analytical results which exactly match simulations. Finally we analyze the throughput of multicast switches when the fanout is random and find, somewhat surprisingly, that the throughput is lowest when the fanout is deterministic.","abstract_html":"The widespread use of new applications such as voice/video streaming, the WWW, and the MBone has caused an increased demand for bandwidth in the Internet. In response to this, Internet backbone speeds have increased to several gigabits/sec, thus causing packet switches and routers to become potential bottlenecks of the network. There is also an increasing need to support services with different QoS requirements over a single integrated network. The support of such capabilities will require an even higher performance of packet switches and routers. Among several competing high-speed router architectures, those based on a cross­bar backplane have become the most widely used by the industry. Essentially, crossbar architectures come in two flavors: (1) The Output-queued Architecture, and (2) The Input-queued Architecture. Despite superior throughput and delay performance, the output-queued architecture is severely impacted by memory bandwidth constraints at high speeds. On the other hand, input-queued switches/routers do not suffer from this, but deliver a poor throughput and delay performance due to the so-called Head of Line (HOL) blocking problem. Therefore, a number of recent studies have focused on overcoming the limitations of input-queued switches through the use of "speedup" and clever packet scheduling algorithms. Research on designing efficient switches for multicast traffic is also of great interest currently, since multicast traffic is a growing proportion of Internet traffic. In this thesis, we revisit the analysis of input-queued switches. Our contribution consists of the use of a conceptual combinatorial model of "balls and urns" to for­mulate and analyze the behavior of input-queued switches both with and without speedup. We also analyze the throughput performance of multicast switches when the fanout is deterministic, and obtain precise analytical results which exactly match simulations. Finally we analyze the throughput of multicast switches when the fanout is random and find, somewhat surprisingly, that the throughput is lowest when the fanout is deterministic.","abstract_has_math":false,"creators":["Maruta, Toru, 1967-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Balaji Prabhakar."],"committee_chairs":[],"committee_members":[],"year":1998,"date_issued":"1998","date_published":"1998","updated_at":"2026-07-22T22:21:24Z","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/9627","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Balaji Prabhakar."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Maruta, Toru, 1967-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2005-08-19T19:02:28Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2005-08-19T19:02:28Z"]},{"key":"dc:date.issued","label":"Date","values":["1998"]},{"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/9627"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.","Includes bibliographical references (p. 75-76)."]},{"key":"dc:description.abstract","label":"Abstract","values":["The widespread use of new applications such as voice/video streaming, the WWW, and the MBone has caused an increased demand for bandwidth in the Internet. In response to this, Internet backbone speeds have increased to several gigabits/sec, thus causing packet switches and routers to become potential bottlenecks of the network. There is also an increasing need to support services with different QoS requirements over a single integrated network. The support of such capabilities will require an even higher performance of packet switches and routers. Among several competing high-speed router architectures, those based on a cross­bar backplane have become the most widely used by the industry. Essentially, crossbar architectures come in two flavors: (1) The Output-queued Architecture, and (2) The Input-queued Architecture. Despite superior throughput and delay performance, the output-queued architecture is severely impacted by memory bandwidth constraints at high speeds. On the other hand, input-queued switches/routers do not suffer from this, but deliver a poor throughput and delay performance due to the so-called Head of Line (HOL) blocking problem. Therefore, a number of recent studies have focused on overcoming the limitations of input-queued switches through the use of \"speedup\" and clever packet scheduling algorithms. Research on designing efficient switches for multicast traffic is also of great interest currently, since multicast traffic is a growing proportion of Internet traffic. In this thesis, we revisit the analysis of input-queued switches. Our contribution consists of the use of a conceptual combinatorial model of \"balls and urns\" to for­mulate and analyze the behavior of input-queued switches both with and without speedup. We also analyze the throughput performance of multicast switches when the fanout is deterministic, and obtain precise analytical results which exactly match simulations. Finally we analyze the throughput of multicast switches when the fanout is random and find, somewhat surprisingly, that the throughput is lowest when the fanout is deterministic."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Throughput analysis of input-queued packet switches : multicasting and speedup"]}]}],"canonical_facts":{"dc:contributor.advisor":["Balaji Prabhakar."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Maruta, Toru, 1967-"],"dc:date.accessioned":["2005-08-19T19:02:28Z"],"dc:date.available":["2005-08-19T19:02:28Z"],"dc:date.issued":["1998"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.","Includes bibliographical references (p. 75-76)."],"dc:description.abstract":["The widespread use of new applications such as voice/video streaming, the WWW, and the MBone has caused an increased demand for bandwidth in the Internet. In response to this, Internet backbone speeds have increased to several gigabits/sec, thus causing packet switches and routers to become potential bottlenecks of the network. There is also an increasing need to support services with different QoS requirements over a single integrated network. The support of such capabilities will require an even higher performance of packet switches and routers. Among several competing high-speed router architectures, those based on a cross­bar backplane have become the most widely used by the industry. Essentially, crossbar architectures come in two flavors: (1) The Output-queued Architecture, and (2) The Input-queued Architecture. Despite superior throughput and delay performance, the output-queued architecture is severely impacted by memory bandwidth constraints at high speeds. On the other hand, input-queued switches/routers do not suffer from this, but deliver a poor throughput and delay performance due to the so-called Head of Line (HOL) blocking problem. Therefore, a number of recent studies have focused on overcoming the limitations of input-queued switches through the use of \"speedup\" and clever packet scheduling algorithms. Research on designing efficient switches for multicast traffic is also of great interest currently, since multicast traffic is a growing proportion of Internet traffic. In this thesis, we revisit the analysis of input-queued switches. Our contribution consists of the use of a conceptual combinatorial model of \"balls and urns\" to for­mulate and analyze the behavior of input-queued switches both with and without speedup. We also analyze the throughput performance of multicast switches when the fanout is deterministic, and obtain precise analytical results which exactly match simulations. Finally we analyze the throughput of multicast switches when the fanout is random and find, somewhat surprisingly, that the throughput is lowest when the fanout is deterministic."],"dc:description.degree":["S.M."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/9627"],"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":["Throughput analysis of input-queued packet switches : multicasting and speedup"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:24Z"}