MCBF: a high-performance scheduling algorithm for buffered crossbar switches

The buffered crossbar architecture is becoming very attractive for the design of high performance routers due the unique features it offers. Many distributed scheduling algorithms have been proposed for this architecture. Despite their distributed nature, the existing schemes require quite a bit of hardware and timing complexity. We propose a novel scheduling scheme named the most critical buffer first (MCBF). This scheme is based only on the internal buffer information and requires much less hardware than the existing schemes. Yet, it exhibits good performance and outperforms all its competitors. More interestingly, MCBF shows optimal stability performance while being almost a stateless algorithm.     

RPA: a simple, efficient, and flexible policy for input bufferedATM switches

Reservation with Preemption and Acknowledgment (RPA) is a simple, efficient, and flexible queuing discipline and scheduling algorithm for input buffered asynchronous transfer-mode (ATM) switches. This letter describes the RPA algorithms, and presents simulation results to demonstrate the effectiveness of the proposed approach     

Fast scheduling algorithm for input and output buffered ATM switchwith multiple switching planes

A new scheduling method is presented, two-dimensional round-robin scheduling with multiple selections (2DRRMS), for an input and output buffered ATM switch. In the switch, both input and output ports are divided into several groups and multiple switching planes are used. In the 2DRRMS method the multiple cells for transfer to an input buffer module are selected and the switching planes which the selected cells are to use in the transmission are concurrently determined     

On the behavior of PHM distributed schedulers for input buffered packet switches

iSLIP and parallel hierarchical matching (PHM) are distributed maximal size matching schedulers for input-buffered switches. Previous research has analyzed the hardware cost of those schedulers and their performance after a small number of iterations. In this paper, we formulate an upper bound for the number of iterations required by PHM to converge. Then, we compare the number of iterations required by iSLIP and PHM to achieve a maximal throughput under uniform Bernoulli traffic, by means of simulation. Finally, we obtain the corresponding delay performances, which are similar. The results suggest that PHM has both the advantages of previous hierarchical matching algorithms (low hardware complexity) and iSLIP (low number of iterations).     

FIRM: high-speed distributed scheduling for ATM switches withmultiple input queues

A new distributed scheduling algorithm for advanced input queueing switch architectures called FIRM is introduced. FIRM provides improved performance characteristics at high load compared to the most efficient alternative, improved fairness, and tighter service guarantees     

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     

An efficient scheduling algorithm for input-queued switches

This letter presents an efficient scheduling algorithm DTRR （Dual-Threshold Round Robin） for input-queued switches. In DTRR, a new matched input and output by round robin in a cell time will be locked by two self-adaptive thresholds whenever the queue length or the wait-time of the head cell in the corresponding Virtual Output Queue （VOQ） exceeds the thresholds. The locked input and output will be matched directly in the succeeding cell time until they are unlocked. By employing queue length and wait-time thresholds which are updated every cell time simultaneously, DTRR achieves a good tradeoff between the performance and hardware complexity. Simulation results indicate that the delay performance of DTRR is competitive compared to other typical scheduling algorithms under various traffic patterns especially under diagonal traffic.     

Optimal algorithm for scheduling CBR traffic in ATM switches

A non-blocking input buffered ATM switch that supports CBR and ABR traffic using a TDM scheduler frame is considered. A new TDM scheduler algorithm (largest-first) for CBR traffic is compared with four others, based on the evenness of the distribution of unused timeslots in the scheduling frame. An even distribution of unused slots minimises the average latency and jitter for ABR traffic. Simulation results show that largest-first allocation is the best     

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.     

Multicast scheduling for input-queued switches

We design a scheduler for an M×N input-queued multicast switch. It is assumed that: 1) each input maintains a single queue for arriving multicast cells and 2) only the cell at the head of line (HOL) can be observed and scheduled at one time. The scheduler needs to be: 1) work-conserving (no output port may be idle as long as there is an input cell destined to it) and 2) fair (which means that no input cell may be held at HOL for more than a fixed number of cell times). The aim is to find a work-conserving, fair policy that delivers maximum throughput and minimizes input queue latency, and yet is simple to implement. When a scheduling policy decides which cells to schedule, contention may require that it leave a residue of cells to be scheduled in the next cell time. The selection of where to place the residue uniquely defines the scheduling policy. Subject to a fairness constraint, we argue that a policy which always concentrates the residue on as few inputs as possible generally outperforms all other policies. We find that there is a tradeoff among concentration of residue (for high throughput), strictness of fairness (to prevent starvation), and implementational simplicity (for the design of high-speed switches). By mapping the general multicast switching problem onto a variation of the popular block-packing game Tetris, we are able to analyze various scheduling policies which possess these attributes in different proportions. We present a novel scheduling policy, called TATRA, which performs extremely well and is strict in fairness. We also present a simple weight-based algorithm, called WBA     

A central-stage buffered three-stage Clos switching fabric and the scheduling algorithm

Current MSM switching fabric has poor performance under unbalanced traffic. This paper presents an alternative, novel Central-stage Buffered Three-stage Clos switching (CB-3Clos) fabric and proves that this fabric can emulate output queuing switch without any speedup. By analyzing the condition to satisfy the central-stage load-balance, this paper also proposes a Central-stage Load-balanced-based Distributed Scheduling algorithm (CLDS) for CB-3Clos. The results show that, compared with Concurrent Round-Robin based Dispatching (CRRD) algorithm based on MSM, CLDS algorithm has high throughput irrespective with the traffic model and better performance in mean packet delay.     

