基于VOQ输入缓存交换系统调度算法研究

基于VOQ缓存策略的信元调度算法是提升交换系统性能的关键因素。介绍了3种富有代表性的调度算法iSLIP算法、iLQF算法和DPA算法。iSLIP算法易于硬件实现,不大于log2N次迭代即可实现收敛,但对于突发通信效率不高,适用于中小规模的高速交换结构;iLQF算法调度效率高,但硬件实现较为困难,且时延较大,目前应用较少;DPA算法可以用简单的组合逻辑实现,时延小,但效率不高,适用于重载大规模的高速交换结构。     

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

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

输入队列交换的公平可扩展调度系统

提出了一种基于输入队列交换的公平可扩展网络调度系统FSSA.通过将若干个容量较小的调度器合理连接并使其协同工作,构成多端口大容量网络交换调度系统,解决了单个调度器容量和端口数受集成电路工艺限制的问题.FSSA不仅速度高、规模可扩展而且易于硬件实现.环型连接、管线工作及公平调度技术的采用使FSSA在性能方面得到了进一步优化.仿真结果显示,FSSA的性能可与基于iSLIP、DSRR等算法的单片调度器相比拟,尤其在流量较大时,FSSA的性能明显优于单调度器性能.     

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

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

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

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

高速信元交换调度算法研究

输入缓存交换结构的特点是缓存器和交换结构的运行速率与端口速率相等、实现容易,但存在队头阻塞(HOL),其吞吐率只有约58%.采用虚拟输出排队方法(VOQ)和适当的信元调度算法可消除HOL,使吞吐率达到100%.本文通过仿真对几种调度算法:PIM、iSLIP和LPF进行了全面地研究、比较和评价.     

一种具有O信息复杂度的高速crossbar调度算法

本文提出一种可扩展性强的高速crossbar调度算法——iRGRR(iterative request-grant-based round-robin),它通过简化处理流程和减小调度开销,克服了传统算法(例如iSLIP^[1]、PIM^[2])可扩展性差的缺陷.iRGRR将控制信息复杂度从O(N)级大大减小到O(logN)级,具有良好的可扩展性,可应用于太比特交换机/路由器中.仿真结果表明,在各种不同的均匀和非均匀业务流下,iRGRR能够获得与iSLIP几乎相同的性能.另外,iRGRR比iSLIP具有更好的公平性以及更加易于用硬件实现.     

一种基于全局调度的改进CLOS结构及其调度算法

现有的关于Clos交换结构的调度算法在关注调度性能的同时,逐渐忽略了其在硬件实现上的复杂度。该文根据一款星载交换芯片的设计实现,提出了一种改进型的Clos结构,且在此基础上设计了一种硬件实现简单且能实现极大匹配的调度算法。     

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

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

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

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

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     

iFONA:光突发交换中的低延时BHP仲裁算法

提出一种新的仲裁算法-iFONA。并且通过计算机仿真,证明了该算法在突发情况下能够降低BHP平均等待时间,性能明显优于iSLIP等经典算法。     

一种基于输入缓冲交叉开关的调度算法

研究了交叉(Crossbar)开关的架构和缓冲策略。在已有的循环优先级多次匹配(RRM)算法和指针滑动多次迭代循环优先级匹配(iSLIP)算法的基础上提出了一种基于优先级列表的轮询调度(PB-RRM2)算法,该算法每次迭代只需要2步,减少了算法的调度时间,提高了Crossbar开关的运行速度。同时采用优先级列表的轮询(Round Robin)指针修改方式消除了指针的同步,提高了吞吐量。理论分析和仿真试验表明,算法在吞吐量和平均信元时延方面与iSLIP算法相当。     

STF：PROVIDE RATE GUARANTEES IN INPUT—QUEUED SWITCH

A QoS-aware input-queued scheduling algorithm,called Smallest Timestamp First (stf),is propsed,which is improved upon is LIP and can allocate bandwidth among imputs sharing a common output based on their reservation by assigning suitable finishing timestamps to contending cells .STF can also provide isolation between flows that share a common output link.Misbehaving flows will be restricted to guarantee the behaving flow^s bandwidth .Simulations prove the feasibility of our algorithm.     

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).