款事其本与点用
通信技术
具有不连通子立方体的超立方体中多播路由
张涌逸
(太原师范学院计算机系山西太原(03(012)
摘要：基于扩展的局部k一维予立方体连通的超立方体网络Hn，提出了超立方体网络Hn中新的多精容错露路由算法.算法分析表明，基于扩展局部k一维子立方体连通的多播路由算法比基于局部k-子直方连通的多格路由算法提高了超立方体网络的容错性和通用性
关键词：客错路由超立方休网络扩展的局部k一维子立方依的连通性多疆算法
文章编号：1007-9416(2011)10-0025-02
中图分类号：TP302.8
文献标识码：A
Multicast Routing in Hypercube Networks
withDisconnected Sub-Cube
ZHANG Yong-yi
(Departnment of Computer,Taiyuan Normal University, Taiyuan 030012,China)
Abstract:Based on the concept of the extended locally ksubscubeconnected hypercube networks, a faulttolerant broadcast routing algorithms was proposed ins a hypercube ivetwork. Acvording to the result of the analysis,compared with the algorithns bosed on the loxcally ksuhcubeconnected hypercuixe nerworks,the algorithm bused on the extended lkocally ksubcubeconnected hypercube networks improves fault tolerant capucity and generality
Key words:fiuittolerant routing hypercube network extended ocally ksubcuhe=connected hypercuhe networks; hroadkast algorithm.
1、引言
超立方体是最常用的拓扑结构，人们对它进行广大量的研究随着互联网规模的急剧增长，许多应用也不断普及，如视频会议、视频点插等，这些交互式规额频、音频等应用需要将数据可靠地传输给数量众多的用户，固此迫切需要高容错的多播路由服务。超立方体网络多播路由服务成为了重要得研究课题4。下面我们给出基于扩展局部k一维了立方体连通的超立方体网络多插容错路由。
2、基于扩展局部k一维子立方体连通的超立方体网络中多播容错路由算法
定义(扩展的局部k一维了立方体的")：如果n一维超立方体网络Hn中每-·个k一维子立方体(定义见")中由正确结点构成的每个连通子图中存在正确结点与邻接的K一维了立方体中正确结点相邻接，且至少有一个k一维了之方体正确结点是连通的，则称Hn是扩展局部k一维子立方体连通的。
显然，扩展的局部k一维子立文方体连通的n一维超之方体网络 H中的正确结点是连通的。
多播容错路由算法要求在其有错误结点的n一维超立方网络中由源结点经由：-系列正确结点和无故障链路到达日的结点。设超立方体网络是扩展局部k一维子文方体连通的。
为叙述方便我们先人2个算法。
构造正确结点结点U到准确结点连通的k一维了立方体 b,b"-b，**b...b."b,某：-个正确结点w,的器错路由算法。
第法1：
(1)u<--a,,"a.其中a,是进制位：
(2)在所有正确结点连通的k一维了立方体中，找-个k一维了立.方体b,b,-b,*+b."，b."-b,，使得此k-—维子立.方体到U所在的k一维了立方的海明距离与此k一维子立方体到V所在的k一维子立方的海明距离之和是正确结点连通的k一维子立方体到U所在
的k一维子立方的海明距离与到V所在的k一维子立方的海明距离之和中最小的一个，
(3)W<-w,w,"w_,这里对所有的i=1,2,"",n有w,=a,;
(4)初始化路径P<--[U];(5)FOR i=1 TO n-k DO:
至此，已经构造了·条从Ua,a,"a,到Ww,w,w_的由正确结点构成的路径：
IF i≤t THEN
1)导找-对正确的邻接点：W"=w,W,"W-，w,w,".“q"...M"..+*M**m".xm W,X.X+ W.W.**W.,
".**—"（中把路径从W扩展到W'，然后从W到W
3)W<- W ELSE
4)予找·对正确的邻接点：Ww,w,w,x."x.... kw.ww和w,w W....W .+**-W.+., h,...W,...W.
5)扩展路径P；k—维了.文.方体w,W,w,*w....w.w2"W
中把路径从W扩展到W，然后从W"到W； 6)W<-W *
在含有证确结点U的k一维立方体的连通图中，构造以正确结点U为根结点，包含此连通了图中的目的结点的树。同时使得此树尽量只包含的结点。
第法2：
(1)加人可作为根树的孩了结点的！的结点；如没有这样的！的结点，任选一日的结点，取此口的结点到根结点的路径最短并加人根子树：
(2)加人可作为已得子树的结点的孩子结点的目的结点如没
25