Torus交换结构流量均衡和容错路由算法研究

论文摘要

随着计算机广泛应用于各行各业,计算机应用在国民经济中扮演了越来越重要的角色。依赖于计算机应用的一些领域如国防、金融、气象对计算机的性能要求越来越高,它要求具有更快的处理速度,更高的带宽以及更大的存储容量。具有多处理器的并行计算机为实现高性能计算提供了可行的解决方案。基于多处理并行计算的相关技术也随之发展起来,如拓扑结构、交换技术、内部路由算法。Torus交换结构由于具有灵活的可扩展性,良好的对称性已成为构建大规模并行处理系统的常用选择。在给定网络拓扑结构情况下,影响并行计算系统性能的因素很多:如路由算法的自适应性、流量分布的均衡性。同时随着交换节点和服务类型的增多,路由算法具有容错性能以及支持QOS功能也不断得到重视。本文主要集中于在Torus交换结构下自适应均衡路由算法和容错路由算法的研究。针对以上问题,本研究的主要工作和贡献在于:提出了一种基于奇偶转弯模型的自适应均衡路由算法,该路由算法在两层虚网络中引入对偶的奇偶转弯模型,且数据包在虚网络中可以相互切换,对于所有的数据包而言都具有相同的路由自适应性,因此可以很好地引导数据流均衡地分布于系统,且受流量模型的影响较少,最大程度地提高了虚通道的利用率,能够较好地提高系统吞吐量,并在一定程度上减少了系统延时。进一步地,我们提出了基于正向优先负向优先（positive-first-negative-first）的容错路由算法,该算法充分利用了正向优先负向优先路由算法良好的自适应性,按照一定规则在双层虚通道上合理地分配数据包来避免死锁,该算法操作实施简单、计算复杂度低、响应速度快,可以适用于不同的故障模型的路由。本文的结构如下:第一章介绍了多维交换结构的拓扑结构,以及相应的基本交换技术和流控技术,对路由算法的基本要求如死锁、活锁以及饿死的情况进行了分析。第二章主要阐述了Torus交换结构中不同机制的路由算法,比较了各自的优缺点,然后介绍了本文的研究角度和相关工作。第三章主要研究了基于奇偶转弯模型的自适应路由算法,分析了双层奇偶转弯模型的路由自适应性以及流量的均衡性,阐述了算法的整体流程图,并进行无死锁的证明,然后根据不同的业务流模型,与其它路由算法进行了性能比较。第四章首先分析了正向优先负向优先自适应均衡路由算法的特性,对它具有的容错特性进行了研究,针对特定的故障模型情况加一些限制进行绕道路由。然后阐述了算法在容错路由的过程中正确绕道路由的机制,最后对算法的性能进行了评估,分析了性能下降的原因及可采用的应对措施。第五章主要阐述了仿真模型,给出了具体的仿真实验设计方案,模型建立和主要的功能模块的介绍。第六章对全文进行了总结,阐述了研究的不足以及以后的发展方向。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 多维交换网络的拓扑结构
• 1.2 基本的交换技术
• 1.2.1 虚跨步交换技术
• 1.2.2 虫孔交换技术
• 1.2.3 疯狂邮差交换
• 1.3 流控机制
• 1.3.1 虚通道技术
• 1.3.2 虚通道的工作机制
• 1.4 路由算法的基本要求
• 1.4.1 死锁、活锁及饿死
• 1.4.2 容错
• 1.5 全文研究思路及其内容安排
• 第二章 TORUS 交换结构中的路由算法
• 2.1 Torus 结构中的路由
• 2.1.1 确定性路由算法
• 2.1.2 自适应路由算法
• 2.2 资源分配策略
• 2.3 相关工作与本文研究角度
• 2.3.1 相关工作介绍
• 2.3.2 本文研究角度的选取
• 2.4 工程实现问题
• 2.5 本章内容小结
• 第三章 基于奇偶转弯模型的流量均衡路由算法设计
• 3.1 奇偶转弯模型
• 3.1.1 奇偶转弯模型介绍
• 3.1.2 自适应度分析
• 3.2 自适应均衡的路由算法设计
• 3.2.1 对称奇偶转弯模型设计
• 3.2.2 路由算法设计
• 3.2.2.1 路由标记函数
• 3.2.2.2 路由函数
• 3.2.2.3 路由选择函数
• 3.2.2.4 虚通道切换中的路由限制
• 3.2.3 算法流程图
• 3.3 路由算法无死锁证明
• 3.4 性能评估
• 3.5 本章内容小结
• 第四章 基于PFNF 容错路由算法设计
• 4.1 容错路由算法分类
• 4.1.1 基于本地信息的容错路由算法
• 4.1.2 基于全局信息的容错路由算法
• 4.2 故障模型分析
• 4.2.1 故障模型类型
• 4.2.2 故障模型生成算法
• 4.3 PFNF 容错路由算法设计
• 4.3.1 PFNF 路由算法介绍
• 4.3.2 基于PFNF 路由算法的容错路由机制
• 4.3.2.1 路由过程
• 4.3.2.2 Misrouting 方向判断
• 4.3.3 容错路由算法描述与实现的关键
• 4.3.4 虚拟信道分配机制
• 4.4 性能评估
• 4.5 本章内容小结
• 第五章 仿真模型
• 5.1 仿真模型设计
• 5.1.1 拓扑结构
• 5.1.2 交换节点设计
• 5.1.3 两级调度算法分析
• 5.1.4 业务源模型
• 第六章 全文总结
• 致谢
• 参考文献
• 攻读硕士学位期间取得的成果
• 个人简历