一种面向MSM型Clos交换结构的启发式并发调度算法

调度算法一直是交换系统中不可或缺的研究内容.为满足新型高速路由及交换系统的研究需求,提出一种主动授权并发轮询调度算法——CRRD-AG算法.多级交换结构Clos交换网络以其良好的可扩展性作为高速交换结构倍受关注,但与之相适应的调度算法却并不多.目前主流算法,如并发分派算法(CD)和基于轮询的并发分派算法(CRRD),不是吞吐率较低就是所处理的业务流单一.CRRD-AG算法以CRRD为基础,将经典的"请求-授权-接受"的匹配计算模式改进为"主动授权-接受"的匹配模式,不仅能够降低CRRD算法在第1阶段的仲裁信息量,而且充分利用了中间级链路带宽,从而降低了整个系统的平均延迟,提高了吞吐率.进行充分的实验后,其结果表明,无论是在均匀业务,还是在突发业务环境中,CRRD-AG算法都能保证100%的吞吐率,更为重要的是,在不降低吞吐率的情况下能够显著改善分组的平均延迟.     

一种具有信元保序能力的Clos网络分布式调度算法

分组交换三级Clos网络信元调度算法可分为集中式和分布式两种实现方式.分布式调度具有良好的可扩展性,适于在高速大容量环境中应用.然而由于分布式调度会带来同一分组各个信元间的乱序问题,给其实现带来困难.该文提出了一种具有信元保序能力的三级Clos网络分布式调度算法.该算法包括第一级的均匀负载分配、中间级的并行调度和第三级的按序输出调度三部分.文中对算法的性能进行了严格的理论证明和相关的仿真分析,表明该算法可以很好地解决传统分布式调度中的信元乱序问题,具有良好的性价比.     

数据中心网络光电交换架构下的流调度算法研究

研究了基于多级Clos数据中心网络的光电交换架构下的流量调度算法,以减少数据传输时延,同时也保证无丢包。传统ADAPT调度算法能实现加速比最小化,但仍然有一些空闲时间槽,而造成带宽未被充分利用。为了解决该问题,在多级Clos网络中,提出了一个多跳路由和调度（Multi-Hop Routing and Scheduling,MHRS）算法,该算法可以在不增加加速比的同时充分利用空闲的带宽。与ADAPT算法类似,MHRS算法先将流量矩阵分解为商矩阵和余矩阵,然后实现两步调度,即将单跳作为第一步,将多跳作为第二步。第一步将余矩阵中的一些数据包调度到商矩阵所形成的配置矩阵的空闲时间槽中,而当这些数据包不能在第一步中被直接调度时,则采用第二步绕道的多跳调度过程传输数据包。仿真结果证明,在多级Clos网络中MHRS算法比ADAPT算法性能更好。     

一种支持QoS的多级交换网络调度算法

现有MSM多级交换结构在非均匀业务源下性能不高.在深入分析多级交换网络内部拥塞控制理论的基础上,提出了一种中间级带缓存的多级交换结构-CB-3Clos结构及信用分发模式下基于背压的流控策略.通过理论分析了中间级负载分配算法应该满足的条件,给出了一种能够有效支持QoS的简单的类iSLIP调度算法-RGA算法.仿真结果表明:与现有的CRRD算法相比,RGA算法具有与业务源模型无关的高吞吐量特性,并在不均衡业务源模型下具有较好的时延性能.     

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

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

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

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

耐故障Clos网及其路由算法

提出了一种新的耐故障Clos网,通过在基础Clos网各段中增加冗余的交换单元,使其能够在发生少量故障的情况下正常工作,从而提供更可靠的服务。针对耐故障Clos网,给出一种耐故障Clos路由算法,该算法采用最小分布优先的策略逐列计算Clos网连接说明矩阵,通过重排完全实现无阻塞路由,该算法的时间复杂度在最坏情况下仅为O(N3/2)。该耐故障Clos网及其算法设计可以用于实现更为可靠的Clos网络。     

分布式系统中的多用户并行调度算法

针对传统调度算法的不足,在多用户分布式天线系统的下行链路中引入并行调度思想,从而在系统吞吐量和公平性能间取得折中。首先将轮询调度算法进行了改进,同时提出一种并行调度算法,每次选择瞬时数据率和平均吞吐量较高的多个用户进行通信。采用优化的匹配算法改进传统穷尽搜索计算量大的缺陷。仿真结果显示与传统的并行调度和改进的并行轮询调度相比,本文算法在保证吞吐量的情况下,公平性有了显著提高。     

一种双匹配动态调度算法

提出了适于异构环境独立任务调度的双匹配动态调度算法（BM算法）．BM算法将任务与处理机实现双匹配，使大部分任务在执行时间最短而且完成时间最早的处理机上执行．对于无法实现双匹配的任务，采用最早完成时间最小者优先的策略进行调度．BM算法可以同时满足负载均衡和高吞吐率两个目标．BM算法与通常用作评测基准的Min-min算法的比较结果表明，BM算法的运行时间远少于Min-min算法，其调度跨度比Min-min算法减少约9％．     

最小分布优先Clos网路由算法

提出了一种新的Clos网无阻塞路由算法、最小分布优先算法,用该算法可以降低Clos路由算法的高时间复杂度。对于Clos网连接说明矩阵,提出并证明了矩阵中某一列的完全性问题是一个独立的问题,并据此提出了以最小分布优先的方式逐列计算Clos连接说明矩阵的策略,消除了产生在矩阵列之间的回溯以及列内元素之间的回溯,能够完全实现无阻塞路由,在最坏情况下的时间复杂度为O(N3/2),可以应用于Clos网路由控制。