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

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

一种支持DiffServ模型的全分布式调度算法

调度算法设计对于网络路由设备实现区分服务(DiffServ)模型的单跳行为(per hop behavior,简称PHB)至关重要.现有支持DiffServ模型的调度算法普遍基于输出排队(output queued,简称OQ)或是输入排队(input queued,简称IQ)交换结构进行设计,均无法在高速环境下提供高性能的调度.基于联合输入/交叉节点排队(combinedinput-crosspoint-queued,简称CICQ)交换结构提出一种支持DiffServ模型的全分布式调度算法DDSS (distributed DiffServ supporting scheduling),并通过理论分析对其公平性进行了验证.DDSS算法采用基于预约带宽的逐级流量控制机制实现所有预约带宽在快速转发(expedited forwarding,简称EF)业务与确保转发(assured forwarding,简称AF)业务之间的分配,采用优先级调度机制为EF业务提供低延迟服务,算法复杂度为O(log N).仿真结果表明,DDSS算法具有良好的时延性能和公平特性,与现有算法相比,能够更好地支持DiffServ模型.     

基于网络编码交换系统仿真平台的设计与实现

网络编码已被证明可以优化交换系统传输效率,然而不被传统交换系统的结构所支持。基于流行的Crossbar结构,采用模块化设计方法,实现了基于网络编码交换系统仿真平台—NCSPS(Network-Cod ing based S imu lation P latform for Sw itches)。该平台实现了输入、输出、交换单元、调度策略、数据生成和数据统计各模块的"松耦合",达到了业务流、交换结构和调度策略的分离,具有一定的配置灵活性和扩展性。用户通过不同的参数设置,实现各种仿真环境和条件。最后通过对传统交换和编码交换的仿真实验,展示了编码交换的良好性能,验证了仿真平台的合理性。     

支持公平服务的CICQ分层混合调度策略

为到达业务提供性能保障是衡量一个交换系统性能的重要参考.针对现有联合输入交叉点排队交换结构(CICQ)调度策略缺乏基于流的服务质量保障,探讨了在CICQ交换结构实施基于"流"调度的可能性,提出了一种能够为到达业务流的提供公平服务的分层混合调度策略(HSFS).HSFS采用分层的混合调度机制,每个输入、输出端口可独立地进行变长分组交换,其复杂度为O(1),具有良好可扩展特性.理论分析结果表明,HSFS无需加速便能为到达业务提供时延上限、速率和公平性保障.最后,基于SPES对HSFS的性能进行了评估.     

基于输入端无冲突算法的面向输出排队的交换结构

该文提出了一种全新的面向输出排队的交换结构,该结构将信元存储于输入端,而信元的调度请求面向输出端排队.利用输入端无冲突调度算法,可以使结构对存储器带宽的需求和输入排队交换机一致.该文设计的调度矩阵使算法复杂度和端口规模呈线性关系,且每一步只需要一次按位"与"操作.文章同时证明了结构要达到稳定的充分条件是使用2倍传输加速比.仿真实验表明,对于均匀流量,该结构时延性能和主流交换结构相似,且抖动性能远优于主流交换结构,而在2倍传输加速比时,其时延性能和OQ完全相同;对于非均匀流量,该结构吞吐率性能优于主流交换结构,且在使用1.14倍传输加速比时,其吞吐率性能和OQ相同.     

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

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

一种公平服务的动态轮询调度算法

调度策略是核心路由交换设备性能的重要保证.针对联合输入交叉节点排队(combined input and cross-point queuing,简称CICQ)交换结构现有调度策略在复杂度或性能方面存在的缺陷,深入探讨了CICQ交换结构调度策略设计的基本准则,并提出了CICQ下虚拟通道的概念.基于基本准则和虚拟通道概念,提出一种简单、高效和公平服务的动态轮询调度策略——FDR(fair service and dynamic round robin).其算法复杂度为O(1),具有良好的可扩展性;并依据虚拟通道的状态为其分配调度份额,具有良好的动态实时性能,能够适应流量负载非均衡的网络环境.SPES(switching performance evaluation systcm)仿真结果表明,该算法具有良好的时延、吞吐量和抗突发性能.     

