局部扭曲立方体容错路由策略研究

摘要

互连网络为多计算机系统中处理器单元之间的通信提供了一种有效的机制，随着并行计算机互连网络规模越来越大，网络中出现处理机故障或处理机间的边故障的可能性也越来越大。因此，在出现处理机故障或处理机间的边故障的情况下，互连网络之间高效的通信成为评估该网络的一个重要依据。 局部扭曲立方体作为超立方体的变体，是一种新型的网络拓扑结构，保持了超立方体的很多优点的同时，其自身也有很多非常好的性质，直径大约只有超立方体的一半，拥有更好的容错和嵌入属性。基于局部扭曲立方体的这些良好的特性，使其成为最为重要和最有吸引力的网络模型之一。 本文主要是对n维局部扭曲立方体存在节点故障或边故障的情况下，如何实现消息传递进行了研究。下面是本文的主要研究工作： ①在节点故障的情况下，提出了一种基于节点安全级概念的单播容错路由算法。该算法除了考虑邻接节点的安全状况外，还充分利用了局部扭曲立方体自身特有的结构，使得信息尽可能沿最优路径传递。通过模拟仿真实验可知，算法具有较高的容错能力。当故障节点的数目达到或超过一半时，算法仍能保持一个相当高的容错路由成功率，且算法所选路径在多数情况下是最优路径。 ②在边故障的情况下，基于局部信息的思想，通过存储其邻接节点的边故障信息数组并引入消息回溯机制，设计了一种单播容错路由算法。仿真实验表明，当有大量的边发生故障时，该算法也能成功地实现消息传递。 ③在节点故障的情况下，基于路由能力的概念提出了一种单播容错路由算法，该算法首先寻找最短路径上满足路由能力值要求的邻接节点，其次寻找非最短路径上满足路由能力值要求的邻接节点。这样求得的容错路径首先是最优路径，其次为次优路径。 ④基于立方体分割的思想，设计了一种广播容错路由算法。通过证明可知，若源节点为安全节点，算法产生的广播树是最优的；若源节点为非安全节点(故障节点数小于n)，广播能够在，n+1步内完成。 ⑤接着，我们提出了一种基于单播的多播容错路由算法，该算法通过把局部扭曲立方体多播组节点分成若干个较小的子集合，多播消息只在各个子集合间进行路由，并由各子集合独立完成消息传递。

目录

文摘

英文文摘

声明

1绪论

1.1引言

1.2互连网络拓扑结构介绍

1.3国内外研究现状

1.4论文的组织结构

2基础知识

2.1局部扭曲立方体及其性质

2.2三种典型的容错路由算法介绍

2.2.1基于本地信息的容错路由算法

2.2.2基于非本地信息的容错路由算法

2.2.3基于图搜索的容错路由算法

2.3本章小结

3局部扭曲立方体单播容错路由算法

3.1基于安全级的单播容错路由算法

3.1.1基本概念

3.1.2算法描述

3.1.3实例分析

3.1.4实验结果及性能分析

3.2基于局部信息的单播容错路由算法

3.2.1算法描述

3.2.2实例分析

3.2.3实验结果及性能分析

3.3基于路由能力概念的单播容错路由算法

3.3.1基本概念

3.3.2算法描述

3.3.3实例分析

3.3.4算法正确性证明

3.4本章小结

4局部扭曲立方体多播容错路由算法

4.1局部扭曲立方体广播容错路由算法

4.1.1基本概念

4.1.2算法描述

4.1.3实例分析

4.1.4算法正确性证明

4.2基于单播的多播容错路由算法

4.2.1算法描述

4.2.2实例分析

4.3本章小结

5全文总结

致 谢

参考文献

附录