Burst-based scheduling algorithms for non-blocking ATM switcheswith multiple input queues

This letter quantitatively evaluates two alternative approaches to the scheduling of traffic streams in a high-speed ATM switch with multiple input queues. Specifically, we compare a previously proposed algorithm, called parallel iterative matching (PIM)-which is a cell-based scheduling algorithm-with our newly proposed algorithm-which is a burst-based variation of the PIM scheduling algorithm. Extensive simulation results demonstrate that burst-based PIM scheduling outperforms cell-based PIM scheduling under a variety of realistic parameters     

Analysis of nonblocking ATM switches with multiple input queues

An analytical model for the performance analysis of a multiple input queued asynchronous transfer mode (ATM) switch is presented. The interconnection network of the ATM switch is internally nonblocking and each input port maintains a separate queue of cells for each output port. The switch uses parallel iterative matching (PIM) to find the maximal matching between the input and output ports of the switch. A closed-form solution for the maximum throughput of the switch under saturated conditions is derived. It is found that the maximum throughput of the switch exceeds 99% with just four iterations of the PIM algorithm. Using the tagged input queue approach, an analytical model for evaluating the switch performance under an independent identically distributed Bernoulli traffic with the cell destinations uniformly distributed over all output ports is developed. The switch throughput, mean cell delay, and cell loss probability are computed from the analytical model. The accuracy of the analytical model is verified using simulation     

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     

An efficient ATM network switch scheduling

The problem of allocating network resources to application sessions backlogged at an individual switch has a great impact on the end-to-end delay and throughput guarantees offered by the network. There exists a class of algorithms based on weighted fair queueing (WFQ) for scheduling packets which are work-conserving and they guarantee fairness to the backlogged sessions. These algorithms also apply to ATM networks with a packet equal to a single cell or an ATM block (of fixed size). Bursts are groups of varying numbers of cells. We generalize WFQ to schedule bursts. Our motivation is to derive an adaptive algorithm which generalizes the (fixed size) packet level to a varying size packet level. The new algorithm enhances the performance of the switch service for many important applications. The proposed scheme maintains the work-conserving property, and also provides throughput and fairness guarantees. The worst-case delay bound is also given. We use simulation to study the performance characteristics of our algorithm. Our results demonstrate the efficiency of the new algorithm.     

A smart photonic ATM switch architecture with compression strategy

Generally, the limitations of optical delay line and link capacity limit the switching efficiency in the photonic asynchronous transfer mode (ATM) switch. Under the constraints, a smart photonic ATM switch designed for high-speed optical backbone network should have some fast switching strategies so that the congestion can be avoided or reduced. In this paper, we mill propose a novel smart photonic ATM switch architecture with a novel compression strategy. In the smart architecture, while more than two frames are destined for the same destination, the losers will be queued and compressed to reduce the degree of congestion. Therefore, not only the total switching time (TST) can be reduced but also the scarce buffer is able to store more incoming cells. To meet the high-speed switching performance, a simple and efficient compression decision algorithm (CDA) is proposed. The timing of employing compression strategy and the saturated performance of proposed strategy are analyzed. Simulation results show that compared to the conventional photonic ATM switch without compression strategy, the proposed strategy offers a much better performance in terms of queueing delay     

Rerouting network: a high-performance self-routing switch forB-ISDN

A high-performance self-routing switch is proposed for ATM (asynchronous transfer mode) switch systems. Switching performance is enhanced by a rerouting algorithm applied to a particular multistage interconnection algorithm. The interconnection algorithm offers many access points to the output and resolves output contention by layering buffers at each switching stage. The author analyzes switching performance and shows that this switch can be easily engineered to have high throughput and low cell loss probability by increasing the number of switching stages. The author also illustrates that the number of switching stages required for a given cell loss probability shows gradual growth with increasing switch size. Analysis shows that the proposed switch is robust even with respect to nonuniform traffic     

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     

Performance evaluation of multiple input-queued ATM switches withPIM scheduling under bursty traffic

In this letter, we analyze the performance of multiple input-queued asynchronous transfer mode (ATM) switches that use parallel iterative matching (PIM) for scheduling the transmission of head-of-line cells in the input queues. A queueing model of the switch is developed under independently, identically distributed, two-state Markov modulated Bernoulli processes bursty traffic. The underlying Markov chain of the queueing model is a quasi-birth-death (QBD) chain. The QBD chain is solved using an iterative computing method. Interesting performance metrics of the ATM switch such as the throughput, the mean cell delay, and the cell loss probability can be derived from the model. Numerical results from both the analytical model and simulation are presented, and the accuracy of the analysis is briefly discussed     

Dynamic bandwidth allocation scheme for multiple real‐time VBR videos over ATM networks

This paper considers VBR transmission of multiple real‐time videos over ATM networks. Multiple real‐time VBR video sources are multiplexed into an ATM switch to transmit cells into the network. Given the ATM switch capacity, the problem is to dynamically allocate the required channel bandwidth for each video source such that the encoder buffer occupancy is maintained at a target level. To solve the problem, we present a mathematical formulation and propose an algorithm for the bandwidth allocation. To allocate a suitable bandwidth at a given control period, QoS demand levels and traffic characteristics of the video sources are considered. The performance of the proposed scheme is examined in terms of the number of encoder rate controls required and the gap between the target and the current buffer occupancy at each control period. Numerical results are analyzed for different QoS environments as well as different levels of target buffer, ATM switch capacity, buffer size and leaky bucket token rate. This revised version was published online in June 2006 with corrections to the Cover Date.     

