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     

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.     

Hierarchical path hunt in a broadband multirate circuit switchingfabric

A circuit switching fabric that switches narrowband (DS0), wideband (N×DS0, N×VT), and broadband (STS-N) signals embedded in SONET streams is studied. Based on the Clos (1953) strictly nonblocking principle, the fabric is strictly nonblocking if all path hunts are performed at the basic-rate (DS0 in our case) level. On the other hand, a hierarchical path hunt can speed up the path hunt process for a high bit-rate call, though the fabric will then lose its nonblocking property. We study several hierarchical path hunt algorithms and investigate how the hierarchy impacts the blocking probability. We also study the performance impact resulting from doing broadcast/multicast in a multirate circuit switching fabric. Our results provide insights into how hierarchical path hunts should be designed in a broadband multirate circuit switching fabric     

A survey of multistage interconnection networks in fast packet switches

This paper comprises a broad survey of multistage interconnection networks (MINs), which are incorporated into the underlying fabric of fast packet switches for use in broadband ATM networks. A general classification of MINs based on network functionality and blocking characteristics in the context of fast packet switches is presented in order to emphasize the fundamental principles which differentiate the network architectures. For each class of network, important theoretical results are given and the underlying design principles are explained with the best known explicit examples. Special emphasis is given to the implementation complexities and control strategies of individual approaches.     

Switching integrated broadband services by sort-banyan networks

Substantial attention has recently been given to the implementation of sort-banyan networks for switching asynchronous transfer mode (ATM) transmission links in a BISDN (broadband integrated service digital network) network. The author gives a three-dimensional view of the theory and implementation of switching, as well as variations of the basic scheme. ATM switches are classified as blocking versus nonblocking, unicast versus multicast, and input queued versus output queued. Sorting networks structured by a three-dimensional interconnection topology are studied. A sorting network, when coupled with a banyan routing network structured in three dimensions, becomes a self-routing and nonblocking switching network. This three-dimensional topology allows CMOS VLSI implementations of the subnetworks and interconnection of these subnetworks at a speed of 150 Mb/s and beyond. The sorting mechanism can also be used for output conflict resolution, subsequently making the switch suitable for ATM switching. Recent enhancements, which provide features such as parallelism, trunk grouping, and modularity, are also described. These features enhance the throughput/delay performance, provide better fault and synchronization tolerance, and enable more economical growth for switch size     

Priority queueing strategies and buffer allocation protocols fortraffic control at an ATM integrated broadband switching system

The problem of furnishing an asynchronous transfer mode (ATM) based broadband-ISDN (B-ISDN) with two bearer services supporting different grades of transfer quality is addressed. The focus is on priority bandwidth and buffer management in the ATM communications nodes (switches, multiplexers or concentrators, and expanders) in the context of a multichannel network architecture. Detailed queueing analyses and simulations and results are provided to evaluate the differentiation between traffic classes that can be achieved by different strategies. The implementation complexity of the different schemes is discussed. Various priority queueing strategies characterized mainly by different degrees of resource sharing and a general system model for performance evaluation are introduced. Performance comparisons and design tradeoffs are addressed     

Performance evaluation of input and output queueing techniques inATM switching systems

Modeling alternatives for a fast packet switching system are analyzed. A nonblocking switch fabric that runs at the same speed as the input/output links is considered. The performance of the considered approaches are derived by theoretical analysis and computer simulations. Performance comparison between input queueing approaches with different selection policies are presented. Novel input and output queueing techniques are also proposed. In particular it is shown that, depending on the implementation, the input queueing approach studied in this paper achieves the same performance as the optimum (output) queueing alternative, without resorting to a faster packet switch fabric     

Survey of switching techniques in high-speed networks and their performance

One of the most promising approaches for high speed networks for integrated service applications is fast packet switching, or ATM (asynchronous transfer mode). ATM can be characterized by very high speed transmission links and simple, hard-wired protocols within a network. To match the transmission speed of the network links, and to minimize the overhead due to the processing of network protocols, the switching of cells is done in hardware switching fabrics in ATM networks. A number of designs have been proposed for implementing ATM switches. Although many differences exist among the proposals, the vast majority of them are based on self-routeing multistage interconnection networks. This is because of the desirable features of multi-stage interconnection networks such as self-routeing capability and suitability for VLSI implementation. Existing ATM switch architectures can be classified into two major classes: blocking switches, where blockings of cells may occur within a switch when more than one cell contends for the same internal link, and non-blocking switches, where no internal blocking occurs. A large number of techniques have also been proposed to improve the performance of blocking and non-blocking switches. In this paper, we present an extensive survey of the existing proposals for ATM switch architectures, focusing on their performance issues.     

