Matching output queueing with a multiple input/output-queued switch

We show that the multiple input/output-queued (MlOQ) switch proposed in our previous paper H. I. Lee and S. W. Seo (May 2003) can emulate an output-queued switch only with two parallel switches. The MIOQ switch requires no speedup and provides an exact emulation of an output-queued switch with a broad class of service scheduling algorithms including FIFO, weighted fair queueing (WFQ) and strict priority queueing regardless of incoming traffic pattern and switch size. First, we show that an N × N MIOQ switch with a (2, 2)-dimensional crossbar fabric can exactly emulate an N × N output-queued switch. For this purpose, we propose the stable strategic alliance (SSA) algorithm that can produce a stable many-to-many assignment, and then apply it to the scheduling of an MIOQ switch. Next, we prove that a (2, 2)-dimensional crossbar fabric can be implemented by two N × N crossbar switches in parallel for an N × N MIOQ switch. For a proper operation of two crossbar switches in parallel, each input-output pair matched by the SSA algorithm must be mapped to one of two crossbar switches. For this mapping, we propose a simple algorithm that requires at most 2N steps for all matched input-output pairs. In addition, to relieve the implementation burden of N input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of N physically-separate memories.