Discrete-Time Queuing Analysis of Dual-Plane ATM Switch with Synchronous Connection Control

In this paper, we propose an ATM switch with the rate more than gigabits per second to cope with future broadband service environments. The basic idea is to separate the connection control flow from the data information flow inside the switch. The proposed switch has a dual-plane switch matrix with the synchronous control algorithm. The queuing behaviors of the proposed switch are shown by the discrete-time queuing analysis. Numerical analyses are taken both in the non-blocking crossbar switch and the banyan switch with internal blocking. Results show that a proposed dual-plane 16×16 switch would have the acceptable performance with maximum throughput of about 95 percent.     

Reconfigurable ATM switch fabrics using traffic history

An ATM switch fabric which is capable of being reconfigured based on the statistics of a previous time period, is introduced. Taking under consideration the strong correlation between ports in a campus or LAN ATM switch, the proposed architecture exhibits improved performance. We prove the performance improvement, by applying data collected from a campus production ATM switch onto our proposed architecture     

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

Performance and buffering requirements of Internet protocols overATM ABR and UBR services

ATM networks are quickly being adopted as backbones over various parts of the Internet. This article studies the dynamics and performance of the TCP/IP protocol over the ABR and UBR services of ATM networks. Specifically the buffering requirements in the ATM switches as well as the ATM edge devices. It is shown that with a good switch algorithm, ABR pushes congestion to the edges of the ATM network while UBR leaves it inside the ATM portion. As a result, the switch ABR buffer requirement for zero-packet-loss high-throughput TCP transmission is a sublinear function of the number of TCP connections     

一种考察CCR的ABR业务二值法流量控制方案

 本文提出了一种考察CCR的有关ATM网络中ABR业务的流量控制方案EFCI(CCR)算法,具有二值法算法简单的特点,并能保证带宽分配的公平性,能有效地控制交换节点队列的长度,且该算法在拓扑结构较为复杂的网络中性能良好.     

Scalable multi-QoS IP+ATM switch router architecture

This article proposes a scalable multi-QoS IP+ATM switch router architecture. The proposed switch router is based on a core ATM switching system with multi-QoS capability. Forwarding engines and a routing engine are attached in front of the line cards of the ATM switching system. The FEs and RE are interconnected with each other via internal VCs. A novel longest matching algorithm is employed at the FE to achieve packet forwarding at wire-speed of OC-12c rate (622.08 Mb/s). Wire-speed unicast and multicast packet forwarding are performed using point-to-point and point-to-multipoint VCs in a unified way. Because FEs and RE are decoupled from the base ATM switching system, the full spectrum of ATM QoS capability is nicely applied for IP QoS control with a packet classification at the edge of the network. The core switching fabric is scalable from 40 to 160 Gb/s capacity (371 MPPS in terms of packet forwarding throughput). Feedback rate control is employed at each line card to eliminate congestion in the high-speed core switching fabric even with a small amount of buffer.     

A new analytical model for the dual-banyan ATM switch throughputcalculation

Dual-banyan is a buffered banyan asynchronous transfer mode (ATM) switch encompassing multiple input-queueing (bifurcated queueing) as its buffering strategy. This paper describes a new analytical model for a throughput evaluation of the dual-banyan switch under different traffic patterns. the model developed and presented enables the computation of buffer state probability and the switch normalized throughput by iterative calculations. The efficiency of the given model is verified through a comparison with simulation results     

A reconfigurable ATM switch fabric for fault tolerance and trafficbalancing

A large-scale asynchronous transfer mode (ATM) switch fabric that can be constructed with currently feasible technology is proposed. Based on analysis of the technology, it is found that module interconnection becomes the bottleneck for a large fast packet switch. Fault tolerance for the switch is achieved by dynamic reconfiguration of the module interconnection network. The design improves system reliability with relatively low hardware overhead. An abstract model of the replacement problem for the design is presented, and the problem is transformed into a well-known assignment problem. The maximum fault tolerance is found, and a fast replacement algorithm is given. The reconfiguration capability can also be used to ameliorate imbalanced traffic flows. The authors formulate this traffic flow assignment problem for the switch fabric and show that the problem is NP-hard. A simple heuristic algorithm is proposed, and an example is given     

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     

具有突发业务量成形的ATM复接器的性能分析

分析了综合业务环境下，具有突业务量成形的ＡＴＭ复接器的性能，提出了用间断贝努利过程可近似描述突发源经成形器后的输出过程。用改进的迭代算法，求出了ＡＴＭ复接器的信元丢失率和平均延迟。     

Design and analysis of a growable multicast ATM switch

This work designs and analyzes a cost-effective growable multicast asynchronous transfer mode (ATM) switch that has a new grouping network structure. The proposed switch can easily be enlarged by using more stages, since both cell routing and contention resolution are designed to distribute over the switch elements. Experimental results indicate that, by allowing valid cells to enter grouping networks from two directions (the west and north sides), the modular ATM switch proposed herein not only meets the ATM performance requirements for both unicasting and multicasting but also uses fewer switch elements and has a shorter cell delay than the ATM switch