《一种基于最长队列预测的CICQ交换结构调度算法》由会员分享,可在线阅读,更多相关《一种基于最长队列预测的CICQ交换结构调度算法(6页珍藏版)》请在金锄头文库上搜索。
1、第 32卷第 6期 电 子 与 信 息 学 报 V ol.32No.6 2010年 6月 Journal of Electronics Combined Input Crosspoint Queued(CICQ); Nonuniform traffic; Longest Queue Detecting(LQD) 1 引言随着近年来 VLSI 技术的发展,在 crossbar 的 交叉点能够植入少量缓存,依据目前的技术条件, 交叉点缓存容量比较小,仍然需要与输入排队结合 使用,这就形成了联合输入交叉点排队(CICQ)交换 结构。与传统基于 crossbar 的高速交换结构相比, CICQ 由于在
2、 crossbar 交叉点设置了缓存,能够将 输入端与输出端的数据传输竞争隔离开来,调度算 法可以在输入/输出端独立并行工作, 不需要集中控2009-06-23收到,2009-10-19改回 江苏省自然科学基金(BK2007001)资助课题 通信作者:彭来献 制。因此,CICQ 交换结构具有分布式实现、易扩 展的良好特性,是构建高速、大容量、可扩展路由 器的理想选择 1 。同时,CICQ 交换结构及其调度算 法也成为高速交换技术领域近期一个研究热点。国 内外对此进行了大量的研究,文献2首次提出了在 输入端使用 VOQ(Virtual Output Queue)排队机制 的 CICQ 结构,在
3、业务流量负载较大(大于 65%)情 况下数据传输平均时延优于单纯的输入排队 crossbar 交换结构,目前对调度算法的研究普遍基 于这种 VOQ+CICQ 的结构。 根据研究方法的不同,整体上看,关于CICQ交 换结构调度算法的研究分为两大类:一类是纯理论1458 电 子 与 信 息 学 报 第 32卷 分析,探讨CICQ调度算法的吞吐量、时延、服务质 量保证等性能的理论基础。文献3-9分别研究了 100%吞吐量、带宽保证、时延保证、公平性等问题, 研究成果为CICQ交换结构调度算法的研究和发展 奠定了坚实的理论基础,但是提出的算法和调度机 制却存在复杂、硬件难以实现的问题,无法在高速 的环
4、境下应用。 关于CICQ交换结构调度算法另一类研究方法 是从实用性出发,以交叉点小缓存、高效、低复杂 度、硬件易实现作为性能指标,设计各种易于硬件 实现的快速启发式调度算法。这类算法的共同点在 于减少控制信息量和复杂的计算,一般采用两种手 段:一种是依据交叉点缓存的状态信息进行调度; 另一种是基于轮转(round-robin)机制。文献10,11 提出的算法MCBF(Most Critical Buffer First)和 LFF-LBF算法都是依据交叉点缓存的忙闲来进行 输入/输出调度,使得交叉点缓存得到充分的利用, 仿真结果表明算法在均匀流量下具有良好的时延性 能。然而这种算法没有考虑输入
5、端队列的状态,在 非均匀流量下会出现不稳定现象,导致吞吐量、时 延性能严重下降。 由于轮转机制具有低复杂度、硬件易实现等优 良特性,成为实用性研究方面的重点,其中典型的 调度算法有RR(Round-Robin)-RR(Round-Robin)12 和LQF(Longest Queue First)-RR 3 。虽然RR-RR 简单易实现、复杂度仅为O(1),但是在非均匀流量 下不能提供良好的吞吐量和时延性能。LQF-RR算 法在输入端总是优先服务最长的VOQ,尽量保持各 个队列调度均衡, 在各种流量下都具有优良的性能, 然而该算法复杂度为O(logN), 限制了算法在高速处 理环境下的应用。
6、为了提高CICQ交换结构在非均匀 流量下的性能,研究者通过改进轮转指针更新的规 则,基于RR-RR提出了众多改进算法,例如 RR-AF(Adaptable-size Frame-based) 13 , DRR (Differential Round Robin) 14 ,FD(Full Draining)- RR 15 ,QD(Quantum-based Draining)-RR 15 以及 FDR (Fair service and Dynamic Round robin)16 等算法。这些算法基本思想都是通过为每个VOQ分 配固定的调度份额、或者根据相邻调度VOQ长度关 系的“差分因子”来
7、约束轮转指针的更新。上述算 法复杂度都是O(1),保留了RR-RR低复杂度的特 点,仿真结果表明,当每个交叉点容量是1个信元大 小时,在非均匀流量下能够获得较好的吞吐量和时 延性能,然而它们的 “份额”或者“差分因子”的 取值都是仿真得到的经验值,难以穷举各种复杂的 业务流量进行可靠性验证。 因此,高效、实用的调度算法应当在简单的 RR-RR算法的基础上,通过某些指针更新策略弥补 其在非均匀流量下性能不佳的缺憾,并且新的更新 策略不依赖其他人为设定的“经验”参数,能够保 持低复杂度,并能适应各种非均匀流量网络环境, 为此,本文也从实用性角度出发,提出一种基于最 长队列预测的轮转型调度算法RR-
8、LQD(Round Robin Based on Longest Queue Detecting),其主 要思想是在输入端内局部预测队列最长的VOQ并 尽力为该队列服务, 保持调度中各个队列长度均衡, 提高系统稳定性。RR-LQD算法依据队列长度信息 进行调度,消除了对各种经验参数的依赖,从根本 上能够适应各种业务流量,仿真结果证明,这十分 有助于提高CICQ交换结构在非均匀流量下吞吐量、 时延等性能。同时,RR-LQD算法以求解局部最佳 取代LQF-RR算法的全局最佳,从而省略了排序比 较的过程,大大降低了算法的复杂度,算法复杂度 仅为O(1),却能够提供近似于LQF-RR算法的吞吐 量、时
9、延性能。 2 CICQ 交换结构及其调度描述 如图1所示,一个NN的CICQ交换结构由N个 输入/输出端和带交叉点缓存的Crossbar组成。每个 交叉点的缓存记为CB(Crosspoint Buffer),在每个 输入端内均采用VOQ的队列组织方式,用VOQ ij 表 示第i个输入端缓存中的第j条虚拟输出队列, 将与之 对应的交叉点缓存记做CB ij ,其中1i, jN。 为解决输入/输出端的竞争,每一个输入/输出 端都分别设有一个调度器。通常,为了实现高速交 换和控制上的方便,交换结构处理的数据单元为固 定长度的信元。各个输入/输出端支持相同的速率, 传输一个信元所需的时间称为一个时隙。在
10、每个时 隙内,每个输入调度器从其输入端的N个VOQ队列 中选出一个送往相应的交叉点;每个输出调度器从 对应的N个交叉点缓存中选出一个输出。输入和输 出端调度器之间不需信息的交互,可以分别独立执 行。 3 RR-LQD 算法 3.1 算法描述 为了算法描述方便,引入如下符号:VOQ ij 在 t 时刻的队列长度表示为 L(VOQ ij , t);CB ij 在 t 时刻 的队列长度表示为 L(CB ij , t);一个交叉点缓存的最 大容量用 C 表示;t 时刻时,若 L(VOQ ij , t)0 且 L(CB ij , t)0,称 CB ij 为 ECB (Eligible Crosspoint Buffer)。