A new class of self-routing permutation networks based on the de Bruijn digraphs is proposed. The new networks are modular and scalable, and have an optimal crosspoint complexity. Compared to the crossbar switches of the same size, nD-dBPN uses less cross-points, and operates faster. With its optimal configuration, the new network uses O (N log N) cross-points compared to O (N/sup 2/) cross-points of the crossbar switches. The 2D-dBPN has the same crosspoint complexity as the 3-stage Clos network, but it has a constant control complexity compared to /spl Omega/(N/sup 3/2/) of the Clos network.

We propose STWnet, a self-routing high bandwidth optical network architecture for interconnecting users, grouped together as g groups with w users per group. STWnet uses the three dimensions of space, time, and wavelength by combining the advantages of space and temporal switching with the benefits of wavelength parallel data transmissions. Technologically difficult switching of individual wavelengths is avoided by prearranging transmissions in a way that they can be switched in a wavelength insensitive manner. Wavelengths are reused within the network thus allowing for a larger switching fabric. The proposed architecture can be internally expanded either in the spatial or temporal dimension to allow for multiple packets to be delivered to the same destination group. The expansion factor is determined based on the group knockout principle and given typical traffic patterns is a small number. STWnet allows easy group to group multicasting and broadcasting while system-wide multicasts and broadcasts can be achieved through repetitive group-to-group transmissions. The network uses readily available components such as opto-electronic directional couplers, fixed wavelength transmitters, and diffraction based parallel receivers while avoiding the use of relatively slow and expensive tunable components.

We propose TDM/TWDM de Bruijn networks and ShuffleNets by utilizing small all-optical dilated slipped banyan networks, DSBs (Thompson, 1991). The proposed networks require fewer switches than DSBs, and smaller numbers of wavelengths than WDM de Bruijn networks and ShuffleNets. Furthermore, only one fixed-wavelength transmitter and one fixed-wavelength receiver are required for each node.

We propose SXmin: a self-routing, group-knockout principle based asynchronous transfer mode (ATM) packet switch which provides comparable delay-throughput performance and packet loss probabilities at significantly reduced hardware requirements compared to earlier switches. The M/spl times/N SXmin consists of an N/spl times/N Batcher sorter followed by log/sub 2/N-1 stages of sort-expander (SX) modules arranged in the form of a complete binary tree. Each SX module consists of a column of 2/spl times/2 switches with a wraparound-unshuffle input-output interconnection. This enables the hierarchical utilization of the group-knockout principle to expand the number of inputs by a small factor at each stage, resulting in a significant reduction in overall hardware complexity. Routing at each switch is controlled by a single bit. However, in case of contention, a dual bit resolution algorithm is used locally which drops excess packets in a predetermined manner while ensuring global randomness of packet loss over the entire switching network. There are no internal buffers at the individual stages and therefore the internal delay is constant and proportional to the number of stages. The use of simple hardware components and regular interconnections in the SX modules makes the network suitable for optical implementation.

The general time-space-time switching problem in telecommunications requires the use of multichannel time slot interchangers. We propose two multichannel time slot sorters which sort N/sup 2/ time-division multiplexed (TDM) optical inputs, arranged as N frames with N time slots per frame using O(Nlog/sup 2/N) optical switch elements. The TDM optical inputs are sorted in place without expanding the space-time fabric into a space-division switch. The hardware components used are 2/spl times/2 optical switches (LiNbO/sub 3/ directional couplers) and optical delay lines connected in a feedforward fashion. Two space-time variants of the spatial odd-even merge algorithm are used to design the sorters. By maintaining the number of shift-exchange operations invariant at each stage, the proposed sorters use fewer switches than previously proposed sorters using switches with feedback line delays. The use of local control at each 2/spl times/2 switch makes the proposed sorters more practical for high-speed optical inputs than Benes-based time slot permuters with global control and high latency, which affects interframe distance. Both time slot sorters support pipelining of input frames and sorted outputs are available at each time slot after an initial frame delay. The proposed sorters find practical application in the time-domain equivalents of space-division, nonblocking, self-routing packet switches using the sort-banyan architecture, such as the Starlite switch, Sunshine switch, etc.

