超立方体网络并行容错路由算法

研究了具有大量错误结点的超立方体网络中的并行容错路由算法.其步骤是首先,通过实验分析基于局部k维子立方体连通性容错模型中并行容错路由算法的容错性和效率,然后分析k=3且有多达25.0%的错误结点时并行容错路由算法的容错性和效率.研究结果表明并行路由算法所能找到的并行路径的数目最多可达到min(D(u),D(v)),至少可达到min(Dk(u),Dk(v));如果只考虑k比较小(如3,4,5等)而n比较大(如10,15,20等)的情况,则min(D(u),D(v))与min(Dk(u),Dk(v))非常接近,说明并行路由算法所能找到的尽可能多的并行路径的能力是接近最优的;并行容错路由算法容错性强,效率高.     

超立方体中基于安全矩阵的容错路由

超立方体网络拓扑结构是多处理机系统中常见的一种.随着多处理机系统规模的增大,系统出现链路与结点故障的概率也随之增大.针对超立方体结构的容错路由设计在信息传输过程中出现迂回的情况,提出了安全矩阵(safety matrices,简称SMs)这一概念,给出了一种建立SMs的方法及其容错路由算法.n维超立方体每个结点所需的存储开销为n2个字,安全矩阵记录了局部更多的信息.与传统的路由算法相比,该算法可以避免信息在传输过程中出现迂回和死锁,使路径达到最优.     

n维超立方体Q_n中边不交的生成树

边不交生成树的研究在互连网络并行广播通讯中具有重要的理论意义和应用价值。设Γ(Qn)为超立方体Qn中以vo为根节点的全体边不交生成树的集合,本文主要讨论|Γ(Qn)|的上界和下界,得到下列结果:(1)|Γ(Qn)|≤n·2n-12n-1,(2)当n≥4时,|Γ(Qn)|≥2。这些结果为设计超立方体互连网络中并行广播路由算法提供了理论依据。     

超立方体网络容错性的概率分析

用概率分析的方法研究在给定结点错误概率的情况下超立方体网络容错性的概率,证明了一个具有1024个结点的10维超立方体网络能够容许多达10%的错误结点而具有99％的概率确保正确结点的连通性;如果结点的错误概率不超过0.1％,则所有实际规模的超立方体网络(结点数可多达1万亿个)能够具有99.9％的概率确保正确结点的连通性.研究结果表明,所提出的方法也能够用于研究其他层次结构的网络和其他网络通信问题.     

条件容错的增强立方体边不交路（英文）

研究增强立方体,它是超立方体显著的变形,并且是从立方体上添加一些补边得到,着重讨论边容错的增强立方体边不交路.主要结果:n维增强立方体Q_(n,k)(n≥3,2≤k≤n-1)是S-强Menger边连通的(|S|≤2n-3).     

Mesh网络容错单播路由算法

基于k Mesh子网连通的概念,提出一个简单的Mesh网络容错单播路由算法.该容错单播路由算法是基于局部信息的,因为路由算法在路由的过程中,只需要知道其相邻结点的信息而无需知道其他结点出错的情况.对于给定的源结点和目的结点,当路由路径扩展到每一个k Mesh子网中时,该子网均可独立地完成算法的操作而无需考虑算法在其他k Mesh子网中的操作状态.所以,路由算法是高度分布式的.容错单播路由算法的时间复杂性是最优的.模拟结果表明,路由算法所构造的路由路径长度非常接近于2个结点之间的最优路径长度.     

超立方体的边可区别数

针对图(点)可区别数,提出了图的边可区别数,给出了n阶路Pn和n阶圈Cn的边可区别数;根据n维超立方体Hn及其p次幂Hpn的结构特性,对n维超立方体Hn和n维超立方体p(＞2)次幂Hpn的边可区别数进行了研究,得到了n维超立方体及其高次幂Hpn的边可区别数的一个上界.即,当n=2时,H2的边可区别数为3;当n≥3时,Hn的边可区别数为2;当n≥4,n≥p＞2时,Hpn的边可区别数小于等于3.     

折叠超立方体网络的t/k诊断问题

为提高系统故障诊断的诊断度,Somani 和Peleg提出了t/k诊断故障策略. n维折叠超立方体网络是具有2n个顶点,(n+1)2n-1条边的(n+1)-维正则图,它是n维超立方体网络增加2n-1补边得到的.中证明了当n≥6和1≤k≤n+1时n维超立方体网络是t/k可诊断的,其中t=(k+1)(n+1)-1/2(k+1)(k+2)+1.     

交叉立方体的限制性连通度（英文）

G是一个图,h是一个正整数,一个图G的h-限制性连通度是使得G删除G中的某个点集使得G不连通且每个分支中点的度数至少是h的最小点集的基数.交叉立方体网络是超立方体的一个变形,在平行计算系统当中交叉立方体是最重要的网络之一.该文证明了n维交叉立方体2-和3-限制性连通度分别是4n-8(n≥4)和8n-24(n≥5).     

超立方体网络中基于LIP的广播容错路由算法

论文给出超立方体网络中的LIP容锆模型,基于该模型提出三个重要的性质定理,并给出超立方体网络中基于该模型的广播容错路由算法.该算法能容许大量的错误节点,且算法所需时间步仅与LIP节点数有关而与故障节点数无关,因此具有较大的优越性.