Emulating an output queued packet switch with systems containing input and output queueing.

摘要

Modern Data Communication networks require packet switches capable of providing quality of service (QoS) guarantees to arriving packets. Economic realities argue for scalable packet switch architectures with practical manufacturing costs. The designer of a packet switch must therefore choose an architecture meeting specific cost and performance goals. To this end it is necessary to understand the performance capabilities of different architectures and to compare their complexity for critical components such as memory and scheduling.; Packet switch architectures containing input and output queueing are considered practical for their low speed memory requirements. This thesis evaluates the performance limits of two types of combined input/output-queued (CIOQ) switches: those containing crossbar switch fabrics and those containing a limited memory switch fabric. In particular, we are interested in necessary and sufficient conditions that enable these architectures to satisfy two important performance goals: that is, to achieve 100% throughput (full utilization of the output lines) and to exactly emulate the “ideal” output-queued (OQ) switch architecture.; We attain our results by developing new performance evaluation methods and by presenting new scheduling algorithms for both types of CIOQ switches. We present a new network structure, termed the Constrained Clos network, that is functionally equivalent to a crossbar-based CIOQ packet switch. Using insights gained from the Constrained Clos network, we establish necessary and sufficient conditions for an N × N crossbar CIOQ switch, operated by specific scheduling algorithms, to achieve both 100% throughput and to emulate an OQ switch. Moreover, we establish that a 2 × 2 crossbar CIOQ switch requires less speedup for both 100% throughput and for OQ switch emulation. Additionally, we develop new distributed scheduling algorithms that allow a limited memory CIOQ switch to exactly emulate an OQ switch. We then compare the complexity of the OQ switch, the crossbar-based CIOQ switch and the limited memory CIOQ switch when these systems perform equivalently. The limited memory CIOQ switch architecture is argued to be the most practical given current technology.