Exact emulation of an output queueing switch by a combined input output queueing switch

Combined input-output queueing switches (CIOQ) have better scaling properties than output queueing (OQ) switches. However, a CIOQ switch may have lower switch throughput and, more importantly, it is difficult to control delay in a CIOQ switch due to the existence of multiple queueing points. In this paper, we study the following problem: can a CIOQ switch be designed to behave identically to an OQ switch? B. Prabhakar and N. McKeown (1997) proposed an algorithm such that a CIOQ switch with an internal speedup of 4 can behave identically to an OQ switch with FIFO as the output queueing discipline. In this paper, we propose a new switch scheduling algorithm called joined preferred matching (JPM) that improves Prahhakar and McKeown's results in two aspects. First, with JPM, the internal speedup needed for a CIOQ switch to achieve exact emulation of an OQ switch is only 2 instead of 4. Second, the result applies to OQ switches that employ a general class of output service disciplines, including FIFO and various fair queueing algorithms. This result lays the theoretical foundation for designing scalable high-speed CIOQ switches that can provide same throughput and QoS as OQ switches, but require lower-speed internal memory.