Accurate modelling of the queueing behaviour of shared buffer ATM switches

A model for the analysis of multistage switches based on shared buffer switching for Asynchronous Transfer Mode (ATM) networks is developed, and the results are compared with the simulation. Switches constructed from shared buffer switches do not suffer from the head of line blocking which is the common problem in simple input buffering. The analysis models the state of the entire switch and extends the model introduced by Turner to global flow control with backpressure mechanism. It is shown that buffer utilization is better and throughput improves significantly compared with the same switch using local flow control policy. Copyright © 1999 John Wiley & Sons, Ltd.     

Pushout with virtual thresholds buffer management scheme in a shared buffer ATM switch

In this paper we investigate the performance metrics of buffer management schemes. In general, the selective pushout (SP) scheme can support very low loss probability of the high‐priority cells, but it may cause unfairness of buffer allocation among different output queues and high overall cell loss probability. In order to fit the dynamic required performance metrics of ATM switches, a novel buffer management scheme called pushout with virtual thresholds (PVT) is proposed. In the PVT scheme, each output queue is guaranteed to increase in length until its virtual threshold (VT). Simulation results show the PVT can dynamically achieve the fairness and low overall cell loss probability or very low loss probability of the high priority cells by adequately adjusting the VT. Specially, when the VT = 0, the PVT control can be viewed as the SP control. Copyright © 2003 John Wiley & Sons, Ltd.     

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     

Analysis of a discrete-time queue with integrated bursty inputs in ATM networks

In this paper, we carry out an exact analysis of a discrete-time queue system with a number of independent Markov modulated inputs in ATM networks, using a generating function approach. We assume that the queueing system has an infinite buffer with M servers. The cell arrival process is characterized by a number of independent Markov modulated geometrical batch arrival processes. We first obtain the generating function of the queue-size distribution at steady-state in vector form, then derive an expression for the average queue-size in terms of the unknown boundary probabilities. To obtain those unknown probabilities, we use the technique proposed in Reference 1. This involves decomposing the system characteristic function to evaluate the roots and solving a set of linear equations. One of the contributions of this paper is presented in Lemma 1, which characterizes the property of the underlying eigenvalues. For one special case of at least M-1 cell arrivals during one slot at one Markov state and of at least M arrivals at all other states, the determination of the unknowns is straightforward. If every Markov modulated arrival process can be further decomposed into a number of i.i.d. two-state, or three-state, or even four-state Markov modulated arrival processes, then each root can be obtained separately using an iterative algorithm. Numerical results are presented to validate the proposed traffic models against actual traffic measurements.     

A prototype broadcast-and-select photonic ATM switch with a WDMoutput buffer

A rack-mounted prototype of a broadcast-and-select (B and S) photonic ATM switch is fabricated. This switch has an optical output buffer utilizing wavelength division multiplexed (WDM) signals. The WDM technology solves. The cell-collision problem in a broadcast-and-select network and leads to a simple network architecture and the broadcast/multicast function. The prototype can handle 10-Gb/s nonreturn-to-zero (NRZ) coded cells and 5-Gb/s Manchester-coded cells and has a switch size of four. In this prototype, the level and timing design are key issues. Cell-by-cell level fluctuation is overcome by minimizing the loss difference between the optical paths and adopting a differential receiver capable of auto-thresholding. The temperature control of delay lines was successful in maintaining the phase synchronization. Using these techniques, we are able to provide a WDM highway with a bit error rate of less than 10^-12. Fundamental photonic ATM switching functions, such as optical buffering and fast wavelength-channel selection, are achieved. We show our experimental results and demonstrate the high performance and stable operation of a photonic ATM switch for use in high-speed optical switching systems as an interconnect switch for a modular ATM switch and an ATM cross-connect switch     

Improved queueing analysis of shared buffer switching networks

The authors describe several methods for analyzing the queueing behavior of switching networks with flow control and shared buffer switches. They compare the various methods on the basis of accuracy and computation speed, where the performance metric of most concern is the maximum throughput. The best of the methods accurately predicts throughput for multistage networks constructed from large switches (⩾8 ports)     

Shared buffer ATM switch with doubly linked lists

