iRGRR/PM：一种新的高速crossbar分组调度策略

iRGRR(iterative Request-Grant-based Round-Robin)算法是一种输入排队crossbar调度算法,具有硬件易实现、可扩展性强、性能优良等优点.在此基础上,该文提出一种新的高速crossbar分组调度策略iRGRR/PM(iRGRR with Packet Mode),可以更好地支持IP分组的调度,能够被应用于高速、大容量的路由器中.与iRGRR算法相比,iRGRR/PM简化了分组输出重组模块的设计,并且提高了crossbar的带宽资源利用率.文中简单分析了两种算法间的分组时延关系,并进行了详尽的仿真研究.结果表明:在相同条件下,iRGRR/PM算法具有更高的吞吐量,尤其在非均匀业务流下能获得接近100%的吞吐量;调度长分组时,iRGRR/PM算法具有更好的时延性能.     

一种基于输入排队的抗突发调度算法

为了提高数据通信的传输速率和可靠性,高速路由器和交换机采用了基于crossbar的交换结构以及多种调度算法.首先对经典的集中式调度算法iSLIP算法进行分析,由于此算法在突发和不均匀业务时的性能有很大的下降.针对这一缺陷,提出了lp_iSLIP(Long Queues Priority iSLIP)算法,此算法在突发业务时表现出比iSLIP算法更好的性能,在均匀业务时的性能与iSLIP算法相当,而且没有增加硬件实现的复杂度.     

分组交换网络调度算法概述

为了合理利用网络资源,提高网络吞吐率,降低通信时延,需要采取有效的调度算法实现输入端和输出端的匹配.基于VOQ的输入排队交换结构是当前分组交换网络最常用的结构.本文介绍了几种基于VOQ的调度算法:用于单级crossbar的PIM、iRRM和iSLIP算法,以及适用于三级Clos网络的RD和CDDR算法.对每种算法,介绍其基本原理和性能,以及与其他算法的区别.     

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

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

分组交换机的极大匹配调度算法仿真与比较

对于输入缓存类型的分组交换系统,调度算法是交换系统的关键技术之一,其性能直接影响着交换单元的性能。研究了几种典型的极大匹配调度算法:PIM,iSLIP,FIRM和输出串行调度算法。通过OPNET构造了一种调度算法模型,以8×8 crossbar交换结构为例,基于该模型对这几种极大匹配调度算法进行了仿真。根据仿真结果从平均调度时延等性能指标及实现复杂度方面进行了分析和比较,指出了现有算法的优缺点,并提出了进一步改进的方向,对卫星ATM/IP交换系统的研究与设计具有指导作用。     

面向可重构服务承载网的分域混合承载组调度研究

传统网络技术体系,网络是封闭的、刚性的,无法满足未来网络大量差异化业务的规模化应用,由此提出了面向服务提供的柔性网络技术体系,该体系将传统网络中的用户业务、网络服务和网络基础设施中的紧耦合关系转变为松耦合关系,通过资源分割构建可重构服务承载网实现对业务的服务质量保证。该文分析了服务承载网映射到交换结构的需求,提出分域调度的思想。通过选择关闭部分交叉节点的方法建立了crossbar交换结构分域模型,实现了分域调度的端口分离。提出了支持可重构服务承载网构建的混合承载组调度(HCGS)算法,推导了承载组内SDRR(Smoothed Deficit Round Robin)调度、单个域内基于时间戳的输入端口调度和交叉节点输出端口调度算法,证明了HCGS具有良好的时延性能和最坏公平指数(WFI)公平性。仿真结果表明:在均匀分布的泊松业务源条件下,分域HCGS算法具有更优的时延性能,可保证业务带宽的公平性。在diagonal非均匀允许流量条件下,该算法的吞吐量可达100%。     

在CICQ交换结构下实现分布式的WFQ类加权公平调度算法

传统的基于crossbar的输入排队交换结构在提供良好的QoS方面存在很大的不足,而CICQ(Combined Input and Crosspoint buffered Queuing)交换结构与传统的交换结构相比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。该文基于CICQ结构,提出了在输入排队条件下实现基于流的分布式WFQ类分组公平调度算法的方案,并通过仿真验证了这一方案的有效性。     

FQLP:ATM网中一种新的实时业务调度算法

 本文提出了基于丢失优先权公平队列(FQLP)调度算法.理论分析和仿真实验表明FQLP调度算法能保证实时业务获得的网络资源不小于预约带宽,为实时业务提供确定的时延上界.FQLP调度算法利用ATM网络中的信元优先权机制,提高了网络资源的利用率.同时FQLP调度策略能保证信元的发送顺序.     