We propose knockout switch-based multistage interconnection networks (KSMINs) for fast packet switching, combining the well-known knockout switch and the concept of multistage interconnection networks. The main objective is to reduce the severe pin requirements of large knockout switches through a phased address filtering. We present an approximate Markov-chain model of KSMINs to study the performance of KSMINs with different numbers of address-filtering phases. The model is shown to be accurate within 5% for all the cases considered and within 20% for the meaningful cases of the buffer sizes /spl ges/4. For the (256/spl times/256) KSMIN, two-phase address filtering based on the (16/spl times/16) knockout switches is shown to perform very closely to the single-stage knockout switch for a reduced hardware cost.>

The knockout switch is a nonblocking, high-performance switch suitable for broadband packet switching. It allows packet losses, but the probability of a packet loss can be kept extremely small in a cost-effective way. The performance of the knockout switch was analyzed under uniform traffic. In this paper, we present a new, more general analytic model of the knockout switch, which enables us to evaluate the knockout switch under nonuniform traffic. The new model also incorporates the effects of a concentrator and a shared buffer on the packet loss probability. Numerical results for nonuniform traffic patterns of interest are presented.>

The authors propose optical networks TdB(d, k) and TDM ShuffleNet(d, k), which are the TDM versions of the WDM de Bruijn network and the WDM ShuffleNet(d, k), respectively. They also propose the TWdB(d, k) and TWDM ShuffleNet(d, k), variations of the TdB and TDM ShuffleNet, which combine the TDM and WDM to further reduce the hardware cost. The dilated slipped banyan networks, DSB(d)'s are used to provide a time division multiplexed operation in all four networks. The proposed networks have a simple column control and a dilated operation suitable for guided-wave and free-space technologies. Only one fixed-wavelength transmitter and one fixed-wavelength receiver are required per node. The performance in terms of channel efficiency, delay and throughput is analysed.>

We consider time slot interchangers (TSIs) which are built from 2/spl times/2 exchange switches and delays and which are useful for time division multiplexed (TDM) systems in telecommunications and pipelined systems such as time multiplexed optical multiprocessors. We formulate a general method for constructing TSIs based on multistage interconnection networks in the space domain via space-to-time mapping. Two types of TSIs, time slot permuters and time slot sorters, are considered. We review the time slot permuter based on the Benes network, and obtain the /spl Lambdaspl tilde/ time slot permuter based on the bit-controlled, self-routing /spl Lambda/ permutation network. The time slot sorter, S/sub N/, is obtained from the Batcher spatial sorting network. The generalized Lambda time slot permuter /spl Lambdasub Nsup q/ is obtained, in an algorithmic approach, by combining the idea of the /spl Lambdaspl tilde/ time slot permuter and Q-way bitonic decomposition (Q=2/sup q/). The numbers of switches, control complexities, and frame delays of these architectures are compared, and the problem of crosstalk in optical implementation is discussed. It is shown that control complexity can be traded against the number of switches.>

Generalized de Bruijn digraph, G_{B}(d,n), was proposed independently by Imase and Itoh, and Reddy, Pradhan and Kuhl to include any number of nodes. Du and Hwang showed that G_{B}(d, n) essentially retains all the nice properties of de Bruijn digraphs, and presented a \left\lceil {\log _d n} \right\rceil -step routing algorithm, where d is the indegree and outdegree, and n is the number of nodes in the graph.

Abstract The star graph has a smaller degree and diameter than the well‐known n‐cube, and can be an alternative to the n‐cube for systems with a large number of nodes [2]. In our previous work [11], three different indirect star‐type networks were obtained from the star graph: the indirect star network I, the indirect star network II, and the star‐delta network. However, the indirect star networks I & II are constructed from large switches, and do not perform as well as the indirect cube‐type networks of comparable switch sizes. Also, they are not modular. The star‐delta network is modular, but it employs varying switch sizes for different switching stages, and has a lower performance than the indirect cube‐type networks based on comparable switch sizes. Moreover, the switch sizes for all three indirect star networks grow with the network size. In this work, a new indirect star network, called the μ‐star network, is proposed. Being modular and constructed from (2 × 2) crossbar switches, the new network is an improvement over previously proposed indirect star‐type networks. The μ‐star network is analyzed for its performance and the analytic results are verified through simulations. © 1993 by John Wiley & Sons, Inc.

