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     

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.     

Optimal cost/performance design of ATM switches

This paper proposes a methodology for performing an evaluation and optimization of the cost of an ATM switching architecture under performance constraints given in terms of virtual connection blocking probability. An analysis of blocking networks is developed, and combined with known results concerning nonblocking networks, provides a theoretical model which relates traffic characteristics, network topology and blocking probability in a multirate/multiservice broadband environment. An analysis of the characteristics determining the cost of a generic ATM switch implementation follows. The model is oriented to optimize both the topological parameters and the speed advantage, with respect to the main cost factors of VLSI-based switching networks i.e., components count and complexity, interconnection costs     

ATM与异种计算机网络互连

在对比了ＡＴＭ网络结构与ＯＳＩ／ＲＭ网络模型异同的基础上，阐述了ＡＴＭ与异种计算机网络互连的基本原理，分析陋有协议对ＡＴＭ网络互连的支持，讨论了新一代ＩＰｖ６及路由器、ＡＴＭ交换机结合技术对ＡＴＭ互连网的推动。     

Omega network-based ATM switch with neural network-controlledbypass queueing and multiplexing

Multistage interconnection networks (MINs) have long been studied for use in switching networks. Since they have a unique path between source and destination and the intermediate nodes of the paths are shared, internal blocking can cause very poor throughput. This paper proposes a high throughput ATM switch consisting of an Omega network with a new form of input queues called bypass queues. We also improve the switch throughput by partitioning the Input buffers into disjoint buffer sets and multiplexing several sets of nonblocking cells within a time slot, assuming that the routing switch operates only a couple of times faster than the transmission rate. A neural network model is presented as a controller for cell scheduling and multiplexing in the switch. Our simulation results under uniform traffic show that the proposed approach achieves almost 100% of potential switch throughput     

PERFORMANCE EVALUATION OF NON-BLOCKING ATM SWITCHES UNDER VARIOUS TRAFFIC AND BUFFERING SCHEMES

Broadband integrated services digital networks (BISDN) are designed to offer a variety of services with bit rates ranging from several kb/s (e.g. teleactions) to hundreds of Mb/s (e.g. HDTV), and in some cases approaching Gb/s (e.g. in interconnections of high-speed LANs). A multiplicity of rates and the burstiness of traffic sources lead naturally to systems based on the fast packet switching (or asynchronous transfer mode) concept. The requirements of data buffering and high-speed processing of packet headers have resulted in a plethora of proposals for ATM switching nodes and an equal number of ways for evaluating them. In particular, the class of non-blocking architectures of ATM switches has received the most attention from the research community. This paper reviews this class of architecture with emphasis on contention resolution methods and communication traffic performance. The contention resolution methods are divided into four categories: input buffering, output buffering, shared buffering, and hybrid buffering. The communication traffic characteristics are divided into two categories: uniform traffic and bursty traffic.     

Wide-sense non-blocking multicast ATM switches

Non-blocking multicast ATM switches can simplify the call admission control process and increase the utilisation level of external links. The condition for wide-sense non-blocking multicast ATM switches is derived and the routing algorithm is proposed. The required number of middle switches for the wide-sense non-blocking multicast switch is significantly less than that of the strictly non-blocking multicast switch     

FAULT-TOLERANT DESIGN OF BATCHER–BANYAN CLASS ATM SWITCHES

Many proposed packet switching systems for high-speed networks have employed the Batcher–banyan fabric due to its modular structure, self-routeing functionality, and distributed conflict-resolving mechanism. In this paper, we present a systematic fault-tolerant design for the Batcher–banyan class of switches. Our first concern is the development of an on-line error detection mechanism which is the prerequisite of any effective fault tolerant operation. Based on the technique developed by Davis, we propose a general fault-testing technique and verify it for a variety of unique-path self-routeing networks. Furthermore, we extend this method to Batcher sorting networks and construct a fault-tolerant Batcher sorter. Lastly, after contemplating the technique constraints and system performance, we deploy the above techniques into different levels of the Batcher–banyan networks and achieve a fault-tolerant version of the StarBurst switch, a member of the Batcher–banyan class of switches.     

