分组交换光网络中的调度算法研究与仿真

摘要

随着Internet网络的高速发展和宽带技术的不断更新，宽带视频、多媒体等各种实时数据流量急剧增加，对通信网的带宽和核心路由器的性能提出了更高的要求，即更高的传输速率和提供确定的服务质量保障(时延抖动、吞吐量等)。 为了适应日益增长的带宽资源需求，作为通信网的两大主要组成部分——传输和交换都在不断的发展和革新。近几年，由于光通信技术尤其是DWDM技术的成熟，光网络因其巨大的频带资源和优越的传输性能，使主干链路的传输带宽不再成为问题。然而，传统的基于总线和中央处理器结构的路由器，由于其体系结构上的局限已经无法满足组建高速主干网络的需求。国际上提出了用交换结构提高各接口单元之间的数据通信速度的基本思想，交换结构成为影响交换机性能的核心模块，光交换技术已经成为实现全光网络的核心技术。但目前世界上的光交换技术都处于电控光交换阶段，即信号交换是全光的，光器件的控制仍由电子电路来完成。 为了保证一定的服务质量，核心路由器必须设法增加交换能力。在普遍采用的定长分组交换结构中，忽略同步和传输时延的情况下，核心交换机的性能主要受排队策略和调度算法的影响。排队策略决定如何缓存到达的分组；调度算法则是通过解决在每一个时隙中发生在相同输出端口的冲突问题，控制业务流对交换网络结构的有序访问。 本文中基于目前最有发展前景的电存储-光交换混合结构，针对带有虚拟输出队列(VOQ)的交换网络结构，研究了分组交换光网络中的高吞吐量和低抖动的调度问题，采用基于矩阵分解的静态调度算法进行求解。在深入研究和分析了以往的调度模型与调度算法的基础上，针对带有VOQ的Crossbar交换结构中的调度问题(NP-hard问题)，提出采用遗传优化算法来解决，并制定了该问题特有的编码、交叉和变异等遗传算子的设计方案。最后，运用仿真程序分析了该算法的吞吐量、抖动性能，并与传统的算法进行了比较。

目录

文摘

英文文摘

论文说明：符号说明

声明

第一章 绪论

1.1调度的基本概念

1.2调度算法类型

1.3网络调度的主要性能指标

1.4光交换网络

1.4.1交换节点结构

1.4.2光分组交换帧格式

1.5光分组交换技术

1.6网络中的重要问题

1.6.1分组竞争

1.6.2同步

1.6.3时延

参考文献

第二章 交换体系结构与调度算法概述

2.1交换机内核结构

2.1.1 Crossbar交换结构

2.2缓冲队列结构

2.3交换机调度算法

2.3.1输出队列调度算法

2.3.2输入队列调度算法

2.3.3带VOQ的输入队列调度算法

2.4基于VOQ结构的调度算法分类

2.4.1矩阵分解法

2.5交换网络调度模型

2.6本章小节

参考文献

第三章智能优化问题及遗传算法概述

3.1优化问题及其求解方法

3.2计算复杂性与NP完全问题

3.2.1计算复杂性的概念

3.2.2 P，NP，NP-C和NP-Hard问题

3.3遗传算法概述

3.3.1编码

3.3.2适应度函数

3.3.3算法控制参数选取

3.3.4遗传算子

3.4本章小节

参考文献

第四章 高吞吐量调度模型与算法

4.1高吞吐量调度数学模型

4.2高吞吐量调度算法

4.2.1 BV算法的基本思想

4.2.2 BV算法吞吐量性能分析

4.3仿真与结果分析

4.4本章小节

参考文献

第五章 高吞吐量低抖动调度算法

5.1低抖动约束条件

5.2贪婪低抖动算法

5.2.1 GLJ算法的基本思想

5.2.2 GLJ算法实现步骤

5.2.3 GLJ算法性能分析

5.3仿真与结果分析

5.4本章小节

参考文献

第六章 高吞吐量低抖动调度模型与遗传算法

6.1高吞吐量低抖动调度的数学模型

6.2遗传算法

6.2.1编码

6.2.2初始化

6.2.3适应度函数与算法控制参数选取

6.2.4选择算子

6.2.5交叉算子

6.2.6变异算子

6.3两种典型的分组交换光网络

6.3.1时隙型WDM光网络

6.3.2无源光网络PON

6.4遗传算法抖动性能分析

6.5仿真与结果分析

6.6本章小节

参考文献

结束语

致谢

攻读硕士学位期间发表的学术论文目录