Buffered banyan networks are highly vulnerable to nonuniform traffic, due to the path sharing as well as the existence of only a single path per network input-output pair. Improving on an earlier packet distribution network which is a banyan network itself, a single-stage packet-scattering hardware, called the pseudo-randomizer (PR), is proposed. The PR-banyan, the PR followed by a buffered banyan, is analyzed under nonuniform traffic, and is shown to be highly effective under nonuniform traffic. The analytic results are shown to match the simulation results very closely.>

The authors formulated a general method for constructing time slot permuters from spatial permutation networks. Using the method, they constructed a new time slot permuter, the Lambda time-slot permuter. The Lambda time slot permuter is obtained from the bit-controlled, self-routing permutation network, the Lambda network. While the Lambda time slot permuter requires more hardware than the time slot permuter based on the Benes network described by S.V. Ramanan et al. (1990), its control is very simple. In the Lambda time slot permuter, a single bit from the destination tag in the first of a pair of time slots entering an exchange element is used as the control bit so that the switch setting can be done before the second time slot arrives; thus, it is possible that the switch setting does not incur any delay. The Lambda time slot permuter is suitable for a class of applications where on-the-fly control of the time slot permuter is important, and is especially efficient for a pipelined operation.>

Existing packet combining schemes, implemented either by hardware or software, developed for hot-spot congestion-control in multiprocessors are not applicable for use in telecommunication systems. The authors propose a hot-spot prevention scheme which exploits the structural characteristics of buffered delta networks to regulate the traffic. This scheme prevents the tree saturation by controlling the flow of the packets into the network and ensures that the hot-spot traffic can be supported with little degradation to the throughput of the uniform traffic, even when more than one hot-spot exists. The scheme retains all the desirable properties, including packet order preserving, of buffered delta networks, and is shown by simulations to be highly effective under either light or heavy hot-spot traffic. Since no a priori knowledge of the traffic patterns is required, the proposed scheme can be applied equally well to buffered delta networks in multiprocessors and telecommunication systems.>

The authors propose three indirect star-type networks, the indirect star networks I and II and the star-delta network, and investigate their properties. An indirect star-type network is obtained by unfolding the star graph. The star-delta network is obtained through an unfolding scheme based on the recursive property of the star graph, and has n-1 switching stages. The star-delta network has the advantage of being controlled by the destination tag routing scheme. The indirect star-type networks are to the star graph as the indirect cube-type networks are to the n-cube. The authors analyze the performance of the indirect star-type networks under uniform traffic to investigate their potential as an alternative to the indirect cube-type networks for the future high-performance large multiprocessor systems.>

A multistage interconnection network (MIN) for multiprocessor systems is proposed. The proposed MIN, called the B-network, uses backward links to provide backward paths for the requests blocked at switches or memory due to contentions. The gamma network is known to contain a cube network (specifically, the inverse omega network) as a substructure. The B-network is obtained from the gamma network by preserving the cube structure but reversing the direction of all other links. These backward links are used as alternate paths for requests blocked due to path or memory contentions. The B-network can be controlled by the simple destination tag control algorithm; packets navigating through the B-network, using both regular forward links and backward links, can reach their destinations under the destination tag control. The performance of the B-network is analyzed under the uniform traffic model and compared to various networks of interest. It is shown that the B-network surpasses the performance of the gamma network, the crossbar switch, and single-buffered MINs based on (2*2) switches, while having the same hardware complexity as the gamma network.>

