多级交换网络路由算法与阻塞率研究

论文摘要

多级Clos网络是一种典型的可扩展交叉互连结构,在数据通信和计算机并行网络中有着广泛应用。基于传统三级Clos网络C（m, n, r）的理论分析表明,当满足m≥2n-1时该网络是严格无阻塞的。该文针地多时隙业务和实际应用情况提出两种基于Clos网络拓扑的交换网络,一种是一、三级具有时隙交叉能力而中间级无交叉能力的网络,该网络一般用于中间级是光交叉模块的交换系统中,针对该网络,本文提出了若干种选路策略和配通算法,该算法针对不同的阻塞类型分别处理做到全配通,另外,本文对该算法的性能进行详尽地仿真分析,分析结果表明该算法与传统的处理单时隙的算法相比具有重排次数低、运行时间快等特点。另一种是利用可快速实现时隙交叉的单级交换模块,构建了一种新型的MTS-Clos交换网络结构C（m, n, r, t）（Multiple Time Slot Clos network）.该网络的每一级都具有时隙调整能力,利用时隙交叉能力,该结构在保留原有网络特性的同时可提供更为理想的交换性能。针对该网络本文提出了几种选路策略和一种配能算法,该算法充分利用了多时隙业务的特点和网络的性能,通过详细的仿真分析得出此算法重排次数低,稳定性高等特点。另外针对MTS-Clos交换网络结构C（m, n, r, t）,采用随机分析模型,对该结构的阻塞率进行了理论分析,结果表明当中间级规模m=n+k,k是一个很小的非负整数,网络即达到无阻塞。对该结构的数值仿真有同样的结论。因此,该结构及分析结果对下一代大容量交换设备的设计,具有良好的参考价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 Clos网络基本结构和性能介绍
• 1.3 Clos网络的应用现状和发展趋势
• 1.4 Clos网络的分类
• 1.5 本文内容及结构安排
• 第二章 传统网络环境下的Clos网络路由算法与阻塞率分析
• 2.1 全局重排算法
• 2.1.1 矩阵分解法
• 2.1.2 二分图的匹配和着色
• 2.1.3 连接说明矩阵及其应用
• 2.2 逐条重排算法
• 2.2.1 路径选择策略
• 2.2.2 重构方法
• 2.2.3 Paull算法
• 2.2.4 现有算法总结与对比
• 2.3 传统网络环境下的Clos网络阻塞率分析模型
• 2.3.1 Lee模型
• 2.3.2 C.Jacobacus模型
• 2.3.3 Yang模型
• 2.3.4 阻塞率模型总结分析
• 第三章 多时隙环境下的Clos网络构造与仿真平台的建立
• 3.1 引言
• 3.2 TST交叉网络与Clos网络
• 3.3 STS交叉网络与Clos网络
• 3.4 三级都支持时隙重排的MTS-Clos构造
• 3.5 仅中间级不支持时隙重排的MTS-Clos构造
• 3.6 仿真平台
• 3.6.1 仿真平台功能
• 3.6.2 仿真流程
• 3.6.3 业务生成
• 3.6.4 业务拆除与重建
• 3.7 本章小结
• 第四章 三级都支持时隙重排的Clos网络阻塞率分析
• 4.1 阻塞率分析模型
• 4.1.1 假设与符号定义
• 4.1.2 级间链路繁忙概率分析
• 4.1.3 网络Clos（m,n,r,t）的阻塞率
• 4.2 仿真及分析
• 4.3 结论
• 第五章 三级都支持时隙重排的Clos网络路由算法
• 5.1 SlotPlan算法
• 5.1.1 SlotPlan算法设计思路
• 5.1.2 中间级分配策略的制定
• 5.1.3 SlotPlan算法重排过程
• 5.2 SlotPlan算法仿真分析
• 5.2.1 SlotPlan算法的基本业务配置
• 5.2.2 SlotPlan算法性能仿真分析
• 5.2.3 算法分析小结
• 第六章 仅中间级不支持时隙重排的Clos网络路由算法
• 6.1 SlotAssign算法设计思路
• 6.1.1 SlotAssign分配与策略
• 6.1.2 SlotAssign重排策略
• 6.2 SlotAssign算法的仿真结果与分析
• 6.2.1 基本业务配置
• 6.2.2 仿真结果与分析
• 6.2.3 算法分析小结
• 第七章 结束语
• 7.1 本文总结及主要贡献
• 致谢
• 参考文献
• 攻读硕士学位期间的研究成果