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

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

在CICQ交换结构下PGPS调度算法的实现

基于CICQ结构提出了在输入排队结构下实现基于流的PGPS分组公平调度算法的方案,该结构在可管理的输入流下可提供接近100％的吞吐率。     

一种交错编码的多重门限调度算法

提出一种交错编码的多重门限调度算法(interleaving coded multi-threshold scheduling,简称ICMTS).该算法将前、后级队列门限标记交错编码作为权值表征输入调度过程前、后两级队列的整体调度需求,根据交错编码的权值对前级虚拟输出队列进行优化调度判决,并通过多重门限机制降低算法的硬件资源开销.采用流模型证明当加速因子为2时,ICMTS算法可获得100%的吞吐量,并给出ICMTS算法的工程简化设计方案,复杂度为O(logN).仿真仿真结果表明,采用ICMTS算法的工程简化方案即可获得比现有算法更优的调度性能.     

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

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

CICQ的高性能LQF_DRR调度算法

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

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

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

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

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

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

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

CMRR:一种新的混合式输入排队调度算法

在传统调度算法的基础上,提出了一种新输入排队调度算法——CMRR,混合式输入排队调度算法,仿真实验和理论分析表明,该算法的性能优于现有的iSLIP等调度算法。     

一种高速crossbar调度算法及其性能分析

分析了高速crossbar调度算法iSLIP在处理突发业务时性能严重恶化的原因。结合LQF/iLQF算法的思想,提出了又一种输入排队crossbar调度算法iPGQM。仿真结果表明:该调度算法在均匀业务流量下和iSLIP算法的性能基本相同;在突发业务的条件下,iPGQM算法具有更好的抗突发特性;特别在重负载的条件下,与iSLIP算法相比,不仅具有更高的吞吐量,而且平均延迟降低了10%左右。     

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

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

一种优化指针策略的输入排队调度算法

针对FIRM（fcfs in round-robin matching）算法在处理非均匀业务时,延时和丢包性能出现缺陷的问题,在FIRM算法的基础上设计并实现了一种优化指针策略的low—FIRM（longest oldest weighted FIRM）算法。该算法根据队列长度和队首信元等待时间的权值修改输入端口的轮询指针。使得权值大的队列趋于优先服务,从而优化了在非均匀业务下的调度性能。接着给出了low—FIRM算法的性能分析和仿真,与iSLIP（iterative round—robin matching with slip）算法、FIRM算法进行了比较。仿真结果表明,low—FIRM与经典算法相比,在均匀业务下的性能近似,而在非均匀业务下性能有了较大的提升。     

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

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

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

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

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

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

基于CICQ的动态重路由交换机制

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