《一种基于最长队列预测的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)。
