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

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

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

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

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

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

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

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

一种高效自适应的CICQ交换机数据包切分机制

为了有效处理CICQ(Combined Input Crosspoint Queued)交换机中的变长数据包,通常采用切分-重组(Segmentation and Reassembly,SAR)机制将变长包切分为定长信元进行交换。针对目前已有切分方法在不同网络流量下交换效率低、灵活性差的问题,设计了一种基于CICQ交换机的高效自适应数据包切分机制。新机制的主要思想是根据输入端的队列状态实时改变切片大小,并采用相邻数据包合并切分的方式进行切片,以自适应网络环境中的不同流量和数据包长度。仿真结果表明,提出的数据包切分机制较传统切分方法有显著优势,与已有方法中表现最好的变长多包切分相比,在不同的流量下能获得更优的时延性能和系统稳定性。

一种双端口CICQ交换机的分组调度方案

Internet中的交换机面临着高速交换和提供QoS保证的双重挑战,前者要求交换机的缓存以线速工作,后者要求交换机能完全模仿输出队列交换机。目前交叉点缓存交换机仿真输出队列交换机的方案需要交换机内部加速2倍,对硬件实现要求较高。该文利用双端口技术,提出了一种新型的交叉点缓存交换机结构,理论分析说明,该变长分组交换机在无需内部加速的情况下能够仿真输出队列交换机,并且交叉点缓存的需求是有下界的,从而表明该交换结构适合高速交换。

CICQ的高性能LQF_DRR调度算法

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

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的动态重路由交换机制

针对现有路由交换机制存在计算复杂度过高以及端口争用问题,提出基于联合输入交叉节点排队交换结构的动态重路由交换机制。该机制依据互联网在路由拓扑层的路径多样化特点,在转发层为每个分组维护多个可选输出端口,并根据交换系统拥塞度实施分组动态重路由,从而实现网络流量的实时动态均衡。仿真结果表明,以该机制为构件的网络交换系统能获得良好的性能保障。

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

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

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

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

基于交叉点缓存状态的CICQ调度算法

针对现有的联合输入交叉点排队(CICQ)调度算法在设计时未充分利用交叉点缓存状态信息的问题,提出一种CICQ状态堆调度算法。该算法分布式地运行于CICQ结构的各个输入端口和输出端口。仿真结果表明,在均匀或非均匀流量模型下,基于该算法的CICQ结构都能获得与输出排队结构相当的性能,且具有较高的时延。

一种高性能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 类分组公平调席算法的方案,并通过仿真验证了这一方案的有效性。

一种基于CICQ支持区分QoS的新型并行交换系统解决方案

在对现有的PPS机制分析研究的基础上,提出一种基于CICQ支持区分QoS的新型并行交换系统PSVIOQ-CICQ解决方案。该方案设计中采用虚拟队列技术,输入缓存设置成N个VOQ,与负载均衡器协同完成负载均衡分配,输出缓存设置成N个VIQ,与分组整合器协同完成信元的按序转发并提供QoS保障。仿真表明PSVIOQ-CICQ具有较好的公平性和负载均衡性,整体达到了设计目标要求。

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

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

CICQ交换的流控实现机制和交叉点缓存容量分析

传统的基于crossbar的输入排队交换结构在提供良好的QOS方面存在很大的不足,而CICQ(combinedinputandcrosspointbufferedqueuing)交换结构与传统的交换结构相比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。文章分析了CICQ结构的流控实现机制,讨论了基于信用的流控机制的开销和实现方案,对crosspoint缓存容量作了分析,给出了在各种存储器写入条件下,保持交换结构100%吞吐率所需的最小缓存容量。

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

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

基于CICQ结构的变长分组交换调度算法研究

在Crossbar交换单元的交叉节点加少量缓存的C ICQ(Comb ined Input-Crosspoint-Queued)交换结构是一种调度简单并能够支持变长分组的交换结构。但是,简单的权重轮询调度算法会造成输入队列服务不公平性。为此,提出了一种改进的权重调度算法———最小配额优先算法(MQF:M in imum Quotient F irst)。通过选择恰当的分组队列调度配额,充分发挥了C ICQ结构先天性支持变长分组交换的优势。通过仿真证明,该算法在均匀和非均匀业务到达下,可以获得近100%的吞吐率和较低的平均分组时延。