상세정보
학술대회
Matching output queueing with a multiple input/output-queued switch
- 저자
- 이형일, Seoung-Woo Seo
- 발행일
- 200403
- 출처
- INFOCOM 2004, pp.1135-1146
- 초록
- 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 제안 키워드
- Class of service, Many-to-many, Output queueing, Scheduling algorithm, Simple algorithm, Strict Priority Queueing, Traffic pattern, Weighted Fair Queueing(WFQ), input and output, memory device, multiple-input