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

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

一种维序的基于组合输入输出排队的并行交换结构

提出一种按序排队(in-order queuing,简称IOQ)PPS体系结构,通过在分流控制器引入固定尺寸的缓冲区,实现负载在每个交换平面的均匀分配;中间层组合输入输出排队(combined input-and-output queuing,简称CIOQ)交换平面受控于中央调度器,在每个时间槽(timeslot),中央调度器将同一种匹配实施到每一个交换平面,称之为同步调度策略.可以证明,在该体系结构下,轮询(round robin)分派算法配合同步调度策略可以保证同一条流的信元按序从交换平面读出.进一步提出了严格最长队列优先同步调度算法,极大地减少了中央调度器需要维护的状态信息和信元重定序开销.与目前主流的PPS设计相比,IOQPPS(in-order queuing parallel packet switch)实现机制简单,易于硬件实现.模拟结果表明,IOQPPS具有最优的延迟性能.

基于CICQ的新型并行交换结构研究

提出一种基于CICQ的支持区分服务的分布式并行分组交换结构(CDPPS,distributed CICQ based diffServ supporting parallel packet switch)。通过使用多个低速交换设备来构建支持区分服务的并行分组交换,CDPPS解决了在高速环境下构建可行的区分服务调度问题。由于可以在不做任何改动的情况下将CICQ结构作为中间层平面,提高了现有资源的利用率。采用全分布式的调度算法,CDPPS避免了系统的通信开销,降低了硬件实现复杂度。理论分析和实验仿真表明,CDPPS能为各类业务提供满意的服务质量。

可行的基于CIOQ的并行分组交换结构

针对传统并行分组交换结构存在的平面可扩展性问题,提出一种可行的分布式并行分组交换PDPPS(practical distributed parallel packet switch)。在端口数为N和中间层平面数为K的情况下,PDPPS的复用器中只需要维护大小为NK的高速缓存,就能保证每条流按序输出。理论分析和仿真结果表明,PDPPS的性能优于使用OQ(output queuing)结构作为中间层平面的分布式并行分组交换结构VIQ PPS(virtual input queuing parallel packet switch),略微低于集中式PPS和IOQ PPS(in-order queuing parallel packet switch)。但相对于集中式PPS,PDPPS使用了更为通用且易于实现的CIOQ(combined input and output queuing)作为中间层平面;相对于IOQ PPS,PDPPS使用了分布式调度算法,从而消除了系统的通信开销,并且PDPPS极大地降低了所需的高速缓存数量。

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

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

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

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

分组交换网络中的调度算法研究分析

该文讨论了分组交换网络中的调度算法,从交换结构模型的角度对现有的调度算法进行了分类和比较,对该领域的成果进行了较全面的总结,对当前研究的新热点进行了重点分析,为进一步的研究提出了新的课题和思路。

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

针对现有的联合输入交叉点排队(CICQ)调度算法在设计时未充分利用交叉点缓存状态信息的问题,提出一种CICQ状态堆调度算法。该算法分布式地运行于CICQ结构的各个输入端口和输出端口。仿真结果表明,在均匀或非均匀流量模型下,基于该算法的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算法的工程简化方案即可获得比现有算法更优的调度性能.

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

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

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

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

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

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

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

在对现有并行分组交换(PPS)分析的基础上,将标识的概念引入交换结构,提出了一种基于标识支持区分服务质量(QoS)的PPS调度机制.该机制以业务类为单位管理网络数据流,采用按序排队的思想解决保序问题,在汇聚模块设置少量缓存,采用双指针轮询算法实现区分QoS保障,保证了交换对高层不同业务类的有效支持.仿真实验结果表明,该机制在满负载情况下可获得高达99%以上的吞吐率,在过载情况下根据预定带宽分配输出链路带宽,确保分组具有时延的上界,能够比较均衡地将负载分配到各中间交换平面.