Throughput analysis of input-queued packet switches : multicasting and speedup

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.

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

1998

Author dc:creator

• Maruta, Toru, 1967-

Advisor dc:contributor.advisor

• Balaji Prabhakar.

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

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/9627