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

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

一种支持变长分组的CIOQ交换结构

在分析了组合输入输出排队结构的基础上,对传统CIOQ(Combined Input—Output Queued)的输出队列进行扩展和在内部交换结构中采用并行传送的方式,实现了交换调度的分布式操作和内部无加速的CIOQ交换;又通过将输出队列的状态信息反压到输入端和在输出端采取基于整包调度的算法,实现了对变长分组的交换,减小了定长信元交换中分组切割和重组的开销。     

iLQF调度算法及其参数的仿真

文章介绍一种无内部阻塞ATM交换结构的输入缓存模型及其缓存信元的iLQF调度算法(即迭代的最长队列优先调度算法),并具体给出该算法的实现方案。通过仿真,分析和确定了交换结构的输入缓存长度和iLQF调度算法的迭代次数对信元丢失率的影响。     

缓冲交叉开关交换结构多播调度算法研究

高性能核心交换设备多播调度受到越来越多的关注·交叉开关结构下的多播调度方案或者性能较差,或者过于复杂,难于应用在高速交换场合·为此,提出一种面向多播的多输入队列缓冲交叉开关体系结构·将多播调度分解为信元分派、输入调度、输出调度3个可分布式并行执行的子问题,并设计了相应的调度算法,降低了算法复杂性·实验结果表明,交叉点缓冲区容量与输入队列数量对多播性能都具有很大的影响·在突发流量到达下,与单多播输入队列的体系结构相比,无论是采用O(1)复杂度的HA-RR-RR还是复杂度更高的调度算法,均能显著提高系统吞吐性能·     

具有o(N2)复杂性的输入缓冲队列加权调度算法

Internet核心路由器多采用输入缓冲交换矩阵,研究输入缓冲队列的调度算法十分重要。加权调度算法具有较高的性能,但由于硬件实现困难,因此很少得到应用。提出了一种简单的加权高度算法L2QF,该算法采用串行轮询的思想,根据虚拟输出队列的长度依次为每个输入端口选择一个输出端口。L2QF算法具有LQF算法的性能,但复杂性仅为o(N^2)。由于L2QF是所有LQF算法中复杂性最低的算法,而且以叠代的方式的执行,因此易于硬件实现。     

Crossbar输入排队调度算法的研究

研究高效易于硬件实现的队列调度算法的目的是为了提高交换系统吞吐率和降低延迟。在阐述输入排队、HOL阻塞、虚拟输出队列等概念的基础上，对MSM、PIM、RRM、iSLIP等调度算法进行了系统的比较，研究表明iSLIP算法是一种性能良好、实现简单的算法。     

iSLIP调度算法研究及其实现

目前，为提高交换系统吞吐率，设计开发高性能网络交换机或路由器内部交换结构的技术已趋成熟．但易于在硬件中实现的、高效的队列调度算法仍然是一项值得研究的重要技术．文章首先讨论了对于输入缓冲采用FIF0队列交换系统，其吞吐率主要受HOL队首阻塞的影响．然后研究了iSLIP调度算法的基本原理、迭代仲裁步骤及它在硬件中的实现．针对硬件交换转发判决这一关键问题，给出了在输入队列交换机中采用虚拟输出队列的交换结构和多优先级调度算法的硬件实现方案．最后，对isLIP算法的性能进行了分析比较，证明isLIP算法的实现方案不仅实现简单，而且具有良好的特性．     

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

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

基于轮转算法的缓冲交叉开关调度算法的设计与实现

研究了一种低复杂度、高性能的交换机调度算法——轮转(Round Robin)调度算法及其硬件实现,它是基于缓冲交叉开关交换结构的。缓冲交叉开关交换结构相比于无缓冲的交叉开关交换结构,仅需要简单的调度算法对输入VOQ队列和交叉点缓存输出分别进行调度,这大大简化了调度算法硬件实现的复杂程度,减小了系统延迟。因此,结合轮转算法和缓冲交叉开关交换结构各自的优点,可以设计出高性能的交换机。     

基于多输出端口的简单高效的交换结构

基于并行存储机制构建高性能PMS交换结构,采用流模型证明在不加速的情况下,PMS交换结构对满足强大数定律的可容许到达业务能实现100%的吞吐量。基于该交换结构,提出支持分组且具有多个输出端口的最短队列优先轮询算法SQF-RR。仿真结果表明,应用该算法的PMS交换结构能获得较好的性能。     

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

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

低碳经济下的港口泊位分配模型及其算法实现

航运公司正在进行前所未有的努力以减少船舶的燃油消耗量及碳排放量,而港口所制定的泊位分配计划对于船舶的油耗量和碳排放量有着直接的影响。由于船舶的到港时间是港方制定泊位分配计划的关键参数,因此将船舶到港时间作为决策变量引入传统的泊位分配（BAP）模型中,设计了港口与船方协调调度的新的泊位分配策略--VAT（Variable Arrival Time）策略,同时将船舶油耗和碳排放量融入BAP 模型的目标函数中,建立了船舶油耗量最小和船舶离港延迟时间最短的双目标优化模型。采用多目标遗传算法对该模型进行求解,并用仿真算例验证了该策略的有效性。计算结果表明,VAT策略可以大大削减航运公司的燃油消耗和船舶的碳排放,同时可以提高港口的服务水平,缩短船舶在港等待时间。     

求解批量流水线调度问题的改进和声搜索算法

针对以最大完工时间为目标的批量流水线调度问题,提出一种改进的和声搜索优化算法。该算法采用ROV规则的编码方式,使具有连续本质的和声搜索算法能直接应用于调度问题。对和声库的初始化和候选解的产生方式进行改进。针对该算法容易陷入局部最优的缺陷,将其与阈值接受算法结合,得到2种混合算法。仿真结果证明了该算法的有效性。     

