一种无权重的高性能CICQ结构调度算法

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

CICQ的高性能LQF_DRR调度算法

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

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

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

支持多优先级分组交换调度算法研究及其调度器设计

输入缓存交换结构的特点是缓存器和交换结构的运行速率与端口速率相等、实现容易,但存在队头阻塞。如果采用虚拟输出排队方法和适当的分组调度算法可予以消除,使吞吐率达到100%。文章首先研究讨论了并行迭代匹配算法,滑动迭代匹配调度算法的基本原理、迭代仲裁步骤及其硬件实现;对高速分组交换调度算法的性能进行了分析比较。然后给出了在高速输入队列交换机中实现多优先级调度算法的调度器设计与实现方案。经设计实现证明高速分组交换调度算法不仅硬件实现简单,而且具有良好的特性。     

一种基于FPGA实现的高速多路交换开关

多路交换开关是高性能交换部件的核心。本文描述了基于Xilinx公司Virtex-Ⅱ系列FPGA的特点设计和实现的一种高速多路交换开关,它由输入信道组织、内部无阻塞crossba r交换和仲裁调度器三部分组成。仲裁调度器的设计是多路交换开关的关键,申请和仲裁许可的完成时间关系到整个实现的综合频率和性能。我们提出一种改进的行波流水仲
裁器设计,它公平有效,工作频率达到135MHz,在实际应用中效果良好。     

高速分组交换网络中调度器的设计

为了满足迅猛发展的网络业务对网络服务质量提出的更高要求,使用高速分组网络交换机中的队列调度器可以有效地提供高质量的网络服务。通过采用分级式队列调度和四种队列调度算法有效地实现了队列调度器的设计。并且深入地比较和分析了队列调度器中多种队列调度算法的优缺点,尤其是对DRR调度算法进行了优化和改进。最后。对所设计的电路进行了仿真验证和电路综合,结果表明该调度器可以满足网络对服务质量的更高要求,并且能够应用到高速分组交换网络的调度器设计中。     

适合星载交换机的调度算法

针对卫星有效载荷处理速度和存储容量受限的情况,提出适合星载交换机的修正DRR调度算法.采用OPNET网络仿真软件,建立低轨卫星星座系统交换机模型,应用修正DRR算法,验证该算法性能.结果表明在星载交换机资源受限情况下,即使业务流量较大,修正DRR算法也可以保证无掉包现象发生,且交换时延低于10 ms,复杂度为O(1).     

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

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

队列长度加权服务的输入排队交换结构匹配算法

针对输入排队交换结构调度问题,提出了队列长度加权服务匹配的思想.基本思路是匹配求解基于实现极大匹配的并行迭代算法,但对于每一个输入输出匹配,一次可以保持超过一个时隙的一段时间,其长度为对应的虚拟输入队列长度的加权函数.依据这一思想,设计了一种基于轮转仲裁器的队列长度加权服务匹配算法.通过实现复杂性的分析与性能评估,给出了优选的权重函数.所提方案以极大尺寸匹配算法近似的复杂性,取得与极大权重匹配算法近似的性能,在非均匀流量模式下也能达到接近100%的吞吐效率,明显优于iSLIP和EiSLIP算法,适合于高性能输入排队路由器的应用.     

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

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

ESSDRR调度算法的性能仿真与分析

鉴于已有的分组调度算法难以同时满足良好的QoS保证特性和算法的低复杂性,结合WF2Q和DRR两种算法的优点,提出了一种基于均匀服务序列的DRR算法——ESSDRR(Even Service Sequence-based Deficit Round-Robin)。为了评价其优劣性,在同一仿真条件下利用NS2对该算法以及三个类似算法做了大量仿真实验,主要考察并比较了各算法的端到端时延、短期吞吐率等性能指标。实验结果显示,ESSDRR具有良好的公平性、低时延特性及较低的复杂性。     

时隙间迭代的输入队列交换机Round-Robin调度算法

输入队列因具有良好的可扩展性而广泛应用于高速交换机和路由器中,但输入队列需要精心设计调度算法以获取较好的性能.Round-Robin算法因其简单性和并行性而得到广泛的研究,但现有的Round-Robin算法在突发流量和非均匀流量下的负荷-延迟性能较差.提出了调度决策在时隙间进行迭代的思想,并利用队列长度具有随机性的特点设计了能近似最大匹配的Round-Robin算法--iSLOT.仿真结果表明,iSLOT不仅在均匀流量下是稳定的,在非均匀流量和突发流量下的吞吐率及延迟性能均远好于现有的Round-Robin算法.     

蓝牙技术中DRR算法的改进方案和应用

DRR算法是为了解决在路由器中多用户情况下的资源合理分配问题而提出的。由于Bluetooth系统帧长可变以及存在SCO链路时特定的收发时序，使得应用于蓝牙系统上的DRR算法需要作出改进。改进后的算法蓝牙主设备可以根据数据流量的变化，进行业务活动规划，文章首先举出蓝牙业务分派中的实际问题，提出了DRR算法的改进方案，然后对方案进行理论分析，最后仿真结果表明了此算法对系统性能的改善。     

A new optimal approach for multiple optimisation objectives grid resource allocation and scheduling

The article considers the resource allocation and scheduling problem in a grid computing environment. The article proposes system optimisation scheduling (SOS) that provides a potential solution of joint optimisation of objectives for both the resource and application layer, which combine both application-oriented and resource-oriented scheduling benefits. Grid systems will strive to find an optimal relation between user satisfaction and resource utilisation. Utility functions are used to express grid user's Quality of Service requirement, resource provider's benefit function and system's objectives. In order to verify the efficiency of the proposed scheduling algorithm, we compare the performance of application optimisation scheduling, resource optimisation scheduling, SOS with a traditional Round-Robin algorithm. The simulations study the effect of the request rate and task-to-resource ratio on the different scheduling algorithm.     

基于平均分配原则的任务调度算法

在分布式系统中,常出现一些处理机处于重载,同时另一些处理机却处于轻载或闲置状态。针对这种情况,为了更好地合理分配任务,结合加权轮转调度算法,提出一种基于平均分配原则的任务调度算法,尽量实现系统的负载平衡,并应用实例来加以证明。     

一种新型的网络包公平调度算法的研究*

针对现有分组轮转法的局限,提出一种新的分组策略——虚拟权重队列分组策略。在这个新的分组策略的基础上,结合DRR和WF2Q,提出了虚拟权重队列分组轮转法。仿真实验表明,虚拟权重队列分组轮转调度算法比现有的分组轮转法拥有更好的延时性能和公平性能。     

异构环境下改进的LATE调度算法

针对异构环境下LATE算法在选择备份任务及执行节点时的不足,提出一个改进的IR-LATE调度算法。算法通过计算为剩余完成时间最长、最需要备份的慢任务启动备份,并将其按负载不同进行分类,结合轮询算法,将备份任务分配到负载最小且成功/负载比高的节点上执行。实验结果表明,该算法与LATE算法比较,有效的将作业完成时间缩短了30%左右,提高了执行效率,进而促进系统的负载均衡。