用最优通路矩阵实现超立方体多处理机系统的容错路由

针对拓扑结构为超立方体的多处理机系统提出了最优通路矩阵（ＯＰＭ）的概念,并约出了一个基于最优通路矩阵的路由算法。存储于超产方体各节点中的最优通路矩阵记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路（长度等于两节点间Ｈａｍｍｉｎｇ距离的通路）。对于ｎ维超方立体,每个节点所需的存储开销为ｎ＾２个字,基于最优通路矩阵的路由算法所选的通路的长度不超过两点间的Ｈａｍｍｉｎｇ距离加２。     

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

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能,随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全通路矩阵(maximum safety path matrices,简称MSPMs)这一概念,给出了一种建立MSPMs及其容错路由算法.证明了MSPMs通过n-1轮邻节点之间的信息交换,能以矩阵的形式记录最多的最优通路     

超立方体多处理机系统中基于扩展安全向量的容错路由

针对超立方体结构的多处理机系统中存在链路故障的情况,修改了吴杰提出的安全向量的概念,提出了扩展安全向量的概念,并给出了一个基于扩展安全向量的容错路由算法,与基于安全向量的路由算法相比,基于扩展安全向量的路由算法搜索最优通路的能力有了非常大的提高,即使故障数较多时,它仍能保证把绝大多数源、目的节点间有最优通路和消息沿最优通路传递。超立方体结构中各节点扩展安全向量的赋值可以通过ｎ－１轮邻接点的信息交换     

超立方体系统中基于安全通路向量的容错路由

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能.随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对系统中存在链路故障的情况,提出了用于记录最优通路的安全通路向量(safety path vectors,简称SPVs)概念,并给出了建立SPVs及其容错路由算法.其中SPVs的赋值可以通过n-1轮邻节点之间的信息交换来完成,且算法中各节点的存储开销仅为n bits,因此,SPVs是安全向量(SVs)与扩展安全向量(ESVs)的一种扩展,具有比SVs和ESVs更好的记录最优通路的能力.另外，与基于最优通路矩阵(optimal path matrices,简称OPMs)及扩展最优通路矩阵(extended optimal path matrices,简称EOPMs)的容错路由算法相比,SPVs呈指数级地降低了算法的存储开销，且能够记录OPMs和EOPMs所不能记录到的最优通路信息.理论分析和仿真实验验证了SPVs的上述性能.     

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

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

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

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.     

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

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

超立方体网络下的自适应容错路由研究*

针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。     

TRANSCUBE—一个超立方体结构的多处理机系统

TRANSCUBE是一个基于分布存贮和信件传递的多处理机系统.它的核心是一个由多个Transputer组成的超立方体结构阵列.本文重点介绍了TRANSCUBE的系统结构和通信软件结构.     

基于LIP和RSC的超立方体网络单播容错路由算法*

基于LIP和RSC的概念,提出了一个有效的超立方体网络单播容错路由算法.该算法不仅能容纳指数级的错误节点,而且算法效率也很高.     

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

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

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

基于最优Path的Ad Hoc网络地理路由算法

对基于地理信息的自组网路由中的凹节点问题做了分析,并提出了一种新的解决方案——PGA算法及其改进算法.算法采用了最优Path的思想,在Path构造、基于Path的最优寻路、路由恢复等多个方面都应用了最优Path的概念,较好地解决了凹节点的问题.通过证明,该算法具有无环性,从而实现了基于局部路由信息的无状态路由,展示了算法的可扩展性和易维护性.实验表明,即使在大型网络中,算法依然可以保持很高的报文投递率、较短的路径长度、可接受的路由表大小及可控的协议带宽开销,同时该路由算法在动态环境中具有较强的鲁棒性.     

基于Pareto最优的QoS路由算法

QoS路由是QoS框架中的重要组成部分,旨在寻找多约束条件下的可行路径.在解决多约束(MCP)问题时,引入了Pareto最优概念.基于此概念,提出了基于Pareto最优的QoS权重空间划分模型.在该模型中,根据路由请求与MCP问题解的关系,很容易判定路由请求是否能够被满足.在模型基础上,提出了用于解决具有两可加约束的动态权重系数路由算法PODWCA,它平均只需要运行2～3次,Dijkstra算法就能达到很高的性能.仿真结果验证了PODWCA算法的有效性.     

点对点网络容错路由算法的路径长度分析

用概率性分析方法 ,研究了在结点错误概率性分布的情形下超立方体网络点对点容错路由算法的路径长度 ,得出了算法的路径长度期望值 ,分析表明 :对于结点错误概率 p≤ 10时 ,源点 U到终点 V所在的 k维子立方体的路径长度期望值不超过 1.11* h,比以往通常的长度分析结果 2 * h小得多 .提出一种改进的算法并证明这一新算法所构造的路径长度的期望值不大于 1.11h- 0 .11k 2 ,这大大改进了以前的路径 2 h k 2 ,其中 h为 U与 V的 Ham ming距离 .