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     

Throughput analysis, optimal buffer allocation, and trafficimbalance study of a generic nonblocking packet switch

A general model is presented to study the performance of a family of space-domain packet switches, implementing both input and output queuing and varying degrees of speedup. Based on this model, the impact of the speedup factor on the switch performance is analyzed. In particular, the maximum switch throughput, and the average system delay for any given degree of speedup are obtained. The results demonstrate that the switch can achieve 99% throughput with a modest speedup factor of four. Packet blocking probability for systems with finite buffers can also be derived from this model, and the impact of buffer allocation on blocking probability is investigated. Given a fixed buffer budget, this analysis obtains an optimal placement of buffers among input and output ports to minimize the blocking probability. The model is also extended to cover a nonhomogeneous system, where traffic intensity at each input varies and destination distribution is not uniform. Using this model, the effect of traffic imbalance on the maximum switch throughput is studied. It is seen that input imbalance has a more adverse effect on throughput than output imbalance     

输入/输出ATM交换机在突发性业务下的性能

本文详尽分析了内部无阻塞输入／输出排队反压型ＡＴＭ交换机在突发性业务下信元丢失、交换机最大吞吐量等性能。输入端口信元的到达过程是ＯＮ－ＯＦＦ突发流，且ＯＮ态以概率ｐ发送信元，ＯＮ－ＯＦＦ长度为Ｐａｒｅｔｏ分布的随机变量；属于同一突发流的信元输往同一个输出端口，不同突发流的信元等概率输往不同的输出端口；输入／输出缓冲器长度有限，交换机加速因子Ｓ任意。本文同时比较了突发长度为周期／几何分布下的交换机性能，其结论对实际设计一输入／输出排队反压型ＡＴＭ交换机具有一定参考意义。     

RPA: a flexible scheduling algorithm for input buffered switches

This paper presents and evaluates a quasi-optimal scheduling algorithm for input buffered cell-based switches, named reservation with preemption and acknowledgment (RPA). RPA is based on reservation rounds where the switch input ports indicate their most urgent data transfer needs, possibly overwriting less urgent requests by other input ports, and an acknowledgment round to allow input ports to determine what data they can actually transfer toward the desired switch output port. RPA must be executed during every cell time to determine which cells can be transferred during the following cell time. RPA is shown to be as simple as the simplest proposals of input queuing scheduling, efficient in the sense that no admissible traffic pattern was found under which RPA shows throughput limitations, and flexible, allowing the support of packet-mode operations and different traffic classes with either strict priority discipline or bandwidth guarantee requirements. The effectiveness of RPA is assessed with detailed simulations in uniform as well as unbalanced traffic conditions and its performance is compared with output queuing switches and the optimal maximum weighted matching (MWM) algorithm for input-buffered switches. A bound on the performance difference between the heuristic weight matching adopted in RPA and MWM is analytically computed     

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     

Performance analysis of a growable architecture for broad-bandpacket (ATM) switching

The performance of a growable architecture for broadband asynchronous transfer mode (ATM) switching consisting of a memoryless self-routing interconnect fabric and modest-size packet switch modules is examined. The cell loss probability is the focus because the architecture attains the best possible delay-throughput performance if the packet switch modules use output queuing. There are two sources of cell loss in the switch. First, cells are dropped if too many simultaneous arrivals are destined to a group of output ports. Second, because a simple, distributed path-assignment controller is used for speed and efficiency, cells are dropped when the controller cannot schedule a path through the switch. The authors compute an upper bound on arrivals, possibly including isochronous circuit connections, and show that both sources of cell loss can be made negligibly small     

Performance of a nonblocking space-division packet switch in a timevariant nonuniform traffic environment

