Providing QoS guarantees to unicast and multicast flows in multistage packet switches

Multistage packet switches that feature a limited amount of buffers in the switching fabric and distribute most of their buffering capacity over the port cards have recently gained popularity due to their scalability properties and flexibility in supporting quality-of-service (QoS) guarantees. In such switches, the replication of multicast packets typically occurs in-the fabric. This approach minimizes the amount of resources needed to sustain the internal expansion in traffic volume due to multicasting, but also exposes multicast flows to head-of-line (HOL) blocking in the ingress port cards. The distributed scheduler that arbitrates the transfer of packets through the switch and the flow-control scheme that restricts access to the fabric buffers have the most critical role in safeguarding the QoS guarantees of multicast flows against HOL blocking. We add minimal overhead to a well-known QoS framework for multistage packet switches to define the generalized distributed multilayered scheduler (G-DMS), which achieves full support of QoS guarantees for both unicast and multicast flows. The main novelty of the G-DMS is in the mechanism that regulates access to the fabric buffers, which combines selective backpressure with the capability of dropping copies of multicast packets that violate the negotiated profiles of the corresponding flows.     

Scheduling of multicast traffic in high-capacity packet switches

Switches with input buffers are scalable due to their simplicity. In these switches, the port that sources a multicast session might easily get congested as it becomes more popular. We propose that destination ports should forward copies of multicast packets to other destination ports in a specified order. In this way, the multicast traffic load is evenly distributed over the switch ports. Packets are scheduled according to the weighted sequential greedy algorithm.     

Throughput analysis for multicast switches with multiple input queues

This letter analyzes the saturated throughput for multicast switches with multiple input queues per input port. Under the assumptions of a Poisson uniform traffic model and random packet scheduling policy, we derive the multicast switch saturated throughput under different fanouts. To verify the analysis, extensive simulations are conducted with different switch sizes and fanouts. It is shown that the theoretical analysis and the simulation results have a discrepancy less than 1.9%. Results from this letter can be used as a guidance to design the optimal queuing for multicast switches.     

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.     

Multicast traffic in input-queued switches: optimal scheduling and maximum throughput

The paper studies input-queued packet switches loaded with both unicast and multicast traffic. The packet switch architecture is assumed to comprise a switching fabric with multicast (and broadcast) capabilities, operating in a synchronous slotted fashion. Fixed-size data units, called cells, are transferred from each switch input to any set of outputs in one time slot, according to the decisions of the switch scheduler, that identifies at each time slot a set of nonconflicting cells, i.e., cells neither coming from the same input, nor directed to the same output. First, multicast traffic admissibility conditions are discussed, and a simple counterexample is presented, showing intrinsic performance losses of input-queued with respect to output-queued switch architectures. Second, the optimal scheduling discipline to transfer multicast packets from inputs to outputs is defined. This discipline is rather complex, requires a queuing architecture that probably is not implementable, and does not guarantee in-sequence delivery of data. However, from the definition of the optimal multicast scheduling discipline, the formal characterization of the sustainable multicast traffic region naturally follows. Then, several theorems showing intrinsic performance losses of input-queued with respect to output-queued switch architectures are proved. In particular, we prove that, when using per multicast flow FIFO queueing architectures, the internal speedup that guarantees 100% throughput under admissible traffic grows with the number of switch ports.     

An analytical approach to the performance evaluation of the balanced gamma switch under multicast traffic

This paper presents the performance evaluation of a new cell‐based multicast switch for broadband communications. Using distributed control and a modular design, the balanced gamma (BG) switch features high performance for unicast, multicast and combined traffic under both random and bursty conditions. Although it has buffers on input and output ports, the multicast BG switch follows predominantly an output‐buffered architecture. The performance is evaluated under uniform and non‐uniform traffic conditions in terms of cell loss ratio and cell delay. An analytical model is presented to analyse the performance of the multicast BG switch under multicast random traffic and used to verify simulation results. The delay performance under multicast bursty traffic is compared with those from an ideal pure output‐buffered multicast switch to demonstrate how close its performance is to that of the ideal but impractical switch. Performance comparisons with other published switches are also studied through simulation for non‐uniform and bursty traffic. It is shown that the multicast BG switch achieves a performance close to that of the ideal switch while keeping hardware complexity reasonable. Copyright © 2006 John Wiley & Sons, Ltd.     

