CICQ交换机调度算法及基于时限的优先级保证

摘要

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％。

目录

文摘

英文文摘

论文说明：图表目录，缩略词表

声明

第1章引言

1.1.研究背景

1.1.1工业背景

1.1.2挑战性课题

1.2.研究动机

1.3.问题描述

1.4.论文组织

第2章研究现状

2.1.交叉点无缓存交换结构及其调度算法

2.1.1 OQ与IQ结构及其调度算法

2.1.2 CIOQ结构及其调度算法

2.1.3 PPS结构的调度算法

2.1.4 Clos多级交换结构及其调度算法

2.2.交叉点缓存结构交换结构及其调度算法

2.3.低层调度与高层调度

2.4.技术路线与思路

2.5.小结

第3章均匀流量下的CICQ交换结构性能分析

3.1.分析Round-Robin调度算法的动机

3.2.CICQ交换机Round-Robin调度算法

3.3.稳定性概念

3.4.在均匀流量下的性能分析

3.5.小结

第4章非均匀流量下的CICQ交换结构性能分析

4.1.非均匀流量模型

4.2.非均匀流量下的吞吐率

4.3.两个结论

4.4.稳定域

4.1.1交换机及流量模型

4.1.2 RR-RR算法的稳定域

4.5.小结

第5章CICQ交换结构调度算法设计

5.1算法设计理念

5.2 XP内的缓存

5.3新算法

5.4服务最长队列的收敛速度

5.5小结

第6章CICQ交换结构调度算法性能评估

6.1仿真环境

6.2交换结构模型

6.3交叉点缓存的分组个数

6.4流量模型

6.5性能度量

6.6小结

第7章确保时限的优先级调度

7.1问题的引入

7.2相关研究进展

7.3单一服务类的调度算法

7.4两个服务类的调度算法

7.5小结

第8章三个以上类优先级的NP调度问题

8.1通用网络流算法

8.1.1一个判定合法流是否存在的己知算法

8.1.2优化问题的一个通用算法

8.1.3网络流G(s，t，U，V,E)优化问题的Max_Lower_Bound算法

8.2三个或者三个以上服务类的调度算法

8.3算法复杂度分析

8.4小结

第9章算法验证

9.1交换机模型

9.2可调度多时限类分组集合构造

9.3验证实验

9.4进一步讨论

9.5小结

第10章结论

10.1研究成果

10.2与已有研究结果的比较

10.3进一步研究的方向

致谢

参考文献

附录

个人简历