| The rapid growth in packet-based network traffic has resulted in a growing demand for network switches that can scale in capacity with increasing interface transmission rates and higher port counts. Furthermore, the continuing migration of legacy circuit-switched services to a shared IP/MPLS packet-based network requires such network switches to provide an adequate Quality of Service (QoS) in terms of traffic prioritization, as well as bandwidth and delay guarantees. While technology advances, such as the usage of faster silicon and optical switching components, provide one dimension to address this demand, architectural improvements provide the other. This dissertation addresses the latter topic. Specifically, we address the subject of constructing and analyzing high-capacity QoS-capable packet switches using multiple lower-capacity modules.;Switches with the output-queueing (OQ) discipline, in theory, provide the best performance in terms of throughput as well as QoS, but do not scale in capacity with increasing rates and port counts. Input-queued (IQ) switches, on the other hand, scale better but require complex arbitration procedures, sometimes impractical, to achieve the same level of performance. We leverage the state-of-the-art in OQ and IQ switching systems and establish a new taxonomy for a class of three-stage packet switches, which we call Buffered Clos Switches. The taxonomy is created by augmenting existing switching elements with aggregation, pipelining and parallelization techniques. This offers a switch designer several alternatives, each driven by specific design and re-use constraints, to build a high-capacity switch composed of lower-capacity basic elements.;We also present a formal framework for optimal packet-switching performance, in order to uniformly characterize the capabilities of the switches in the class. The optimality is based on establishing functional equivalence of a given switch and its associated arbitration algorithms with a well-understood ideal switch. For the items in the above taxonomy, we demonstrate how some existing algorithms perform with respect to the optimality criteria, and then augment the state-of-the-art by presenting algorithms and analytical results for stricter equivalence with an ideal switch. |
