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.     

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.     

A growable packet (ATM) switch architecture: design principles andapplication

The problem of designing a large high-performance, broadband packet of ATM (asynchronous transfer mode) switch is discussed. Ways to construct arbitrarily large switches out of modest-size packet switches without sacrificing overall delay/throughput performance are presented. A growable switch architecture is presented that is based on three key principles: a generalized knockout principle exploits the statistical behaviour of packet arrivals and thereby reduces the interconnect complexity, output queuing yields the best possible delay/throughput performance, and distributed intelligence in routing packets through the interconnect fabric eliminates internal path conflicts. Features of the architecture include the guarantee of first-in-first-out packet sequence, broadcast and multicast capabilities, and compatibility with variable-length packets, which avoids the need for packet-size standardization. As a broadband ISDN example, a 2048×2048 configuration with building blocks of 42×16 packet switch modules and 128×128 interconnect modules, both of which fall within existing hardware capabilities, is presented     

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     

Nonblocking architectures for ATM switching

General models for a class of nonblocking architectures of asynchronous transfer mode (ATM) switches are described. Hardware aspects are discussed to show the implementation feasibility of the proposed switch architectures by means of the current technology. Performance issues are studied to point out the traffic bottlenecks of the different structures. It is shown that the classification of queueing is the main concept that enables the classification of nonblocking ATM switches. Three main packet queueing strategies can be adopted in the switching fabric: input queueing, shared queueing, and output queueing. Switch architectures adopting only one of these strategies are described. The ways in which two strategies can be jointly adopted in a switching fabric to result in the mixed queueing strategies input-output queueing, input-shared queueing, and shared-output queueing are also discussed     

Output-buffer switch architecture for asynchronous transfer mode

This paper proposes a new asynchronous transfer mode (ATM) switch architecture for the broadband ISDN. The ATOM switch ATM output-buffer modular switch has a multi-stage network structure, and is highly modular to facilitate capacity expansion. The ATOM switch element is of the output-buffer type with a time-division multiplexed bus and FIFO buffer for each outgoing line. Bit-slice techniques are used to implement the high-speed time-division bus and buffer memories. The output buffer switch has the advantages of no throughput degradation since internal contention is eliminated, and a simple control structure for providing priority and multi-point connections. This paper also deals with switching delay and buffer overflow probabilities for mixed (bursty and non-bursty) traffic.     

Reservation-based contention resolution mechanism forBatcher-Banyan packet switches

The authors introduce a new method, called ring reservation, to design high-capacity packet switches. Input buffering is used with output port reservations to eliminate packet collisions. They describe a 32×32 prototype packet switch, built as a part of a broadband ISDN prototype, which has a per-port capacity of 30-55 Mbit/s     

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     

Fast ping‐pong arbitration for input–output queued packet switches

Input–output queued switches have been widely considered as the most feasible solution for large capacity packet switches and IP routers. In this paper, we propose a ping‐pong arbitration scheme (PPA) for output contention resolution in input–output queued switches. The challenge is to develop a high speed and cost‐effective arbitration scheme in order to maximize the switch throughput and delay performance for supporting multimedia services with various quality‐of‐service (QoS) requirements. The basic idea is to divide the inputs into groups and apply arbitration recursively. Our recursive arbiter is hierarchically structured, consisting of multiple small‐size arbiters at each layer. The arbitration time of an n‐input switch is proportional to log₄?n/2? when we group every two inputs or every two input groups at each layer. We present a 256×256 terabit crossbar multicast packet switch using the PPA. The design shows that our scheme can reduce the arbitration time of the 256×256 switch to 11 gates delay, demonstrating the arbitration is no longer the bottleneck limiting the switch capacity. The priority handling in arbitration is also addressed. Copyright © 2001 John Wiley & Sons, Ltd.     

Performance study of an input and output queueing ATM switch with a window scheme and a speed constraint

In this paper, we study the performance of an input and output queueing switch with a window scheme and a speed constraint. The performance of a non-blocking ATM switch can usually be improved by increasing the switching speed. Also, the performance of a switch can be improved using a window scheme by relaxing the first-in-firstout (FIFO) queueing discipline in the input queue. Thus, one can expect that a combined scheme of windowing and a speed constraint can improve further the performance of the packet switch. Here, we analyze the maximum throughput of the input and output queueing switch with a speed constraint combined with windowing, and show that it is possible to obtain high throughput with a small increment of speed-up and window size. For analysis, we model the HOL queueing system as a virtual queueing system. By analyzing the dynamics of HOL packets in this virtual queueing model, we obtain the service probability of the HOL server as a function of output contention capabilities. Using the result, we apply the flow conservation relation to this model and obtain the maximum throughput. The analytical results are verified by simulation.     

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     

