论文部分内容阅读
互连网络是改善并行计算机性能的一个关键因素。Torus网络作为直接网络中典型的拓扑结构之一,具有很多优越的性质。随着处理器数目的增多,网络容错性成为一个不可回避的研究课题。因此本文主要研究Torus网络的容错性及容错路由算法。
首先,本文基于k-Torus子网及概率模型研究Torus网络的容错性,给出一个简单的容错路由算法。在节点出错概率相互独立的假设下,计算出容错路由算法成功返回由正确节点组成路径的概率。对于几十万个节点以上的Torus网络,提出的容错路由算法找到由正确节点组成路径的概率可达99%,从而说明了Torus网络是一个容错性很强的网络拓扑结构。
然后,本文研究Torus网络中基于局部故障信息容错路由算法的实现,即给出一个基于标志位的容错路由算法。存储于Torus网络中各节点的标志位记录了系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路。标志位的赋值是通过与邻节点之间的信息交换来完成,因此所提的容错路由算法本质上是基于局部故障信息的。
最后,本文改进了一个针对超立方体网络提出的防止消息往返的容错路由算法。对于任意给定的源节点和目的节点,改进后的容错路由算法均能够找到一条路径长度接近于两个节点之间最优路径长度的容错路径。算法仍然只需要知道其邻节点的信息,而无须知道整个网络的情况。