The Tera project: a hybrid queueing ATM switch architecture for LAN

The Tera ATM LAN project at Carnegie Mellon University addresses the interconnection of hundreds of workstations in the Electrical and Computer Engineering Department via an ATM-based network. The Tera network architecture consists of switched Ethernet clusters that are interconnected using an ATM network. This paper presents the Tera network architecture, including an Ethernet/ATM network interface, the Tera ATM switch, and its performance analysis. The Tera switch architecture for asynchronous transfer mode (ATM) local area networks (LAN's) incorporates a scalable nonblocking switching element with hybrid queueing discipline. The hybrid queueing strategy includes a global first-in first-out (FIFO) queue that is shared by all switch inputs and dedicated output queues with small speedup. Due to hybrid queueing, switch performance is comparable to output queueing switches. The shared input queue design is scalable since it is based on a Banyan network and N FIFO memories. The Tera switch incorporates an optimal throughput multicast stage that is also based on a Banyan network. Switch performance is evaluated using queueing analysis and simulation under various traffic patterns     

A New Architecture for Nonblocking Optical Switching Networks

With the current technology, all-optical networks require nonblocking switch architectures for building optical cross-connects. The crossbar switch has been widely used for building an optical cross-connect due to its simple routing algorithm and short path setup time. It is known that the crossbar suffers from huge signal loss and crosstalk. The Clos network uses a crossbar as building block and reduces switch complexity, but it does not significantly reduce signal loss and crosstalk. Although the Spanke's network eliminates the crosstalk problem, it increases the number of switching elements required considerably (to 2N ² - 2N). In this paper, we propose a new architecture for building nonblocking optical switching networks that has much lower signal loss and crosstalk than the crossbar without increasing switch complexity. Using this architecture we can build non-squared nonblocking networks that can be used as building block for the Clos network. The resulting Clos network will then have not only lower signal loss and crosstalk but also a lower switch complexity.     

Design of wide-sense nonblocking multicast ATM switches

Nonblocking multicast asynchronous transfer mode (ATM) switches can simplify the call admission control process and increase the external links' utilization. We derive the wide-sense nonblocking condition for multicast ATM switches based on a general Clos network. We also propose a routing algorithm to achieve wide-sense nonblocking. It is illustrated by an example that the number of required middle stages in our switch is significantly less than that of strictly nonblocking multicast switches     

基于信元分布网络结构的内部无阻塞Banyan┐n网络

本文首先给出了Ｂａｎｙａｎ－ｎ网络的概念。在指出了传统缓冲Ｂａｎｙａｎ－ｎ中存在的内部阻塞现象以后，提出了一种具有信元分布网络（ＣｅｌＤｉｓｔｒｉｂｕｔｉｏｎＮｅｔｗｏｒｋ，ＣＤＮ）结构的Ｂａｎｙａｎ－ｎ网络，该网络几乎无内部信元阻塞。同时，通过在每个交换单元中采用Ｋｎｏｃｋｏｕｔ交换结构，可使其内部加速因子保持恒定，从而使其能够作为构成大规模ＡＴＭ交换网络的一种基本结构。     

A new design for wide-sense nonblocking multicast switching networks

In this paper, we propose a new design for a wide-sense nonblocking multicast switching network, which has many comparable properties to a strictly nonblocking Clos permutation network. For a newly designed four-stage N/spl times/N multicast network, its hardware cost, in terms of the number of crosspoints, is about 2(3+2/spl radic/2)N/sup 3/2/=11.66N/sup 3/2/, which is only a small constant factor higher than that of a three-stage nonblocking permutation network, and is lower than the O(N/sup 3/2/(logN/loglogN)) hardware cost of the well-known three-stage wide-sense nonblocking multicast network. In addition, the proposed four-stage nonblocking multicast network has a very simple routing algorithm with sublinear time complexity, and does not require multicast capability for the switch modules in the input stage.     

Rearrangeable Nonblocking 8 × 8 Matrix Optical Switch Based on Silica Waveguide and Extended Banyan Network

Based on the crossbar network and the Banyan network (BN), a new rearrangeable nonblocking structure of extended Banyan network (EBN) was proposed for implementing an 8 times 8 optical matrix switch. The interconnection characteristics of the rearrangeable nonblocking EBN were studied, and the diagram of the logic program for driving the operation of switching units was provided. A silica waveguide 8 times 8 matrix optical switch was designed and fabricated according to the calculated results. The silica waveguide propagation loss of 0.1 dB/cm and waveguide-fiber coupling loss of 0.5 dB/facet were measured. With the fabricated 8 times 8 matrix optical switch, the insertion loss of 4.6 dB, the crosstalk of -38 dB, the polarization-dependent loss of 0.4 dB, the averaged switching power of 1.6 W, and the switching time of 1 ms were achieved. A basic agreement between experimental results and theoretical calculated values was achieved     

A superconducting Batcher-Banyan switch

The paper describes a Batcher sorter and a Banyan network which together form a nonblocking and self-routing switch. The Batcher sorter sorts input packets in the order of their address values. This sorting operation guarantees no blocking in the succeeding Banyan network and presents an efficient way to check contention. The Banyan network distributes contention-free packets to their final destinations. The Batcher and Banyan switches were designed by using a three-junction SQUID gate family driven by three-phase powering clocks. The Batcher sorter is composed of 2×2 Batcher switching elements. Each Batcher switching element sorts two input packets in the order of their address values. A 4×4 Batcher sorter with 2-b data width, which is composed of six 2×2 Batcher switching elements, was fabricated by an Nb tri-layer process. Its correct operation was confirmed. The Banyan network consists of 2×2 Banyan switching elements. A 2×2 Banyan switching element with 2-b data width was also fabricated. The correct operation was confirmed up to 4 GHz by using a test pattern generator integrated on-chip     

Banyan网输入输出排队的神经网络调度及其实现

Ｂａｎｙａｎ网是一种多级互联网络，它广泛地应用在ＡＴＭ交换结构中．Ｂａｎｙａｎ网输入排队的神经网络调度方法已有文章提出，但其硬件实现比较复杂．本文提出了一种Ｂａｎｙａｎ网输入输出排队的神经网络调度方法，它的硬件实现容易．计算机模拟结果表明，该调度方法是非常有效的．在此，还给出了该系统的硬件实现方法．     

适用于准循环LDPC码译码器的新型循环移位置换结构设计

循环移位置换单元是准循环LDPC码的部分并行译码器的重要组成部分。该文研究并证明了Reverse Banyan交换结构在实现信息循环移位时各个基本交换单元的连接规律。基于该规律设计了基于可预置选路算法的无阻塞循环移位置换结构。相比Benes交换结构和Reverse Banyan交换结构,提高了信息循环移位交换的速率,且占用较少的硬件资源和面积。最后设计了一个出线转换单元,该单元适用于各种循环移位交换结构。     

Nonblocking multirate distribution networks

Results for nonblocking distribution networks are generalized for the multirate environment in which different user connections share a switch's internal data paths for arbitrary fractions of the total capacity. Conditions under which network proposed by Y.P. Ofman (1965), C.D. Thompson (1978), and N. Pippenger (1973) lead to multirate distribution networks are derived. The results include both rearrangement and wide-sense nonblocking networks. The complexity of the rearrangement multirate network exceeds that of the corresponding space-division network by a log log factor, while the complexity of the wide-sense nonblocking network is within a factor of two of the corresponding space-division network     

Proposed Low-Power High-Speed Microring Resonator-Based Switching Technique for Dynamically Reconfigurable Optical Interconnects

The dynamic bandwidth re-allocation (DBR) technique balances traffic by re-allocating bandwidth from under-utilized links to over-utilized links in a network. In this letter, we propose a nonblocking, fast, low-power, and integratable optical switch that enables DBR. The basic building blocks of the proposed switch are silicon-on-insulator-based microring resonators. Analytical and numerical studies show that the active switch design gives similar performance in throughput and latency, while reducing cost (number of lasers) and area significantly when compared to implementation of DBR with only passive components. There is a slight increase in power (~0.4% for worst-case traffic pattern) using the active switch implementation.     

Wide-sense and strict-sense nonblocking operation of multicastmulti-log2 n switching networks

Multicast connections are used in broad-band switching networks as well as in parallel processing. We consider wide-sense and strict-sense nonblocking conditions for multi-log₂ N switching networks with multicast connections. We prove that such networks are wide-sense nonblocking if they are designed by vertically stacking at least t · 2^n-t-1 + 2 ^n-2t-1 planes of a log₂ N networks together, where 1 ⩽ t ⩽ [n/2] and t defines the size of a blocking window K = 2^t. For t = [n/2] and n even, and for [n/2] ⩽ t ⩽ n the number of planes must be at least t · 2^n-t-1 + 1 and 2^t + (n - t - 1) · 2^n-t-1 - 2^2t-n-1 + 1, respectively. In the case of strict-sense nonblocking switching networks, the number of planes is at least N/2. The results obtained in this paper show that in many cases number of planes in wide-sense nonblocking switching networks is less than those for t = [n/2] considered by Tscha and Lee (see ibid., vol.47, p.1425-31, Sept. 1999). The number of planes given in the paper is the minimum number of planes needed for wide-sense nonblocking operation provided that Algorithm 1 is used for setting up connections. The minimum number of planes for such operation in general is still open issue     

Fault-Tolerant Multistage Interconnection Network

In this paper, a new fault-tolerant Banyan (FTB) network design is proposed. The rules to add extra hardware and links to the regular Banyan network in order to get the new FTB network are presented. The work includes a modular design for a new 2×2 switch element that can be configured in different well-defined modes. In case an error occurs in the function of a switch in the FTB network, the switch can be bypassed and other switch in the network replaces its role. The most attractive feature of the new design is that it can maintain the original (regular) Banyan topology in the presence of faults. Consequently, the system performance will not be affected due to the occurrence of tolerable faults in the interconnection network. This feature makes our design different from all fault-tolerant designs. Moreover, multiple faults can be tolerated in the proposed FTB network. The FTB network will be very powerful in safety critical systems and applications where error can lead to catastrophic events.     

A fast parallel-tree switch architecture for ATM networks

In this paper we present a novel fast packet switch architecture based on Banyan interconnection networks, called parallel-tree Banyan switch fabric (PTBSF). It consists of parallel Banyans (multiple outlets) arranged in a tree topology. The packets enter at the topmost Banyan. Internal conflicts are eliminated by using a conflict-free 3 × 4 switching element which distributes conflicting cells over different Banyans. Thus, cell loss may occur only at the lowest Banyan. Increasing the number of Banyans leads to a noticeable decrease in cell loss rate. The switch can be engineered to provide arbitrarily high throughput and low cell loss rate without the use of input buffering or cell pre-processing. The performance of the switch is evaluated analytically under uniform traffic load and by simulation, under a variety of asynchronous transfer mode (ATM) traffic loads. Compared to other proposed architectures, the switch exhibited stable and excellent performance with respect to cell loss and switching delay for all studied conditions as required by ATM traffic sources. The advantages of PTBSF are modularity, regularity, self-routing, low processing overhead, high throughput and robustness, under a variety of ATM traffic conditions. © 1998 John Wiley & Sons, Ltd.     

The deflection self-routing Banyan network: A large-scale ATMswitch using the fully adaptive self-routing and its performanceanalyses

Because the Internet traffic, that will be the major traffic of broadband integrated services digital networks, is bursty when cells are being switched within the multistage switching network, it has a higher possibility that multiple cells arriving simultaneously at a switching element through different incoming links may have to be forwarded along the same outgoing link. We propose a high-performance large-scale ATM switch dealing with such link contention problem. It is a new unbuffered augmented Banyan network using fully adaptive self-routing control: the deflection self-routing Banyan network. To utilize all the links of the network as alternate paths, we employ the deflection-routing algorithm in each switching element, such that cells failing to get selected for the intended link are sent along different links, in the hope that they later return, or detour the contended link and continue their journey to the destination. Cells are never dropped within the switching network, whereas the switch has no multiple cell buffers. The proposed routing is as simple as that of the generic Banyan network, and all the switch elements (SEs) have a uniform structure. To design the proposed network and its self-routing, we use the topological properties that all the SEs of the Banyan network are arranged in a regular pattern topologically. We formulate and prove these properties through an algebraic formalism. We also ran a performance analysis to provide quantitative comparison against the Banyan network and the replicated Banyan networks. As a result, we show that the new network has a far better performance and scalability than the other networks     

An Architecture for TSI-Free Nonblocking Optical TDM Switches

One of the key elements in building a time-division- multiplexed (TDM) switch is the time slot interchange (TSI). Given the current optical switching and buffer technologies, TSI-based TDM architectures have many implementation drawbacks, including severe signal attenuation. Some studies showed that some space-time equivalence diagrams can be converted into a delay-unit-based (TSI-free) TDM. This type of architecture is attractive for optical TDM switches, but the techniques discussed in those studies are for rearrangeable switches. Many applications require nonblocking switches where adding a new connection (or a flow) will not cause rearrangement of existing connections. In this paper, we present the design principle for building strictly nonblocking delay-unit-based (TSI-free) optical TDM switches.     

Optimum switching architectures using D-fiber opticalspace switches

An optical space switch based on D-fibers has been fabricated and its use in switching networks investigated. The characteristics of a switching network depend not only on the nature of the switches used, but also on the architecture utilized. In general, architectural complexity can be used in a trade with switch specification to achieve a given network behavior. Several architectures are reviewed and their consequences on the switch specification evaluated. The principles of a D-fiber space switch are described, and the switching characteristics predicted and measured. The characteristics of the switch, within its optimum architecture, enable a fully transparent network, i.e. totally nonblocking with minimum restriction on optical bandwidth, to be realized. The limits to the size of such a network are calculated using the measured characteristics of a switch fabricated in the laboratory     

Nonblocking, repackable, and rearrangeable Clos networks: fifty years of the theory evolution

The article gives an overview of major theoretical issues associated with a switching network structure proposed by C. Clos (1953). The concepts of strict-sense and wide-sense nonblocking as well as repackable and rearrangeable networks are described, showing the development of major research areas. A taxonomy of Clos switching networks and some important results for the basic network structure are given and discussed. Other research issues are enumerated.     

Rearrangeably nonblocking 8×8 guided wave optical switch

The design and construction of a lithium niobate 8×8 optical switch with a rearrangeably nonblocking architecture is described. The design is compared with the more familiar strictly nonblocking architecture. The switch has 28 elements, a switching voltage of 26 V and a loss of 5.5 dB at 1.3 μm wavelength     

Extended baseline architecture for nonblocking photonic switching

A new switch architecture called extended baseline networks (EBN) is proposed for nonblocking photonic switching. This switch is a space-division multistage network using 2×2 optical switch elements which may be directional couplers fabricated on titanium diffused lithium niobate (Ti:LiNbO₃) substrates. A recursive definition for the proposed architecture is presented. Some properties including the number of switch elements required, blocking characteristics, number of crossovers, system attenuation, and signal-to-noise ratio (SNR) are derived and analyzed. Most of the characteristics are shown to be better than those of other well-known networks fabricated on single Ti:LiNbO₃ substrates