论文部分内容阅读
CICQ或者缓存交换结构具有内部无需提速及输入和输出的分组调度可以分布并行执行的优点,在高性能交换结构设计中具有独特优势。交换结构领域的开放问题是:低层调度上强调调度算法的实用性,需要有小缓存、低复杂度和高吞吐率的调度算法;而在满足更高约束条件的高层调度上,3个或3个以上类(即具有不同时限)的优先级分组调度问题被证明是一个NP-C问题,在交换机实时调度领域同样是一个研究的热点和难点。然而,现有研究成果所提出的低层调度算法只能达到其中一个或者几个性能指标,同时高层调度算法在近30年未能突破EDF类算法的性能极限。本文定位于解决以上研究问题。
在低层调度上,做出CICQ在均匀和非均匀流量下的性能分析结果。提出了CICQ交换结构调度算法设计的3个指标:小缓存、低复杂度和高吞吐率,并且输出端采用RR算法是最优的不二选择。提出一种小缓存、O(1)复杂度、100%吞吐率调度算法。在CICQ交叉点缓存1个分组的情况下,新算法在均匀与非均匀流量下均能达到100%吞吐率。新算法仅具有O(1)的复杂度,保持了Round-Robin算法简单有效特性,同时克服了Round-Robin算法在非均匀流量下的不稳定性。在高层调度上,提出了基于网络流模型的FIPS算法。FIPS算法采用了与经典的EDF类算法完全不同的调度策略。通过建立不同时限类分组集合之间的流模型,将多时限优先级调度的NP-C问题问题转化为求解带上下界的网络流优化问题。FIPS算法全局考虑而非随机地将低优先级分组提升到高优先级里的空闲位置进行调度。算法验证结果表明,FIPS算法比,EDF等经典算法具有更低的丢包率和更高的调度成功率。
低层调度提出的新算法不依赖于流量模型,有效克服由于流量不均匀造成的服务损失,这项研究工作基于可以将有限的缓存做进交叉点的硬件工业背景,新算法完全具备实用性。CICO结构采用调度新算法后,支持OC192的每端口成本大幅降低到现有成本的20%。