基于局部故障信息路由算法(Safety level与Safety 向量)

基于局部故障信息路由算法(Safety level与Safety 向量)
摘 要
在设计多处理器系统上，拓扑连接结构尤为重要。拓扑结构可以把实际的连接网络用图来表示，每个结点代表一个处理器，每条连线代表每两个处理器的连接。Cayley图为我们提供了一组系统的方法模型，让我们系统的从超立方体或者星图上面研究网络的连接。星图在描绘网络连接时在图的度数和直径上都比超立方体有优势。当结点或链路在网络连接时出现错误时，有部分路径是不可用，导致某些路径要绕路或者导致路径不通。在这种情况下，我们需要一个容错算法演绎路由选择。
基于错误结点的情况，容错路径能够分为以下三类：
1， 基于全局信息方法；
2， 基于局部信息方法；
3，限制全局信息方法。
限制全局信息方法分别有两种:安全系数方法和安全向量方法。而安全向量方法的扩展称为扩展安全向量。
基于安全系数与安全向量的定义局限，在错误结点和错误链路同时出现的网络结构中，根据安全系数和安全向量定义下的算法可能找不到可能存在的可通路径，导致寻路失败。此文也针对这一局限提出的相应的改进，在安全系数和安全向量定义的基础上增加一些元素来描述结点的性质和邻结点的错误信息，这些信息可以作为算法寻路时判断的标准。
    最后我们介绍一种基于局部信息方法的新算法。它在每个n维结点上设置一个n维矩阵，用此矩阵来记录其邻结点的错误信息。这种方法比起传统的路由算法不但可以引导未来两步的走向而且可以减少路径的迂回。

关键词：安全系数，安全向量，扩展安全向量，拓扑结构，超立方体网络

*若需了解更多与协助请咨询↓→[电脑QQ][手机QQ]【数据协助】