关于广义超立方体网络的容错性和通信延迟 被引量：8

1

作者 徐俊明 《中国科学技术大学学报》 CAS CSCD 北大核心 2001年第1期16-20,共5页

直径是度量并行计算系统网络的容错性和信息延迟的重要参数 .广义超立方体网络Q(m1,m2 ,… ,mn)是并行计算系统网络中的一个重要拓扑结构 .令k=m1+m2 +… +mn-n .论文证明 :Q(m1,m2 ,… ,mn)的k直径等于n+ 1 .

关键词 广义超立方体网络 容错性 通信延迟 连通度 宽直径 并行计算系统网络 拓扑结构

下载PDF 职称材料

一般化超立方网络的容错寻径算法 被引量：3

2

作者 童明生 刘长河 范天佑 《计算机学报》 EI CSCD 北大核心 1998年第12期1074-1083,共10页

本文研究一般化超立方网络（GeneralizedHypercube，简记为GHC）的容错寻径算法．给定一个一般化超立方网络G（m，r）：N=mr（m≥2，r≥1），F为其故障结点集合，且G（m，r）-F是连通的，S和D是G（m，r）中任意两个非故障结点，其汉明距... 本文研究一般化超立方网络（GeneralizedHypercube，简记为GHC）的容错寻径算法．给定一个一般化超立方网络G（m，r）：N=mr（m≥2，r≥1），F为其故障结点集合，且G（m，r）-F是连通的，S和D是G（m，r）中任意两个非故障结点，其汉明距离H（S，D）=h，则当故障结点的个数|F|＜d时，一定存在一条长度≤h＋2的非故障路径P（S，D），而当d≤|F|＜m（d-m＋1）时，一定存在一条长度≤h＋4m-2的非故障路径P（S，D）．这里d是G（m，r）的度，路径P（S，D）是非故障的是指在P（S，D）上的所有结点均非故障．本文还给出其寻径算法． 展开更多

关键词 互连网络 容错 寻径算法 计算机网络 GHC

下载PDF 职称材料

广义超立方体网络容错路由算法 被引量：3

3

作者 刘红美 《武汉理工大学学报（交通科学与工程版）》 2006年第4期682-685,共4页

基于广义超立方体图的局部连通性概念,讨论了具有局部连通性的广义超立方体网络的容错路由算法.一个局部连通的广义超立方体网络可以容许大量的错误结点比较均匀地存在于多个广义子立方体而仍保证其全局连通性.对失效结点比较集中的情况... 基于广义超立方体图的局部连通性概念,讨论了具有局部连通性的广义超立方体网络的容错路由算法.一个局部连通的广义超立方体网络可以容许大量的错误结点比较均匀地存在于多个广义子立方体而仍保证其全局连通性.对失效结点比较集中的情况,给出了路由算法. 展开更多

关键词 广义超立方体 容错 路由算法 局部连通性

下载PDF 职称材料

基于NPV广义超立方体最佳容错路由算法(英文) 被引量：1

4

作者 田绍槐 陆应平 张大方 《软件学报》 EI CSCD 北大核心 2007年第7期1818-1830,共13页

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

关键词 容错路由 广义超立方体 节点通路向量 中转点技术

下载PDF 职称材料

广义超立方体网络的容错性和通信延迟 被引量：1

5

作者 侯晶 张先迪 《电子科技大学学报》 EI CAS CSCD 北大核心 2006年第2期268-270,共3页

宽直径是用来同时度量并行计算系统的容错性和通信延迟的新参数。广义超立方体网络是并行计算系统网络的一个重要拓扑结构。论文用两种方法给出了广义超立方体网络宽直径的具体证明,而两种方法的主要区别在于分别采用数学归纳法和直接... 宽直径是用来同时度量并行计算系统的容错性和通信延迟的新参数。广义超立方体网络是并行计算系统网络的一个重要拓扑结构。论文用两种方法给出了广义超立方体网络宽直径的具体证明,而两种方法的主要区别在于分别采用数学归纳法和直接构造法证明了不等式(1)。 展开更多

关键词 广义超立方体 连通度 直径 宽直径

下载PDF 职称材料

广义超立方体网络的容错路由分析 被引量：1

6

作者 公维凤 王传会 《山东轻工业学院学报（自然科学版）》 CAS 2006年第4期34-38,共5页

