高速路由器交换网络中调度算法的研究

摘要

本文对高速路由器交换网络中的调度算法进行了研究，包括基于crossbar结构的输入排队调度算法和基于负载平衡的两级交换结构的调度算法。 论文首先介绍了高速路由器的交换结构和发展概况，然后介绍了基于最新结构的crossbar的输入排队调度算法、输出排队调度算法和联合输入输出调度算法。其中基于极大匹配的输入排队调度算法有良好的性能，重点分析了几种极大匹配调度算法PIM、RRM、iSLIP算法，运用排队论分析了加入优先级算法的性能，并在此基础上提出了抗突发和非均匀业务的lp_iSLIP、op_iSLIP和OSRR算法。对负载平衡的两级交换算法进行了理论分析，证明了算法的稳定性和延时，对经典的UFS算法做了改进方案。最后通过仿真结果说明提出的几种算法性能有明显的改善。

目录

文摘

英文文摘

声明

第一章绪论

1.1课题背景

1.2路由器体系结构和发展

1.3国内外研究现状

1.4课题主要研究内容

第二章交换结构及算法分析

2.1调度算法的性能指标

2.2排队结构

2.2.1输出排队

2.2.2输入排队

2.2.3联合输入输出排队

2.3基于负载平衡的两级交换结构

2.4通信量模型

2.5本章小节

第三章输入排队调度算法的研究

3.1基于输入排队的交换结构调度模型

3.2几种极大匹配调度算法介绍

3.2.1 PIM算法

3.2.2 RRM算法

3.2.3 iSLIP算法

3.3基于优先级性能分析

3.3.1无优先级算法延时分析

3.3.2具有优先级算法延时分析

3.4 lp_iSLIP算法、op_iSLIP算法描述

3.5 OSRR算法描述

3.6本章小节

第四章负载平衡的两级交换结构和算法研究

4.1负载平衡交换机的基本结构

4.2算法稳定性分析

4.3算法延时分析

4.3.1均匀分布业务模型延时分析

4.3.2均匀突发业务模型延时分析

4.4 UFS算法分析及改进方案

4.4.1 UFS算法描述

4.4.2 LIFS算法特点

4.4.3 UFS算法的改进方案

4.5本章小节

第五章仿真性能及结果分析

5.1 SIM仿真平台介绍

5.2 SIM运行流程

5.3仿真结果分析

5.3.1 pri-iSLIP算法仿真

5.3.2 lp_iSLIP算法与op_iSLIP算法的仿真

5.3.3 OSRR算法仿真

5.4本章小节

第六章总结与展望

6.1研究成果

6.2未来工作的展望

参考文献

致谢

在学期间发表的学术论文和参加科研情况