高速路由器交换结构和调度算法的研究

摘要

随着网络流量和业务种类的剧增，交换设备性能的提升已经成为影响网络服务质量的关键因素。交换结构和调度算法是当今高速路由设备的核心技术和重点研究方向，其性能直接决定了高速路由设备的整体性能。
　　 本文首先从队列结构和体系结构两方面研究了交换结构的发展过程和现状。输出排队的队列结构能够提供较好的服务质量，但其对队列缓冲的读写速度的苛求极大的限制了发展。输入排队对于队列缓冲的读写速度不存在苛刻的要求，同时本身存在的队首阻塞的问题被研究者提出的虚拟输出队列(virtualoutput queue)的方式完全解决。另一方面，单机分布式交叉开关(crossbar)的体系结构能够保证交换内核并行处理多路数据流，大幅提升了系统整体的交换容量。输入排队的crossbar交换结构成为现今主流路由设备的首选结构。
　　 本文随后对采用输入排队crossbar交换结构的调度算法进行了研究。通过对调度模型的分析，将其抽象为无向二分图的匹配问题。本文选择了几种典型的极大匹配算法进行研究：并行迭代匹配算法由于采用随机仲裁的方式，实现复杂度较高；轮转匹配调度算法使用轮转优先级的仲裁方式，降低了实现的复杂度，但由于轮转指针更新规则存在缺陷，导致端口出现同步现象，影响了吞吐性能；滑动多次迭代调度算法解决了指针同步现象和不公平性导致的饿死现象，已经被交换设备厂商应用到实际产品中；较新提出的先到先服务轮转匹配调度算法做了进一步的优化，改善了延时性能和公平性。滑动多次迭代调度算法和先到先服务轮转匹配调度算法由于其实现简单和性能良好，成为如今主流的调度算法。但是，这两种算法在处理非均匀业务的时候，性能表现不佳。后文在这两种算法的基础上，提出了一种优化指针策略的low-FIRM算法，并对这种新算法进行详尽的性能分析和实现介绍。
　　 最后，本文设计并实现了针对输入排队crossbar交换结构的调度算法仿真平台，应用这个平台对新算法和两张典型算法进行了仿真实验。通过实验结果的比较，可以得出，本文提出的新算法不仅保持了典型算法在均匀业务流下的良好性能，而且对非均匀业务流下的性能表现有较显著的提升。

目录

文摘

英文文摘

声明

第1章 绪论

1.1引言

1.2研究背景及意义

1.2.1路由器成为网络性能提升的瓶颈

1.2.2研究意义

1.3研究现状

1.3.1交换结构

1.3.2调度算法

1.4本文主要工作

1.5论文结构安排

第2章 交换结构分析

2.1结构组成

2.2队列结构

2.2.1输出排队

2.2.2输入排队

2.2.3联合输入输出排队

2.3体系结构

2.3.1单机集中式总线

2.3.2单机分布式总线结构

2.3.3单机分布式crossbar

2.3.4多机互连集群

2.4本章小结

第3章 输入排队crossbar交换结构的调度算法

3.1调度模型

3.2通信量模型

3.2.1通信量的容许性

3.2.2信元到达过程

3.2.3流量分布模型

3.3算法设计的性能指标

3.3.1稳定性

3.3.2吞吐率

3.3.3时延特性

3.3.4公平性

3.3.5丢包率

3.3.6带宽利用率

3.3.7复杂性

3.4几种典型的极大匹配调度算法

3.4.1并行迭代匹配算法

3.4.2轮转匹配调度算法

3.4.3滑动多次迭代调度算法

3.4.4先到先服务轮转匹配调度算法

3.5本章小结

第4章 优化指针策略的low-FIRM调度算法

4.1两种输入排队调度算法的性能分析

4.2优化指针策略的low-FIRM调度算法

4.2.1算法的提出

4.2.2算法的性能分析

4.2.3算法的实现

4.3本章小结

第5章 仿真实验及性能评价

5.1仿真平台软件的设计与实现

5.1.1总体设计

5.1.2信元和队列

5.1.3流量发生器

5.1.4数据收集和性能分析

5.2仿真实验及结果

5.2.1实验环境设置

5.2.2均匀独立同分布流量下的仿真结果及分析

5.2.3强对角独立同分布流量下的仿真结果及分析

5.2.4弱对角独立同分布流量下的仿真结果及分析

5.2.5突发流量下的仿真结果及分析

5.3本章小结

第6章 总结和展望

6.1总结

6.2展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果