Burst switching-an update

Burst switching research in dispersed control and integrated switching is described. Burst transport is integrated in that voice and data are switched through the same switching fabric and transmission media. Burst switching is compared to and distinguished from fast packet, fast circuit, and ATM (asynchronous transfer mode) switching. Misunderstandings about burst transport that have appeared in the literature are corrected, to wit: burst does not immediately clip in case of channel contention; burst switches voice and data in the same way; and a burst switch interfaces naturally to other types of switches. Round-trip delay performance is calculated to be less than 5 ms. The current status of the burst project is described     

NN based ATM cell scheduling with queue length-based priorityscheme

The asynchronous transfer mode (ATM) is the choice of transport mode for broadband integrated service digital networks (B-ISDNs). We propose a window-based contention resolution algorithm to achieve higher throughput for nonblocking switches in ATM environments. In a nonblocking switch with input queues, significant loss of throughput can occur due to head-of-line (HOL) blocking when first-in first-out (FIFO) queueing is employed. To resolve this problem, we employ bypass queueing and present a cell scheduling algorithm which maximizes the switch throughput. We also employ a queue length based priority scheme to reduce the cell delay variations and cell loss probabilities. With the employed priority scheme, the variance of cell delay is also significantly reduced under nonuniform traffic, resulting in lower cell loss rates (CLRs) at a given buffer size. As the cell scheduling controller, we propose a neural network (NN) model which uses a high degree of parallelism. Due to higher switch throughput achieved with our cell scheduling, the cell loss probabilities and the buffer sizes necessary to guarantee a given CLR become smaller than those of other approaches based on sequential input window scheduling or output queueing     

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     

Design and performance of Multinet switch: a multistage ATM switcharchitecture with partially shared buffers

A new ATM switch architecture is presented. Our proposed Multinet switch is a self-routing multistage switch with partially shared internal buffers capable of achieving 100% throughput under uniform traffic. Although it provides incoming ATM cells with multiple paths, the cell sequence is maintained throughout the switch fabric thus eliminating the out-of-order cell sequence problem. Cells contending for the same output addresses are buffered internally according to a partially shared queueing discipline. In a partially shared queueing scheme, buffers are partially shared to accommodate bursty traffic and to limit the performance degradation that may occur in a completely shared system where a small number of calls may hog the entire buffer space unfairly. Although the hardware complexity in terms of number of crosspoints is similar to that of input queueing switches, the Multinet switch has throughput and delay performance similar to output queueing switches     

A multistage ATM switch with interstage buffers

Asynchronous transfer mode (ATM) is the transport technique for the broadband ISDN recommended by CCITT (I.121). Many switches have been proposed to accommodate the ATM that requires fast packet switching capability.^1-8 The proposed switches for the broadband ISDN can be classified as being of input queueing or output queueing type. Those of the input queueing type have a throughput performance which is approximately 58 per cent that of the output queueing type. However, output queueing networks require larger amounts of hardware than input queueing networks. In this paper, we propose a new multistage switch with internal buffering that approaches a maximum throughput of 100 per cent as the buffering is increased. The switch is capable of broadcasting and self-routeing. It consists of two switching planes which consist of packet processors, 2 x 2 switching elements, distributors and buffers located between stages and in the output ports. The internal data rate of the proposed switch is the same as that of the arriving information stream. In this sense, the switch does not require speed-up. The switch has log₂ N stages that forward packets in a store-and-forward fashion, thus incurring a latency of log₂ N time periods. Performance analysis shows that the additional delay is small.     

Clos lives on in optical packet switching

While the technological evolution since C. Clos's seminal article (see Bell Sys. Tech. J., vol.32, p.406-24, 1953) on multistage switch architectures has been huge, his work and ideas still live on. We discuss node architectures for optical packet switching and show how the multistage approach proposed by Clos can be adopted to solve scalability issues and construct switches with large port counts. As in the old days, the driving factors behind the introduction of multistage concepts also include economic issues: compared to a single-stage architecture, the number of components to realize the switching fabric is reduced.     

Comparison of ATM switching architectures