On the non-blocking conditions of self-routeing multistage interconnection networks

This paper studies the non-blocking conditions of a generic N × N multistage interconnection network, such as an omega network or an n-cube network, in which only one path connects any inlet to each outlet and different I/O paths can share interstage links. It is widely known that any of these networks is non-blocking for a compact and monotone pattern of k ≤ N I/O paths. Recently it has become very important to show the network non-blocking property for permutation sets, wider than the compact and monotone, which are usually encountered in broadband ATM networks. By using a new approach based on the concept of distance between I/O paths, we show here that these networks are non-blocking for a set of I/O paths obtained by shifting cyclically the inlets of a compact and monotone pattern of I/O paths by an arbitrary number of steps.     

ATM switches—basic architectures and their performance

The prospect of a broadband ISDN based on the ATM principle has stimulated the development of new, high-performance switching node architectures. In this paper different options for the switching networks used in such a node will be discussed in some detail. First, some generic architectures for the individual switching elements will be presented including the aspects of buffering and collision resolution, followed by a short classification of different types of switching networks and some performance figures for delta networks, a class of multi-stage, single-path interconnection networks. In the last section, the sensitivity of the performance results with respect to the traffic assumptions will be discussed.     

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.     

Design of a non-blocking shared-memory copy network for ATM

The design of a copy network is presented for use in an ATM (asynchronous transfer mode) switch supporting BISDN (broadband integrated services digital network) traffic. Inherent traffic characteristics of BISDN services require ATM switches to handle bursty traffic with multicast connections. In typical ATM switch designs a copy network is used to replicate multicast cells before being forwarded to a point-to-point routeing network. In such designs, a single multicast cell enters the switch and is replicated once for each multicast connection. Each copy is forwarded to the routeing network with a unique destination address and is routed to the appropriate output port. Non-blocking copy networks permit multiple cells to be multicasted at once, up to the number of outputs of the copy network. Another critical feature of ATM switch design is the location of buffers for the temporary storage of transmitted cells. Buffering is required when multiple cells require a common switch resource for transmission. Typically, one cell is granted the resource and is transmitted while the remaining cells are buffered. Current switch designs associate discrete buffers with individual switch resources. Discrete buffering is not efficient for bursty traffic as traffic bursts can overflow individual switch buffers and result in dropped cells, while other buffers are under-used. A new non-blocking copy network is presented in this paper with a shared-memory input buffer. Blocked cells from any switch input are stored in a single shared input buffer. The copy network consists of three banyan networks and shared-memory queues. The design is scalable for large numbers of inputs due to low hardware complexity, O (N log₂ N), and distributed operation and control. It is shown in a simulation study that a switch incorporating the shared-memory copy network has increased throughput and lower buffer requirements to maintain low packet loss probability when compared to a switch with a discrete buffer copy network.     

Implementation of multipoint connections in an ATM switching network

This paper presents the problems in the implementation of multipoint connections at switching level using the example of an ATM switching network. By choosing the proper routeing mechanism and the appropriate architecture of the switching element, a switching network can gradually be adapted to an increasing share of multipoint traffic. The first section describes the problems with the handling of multipoint connections within a multiple stage connection oriented switching network. In particular this refers to the routeing of the cells through the switching network. Several alternatives on this issue are discussed. Both, the selected approach based on a differentiated self-routeing mechanism and the corresponding cell format are introduced. In the second part of this article several switch architectures are compared in respect of their multipoint capability. It is demonstrated that at present the most promising solution are switching elements based on the principle of central buffering. A single chip solution using this concept is employed in the presented switching network.     

模块化结构的ATM交换节点的性能分析

模块化结构是形成大容量ＡＴＭ交换节点的最有效手段，本文提出一种分析模块化结构的ＡＴＭ交换节点性能的新方法，该方法通过引入虚队列考虑了相邻模块间的相关性，与计算机模拟相比，分析结果在整个负载变化范围内都有很高的准确性，方法适用于任意大小模块并采用输出排队和以Ｂａｎｙａｎ网为互连网的ＡＴＭ交换节点的性能分析。     

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     

