适于高速分组交换输出调度策略的研究与实现

论文摘要

随着因特网朝着高速化、宽带化的日益发展,人们对核心级路由器的性能提出了越来越高的要求,而路由器的交换结构和调度算法成为限制路由器性能的瓶颈。其中PPS（Parallel Packets Switches并行分组交换）交换结构因为其对存储器存储速率要求不高,易于构建大规模路由交换体系的优点成为目前T-Bit路由器技术中的研究热点。 在PPS交换结构的要求中,输出调度级的主要功能是通过调度算法合路输出各个核心交换子层送来的IP数据包,并根据线路接口模块的拥塞状态决定是否对数据包进行缓存。为了实现输出调度功能,文章结合国家863项目“可扩展到T比特的高性能IPv4/v6路由器基础平台及实验系统”,在较深入的研究了高速路由器调度算法及其实现技术的基础上,结合库存论原理讨论了无输入缓存PPS和带输入缓存PPS稳定工作的充要条件,并给出了输出合路器缓存的必要性以及其大小的下界。 在前述理论分析的基础上,文章提出了一种适合于PPS交换结构的合路输出调度算法:MWDRR（Modifying Weighted Deficit Round Robin）加权差额轮询算法,该算法较好的保证了各个子层交换结构数据在带宽分配上的公平性。文章从理论上分析了算法的复杂度和公平性,并给出了算法实现电路。同时从成本以及存储器的速率和容量方面考虑,介绍了一种采用普通DDR SDRAM内存即可实现的高达16.5Gbit/s访问带宽的缓存方案。综合采用了这两者的输出调度模块能够支持12路2.5G报文的合路调度,并在输出端口的速率达10Gbps时,具有250ms的数据报文缓存能力。 本文的创新和主要贡献主要包括以下几点: ● 从不同的分类角度系统归纳了常见的各种调度算法及其实现技术,并对算法的优劣点进行比较评析。 ● 结合库存论原理,从流交换的角度讨论了无输入缓存PPS和带输入缓存PPS稳定工作的条件,在此基础上,证明了输出缓存的必要性以及所需缓存的下界。 ● 根据排队论中的M/D/1队列模型,得出了输出合路调度服务中报文数据的等待时间取决与链路平均服务率的结论。 ● 提出了一种保障带宽分配的低复杂度算法MWDRR加权差额轮询算法,并在NS仿真实验中与其他算法比较,验证了该算法具有良好的公平性和时延特性。对算法的关键部分给出了详细的分析和设计。 ● 阐述了一种采用普通DDR内存即可实现的高速大容量报文缓存方案,并在FPGA中实现了DDR内存接口管理控制器。 ● 工程实现了支持12路2.5G报文的合路调度,并在输出端口的速率达10Gbps时,具有250ms的数据报文缓存能力的调度模块。

论文目录

• 目录
• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1 研究背景
• §1.2 高速分组交换研究中的热点问题
• §1.3 本文主要工作
• §1.4 论文的结构和安排
• 第二章 并行分组交换结构以及调度算法的研究分析
• §2.1 PPS结构的定义和模型
• §2.2 PPS结构的稳定工作条件
• §2.3 调度算法的分类及其性能指标
• §2.4 输出调度器的数学服务模型分析
• §2.5 本章小结
• 第三章 加权式变长分组MWDRR调度算法
• §3.1 引言
• §3.2 算法的提出和描述
• §3.3 算法的性能分析和比较
• §3.4 算法的工程实现分析
• §3.5 多门限随机早期探测MTRED
• §3.6 本章小结
• 第四章 大容量缓存结构及实现方案
• §4.1 引言
• §4.2 大容量缓存结构的意义和模型
• §4.3 大容量输出缓存工程实现方案
• §4.4 DDR内存接口的FPGA实现
• §4.5 本章小结
• 第五章 用于T比特路由器的输出调度策略实现方案
• §5.1 T比特路由器实现结构
• §5.2 输出调度结构设计
• §5.3 输出调度结构实现
• §5.4 本章小结
• 结束语
• 致谢
• 参考文献