The Shared buffer memory switch (SBMS) architecture was originally proposed as an effective approach to implement ATM switch fabrics. However, in this paper we find that if an error occurs in the address chain memory of one linked list which stores the address of the next cell in the shared buffer memory, the erroneous situation will spread over all linked lists in the SBMS in a short time. In order to prevent the fault spread phenomenon, we propose two doubly linked list based architectures to combat address chain failure; these are referred to as the Flush and In-Seq schemes. The first scheme flushes the remaining cells in the faulty queue but collect their addresses for later usage. The second scheme outputs the remaining cells in their correct sequence. From our simulation, if the error injection rate is low, the performance of the In-Seq scheme experiences slight degradation compared with the errorfree situation.     

A queueing model for analysis of a bursty multiple-access communication channel

A bursty multiple-access communication channel with constrained total system bandwidth, total average power, and message error rates is considered. A stochastic model for the number of active transmitters is developed. Four schemes for the dynamic assignment of power and coding rate to active transmitters are considered and compared under the expected burst system time criterion. Necessary and sufficient conditions for system operation are given, and all schemes are shown to have the same saturation behavior. Adaptive coding rates are shown to enjoy substantial advantages over fixed coding; adaptive power assignment does not offer advantages over fixed power assignment.     

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     

Analysis of a discrete-time single-server queue with bursty inputsfor traffic control in ATM networks

The performance of an asynchronous transfer mode (ATM) network subject to admission control and traffic smoothing is analyzed. Basically, an ATM switch is modeled as a discrete-time single-server queuing system in which a new call joins existing calls. Cell arrivals from a new call are assumed to follow a general distribution. It is also assumed that aggregated arrivals of cells from existing calls form batch arrivals with a general batch size distribution and a geometric distribution of the interarrival times between batches. Both finite- and infinite-buffer cases are considered. An exact analysis yields the waiting time distribution and cell loss probability for a new call and for existing calls. Numerical examples are given to show how the network performance depends on the statistics of a new call (burstiness, time that a call stays in an active or inactive state, etc.) and to demonstrate the effectiveness of admission control and traffic smoothing     

Banyan multipath self-routing ATM switches with shared buffer typeswitch elements

The asynchronous transfer mode (ATM) has been selected as the multiplexing and switching technique for use in the public broadband ISDN (B-ISDN). We propose a large-scale ATM switch architecture in which a banyan multipath self-routing network is combined advantageously with a shared buffer type switch element. The proposed banyan space-division concept yields a simple architecture having the potential to accommodate easily the growth of switch size. Since the interconnection network between switch modules or between switch elements has a twofold banyan architecture, expansion in crosspoints or interconnections with the increase of switch size can be lessened. The multipath self-routing concept makes the switch performance better and leads to an efficient realization of a switch element on a single chip as the fundamental building block of a large-size switch. We analyze the required capacity for queuing buffers in the switching network. The multipath approach inevitably creates information sequence disturbances. Therefore, we also analyze the out-of-sequence phenomenon of a banyan multipath switching system. To satisfy the sequence integrity requirement for ATM, a simple approach is proposed for the multipath switch by using a spacing controller. In addition, we quantify the improvement of out-of-sequence performance under the spacing controller scheme     

Physical performance limits for shared buffer ATM switches

Performance studies, linking ATM switch capabilities to physical limitations imposed by integrated circuit technology, have been scarce. This paper explores trends in circuit capabilities, and makes projections toward the 0.25-μm technologies that will be available to all switch designers in the year 2000. The limits imposed by circuit technology are applied to shared buffer ATM switches. We determine requirements and physical limits for buffer capacity, buffer throughput, chip I/O throughput, and power dissipation. As a result, we are able to project chip counts, aggregate switch throughputs, and switch dimensions. As well, performance capabilities of single-chip shared buffer switches are estimated. A single-chip shared buffer switch implemented in 0.25-μm technology will be capable of an aggregate throughput of 1.3 Tb/s, will accomplish almost arbitrarily low cell loss rates for bursty traffic, and may be integrated together with translation tables supporting hundreds of connections per port     

Efficient buffer sharing in shared memory ATM systems with spacepriority traffic