改进捕鱼算法求解柔性作业车间调度问题

传统基于精确算法求解柔性作业车间调度问题时,仅能对小量柔性作业车间调度问题实施求解,具有一定的局限性。针对该问题,采用改进捕鱼算法求解柔性作业车间调度问题,在分析经典捕鱼算法存在弊端的基础上,提出改进捕鱼算法,融入渔夫的自身感知性能以及捕鱼经验,分析鱼浓度高的区域,并不断趋向该区域区间,通过概率分布原理对渔夫撒网方案实施优化。分析求解柔性作业车间调度问题的描述以及性能指标,将性能指标作为改进捕鱼算法的输入,通过运算获取最佳的调度结果。实验结果说明,所提算法具有较高的调度效率和精度,并且确保作业车间能耗的最小化。     

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     

Optimum scheduling and memory management in input queued switches with finite buffer space

The goal of this paper is to design optimal scheduling and memory management so as to minimize packet loss in input queued switches with finite input buffers. The contribution is to obtain closed-form optimal strategies that minimize packet loss in 2/spl times/2 switches with equal arrival rates for all streams. For arbitrary arrival rates, the contribution is to identify certain characteristics of the optimal strategy, and use these characteristics to design a near-optimal heuristic. A lower bound for the cost associated with packet loss for N/spl times/N switches is obtained. This lower bound is used to design a heuristic which attains near-minimum packet loss in N/spl times/N switches with arbitrary N. These policies reduce packet loss by about 25% as compared to the optimal strategy for the infinite buffer case. The framework and the policies proposed here apply to buffer-constrained wireless networks as well.     

Neural scheduling algorithms for time-multiplex switches

In an N×N time-multiplex switch, transmission conflict arises when two or more input adaptors transmit packets to the same output adaptor simultaneously. To resolve transmission conflict, we propose two neural-based scheduling algorithms which use a large number of simple processing elements to perform scheduling in parallel. The first algorithm uses N² hysteresis McCulloch-Pitts (1943) neurons to determine conflict-free transmission schedules with maximum throughput. The second algorithm resolves transmission conflict among the first M packets in each input queue. It determines suboptimal transmission schedules using only NM neurons (M2=250000 to NM=5000     

Deficit round-robin scheduling for input-queued switches

We address the problem of fair scheduling of packets in Internet routers with input-queued switches. The goal is to ensure that packets of different flows leave a router in proportion to their reservations under heavy traffic. First, we examine the problem when fair queuing is applied only at output link of a router, and verify that this approach is ineffective. Second, we propose a flow-based iterative deficit-round-robin (iDRR) fair scheduling algorithm for the crossbar switch that supports fair bandwidth distribution among flows, and achieves asymptotically 100% throughput under uniform traffic. Since the flow-based algorithm is hard to implement in hardware, we finally propose a port-based version of iDRR (called iPDRR) and describe its hardware implementation.     

MUMF-支持单多播公平服务的调度策略

基于联合输入交叉点排队(CICQ,combined input and cross-point queuing)交换结构探讨了单多播混合调度的公平性问题,提出了能够为单多播业务提供混合公平性的CICQ理想调度模型。基于理想调度模型,提出了逼近理想调度模型的MUMF(mixed uni-and multicast fair)调度算法,MUMF调度算法采用了分级和层次化的公平调度机制,通过输入调度和交叉点调度确保单多播业务混合调度的公平性。MUMF交换机制的每个输入、输出端口可独立地进行分组交换,具有良好可扩展特性。最后,基于SPES(switching performance evaluation system)的性能仿真结果表明MUMF调度算法具有良好的时延、公平性和吞吐量性能。     

Optimum architecture for input queuing ATM switches

An input queueing ATM switch architecture employing the contention resolution called 'scheduling algorithm' is described. A high efficiency of over 90% can be achieved without any considerable increase in the amount of hardware or contention control speed.<>     

Randomized scheduling algorithms for high-aggregate bandwidth switches

The aggregate bandwidth of a switch is its port count multiplied by its operating line rate. We consider switches with high-aggregate bandwidths; for example, a 30-port switch operating at 40 Gb/s or a 1000-port switch operating at 1 Gb/s. Designing high-performance schedulers for such switches with input queues is a challenging problem for the following reasons: (1) high performance requires finding good matchings; (2) good matchings take time to find; and (3) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers for high-aggregate bandwidth switches: (1) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time and (2) observing arriving packets will convey useful information about the state of the switch. The above features are exploited using hardware parallelism and randomization to yield three scheduling algorithms - APSARA, LAURA, and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite close to that of the maximum weight matching, even when the traffic is correlated. We also consider the stability property of these algorithms under generic admissible traffic using the fluid-model technique. The main contribution of this paper is a suite of simple to implement, high-performance scheduling algorithms for input-queued switches. We exploit a novel operation, called MERGE, which combines the edges of two matchings to produce a heavier match, and study of the properties of this operation via simulations and theory. The stability proof of the randomized algorithms we present involves a derandomization procedure and uses methods which may have wider applicability.