CICQ的高性能LQF_DRR调度算法

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

基于输入排队的高速交换调度算法研究

高速交换网络一般采用基于定长信元的交换结构,其性能决定于排队策略和信元调度算法.输入排队策略只有和一个有效的调度算法相结合,才能保证交换结构具有良好的吞吐率和时延等性能.主要阐述了基于VOQ的最大数量匹配算法,最大权重匹配算法,稳定结合算法,神经网络算法等输入排队调度算法,分别从技术特点,性能指标和实现复杂度等多个方面进行比较和分析.分析了分布式和集中式两大类调度算法的工作方式,并根据各类算法的特点提出,神经网络算法可以通过定义其优先级函数实现其余各类算法.     

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

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

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

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

Achieving fair service with a hybrid scheduling scheme for CICQ switches

Providing performance guarantees for arriving traffic flows has become an important measure for today’s routing and switching systems. However, none of current scheduling algorithms built on CICQ (combined input and cross-point buffered) switches can provide flow level performance guarantees. Aiming at meeting this requirement, the feasibility of implementing flow level scheduling is discussed thoroughly. Then, based on the discussion, it comes up with a hybrid and stratified fair scheduling (HSFS) scheme, which is hierarchical and hybrid, for CICQ switches. With HSFS, each input port and output port can schedule variable length packets independently with a complexity of O(1). Theoretical analysis show that HSFS can provide delay bound, service rate and fair performance guarantees without speedup. Finally, we implement HSFS in SPES (switch performance evaluation system) to verify the analytical results.     

高速IP路由器中输入排队调度算法综述

高速IP路由器一般采用基于定长信元的交换结构,其可扩展性和性能分别受排队策略和调度算法的影响.基于输入排队策略的路由器具有良好的可扩展性,但需要一个有效的调度算法的支持,才能保证吞吐率和延迟等性能.主要讨论输入排队调度算法,将现有的调度算法分为4类:最大(无权重)匹配、最大权重匹配、稳定婚姻匹配和确定型调度.对每一类算法,从技术特点和性能指标两个方面进行比较和分析.最后给出了输入排队调度算法的发展趋势.     

高速路由器中一种有效的组播交换排队机制

许多Internet新业务产生的网络流量都属于组播类型．高速路由器中组播交换队列设计是解决组播数据在复杂网络中有效传输的关键问题之一．理想情况下，为保证服务的公平性及有效性，不应该在排队和调度时对组播和单播人为地进行区分．在二者共存的情况下，如何进行公平地排队、交换是亟待解决的问题．基于共享存储交换结构，提出了一种有效的组播交换队列设计方案，同时提供了相应的与组播比例和平均扇出相关的缓存管理机制和队列调度算法．仿真结果表明，与在Cisco高端路由器中广泛应用的ESLIP设计方案相比，在输入负载大于80％的重负载环境中，该系统能够获得更低的平均时延和更小的系统丢包率．     

Toward balanced and sustainable job scheduling for production supercomputers

Job scheduling on production supercomputers is complicated by diverse demands of system administrators and amorphous characteristics of workloads. Specifically, various scheduling goals such as queuing efficiency and system utilization are usually conflicting and thus need to be balanced. Also, changing workload characteristics often impact the effectiveness of the deployed scheduling policies. Thus it is challenging to design a versatile scheduling policy that is effective in all circumstances. In this paper, we propose a novel job scheduling strategy to balance diverse scheduling goals and mitigate the impact of workload characteristics. First, we introduce metric-aware scheduling, which enables the scheduler to balance competing scheduling goals represented by different metrics such as job waiting time, fairness, and system utilization. Second, we design a scheme to dynamically adjust scheduling policies based on feedback information of monitored metrics at runtime. We evaluate our design using real workloads from supercomputer centers. The results demonstrate that our scheduling mechanism can significantly improve system performance in a balanced, sustainable fashion.