一种高速crossbar调度算法及其性能分析
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种高速crossbar调度算法及其性能分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要:分析了高速crossbar调度算法iSLIP在处理突发业务时性能严重恶化的原因。结合LQF/iLQF算法的思想,提出了又一种输入排队crossbar调度算法iPGQM。仿真结果表明:该调度算法在均匀业务流量下和iSLIP算法的性能基本相同;在突发业务的条件下,iPGQM算法具有更好的抗突发特性;特别在重负载的条件下,与iSLIP算法相比,不仅具有更高的吞吐量,而且平均延迟降低了10%左右。
关键词:crossbar;调度算法;输入排队;非均匀业务流;iSLIP
中图分类号: TP393
文献标志码:A
Novel scheduling algorithm in highspeed crossbar and its performance analysis
JIANG Xiaobo, DU Xiaowei
School of Electronic and Information, South China University of Technology, Guangzhou Guangdong 510641,China
)
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交换一个信元的时间间隔称为一个时隙。信元到达过程可用一个离散时间随机过程Ai (n)表示,1≤i≤N,n指时隙数,每个时隙在每个输入端有0或者1个信元到达。到达输入端i且目的端为j的信元被存储在VOQij中,信元平均到达VOQij的速率为λij,即每个时隙平均到达的信元数。オ
定义1 如果λij满足约束条件:オ
∑Nj=1λij≤1;1≤i≤N
∑Ni=1λij≤1;1≤j≤N
(1)お
г虺Ai(k)是容许的,否则就是非容许的。オ
由于crossbar无内部存储、无阻塞,为了避免发送和接收冲突,匹配算法必须保证在一个时隙内每个输入端口至多发送一个信元,每个输出端口至多接受一个信元。使用mij(n)表示第n个时隙时输入端口i与输出端口j的连接关系。Э梢越crossbar结构的连接约束描述如下:
∑Nj=1mij≤1;1≤i≤N
∑Ni=1mij≤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算法是一种最大权重匹配算法,它把VOQij长度Lij设为权重ωij,в畔确务有较高VOQ长度的输入。对于独立到达的流量LQF算法可获得100%的吞吐量,对于任何容许流量该算法都是稳定的。iLQF算法[11]作为LQF算法的迭代近似算法也包括请求、响应、确认三步。iLQF在输入端向相应的输出端发送请求的同时也发送VOQ长度,这往往需要更多的参数编码比特数和更大的时间复杂度,由于现有电子器件很难在几十甚至几纳秒内为G比特级端口速率的Scheduler做出调度决策,从而限制了这些最大权重算法的┦褂谩
┑1期 ┙小波等:一种新的高速crossbar调度算法及其性能分析
┆扑慊应用 ┑30卷
2 iPGQM算法
2.1 算法思想
传统crossbar调度算法输入/输出端竞争采用roundrobin方式来解决,同等对待各个有请求的输入端口。在突发流量条件下,这种策略会使队列的长度变化不均衡,从而限制了吞吐量,最终会降低整个交换网络性能。
为了提高算法在非均匀流量下适应性,需要考虑到达各输入端口负载的不均匀性,增加负载较重端口的匹配机会。本文提出的调度算法iPGQM,通过增加重负载端口提请求机会的策略,来保证长队列得到较多的服务机会。从而提高在突发业务流下的吞吐量和时延性能。
增加重负载VOQ匹配机会的策略为:Ц据迭代次数n,为去往相同目的端口的VOQ设置n个门限值th1,th2,…,thn(th1≥th2≥…≥thn),第k次迭代允许长度超过thk的VOQij(并且输入端i和输出端j都未匹配)向相应的输出端提请求。由于thk≥thk+1,如果该VOQij在第k次迭代中没有得到匹配机会,可以在第k+1次迭代中继续参与竞争。这就使那些负载较重的队列获得了更多的发送机会,从而实现根据输入流量的非均匀性区别对待各个端口。オ
2.2 iPGQM算法描述
iPGQM算法同样分为请求响应接受三个步骤。Ц据迭代次数n,为所有去往输出端口j 的VOQ设置n个门限值thj,1,thj,2,…,thj,n(thj,1А莳thj,2А荨≥thj,n)。只有长度大于门限值的VOQ才会提请求,把请求作为输入,经过n次迭代则得到一个新的匹配。
第k次迭代的三个步骤为:オ
步骤1 请求。如果一个未匹配的输入端i有信元等待发送,根据要求发送的输出端口号j,如果相应的VOQij大于thj,k,则向输出端j发送请求信号。オ
步骤2 许可。如果一个未匹配的输出端接收到多个请求信号,从中随机选取一个进行许可。
步骤3 接受。如果输入端接收到多个许可信号,从中随机选取一个进行接受,这样就建立了一个匹配边。
3 性能仿真
对于输入排队crossbar调度算法的性能分析,由于解析分析的困难性,计算机仿真是一种有效而广泛采用的研究手段。
仿真条件是针对32×32的crossbar,使用Bernoulli业务源模拟均匀业务源和基于Markov过程调制的ONOFF过程模拟突发业务源。所有输入端口的输入buffer最大缓冲1万个cell,每个VOQ最多缓存500个cell。б蛭N=32,所以为去往相同输出端口号的VOQ设置5个门限,Х直鹞:th,3/4th,1/2th,1/4th和0,其中th等于去往相同输出端口的VOQ长度和除以N。仿真长度均为100B000个时隙。オ
3.1 Bernoulli业务
首先针对所有输入端口使用Bernoulli业务源,每个信元的目的端口在各个输出端口中等概率选择。对算法iPGQM和iSLIP进行了仿真,结果如图2所示,Ш嶙标为负载λ,纵坐标为单位信元的平均时延t。图2显示iPGQM算法的平均时延基本上与iSLIP算法相同。在这种业务下两种算法都表现出极好的性能,系统时延低并且没有出现丢包。这表明iPGQM算法在普通业务条件下性能与iSLIP算法基本相同。
图片
图2 iPGQM与iSLIP算法在Bernoulli业务下的平均时延
3.2 突发业务
以上我们都假设信元按照Bernoulli过程到达的,现实中分组往往突发到达,并且每个分组包含多个交换的信元,因此信元突发到达更加接近网络真实情况,通常用基于Markov过程调制的ONOFF过程来模拟这种流量。在每段突发过程中数据包的目的地址不变,每段突发数据包的目的端口在各个输出端口中等概率选择。下面我们考虑当所有端口业务源均采用突发业务的条件下,平均突发长度变化对iPGQM以及iSLIP算法的影响。这里取递增的32、64、128三种突发长度。
图3反映了时延随负载增加和突发长度增加的变化情况,可以看出随着流量负载的增加,iPGQM算法的平均延迟曲线上升较缓慢。特别在流量负载大于0.7的情况下,平均延迟明显低于iSLIP算法。
图片
图3 iPGQM与iSLIP算法在突发业务下的平均时延
图4为这两种算法丢包率的对比情况。可以看出iPGQM算法的丢包率在三种突发长度的情况下均显著低于iSLIP算法的丢包率。这是因为iPGQM算法中充分考虑了信元到达信息从而增大了crossbar的通过率,从而使平均延迟和丢包率减小,因而具有更好的流量适应性。比iSLIP算法相比,不仅大大降低了丢包率,而且平均时延减少了10%左右。
图片
图4 iPGQM与iSLIP算法在突发业务下的平均丢包率
综上可以看出在Bernoulli业务下,iPGQM算法和iSLIP算法具有同样的性能。在突发业务的条件下,iPGQM算法比iSLIP算法具有更低的时延和丢包率。特别是在重负载的条件下,与iSLIP算法相比,性能有了显著提升。
4 结语
随着高速路由器的发展,传统的调度方案由于性能或实现复杂度的原因,逐渐成为了系统性能的瓶颈。本文提出了一种高性能输入排队crossbar调度算法iPGQM。仿真结果表明,该调度算法在均匀业务流量和突发流量的条件下均具有较好的性能,因而可以用于骨干网核心路由器中。
参考文献:[1] PARTRIDGE C, CARVEY P, BURGESS E, et al. A 50Gb/s IP router[J]. IEEE/ACM Transactions on Networking,1998,6(3):237-248.
[2] BONUCCELLI M A, URPI A. A multicast FCFS output queued switch without speedup[C]// Proceedings of 2nd IFIP Conference in Networking. London: SpringerVerlag,2002:1057-1068.
[3] PRAKASH A, SHARIF S, AZIZ S. An O(log2N)parallel algorithm for output queuing[EB/OL].[2009-05-20]. users.ece.utexas.edu/~adnan/publications/schedinfocom02.pdf.
[4] KAROL M, HLUCHYJ M, MORGAN S.Input versus output queuing on a spacedivision packet switch[J]. IEEE Transactions on Communications, 1987,35(12):1347-1356.
[5] MHAMDI L. A partially buffered crossbar packet switching architecture and its scheduling[EB/OL].[2009-05-20]. ce.et.tudelft.nl/publicationfiles/1504_550_Lotfi_ISCC_2008.pdf.
[6] McKEOWN N. Scheduling algorithms for inputqueued cell switches[D]. Berkeley, CA, USA: University of California at Berkeley,1995.
[7] MCKEOWN N, ADISAK M, VENKAT A, et al. Achieving 100% throughput in an inputqueued switch[J]. IEEE Transactions on Communications, 1999, 47(8):1260-1267.
[8] ADISAK M. Scheduling nonuniform traffic in high speed packet switches and routers[D]. Stanford, CA: Stanford University,1998.
[9] MNEIMNEH S. Matching from the first iteration: An iterative switching algorithm for an input queued switch[J]. IEEE/ACM Transactions on Networking,2008,16(1):206-217.
[10]
Cisco Systems. Cisco 12000 Gigabit Switch Router[EB/OL].[2009-04-20]. /warp/public/cc/pd/rt/12000/prodlit/gsr_ov.pdf.
[11]
McKEOWN N, ANDERSON T E. A quantitative comparison of scheduling algorithms for inputqueued switches[J].Computer Networks and ISDN Systems,1998,30(11):319-352.