基于遗传算法的不定期船舶调度优化模型研究

针对不定期船舶调度中客户需求信息的动态变化、船舶类型的多样化以及船舶航线的不定性,以最小化航运成本为目标函数,建立了带滚动窗口的不定期多目标船舶调度优化模型（SRPRW）,并制定了基于SRPRW模型的实时优化策略以实现需求信息变化时能及时快速地调整船舶调度航线.SRPRW模型求解时,在遗传算法（GA）中引入模拟退火机制以防止SRPRW模型的调度结果陷入局部最优解,同时设计了一种自适应交叉算子和自适应变异算子,以提高模型求解的收敛速度.实验结果表明该模型能快速地制定出船舶调度路线,及时响应客户的动态需求.     

Max-Min Fair Scheduling in Input-Queued Switches

Fairness in traffic management can improve the isolation between traffic streams, offer a more predictable performance, eliminate transient bottlenecks, mitigate the effect of certain kinds of denial-of-service attacks, and serve as a critical component of a quality-of-service strategy to achieve certain guaranteed services such as delay bounds and minimum bandwidths. In this paper, we choose a popular notion of fairness called max-min fairness and provide a rigorous definition in the context of input-queued switches. We show that being fair at the output ports alone or at the input ports alone or even at both input and output ports does not actually achieve an overall max-min fair allocation of bandwidth in a switch. Instead, we propose a new algorithm that can be readily implemented in a distributed fashion at the input and output ports to determine the exact max-min fair rate allocations for the flows through the switch. In addition to proving the correctness of the algorithm, we propose a practical scheduling strategy based on our algorithm. We present simulation results, using both real traffic traces and synthetic traffic, to evaluate the fairness of a variety of popular scheduling algorithms for input-queued switches. The results show that our scheduling strategy achieves better fairness than other known algorithms for input-queued switches and, in addition, achieves throughput performance very close to that of the best schedulers.     

基于OLS与EPSO算法的RBF企业订单预测模型研究

提出了一种最小正交二乘算法（OLS）和进化粒子群优化算法（EPSO）相结合构建RBF神经网络的企业订单预测模型。OLS采用前向回归算法,从输入数据中选取适当的中心,动态地避免网络规模过大和随机选择中心带来的数值病态问题;EPSO方法调整网络中的参数,如RBF中心位置,RBF宽度和隐层与输出层之间的权值,以提高网络的泛化能力。     

求解作业车间调度问题的禁忌分布估计算法

为优化作业车间调度问题的解,提出一个禁忌和分布估计的混合算法。分布估计算法是一种新的进化模式,通过概率优化模型在连续空间进行求解;通过对已获得的群体进行选择操作生成优势群体,提出的分布估计算法使用单变量边缘分布算法构建概率模型,估计离散空间中的联合概率分布,从概率向量采样生成新群体;采用基于工件编号的编码和解码机制保证解的可行性。为提高局部搜索能力,算法基于禁忌搜索算法设计新的双重移动组合、块禁忌和选择策略,在搜索陷入局部最优时利用遗传算法的变异算子生成新解;算法通过混合分布估计算法和禁忌搜索算法的优点,兼具全局搜索与局部搜索能力,提高了搜索的效率和性能。通过与现有算法在典型实例上的实验结果比较,表明该算法在求解作业车间调度问题上具有可行性和有效性。     

线路速率缓存的重端口交换机方案及行为分析

伴随着世界经济的快速发展,我国国内的经济形势也在日新月异的发生着变化,而网络的出现和更新更是无时无刻不在影响着我们的生活,同时,人们对网络存在的要求也逐渐变得更高.在因特网中的交换机,也就是所说的路由器现如今面临着两种挑战,一种是高交换速率的挑战,一种是联网服务质量（QOS）的挑战.高交换速率的挑战需要交换机/路由器尽可能的通过链路速率进行工作,联网服务质量（QOS）需要要求交换机/路由器可以完全仿效输出队列（OQ/outputqueuing）交换机的方式行为.到目前为止,联合输入输出队列（CIOQ/combined input-output queuing）的设计方案与交换机/路由器的不同,它需要交换机/路由器的内部速率加速到原有的2倍.为了满足这种技术的要求,重端口交换机（DPS/duplicated ports switch）的并行技术设计方案应运而生.这套方案有效证明了仿照交换机输出队列（OQ）的行为,以2为端口重数的必要充分性,并且这套方案的使用交换机/路由器可以工作在输入链路速率上,它的行为同交换机/路由器（OQ）的行为是等价的.     

IEEE 802.16中改进的QoS调度算法设计

IEEE802.16标准在每个节点处都提供实时业务和非实时业务。由于基于优先级的业务的服务质量（QoS）的需求不同,因此需要对传统的调度算法进行改进使其具有更大的适应性。为了改善QoS端到端时延的性能,提出了一种混合调度算法（EDD和WFQ算法相结合）。仿真结果表明：在每个节点处,提出的混合算法比仅使用EDD算法能给实时业务产生的时延更少,并且还能够使单个BS在可允许的端到端时延范围内容纳数量更多的子SS,而且使用从BS到SS的GPSS模式的调度机制比使用GPC模式能产生更小的时延。     

基于Edmonds-Karp算法的输入排队调度

输入排队Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的.因而在调度算法理论研究中把应用了二部图最大匹配的Maximum Size Matching和 Maximum Weight Matching算法作为目前各种调度算法性能评价标准.Edmonds-Karp算法是图论中求解网络最大流的经典算法之一.该文介绍了如何使用Edmonds-Karp算法求解二部图的最大匹配问题,并且应用算法于输入排队调度算法仿真中,得出经典MSM和MWM算法的性能仿真曲线,为进一步研究调度算法打下了理论基础.