BROWSE
Detail
Conference Paper
Matching output queueing with a multiple input/output-queued switch
Cited 4 time in 
Share 
Share
- Authors
- Hyoung-II Lee, Seoung-Woo Seo
- Issue Date
- 2004-03
- Citation
- INFOCOM 2004, pp.1135-1146
- Language
- English
- Type
- Conference Paper
- Abstract
- In this paper, we show that the multiple input/output-queued (MIOQ) switch proposed in our previous paper can emulate an output-queued switch only with two parallel switches. The MIOQ switch requires no speedup and provides an exact emulation of an output-queued switch with a broad class of service scheduling algorithms including FIFO, weighted fair queueing (WFQ) and strict priority queueing regardless of incoming traffic pattern and switch size. First, we show that an N × N MIOQ switch with a (2, 2)-dimensional crossbar fabric can exactly emulate an N × N output-queued switch. For this purpose, we propose the stable strategic alliance (SSA) algorithm that can produce a stable many-to-many assignment, and then apply it to the scheduling of an MIOQ switch. Next, we prove that a (2, 2)-dimensional crossbar fabric can be implemented by two N × N crossbar switches in parallel for an N × N MIOQ switch. For a proper operation of two crossbar switches in parallel, each input-output pair matched by the SSA algorithm must be mapped to one of two crossbar switches. For this mapping, we propose a simple algorithm that requires at most 2N steps for all matched input-output pairs. In addition, to relieve the implementation burden of N input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of N physically-separate memories.
- KSP Keywords
- Class of service, Input-Output, Many-to-many, Output queueing, Scheduling algorithm, Simple algorithm, Strict Priority Queueing, Traffic pattern, Weighted Fair Queueing(WFQ), memory device, multiple-input