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.     

Sharing memory in banyan-based ATM switches

We study a multistage ATM switch in which shared-memory switching elements are arranged in a banyan topology. By “shared-memory,” we mean that each switching element uses output queueing and shares its local cell buffer memory among all its output ports. We apply a buffer management technique called delayed pushout that was originally designed for multistage ATM switches with hierarchical topologies. Delayed pushout combines a pushout mechanism, for sharing memory efficiently among queues within the same switching element, and a backpressure mechanism, for sharing memory across switch stages. The backpressure component has a threshold to restrict the amount of sharing between stages. A synergy emerges when pushout, backpressure, and this threshold are all employed together. Using a computer simulation of the switch under bursty traffic, we study delayed pushout as well as several simpler pushout and backpressure schemes under a variety of traffic conditions. Of the five schemes we simulate, delayed pushout is the only one that performs well under all load conditions     

32×32 shared buffer type ATM switch VLSIs for B-ISDNs

A set of 0.8 μm CMOS VLSIs developed for shared buffer switches in asynchronous transfer mode (ATM) switching systems is described. A 32×32 unit switch consists of eight buffer memory VLSIs, two memory control VLSIs, and two commercially available first in first out (FIFO) memory LSIs. Using the VLSIs, the switch can be mounted on a printed board. To provide excellent traffic characteristics not only under random traffic conditions but also under burst traffic conditions, this switch has a 2-Mb shared buffer memory, the largest reported to date. which can save 4096 cells among 32 output ports. This switch has a priority control function to meet the different cell loss rate requirements and switching delay requirements of different service classes. A multicast function and a 600 Mb/s link switch architecture, which are suitable for ATM network systems connecting various media, and an expansion method using the 32×32 switching board to achieve large-scale switching systems such as 256×256 or 1024×1024 switches are discussed     

Design and implementation of Abacus switch: a scalable multicastATM switch

Describes a new architecture for a multicast ATM switch scalable from a few tens to a few thousands of input ports. The switch, called the Abacus switch, has a nonblocking switch fabric followed by small switch modules at the output ports. It has buffers at input and output ports. Cell replication, cell routing, output contention resolution, and cell addressing are all performed in a distributed way so that it can be scaled up to thousands of input and output ports. A novel algorithm has been proposed to resolve output port contention while achieving input buffers sharing, fairness among the input ports, and call splitting for multicasting. The channel-grouping mechanism is also adopted in the switch to reduce the hardware complexity and improve the switch's throughput, while the cell sequence integrity is preserved. The switch can also handle multiple priority traffic by routing cells according to their priority levels. The performance study of the Abacus switch in throughput, average cell delay, and cell loss rate is presented. A key ASIC chip for building the Abacus switch, called the ARC (ATM routing and concentration) chip, contains a two-dimensional array (32×32) of switch elements that are arranged in a crossbar structure. It provides the flexibility of configuring the chip into different group sizes to accommodate different ATM switch sizes. The ARC chip has been designed and fabricated using 0.8 μm CMOS technology and tested to operate correctly at 240 MHz     

Extended multicasting technique to allow multiple destinations peroutput port in ATM switches

When a multicast cell at an aynchronous transfer mode (ATM) switch requires distribution of its copies to the multiple users and/or outgoing sub-rate links served by one of its output ports, multiple cell copies at that output port are required. The conventional copy approach and broadcast approach of multicasting either cannot handle such situations or handles at the cost of switch performance. In this letter we propose a technique to enhance the ability of the copy and broadcast approaches to multicasting to enable them to handle such situations efficiently and economically     

Evaluation of pipelined dilated banyan switch architectures for ATMnetworks