The authors study the performance of a nonblocking space-division packet switch, given that the traffic intensities at the switch not only are nonuniform but also change as a function of time. A finite-state Markov chain is used as an underlying process to govern the time variation of traffic for the entire switch. The packet arrivals at each input form an independent Bernoulli process modulated by the underlying Markov chain. The output address of each packet is independently and randomly assigned with probability distributions, which are also modulated by the Markov chain. Provided that the traffic on each output is not dominated by individual inputs the service time of each output queue for sufficiently large switches can be characterized by an independent Markov modulated phase-type process. A matrix geometric solution for the resultant quasi-birth-death type queuing process is presented. The maximum throughput is obtained at the system saturation. The performance of the switch is numerically examined under various traffic conditions. A contention priority scheme to improve the switch performance is proposed     

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     

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.     

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     

Benes switching fabrics with O(N)-complexity internal backpressure

Multistage buffered switching fabrics are the most efficient method for scaling packet switches to very large numbers of ports. The Benes network is the lowest-cost switching fabric known to yield operation free of internal blocking. Backpressure inside a switching fabric can limit the use of expensive off-chip buffer memory to just virtual-output queues in front of the input stage. This article extends the known credit-based flow control (backpressure) architectures to the Benes network. To achieve this, we had to successfully combine per-flow backpressure, multipath routing (inverse multiplexing), and cell resequencing. We present a flow merging scheme that is needed to bring the cost of backpressure down to O(N) per switching element, and for which we have proved freedom from deadlock for a wide class of multipath cell distribution algorithms. Using a cell-time-accurate simulator, we verify operation free of internal blocking, evaluate various cell distribution and resequencing methods, compare performance to that of ideal output queuing, the iSLIP crossbar scheduling algorithm, and adaptive and randomized routing, and show that the delay of well-behaved flows remains unaffected by the presence of congested traffic to oversubscribed output ports.     

Queueing in high-performance packet switching

The authors study the performance of four different approaches for providing the queuing necessary to smooth fluctuations in packet arrivals to a high-performance packet switch. They are (1) input queuing, where a separate buffer is provided at each input to the switch; (2) input smoothing, where a frame of b packets is stored at each of the input line to the switch and simultaneously launched into a switch fabric of size Nb×Nb; (3) output queuing, where packets are queued in a separate first-in first-out (FIFO) buffer located at each output of the switch; and (4) completely shared buffering, where all queuing is done at the outputs and all buffers are completely shared among all the output lines. Input queues saturate at an offered load that depends on the service policy and the number of inputs N, but is approximately 0.586 with FIFO buffers when N is large. Output queuing and completely shared buffering both achieve the optimal throughput-delay performance for any packet switch. However, compared to output queuing, completely shared buffering requires less buffer memory at the expense of an increase in switch fabric size     

Delay performance of some scheduling strategies in an input queuingATM switch with multiclass bursty traffic

Considers an N×N nonblocking, space division, input queuing ATM cell switch, and a class of Markovian models for cell arrivals on each of its inputs. The traffic at each input comprises geometrically distributed bursts of cells, each burst destined for a particular output. The inputs differ in the burstiness of the offered traffic, with burstiness being characterized in terms of the average burst length. We analyze burst delays where some inputs receive traffic with low burstiness and others receive traffic with higher burstiness. Three policies for head-of-the-line contention resolution are studied: two static priority policies [shorter-expected-burst-length-first (SEBF), longer-expected-burst-length-first (LEBF)] and random selection (RS). Direct queuing analysis is used to obtain approximations for asymptotic high and low priority mean burst delays with the priority policies. Simulation is used for obtaining mean burst delays for finite N and for the random selection policy. As the traffic burstiness increases, the asymptotic analysis can serve as a good approximation only for large switch sizes. Qualitative performance comparisons based on the asymptotic analysis are, however, found to continue to hold for finite switch sizes. It is found that the SEBF policy yields the best delay performance over a wide range of loads, while RS lies in between. SEBF drastically reduces the delay of the less bursty traffic while only slightly increasing the delay of the more bursty traffic. LEBF causes severe degradation in the delay of less bursty traffic, while only marginally improving the delays of the more bursty traffic. RS can be an adequate compromise if there is no prior knowledge of input traffic burstiness     

