iRSDRR:一种全异步的基于输入排队Crossbar交换结构的调度算法

DRR(DualRound-Robin)[1]调度算法是一种公平、高效、硬件实现简单的基于输入排队Crossbar交换结构的信元调度算法。为了进一步改善这种算法的性能,该文提出了一种全异步的多次迭代DRR算法,即iRSDRR(iterativeRo-tatingStaticDualRound-Robin)。该算法在开始时,将所有的输入、输出仲裁器的指针全部设置为异步的,以后每个时隙静态地更新所有的仲裁器的指针。仿真结果表明该算法在不同业务流条件下的性能都优于DRR调度算法。

输入排队Crossbar架构下的矩阵模型及MM-LQF调度策略

输入排队Crossbar交换是高性能交换设备最为常用而关键的技术之一.本文建立了IQ-Crossbar架构下的矩阵模型,给出了IQ-Crossbar的状态矩阵、队长矩阵、到达矩阵和匹配矩阵的数学定义,并通过分析IQ-Crossbar的信元排队机理,提出和证明了队长矩阵迭代定理和状态矩阵迭代定理.该矩阵模型为分析IQ-Crossbar架构下的调度算法提供了理论依据.基于所建立的矩阵模型,在分析现有LQF调度算法优缺点的基础上,本文提出了一种新的调度策略MM-LQF,该策略的运算效率是LQF的3.72倍,支持的端口门限速率是LQF的2.35倍,在贝努利均匀流量重载条件下平均时延是LQF的1/2;在贝努利Diagonal流量条件下吞吐率为100%.

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

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

基于Crossbar的高性能输入排队调度算法对比分析

讨论了高速交换技术中排队调度策略主要输入排队调度算法。从高速网络发展研究的角度出发,基于Crossbar交换结构的高性能输入排队调度算法进行了比较;对该领域的最新研究进展进行了分析,提出了新的研究方向。

队列长度加权服务的输入排队交换结构匹配算法

针对输入排队交换结构调度问题,提出了队列长度加权服务匹配的思想.基本思路是匹配求解基于实现极大匹配的并行迭代算法,但对于每一个输入输出匹配,一次可以保持超过一个时隙的一段时间,其长度为对应的虚拟输入队列长度的加权函数.依据这一思想,设计了一种基于轮转仲裁器的队列长度加权服务匹配算法.通过实现复杂性的分析与性能评估,给出了优选的权重函数.所提方案以极大尺寸匹配算法近似的复杂性,取得与极大权重匹配算法近似的性能,在非均匀流量模式下也能达到接近100%的吞吐效率,明显优于iSLIP和EiSLIP算法,适合于高性能输入排队路由器的应用.

一类具有可变输入率的M/M/1排队模型

讨论了到达的顾客以概率α_k=1/(βk+1)进入M/M/1排队系统的可变输入率模型,获得了该模型的平稳分布和顾客的平均输入率,系统的平均服务强度,平均等待队长,系统的平均队长,系统的损失概率,顾客进入系统并接受服务的概率,单位时间内平均进入系统的顾客数,单位时间内平均损失的顾客数等相关指标,从而推广了文献[1]中的结果。

高速IP路由器中输入排队调度算法综述

高速IP路由器一般采用基于定长信元的交换结构,其可扩展性和性能分别受排队策略和调度算法的影响.基于输入排队策略的路由器具有良好的可扩展性,但需要一个有效的调度算法的支持,才能保证吞吐率和延迟等性能.主要讨论输入排队调度算法,将现有的调度算法分为4类:最大(无权重)匹配、最大权重匹配、稳定婚姻匹配和确定型调度.对每一类算法,从技术特点和性能指标两个方面进行比较和分析.最后给出了输入排队调度算法的发展趋势.

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

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

匈牙利算法在输入排队调度仿真中的应用研究

匈牙利算法是图论中完成二分图匹配的经典算法之一。输入排队的Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的。因而在调度算法理论研究中应用了二分图最大匹配的MaximumSizeMatching(MSM)和MaximumWeightMatching(MWM)算法成为各种调度算法性能的评价标准。文中介绍了匈牙利算法在输入排队调度算法仿真中的应用,并且得出相应典型算法的性能仿真曲线,从而为进一步研究调度算法打下理论基础。

输入排队中抢占式的短包优先调度算法

调度算法决定了输入排队交换结构的性能.本文根据Internet业务特征提出调度算法应保证短包的高优先级和低延迟.已有包方式调度中,长包信元的连续传输将造成短包长时间等待.为解决该问题,本文设计了一种低复杂度抢占式交换结构,并提出了相应的抢占式短包优先调度算法(P SPF) .短包优先可减小TCP流的RTT ,并由此提高TCP之性能.通过排队论分析和实际业务源模型下仿真可知P SPF取得短包近似为零的平均包等待时间,同时达到94 %的系统吞吐量.

基于双轮转指针的输入与交叉点联合排队型(CICQ)交换结构调度算法