In the pipeline banyan (PB), the reservation cycle in the control plane is made several times faster than payload transmission in data plane. This enables pipelining multiple banyans. It is observed that the ratio of throughput to switching delay (service rate) is relatively low in the PB due to the banyan. For this, we present a scalable pipelined asynchronous transfer mode (ATM) switch architecture employing a family of dilated banyan (DB) networks together with their complexity analysis and performance. A DB can be engineered between two extremes: (1) a low-cost banyan with internal and external conflicts, or (2) a high-cost conflict-free fully connected network with multiple outlets. Between the two extremes lies a family of DBs having different switching delays and throughputs. Increasing the dilation degree reduces path conflicts, which produces noticeable increase in service rate due to increase in throughput and decrease in path delay. Compared to PB, the pipelined dilated banyan (PDB) requires smaller number of data planes for the same throughput, or provides higher throughput for a given number of data planes. Simulation of PDB is carded out under uniform traffic and simulated ATM traffic. We study the switch performance while varying the load, buffer size, and number of data planes. To analyze the robustness of the switch, we show that performance is not degradable under ATM traffic with temporal and spatial burstiness generated using the on-off model. The PDB is scalable with respect to service rate and can be engineered with respect to: (1) cell loss rate; (2) hardware resources; (3) size of buffers; (4) switching delays; and (5) delay incurred to higher priority traffic. The PDB can deliver up to 3.5 times the service rate of the PB with only linear increase in hardware cost     

Performance of shared-memory switches under multicast burstytraffic

We study shared-memory switches under multicast bursty traffic and characterize the relation between their performance and the multicast distribution that defines the mix of multicast traffic arriving at the switches. We consider two schemes that have been used in practical realizations of these switches to replicate multicast cells: (1) replication-at-receiving (RAR), where multiple copies of a multicast cell are stored in the buffer and served independently, and (2) replication-at-sending (RAS), where a single instance of a multicast cell is stored in the buffer, and the cell is replicated as it is transmitted to the output ports. For each scheme, we study two configurations: (1) the shared-memory-only (SMO) configuration, where the bandwidth of the replication mechanism is sufficient to accommodate even the worst-case replication requirements, and (2) the shared-memory-with-replication-first-in-first-out (SM+RFIFO) configuration, where the bandwidth of the replication mechanism is lower than that required by the worst case, and thus an additional buffer is used in front of the shared memory to temporarily store cells while they are replicated. For all cases, using simulation, we find upper bounds for the buffer requirements to achieve a desired cell-loss rate. We show that these upper bounds are significantly larger than the buffer requirements under unicast traffic and are approached even for very small volumes of multicast traffic; thus, these upper bounds should be used in practice to size the buffers to achieve the desired performance under traffic with general multicast distributions. We also study shared-memory switches with output demultiplexers and characterize and compare the different multicasting schemes that are used in these switches     

Cell loss analysis and design trade-offs of nonblocking ATMswitches with nonuniform traffic

In practical ATM switch design, a proper dimensioning of buffer sizes and a cost effective selection of speed-up factor should be considered to guarantee a specified cell loss requirement for a given traffic. Although a larger speed-up factor provides better throughput for the switch, increasing the speed-up factor involves greater complexity and cost. Hence, it may not be cost effective to increase the speed-up factor for 100% throughput. Moreover, with a given buffer budget, an increase in the speed-up factor beyond a certain value only adds to the cell loss. The paper addresses design trade-offs existing between finite input/output buffer sizes and speed-up factor in a nonblocking ATM switch. Another important issue is the adverse effect on cell loss performance caused by nonuniform traffic (different traffic intensity and unevenly distributed routing). The paper analyzes cell loss performance of ATM switches with nonuniform traffic, and examines the effect of each nonuniform traffic parameter. The authors also provide an algorithm for effective buffer sharing that alleviates the performance degradation caused by traffic nonuniformity     

A shared-memory virtual channel queue for ATM broadband terminal adaptors