In this letter we study the problem of the optimal design of buffer management policies within the class of pushout and expelling policies for a shared memory asynchronous transfer mode (ATM) switch or demultiplexer fed by traffic containing two different space priorities. A numerical study of the optimal policies for small buffer sizes is used to help design heuristics applicable to large buffer sizes. Simulation studies for large buffer systems are then presented     

A discrete-time queueing network model of a hub-based OBS architecture

We propose and analyze a novel discrete-time queueing network model of a zero loss hub-based Optical Burst Switched (OBS) architecture, consisting of multiple input edge nodes and one destination edge node. The arrival process of bursts is slotted with bulk arrivals as generated by a Time and Burst-Length based burst aggregation algorithm. The queueing network is analyzed by decomposition. We obtain the average end-to-end delay of a burst in the queueing network as well as queueing delays at individual nodes. Our model provides a tight upper bound as shown by comparing the analytical data to simulation results.     

A queueing model for an ATM rate control scheme

Many applications in telecommunications engineering lead to highly degenerate partitioned Markov chains of QBD type. In this paper, we study a traffic shaping scheme which is based on a generalization of the bucket method. The arrival process is modeled by a discrete Markovian arrival process. For this model, a detailed mathematical analysis leads to special algorithms involving matrices of lower order. The characteristics of the model are discussed from this viewpoint. Some performance measurements are derived and numerical examples are shown to demonstrate the effectiveness of the rate control scheme.This research was supported in part by Grant No. DDM-8915235 from the National Science Foundation.     

Performance of two-stage shared fiber delay line optical packet switch under bursty traffic

Packet contention is a major issue in an optical packet switching network. It is not a trivial task to resolve contention due to lack of optical RAM technology. This article proposes a two-stage shared fiber delay line (FDL) optical packet switch for contention resolution. In this article, shared FDLs are used to buffer optical packets, in which a pool of buffer memory is shared among all switch output ports. Most of the existing optical buffering schemes are output-based which require a huge number of FDLs as well as a larger switch size that incur extra implementation cost. However, a shared buffering approach is considered in this article in order to reduce implementation cost. In this article, FDLs are implemented in two stages using an extremely simple auxiliary switch. The proposed switch architecture leads to more efficient use of buffer space. The superiority of the proposed switch architecture has been established by means of extensive simulations. The performance of the proposed switch is investigated under bursty traffic. Simulation result shows that the proposed switch can achieve satisfactory performance at the price of a reasonable amount of FDLs. Moreover, the significance of the proposed switch is confirmed by simulation.     

A one-chip scalable 8*8 ATM switch LSI employing shared bufferarchitecture

The authors present a one-chip scalable 8×8 shared buffer switch LSI which includes a 256-cell buffer. Speedup, flow control, and input slot rotation functions are provided in order to interconnect LSIs for scaling-up without degrading cell loss rates. Computer simulations show that these functions bring a satisfactory result and can make the cell loss- rate for a Clos three-stage network superior to that for the output buffer switch which includes the same amount of buffer space. A 0.8 μm BiCMOS process is employed for this LSI. The total number of transistors is one million. This LSI has already been fabricated     

A queueing problem with random memory arrivals and heterogeneous servers

This paper studies the steady state behaviour in discrete time of a limited space queueing problem with random memory arrivals wherein service is accomplished through S-heterogeneous parallel channels. The arrivals at two consecutive time marks depend upon a random variable which takes values one and zero with probabilities p and q respectively according to whether the arrivals at two consecutive time marks are correlated or uncorrelated. The explicit probabilities for the number of units in the system have been worked out. Some special cases of interest have also been derived.     

A new analytical model for the CQ switch throughput calculation under the bursty traffic

In this paper we propose a new analytical iterative method for the throughput calculation of the Crosspoint Queued (CQ) switch with a random scheduling algorithm under the bursty traffic model. This method is verified by comparing it with the simulation results, which shows a very good match. To the authors’ knowledge, this is the first analytical method for the throughput calculation of such a switch for the bursty traffic model.     

Input and output queueing ATM switch architecture with spatial and temporal slot reservation control

A viable ATM switch architecture exploiting both input and output queueing on a space division switch is proposed. This architecture features both input and output ports that are divided into several groups, and an efficient contention resolution algorithm is developed. The performance study indicates that a group size of eight is sufficient to achieve 90% efficiency.<>