A QoS-aware scheduling algorithm for combined-input-crosspoint-queued switch

In this paper, we study the quality of service requirement and guaranteed-rate scheduling problem for combined-input-crosspoint-queued (CICQ) switches. Using crosspoint buffers between input queues and output ports, the input and output scheduling can be decoupled in CICQ switches. Here we propose a new guaranteed-rate scheduling algorithm which is divided seperately into input and output scheduling. Simulation results show that our algorithm can perform better than existing scheduling schemes in both packet loss and jitter control.

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

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交换结构调度算法

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

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

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

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

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

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

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

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

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

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

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

CICQ的高性能LQF_DRR调度算法

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

一种基于重端口的CICQ交换机方案及行为分析

为了使交换机保证服务质量并提高交换速率,提出了一种新型组合输入交叉点排队(CICQ)的交换结构,并运用理论证明的方法分析了它的性能.分析结果表明,重端口数为2的CICQ交换结构能在无需内部加速的情况下精确地模仿输出队列交换机,从而解决了服务质量与交换速率之间的矛盾.

基于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结构调度算法

在Crossbar交换单元的交叉节点加少量缓存的组合输入交叉节点排队(CICQ)结构,具有调度算法简单、性能优良、适于高速大容量路由器实现的特点。在总结现有研究成果的基础上,提出了一种避免仲裁指针同步的异步指针轮询算法。该算法将所有的输入、输出仲裁器的指针全部设置为异步,每个时隙静态地更新所有的仲裁器的指针,以达到网络指针去同步的目的。仿真结果表明,该算法在保持无权重算法简单性同时对不同业务流下的时延和吞吐率性能均有明显改善。

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

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

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

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

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

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

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

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