The iSLIP scheduling algorithm for input-queued switches

An increasing number of high performance internetworking protocol routers, LAN and asynchronous transfer mode (ATM) switches use a switched backplane based on a crossbar switch. Most often, these systems use input queues to hold packets waiting to traverse the switching fabric. It is well known that if simple first in first out (FIFO) input queues are used to hold packets then, even under benign conditions, head-of-line (HOL) blocking limits the achievable bandwidth to approximately 58.6% of the maximum. HOL blocking can be overcome by the use of virtual output queueing, which is described in this paper. A scheduling algorithm is used to configure the crossbar switch, deciding the order in which packets will be served. Previous results have shown that with a suitable scheduling algorithm, 100% throughput can be achieved. In this paper, we present a scheduling algorithm called iSLIP. An iterative, round-robin algorithm, iSLIP can achieve 100% throughput for uniform traffic, yet is simple to implement in hardware. Iterative and noniterative versions of the algorithms are presented, along with modified versions for prioritized traffic. Simulation results are presented to indicate the performance of iSLIP under benign and bursty traffic conditions. Prototype and commercial implementations of iSLIP exist in systems with aggregate bandwidths ranging from 50 to 500 Gb/s. When the traffic is nonuniform, iSLIP quickly adapts to a fair scheduling policy that is guaranteed never to starve an input queue. Finally, we describe the implementation complexity of iSLIP. Based on a two-dimensional (2-D) array of priority encoders, single-chip schedulers have been built supporting up to 32 ports, and making approximately 100 million scheduling decisions per second     

NN based ATM cell scheduling with queue length-based priorityscheme

The asynchronous transfer mode (ATM) is the choice of transport mode for broadband integrated service digital networks (B-ISDNs). We propose a window-based contention resolution algorithm to achieve higher throughput for nonblocking switches in ATM environments. In a nonblocking switch with input queues, significant loss of throughput can occur due to head-of-line (HOL) blocking when first-in first-out (FIFO) queueing is employed. To resolve this problem, we employ bypass queueing and present a cell scheduling algorithm which maximizes the switch throughput. We also employ a queue length based priority scheme to reduce the cell delay variations and cell loss probabilities. With the employed priority scheme, the variance of cell delay is also significantly reduced under nonuniform traffic, resulting in lower cell loss rates (CLRs) at a given buffer size. As the cell scheduling controller, we propose a neural network (NN) model which uses a high degree of parallelism. Due to higher switch throughput achieved with our cell scheduling, the cell loss probabilities and the buffer sizes necessary to guarantee a given CLR become smaller than those of other approaches based on sequential input window scheduling or output queueing     

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 study of an input and output queueing ATM switch with a window scheme and a speed constraint

In this paper, we study the performance of an input and output queueing switch with a window scheme and a speed constraint. The performance of a non-blocking ATM switch can usually be improved by increasing the switching speed. Also, the performance of a switch can be improved using a window scheme by relaxing the first-in-firstout (FIFO) queueing discipline in the input queue. Thus, one can expect that a combined scheme of windowing and a speed constraint can improve further the performance of the packet switch. Here, we analyze the maximum throughput of the input and output queueing switch with a speed constraint combined with windowing, and show that it is possible to obtain high throughput with a small increment of speed-up and window size. For analysis, we model the HOL queueing system as a virtual queueing system. By analyzing the dynamics of HOL packets in this virtual queueing model, we obtain the service probability of the HOL server as a function of output contention capabilities. Using the result, we apply the flow conservation relation to this model and obtain the maximum throughput. The analytical results are verified by simulation.     

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.     

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     

Two-dimensional round-robin schedulers for packet switches withmultiple input queues

Presents a new scheduler, the two-dimensional round-robin (2DRR) scheduler, that provides high throughput and fair access in a packet switch that uses multiple input queues. We consider an architecture in which each input port maintains a separate queue for each output. In an N×N switch, our scheduler determines which of the queues in the total of N² input queues are served during each time slot. We demonstrate the fairness properties of the 2DRR scheduler and compare its performance with that of the input and output queueing configurations, showing that our scheme achieves the same saturation throughput as output queueing. The 2DRR scheduler can be implemented using simple logic components, thereby allowing a very high-speed implementation     

有优先级的输出排队快速分组交换机性能研究

输出排队结构是快速分组交换中交换性能最佳的交换结构。本文研究输出排队结构交换任意种优先级业务的排队性能。分别在独立和相关到达两种情况下导出了任意优先级业务的平均排队长度等特征参数,发现当N×N规模互连网络的端口数N足够大时,两种业务到达模型的排队性能趋于一致。文中提出了一种数值迭代法来求取用二维Markov过程表示的高、低优先级分组队列长度的稳态解。计算机模拟结果证实了文中的分析。     

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.     

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     

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     

On achieving throughput in an input-queued switch

