基于输入排队的可扩展交换结构调度算法的研究

论文摘要

交换结构（switch fabric）作为交换机和路由器的核心,如何提高其交换容量可扩展性和服务质量可预测性,是近十年来网络研究的一个热点和难点问题。一个典型的交换结构由三部分组成:输入端口、输出端口和交换内核。为了避免来自不同输入端口的信元同时发往同一个输出端口,需要在输出端口或者输入端口设置缓冲区,从而形成输出排队和输入排队两大基本交换结构。尽管输出排队型交换结构可以提供良好的服务质量保证（100%的吞吐率,有界的延迟,带宽公平性等）,然而其存储器的带宽却需要所有输入端口带宽总和,这极大限制了其扩展性。与之相比,输入排队型交换结构允许内部存储器的带宽工作在线速,其良好的可扩展性使其成为高性能路由器的主流交换结构。由于交换结构的调度算法负责将输入端口的信元通过交换内核发送至输出端口,所以它在提高交换设备的利用率及其服务质量保证方面起着关键性作用。本文从交换容量的可扩展性及服务质量可预测性的角度出发,研究了基于输入排队的不同类型交换结构下的调度算法设计。目前,核心交换机/路由器的主流交换结构一般采用交叉开关（crossbar）以保证交换内核无阻塞,并采用集中式调度器调度定长信元通过交叉开关。对于该交换结构,具有较强理论意义的一类算法为最大权重匹配算法,已证明对于任意容许的流量,均能达到100%的吞吐率,并且平均延迟有界,然而其算法的复杂度高达O（N3）,本文从局部搜索的角度研究了最大权重匹配的近似算法,结合局部搜索的可并行计算的特点,提出了一种并行随机调度算法及一种并行确定性调度算法,并且证明了算法的稳定性,与已有近似算法相比,具有更低的平均延迟。缓冲交叉开关型交换结构由于具有分布式存储及分布式调度的特点,是构建特比特级（Terabit）路由器的一种理想选择。由于轮转型调度算法易于硬件实现,具有较高的应用价值,从而得到了广泛的研究。现有轮转型算法在调度均匀流量时具有逼近100%的吞吐率,然而对于非均匀的流量,现有轮转型算法的吞吐率却明显下降。为解决此问题,与当前的单轮转指针不同,本文提出了一类双轮转指针的调度算法,即在每个输入调度器均设置了主指针与辅助指针,主指针对应的队列具有最高的调度优先级,算法可以根据各个队列的状态来动态决定何时更新主指针,当主指针对应的队列被流控机制阻塞时,将根据辅助指针依次公平服务其他队列。仿真实验表明,对于每个交叉点缓冲区仅有一个信元的交换结构,基于双指针的调度算法可以显著提高该交换结构在已知多种非均匀流量下的性能。对于缓冲交叉开关型交换结构,一般采用基于份额的流控机制,在这种方式下,为了确保输入和输出端口都可以工作保持（work-conserving）,每一个交叉点缓冲区大小至少需要线速乘以交换结构内部环路延迟,对于特比特级、多机柜的交换机,其交叉点缓冲

论文目录

