Quality of Service Guarantee in a Combined Input Output Queued Switch

Tsern-Huei LEE
Yaw-Wen KUO
Jyh-Chiun HUANG

Publication
IEICE TRANSACTIONS on Communications   Vol.E83-B    No.2    pp.190-195
Publication Date: 2000/02/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (IEICE/IEEE Joint Special Issue on Recent Progress in ATM Technologies)
Category: ATM Switch and System Development
Keyword: 
quality of service,  combined input output queued switch,  matching,  exact emulation,  

Full Text: PDF(668.5KB)>>
Buy this Article


Summary: 
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. 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 new 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.