We present an approach which addresses a fundamental scaling limitation for conventional switches. Instead of processing the data packets one by one, train queue processing groups multiple data packets together and processes them as one unit. There are two basic train queuing techniques, sequential train queuing and sequential-to-parallel train queuing. The sequential train queue processing can reduce the global switch processing frequency for the switch. The sequential-to-parallel train queue processing can reduce both the global switch processing frequency and data rate by using packet grouping and slicing mechanism. By employing train queuing techniques, a high bandwidth switch can be built and feasibly implemented.

We rigorously examine how to construct a large-scale distributor by taking a logical and systematic approach. We first consider requirements for realization, which include the independent operation of unit modules and the packet sequence integrity, and consider what kind of existing devices have large-scale growth potential. In this process, we take the Batcher sorting network as the candidate device and show that the distribution function can be incorporated to it by furnishing each constituent sorting element with the state inversion capability. Then we show that this is equivalent to replacing each sorting element with a 2/spl times/2 distributor. As a consequence, the large-scale distributor design problem turns into a simple substitution problem for which we substitute a unit distributor for each sorting element in the prototype Batcher sorting network. In addition, we show that this substitution approach can be extended to larger scale unit distributor modules, thus enabling a large-scale distributor realization. The resulting large-scale distributor design procedure can be summarized as follows: given a desired size L=MN for the design of a large-scale distributor, we first design an N/spl times/N Batcher sorter (BS) and then replace each constituent 2/spl times/2 sorting element with a 2M/spl times/2M distributor module.

In this letter we consider two efficient external control input (ECI) value generation methods for the controlled switching element (CSE)-based distributor, which is a new distributor structure that does not require the dummy address generation and extraction operations of the conventional distributors. The first method relies on the active packet counter and the ECI generator for ECI value generation, and the second method utilizes the intrinsic ECI generation property of the CSE-based reverse banyan network (RBN). The first method brings forth a flexible distributor structure, while the second method renders a very simple structure. In fact, the second method yields the so-called autonomous distributor, consisting only of a CSE-based RBN and a set of delays, which is perceived as the simplest among all available distributors. In addition, we introduce a modified version of the autonomous distributor which can speed up the connection-state setup process.

The paper presents a new distribution network which is capable of concentrating and shifting the incoming active packets simultaneously, without requiring dummy destination address generation and extraction processes. It has the structure of a reverse banyan network (RBN) and consists of controlled switching elements (CSEs) which is obtained by extending the passive iterative-cells introduced by Narasimha [1994]. The CSE-based RBN has a set of external control inputs (ECIs) in addition to the data input and output lines and can generate different output patterns according to the ECI values. It is shown through four properties that the CSE-based RBN can perform the distribution function of the conventional distributor. In addition, it is rigorously described in the properties how to determine the set of ECI values to achieve the desired distribution function, which includes the distribution in the normal mode, in the reversed mode, and in alternation of these two modes. The proposed CSE-based distributor can be applied to a variety of occasions by modifying the use of the counter, the numbers to write on the registers, and the table to store the ECI values. Some of useful examples are demonstrated through applications to shift-sequence permutation, N/spl times/R concentration, nonblocking point-to-point switching, and virtual FIFO queueing.>