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

第 卷 第 期 小 型微 型计 算 机 系 统 #4 $ P/- Q#4 J/ Q$ 年 月 ## $ HIJI G HIKLM NON:)H AB (## 文 章 编 号： （ ） !! !## ## $!%#! 具有大量错误结点的超立方体网络中的 单播路由算法的设计与分析 王国军 陈松乔 陈建二 （中南大学 信息科学与工程学院 ，湖南 长沙3!$4 ） 摘 要：本文讨论具有大量错误结点的超立方体网络中的单播路由算法 假定 是一个局部 维子立方体连通的 ( 8 4! ! 维超立方体网络并且每一个基本的 维子立方体中分别最多有 个和 个错误结点，本文提出的单播路由算法能够在 4! ! # 线性时间找到路径长度分别为源结点和目的结点之间大约 倍和 倍海明距离的次优路径 我们提出的单播路由算 !# 9 # # 法只需要结点知道其邻结点的状态，而无需知道整个网络信息，也就是说，该算法是基于局部信息的，因而该算法具有 很强的实际意义# 关 键 词：容错性；超立方体网络；局部连通性；单播路由算法 中图分类号： 文献标识码： :;4# 算法在 （ ）时间内找到长度不超过 （，） ! 引 言 + D , D E -. $ % E + # （ ）的正确结点组成的路径 论文〔〕的单播算法与以前各种 # C 网络中的单播路由问题是网络路由中的最为基本的问 单播算法相比不论在性能上还是在容错性上都是一种飞跃# 题 单播是指找出一条从源结点 到目的结点 之间可以传 ( $ % 但是，我们指出，第一，该容错模型的容错性还远没有达到超 送信息的正确结点组成的路径的问题# 近年来有许多研究人