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

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

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

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

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

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

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

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

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)的交换结构,并运用理论证明的方法分析了它的性能.分析结果表明,重端口数为2的CICQ交换结构能在无需内部加速的情况下精确地模仿输出队列交换机,从而解决了服务质量与交换速率之间的矛盾.

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

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

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

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

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

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

一种基于PRIRR-PRIRR算法的CICQ交换机

研究了基于交叉点缓存的各种调度算法和基于CICQ的交换结构,运用非稳定VOQ和非稳定交叉点缓存两个概念,提出了PRIRR-PRIRR算法,保证了非稳定VOQ被优先轮询。仿真分析表明,该算法在非均匀分布业务源的情况下具有良好的平均时延性能和稳定性能,彻底解决了RR-RR算法在非均匀业务源下的不稳定缺陷。

CICQ的高性能LQF_DRR调度算法

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

一种基于CICQ支持区分服务质量的分布式动态双轮询调度算法

为了在高速交换中提供具有服务质量保证的调度器,基于联合输入交叉点排队交换结构提出了一种支持区分服务质量的分布式动态双轮询调度算法.分布式双轮询调度算法不仅能有效处理不同业务类的突发数据,比较迅速地缓解网络的拥塞状况,具有良好的时延性能,而且又保持了各优先业务类的相对公平性,能够更好地支持区分服务,从而实现服务质量保障.

高性能交换结构中的输入排队调度算法综述

文章对各种输入排队调度算法进行了比较详细地分析,并着重对算法的吞吐量、稳定性、公平性、延迟控制、组播支持等方面进行了分析,同时对各种输入排队调度算法作了总结并且指出了进一步研究的方向。

一种支持变长分组的CIOQ交换结构

在分析了组合输入输出排队结构的基础上,对传统CIOQ(CombinedInputOutputQueued)的输出队列进行扩展和在内部交换结构中采用并行传送的方式,实现了交换调度的分布式操作和内部无加速的CIOQ交换;又通过将输出队列的状态信息反压到输入端和在输出端采取基于整包调度的算法,实现了对变长分组的交换,减小了定长信元交换中分组切割和重组的开销。

基于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算法显著提高了吞吐率及分组平均时延性能。

基于缓解HoL堵塞的单组播混合调度算法

针对联合输入交叉队列(CICQ)结构的单组播混合调度研究不多,且没有针对性研究头分组(HoL)堵塞问题,提出了以缓解HoL堵塞为目标的一种新的单组播混合调度算法,即单组播低Ho L堵塞(MULHB)算法,使交换机尽量逼近work-conserving状态。该算法还充分考虑了单组播之间的差异性,利用权重裁决单组播之间的竞争,避免"饿死"现象发生。同时,还给出了一种新的组播分组入队算法,即动态组播分组入队(DMQ)策略,该策略在不乱序的前提下,允许新到达分组选择合适的队列入队。仿真结果表明,在不同业务下,DMQ-MULHB算法的通过率及平均时延均优于现有主流的单组播混合调度算法,尤其在非均匀业务下,该算法性能接近输出排队(OQ)调度。

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

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

高性能交换机最新调度算法分析

随着互连网络规模不断扩大 ,以及各种大数据量传输应用的出现 ,对核心路由器和交换内核的性能要求越来越高。本文综述了交换内核研究领域的发展情况 ,介绍了基于交叉开关内核的各种单播和组播调度算法 ,既回顾了早期的算法 ,又对较新的算法做了阐述 ,以及对这些算法的对比分析 ;同时也对最新发展和研究方向做了一下讨论。

高性能组合输入交叉点排队交换机

运用非稳定虚拟输出队列和非稳定交叉点缓存的概念,提出了基于优先级轮询方案的组合输入交叉点排队方案,并通过数值仿真,详细研究了该方案的时延性能和稳定性能.仿真结果表明,在非均匀分布业务源的情况下,优先级轮询方案比普通轮询算法具有更好的平均时延性能和稳定性能.该研究成果为设计交叉点缓存交换机提供了理论依据.