三级Clos网络中分布式调度算法研究

调度算法用于解决交换网络输出端口竞争问题.鉴于现有三级C los网络调度算法存在实现复杂、性能无法保证的缺点,本文提出了一种利于分布式调度的三级C los网络结构和相应的负载均衡调度思想,并给出了一种简单负载均衡调度算法.采用这种新结构和相应的调度思想不仅可以简化三级C los网络的调度,而且可以充分利用现有单Crossbar网络调度的研究成果,保证算法性能.文中通过理论和仿真分析证明基于这种思想的调度算法比现有算法具有很大的优越性.

混合交换机制三级Clos网络分布式调度算法

提出了一种新型的采用变长分组和定长信元交换机制相结合的三级Clos网络分布式调度算法.在输入级采用以变长分组为单位的负载分配方式,使得属于同一分组的各个信元通过同一个中间级交换单元转发,消除了定长信元交换机制的信元乱序问题;采用一种基于新型令牌方式的负载均衡算法,消除了变长分组负载分配的不公平性;中间级和输出级交换单元的调度采用定长信元方式,提高了调度算法的效率,增强了算法对业务的适应能力.理论分析证明了该算法的稳定性,仿真分析证明了该算法在转发时延和业务适应能力上优于其他算法.

一种新型的三级Clos网络分布式容错调度机制

通过对不同故障影响的分析,建立了三级Clos网络的故障模型,将各个不同的故障归结到对网络输入级不同队列的影响上,提出了一种新型的基于Credit机制的三级Clos网络分布式容错调度算法。利用Credit机制可以引导网络业务绕开受故障影响队列;同时,Credit机制还可以把网络业务完全均匀地分配到网络有效中间级交换单元上。理论分析证明了该容错调度算法可以在不增加网络资源的情况下,至少容m-n(m、n分别为输入级交换单元输入输出端口数)个网络各类故障,通过仿真说明了算法在不同网络故障下的良好性能。

分布式调度三级CLOS网络中交换机制的选择

以分布式调度三级Clos网络为重点,对定长信元和变长分组两种交换方式性能和实现成本进行了对比分析;通过对网络第一级负载分配原则的理论分析,给出了变长分组交换方式下网络稳定性的条件,利用仿真分析对比了两种交换方式的时延特性。给出了分布式调度三级Clos网络中交换机制的选择原则。

星上Clos交换网络的逆向调度算法

针对星上交换在匹配效率、硬件复杂度等方面的特殊要求,提出了基于MSM型三级Clos网络的逆向调度算法.与以往调度算法按模块排列顺序执行匹配操作不同,该算法首先在中间级缓存信元请求并进行内部匹配,然后使用中间级的匹配结果指导输入级模块的信元发送.调度过程中各阶段间相互分离,每一阶段的执行不依赖于前一阶段的结果,从而实现整个匹配过程的流水线操作.仿真结果表明,逆向调度算法在不增加硬件开销的前提下提高了调度匹配速度和效率,并达到较低的端到端时延性能.

一种支持单组播混合交换的Clos网络及调度算法

针对MSM型Clos网络的组播支持问题,提出了一种新的交换结构以及相应的调度算法,可同时支持单组播业务的交换.支持组播的Clos交换结构中,输入级模块内增加的组播队列采用与单播队列相同的方式竞争输出端口,输出链路从判决器则基于单组播优先级选择一类业务进行匹配.基于静态轮询的单组播调度算法继承了SRRD算法中指针初始化和更新方式简单高效的特点,可提供业务类型级和流级的公平,并且算法复杂度低,硬件实现简单.仿真结果表明,在多种业务源模型下,基于静态轮询的单组播调度算法均具有良好的时延和吞吐率性能.

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

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

星上Clos交换网络的分治调度算法

针对星上交换的特殊要求,该文提出了基于MSM(Memory-Space-Memory)型Clos交换网络的分治调度算法。通过引入冲突域的概念,分治调度算法将MSM型Clos网络中的匹配问题分解成在冲突域内为每个中间级模块选择信元的问题。该调度算法限制了冲突发生的范围,简化了调度的复杂度,并且具有硬件实现简单、能适应多种业务等优点。仿真表明,分治调度算法在各种业务模型下的吞吐率都能接近100%,并具有良好的时延性能,满足了卫星通信的要求。

基于帧填补的MMM Clos网络按序分组交换算法

与其它类型的Clos网络相比,各级带缓存的MMM(Memory-Memory-Memory)Clos网络使得交换网络的配置时间最小化,但是MMM交换中间级缓存的存在会引起输出端口的信元乱序。该文提出了一种满帧填补扩展算法(EPF),采用逐帧转发的方式来避免MMM Clos网络中的乱序问题。新算法在输入级和输出级采用固定周期轮转方式,中间级采用最早信元优先输出调度,具有复杂度低,可分布式控制,以及不需要缓存加速的特点。分析和仿真结果表明该算法是稳定的,即输入输出为可允许业务时,算法可达100%吞吐率。

谈三级CLOS交换构架

多级CLOS网络由于其模块化性强和良好的可扩展性在大容量路由器交换网络设计中受到了人们越来越多的青睐。该文中,作者从分组交换技术的发展趋势入手,着重介绍多级交换中的三级CLOS网络交换架构的原理及优势。

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

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