一种交叉点小缓存CICQ交换机高性能调度算法

CICQ(combinedinput crosspoint queued/queuing)结构具有内部无需提速及输入和输出的分组调度可以分布并行执行的优点,使用RR(round robin)算法在高性能交换机设计中具有独特优势·然而,CICQ交换机使用RR算法在非均匀流量下不能达到100%的吞吐率·RR-RR算法在非均匀流量下性能有两个关键因素组成:中央缓存容量大小和输入端长队列未能及时服务导致的服务损失·基于理论分析,提出了一种小缓存高性能调度算法,仿真结果表明,即使在1个信元缓存的情况下新算法在均匀与非均匀流量下均能达到100%吞吐率·新算法仅具有O(1)的复杂度,保持了RR-RR算法简单有效特性,同时克服了RR-RR算法在非均匀流量下的不稳定性·

一种基于最长队列预测的CICQ交换结构调度算法

CICQ(Combined Input Crosspoint Queued)是一种在crossbar交叉点加入少量缓存的交换结构,具有无需内部加速比及分布并行调度的特性。为了自适应网络环境中各种业务流量,提高在非均匀流量下的性能,该文提出了一种基于最长队列预测的高效CICQ交换结构调度算法——RR-LQD(Round Robin with Longest Queue Detecting)。RR-LQD算法复杂度为O(1),具有良好的可扩展性;通过预测局部"最长"队列并尽力为其服务,保持调度中队列长度的均衡,能够适应各种非均匀流量的网络环境。仿真结果表明:在各种均匀和非均匀流量下,RR-LQD算法均能达到100%的吞吐量,并且具有优良的时延性能。该文使用FPGA芯片实现了RR-LQD算法仲裁器,能够满足高速、大容量交换结构的设计需要。

CICQ交换结构的调度算法研究

研究了基于缓冲交换结构的各种调度算法,并基于CICQ(combinedinputandcrosspoint-queued)的交换结构提出LQF_LQF算法.仿真结果说明该算法在均匀分布和突发业务源的情况下都能近似达到输出排队的时延性能.

CICQ交换机中一类服务可保障的调度策略研究

具备QoS保障能力的快速调度算法是高速交换机的首选.基于EPFTS(Ethernet-oriented physical frame timeslot switching)和CICQ(combined input-crosspoint-queued)交换技术的特点,提出了一类新的调度策略———TRWFS(ti meslot reservation weighted fair scheduling).为确保各端口对上保障业务的预留带宽,TRWFS以各端口对上保障业务预留时槽数为调度权重,以优先调度保障业务和平衡各保障业务的盈余时槽(surplus timeslot,定义为现实系统和理想系统之间的服务差额)为业务调度准则.基于该调度策略进一步提出了两种实现算法———TRWFS-I和TRWFS-II,总体上使实现TRWFS的时间复杂度降至O(1).性能分析和仿真实验结果均表明两种调度算法都达到了服务保障的设计目标,仿真实验结果还表明CICQ排队方式下与其他调度算法相比,TRWFS和轮询调度综合的调度机制具有交叉缓存容量要求更低的优点.

一种基于CICQ支持组播公平服务的调度策略

针对目前基于CICQ(combined input and crosspoint queuing)支持组播的调度策略在公平性和实时性能保障方面存在的不足,提出了一种简单、高效的支持组播公平服务的分层平滑轮询调度算法——mFGSR(multi-cast fair service and group smoothed round robin)。mFGSR依据组播业务流的权重进行分组和平滑调度,具有良好的可扩展性和公平性能,能够适应实时业务的性能需求。理论分析和仿真结果表明,该算法具有良好的时延、吞吐量和公平性能。

混合优化的CICQ交换结构调度算法