An analytic model and analytic results for the performance of multibuffered packet-switching interconnection networks in multiprocessor systems are presented. The performance of single-buffered delta networks is first modeled using the state transition diagram of a buffer. The model is then extended to account for multiple buffers. The analytic results for multibuffered delta networks are compared to simulation results. The performance of multibuffered data manipulator networks is analyzed to demonstrate the generality of the model.>

This paper presents a new analytic model for buffered Banyan networks. The new model is the most general one in the current literature, and allows the traffic pattern, the buffer size, and the switch size as input parameters among other things. The main motivation of the development of the new model was to provide an analytical tool to evaluate the performances of buffered Banyan networks under nonuniform traffic patterns, which mostly remained unknown except for some very limited cases. With the new model, we measured network performances for several important memory access patterns occurring in the parallel loop execution in multiprocessors. The performance results and the implications of the results on data storage schemes are discussed.

A scheme based on the standard multiplier recoding technique that enables the use of (5*5) switches for PM2I networks is presented. The connections between switching stages are based on the modified PM2I functions, and are called plus-minus-2/sup 2i/ (PM22I); hence, these networks are called the PM22I networks. Since the number of switching stages in the PM22I networks is one-half of those in the PM2I networks, with a moderate increase in the switch size from (3*3) to (5*5), these networks provide similar design tradeoffs availability by the (2*2) and (4*4) cube networks.>

The augmented data manipulator (ADM), inverse augmented data manipulator (IADM), and the gamma network are based on the plus-minus-2/sup i/ connection patterns. In such a network, there exists multiple paths to connect a source S to a destination D except when S=D. The number of paths for (S,D) is a function of the tag value (D-S) modulo N, and the size of the network N. It is shown that by adding an extra stage to the PM2I interconnection network, multiple paths are provided for all the tag values including 0. The extra stage can be any stage out of n=log/sub 2/N stages of the original network. The analyses on the distribution of the number of paths for various tag values are performed for n possible choices of the extra stage. It is shown that the extra stage of 0, +1, -1 connection patterns gives the most uniform distribution, and also results in a 1-fault tolerant interconnection network.>

Formulas for the number of the augmented-data-manipulator (ADM)-passable permutations were given previously as cross-recurrence relations for the cardinalities of three specific subsets of such permutations. More concise, transparent recurrence formulas are derived utilizing a novel and conceptually simple model of the ADM. As a byproduct, a global control algorithm for the inverse ADM (IADM) is obtained that can set paths for all the IADM-passable permutations. This algorithm can be adapted for the ADM. Also included are two local control algorithms for the IADM/ADM: the signed bit difference tag control and the destination tag control.>

A new Benes network control algorithm is presented. Unlike the original looping algorithm, the new algorithm is not recursive. In this algorithm (N x N) Benes network is viewed as a concatenation of two subnetworks SN1 and SN2. The first (log N - 1) stages of a Benes network correspond to SN1, and the remaining log N stages correspond to SN2. SN1 is controlled by a full binary tree of set partitioning functions, called a Complete Residue Partition Tree, and SN2 is bit controlled. The new control algorithm sets switches one stage at a time, stage by stage.

The augmented data manipulator (ADM), inverse augmented data manipulator (IADM), and the gamma network are based on the Plus-Minus-2 i connection patterns. In such a network there exist multiple paths to connect a source S to a destination D except when S=D. The number of paths for (S,D) is a function of the tag value (D-S) modulo N, and the size of the network N. It is shown in this paper that by adding an extra stage to the original PM21 interconnection network, multiple paths are provided for all the tag value including 0. The extra stage can be any stage out of n=log 2 N stages of the original network. The analyses on the distribution of the number of paths for various tag values are performed for n possible choices of the extra stage. It is shown that the extra stage of 0, +1, -1 connection patterns gives the most uniform distribution, and also results in a 1-fault tolerant interconnection network.

For any parallel computer systems which consist of many processing elements and memories, interconnection networks provide communication paths among processing elements and memories. Both the rearrangeability proof and the control algorithm are well known for the Benes network, which is intrinsically symmetric. However, there has been little progress for the case of nonsymmetric networks of similar hardware requirements.