We establish some lower bounds on the speedup required to achieve throughput for some classes of switching algorithms in a input-queued switch with virtual output queues (VOQs). We use a weak notion of throughput, which will only strengthen the results, since an algorithm that cannot achieve weak throughput cannot achieve stronger notions of throughput. We focus on priority switching algorithms, i.e., algorithms that assign priorities to VOQs and forward packets of high priority first. We show a lower bound on the speedup for two fairly general classes of priority switching algorithms: input priority switching algorithms and output priority switching algorithms. An input priority scheme prioritizes the VOQs based on the state of the input queues, while an output priority scheme prioritizes the VOQs based on their output ports. We first show that, for output priority switching algorithms, a speedup S/spl ges/2 is required to achieve weak throughput. From this, we deduce that both maximal and maximum size matching switching algorithms do not imply weak throughput unless S/spl ges/2. The bound of S/spl ges/2 is tight in all cases above, based on a result in Dai et al. Finally, we show that a speedup S/spl ges/3/2 is required for the class of input priority switching algorithms to achieve weak throughput.     

针对高速交换结构的广义极大匹配调度算法

调度算法是决定交换结构性能和实现复杂度的重要因素,极大匹配算法在这两方面存在不足.本文提出一类广义极大匹配(EMM)算法,使用不同权值参数能够派生出不同子类的算法.对广义极大匹配算法的研究从两方面展开,首先在2倍数据加速比下证明任何EMM(2)算法都能取得100％的吞吐量,并通过仿真表明能够取得与理想输出排队相近的延时性能;其次在没有加速比的条件下通过仿真表明具有2个以上权值参数的广义极大匹配算法能够大大提高极大匹配算法的吞吐量性能.     

Dynamic server allocation to parallel queues with randomly varyingconnectivity

Consider N parallel queues competing for the attention of a single server. At each time slot each queue may be connected to the server or not depending on the value of a binary random variable, the connectivity variable. Allocation at each slot; is based on the connectivity information and on the lengths of the connected queues only. At the end of each slot, service may be completed with a given fixed probability. Such a queueing model is appropriate for some communication networks with changing topology. In the case of infinite buffers, necessary and sufficient conditions are obtained for stabilizability of the system in terms of the different system parameters. The allocation policy that serves the longest connected queue stabilizes the system when the stabilizability conditions hold. The same policy minimizes the delay for the special case of symmetric queues. In a system with a single buffer per queue, an allocation policy is obtained that maximizes the throughput and minimizes the delay when the arrival and service statistics of different queues are identical     

A note on the conservation law for queues with batch arrivals

The conservation law formula for work-conserving queues with batch arrivals is derived for when the arrival instants of customers are assumed to constitute an arrivals see time averages (ASTA) process. The derivation is based on the analysis of the corresponding first-in first-out (FIFO) multiclass queue and its steady state. Hence, the mean work load in the queue at an arbitrary time instant can be equated with the mean time that an arbitrary customer has to wait in the FIFO queue     

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     

Queue Proportional Scheduling via Geometric Programming in Fading Broadcast Channels

For fading broadcast channels (BC), a throughput optimal scheduling policy called queue proportional scheduling (QPS) is presented via geometric programming (GP). QPS finds a data rate vector such that the expected rate vector over all fading states is proportional to the current queue state vector and is on the boundary of the ergodic capacity region of a fading BC. Utilizing the degradedness of BC for each fading state, QPS is formulated as a geometric program that can be solved with efficient algorithms. The GP formulation of QPS is also extended to orthogonal frequency-division multiplexing (OFDM) systems in a fading BC. The throughput optimality of QPS is proved, and it is shown that QPS can arbitrarily scale the ratio of each user's average queueing delay. Throughput, delay, and fairness properties of QPS are numerically evaluated in a fading BC and compared with other scheduling policies such as the well-known maximum weight matching scheduling (MWMS). Simulation results for Poisson packet arrivals and exponentially distributed packet lengths demonstrate that compared with MWMS, QPS provides a significant decrease in average queueing delay and has more desirable fairness properties.     

Priority-based grant-aware scheduling for low-latency switching

This paper introduces new scheduling algorithms supporting low-latency switching. The proposed grant-aware (GA) algorithm improves the average delay performance by using the grant information of previous iteration. The simulation result shows that the average delay of GA algorithm is about one-tenth of the existing algorithm in high-load condition. We also introduce two priority-based scheduling algorithms grant-aware and priority-aware (GAPA) algorithm and cyclic scheduling with the longest-queue-first (C-LQF) algorithm. In the priority-based scheduling, the scheduling priority of VoQ is determined based on its queue size. GAPA and C-LQF consider the priority only after the first iteration to prevent the starvation problem. The simulation result shows that GAPA and C-LQF scheduling achieves better performance than GA in terms of average delay, maximum delay, and hotspot throughput.     

On the stability of local scheduling policies in networks of packet switches with input queues

A significant research effort has been devoted to the design of simple and efficient scheduling policies for input queued (IQ) and combined input-output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on maximum weight matching (MWM) were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible arrival process satisfying the strong law of large number. On the contrary, it has been shown that the usual MWM policies fail to guarantee 100% throughput in networks of interconnected IQ/CIOQ switches. Hence, new policies suited for networks of interconnected switches were proposed and proved to achieve 100% throughput. All of these new policies require coordination and cooperation among different switches. We identify scheduling policies that require no coordination among switches (and are, thus, said to be local), and that guarantee 100% throughput in a network of IQ/CIOQ switches. The only assumptions on the input traffic pattern are that it is stationary, satisfies the strong law of large numbers and does not oversubscribe any link in the network.     

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