广义超立方体网络中一类容错路由选择  

A Routing Strategies for Fault-tolerance Routing in Generalized Hypercube Networks

作　　者：公维凤[1] 刘红美[1] 宦红伦[1] 谢炜[1] 

机构地区：[1]三峡大学理学院,湖北宜昌443002

出　　处：《数学的实践与认识》2006年第9期244-249,共6页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10371048)

摘　　要：证明了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-维广义超立方体中的任意两个有效节点之间可以找到最优路由或接近最优路由的有效路由.This paper shows that there are m1＋m2＋…＋mn vertex-disjoint routes between any two nodesxandy, with length less than or equal to H（x,y） ＋ 2 in n-dimension ~：~eneralized Hypercube networks Q（m1,m2,…,mn） in which there exists H（x,y） routes betweenxandywith length equal to H（x,y）. here H（x,y） denotes Hamming distance betweenxandy. Based on this kind of topological structure, the issue of fault-tolerance routes is discussed in n-dimension Generalized Hypercube networks. When there are many faulty nodes, there is a feasible route arriving or approaching the optimum route if there exist fewer faulty nodes in one of the （n-1）-dimension Generalized Hypercubes.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]