具有大量错误结点的超立方体网络中的单播路由算法的设计与分析  

Unicast Routing Algorithms on Hypercube Networks with a Large Number of Faulty Nodes

作　　者：王国军[1] 陈松乔[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《小型微型计算机系统》2002年第8期920-925,共6页Journal of Chinese Computer Systems

基　　金：国家海外杰出青年自然科学基金 ( 6 992 82 0 1)资助 ;教育部高等学校骨干教师资助计划和长江学者奖励计划资助

摘　　要：本文讨论具有大量错误结点的超立方体网络中的单播路由算法 .假定 Hn是一个局部 3-维子立方体连通的 n-维超立方体网络并且每一个基本的 3-维子立方体中分别最多有 1个和 2个错误结点 ,本文提出的单播路由算法能够在线性时间找到路径长度分别为源结点和目的结点之间大约 1.5倍和 2倍海明距离的次优路径 .我们提出的单播路由算法只需要结点知道其邻结点的状态 ,而无需知道整个网络信息 ,也就是说 ,该算法是基于局部信息的 ,因而该算法具有很强的实际意义 .In this paper, we consider unicast routing algorithms on hypercube networks with a large number of faulty nodes. Suppose H n is a locally 3 subcube connected n dimensional hypercube network, in which every basic 3 subcube has at most one and two faulty nodes respectively, our unicast routing algorithms can find nearly optimal routing paths with length bounded by about 1.5 and 2 times the Hamming distance between the source node and the destination node respectively in linear time. Our unicast routing algorithms are local information based in the sense that each node in the network knows only its neighbors status and no global information of the network is required by the algorithms.

关 键 词：错误结点 超立方体网络 单播路由算法 设计 容错性 局部连通性 计算机网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]