Quality of service guarantee in a combined input output queued switch

Abstract

Combined input output queued (CIOQ) architecture such as crossbar with speedup has recently been proposed to build a large capacity switch for broadband integrated services networks. It was shown that, for a speedup factor of 2, a CIOQ switch can achieve 100% throughput with a simple maximal matching algorithm [1]. Achieving 100% throughput, however, is not sufficient for per-connection quality of service QoS) guarantee. In [2],[3], it is proved that a CIOQ switch with a speedup factor of 2 can exactly emulate an output queued (OQ) switch if stable matching is adopted. Unfortunately, the complexity of currently known algorithms makes stable matching impractical for high-speed switches. In this paper, we propose a nerv matching algorithm called the least cushion first/most urgent first (LCF/MUF) algorithm and formally prove that a CIOQ switch with a speedup factor of 2 can exactly emulate an OQ switch which adopts any service discipline for cell transmission. A potential implementation of our proposed matching algorithm for strict priority service discipline is also presented.