Performance Analysis of Clos-Network Packet Switch with Virtual Output Queues

Eiji OKI  Nattapong KITSUWAN  Roberto ROJAS-CESSA  

IEICE TRANSACTIONS on Communications   Vol.E94-B   No.12   pp.3437-3446
Publication Date: 2011/12/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E94.B.3437
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network System
packet switch,  Clos network,  throughput,  matching,  random selection,  

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

A three-stage Clos-network switch with input queues is attractive for practical implementation of a large-capacity packet switch. A scheme that configures the first, second, and third stages in that sequence by performing iterative matchings based on random selections is called the staged random scheduling scheme. Despite the usefulness of such a switch, the literature provides no analytical formula that can accurately calculate its throughput. This paper develops a formula to calculate the throughput analysis of the staged random scheduling scheme for one and multiple iterations used in an input-queued Clos-network switch under uniform traffic. This formula can be used to verify simulation models for very large switches. The introduced derivation considers the processes of the selection scheme at each stage of the switch. The derived formula is used in numerical evaluations to show the throughput of large switch sizes. The results show that the staged random scheduling scheme with multiple iterations for a Clos-network switch with VOQs without internal expansion approaches 100% throughput under uniform traffic. Furthermore, evaluations of the derived formulas are used in a practical application to estimate the number of iterations required to achieve 99% throughput for a given switch size. In addition, the staged random scheduling scheme in an input-queued Clos-network switch is modeled and simulated to compare throughput estimations to those obtained with the derived formulas. The simulation results support the correctness of the derived formulas.