• 摘要
• 图目录
• 表目录
• 第一章 绪论
• 1.1 交换结构参考模型
• 1.1.1 名词定义
• 1.1.2 交换结构组成
• 1.2 基于输入排队的交换结构调度模型
• 1.3 通信量模型
• 1.4 性能评价
• 1.5 相关工作
• 1.5.1 输入排队交叉开关型交换结构的调度算法
• 1.5.1.1 最大尺寸匹配算法（maximum size matching）
• 1.5.1.2 极大匹配型调度算法
• 1.5.1.3 最大权重匹配（maximum weight matching ）
• 1.5.1.4 极大权重匹配算法
• 1.5.1.5 最大权重匹配的近似算法
• 1.5.1.6 输入排队交叉开关型交换结构的服务质量分析
• 1.5.2 缓冲交叉开关型交换结构及其调度算法
• 1.5.2.1 CICQ 交换结构下的调度算法
• 1.5.2.2 小结
• 1.5.3 基于负载平衡的两级交换结构及相关算法
• 1.5.3.1 基于FCFS （first come first service）与EDF（earliest deadline first）的失序重排算法
• 1.5.3.2 全帧优先算法FFF （full frames first）与全帧有序优先算法FOFF （full ordered frames first）
• 1.5.3.3 基于邮箱的调度算法
• 1.5.3.4 小结
• 1.5.4 三级Clos 交换结构及相关算法
• 1.5.4.1 三级Clos 有缓冲区的交换结构ATLANTA
• 1.5.4.2 三级Clos 无缓冲区的交换结构及调度算法
• 1.5.4.3 小结
• 1.5.5 其他新型交换结构
• 1.5.5.1 并行分组交换结构 PPS （parallel packet switch）
• 1.5.5.2 SMS （switch-memory-switch） 交换结构
• 1.5.5.3 小结
• 1.6 本文的贡献
• 1.7 论文的组织
• 第二章 基于局部搜索技术的最大权重匹配近似算法
• 2.1 局部搜索技术简介
• 2.2 问题建模
• 2.3 基于局部搜索的随机化调度算法
• 2.3.1 GALS 的工作原理
• 2.3.2 GALS 算法描述
• 2.3.3 算法特点
• 2.4 基于局部搜索的并行随机化调度算法
• 2.4.1 算法描述
• 2.4.2 算法PGALS 的特点
• 2.5 基于局部搜索技术的确定性并行调度算法
• 2.5.1 算法描述
• 2.5.2 DPSA 算法的特点
• 2.6 小结
• 第三章 最大权重匹配近似算法的性能分析及实验评价
• 3.1 算法PGALS 的性能分析
• 3.2 算法DPSA 的性能分析
• 3.2.1 流体模型
• 3.2.2 算法DPSA 的稳定性
• 3.3 SIM 仿真环境简介
• 3.4 实验评价
• 3.4.1 GALS 的性能评价
• 3.4.2 PGALS 的性能评价
• 3.4.3 DPSA 的实验评价
• 3.5 小结
• 第四章 基于双轮转指针的缓冲交叉开关型交换结构调度算法
• 4.1 缓冲交叉开关型交换结构模型及其工作原理
• 4.2 FD-RR （full draining round robin ）调度算法
• 4.2.1 FD-RR 算法描述
• 4.2.2 FD-RR 算法仿真结果
• 4.3 基于份额的双指针轮转算法QD-RR（a quantum-based dual round-robin algorithm）
• 4.3.1 QD-RR 算法描述
• 4.3.2 QD-RR 的一个实例
• 4.3.3 QD-RR 算法仿真结果
• 4.4 一种流量自适应的启发式轮转型算法TARR （a traffic adaptive round-robin algorithm）
• 4.4.1 TARR 的数据结构
• 4.4.2 算法TARR 描述
• 4.4.3 算法TARR 的一个实例
• 4.4.4 TARR 仿真实验
• 4.5 小结
• 第五章 缓冲交叉开关结构中的均匀交换问题
• 5.1 实时调度理论简介[Buttazzo 1997]
• 5.2 均匀交换问题
• 5.3 均匀交换的定量刻划
• 5.3.1 覆盖均匀性（covering smoothness）
• 5.3.2 间隔均匀性（spacing smoothness）
• 5.3.3 覆盖均匀性与间隔均匀性的关系
• 5.4 算法F-sMux 及其均匀性分析
• 5.5 支持均匀交换的路由器交换结构Sbux
• 5.5.1 Sbux 交换结构模型
• 5.5.2 XPB 容量需求的分析
• 5.5.3 支持流一级均匀交换的路由器交换结构Sbux
• 5.6 小结
• 第六章 结束语
• 6.1 本文工作总结
• 6.2 下一步研究方向
• 附录A （FD-RR 算法的伪码描述）:
• 附录B （QD-RR 算法的伪码描述）
• 附录C （TARR 算法的伪码描述）
• 附录D （算法 F-sMux 的流程图）:
• 参考文献
• 致谢
• 作者简历