In order to take advantage of the low entry cost of the future public ATM (asynchronous transfer mode) network with shared facilities, it is highly desirable to interconnect different hosts and local area networks (LANs) to the ATM network. The interface between the computer hosts or LANs and the ATM network, commonly called a broadband terminal adaptor (BTA), provides the necessary format conversion for the data packets and the ATM cells. It is conceivable that multiple packets from different virtual channels are interleaved as they arrive at the receive-end BTA. The BTA must have a sufficiently large buffer, called a virtual channel queue (VCQ), to temporarily store the partially received packets. Once a complete packet has been received, it is forwarded to the host or LAN. Whenever the buffer fills with all incomplete packets, a packet must be discarded to make room for others. In this paper, we first study, through computer simulations, the buffer size requirement of a shared-memory VCQ for different numbers of virtual channels at various packet loss probabilities. We then present two different implementation architectures for the shared-memory VCQ, and compare their hardware complexity. The second architecture with linked-queue approach, adopted in our work, requires less buffer and has better scalability to accommodate a large number of virtual channels. Various possible error conditions, such as cell losses in the ATM network and the VCQ buffer overflow, are considered. Corresponding solutions are proposed and included in the VCQ designs.     

Scalable QoS-based IP multicast over label-switching wireless ATMnetworks

A Mobile IP multicast prototype that integrates a label-switching wireless asynchronous transfer mode, the mobile core-based multicast architecture, and an Internet multicast infrastructure is presented. MCOM creates multiple core-based layer 2 multicast trees that are independently established in member networks. They are interconnected via the Internet using layer 3 multicast routing. Gateways on the border of the Internet and wireless ATM networks convert ATM multicast traffic to suitable IP packets as well as converting from IP packets to ATM cells for MCOM. To solve the cell interleaving problem that results, ATM block transfer/immediate transmission capability is reasonably modified. Additionally, class-based block buffer management for ATM multicast connections is built into wireless ATM switches for soft quality of service control. Dynamic group management, multicast channel rerouting, and reliable multicasting are also studied in relation to existing Internet protocols like Mobile IP, Internet group management protocols, and multicast routing protocols     

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     

An approximate analysis of shared‐buffer channel‐grouped ATM switches under imbalanced traffic

Grouping output channels in a shared‐buffer ATM switch has shown to provide great saving in buffer space and better throughput under uniform traffic. However, uniform traffic does not represent a realistic view of traffic patterns in real systems. In this paper, we extend the queuing analysis of shared‐buffer channel‐grouped (SBCG) ATM switches under imbalanced traffic, as it better represent real‐life situations. The study focuses on the impact of the grouping factor and other key switch design parameters on the performance of such switches as compared to the unichannel allocation scheme in terms of cell loss probability, throughput, mean cell delay and buffer occupancy. Numerical results from both the analytical model and simulation are presented, and the accuracy of the analysis is presented. Copyright © 2005 John Wiley & Sons, Ltd.     

A high-speed-retry banyan switch architecture for giga-bit-rate BISDN networks

This paper proposes a high-speed ATM switch architecture for handling cell rates of several Gb/s in a broadband communication switching system or cross-connect system. The proposed switch architecture, named the high-speed-retry banyan switch, employs a bufferless banyan network between input and output buffers; a cell is repeatedly transmitted from an input buffer until it can be successfully transmitted to the desired output buffer. A simple cell-retransmission algorithm, is employed as is a ring-arbitration algorithm for cell conflict. They are suitable for FIFO type buffers and bufferless highspeed devices. Good traffic characteristics which are independent of switch size are achieved for an internal speed ratio of only four times the input line speed. A prototype system with the internal speed of 1·2 Gb/s is constructed in order to confirm the basic operation of the high-speed-retry banyan switch. The prototype system, even in its present state, could be used to realize a giga-bit-rate BISDN switching system.     

Performance of a large multicast ATM switch

In this paper, we present the design of a large self-routing multicast ATM switch. The switch consists of a sorting network followed by a 3-stage routing network. We first present a simple design of a large sorting network built using small sized shared memory that can be used as a building block for a large sorting network. Small sized shared memory is also used in the 3-stage routing network making the switch modular and easy to implement using current VLSI technology. As the network uses shared memory modules, multicasting functionality is easily built into the network. The performance of the proposed network is compared with an equivalent completely shared memory switch using computer simulations under bursty traffic model. The results show that the proposed network has better performance in terms of cell loss ratio than the completely shared memory switch under moderate to heavy traffic load (0.6 ≤ effective offered load ≤ 1.2). Furthermore, multicast cell delays are drastically improved. This revised version was published online in June 2006 with corrections to the Cover Date.     

