Emulation of an output queued switch with a combined input output queued switch

The combined input output queued (CIOQ) architecture such as crossbar fabrics with speedup has recently been proposed to build a large-capacity switch for future broadband integrated services networks. Unlike an output queued (OQ) switch where queueing happens only at output ports, it is much more difficult for a CIOQ switch to provide quality of service (QoS) guarantee. Obviously, to achieve good performance in a CIOQ switch, the usage of switching fabrics has to be wisely scheduled. A scheduling algorithm named the least output occupancy first algorithm has been proposed to achieve 100% throughput in a CIOQ switch with a speedup factor of 2. However, achieving 100% throughput is not sufficient for per-connection QoS guarantees. Another proposed algorithm makes a CIOQ switch with a speedup factor of 4 to exactly emulate an output queued (OQ) switch which adopts FIFO as the service discipline at each output port. Unfortunately, FIFO is inappropriate for providing QoS guarantees. In this paper, we propose a new scheduling algorithm called the least cushion first/most urgent fist (LCF/MUF) algorithm and formally prove that a CIOQ switch with a speedup factor of 2 can exact emulate an OQ switch which adopts any service scheduling algorithm for cell transmission