摘 要:分析了高速crossbar调度算法iSLIP在处理突发业务时性能严重恶化的原因。结合LQF/iLQF算法的思想,提出了又一种输入排队crossbar调度算法iPGQM。仿真结果表明:该调度算法在均匀业务流量下和iSLIP算法的性能基本相同;在突发业务的条件下,iPGQM算法具有更好的抗突发特性;特别在重负载的条件下,与iSLIP算法相比,不仅具有更高的吞吐量,而且平均延迟降低了10%左右。
　　关键词:crossbar;调度算法;输入排队;非均匀业务流;iSLIP
　　一种高速crossbar调度算法与性能分析
　　随着高速路由器的发展,传统的调度方案由于性能或实现复杂度的原因,逐渐成为了系统性能的瓶颈。本文提出了一种高性能输入排队crossbar调度算法iPGQM。仿真结果表明,该调度算法在均匀业务流量和突发流量的条件下均具有较好的性能,因而可以用于骨干网核心路由器中。
　　
　　Novel scheduling algorithm in highspeed crossbar and its performance analysis
　　
　　Abstract: This paper analyzed the reasons for which the highspeed crossbar scheduling algorithm iSLIP has a serious deterioration of performance under burst traffics. With reference to the ideas of LQF/iLQF, this paper proposed a novel inputqueued crossbar scheduling algorithm called iPGQM (iterative Parallel GradedLength Queue Matching). Simulation results show that iPGQM has the same performance as iSLIP under uniform traffics. Furthermore it has better performance than iSLIP under burst traffics. Especially in heavy load conditions, iPGQM not only achieves higher throughput, but also reduces the average delay about 10% compared with iSLIP algorithm.
　　
　　Key words: crossbar; scheduling algorithm; input queueing; nonuniform traffic; iSLIP
　　
　　0 引言
　　输入排队(Input Queuing, IQ)crossbar作为一种简单、高效的高速交换结构,被广泛应用于高速路由器中[1]。在这种交换结构中,如果输入队列只采用简单的先进先出(First In First Out,FIFO)队列机制,其线头阻塞(Head Of Line blocking,HOL)将限制交换网络的最大吞吐量为58.6%[2-4]。因而,一般采用虚拟输出排队技术(Virtual Output Queueing, VOQ),即一个输入端为每一个输出端维护一个FIFO队列。由于采用了VOQ,还必须使用有效的crossbar控制算法解决输入/输出端的竞争,保证无冲突地传输信元[5]。基于输入排队调度算法中iSLIP(iterative SLIP)算法以其高吞吐量和低复杂度得到了广泛的应用,但iSLIP[6](iterative SLIP)算法在突发流量下性能严重下降。为此,又提出了以队列长度为权重的调度算法[7-8],如LQF算法,该算法对任何容许的流量都是稳定的。但硬件实现较为复杂,目前应用较少。
　　本文首先分析了高速crossbar调度算法iSLIP在处理突发业务时性能严重恶化的原因,并结合LQF/iLQF算法的思想,提出一种简单、硬件易实现的调度算法iPGQM(iterative Parallel GradedLength Queue Matching),该算法根据VOQ队列的长度来调节提请求的机会,从而增加负载高的输入队列的匹配机会。结果表明,该算法能够明显改善高速crossbar调度算法在非均匀业务流下的吞吐量和时延等性能。
　　1 问题描述
　　1.1 输入排队交换和匹配问题
　　crossbar交换结构是输入排队的典型实现方式,这种结构实质上相当于一个多总线的结构,支持多个点到点的链路同时进行通信,一般用于高性能交换。
　　图片
　　
　　图1 IQ crossbar逻辑结构
　　
　　图1所示是一个基于输入排队的N×N规模的crossbar交换结构:每个输入端口的缓存分为N个VOQ队列,每个VOQ队列存储从输入端口i到达,目的端口为j的信元。输入端总共有N2个FIFO,构成交换网络的队列系统。图中调度器用于管理队列信息,执行调度算法。调度算法首先根据输入队列的状态,做出匹配结果,然后控制交换结构中交叉点的开合,最终建立输入/输出端信元传输通道。
　　
　　crossbar交换一个信元的时间间隔称为一个时隙。信元到达过程可用一个离散时间随机过程Ai (n)表示,1≤i≤N,n指时隙数,每个时隙在每个输入端有0或者1个信元到达。到达输入端i且目的端为j的信元被存储在VOQij中,信元平均到达VOQij的速率为λij,即每个时隙平均到达的信元数。
　　定义1 如果λij满足约束条件:
　　
　　∑Nj=1λij≤1;1≤i≤N
　　∑Ni=1λij≤1;1≤j≤N
　　(1)
　　则称Ai(k)是容许的,否则就是非容许的。
　　由于crossbar无内部存储、无阻塞,为了避免发送和接收冲突,匹配算法必须保证在一个时隙内每个输入端口至多发送一个信元,每个输出端口至多接受一个信元。使用mij(n)表示第n个时隙时输入端口i与输出端口j的连接关系。可以将crossbar结构的连接约束描述如下:
　　
　　∑Nj=1mij≤1;1≤i≤N
　　∑Ni=1mij≤1;1≤j≤N
　　(2)
　　1.2 iSLIP和LQF/iLQF算法分析
　　调度算法按照一定的规则决定输入端和输出端的匹配关系,解决信元在输入端和输出端的竞争。路由器能达到的吞吐率要求和延时特性取决于其所采用的调度算法。具有代表性的如PIM、iSLIP、LQF和OCF等[9]。这四种算法的特性比较如表1。
　　
　　表格(有表名)
　　
　　表1 四种典型算法的特性比较
　　
　　算法稳定性公平性延迟控制复杂度
　　PIM差较好差低
　　iSLIP差好差低
　　LQF好较好好高
　　OCF好较好好高
　　
　　由于PIM、iSLIP等算法的低复杂度,易于硬件实现。iSLIP被应用于CISCO的GSR12000[10]系列高速路由器中,但这类算法在突发流量情况下,性能会急剧下降[6]。缺乏LQF、OCF等算法的稳定性,但LQF、OCF算法的复杂度又较高。
　　
　　iSLIP算法只需要log N次迭代就能收敛[6],并且 iSLIP算法在均匀业务流下能够达到100%吞吐量,但对于突发业务,该算法的平均时延迅速增大,在高负载条件下出现大量丢包。原因在于iSLIP调度算法采用roundrobin的方式调度输入队列中的信元,这样虽然对于每个输入端内的VOQ得到的服务是maxmin公平的,但是无法对不同的队长,不同等待时间的数据包做出合理的区别调度。当到达信元分布不均匀时,roundrobin服务致使队列长度变化不均衡,负载较大的VOQ的队列长度容易持续增长,从而限制了吞吐量,进而使延迟和丢包率增大。
　　LQF算法是一种最大权重匹配算法,它把VOQij长度Lij设为权重ωij,优先服务有较高VOQ长度的输入。对于独立到达的流量LQF算法可获得100%的吞吐量,对于任何容许流量该算法都是稳定的。iLQF算法[11]作为LQF算法的迭代近似算法也包括请求、响应、确认三步。iLQF在输入端向相应的输出端发送请求的同时也发送VOQ长度,这往往需要更多的参数编码比特数和更大的时间复杂度,由于现有电子器件很难在几十甚至几纳秒内为G比特级端口速率的Scheduler做出调度决策,从而限制了这些最大权重算法的使用。
　　
　　第1期 姜小波等:一种新的高速crossbar调度算法及其性能分析
　　
　　计算机应用 第30卷
　　
　　2 iPGQM算法
　　2.1 算法思想
　　传统crossbar调度算法输入/输出端竞争采用roundrobin方式来解决,同等对待各个有请求的输入端口。在突发流量条件下,这种策略会使队列的长度变化不均衡,从而限制了吞吐量,最终会降低整个交换网络性能。

我来说两句：
	用户名： 密码： 匿名发表
	验证码：