Input queueing multicast ATM packet switch with two priorityclasses using a priority scheme with a window policy

To achieve a high performance multicast switch with multiple priority classes, we have proposed a new N×N input queuing technique which uses a novel priority scheme and a high-performance arbitration algorithm. The scheme uses a priority without iteration (POI) method and a pipeline arbitration. Simulation results show that this scheme improves the performance of delay critical services and it can give almost the same performance as that which uses a priority with iteration (PWI) method     

Tandem-crosspoint ATM switch with input and output buffers

This letter proposes a high-speed input and output buffering asynchronous transfer mode (ATM) switch, named the tandem-crosspoint (TDXP) switch, The TDXP switch consists of multiple crossbar switch planes, which are connected in tandem at every crosspoint. The TDXP switch does not increase the internal line speed in eliminating head-of-line (HOL) blocking. In addition, since the TDXP switch employs a simple cell reading algorithm at the input buffer in order to retain the cell sequence, the TDXP switch does not require the cell sequences to be rebuilt at output buffers using time stamps, as is required by a parallel switch. It is shown that the TDXP switch can eliminate the HOL blocking effectively and achieve high throughput     

Matching output queueing with a combined input/output-queued switch

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N×N switch, a “speedup” of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies     

Matching output queueing with a multiple input/output-queued switch

We have previously proposed an efficient switch architecture called multiple input/output-queued (MIOQ) switch and showed that the MIOQ switch can match the performance of an output-queued switch statistically. In this paper, we prove theoretically that the MIOQ switch can match the output queueing exactly , not statistically, with no speedup of any component. More specifically, we show that the MIOQ switch with two parallel switches (which we call a parallel MIOQ (PMIOQ) switch in this paper) can provide exact emulation of an output-queued switch with a broad class of service scheduling algorithms including FIFO, weighted fair queueing (WFQ) and strict priority queueing regardless of incoming traffic pattern and switch size. To do that, we first propose the stable strategic alliance (SSA) algorithm that can produce a stable many-to-many assignment, and prove its finite, stable and deterministic properties. Next, we apply the SSA algorithm to the scheduling of a PMIOQ switch with two parallel switches, and show that the stability condition of the SSA algorithm guarantees for the PMIOQ switch to emulate an output-queued switch exactly. To avoid possible conflicts in a parallel switch, each input-output pair matched by the SSA algorithm must be mapped to one of two crossbar switches. For this mapping, we also propose a simple algorithm that requires at most 2N steps for all matched input-output pairs. In addition, to relieve the implementation burden of N input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of N physically-separate memories. In conclusion, we demonstrate that the MIOQ switch requires two crossbar switches in parallel and two physical memories at each input and output to emulate an output-queued switch with no speedup of any component.     

Analysis of input and output queueing for nonblocking ATM switches

A switch model for ATM networks is analyzed. Its interconnection network is internally nonblocking and is provided with dedicated input and output queues, one per switch inlet and one per switch outlet. The switch operates with an internal speed-up: more than one packet per slot can be transferred from the head-of-line positions of the input queues to each output queue by the interconnection network. Two different operation modes are considered for the interaction between input and output queues: backpressure mode and queue loss mode. The analytical model developed for the evaluation of the switch performance under random traffic assumes an infinite size for the switch, arbitrary values for input and output queue size, as well as for the speed-up factor. Switch throughput, packet delay and loss performance are evaluated and the analytical model accuracy is assessed using computer simulation results     

Design implementation of ATM switch with input priority anddistributed output buffers

A switch architecture for ATM is described which uses a simple priority module to resolve input contention and a distributed design to permit transfer of input cells to the first free output buffer. The switch has been synthesised using VHDL software and a target generic library and can operate at speeds >400 Mbit/s     

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.<>     

Maximum throughput of an input queueing packet switch with twopriority classes