联合输入端和交叉点排队(CICQ)的Crossbar是一种性能优于传统结构的交换结构,对CICQ交换结构的特点进行了讨论并提出一种新的混合优化调度(HOPS)算法,算法在输入端调度时采取混合优化的策略,首先尽力保证系统的吞吐率性能,然后根据长队列优先的原则优化系统的时延性能。算法以轮询调度为基础,最多只在输入端进行一次比较操作,其算法复杂度仅为O(1),实现简单。通过流体模型证明该算法对满足强大数定律的许可输入流量能够达到100%的吞吐率性能。仿真结果进一步表明HOPS调度算法在各种流量模型下都能稳定运行,且具有良好的时延和吞吐率性能。

基于标识支持区分QoS的CICQ调度机制

为了在高速环境下对不同业务提供更好的区分服务质量QoS(quality of service)保障,将标识的概念引入交换结构,提出一种基于标识支持区分QoS的CICQ(combined input and cross-point queued)调度机制.该机制采用基于标识和预约带宽约束的流控机制,以业务类为单位管理网络数据流,保证了交换对高层不同业务类的有效支持,理论分析和仿真实验一致.这表明该机制具有良好的时延性能,在过载情况下根据预定带宽分配输出链路带宽,保持了各业务类的相对公平性.

一种支持DiffServ模型的CICQ调度策略

结合大规模接入汇聚路由器需要对不同汇聚业务流进行不同的处理这一实际需求,基于CICQ交换结构,该文给出了一种支持DiffServ模型的调度策略(DS),该算法以"节点行为"方式对业务流进行调度。和以往算法相比,DS采取了分布式的控制策略,并且具有较低的时间复杂度,工程上更易实现。仿真结果表明,DS不仅能够为EF和AF业务提供带宽保证,而且具有良好的时延性能。

卫星CICQ交换系统调度算法研究

联合输入交叉点排队(CICQ)交换结构由于在交叉点引入少量缓存,可以将输入端口和输出端口进行有效隔离,降低调度算法的复杂度,并适用于大容量交换。为此,研究基于交叉点缓存的各种调度算法和基于CICQ的交换结构,提出一种基于流量控制的FCSA算法,通过OPNET仿真分析表明该算法在均匀分布和突发业务源的情况下具有较好的时延性能,并且复杂度低,吞吐量大。将该算法应用于星载交换机,结果表明,该算法可以满足星载交换机多业务突发传输的特点,易于硬件实施。

CICQ交换结构中队列长度均衡仿真研究

CICQ(Combined Input Crosspoint Queued)交换结构具有分布并行调度的特性,是高速、大容量路由器设计的理想选择。对现有各种CICQ调度算法研究发现,在非均匀业务流下输入队列服务不均衡是造成CICQ稳定性、吞吐率等性能下降的根本原因。为此,提出了一种均衡队列长度的调度算法——MUIQF(Most Urgent Input Queue First),仿真结果表明:在各种均匀和非均匀流量下,MUIQF算法均能保持输入队列长度的均衡,能够达到100%的吞吐率,并且具有良好的稳定性和时延性能。

CICQ交换结构的调度算法分析

分析了影响Crossbar性能的三种阻塞及解决途径,研究了CICQ交换结构的4种调度算法:RR-RR算法、LQF-RR算法、OCF-OCF算法、MCBF算法,探讨了它们的优点及不足。

(TCBF):CICQ中一种复杂度低的高效算法

随着芯片集成度快速提高,带有交叉缓存(crosspoint buffer)的cicq(Combined Input and Crossbar Queued switch)交换机引起了人们的广泛关注和研究兴趣.分析了cicq模型的性质后,提出了在cicq中瞬时加速比和有效加速比的概念,指出瞬时加速比也是一种资源.分析了输入队列和输出队列对cicq系统性能的影响,在此基础上提出了基于cicq的输入仲裁算法-TCBF(Thresh-hold Crosspoint Buffer First),并进行了仿真实验,针对非均匀业务模式(nonuniform)的情况作了改进.实验证明,这种时间复杂度为O(1)的算法有100%的吞吐率,有和OQ-N近似的输出延迟.并且非常易于硬件实现.最后讨论硬件实现办法.

CICQ的高性能LQF_DRR调度算法

