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.

Combined input-crosspoint buffered (CICB) switches relax arbitration timing and provide high-performance switching for packet switches with high-speed ports. It has been shown that these switches, with one-cell crosspoint buffer and round-robin arbitration at input and output ports, provide 100% throughput under uniform traffic. However, under admissible traffic patterns with nonuniform distributions, only weight-based selection schemes are reported to provide high throughput. This paper proposes a round-robin based arbitration scheme for a CICB packet switch that provides 100% throughput for several admissible traffic patterns, including those with uniform and nonuniform distributions, using one-cell crosspoint buffers and no speedup. The presented scheme uses adaptable-size frames, where the frame size is determined by the traffic load.

This letter presents a theoretical analysis of the Parallel Iterative Matching (PIM)'s dynamics with multiple iterations used in an input-buffered packet switch. In our approach, by carefully categorizing all unmatched patterns into several representative patterns after each iteration, probabilities of accumulated matched pairs in a recursive manner are successfully obtained. Numerical evaluations of the analytical formulas are performed.

The scalability of three-stage Clos-network packet switches makes them an attractive approach in implementing large-size packet switches. However, the configuration time of Clos-network switches depends on both the buffering strategy used and the adopted configuration process. To reduce configuration time, this paper focuses on the so-called Memory-Space-Memory (MSM) Clos-network packet switch, where the switch modules in the first and third stages use memory to support resolution of output port contention. The configuration of these switches is then based on a process to dispatch cells from the first-stage modules to the third-stage modules. Therefore, the throughput of an MSM Clos-network switch depends on the dispatching scheme used. This paper introduces a cell dispatching scheme, called maximum weight matching dispatching (MWMD) scheme, for MSM Clos-network switches and a request queue structure in the first-stage modules. The MWMD scheme performs maximum weight matching, similar to that used for input-queued single-stage packet switches, that in combination with the request queues can achieve 100% throughput under independent and identical admissible traffic. This high throughput can be achieved without allocating buffers in the second stage and without expanding the second stage of this three-stage packet switch. A low-complexity dispatching scheme, the maximal oldest-cell-first matching dispatching (MOMD) scheme, is also introduced as an alternative to MWMD. The performance evaluation in this paper shows that MOMD achieves high throughput under unbalanced traffic through the execution of a finite number of iterations.

This paper proposes an innovative Pipeline-based Maximal-sized Matching scheduling approach, called PMM, for input-buffered switches. It dramatically relaxes the limitation of a single time slot for completing a maximal matching into any number of time slots. In the PMM approach, arbitration is operated in a pipelined manner, where K subschedulers are used. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of the subschedulers provides the matching result. We adopt an extended version of Dual Round-Robin Matching (DRRM), called iterative DRRM (iDRRM), as a maximal matching algorithm in a subscheduler. PMM maximizes the efficiency of the adopted arbitration scheme by allowing sufficient time for the number of iterations. We show that PMM preserves 100% throughput under uniform traffic and fairness for best-effort traffic of the non-pipelined adopted algorithm, while ensuring that cells from the same virtual output queue (VOQ) are transmitted in sequence. In addition, we confirm that the delay performance of PMM is not significantly degraded by increasing the pipeline degree, or the number of subschedulers, when the number of outstanding requests for each subscheduler from a VOQ is limited to 1.

Combined input-crosspoint buffered (CICB) packet switches have been of research interest in the last few years because of their high performance. These switches provide higher performance than input-buffered (IB) packet switches while requiring the crosspoint buffers run at the same speed as that of the input buffers in IB switches. Recently, it has been shown that CICB switches with one-cell crosspoint buffers, virtual output queues, and simple input and output arbitrations, provide 100% throughput under uniform traffic. However, it is of general interest to know the maximum throughput that a CICB switch, with no speedup, can provide under admissible traffic. This paper analyzes the throughput performance of a CICB switch beyond uniform traffic patterns and shows that a CICB switch with one-cell crosspoint buffers can provide 100% throughput under admissible traffic while using no speedup.