Clos交叉矩阵中的路由算法研究

论文摘要

Clos网络自从诞生以来,广泛应用于电话网络、多处理器系统以及路由交换机中。作为一种流行的的多级交叉结构,具有成本低、可扩展性好以及良好的路由性能的特点,因此一直是研究的热点。目前智能光网络的发展要求交叉矩阵具有高容量、快速的端口配置和组播支持能力。而目前的Clos交叉矩阵,主要采用可重构无阻塞结构,在发生阻塞时需要对交叉矩阵的状态进行重构,目前的算法搜索重构解的时间长,无法找到最优的重构解,受影响的业务多,在单播业务和组播业务同时存在的时候组播业务的阻塞率太高。本文主要对Clos交叉矩阵中的路由算法进行了研究,主要的工作和贡献包括以下两个方面:1.针对单播业务中的重构问题,提出了一种改进的路由算法——最优重构路由算法(ORRA)。该算法首先采用顺序方法分配中间模块,出现阻塞时再进行重构,采用的重构算法是一种最优重构算法,它是在Paull算法的基础上,通过并行搜索不同的重构解,并在搜索过程中将这些重构解的集合构成输入重构树和输出重构树,重构树的每一个路径代表一个重构解,每个路径的深度代表一个重构解的重构次数,故按照此算法搜索到的第一个找到的解即为最优重构解。该重构算法是基于Paull算法的改进算法,因此重构树在有限的高度下必然能够找到最优的重构解。通过OPNET软件的仿真,发现通过ORRA算法在搜索出最优重构解的基础上并没有增加算法的运行时间和交叉矩阵中的阻塞率。2.研究了Clos交叉矩阵中的组播问题,并提出了一种基于四级Clos交叉矩阵结构的单组播混合业务的路由算法——置换路由算法(PRA)。该算法在三级Clos交叉矩阵的输入级前增加一级,称之为置换级,路由时先将每一个请求业务按照其扇出值及输入模块的负载置换到不同的输入模块,利用输入模块完成扇出,最后采用ORRA算法完成扇出后业务的路由。通过OPNET软件的仿真结果可以看出,通过该算法能够明显的降低单组播混合业务的阻塞率,特别是组播业务的阻塞率。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景及现状
• 1.1.1 自动交换光网络
• 1.1.2 ASON 网络中的业务
• 1.1.3 光网络中的传输设备
• 1.2 Clos 网络的介绍
• 1.2.1 结构及分类
• 1.2.2 单播阻塞条件分析
• 1.2.3 组播阻塞条件分析
• 1.2.4 阻塞率分析
• 1.3 论文内容及结构
• 第2章 现有的路由算法研究
• 2.1 单播路由算法分析
• 2.1.1 一次统一调整算法
• 2.1.2 逐条调整算法
• 2.2 组播路由算法介绍
• 2.2.1 扇出机制分析
• 2.2.2 现有组播路由算法分析
• 2.3 本章小结
• 第3章 ORRA 单播路由算法
• 3.1 算法描述
• 3.1.1 问题描述
• 3.1.2 ORRA 算法思路与实现
• 3.2 仿真结果与分析
• 3.2.1 仿真设置
• 3.2.2 仿真结果分析
• 3.3 本章小结
• 第4章 PRA 组播算法
• 4.1 Clos 交叉矩阵的结构的组播分析
• 4.1.1 Clos 交叉矩阵中的组播问题描述
• 4.1.2 改进的Clos 交叉矩阵结构
• 4.1.3 四级Clos 交叉矩阵分析
• 4.2 PRA 算法
• 4.2.1 问题描述
• 4.2.2 PRA 算法思路与实现
• 4.3 仿真分析
• 4.3.1 仿真设置
• 4.3.2 仿真结果分析
• 4.4 本章小结
• 第5章 结束语
• 5.1 本文的主要贡献
• 5.2 有待进一步研究的工作
• 致谢
• 参考文献
• 作者在读研期间的研究成果