多维交换结构容错技术研究

论文摘要

由于光传输网络技术的不断发展,使得Internet的传输网络的容量迅速增加,而且光传输网络中的各种设备成本也在不断降低。而路由器技术的发展尚未能完全满足整个Internet网络发展的需要,成为整个网络发展的瓶颈。多维交换结构由于其灵活的扩展性,已经成为构建大容量、可扩展路由器的常用选择之一,其中Mesh/Torus是多维交换网络中两种典型的互连网络结构。本文所研究的交换结构就是基于Mesh/Torus的交换网络。另一方面,随着高性能路由器中多维交换结构规模的扩大、节点数目的增多,多维交换结构中部件发生故障的可能性也随之增加,在交换结构上实现容错已经成为当前国内外研究的持续热点。多维交换结构中的容错技术是指部分部件失效的情况下交换网络运作的能力,然而容错技术的实现往往是以巨大的性能降低为代价,所以设计具有容错能力的高性能内部交换网技术是一个极具挑战性且极具意义的问题,其中容错路由是解决网络故障问题的一种有效方式。容错路由是在故障网络中将消息分组从正常源节点发送到正常目的节点的一种通信过程。为了保证多维交换结构的高性能和高可靠性,必须设计具有良好容错能力的路由算法。首先,本文从Mesh/Torus网络的拓扑结构、虫孔交换技术的基本理论、虚通道流控制和多维网络死锁几个角度出发,介绍本文研究的背景知识。其次,本文介绍了多维交换结构中容错路由研究的主要内容和相关的基础知识。在介绍基于Mesh/Torus新的容错路由算法之前,我们介绍了多维交换结构容错路由研究领域里一些著名的算法,并总结出良好的容错路由算法需具备的特征与性能参数。我们设计了两个新型的基于Mesh/Torus网络结构的容错路由算法。第一个算法是基于死锁恢复策略的自适应容错路由算法MMAR(Minimal Misrouted AdaptiveRouting)。MMAR算法基于各非故障节点周围链路的状态容错网路各部件故障,且通过在故障模型凹形区域表面节点中设置该凹形区域内节点的位置信息表以避免消息进入与其目的节点无关的凹形区域,以使消息绕道路径最短。同时,该算法采用死锁恢复策略解决网络死锁问题。第二个算法是基于故障均衡环的自适应容错路由算法EFAM。该算法解决了现有容错路由算法由于基于故障环绕行,容易使其成为热环而导致交换网络过早饱和的问题。同时,EFAM采用孔表面节点的代理机制有效解决多维交换网络出现宽孔凹型故障模型的情况,使凹型区域内的节点能正常发挥源节点、目的节点以及路由转发能力,提高网络性能。仿真结果表明,基于故障均衡环的容错路由算法性能比原有容错路由算法性能有很好的改善,有效地提高了交换网络的吞吐率,降低系统的平均延迟。最后,本文给出了为考察MMAR算法和EFAM算法的性能而基于OPNET搭建的仿真平台,算法的实现采用面向策略的设计模式。此外,本文还结合对仿真结果的讨论,提出了展开下一步研究的参考性建议。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 路由器体系结构的发展
• 1.2 多维交换结构概述
• 1.2.1 互连网络的分类
• 1.2.2 Mesh/Torus网络概述
• 1.2.2.1 n 维 Mesh结构
• 1.2.2.2 n 维 Torus结构
• 1.2.2.3 Mesh/Torus网络中节点的组成结构
• 1.2.3 多维交换结构路由的相关技术
• 1.2.3.1 虫孔路由技术
• 1.2.3.2 虚通道流控制机制
• 1.2.3.3 死锁解决方案
• 1.2.3.4 Mesh/Torus的路由算法
• 1.3 容错概述
• 1.3.1 容错的意义
• 1.3.2 多维交换网络中的容错
• 1.4 全文的研究思路及内容安排
• 第二章 多维交换网络的容错路由研究
• 2.1 问题分析
• 2.1.1 容错技术分类
• 2.1.2 容错路由性能评估参数
• 2.2 故障相关数学模型
• 2.3 一些典型的容错路由算法
• 2.4 工程实现问题
• 2.5 本章内容小结
• 第三章 MMAR:基于死锁恢复策略的自适应容错路由算法
• 3.1 MMAR算法概述
• 3.1.1 算法设计
• 3.1.2 算法流程
• 3.2 算法的关键技术分析
• 3.2.1 真完全自适应路由TEAR
• 3.2.2 死锁检测技术 FC3D
• 3.2.3 死锁恢复技术 DISHA
• 3.2.4 凹形区域孔的形成
• 3.3 仿真结果及分析
• 3.4 本章内容小结
• 第四章 基于故障均衡环的自适应容错路由算法
• 4.1 算法概述
• 4.1.1 EFAM路由算法基础
• 4.1.2 故障均衡环的形成
• 4.2 EFAM算法设计
• 4.2.1 EFAM算法步骤
• 4.2.2 EFAM算法流程
• 4.3 仿真结果及分析
• 4.4 本章内容小结
• 第五章 仿真模型设计与实现
• 5.1 多维交换结构仿真平台的架构
• 5.1.1 交换网络中分层结构
• 5.1.2 两级调度
• 5.2 多维交换结构仿真平台的节点模型
• 5.2.1 路由与仲裁模块
• 5.2.2 crossbar模块
• 5.2.3 分组切分模块
• 5.2.4 分组接收模块
• 5.3 本章内容小结
• 第六章 全文总结
• 致谢
• 参考文献
• 个人简历
• 作者在攻读硕士学位期间的研究成果