通过研究4种经典的CICQ调度算法,提出一种高性能的LQF_DRR交换调度算法。该算法在输入端采用最长队列优先调度策略,在输出端采用DRR调度机制,通过输入端与输出端的相互配合,优先服务异常队列,以减小交换结构输入端长队列对算法性能的影响。仿真结果证明该算法在各种流量下都有良好的时延性能和稳定性。

高性能CICQ仿真平台的设计与实现

交换结构与调度策略对于核心路由器的性能及网络业务流的QoS保证具有重要的意义。基于目前流行的带缓存交叉开关交换结构(CICQ),采用系统级设计方法和面向对象技术,设计并实现了用于研究基于带缓存交叉开关构建的交换结构与调度策略的仿真平台-SPES。设计上实现了业务流、交换结构和调度策略三者之间的分离,具有良好的可继承与可扩展性。最后给出了在该平台下,CICQ流行调度策略的仿真结果,展示了SPES的优良性能。

一种高性能CICQ交换结构调度算法

在CICQ的两类调度算法中,无队列状态信息调度算法相对简单,但在非均匀的业务流环境下性能无法令人满意;基于队列状态信息的调度算法在非均匀的业务流环境下性能良好,但算法复杂度高。针对以上不足,提出一种低复杂度的高效调度算法CRR-FRR。新算法无需比较和排序,硬件实现简单,具有良好的可扩展性。仿真结果表明,无论是在均匀分布还是在突发业务源的情况下,均具有良好的时延性能。

一种保证服务质量的大型CICQ交换结构

现代包交换机需要具有为不同的数据流提供不同的服务质量(QoS)的能力,同时随着网络规模和业务的增长,交换机的线卡数目会大量增加,线卡和交换矩阵需要分布在多个线柜中,它们之间的距离可能达到数十米,因此在设计交换机时不能忽视交换机内部的往返时延(RTT).该文从这两个方面来讨论支持大RTT的组合输入和交叉点缓存排队(CICQ)交换结构实现服务质量保证问题,提出了基于扩展交叉点缓存的支持大RTT并提供基于流的性能保证的CICQ(CICQ-ECBs)交换结构,给出解除扩展交叉点缓存(ECB)阻塞机制,并用Counting方法证明了2倍加速的CICQ-ECBs交换结构能够实现PIFO-OQ仿效.

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

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

基于Work-Conserving的CICQ结构中单组播分组调度算法

基于联合输入交叉队列(CICQ)结构提出了一种新的均衡交叉节点缓存单组播混合调度算法,即单组播交叉缓存均衡(MUCB)算法,该算法不同于现有的基于业务状态如队长和/或等待时间的调度算法,而是尽力使交换机最大程度地工作于工作保持(Work-Conserving)状态,其方法是尽量均衡CICQ交叉节点的缓存占用。同时,算法充分考虑单组播业务差异性及CICQ结构下输入输出调度间的影响关系。仿真结果显示,在不同组播业务比例条件下,与现有CICQ结构中主流的单组播混合调度算法相比,MUCB算法显著提高了单组播业务总体的通过率及分组平均时延性能。

CICQ结构中逼近work-conserving的分组调度算法

联合输入交叉点排队(CICQ)结构的分组调度算法是一个得到了充分研究的领域,但已有算法在吞吐率和分组平均时延方面与输出排队(OQ)的结果相比,依然不够令人满意,其关键在于OQ交换机可以工作于work-conserving状态。不同于已有的研究,本文提出了以使得交换机最大程度工作于work-conserving状态为目标的新的研究思路,给出并证明了CICQ交换机实现work-conserving状态的充分且必要条件。以此为基础,提出了一种新的CICQ输入调度的算法即交叉缓存队列均衡(CQB)算法,并将经典的最大队长优先(LQF)算法用于输出调度,结合得到CQB-LQF算法。仿真结果显示,与经典的及最新的CICQ分组调度算法相比,CQB-LQF算法显著提高了吞吐率及分组平均时延性能。

在CICQ交换结构下实现分布式的输入排队DRR分组公平调度

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