讨论了广义超立方体网络的容错路由问题。并在此基础上证明了当无效点很多时,只要存在某个(n-1)-维广立方体中无效节点不超过两个,则该n-维广义超立方体中的任意两个有效节点x和y之间的有效路由长度区间为[H(x,y),O(x,y)+4]。这里H(x,y... 讨论了广义超立方体网络的容错路由问题。并在此基础上证明了当无效点很多时,只要存在某个(n-1)-维广立方体中无效节点不超过两个,则该n-维广义超立方体中的任意两个有效节点x和y之间的有效路由长度区间为[H(x,y),O(x,y)+4]。这里H(x,y)表示x到y的汉明距离,O(x,y)表示x到y的最优距离。 展开更多

关键词 广义超立方体 容错路由 汉明距离 内点不交 最优路由

下载PDF 职称材料

广义超立方体网络中一类容错路由选择 被引量：1

7

作者 公维凤 刘红美 +1 位作者 宦红伦 谢炜 《数学的实践与认识》 CSCD 北大核心 2006年第9期244-249,共6页

证明了n-维广义超立方体网络Q(m1,m2,…,mn)中,任意两个节点x和y之间存在长度均不超过H(x,y)+2的m1+m2+…+mn-n条内点不交的路由,其中有H(x,y)条长度不超过H(x,y),此处H(x,y)表示x到y的汉明距离.并在此基础上讨论了广义超立方体网络的... 证明了n-维广义超立方体网络Q(m1,m2,…,mn)中,任意两个节点x和y之间存在长度均不超过H(x,y)+2的m1+m2+…+mn-n条内点不交的路由,其中有H(x,y)条长度不超过H(x,y),此处H(x,y)表示x到y的汉明距离.并在此基础上讨论了广义超立方体网络的容错路由问题.证明了即使无效点很多,但只要存在某个(n-1)-维广义超子立方体中无效节点较少,则该n-维广义超立方体中的任意两个有效节点之间可以找到最优路由或接近最优路由的有效路由. 展开更多

关键词 广义超立方体 内点不交 容错路由 最优路由

原文传递

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

8

作者 张涌逸 《电脑知识与技术》 2009年第10X期8418-8420,共3页

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

关键词 广义超立方体 容错 路由算法 广义子连通性

下载PDF 职称材料

广义超立方体的点扩张

9

作者 赵学峰 李喜平 《西北师范大学学报（自然科学版）》 CAS 2002年第4期35-38,共4页

通过广义超立方体的一种点扩张方法构造了广义超立方体循环网络,它包括了人们熟悉的带环连通立方体;证明了广义超立方体循环网络是Cayley图.

关键词 广义超立方体 点扩张 CAYLEY图 广义超立方体循环网络 拓扑结构 计算机网络 网络结构

下载PDF 职称材料

在BCube型拓扑中嵌入环结构

10

作者 任方俊 邓倩妮 《计算机应用研究》 CSCD 北大核心 2011年第6期2280-2285,共6页

在数据中心网络(DCN)中,为了实现BCube拓扑与基于环的应用的对接,利用互连网络与组合数学的知识,研究了在BCube中嵌入环(ring)结构的问题,提出了基于最小异维环组和递归化的算法。该算法找到了BCube(n,k)(n为偶数且k≥1)(简记为B(even,k... 在数据中心网络(DCN)中,为了实现BCube拓扑与基于环的应用的对接,利用互连网络与组合数学的知识,研究了在BCube中嵌入环(ring)结构的问题,提出了基于最小异维环组和递归化的算法。该算法找到了BCube(n,k)(n为偶数且k≥1)(简记为B(even,k≥1))中的Hamilton圈,能保证嵌入图的膨胀率是1;而且在BCube中的switch发生故障时,相对其他环嵌入算法,嵌入的膨胀率较小。针对BCube(n,k)(n为奇数且k≥1)(简记为B(odd,k≥1)),也提出了可供参考的环化算法。 展开更多

关键词 数据中心网络 BCube拓扑 环化 图嵌入 最小异维环组 广义超立方体

下载PDF 职称材料

广义超立方网络的容错寻径算法研究

11

作者 刘永峰 刘长河 寿玉亭 《北京工业大学学报》 CAS CSCD 北大核心 2001年第3期273-281,共9页

给定一个广义超立方网络以Ｇ（ｍ，ｒ）：Ｎ＝ｍｒ（ｍ≥２，ｒ≥１），其上有若干条连线发生故障，Ｆ为其故障连线集合，且 Ｇ（ｍ，ｒ）－Ｆ是连通的，Ｓ和 Ｄ是 Ｇ（ｍ，ｒ）中任意两个结点（处理器），其汉明距离 Ｈ（Ｓ， Ｄ）＝... 给定一个广义超立方网络以Ｇ（ｍ，ｒ）：Ｎ＝ｍｒ（ｍ≥２，ｒ≥１），其上有若干条连线发生故障，Ｆ为其故障连线集合，且 Ｇ（ｍ，ｒ）－Ｆ是连通的，Ｓ和 Ｄ是 Ｇ（ｍ，ｒ）中任意两个结点（处理器），其汉明距离 Ｈ（Ｓ， Ｄ）＝ｈ．得出如下结论：（１）当｜ｆ｜＜ｄ时，存在一条非故障路径Ｐ（Ｓ，Ｄ），且｜Ｐ（Ｓ，Ｄ）｜≤ｈ＋２； （２）当ｄ≤｜Ｆ｜＜ｍ（ｄ－ｍ＋１）时，存在一条非故障路径Ｐ（Ｓ，Ｄ），且｜Ｐ（Ｓ，Ｄ）｜≤ ｈ＋４ｍ－２．这里，ｄ是Ｇ（ｍ，ｒ）的度，｜Ｐ（Ｓ，Ｄ）｜ 是路径Ｐ（Ｓ，Ｄ）的长度，Ｐ（Ｓ，Ｄ）是非故障的是指在其上的所有连线均非故障．给出了寻径算法． 展开更多

关键词 广义超立方网络 容错寻径算法 处理器 互连网络 结点 结构分析

下载PDF 职称材料

Cayley图的笛卡尔乘积 被引量：6

12

作者 徐俊明 徐克力 《中国科学技术大学学报》 CAS CSCD 北大核心 2001年第6期635-640,共6页

Cayley图是由有限群导出的一类重要的高对称正则图 ,被认为是非常合适的互连网络拓扑结构 .而笛卡尔乘积则是从小规模的指定网络构造大规模网络的重要构造方法 .本文证明了Cayley图的笛卡尔乘积仍是Cayley图 .作为实例 ,指明循环网络、... Cayley图是由有限群导出的一类重要的高对称正则图 ,被认为是非常合适的互连网络拓扑结构 .而笛卡尔乘积则是从小规模的指定网络构造大规模网络的重要构造方法 .本文证明了Cayley图的笛卡尔乘积仍是Cayley图 .作为实例 ,指明循环网络、超立方体、广义超立方体、超环面和立方连通圈等都是Cayley图 . 展开更多

关键词 CAYLEY图 互连网络 超立方体 广义超立方体 笛卡尔乘积 拓扑结构

下载PDF 职称材料