均匀业务下反压型输入/输出排队ATM交换机的性能分析

本文利用矩阵几何分析法分析了内部无阻塞输入/输出排队反压型ATM交换机在均匀贝努利输入下的信元丢失、信元延时及吞吐量等性能指标。本文结论对实际设计一反压型输入/输出排队分组交换机具有一定参考意义。     

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     

Approximate analysis of a multi-plane and multi-phase Banyan ATMswitch

An approximate analysis of a multi-plane and multi-phase Banyan ATM switch with both input and output buffering is presented. The approach gives a reasonable estimate of throughput and input queueing delay, and can be refined to give more accurate results     

The bypass queue in fast packet switching

The telecommunications networks of the future are likely to be packet switched networks consisting of wide bandwidth optical fiber transmission media, and large, highly parallel, self-routing switches. Recent considerations of switch architectures have focused on internally nonblocking networks with packet buffering at the switch outputs. These have optimal throughput and delay performance. The author considers a switch architecture consisting of parallel plans of low-speed internally blocking switch networks, in conjunction with input and output buffering. This architecture is desirable from the viewpoint of modularity and hardware cost, especially for large switches. Although this architecture is suboptimal, the throughput shortfall may be overcome by adding extra switch planes. A form of input queuing called bypass queuing can improve the throughput of the switch and thereby reduce the number of switch planes required. An input port controller is described which distributes packets to all switch planes according to the bypass policy, while preserving packet order for virtual circuits. Some simulation results for switch throughput are presented     

SCOQ: a fast packet switch with shared concentration and outputqueueing

A space-division, nonblocking packet switch with data concentration and output buffering is proposed. The performance of the switch is evaluated with respect to packet loss probability, the first and second moments of the equilibrium queue length and waiting time, throughput, and buffer overflow probability. Numerical results indicate that the switch exhibits very good delay-throughput performance over a wide range of input traffic. The switch compares favorably with some previously proposed switches in terms of fewer basic building elements used to attain the same degree of output buffering     

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.     

Head of the line arbitration of packet switches with combined input and output queueing

A single-stage non-blocking N × N packet switch is considered. Data units may be stored before switching at the inputs as well as after switching at the outputs. Some output buffering capacity is intended to achieve high throughput, whereas an additional input buffering capacity keeps losses due to input-buffer overflow reasonably low. The paper studies the impact on performance of the head of the line arbitration policy, i.e. the sequence which is used to transfer data units from the heads of input queues to each output queue. The investigation is based on two performance measures: the average delay and the maximum throughput of the switch. Closed-form expressions for the FCFS, LCFS and the ROS policies are obtained. The result of the average delay with the FCFS policy leads to a lower bound, and that with the LCFS policy to an upper bound for the average delay, corresponding to an arbitrary symmetric policy which does not use information related to the state of the input queues. It is shown that the maximum throughput does not depend on the head of the line arbitration policy. It depends only on the output-buffer size and the packet-size distribution. The cases of fixed and exponentially distributed packet sizes are studied. The effects of asymmetric policies which result in different behaviours of some of the input queues is also considered.     

An experimental ATM switch for BISDN studies

This paper describes the architecture, functionality and performance of an experimental ATM switch being developed at the Telecom Australia Research Laboratories as part of its investigations into the broadband ISDN. The proposed switch architecture consists of parallel omega networks preceded by a Batcher bitonic sorting network. The switching fabric has no internal cell buffering. Cell buffering is provided only on the switch outputs for cells simultaneously contending for the same output port. The switch fabric and cell buffers include mechanisms for providing prioritized servicing of queued cells and prioritized discarding of cells based on priority fields contained within the cell header. Components of the switch are currently being implemented in 2 μm CMOS VLSI.     

The performance analysis and implementation of an input accessscheme in a high-speed packet switch

The performance analysis of an input access scheme in a high-speed packet switch for broadband ISDN is presented. In this switch, each input port maintains a separate queue for each of the outputs, thus n ² input queues in an (n×n) switch. Using synchronous operation, at most one packet per input and output will be transferred in any slot. We derive lower and upper bounds for the throughput which show close to optimal performance. The bounds are very tight and approach to unity for switch sizes on the order of a hundred under any traffic load, which is a significant result by itself. Then the mean packet delay is derived and its variance is bounded. A neural network implementation of this input access scheme is given. The energy function of the network, its optimized parameters and the connection matrix are determined. Simulation results of the neural network fall between the theoretical throughput bounds