An efficient contention resolution algorithm for input queuing atm cross-connect switches

This paper describes an efficient contention resolution algorithm and its distributed implementation for large capacity input queuing cross-connect switches, which will establish virtual paths in future broadband ATM networks. The algorithm dynamically allocates sending time to cells held in input queues when no contention is indicated in the designated output ports. An expression for the mean delay and the cell loss probability for random traffic are derived through an approximate analysis. Input cells are served on a first-come, first-served basis as conventional contention resolution algorithms whose throughput saturates at 58 per cent because of head of line blocking in input queues. The proposed algorithm achieves a maximum throughput of 76 per cent.     

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     

Derivation of the mean cell delay and cell loss probability formultiple input-queued switches

The multiple input-queued (MIQ) asynchronous transfer mode (ATM) switch has drawn much interest as a promising candidate for a high-speed and high-performance packet switch. The most conspicuous feature of the switch is that each input port is equipped with m(1⩽m⩽N) distinct queues, each for a group of output ports. Since the MIQ switch has multiple queues, an input can serve up to m cells in a time slot, leading to an enhanced performance. We derive the average queue length, mean cell delay, and cell loss probability for the MIQ switch in terms of the number of queues in an input port (m) and input load. The results include a special case of the single input-queued (SIQ) switch (m=1), which is analyzed by Hui et al. (1987)     

可行的基于CIOQ的并行分组交换结构

针对传统并行分组交换结构存在的平面可扩展性问题,提出一种可行的分布式并行分组交换PDPPS(practical distributed parallel packet switch)。在端口数为N和中间层平面数为K的情况下,PDPPS的复用器中只需要维护大小为NK的高速缓存,就能保证每条流按序输出。理论分析和仿真结果表明,PDPPS的性能优于使用OQ(output queuing)结构作为中间层平面的分布式并行分组交换结构VIQ PPS(virtual input queuing parallel packet switch),略微低于集中式PPS和IOQ PPS(in-order queuing parallel packet switch)。但相对于集中式PPS,PDPPS使用了更为通用且易于实现的CIOQ(combined input and output queuing)作为中间层平面;相对于IOQ PPS,PDPPS使用了分布式调度算法,从而消除了系统的通信开销,并且PDPPS极大地降低了所需的高速缓存数量。     

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.     

Performance Analysis of ATM Replicated Banyan Networks with External Input–Output Queueing

This paper develops an improved analysis of ATM switching architectures adopting a replicated banyan interconnection network provided with dedicated input and output queues, one per switch inlet and outlet. Two different plane selection policies are studied, random choice and alternate sharing, and two different operation modes are considered for the interaction between input and output queues, backpressure and output queue loss. These different internal operations are ranked in terms of traffic performance and the problem of optimal allocation of a given buffer budget between input and output queues is addressed. The analysis, which assumes that the network is loaded by uniform traffic, always provides conservative results whereas known models are less accurate and give optimistic traffic results. Packet delay and loss probability performance is evaluated for the ATM switch and its accuracy is assessed using computer simulation also in comparison with results given by previous models.     

带输入缓冲的ATM交换机的吞吐量分析

在ＦＣＦＳ（先来先服务）准则下,ＡＴＭ（异步传递模式）交换机的吞吐量为０．５９。文章提出了三种提高ＡＴＭ交换机的吞吐量的方案：方案Ａ（输入扩展方案）、方案Ｂ（窗口选择方案）和方案Ｃ（信元舍充方案）。笔者认为,对于方案Ｃ,所有信元都属于一个猝发的相关业务,被分配到同一个输出端口,而且每一个业务源都是ＩＢＰ（中断贝努利业务进程）模型,方案Ｃ的结果表明：目标的相关性不影响吞吐量,当所有的输入业务平衡时,