In this paper, we propose a novel load-balancing scheme for the Birkhoff-von Neumann input-queued (BvN-IQ) switch, which we call the cyclic exchange. According to the cyclic exchange scheme, in each time slot each linecard transfers a cell from its non-empty VOQ to the empty VOQ of another linecard which is destined for the same output. In order to guarantee the cell sequence in this procedure, we propose a simple rule of selecting the cells to be transferred for load balancing, and prove the sequence guarantee by the proposed rule. Since the cyclic exchange is performed locally between two linecards, its communication and computation overhead is not too heavy to implement. To be specific, the communication overhead of the proposed scheme is the transmission of N bits and its computation overhead corresponds to a priority encoder with a fixed highest priority. The simulation results show that the proposed scheme achieves 100% throughput asymptotically and shorter delay than the two-stage switch.

In this paper, we propose a novel load-balancing scheme for two-stage switches which does not disturb the sequence of packets. The proposed scheme uses chamber queues(CQs) in front of the second crossbar fabric as well as VOQs in front of the first crossbar. A chamber queue is composed of N banks each of which can store only one packet destined for each output. The two crossbar fabrics in the proposed switch are configured by a deterministic sequence of N connection patterns as in other two-stage switches. In a time slot, the proposed switch transfers packets from non-empty VOQs to the corresponding empty banks of CQs via the first crossbar, and the packets from CQs are switched to their destinations via the second crossbar. While the proposed scheme is very simple, it can achieve 100% throughput under not only uniform but also non-uniform traffic. Moreover, the simulation results show that the average delay of packets in the proposed two-stage switch is lower than that in the original two-stage switch.

We show that the multiple input/output-queued (MlOQ) switch proposed in our previous paper H. I. Lee and S. W. Seo (May 2003) 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 /spl times/ N MIOQ switch with a (2, 2)-dimensional crossbar fabric can exactly emulate an N /spl times/ 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 /spl times/ N crossbar switches in parallel for an N /spl times/ 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.

In this paper, we study a practical approach to match the performance of an output-queued switch statistically. For this purpose, we propose a novel switching architecture called a multiple input/output-queued (MIOQ) switch that requires no speedup for providing sufficient switching bandwidth. To operate an MIOQ switch in a practical manner, we also propose a multi-token-based arbiter which schedules the switch at a high operation rate and a virtual FIFO queueing scheme which guarantees the departure order of cells belonging to the same traffic flow at output. Additionally, we show that the proposed switch can naturally provide symmetric bandwidth for dealing with the links with different bandwidth demands. Finally, we compare the performance of an MIOQ switch with that of an output-queued switch and discuss the design criteria to match the performance of an output-queued switch.

We study a practical approach to match the performance of an output-queued switch statistically. For this purpose, we propose a novel switching architecture called a multiple input/output-queued (MIOQ) switch that requires no speedup for providing sufficient switching bandwidth. To operate an MIOQ switch in a practical manner, we also propose a multitoken-based arbiter which schedules the switch at a high operation rate and a virtual first-in first-out queueing scheme which guarantees the departure order of cells belonging to the same traffic flow at output. Additionally, we show that the proposed switch can naturally provide asymmetric bandwidth for inputs and outputs, which may be important in dealing with the links with different bandwidth demands. Finally, we compare the performance of an MIOQ switch with that of an output-queued switch and discuss the design criteria to match the performance of an output-queued switch.

In this paper, we investigate the performance characteristics of parallel switching architectures constructed by a stack of multistage switching networks. First, we propose a general analysis model which describes two directional traffic flows with a traffic-distribution characteristic. By applying this model to an MBCP (multiple banyan connected in parallel) switch, we show that the traffic-distribution characteristic plays an important role for the accuracy of a performance model. Next, to verify the accuracy of our approach to model the parallel switching architecture with a traffic-distribution capability, we select and analyze the WGSN (weaved generalized shuffle network) which is based on a multihop switching architecture. From the comparison with simulation results, we show that the developed model accurately predicts the performance of a WGSN under the assumption that the traffic-distribution characteristic is uniform.

In this paper, we analyze ways of realizing permutations in a class of 2log/sub 2/N- or (2log/sub 2/N-1)-stage rearrangeable networks. The analysis is based on the newly developed inside-out routing algorithm and we derive the upper and lower bounds on the number of possible realizations of a permutation. It is shown that the algorithm can provide us with comparable degrees of freedom in realizing a given permutation as the well-known looping algorithm, while it can be more generally applied to a class of 2log/sub 2/N- or (2log/sub 2/N-1)-stage rearrangeable networks. In finding a set of complete assignments for the center-stage cycles, alternate realizations of a permutation can be obtained by changing the initial position, changing the assigning direction, or even interchanging the first-level decompositions of the permutation. We also show that these numerable alternate realizations can be utilized to make the networks tolerate some sets of faults, i.e., control faults of SEs including stuck-at-straight and stuck-at-cross. Various cases of single control faults at the center stages and other stages are examined through examples. These new approaches originate from routing outward from center stages to outer stages; therefore, the center stages and two half networks may be treated separately.

A new multipath multistage interconnection network called the Augmented Composite Banyan Network (ACBN) is proposed. The ACBN is created by adding a link to each SE of the Composite Banyan Network (CBN), which is a multipath network with at least two disjoint paths and was originally proposed in (Seo and Feng, 1995). Therefore, the basic building blocks in the ACBN are 4/spl times/4 SEs with log/sub 2/N stages. The ACBN inherits the favorable features of the CBN such as regularity, symmetry and easy rerouting capability under faults and conflicts. The ACBN also has an efficient and fast control algorithm that can easily generate a primary routing tag and alternative routing tags as in the CBN. A major improvement of the ACBN over the CBN is the higher connectivity with four disjoint paths between any source and destination pair. Moreover the ACBN can generate alternative routing tags in a much simpler way i.e., by a simple binary operation not by the conversion table as in the CBN. To compare the ACBN with other networks in connectivity, we introduce the definition of a degree of connectivity as a new connectivity measure function. The comparison results show that due to high connectivity the ACBN can resolve more random connection requests than other networks by using only a small amount of additional hardware.

In this paper, we propose a new high performance ATM switch architecture based on a high connectivity multipath multistage interconnection network called augmented composite banyan network (ACBN). The ACBN is created by adding a link to each switching element of the composite banyan network, which is a multipath network with at least two disjoint paths and was originally proposed in Seo and Feng (1995). The switch performance is studied under uniform and full load conditions. The analysis and simulation results show that the proposed switch can achieve a required cell loss probability using fewer stages than previously reported switches.