Document Type

Article

Publication Date

2006

Publication Title

IEICE Transactions on Communications

Volume

E89-B

Issue

9

First page number:

2457

Last page number:

2468

Abstract

Combined input and output queuing (CIOQ) switches are being considered as high-performance switch architectures due to their ability to achieve 100% throughput and perfectly emulate output queuing (OQ) switch performance with a small speedup factor S. To realize a speedup factor S, a conventional CIOQ switch requires the switching fabric and memories to operate S times faster than the line rate. In this paper, we propose to use a CIOQ switch with space-division multiplexing expansion and grouped input/output ports (SDMG CIOQ switch for short) to realize speedup while only requiring the switching fabric and memories to operate at the line rate. The cell scheduling problem for the SDMG CIOQ switch is abstracted as a bipartite k-matching problem. Using fluid model techniques, we prove that any maximal size k-matching algorithm on an SDMG CIOQ switch with an expansion factor 2 can achieve 100% throughput assuming input line arrivals satisfy the strong law of large numbers (SLLN) and no input/output line is oversubscribed. We further propose an efficient and starvation-free maximal size k-matching scheduling algorithm, kFRR, for the SDMG CIOQ switch. Simulation results show that kFRR achieves 100% throughput for SDMG CIOQ switches with an expansion factor 2 under two SLLN traffic models, uniform traffic and polarized traffic, confirming our analysis.

Keywords

Algorithms--Data processing; Computer networks; Parallel Computer Architecture; Switching theory--Data processing

Disciplines

Computer and Systems Architecture | Digital Communications and Networking | Electrical and Computer Engineering | Systems and Communications | Systems Architecture | Theory and Algorithms

Language

English

Permissions

Copyright Institute of Electronics, Information and Communication Engineers. Used with permission.

Download

UNLV article access

Search your library

Share

COinS