超立方体图上的容错路由算法研究

论文摘要

随着现代工业对数据计算的要求越来越高，包括运算速度，运算准确度和连续性安全性，导致计算机技术飞速发展以适应各种计算的需要。多计算机系统和多处理器计算机系统的出现解决了对计算量的巨大需要，并且拥有很强的稳定性和安全性。超立方体网络是多处理机系统中常见的一种互连网络。由于多处理机系统的规模越来越大，系统中出现处理机故障或处理机间的链路故障的可能性也随之增加。因此设计较好的容错路由策略，尽可能多地记录系统中存在的最优通路的信息，使得当系统中存在故障的情况下实现更有效的容错路由，达到提高整个系统性能的目的，也越发显得重要。本文首先对一些基本概念作了介绍，包括当前多计算机系统的发展趋势，研究模型，图和超立方体图，容错路由及其算法。然后从一种最基本和简单的研究模型—安全系数模型入手，对超立方体网络的容错性能作了分析和介绍。但是安全系数模型是针对仅出现故障机的情况而言的，并且容错路由算法是一种近似贪婪算法，因此应用方面具有较大的局限性。所以在安全系数模型的基础上引入了安全向量模型。安全向量模型大大改善了其可用性，使超立方体网络中无论出现故障链路还是故障机都可以运用，只要故障机的数目不超过总数—1。但是安全向量算法的缺陷在于每个处理机的安全向量仅仅根据其相邻处理机的安全向量来计算得到，在一定程度上限制了每个处理机反映全局故障信息的能力，导致有些最优路由不能通过算法得到。扩展安全向量模型改进了安全向量模型的局限性，将范围扩大到距离为2以内的相邻处理机，也就是说根据距离为2以内的处理机的安全向量来确定该处理机的安全向量，使得得到的最优和次优容错路由的数目更接近于实际数目，大大提高了网络的容错性。本文在上述三种模型的基础上提出了改进型安全通路向量模型，即将所有的故障处理机转化成故障链路，简化了网络研究的复杂程度，然后针对纯故障链路的超立方体网络进行分析，提出了改进安全通路向量的定义，此种模型计算出来的安全向量比扩展安全向量更接近于实际值，并且比单纯解决故障机问题的安全系数模型和解决故障链路问题的安全通路向量模型更具有普遍性，也更实用。

论文目录

• 摘要
• ABSTRACT
• 目录
• Contents
• 第一章: 绪论
• 1.1 研究背景介绍
• 1.2 图和Cayley图
• 1.3 超立方体图
• 1.4 容错路由算法
• 1.4.1 基本概念
• 1.4.2 容错路由的方法
• 第二章: 安全系数和安全向量模型
• 2.1 安全系数模型
• 2.1.1 超立方体图的安全系数
• 2.1.2 超立方体图中安全系数的容错路由算法
• 2.1.3 超立方体图的安全系数的相关性质
• 2.2 安全向量模型
• 2.2.1 概念简述
• 2.2.2 安全向量在超立方体图上的应用
• 2.3 安全向量的局限性
• 第三章: 扩展安全向量模型
• 3.1 扩展安全向量的定义
• 3.2 扩展安全向量的赋值算法
• 3.3 路由算法
• 3.4 扩展安全向量的性质
• 第四章.改进型安全通路向量模型
• 4.1 安全通路向量的定义
• 4.2 安全通路向量改进
• 4.3 SPVs与SVs，ESVs数据对比示例
• 4.4 安全通路向量的赋值算法
• 4.5 路由算法与性能分析
• 4.5.1 路由算法
• 4.5.2 性能分析与比较
• 结论
• 参考文献
• 攻读学位期间发表的论文
• 致谢