高性能新型交换结构综述

 目前基于单级交换结构(single-stage switch)集中式调度的路由器已经不能满足Internet网络流量、网络规模和上层应用的快速发展.近年来,旨在提高路由器可扩展性、吞吐率、QoS能力的高性能交换技术,成为路由器技术研究中的一大热点.文章从体系结构、调度策略、QoS特性三个方面对高性能交换结构研究进展进行了综述,以可扩展性、实现复杂度、延迟和吞吐率保证、负载均衡及报文乱序为主要衡量指标分析比较了每一类交换结构调度算法的性能,最后提出下一步的研究课题和思路.     

一种新的输入排队crossbar的公平调度算法

本文提出一种新的输入排队crossbar调度算法——WMFS(weighted max-min fair scheduling)算法，可以为各个竞争的流提供近似的归一化公平服务，保证了带宽分配的加权max-min公平性．另外，仿真结果表明在均匀业务流到达情况下，WMFS具有100％的吞吐量和良好的时延性能．     

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     

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.     

一种公平输入排队调度算法

输入排队交换结构以其良好的可扩展性被越来越多的高速交换机和路由器所采用。当前的调度算法大都以牺牲公平性来换取最大的吞吐量。但随着对QoS支持的要求增强,适用于输入排队交换结构的高效、公平的调度算法成为迫切需要解决的问题。该文提出了一种具有公平性保证的基于虚服务量的公平调度算法。理论分析和计算机仿真都表明算法在信元时延和公平性方面都能提供较好的保证。算法还具有与iSLIP相同的较低通信开销,以及和iLQF相同的算法复杂度。因此,算法具有较好的实用性。     

Stability of a frame-based oldest-cell-first maximal weight matching algorithm

Input-queued cell switches employing the oldest-cell-first (OCF) policy have been shown to yield low mean delay characteristics. Moreover, it has been proven that OCF is stable for admissible traffic conditions when executed with a scheduling speedup of 2. However, as link speeds increase, the computational complexity of these algorithms limits their applicability in high port-density switches and routers. To address the scalability issue, we describe a Frame-Based Maximal Weight Matching (FMWM) algorithm, employing OCF as queue weights, in which a new scheduling decision is issued once every several cell times. Between scheduling decisions, the configuration of the crossbar switch remains unchanged. We further extend the analysis to address the case of multiple classes of service, and prove that the algorithm is stable with an internal buffer transfer speedup of 2, thereby significantly relaxing the timing constraints imposed on the scheduling process.     

片上网络路由器的交叉开关设计实现

交叉开关是片上网络路由器的关键部分。交叉开关的设计可以采用三态触发器或多路复用器实现。本文针对几种不同形式的交叉开关实现方案,比较了其面积和功耗的开销,同时设计了基于iSLIP算法的交叉开关调度机制。通过基本逻辑门搭建的多路复用器实现的交叉开关相比于采用三态门实现的交叉开关,在功耗、面积上有较大优势。采用iSLIP算法实现的片上网络交叉开关,具有最高的工作频率上限。     

Logarithmic Delay for N ×N Packet Switches Under the Crossbar Constraint

We consider the fundamental delay bounds for scheduling packets In an N times N packet switch operating under the crossbar constraint. Algorithms that make scheduling decisions without considering queue backlog are shown to incur an average delay of at least O(N). We then prove that O(log(N)) delay is achievable with a simple frame based algorithm that uses queue backlog information. This is the best known delay bound for packet switches, and is the first analytical proof that sublinear delay is achievable in a packet switch with random inputs.     

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.     

Resource allocation for statistical quality of service provision in buffered crossbar switches

The buffered crossbar switch is a promising switching architecture that plays a crucial role for providing quality of service (QoS) in computer networks. Sufficient amount of resources—bandwidth and buffer space—must be allocated in buffered crossbar switches for QoS provision. Resource allocation based on deterministic QoS objectives might be too conservative in practical network operations. To improve resource utilization in buffered crossbar switches, we study the problem of resource allocation for statistical QoS provision in this paper. First, we develop a model and techniques for analyzing the probabilistic delay performance of buffered crossbar switches, which is described by the delay upper bound with a prescribed violation probability. Then, we determine the required amounts of bandwidth and buffer space to achieve the probabilistic delay objectives for different traffic classes in buffered crossbar switches. In our analysis, we apply the effective arrival envelope to specify traffic load in a statistical manner and characterize switch service capacity by using the service curve technique. Instead of just focusing on one specific type of scheduler, the model and techniques developed in this paper are very flexible and can be used for analyzing buffered crossbar switches with a wide variety of scheduling algorithms. Copyright © 2007 John Wiley & Sons, Ltd.