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

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. In [1], a scheduling algorithm named the least output occupancy first algorithm was 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 guarantee. Another algorithm proposed in [5] makes a CIOQ switch with a speedup factor of 4 to exact emulate an output queued (OQ) switch which adopts FIFO as the service discipline at each output port. Unfortunately, FIFO is inappropriate for providing QoS guarantee. 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.