Strictly Non-Blocking Conditions for the Central-Stage Buffered Clos-Network

We consider using the Clos-network to scale high performance routers, especially the space-memory-space (SMS) packet switches. In circuit switching, the Clos-network is responsible for pure connections and the internal links are the only blocking sources. In packet switching, however, the buffers cause additional blockings. In this letter, we first propose a scalable packet switch architecture that we call the central-stage buffered Clos-network (CBC). Then, we analyze the memory requirements for the CBC to be strictly non-blocking, especially for emulating an output-queuing packet switch. Results show that even with the additional memory blockings the CBC still inherits advantages from the Clos-network, e.g., modular design and cost efficiency.     

异步传递模式的协议原理及其关键技术的研究进展

异步传递模式（ATM）一致被看成宽带数据骨干网的基础传输技术。本文首先简要介绍ATM协议的基本结构和ATM信元交换的基本原理,并说明ATM网络的资源管理方案,然后具体分析ATM信元交换及其与IP网结合所面临的一些关键技术问题,并讨论了解决这些问题所采用的方法及其研究进展,最后总结了今后有关ATM技术应用急需解决的一些问题。     

Preventing internal and external conflicts in an input buffering reverse baseline ATM switch

When two or more packets that are destined to the same output of an ATM switch arrive at different inputs, buffers at inputs or outputs are used to queue all but one of these packets so that external conflict is prevented. Although input buffering ATM switches are more economical and simpler than output buffering ATM switches, significant loss of throughput can occur in input buffering ATM switches due to head‐of‐line (HOL) blocking when first‐in–first‐out (FIFO) queueing is employed. In order to avoid both external conflict and alleviate HOL blocking in non‐blocking ATM switches, some window‐based contention resolution algorithms were proposed in the literature. In this paper, we propose a window‐based contention resolution algorithm for a blocking ATM switch based on reverse baseline network with content addressable FIFO (CAFIFO) input buffers. The proposed algorithm prevents not only external conflicts but also internal conflicts, in addition to alleviating HOL blocking. This algorithm was obtained by adapting the ring reservation algorithm used on non‐blocking ATM switches to a reverse baseline network. The fact that a non‐blocking network is replaced by a log₂ N‐stage reverse baseline network yields a significant economy in implementation. We have conducted extensive simulations to evaluate the performance of reverse baseline network using the proposed window‐based contention resolution algorithm. Simulation results show that the throughput of reverse baseline network can be as good as the throughput of non‐blocking switches if the window depth of input buffers is made sufficiently large. Copyright © 2000 John Wiley & Sons, Ltd.     

A generalized framework for analyzing time-space switched opticalnetworks

The advances in photonic switching have paved the way for realizing all-optical time switched networks. The current technology of wavelength division multiplexing (WDM) offers bandwidth granularity that matches peak electronic transmission speed by dividing the fiber bandwidth into multiple wavelengths. However, the bandwidth of a single wavelength is too large for certain traffic. Time division multiplexing (TDM) allows multiple traffic streams to share the bandwidth of a wavelength efficiently. While introducing wavelength converters and time slot interchangers to improve network blocking performance, it is often of interest to know the incremental benefits offered by every additional stage of switching. As all-optical networks in the future are expected to employ heterogeneous switching architectures, it is necessary to have a generalized network model that allows the study of such networks under a unified framework. A network model, called the trunk switched network (TSN), is proposed to facilitate the modeling and analysis of such networks. An analytical model for evaluating the blocking performance of a class of TSNs is also developed. With the proposed framework, it is shown that a significant performance improvement can be obtained with a time-space switch with no wavelength conversion in multiwavelength TDM switched networks. The framework is also extended to analyze the blocking performance of multicast tree establishment in optical networks. To the best of our knowledge, this is the first work that provides an analytical model for evaluating the blocking performance for tree establishment in an optical network. The analytical model allows a comparison between the performance of various multicast tree construction algorithms and the effects of different switch architectures     

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.