A buffer management scheme for the SCOQ switch under nonuniformtraffic loading

The SCOQ switch is a Batcher-banyan based high performance fast packet switch with shared concentration and output queueing, with a maximum of L(相似文献   

The knockout switch under nonuniform traffic

The knockout switch is a nonblocking, high-performance switch suitable for broadband packet switching. It allows packet losses, but the probability of a packet loss can be kept extremely small in a cost-effective way. The performance of the knockout switch was analyzed under uniform traffic. In this paper, we present a new, more general analytic model of the knockout switch, which enables us to evaluate the knockout switch under nonuniform traffic. The new model also incorporates the effects of a concentrator and a shared buffer on the packet loss probability. Numerical results for nonuniform traffic patterns of interest are presented     

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     

Nonuniform traffic analysis on a nonblocking space-division packetswitch

The nonuniform traffic performance on a nonblocking space division packet switch is studied. When an output link is simultaneously contended by multiple input packets, only one can succeed, and the rest will be buffered in the queues associated with each input link. given the condition that the traffic on each output is not dominated by individual inputs, this study indicates that the output contention involved by packets at the head of input queues can be viewed as an independent phase-type process for a sufficiently large size of the switch. Therefore, each input queue can be modeled by an independent Geom/PH/1 queueing process. Once the relative input traffic intensities and their output address assignment functions are defined, a general formulation can be developed for the maximum throughput of the switch in saturation. The result indicates under what condition the input queue will saturate. A general solution technique for the evaluation of the queue length distribution is proposed. The numerical study based on this analysis agrees well with simulation results     

Performances of the Data Vortex switch architecture under nonuniform and bursty traffic

The Data Vortex switch architecture has been proposed as a scalable low-latency interconnection fabric for optical packet switches. This self-routed hierarchical architecture employs synchronous timing and distributed traffic-control signaling to eliminate optical buffering and to reduce the required routing logic, greatly facilitating a photonic implementation. In previous work, we have shown the efficient scalability of the architecture under uniform and random traffic conditions while maintaining high throughput and low-latency performance. This paper reports on the performance of the Data Vortex architecture under nonuniform and bursty traffic conditions. The results show that the switch architecture performs well under modest nonuniform traffic, but an excessive degree of nonuniformity will severely limit the scalability. As long as a modest degree of asymmetry between the number of input and output ports is provided, the Data Vortex switch is shown to handle very bursty traffic with little performance degradation.     

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     

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.     

Performance of a nonblocking space-division packet switch withcorrelated input traffic

This work studies the performance of a nonblocking space-division packet switch in a correlated input traffic environment. In constructing the input traffic model, the author considers that each input is a time division multiaccess (TDM) link connecting to multiple sources. Every source on a link supports one call at a time. Each call experiences the alternation of ON and OFF periods, and generates packets periodically while in ON period. The stochastic property of each call does not have to be identical. Packets from each individual call are destined to the same output. The output address of each call is assumed to be uniformly assigned at random. The author derives both upper and lower bounds of the maximum throughput at system saturation. His study indicates that, if the source access rate is substantially lower than the link transmission rate, the effect of input traffic correlation on the output contentions can generally be ignored. Also, the analysis of each input queue becomes separable from the rest of the switch. The same study is carried out with nonuniform call address assignment     

The performance analysis and implementation of an input accessscheme in a high-speed packet switch

The performance analysis of an input access scheme in a high-speed packet switch for broadband ISDN is presented. In this switch, each input port maintains a separate queue for each of the outputs, thus n ² input queues in an (n×n) switch. Using synchronous operation, at most one packet per input and output will be transferred in any slot. We derive lower and upper bounds for the throughput which show close to optimal performance. The bounds are very tight and approach to unity for switch sizes on the order of a hundred under any traffic load, which is a significant result by itself. Then the mean packet delay is derived and its variance is bounded. A neural network implementation of this input access scheme is given. The energy function of the network, its optimized parameters and the connection matrix are determined. Simulation results of the neural network fall between the theoretical throughput bounds     

A performance model of deflection routing in multibuffer networkswith nonuniform traffic

Deflection routing can be used in networks whose stations have the same number of input and output links. Fixed length packets arrive synchronously on the station's input links at the beginning of time slots, and each packet is routed via the output link that offers the shortest path to its destination. Since the number of packet buffers at each output link is finite, the simultaneous contention of two packets for the last buffer of a common output link must be resolved by “deflecting” one of the packets to another output link. Thus, the deflection of a packet could result in the packet following a route that is not a shortest path. The potentially unbounded number of routes that a given packet can take makes analyzing the performance of such networks difficult. In particular, there are no analytical models that can analyze multibuffer deflection-routing networks with nonuniform traffic. Using independence assumptions, the authors develop a performance model of deflection routing that allows to estimate accurately and efficiently the mean transport time and throughput in a network that has any given two-connected topology, multiple buffers at each output port, and an arbitrary traffic matrix     

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     

Multistage shuffle networks with shortest path and deflectionrouting for high performance ATM switching: the open-loopshuffleout

A new class of switching architectures for broadband packet networks, called shuffleout, is described and analyzed in the paper. Shuffleout is basically an output-queued architecture with a multistage interconnection network built out of unbuffered b×2b switching elements. Its structure is such that the number of cells that can be concurrently switched from the inlets to each output queue equals the number of stages in the interconnection network. The switching element operates the cell self-routing adopting a shortest path algorithm which, in case of conflict for interstage links, is coupled with deflection routing. The paper presents the basic shuffleout architecture, called open-loop shuffleout, in which the cells that cross the whole interconnection network without entering the addressed output queues are lost. The key target of the proposed architecture is coupling the implementation feasibility of a self-routing switch with the desirable traffic performance typical of output queueing     

一种基于Credit的变长分组并行交换网络调度算法

该文提出了一种新的并行分组交换(PPS)网络调度算法。该算法通过在解复用器处采用以变长分组为业务分配单元的方式消除了信元的乱序问题;通过采用Credit机制进行业务分配,实现了业务到各个交换平面完全公平的分配;各个并行交换单元采用组合输入输出排队,降低了对缓存和交换平面的加速要求,同时可以充分利用现有单Crossbar网络调度算法的研究成果。文中证明了该算法对业务分配的公平性,对高速缓存的需求量以及整个网络的稳定性,仿真进一步证明了该算法具有良好性能。     

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.     

On the combined input-crosspoint buffered switch with round-robin arbitration

Input-buffered switches have been widely considered for implementing feasible packet switches. However, their matching process may not be time-efficient for switches with high-speed ports. Buffered crossbars (BXs) are an alternative to relax timing for packet switches with high-speed ports and to provide high-performance switching. BX switches were originally considered expensive, as the memory amount required in the crosspoints (XPs) is proportional to the square of the number of ports (O(N/sup 2/)). This limitation is now less stringent with the advances on chip-fabrication techniques, and when considering small crosspoint (XP) buffer sizes. In this paper, we study a combined input-crosspoint buffered packet switch, named CIXB, with virtual output queues (VOQs) at the inputs, and arbitration based on round-robin selection. We show that the CIXB switch achieves 100% throughput under uniform traffic, and high performance under nonuniform traffic, using one-cell XP buffer size and no speedup.     

Architecture design,performance analysis and VLSI implementation of a reconfigurable shared buffer for high‐speed switch/router

Modern switches and routers require massive storage space to buffer packets. This becomes more significant as link speed increases and switch size grows. From the memory technology perspective, while DRAM is a good choice to meet capacity requirement, the access time causes problems for high‐speed applications. On the other hand, though SRAM is faster, it is more costly and does not have high storage density. The SRAM/DRAM hybrid architecture provides a good solution to meet both capacity and speed requirements. From the switch design and network traffic perspective, to minimize packet loss, the buffering space allocated for each switch port is normally based on the worst‐case scenario, which is usually huge. However, under normal traffic load conditions, the buffer utilization for such configuration is very low. Therefore, we propose a reconfigurable buffer‐sharing scheme that can dynamically adjust the buffering space for each port according to the traffic patterns and buffer saturation status. The target is to achieve high performance and improve buffer utilization, while not posing much constraint on the buffer speed. In this paper, we study the performance of the proposed buffer‐sharing scheme by both a numerical model and extensive simulations under uniform and non‐uniform traffic conditions. We also present the architecture design and VLSI implementation of the proposed reconfigurable shared buffer using the 0.18 µm CMOS technology. Our results manifest that the proposed architecture can always achieve high performance and provide much flexibility for the high‐speed packet switches to adapt to various traffic patterns. Furthermore, it can be easily integrated into the functionality of port controllers of modern switches and routers. Copyright © 2008 John Wiley & Sons, Ltd.     

Cell loss analysis and design trade-offs of nonblocking ATMswitches with nonuniform traffic

In practical ATM switch design, a proper dimensioning of buffer sizes and a cost effective selection of speed-up factor should be considered to guarantee a specified cell loss requirement for a given traffic. Although a larger speed-up factor provides better throughput for the switch, increasing the speed-up factor involves greater complexity and cost. Hence, it may not be cost effective to increase the speed-up factor for 100% throughput. Moreover, with a given buffer budget, an increase in the speed-up factor beyond a certain value only adds to the cell loss. The paper addresses design trade-offs existing between finite input/output buffer sizes and speed-up factor in a nonblocking ATM switch. Another important issue is the adverse effect on cell loss performance caused by nonuniform traffic (different traffic intensity and unevenly distributed routing). The paper analyzes cell loss performance of ATM switches with nonuniform traffic, and examines the effect of each nonuniform traffic parameter. The authors also provide an algorithm for effective buffer sharing that alleviates the performance degradation caused by traffic nonuniformity     

Impact of scheduling algorithms on performance of crosspoint-queued switch

The performance analysis of the 32?×?32 crosspoint-queued switch is presented in this paper. Switches with small buffers in crosspoints have been evaluated in the late 1980s but mostly for uniform traffic. However, due to technological limitations of that time, it was impractical to implement large buffers together with switching fabric. The crosspoint-queued switch architecture has been recently brought back into focus since modern technology enables an easy implementation of large buffers in crosspoints. An advantage of this solution is the absence of control communication between linecards and schedulers. In this paper, the performances of four algorithms (longest queue first, round robin, exhaustive round robin, and frame-based round robin matching) are analyzed and compared. The results obtained for the crosspoint-queued switch are compared with the output queued switch. Throughput, average cell latency and instantaneous packet delay variance are evaluated under uniform and nonuniform traffic patterns. The results will show that the longest queue first algorithm has the highest throughput in many simulated cases but the highest average cell latency and delay variance among observed algorithms. It will also be shown that the choice of the scheduling algorithm does not play a role in the switch performance if the buffers are long enough. This will prove that some form of round-robin-based algorithms become a better choice for implementation due to their simplicity, small hardware requirements, and avoidance of the starvation problem, which is a major drawback of the longest queue first algorithm.     

Dimensioning an ATM switch based on a three-stage Clos interconnection network

ATM (asynchronous transfer mode) is a new technique for transmitting voice, data and video. The performance of atm networks will depend on switch structure. Performance analysis of an atm switch based on a three-stage Clos network is presented. In this paper two types of switches are studied: a switch with input queues in the switching elements and a switch with output queues. This study is at the cell level and intends to dimension the switch. First, the traffic is supposed to be uniform, cells arrive on each input according to a geometric arrival process, they are uniformly directed over all the network outputs. An analytic model is proposed for both input and output queues in the switching elements. A study of the saturation throughput is proposed for input buffer switching elements. This work proves the influence of buffer dimensioning on the different stages of the switch. Dissymmetric switching elements are shown to be better than symmetric ones. A model is then designed for nonuniform traffic patterns and output buffers. Two types of non-uniform traffic are presented: single source to single destination (sssd) and multi-hot spots traffic (mhs). Discrete event simulations are used to validate the different models.     

Buffer Management in a Packet Switch

Consider a single packet switch with a finite number of packet buffers shared between several output queues. An arriving packet is lost if no free buffer is available, as in the CIGALE network. It has been observed by simulation that if load increases too much, congestion may occur, i.e., throughput declines; it appears that the busiest link's queue tends to hog the buffers. Therefore, we will limit the queue length and when the queue is full the packet will be dropped. We expect that this restricted buffer sharing policy will avoid congestion under conditions of heavy load. A queueing model of a packet switch is defined and solved by local balance. Loss probability is evaluated, and values of queue limit to minimize loss are found; they depend on load. A Square-Root rule is introduced to make the choice of queue limit independent of load. For a sample switch, with three output links, a comparison is made between performance under different buffer sharing policies; it is shown that restricted sharing prevents congestion by making throughput an increasing function of load.