ATM交换的最佳缓存器分配

研究具有输入和输出队的ＡＴＭ交换的缓存器分配策略。文中首先建立了描述交换网络的模型，然后分析了在有限缓存容量下在输入队和输出队中分组的丢失率。分析表明总的丢失率是输入队和输出队容量的复杂函数，因而在总的缓存容量一定的情况下，必存在使丢失率最小的缓存分配方法。最后用数值结果说明了最佳的分配策略。     

A high-performance input access scheme for ATM multicast switching

In this paper, we propose an input access scheme for input-queued ATM multicast switches, achieving high system throughput, low packet delay and packet loss probability. Multicast and unicast packets of each input port are separately queued. Multicast queues take priority over the unicast queues, and both types of queues are fairly served in a cyclic-priority access discipline. In particular, each unicast queue is handled on a window-service basis, and each multicast packet is switched in a one-shot scheduling manner. To evaluate the performance of the access scheme, we propose an approximate analysis based on a simplified cyclic-priority model for anN×N finite-buffer multicast switch possessing Bernoulli multicast and unicast arrivals, with window-service (for unicasting) and one-shot scheduling (for multicasting) both taken into account. Finally, we show simulation results to demonstrate the accuracy of the approximate analysis and the superiority of the scheme over existing schemes with respect to normalized system throughput, mean packet delay, and packet loss probability.An earlier version of this paper appeared in IEEE ICC'96.     

Dynamic buffer management using per‐queue thresholds

Shared buffer switches consist of a memory pool completely shared among output ports of a switch. Shared buffer switches achieve low packet loss performance as buffer space is allocated in a flexible manner. However, this type of buffered switches suffers from high packet losses when the input traffic is imbalanced and bursty. Heavily loaded output ports dominate the usage of shared memory and lightly loaded ports cannot have access to these buffers. To regulate the lengths of very active queues and avoid performance degradations, threshold‐based dynamic buffer management policy, decay function threshold, is proposed in this paper. Decay function threshold is a per‐queue threshold scheme that uses a tailored threshold for each output port queue. This scheme suggests that buffer space occupied by an output port decays as the queue size of this port increases and/or empty buffer space decreases. Results have shown that decay function threshold policy is as good as well‐known dynamic thresholds scheme, and more robust when multicast traffic is used. The main advantage of using this policy is that besides best‐effort traffic it provides support to quality of service (QoS) traffic by using an integrated buffer management and scheduling framework. Copyright © 2006 John Wiley & Sons, Ltd.     

Round-robin selection with adaptable-size frame in a combined input-crosspoint buffered switch

As an alternative to input-buffered switches, combined input-crosspoint buffered switches relax arbitration timing and provide high-performance switching for packet switches with high-speed ports. It has been shown that these switches, with one-cell crosspoint buffer and round-robin (RR) arbitration at input and output ports, provide 100% throughput under uniform traffic. However, under admissible traffic patterns with nonuniform distributions, only weight-based selection schemes are reported to provide high throughput. We propose an RR based arbitration scheme for a combined input-crosspoint buffered packet switch that provides nearly 100% throughput for several admissible traffic patterns, including uniform and unbalanced traffic, using one-cell crosspoint buffers. The presented scheme uses adaptable-size frames, so that the frame size adapts to the traffic pattern.     

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.     

保证100%吞吐率的两级组播交换结构

在路由器或交换机的交换结构中实现组播是提高组播应用速度的重要途径之一。传统的交叉开关结构(crossbar)组播调度方案有两种缺陷,一种是性能较低,另一种是实现的复杂度太高,无法满足高速交换的需要。该文提出了一个新的基于交叉开关的两级组播交换结构(TSMS),第1级是组播到单播的交换结构,第2级是联合输入和输出排队(CIOQ)交换,并为该结构设计了合适的最大扇出排队(FCN)优先-均匀分配中间缓存调度算法(LFCNF-UMBA)。理论分析和仿真实验都显示在该结构中,加速比低于22/(N+1)倍时吞吐率不可能实现100%;而采用LFCNF-UMBA调度算法,2倍加速比就可保证在任意允许(admissible)组播的吞吐率达到100%。     

