交换超立方体网络容错路由研究

为了研究交换超立方体网络容错路由问题,引入了相邻结点集合类的概念,提出了相邻结点集的求解公式。对于满足任意子连通性条件的交换超立方体网络,给出了基于相邻结点集合类的自适应容错路由算法及算法的步长上界。仿真实验结果表明算法是有效的。     

具有混合故障广义超立方体中的容错路由

针对广义超立方体网络中的同时具有大量结点和链路故障模式,提出了两类新的局部连通性概念。在这两类局部连通性概念的基础上给出了两个广义超立方体网络的分布式容错路由算法。基于两类新的局部连通性概念的广义超立方体网络容错路由算法与基于局部连通性的广义超立方体网络容错路由容错路由算法相比较,新算法提高了容错能力。     

故障超立方体网络中的高效容错路由算法研究

对超立方体网络中具有大量节点和链路故障模式进行了研究,提出了两类"子连通性"即k-维子连通性和任意子连通性的概念;基于两类子连通性概念,分别给出了两个满足该两类子连通性条件的超立方体网络的分布式容错路由算法.证明了已有的两类局部连通性概念中的条件"错误节点数小于正确节点数"是不必要的.提出的两个子连通性概念是两类局部连通性概念的最大扩展,可以在更大程度上保证整个超立方体网络的全局连通性,是已有的两类局部连通性概念的一种完全扩展.     

基于超立方体容错路由算法分析*

基于超立方体的优良的拓扑性质,提出了一个应用于超立方体网络的容错路由算法.该容错路由算法是基于局部信息的,因为路由算法在路由过程中,只需要知道其邻节点的信息,而无须知道其他节点的出错情况.对于给定的源节点和目的节点,路由算法均能够找到一条最优容错路径,并且可以预防死锁.模拟实验结果表明,路由算法所构造的路由路径长度接近于两个节点之间的最优路径长度.     

具有大量错误结点的超立方体网络中的高效路由算法的设计与讨论

该文提出了容错超立方体网络的一个很自然的机关报概念;局部连通性;讨论了两种类型的局部连通性;大局中部k-维子立方体连通性和局部子立方体连通性;一个局部连通的超立方体网络可容许大量错误结点且能确保超立方体网络是全局连通的;给出了满足局部连通性条件的超立方体网络中的几个高效的容错路由算法,文中的容错路由算法是分布式的和基于局部信息的,因而具有很强的实际意义。     

故障超立方体网络中的路由算法

针对超立方体结构的多处理机系统中存在故障的情况,提出了一个应用于超立方体网络的容错路由算法。该容错路由算法是基于局部信息的,只需要知道邻节点的状态,而无需知道整个网络的运行情况。对于给定的源节点和目的节点,路由算法均能够找到一条最优通路,并且可以预防死锁。模拟实验结果表明,路由算法所构造的路径长度接近于两个节点之间的最优路径长度。     

网络容错路由算法概率分析的一种新的方法

该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。     

基于NPV广义超立方体最佳容错路由算法

在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1) 定义广义超立方体系统;(2) 在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3) 提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4) 提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.     

交叉立方体互联网络的容错性研究

提出了交叉立方体网络的局部连通性和限制容错度概念,讨论了n维交叉立方体的局部k维子立方体连通性和局部子立方体连通性。利用这些结果,可以大大提高交叉立方体网络的容错能力。     

基于局部扭曲立方体的单播容错路由算法

对n维局部扭曲立方体存在节点故障时,提出了一种基于节点安全级概念的单播容错路由算法。该算法除了考虑邻接节点的安全状况外,还充分利用了局部扭曲立方体自身特有的结构,使得信息尽可能沿最优路径传递。通过模拟仿真实验可知,算法具有较高的容错能力。当故障节点的数目达到或超过一半时,算法仍能保持一个相当高的容错路由成功率,且算法所选路径在多数情况下是最优路径。     

三维Mesh网络容错路由算法及其概率分析

基于三维Mesh网络中k-Mesh子网连通的概念提出一个简单的基于局部信息和分布式的容错路由算法，并对其容错性进行概率分析．假设每个结点具有独立的出错概率，推导出路由算法成功返回由正确结点组成的路径的概率,结果表明即使三维Mesh网络上非常简单的路由算法也有相当高的成功概率．算法的时间复杂性是线性的,所构造的路由路径长度非常接近两点间的最优路径长度．另外，基于k-Mesh子网容错模型提出的容错路由算法是基于局部信息的和分布式的，因而具有很好的实际意义．     

局部子立方体连通的超立方体网络容错路由算法和概率分析研究

In this paper, first we analyze and give opinions of fault tolerant routing and probabilistic analysis. Then,on the basis of locally subcube-connected hypercube networks, we put forward some ideas to develop efficient fault tolerant routing algorithms and powerful probabilistic analysis techniques to study fault tolerant models and the corre-sponding routing algorithms, which is of great importance to the research of parallel computer interconnection net-works.     

Mesh网络路由算法容错性的概率分析

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．     

超立方体互连网络自适应简捷盲寻径搜索算法

根据n-cube超立方体互连网络的并行特点，分析了任意当前结点相邻集合类的求解方法，并给出一种自适应优化盲寻径搜索算法，即通过任一当前结点的Hamming距离相邻测度，寻找从任一始发结点到目标结点的所有可能的自适应盲寻径优化算法．     

超立方体多处理机系统中基于扩展最优通路矩阵的容错路由

该文在高峰等文章的基础上，提出了针对超立方体结构多处理机系统的扩展最优通路矩阵（Extended Optimal Path Matrices,EOPMs）的概念，并给出了一个建立EIPMs的算法和基于EOPMs的容错路由算法，证明了基于EOPMs的容错路由算法是基于扩展安全向量（ESVs）^[13]和基于最优通路矩阵（OPMs)^[14]容错路由算法的扩展，与原文相比，该算法的存储开销与OPMs,相同，但记录的最优通路的信息，包含了原文所记录的最优通路的信息，使搜索最优通路的能力比它们有进一步的提高。     

基于路由选择能力的容错路由选择

本文基于路由选择能力的概念,建立了一个有效的路由选择算法,该算法在故障超立方上具有较强的容错性,并可在不连通的故障立方体或含有故障边的立方体上使用。