Clear examination of work currently done within CCITT indicates the importance of a broadband telecommunication network. As this network should be capable of integrating all services in an efficient way—in order to reduce cost—the asynchronous transfer mode (ATM) was selected by CCITT as the target transfer mode for implementing the broadband integrated services digital network (BISDN). This selection implies that the switching nodes in the BISDN network are capable of supporting this high-speed packet and connection-orientated technique. Within the literature different switching node architectures based upon ATM have been proposed. All of these architectures should meet the high-speed and high-throughput requirements so as to cope with the delay and jitter performance objectives. In a first step this paper describes alternative switching techniques for the basic building block (switching element) of a switching node. A common model architecture of the switching element is drafted. A classification of switching elements described in the literature is derived and the influence on the complexity and performance is weighted. In a second step the switching node architecture is further elaborated according to the control and flexibility requirements. Core (switching) and edge (switching related) functions are listed, and possible functional partitionings are discussed. Finally, these ATM switching architectures are compared according to a background frame consisting of several straightforward comparison points such as the buffering strategy, the internal routeing method, the switching overhead, the connection-orientated or connectionless operation, etc.     

A 622-Mb/s 8×8 ATM switch chip set with shared multibufferarchitecture

An asynchronous transfer mode (ATM) switch chip set, which employs a shared multibuffer architecture, and its control method are described. This switch architecture features multiple-buffer memories located between two crosspoint switches. By controlling the input-side crosspoint switch so as to equalize the number of stored ATM cells in each buffer memory, these buffer memories can be treated as a single large shared buffer memory. Thus, buffers are used efficiently and the cell loss ratio is reduced to a minimum. Furthermore, no multiplexing or demultiplexing is required to store and restore the ATM cells by virtue of parallel access to the buffer memories via the crosspoint switches. Access time for the buffer memory is thus greatly reduced. This feature enables high-speed switch operation. A three-VLSI chip set using 0.8-μm BiCMOS process technology has been developed. Four aligner LSIs, nine bit-sliced buffer-switch LSIs, and one control LSI are combined to create a 622-Mb/s 8×8 ATM switching system that operates at 78 MHz. In the switch fabric, 155-Mb/s ATM cells can also be switched on the 622-Mb/s port using time-division multiplexing     

Asymptotic Performance Limits of Switches With Buffered Crossbars Supporting Multicast Traffic

Input queued (IQ) switches exploiting buffered crossbars (CICQ switches) are widely considered very promising architectures that outperform IQ switches with bufferless switching fabrics both in terms of architectural scalability and performance. Indeed the problem of scheduling packets for transfer through the switching fabric is significantly simplified by the presence of internal buffers in the crossbar, which makes possible the adoption of efficient, simple and fully distributed scheduling algorithms. This paper studies the throughput performance of CICQ switches supporting multicast traffic, showing that, similarly to IQ architectures, also CICQ switches with arbitrarily large number of ports may suffer of significant throughput degradation under ldquopathologicalrdquo multicast traffic patterns. Despite the asymptotic nature of these results, the authors believe that they can contribute to a deeper understanding of the behavior of CICQ architectures supporting multicast traffic.     

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     

Architecture design for ATM statistical multiplexers

Both high-speed packet switches and statistical multiplexers are critical elements in the ATM (asynchronous transfer mode) network. Many switch architectures have been proposed and some of them have been built, but relatively fewer statistical multiplexer architectures have been investigated to date. It has been considered that multiplexers are a special kind of switches which can be implemented with similar approaches. The main function of a statistical multiplexer, however, is to concentrate traffic from a number of input ports to a comparatively smaller number of output ports; ‘switching’ in the sense that a cell must be delivered to a specific output port is often not required. This implies that the channel grouping design principle, in which more than one path is available for each virtual circuit connection, can be applied in the multiplexer. We show that this technique reduces the required buffer memory and increases the system performance significantly. The performances of three general approaches for implementing an ATM statistical multiplexer are studied through simulations with various bursty traffic assumptions. Based on the best performing approach (sharing output channels and buffers), we propose two architecture designs to implement a scalable statistical multiplexer that is modularly decomposed into many smaller multiplexers by using a novel grouping network.     

The single-queue switch: a building block for switches withprogrammable scheduling

We introduce a new approach to ATM switching. We propose an ATM switch architecture which uses only a single shift-register-type buffering element to store and queue cells, and within the same (physical) queue, switches the cells by organizing them in logical queues destined for different output lines. The buffer is also a sequencer which allows flexible ordering of the cells in each logical queue to achieve any appropriate scheduling algorithm. This switch is proposed for use as the building block of large-stale multistage ATM switches because of low hardware complexity and flexibility in providing (per-VC) scheduling among the cells. The switch can also be used as scheduler/controller for RAM-based switches. The single-queue switch implements output queueing and performs full buffer sharing. The hardware complexity is low. The number of input and output lines can vary independently without affecting the switch core. The size of the buffering space can be increased simply by cascading the buffering elements