Buffer sizing for synchronous self-routeing broadband packet switches with bursty traffic

Previous studies on the performance of synchronous self-routeing packet switches have assumed that the input traffic is random, i.e. there is no correlation between adjacent packet arrivals. This assumption is generally not valid in the data communication environment (e.g. host-to-host communication) where a file transfer usually generates a string of correlated packets. The consequence is that the random traffic assumption greatly underestimates the buffer requirement of the switch. In this paper, we model each input traffic stream as a binary source as a first step to understand the performance of a packet switch in a bursty traffic environment. We found that, given a fixed traffic load (or switch utilization), the required buffer size increases linearly as the burstiness index (the average burst length) of the traffic increases. In addition, the required buffer size is more sensitive to the burstiness of the traffic, when the average traffic load is higher and when the packet loss requirement is more stringent. Initial applications of broadband packet switches are likely to be the interconnections of LANs and hosts. The results of the study indicate that the high burstiness in certain broadband traffic significantly reduces the allowable switch utilization, given a fixed amount of buffers. To increase the switch utilization, an appropriate congestion control mechanism needs to be implemented.     

Odd-even input-buffered multicast switch

An input buffered packet switch called the odd-even multicast switch is proposed. The packet splitting probability of the proposed switch is derived and the packet output contention is resolved using the cyclic-priority reservation (CPR) algorithm. The throughput and mean packet delay of the proposed switch are compared with a simple input buffered switch. It is found that the proposed switch gives a significant performance improvement at the expense of extra packet splitting overhead     

On the speedup required for a multicast parallel packet switch

A parallel packet switch (PPS) is a switch in which the memories run slower than the line rate. Arriving packets are load-balanced packet-by-packet over multiple lower speed center stage packet switches. It is known that, for unicast traffic, a PPS can precisely emulate a FCFS output-queued (OQ) switch with a speedup of two and an OQ switch with delay guarantees with a speedup of three. In this paper we ask: is it possible for a PPS to emulate the behavior of an OQ multicast switch? The main result is that for multicast traffic an N-port PPS can precisely emulate a FIFO OQ switch with a speedup of S>2√N+1, and a switch that provides delay guarantees with a speedup of S>2√(2N)+2     

Performance study of ATM multicast switching systems

We evaluate the performance of an N × N ATM discrete time multicast switch model with input queueing operating under two input access disciplines. First we present the analysis for the case of a purely random access discipline and subsequently we concentrate on a cyclic priority access based on a circulating token ring. In both cases, we focus on two HOL (head-of-line) packet service disciplines. Under the first (one-shot transmission discipline), all the copies generated by each HOL packet seek simultaneous transmission during the same time slot. Under the second service discipline (call-splitting), all HOL copies that can be transmitted in the same time slot are released while blocked copies compete for transmission in subsequent slots. In our analysis the performance measures introduced are the average packet delay in the input buffers as well as the maximum throughput of the switch. A significant part of the analysis is based on matrix geometric techniques. Finally, numerical results are presented and compared with computer simulations.     

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     

Performance analysis of nonblocking packet switch with input andoutput buffers

The performance of nonblocking packet switches such as the knockout switch and Batcher banyan switch for high-speed communication networks can be improved as the switching capacity L per output increases; the switching capacity per output refers to the maximum number of packets transferred to an output during a slot. The N×N switch with L=N was shown to attain the best possible performance by M.J. Karol et al. (1987). Here a N×N nonblocking packet switch with input and output buffers is analyzed for an arbitrary number of L such that 1⩽L⩽N. The maximum throughput and packet loss probability at input are obtained when N=∞     

On Packet Switches with Infinite Storage

Most prior work on congestion in datagram systems focuses on buffer management. We find it illuminating to consider the case of a packet switch with infinite storage. Such a packet switch can never run out of buffers. It can, however, still become congested. The meaning of congestion in an infinite-storage system is explored. We demonstrate the unexpected result that a datagram network with infinite storage, first-in, first-out queueing, at least two packet switches, and a finite packet lifetime will, under overload, drop all packets. By attacking the problem of congestion for the infinite-storage case, we discover new solutions applicable to switches with finite storage.     

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