CICQ交换结构因具有良好的分布式调度特性而成为构建太比特(Tbs)级以上交换机的一种理想选择.轮转型调度算法因硬件实现的简单性而得到广泛的研究,尽管此类型的调度算法在均匀流量下具有较高的吞吐率,然而在非均匀的流量下其性能则明显下降.指出了已有轮转型算法在非均匀流量下性能下降的原因,提出了一类基于双指针的轮转型调度算法,即每个输入调度器均有两个轮转指针(主指针和辅助指针).主指针对应的队列具有最高的调度优先级,算法可以根据各个队列的状态动态决定何时更新主指针,当主指针对应的队列被流控机制阻塞时,将根据辅助指针依次公平服务其他队列.实验结果表明,基于双指针的调度算法可以显著提高CICQ交换机在非均匀流量下的性能.

一种维序的基于组合输入输出排队的并行交换结构

提出一种按序排队(in-order queuing,简称IOQ)PPS体系结构,通过在分流控制器引入固定尺寸的缓冲区,实现负载在每个交换平面的均匀分配;中间层组合输入输出排队(combined input-and-output queuing,简称CIOQ)交换平面受控于中央调度器,在每个时间槽(timeslot),中央调度器将同一种匹配实施到每一个交换平面,称之为同步调度策略.可以证明,在该体系结构下,轮询(round robin)分派算法配合同步调度策略可以保证同一条流的信元按序从交换平面读出.进一步提出了严格最长队列优先同步调度算法,极大地减少了中央调度器需要维护的状态信息和信元重定序开销.与目前主流的PPS设计相比,IOQPPS(in-order queuing parallel packet switch)实现机制简单,易于硬件实现.模拟结果表明,IOQPPS具有最优的延迟性能.

输入排队结构交换机分组调度研究

以决定分组调度算法的交换结构为基础,从协调,减少和隔离输入排队交换结构中输入输出竞争裁决冲突的角度,分别讨论了VOQ,CIOQ,CICQ结构中的分组调度问题,并以当前最新的调度算法为例加以说明,进行了定性分析和定量对比,指出了具体有待研究的问题。随后讨论了最近才开始研究的光电混合结构中的分组调度问题。最后从交换结构和算法两个方面探讨了今后的研究方向和发展趋势。

具有可变输入率的M/M/1排队模型的一个注解

输入率可变的M/M/1排队系统是一种重要的排队论模型.在日常生活中,经常可以看到顾客到达某服务窗(台)前,发现顾客较多而产生犹豫,即要确定是否加入队列等候服务.一般而言,到达的顾客进入系统的概率随当时的队长而发生变化.本文讨论了到达的顾客以概率αk=a-k进入M/M/1排队系统的可变输入率模型,获得了该模型的平稳分布和相关指标.从而推广了文献[1]中的结果.

基于输入排队的调度算法

基于输入排队(IQ)调度算法的存储器带宽要求较低,因而能很好应用于高速路由器中。该文讨论了目前基于IQ的调度算法,对该领域的成果进行了较全面的总结,对当前研究的新进展进行了重点分析和比较,为进一步的研究提出了新的课题和思路。

Gigabit路由器中变长分组输入排队的神经网络调度

高速有效的分组调度算法是影响路由器性能的关键。该文基于神经网络,提出了一种输入排队的变长分组调度算 GigabitHopfield法,并给出了调度系统的结构。模拟运行显示该算法是高效的。同时提出了硬件实现的电路模型,以利于该算法的实际应用。

QNQL过程在排队论中的应用（Ⅰ）：输入过程（独立同分布情形）

本文在“相邻两个顾客到达时间间隔独立同分布”这个假定下，讨论输入过程Ｎ（ｔ）的拉氏变换及概率分布问题．

输入缓存ATM交换中多FIFO队列的最佳排队策略

对于每个输入端口具有多ＦＩＦＯ（先入先出）队列的输入缓存ＡＴＭ交换网，信元（Ｐａｃｋｅｔ）的排队策略是研究如何将进入输入端口的信元安排在不同排队队列中．最佳排队策略是给定信元排队规则，以使交换吞吐率（Ｔｈｒｏｕｇｈｐｕｔ）达到最大的策略．作者着重研究了输入端口具有２－ＦＩＦＯ缓冲队列的交换网，并从数学上证明了该交换网络的最佳排队策略。

多重工作休假的Geom/Geom/(Geom/Geom)/H双输入排队系统

本文研究多重工作休假的Geom/Geom/(Geom/Geom)/H双输入排队的问题.利用Markov链及矩阵几何解的方法,获得所研究的模型,建立稳态概率满足的方程组,进而推导出稳态队长分布、服务台消失的概率,推广了排队系统的模型及相关的结果.

ATM交换机混合服务规则输入缓存排队策略研究

文章在ATM交换机输入缓存队列中引入完全、门限服务规则[1,2],探讨混合服务规则下的输入缓存优先级特性。