The UniMIN switch architecture for large-scale ATM switches

A general expansion architecture is proposed that can be used in building large-scale switches using any type of asynchronous transfer mode (ATM) switch. The proposed universal multistage interconnection network (UniMIN) switch is composed of a buffered distribution network (DN) and a column of output switch modules (OSMs), which can be any type of ATM switch. ATM cells are routed to their destination using a two-level routing strategy. The DN provides each incoming cell with a self-routing path to the destined OSM, which is the switch module containing the destination output port. Further routing to the destined output port is performed by the destination OSM. Use of the channel grouping technique yields excellent delay/throughput performance in the DN, and the virtual FIFO concept is used for implementing the output buffers of the distribution module without internal speedup. We also propose a “fair virtual FIFO” to provide fairness between input links while preserving cell sequence. The distribution network is composed of one kind of distribution module which has the same size as the OSM, regardless of the overall switch size N. This gives good modular scalability in the UniMIN switch. Performance analysis for uniform traffic and hot-spot traffic shows that a negligible delay and cell loss ratio in the DN can be achieved with a small buffer size, and that DN yields robust performance even with hot-spot traffic. In addition, a fairness property of the proposed fair virtual FIFO is shown by a simulation study     

The split-switching network (SSN): A high-performance multicast ATM switch

This paper proposes a new high-performance multicast ATM switch architecture. The switch, called the split-switching network (SSN), is based on banyan networks. The SSN achieves multicasting in a way that is non-typical for banyan-based switches: copying and routeing of multicast cells are carried out simultaneously and within the same fabric. Thus, cells are copied only when needed as they traverse the switch towards the appropriate output ports. The SSN consists of successive spliting stages, and buffering is provided in front of each stage. The SSN is non-blocking with complexity of order Nlog2/2N for a switch of size N, and is characterized by distributed and parallel control. The throughput-delay performance of the SSN is shown to be similar to that of a non-blocking output-buffering switch under different mixtures of unicast/multicast traffic. In particular, the SSN achieves a maximum throughput of 100 per cent and the cell delay and delay variation remain small for loads just below the maximum throughput.     

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     

Large-scale ATM multistage switching network with shared buffermemory switches

The configuration of an asynchronous transfer mode (ATM) switch architecture using a shared buffer memory switch (SBMS) is discussed. The scaling factors of the ATM switching network under a condition of mixed applications, including a conventional mix and telecommunication with video, are analyzed. The use of the SBMS as the unit switch for a multistage switching network is examined. A prototype system and its performance evaluation and experimental data are presented. The data indicate excellent performance under a burst cell arrival condition. The buffer size of the SBMS can be reduced in comparison with that of an individual (nonshared) buffer memory switch. A configuration for a large-scale ATM switching network with multistage switches is proposed     

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 sliding-window packet switch: a new class of packet switch architecture with plural memory modules and decentralized control

Shared-memory based packet switches are known to provide the best possible throughput performance for bursty data traffic in high-speed packet networks and internets compared with other buffering strategies under conditions of identical memory resources deployed in the switch. However, scaling of shared-memory packet switches to a larger size has been restricted mainly due to the physical limitations imposed by the memory-access speed and the centralized control for switching functions in shared-memory switches. A new scalable architecture for a shared-memory packet switch, called the sliding-window (SW) switch, is proposed to overcome these limitations. The SW switch introduces a new class of switching architecture, where physically separate multiple memory modules are logically shared among all the ports of the switch, and the control is decentralized. The SW switch alleviates the bottleneck caused by the centralized control of switching functions in large shared-memory switches. Decentralized switching functions enable the SW switch to operate in a pipeline fashion to enhance scalability and switching capacity compared with that of previously known classes of shared-memory switch architecture.