The maximum throughput of an N×N nonblocking packet switch with input queues and two priority classes is analyzed. Packets are of fixed length and the switch operation is slotted. Packets of both priority classes are queued when waiting for service. High-priority packets preempt low-priority ones and move ahead of all low-priority packets waiting in the queue. A new method of analysis is employed. The calculated results of the maximum throughput obtained are close to the simulation results     

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     

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.     

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     

ATM switch with distributed queue windowing scheme

The input queueing switch can be enhanced using a non-first come-first-service (non-FCFS) discipline like window scheme. However, large window sizes are not feasible in centralised contention resolution algorithms due to the increased internal bit rate. Based on the distributed queue concept, a new window scheme for the ATM switch is proposed where the window size can be easily extended. The proposed scheme does not require that the scheduling hardware be speeded up in proportion to the window size, which is essential in the conventional window scheme     

Ultrafast photonic ATM switch with optical output buffers

An ultrafast photonic asynchronous transfer mode (ATM) (ULPHA) switch based on a time-division broadcast-and-select network with optical output buffers is presented. The ULPHA switch has an ultra-high throughput and excellent traffic characteristics, since it utilizes ultrashort optical pulses for cell signals and avoids cell contentions by novel optical output buffers. Feasibility studies show that an 80×80 ULPHA switch with 1-Gb/s input/output is possible by applying the present technology, and that more than 1 Tb/s is possible by making a three-stage network using such switches. As an experimental demonstration, 4-bit 40-Gb/s optical cells were generated and certain cells were selected at an output on a self-routing basis. With its high throughput and excellent traffic considerations, the ULPHA switch is a strong candidate for a future large-capacity optical switching node     

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.     

Broadcast-and-select photonic ATM switch with frequency divisionmultiplexed output buffers

A photonic ATM switch has been developed with frequency division multiplexed (FDM) output buffers. The switch has a broadcast-and-select network architecture using fixed-frequency-channel transmitters and a passive star configuration. Although it has a simple structure, it can provide either broadcast or multicast switching. The output buffers, which resolve cell contentions, are comprised of fiber delay lines that can easily handle signal speed of over 10 Gb/s. Experimental switching of two-multiplexed 10 Gb/s cells with a 2.8-dB power penalty demonstrated high-speed switching     

Performance of an input-queued ATM switch with even/odd switchingplanes

A switch architecture is proposed for alleviating the HOL blocking by employing even/odd dual FIFO queues at each input and even/odd dual switching planes dedicated to each even/odd queue. Under random traffic, it gives 76.4% throughput without output expansion and 100% with output expansion r=2, with the same amount of crosspoints as for the ordinary output expansion scheme     

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     

Performance trade-offs in input/output buffer design for a non-blocking space-division packet switch

Performance trade-offs in buffer architecture design for a space-division packet switching system is studied. As described in Figure 1, the system is constructed by a non-blocking switch fabric and input/output buffers. The capacity of the non-blocking switch fabric is defined by the maximum number of packets, denoted by m, which can be simultaneously routed from multiple inputs to each output. The buffer size at each input is considered to be finite, equal to K. The emphasis here is placed on the input packet loss probability for systems constructed by different ms and Ks. From the performance point of view, we conclude:

• (a) choosing m = 3 or 4 is sufficient to exploit the maximum utilization of a non-blocking switch fabric
• (b) introducing input buffers of moderate size K significantly reduces the packet loss probability.

     

Performance evaluation of a high-speed ATM switch with multiplecommon memories

We consider a common-memory (CM) type N × N ATM switch, where CM block consists of K (K ⩾ N) separated submemories. We propose an address assignment algorithm to avoid input/output contentions so that we can have the read/write speed of submemories as low as the interface (input/output) port speed. Taking a replication-at-sending approach to multicast, we pursue memory efficiency and maximum throughput. We develop an analytical model to evaluate the system in terms of cell loss ratio and average delay time. In the analysis, we take into account two loss factors causing losses of incoming cells: (1) the failure of scheduling to avoid the input/output contentions and (2) overflow in the CM block. The first factor is dominating and can be significantly reduced by increasing K. From our analytical results compared with simulations, it is observed that we can take K ≈ 3N as a guide of system design     

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.