已阅读5页,还剩115页未读, 继续免费阅读
(计算机应用技术专业论文)规则网络容错路由算法及可靠组播的研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 随着交互式多用户应用的增加,如网络视频会议、v o d a o d 、i n t e r n e t - t v 、 交互式仿真、远程教学等网络多媒体应用,在i n t e m e t 上迫切需要高可靠的组播 路由服务以确保发送消息队列的可靠性,而现有的基于高层组播实现普遍缺少这 种可靠性保证,因此可靠组播成为当前网络技术的研究热点。基于高层的可靠组 播技术研究主要涉及到控制拓扑结构的可扩展性、容错性、组播算法、路由长度 及组播协议的可靠性、容错性、可维护性与可扩展性等问题。随着i n t e m e t 上结 点数的急剧增加及结点进出网络存在较大的随意性,只有支持大结点数的、具有 较好容错性的可靠组播协议才可能有真正的实用价值,因此协议的可扩展性与容 错性问题成为研究的焦点。 论文在介绍相关基本概念及国内外相关研究现状的基础上,首先论述了超立 方体网络的容错性,提出了多个容错性路由算法,并对算法的容错性、路径长度 及对大结点规模的支持等方面进行了深入的分析。针对超立方体容错性好与可靠 组播传输对控制拓扑的要求,提出了基于逻辑超立方体的可靠组播传输控制模 型,在分析模型相关性能的基础上,提出了新的容错可靠组播协议。本文的具体 工作为: ( 1 ) 论文在已有的强容错路由算法l 2 的基础上,提出了改进的路由算法l 3 及点对点的容错路由算法n l 2 ,采用基于全局联通性的理论分析技术,详细分析 了算法n l 2 的连通性概率等特性,理论分析与实际计算表明算法n l 2 的路径连 通性概率比算法l 3 要好,而算法l 3 又比算法l 2 好得多。提出了点对点并行路 由算法h p p a ,对算法进行了详细的描述与分析,得出了并行路径条数、路由连 通性概率与结点出错概率的公式,并分析了多种情况下的结点错误概率上界。论 文还详细分析了算法n l 2 产生的路由路径的长度期望值,提出了改进的算法 n l 2 n ,得出了路由长度的较好上界表达式。 ( 2 ) 论文针对可靠组播传输协议采用控制拓扑结构的特点,在已有的前沿研 究成果包括在l o g c u b e 结构上的h y p e r c a s t 可靠组播协议和在凡f z ,c ”搪结构上 的支持可靠组播传输的稳定性检测协议c u b e f u l l d i s t 的基础上,提出新的控制拓 扑结构- - - - c o m c u b e ,详细论述了c o m c u b e 的构造与维护过程,提出了用逻辑联 接增强结构联通性的思想,既改善l o g c u b e 结构中因部分结点联通度低造成整 第1 页 体结构容错性差的缺点,又克服了f u l l c u b e 结构中逻辑边难以构造的缺陷。分 析表明c o m c u b e 既突破了超立方体中结点数为2 ”的限制,又具有可扩展性好、 容错性高等特性。 ( 3 ) 针对c o m c u b e 容错性好的特性,提出了容错性可靠组播的思想与新的 可靠组播协议c o m c a s t 。论文详细论述了c o m c a s t 协议的信息传输与反馈过程, 分析了协议的可靠性机制,对h y p e r c a s t 可靠组播协议进行了容错性扩展。对三 个协议- - - c o m c a s t 、c u b e f u l l d i s t 及扩展的h y p e r c a s t 从结构建立、信息传输与 反馈到结构维护以及结点出错等多种状态进行了仿真模拟,采集了完好状态与出 错状态的传输时间、最大路径长度及结点负载等数据,实验结果表明,c o m c a s t 协议在结点负载保持稳定的情形下,具有比c u b e f u l l d i s t 及扩展的h y p e r c a s t 更 好的总体传输性能与短路径特性。 关键词:超立方体网络,容错性,路由算法,组通信,可靠组播协议 第2 页 a b s t r a c t a l o n gw i t ht h ei n c r e m e n t o fi n t e r a c t i v em u l t i u s e ra p p l i c a t i o n ,s u c ha sn e t w o r k v i d e oc o n f e r e n c e ,v o d a o d ,i n t e m e t t v ,i n t e r a c t i v es i m u l a t i o n , r e m o t et e a c h i n g e t c i n t e r n e tn e e d sh i 曲r e l i a b l em u l t i c a s tr o u t i n gs e r v i c et oe n s u r et h er e l i a b i l i t yo f t h et r a r s m i s s i o nq u e u e b u tm u l t i c a s ti m p l e m e n t sb a s e do nh i g hl e v e l sa r eg e n e r a l l y s h o r to f r e l i a b i l i t ya s s u r a n c e ,s os t u d i e si nr e l i a b l em u l t i c a s ti sh o ti nc u r r e n tn e t w o r k t e c h n o l o g y r e l i a b l em u l t i c a s tt e c h n o l o g yb a s e do nh j 【g hl e v e l sm a i n l yr e f e r st o s c a l a b i l i t y , f a u l tt o l e r a n c e ,m u l t i c a s ta l g o r i t h m ,p a t hl e n g t ho f t h ec o n t r o lt o p o l o g i e s a n dr e l i a b i l i t y , f a u l tt o l e r a n c e ,m a i n t a i n a b i l i t ya n ds c a l a b i l i t yo ft h em u l t i c a s t p r o t o c o l s d u et ot h er a p i d l yi n c r e m e n to ft h en o d en u m b e ri ni n t e r a c ta n dt h e r a n d o m n e s sc a u s e db yn o d e s g o i n gi na n do u tt h en e t w o r k , o n l yt h er e l i a b l e m u l t i c a s tp r o t o c o l sw h i c hs u p p o r tl a r g en o d en u m b e ra n dh a v eb e a e rf a u l tt o l e r a n c e a b i l i t yc a nb eu s e d ,s os t u d i e sf o c u so nt h es c a l a b i l i t ya n df a u l tt o l e r a n c eo ft h e m u l t i c a s t p r o t o c o l s t h i sp a p e ri n t r o d u c e ss o m eb a s i cc o n c e p t i o n sa n ds o m er e l a t e dw o r k s ;f i r s t l y , w ed i s c u s st h ef a u l tt o l e r a n c eo fh y p e r c u b en e t w o r k , p r o p o s es o m er o u t ea l g o r i t h m s w i t hf a u l tt o l e r a n c ea n da n a l y z et h ef a u l tt o l e r a n c e ,p a t hl e n g t ha n ds a r i s f yl a r g e n o d en u m b e ro ft h e s ea l g o r i t h m s t h e n ,d u et ot h eb e t t e rf a u l tt o l e r a n c ea b i l i t yo f h y p c r c u b e a n dt h ec o n l r o l t o p o l o g y r e q u i r e m e n t s o ft h er e l i a b l em u l t i c a s t 蜮s i o n 、p r o p o s ec o n t r o lm o d e lo fr e l i a b l em u l t i c a s tb a s e d o nl o g i c a l h y p e r c u b e a n dw e a l s op r o p o s ep r o t o c o lo ft h er e l i a b l ea n df a u l tt o l e r a n c em u l t i c a s t b a s e do nt h ea n a l y s i so ft h ep e r f o r m a n c e so f t h em o d e l o u rw o r k sa r ea sf o l l o w s : ( 1 ) b a s e do nl 2w h i c hi saf a u l tt o l e r a n c ea l g o r i t h mo fl o c a ls u b c u b e ,w e p r o p o s et h ei m p r o v e dr o u t ea l g o r i t h ml 3a n dt h ep 2 pr o u t ea l g o r i t h mn l 2 、i t l l f a u l tt o l e r a n c ea b i l i t y , a n dw ea n a l y z et h ec o n n e c t i v i t yp r o b a b i l i t yo fn l 2b yan e w a n a l y s i s m e t h o dw h i c hb a s e do n g l o b l ec o n n e c t i v i t y , t h et h e o r y a n a l y s i sa n d c a l c u l a t i o ns h o wt h er o u t ec o n n e c t i v i t yo fn l 2i sb e t t e rt h a nl 3 ,b u tl 3i sm o r e b e t t e rt h a nl 2 w ep r o p o s et h ep 2 pa n dp a r a l l e lr o u t ea l g o r i t h mh p p a ,d e s c r i b ea n d 第1 页 a n a l y z ei tc l e a r l y , d e d u c et h ef o r m u l a sf o rp a r a l l e lr o u t en u m b e r , r o u t ec o n n e c t i v i t y p r o b a b i l i t y , a n dn o d e s f a u l tp r o b a b i l i t y w ea n a l y z et h eu p p e rb o u n do ft h en o d e s f a u l t p r o b a b i l i t yi nm a n yc o n d i t i o n sa n dt h ee x p e c t e dv a l u eo ft h ep a t h - l e n g t h c r e a t e db yn l 2 w ep r o p o s et h ei m p r o v e da l g o r i t h mn l 2 na n dg e tt h eb e t t e ru p p e r b o u n de x p r e s s i o no f t h ep a t hl e n g t h ( 2 ) b a s e do nt h ef e a t u r et h a tr e l i a b l em u l t i c a s tp r o t o c o lu s i n gc o n t r o lt o p o l o g y a n ds o m ea d v a n c e dw o r k ss u c ha sh y p e r c a s to fl o g c u b ea n dc u b e f u l l d i s to f f u l l c u b e ,w ep r o p o s ean e wc o n t r o lt o p e l o 尉c o m c u b ea n dd i s c u s st h eb u i l d i n g a n dm a i n t a i n i n gp r o c e s so fi tc l e a r l y w ep u tf o r w a r dt h ec o n c e p t i o no fe n l a r g i n g s t r u c t u r ec o n n e c t i v i t yb yl o g i c a l e d g e s ,n o to n l yd o e si t c o r r e c tt h ed e f e c to f l o g c u b et h a ti t s f a u l tt o l e r a n c ea b i l i t yi sn o tg o o dd u et os o m en o d e s l o w e r c o n n e c t i v i t y , b u ta l s oc o n q u e r st h ed e f e c to f f u l l c u b et h a ti t sl o g i c a le d g e sa r eh a r d t ob u i l d a n a l y s i ss h o w sc o m c u b eb r e a k st h r o u g ht h ec o n s t r a i n tt h a tt h en o d e n u m b e rm u s tb e2 i nh y p e r c u b ea n ds t i l lk e e p st h eg o o df e a t u r e ss u c ha sg o o d s c a l a b i l i t y , g o o df a u l tt o l e r a n c ea b i l i t y , s h o r tr o u t ep a t he t c ( 3 ) d u et 0t h eb e r e rf a u l tt o l e r a n c ef e a t u r eo fc o m c u b e ,w ep r o p o s et h ef a u l t t o l e r a n c ea n dr e l i a b l em u l t i c a s tc o n c e p t i o n ,a n di n v o l v ei ti nt h er e l i a b l em u l t i c a s t p r o t o c o lc o m c a s t w ed i s c u s st h et r a n s m i s s i o na n df e e d b a c kp r o c e s so fc o m c a s ti n d e t a i l ,a n a l y z et h er e l i a b i l i t yo ft h ep r o t o c o l ,a n de x t e n dt h ef a u l tt o l e r a n c ea b i l i t yo f h y p e r c a s t t ot h e s et h r e ep r o t o c o l s ,c o m c a s t ,c 钍b e f h l l d i s t ,a n de x t e n d e d h y p e r c a s t ,w es i m u l a t et h e s t a t e so fs t r u c t u r ec o n s t r u c t i o n ,t r a n s m i s s i o na n d f e e d b a c k ,s t r u c t u r em a i n t e n a n c e ,a n dt h en o d e sf a u l te t c w ec o l l e c tt h ed a t ao f t r a n s m i s s i o nt i m e , t h em a x i m u mp a t hl e n g t h ,n o d el o a di np e r f e c ts t a t ea n df a u l t s t a t e t h er e s u l t ss h o w st h a tt h et o t a lt r a n s m i s s i o np e r f o r m a n c eo fi sb e t t e rt h a n c u b e f u l l d i s ta n de x t e n d e dh y p e r c a s t c o m c a s t sp a t hl e n g t hi ss h o r t e ra n dk e e p t h en o d el o a ds t a b l e k e yw o r d s :h y p e r c u b en e t w o r k s ,f a u l tt o l e r a n c e ,r o t r t i n ga l g o r i t h m s ,g r o u p c o m m u n i c a t i o n ,r e l i a b l em u l t i c a s tp r o t o c o l 第2 页 原创性声明 本人声明,所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知,除了论文中特别加以标注和致谢的地 方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含 为获得中南大学或其它单位的学位或证书而使用过的材料。与我共同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明。 作者签名:型丕堡! 喀日期:丝年上月堑日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定,即:学校有 权保留学位论文,允许论文被查阅和借阅;学校可以公布学位论文的 全部或部分内容,可以采用复印、缩印或其他手段保存学位论文;学 校可根据国家或湖南省有关部门规定送交学位论文。 名:峄燧名:敞 博士学位论文第1 章绪论 第1 章绪论 本章首先介绍了课题的研究内容及研究意义,其次介绍了论文涉及到的一 些基本概念,重点论述了与本文相关的研究方向的进展与现状,主要包括超立 方体网络的容错路由算法与概率性分析方法、超立方体结构的扩展与应用扩展、 基于高层的可靠组播传输模型以及基于c u b e 的可靠组播传输协议等,最后对 本文的组织结构进行了说明。 1 1 研究内容及意义 1 1 1 课题来源 本课题主要来源于国家自然科学基金杰出青年研究基金中计算机网络优化 算法及应用研究、国家自然科学基金中参数计算研究及应用,主要研究超立方 体网络容错路由算法及概率性分析,研究超立方体结构的针对互联网上的可靠 组播传输的扩展与应用。 1 1 2 研究内容 论文主要论述了如下四个方面的研究工作。 ( 1 ) 超立方体网络容错路由算法的设计与概率性分析 在已有超立方体网络“局部连通性”容错模型的基础上,研究了超立方体 网络基于“局部连通性”的容错路由算法与概率性分析,在基于局部联通的强 容错路由算法l 2 的基础上,提出了改进的算法l 3 ,并作了相应的理论分析与 计算。提出了超立方体网络点对点的容错路由算法n l 2 及点对点并行路由算法 h p p a ,采用了新的基于全局联通性的路由概率分析方法,深入分析了路由算法 n l 2 与算法h p p a 的路径连通性与结点错误概率的关系,得出了理论与计算结 果。 ( 2 ) 容错路由算法的路径长度分析 在点对点容错路由算法n l 2 的基础上,详细分析了路由路径长度的期望值。 第1 页 博士学位论文第1 章绪论 针对容错路径的特性,提出了算法n l 2 的改进算法n l 2 n ,进一步缩短了路径 的长度。针对超立方体网络错误结点随机分布的特性,提出了求解超立方体网 络的最长最短路径算法f l s p ,通过程序计算,得出了1 1 0 维超立方体网络的 最长最短路径,并分析了低维超立方体网络的最长最短路径产生的特定条件。 ( 3 ) 逻辑超立方体结构及基于其上的可靠组播传输控制模型与性能分析 在已有的基于互联网的可靠组播传输控制模型的基础上,针对结点不满足 2 ”的情形,扩展超立方体结构的概念,引进逻辑超立方体模型,在已有的支持 可靠组播传输控制模型的基础上,提出了个新的模型- - - c o m c u b e ,提出了新 的逻辑联接形成机制,有效地解决了结构不完全造成容错性降低、而增加逻辑 联接效率低的问题,并分析了模型的可扩展性( s e a l a b i l i t y ) 、容错性、短路径 等特性。 ( 4 ) 基于逻辑超立方体结构的可靠组播传输协议及性能分析 深入分析了可靠组播传输协议的要求及已有的前沿性的研究成果,基于新 的可靠组播传输控制模型- - c o m c u b e ,结合容错性的研究成果,提出了基于 c o m c u b e 的容错性可靠组播传输协议- - c o m c a s t ,对c o m c a s t 协议进行了详细 的描述与分析。对可靠组播传输协议一聊p r c a s t 进行了容错性扩展,论述了由 此形成的新的协议h y p e r c a s t - u p ,引进了两层存储的思想,克服了原h y p e r c a s t 协议中由于单个结点出错只能重新构造结构从而使系统效率低下的缺陷。对三 个可靠组播协议c o m c a s t 、h y p e r c a s t - 叻、c u b e f u l l d 括t 进行了分析与实验仿真, 得出多组实验结果,并进行了完整的分析。 1 1 3 课题研究意义 本课题旨在揭示超立方体结点错误分布与容错路由算法的关系,深入分析 超立方体网络的容错性,以便为超立方体网络的迸一步应用提供理论与技术依 据,同时通过深入的推理与分析,深刻揭示了其中的关系,得出了让网络制造 商有说服力、网络用户放心的计算结果,为超立方体网络的进一步研究与应用 提供了明晰的理论基础。 以理论推导与计算相结合的方式,清楚地揭示了超立方体网络容错路由的 长度,得出了一般情况下与极端状况下的路径长度值,从而为超立方体网络的 路由算法的步长研究提供强有力的佐证,包括单播、广播、组播等传输方式的 第2 页 博士学位论文第1 章绪论 研究。 以往超立方体网络主要局限应用于结构规则化、过程静态化的应用如并行 计算机体系结构、数据库仓库的历史数据存储结构等,对于像互联网类似的极 不规则又变化莫测的应用环境很少涉及,本课题却是研究超立方体结构应用于 互联网上的基于高层的可靠组播传输机制与协议,通过引进逻辑超立方体网络 的概念,解决互联网上结构不规则的问题;通过引进由于结点的不规则加入与 退出引起结构变化的机制解决互联网结构的动态变化问题,从而使超立方体结 构的诸多性能在互联网得到了发挥,为超立方体网络的应用研究开辟了新的方 向,也为互联网上基于高层的可靠组播研究提供了新的有效解决途径。 在组播传输中引进可靠性与容错性,有效地扩展了基于高层的组播协议, 使得基于很多的应用场合能够提供高可靠性与高容错性的组播路由服务。如随 着交互式多用户应用的增加,像网络视频会议、v o d a o d 、i n t e m e t 一丁v 、交互 式仿真、远程教学等网络多媒体应用,在i n t e m e t 上迫切需要高可靠的组播路由 服务以确保发送消息队列的可靠性。 1 2 基本概念介绍 1 2 1 超立方体结构简介 定义1 1 伽维超立方体网络) n 维超立方体网络以( 或简称为n - c u b e ) 是 具有下述性质的一种网络拓扑结构: ( 1 ) 它由2 ”个结点和肝2 + 1 条边构成; ( 2 ) 每一个结点可由一个不相同的仃位二进制串b l b 2 b 。进行编号: ( 3 ) 结点编号的规则为,当且仅当玩中两个结点的二进制串恰有一位不 同时,两个结点是相邻的,即这两个结点之间有一条边相连。 图1 1 是3 维超立方体网络的图例,图中有2 3 = 8 个结点和3 2 1 = 1 2 条边, 图中标识出了结点的编号( 分别从o o o 到1 1 1 ) 。 图1 2 是4 维超立方体网络的图例,图中有2 4 = 1 6 个结点和4 2 4 j = 3 2 条边, 图中标识出了结点的编号( 分别从o o o o 到1 1 1 1 ) 。很明显,4 维超立方体网络 可看作由两个3 维超立方体网络通过将对应结点用一条边连接起来构成,以这 第3 页 博士学位论文第1 章绪论 研究。 以往超立方体网络主要局限应用于结构规则化、过程静态化的应用如并行 计算机体系结构、数据库仓库的历史数据存储结构等,对于像互联网类似的极 不规则又变化莫测的应用环境很少涉及,本课题却是研究超立方体结构应用于 互联网上的基于高层的可靠组播传输机制与协议,通过引进逻辑超立方体网络 的概念,解决互联网上结构不规则的问题;通过引进由于结点的不规则加入与 退出引起结构变化的机制解决互联网结构的动态变化问题,从而使超立方体结 构的诸多性能在互联网得到了发挥,为超立方体网络的应用研究开辟了新的方 向,也为互联网上基于高层的可靠组播研究提供了新的有效解决途径。 在组播传输中引进可靠性与容错性,有效地扩展了基于高层的组播协议, 使得基于很多的应用场合能够提供高可靠性与高容错性的组播路由服务。如随 着交互式多用户应用的增加,像网络视频会议、v o d t a o d 、i n t e m e t t v 、交互 式仿真、远程教学等网络多媒体应用,在h t e r a e t 上迫切需要高可靠的组播路由 服务以确保发送消息队列的可靠性。 1 2 基本概念介绍 1 2 1 超立方体结构简介 定义1 1m 维超立方体网络) ”维超立方体网络( 或简称为n - c u b e ) 是 具有下述性质的一种网络拓扑结构: ( i ) 它由2 ”个结点和n 2 “1 条边构成; ( 2 ) 每一个结点可出一个不相同的月位二进制串6 】b 2 b 。进行编号; ( 3 ) 结点编号的规则为,当且仅当风中两个结点的二进制串恰有一位不 同时,两个结点是相邻的,即这两个结点之间有一条边相连。 图1 1 是3 维超立方体网络的图例,图中有2 3 = 8 个结点和3 2 1 - 1 2 条边, 图中标识出了结点的编号( 分别从0 0 0 到1 1 1 ) 。 图1 2 是4 维超立方体网络的图倒,图中有2 4 _ 1 6 个结点和4 2 4 1 - 3 2 条边, 图中标识出了结点的编号( 分别从0 0 0 0 到1 1 1 1 ) 。很明显,4 维超立方体网络 可看作由两个3 维超立方体网络通过将对应结点用一条边连接起来构成,以这 可看作由两个3 维超立方体网络通过将对应结点用一条边连接起来构成,以这 第3 页 博士学位论文第1 章绪论 种方式来看待4 维超立方体网络时也很容易对各个结点进行编号。 0 1 0 0 0 0 0 0 图1 - 13 维超立方体网络 1 0 1 图1 - 24 维超立方体网络 0 0 1 0 由于超立方体网络具有正规性、对称性、强容错性、直径短、可嵌入性、 并行性和网络通信能力的可扩展性等优点而深受研究者和实践者的欢迎。 当超立方体结点数增大时,结构变得复杂,尤其是在研究结构的容错性等 特性时,需要清楚了解超立方体结构的内部特性,因此引进如下的k 维子立方 体结构。 第4 页 博士学位论文第1 章绪论 定义1 2 维子立方体网络) f 1 2 0 in 维超立方体网络凰的h 位二进制串 6 1 6 2 b 。中长度为卜的二进制串6 1 6 2 “ 对应于焉中的一个具有矽个结点 和k 2 “条边的子图,称为h 维超立方体网络巩中的一个k 维子立方体网络峨 ( 或简称为k - s u b c u b e ) 。 很明显,这里定义的k 维子立方体网络凰中的结点的二进制串具有 b l 幻巩硒靠1 粕的形式,其中每一个斗要么为0 要么为l 。本文有时也将k 维子立方体凰记作风= b i b 2 6 。+ 。容易看出f 的每一个k 维子立方体与 扛c l n ) e 是同构的。t i t 维超立方体见也包含其它与k - c u b e 同构的子图。但是, 本文只考虑形式为b i b 2 巩+ 的“基本的”k 维子立方体。为简单起见,如 不特别申明,本文将“基本的”k 维子立方体简称为k 维子立方体。 图1 2 是表示一个4 维超立方体网络由两个基本的3 维子立方体构成的示 意图。当然,每一个基本的3 维子立方体还可以进一步划分为两个基本的2 维 子立方体( 图中每个3 维予立方体的一个面) ,每一个基本的2 维子立方体还可 以进一步划分为两个基本的1 维子立方体( 图中每个2 维子立方体的一条边及 两个相关的结点构成) 。 k 维子立方体结构的引入,可以更清晰地刻画低维与高维立方体之间的关 系,文献 1 2 5 的局部子立方体联通的概念及特性也是基于k 维子立方体结构的。 1 2 2 逻辑超立方体网络简介 在超立方体中,要求结点数h 一定满足九= 2 ”( 其中m 为整数) ,而事实 上很多斑用场合是不能满足这个要求的。 逻辑超立方体是最近几年发展起来并得到广泛研究与应用的一种新型拓扑 结构,其主要特点是结点数刀可以不为2 “( 肌为整数) ,然而逻辑超立方体在 结构上除仍旧保留可扩展性好、稳定性高、容错性强等性能外,还具有更好的 适用性。在网络应用中,为处理结点进出结构及出错情形提供了可用的模型, 为网络路由算法如单播、组播、广播及选播等的进一步研究与实际应用提供了 很好的拓扑结构与模型。 定义1 3 ( 具有一个结点的非完全超立方体网络) 4 0 1 具有胛个结点的非完全 超立方体网络是具有如下性质的网络拓扑结构:令珊= i1 0 2hl , ( 1 ) 所有结点都表示为二进制串a l a 2 ( m 位长) 第5 页 博士学位论文第】章绪论 ( 2 ) 两结点有边相连当且仅当其位串有且只有一位不同。 非完全超立方体网络在去掉结点数万一定满足n = r ( 其中m 为整数) 的 约束后,部分结点的联通度达不到州,因此原有的完全超立方体的特性将会受 损。如强联通性,强容错性等。为了弥补这些缺陷,引进了如下的逻辑超立方 体结构。 定义1 4 ( 具有府个结点的逻辑超立方体网络) 具有一个结点的逻辑超立方 体网络是具有如下性质的网络拓扑结构:令用= i - l o g - i , ( 1 ) 所有结点都表示为二迸制串a l a 2 a m 阳位长) ( 2 ) 两结点有物理边相连当且仅当其位串有且只有一位不同 ( 3 ) 没有肌条物理边相连的结点通过一定规则与其它结点形成逻辑边。 此处的规则,不同的文献有不同的说明,并且形成不完全相同的逻辑超立 方体结构,参见文献【7 2 】与文献【8 6 】及本文的第4 章。 如图1 3 ,在结点1 1 0 和1 0 1 之间加入一条逻辑边。 逻辑超立方体网络有效地解决了各结点的联通度问题,同时保证了超立方 体原有的强容错性与强连通性等具有明显优势的特性,被广泛应用于互联网的 路由算法及协议研究【】7 , 3 9 , 8 1 , 8 6 , 8 9 , 1 0 4 , 1 0 5 】。 t 0 0 1 0 0 0 0o o l 图1 - 3 逻辑超立方体结构示意图 1 3c u b e 结构的扩展与容错性研究 超立方体网络拓扑结构是最早提出的网络拓扑结构之一,由于其正规性、 对称性、强容错性、直径短、可嵌入性、并行性和网络通信能力的可扩展性等 第6 页 博士学位论文第1 章绪论 优点而深受研究者和实践者的欢迎。但是,人们也发现,要设计和实现高维的 超立方体网络以及对超立方体网络进行扩展( 升级) 则仍存在一些问题。因此, 一些研究者和实践者提出了多种超立方体网络的变型。下面从两个主要方向来 介绍超立方体网络的变型或扩展:其一是在保留超立方体特性的基础上,扩展 结构的功能与特性,另一个是降低超立方体结构的部分特性,使其与应用相适 应。 1 3 1 基于结构特性的扩展 1 9 8 4 年b h u y a n 和a g r a w a l 提出了g h c 网络( g e n e r a l i z e dh y p e r c u b e ) 5 1 o g h c 网络可以看作是超立方体网络的推广,它包含了r i n g ,h y p e r c u b e 和m e s h 等一大类拓扑结构,其直径与度的乘积较小,并且具有较强的容错能力。 一些研究者基于分层的方法提出了几种超立方体网络的变型。1 9 9 3 年 m e l i k s e t i a n 和c h e n 提出了c c c 网络( c u b e - c o n n e c t e dc y c l e s ) 【8 j ,1 9 9 4 年m a l l u h i 和b a y o u m i 提出了h h c 网络( h i e r a r c h i c a l h y p e r c u b e ) 【6 5 j ,1 9 9 4 年d a y 和t r i p a t h i 提出了h c n 网络( h i e r a r c h i c a lc u b i cn e t w o r k ) 【4 9 】,1 9 9 5 年c h e n 和f a n g 提出 了f h n 网络( f o l d e dh y p e r c u b en e t w o r k ) 【伸】。这些基于分层方法的目的在于 降低超立方体网络的结点度。同c c c 网络相比,h h c 网络的直径和平均网络 结点距离比较小,但是它的网络结点度等于l o g l o g n ,仍然与网络的结点数 有关。c c c 网络的结点度等于常数3 ,其固定不变的结点度使得它在超大规模 集成电路设计和实现方面非常容易且非常高效。h c n 网络是以超立方体为基本 单元,而f h n 网络以环绕超立方体为基本单元。c c c 网络、h h c 网络以及h c n 网络都是两层的分层互联网络,在网络规模需要扩展时必须破坏原有的网络结 构以便加入新的结点,因此网络规模的扩展仍然比较困难。2 0 0 1 年王洪玉和董 秀国提出了一种应用于m p p 系统的结点度等于常数的递归多级分层互联网络, 称为全互联立方体网络( f u l l y c o n n e c t e dc u b i cn e t w o r k ,f c c n ) 【1 2 6 】。f c c n 具有可扩展性好、延伸性能好等优点。f c c n 网络的结点度与网络的规模无关, 为一常数4 ,且网络的直径和平均结点距离都与结点数的立方根成正比。f c c n 网络具有很高的互联效率,而且f c c n 网络连接的并行系统在扩展时无需破坏 原有的任何物理连接,且没有增加结点度,使得f c c n 网络的扩展开销很小, 适合于扩展到任意多的结点数,可以在m p p 系统中得到应用。 第7 页 博士学位论文第1 章绪论 1 9 9 5 年c u l l 和l a r s o n 提出了m o b i u s 立方体网络( m o b i u sc u b e s ) 【。 m o b i u s 立方体网络是超立方体网络的变型,它具有一些比超立方体网络更优越 的特性,如一维m o b i u s 立方体网络的直径大约是一维超立方体网络的一半,其 期望距离大约是h 维超立方体网络的三分之二等。1 9 9 8 年樊建席和逯昭义证明 了m o b i u s 立方体网络的另一个比超立方体网络优越的性质【9 1 1 ,即任一长度为 f ( 4 尥的圈能嵌入到n 维m o b i u s 立方体网络中( 以2 ) ,并给出了构造过程, 从而也证明了m o b i u s 立方体网络对环网络的模拟能力比超立方体网络的高( 因 超立方体网络不含奇长圈) 。1 9 9 9 年樊建席和管殿柱将具有2 ”个结点的m o b i u s 立方体网络的拓扑结构加以改变,得到了包含任意多个结点的互联网络一超级 m o b i u s 立方体网络【9 0 】,并证明了它保持了m o b i u s 立方体网络的高连通度、对 数级的直径和结点度数等优良性质,并且当结点个数n = 2 ”+ 2 + 1 时,0 型超级 m o b i u s 立方体网络是一个+ 1 ) 正则图;更进一步,由于它包含任意个结点, 所以其升级只需要增加任意个结点,从而克服了m o b i u s 立方体网络的升级必须 成倍增加结点个数的缺点。1 9 9 9 年樊建席还基于交叉立方体互连网络提出了超 级交叉立方体则互连网络的概念,并研究了其拓扑性质嗍和圈嵌入算法 9 3 。 1 9 9 6 年0 k r i n g 匪l d a s 基于p e t e r s e n 图和超立方体网络提出了一种称为 f o l d e dp e t e r s e nc u b en e t w o r k s 丌】的超立方体网络的变型。这种拓扑结构具有正 规性、结点一和边对称性、最优连通性( 因而也具有最大容错性) 、对数级的直 径、模块性,以及允许简单的自路由( s e l f - r o u t i n g ) 和广播算法等优点。 s g i c r a y 公司推出的o r i g i n2 0 0 0 系统采用了称为胖超立方体( f a t h y p e r c u b e ) 【3 8 】的网络拓扑结构,其优点是保持了超立方体网络的线性对剖宽度 而且避免了结点度的增加。这里的“对剖宽度”是指将网络对分成两半时所必 须移去的最少边数。 1 3 2 基于应用特性的扩展 超立方体结构最早的提出主要是解决并行计算系统的体系结构,随着对超 立方体结构研究的深入及应用的需求,基于超立方体的广播、组播、单播研究 进入到互联网络,然而,超立方体结构的一个显著的特性是结点数理= 吵,而 i n t e m e t 上结点的加入与退出不受限制,随时可能失效,因此需要一个能即时调 整、快速适应、性能保持稳定的结构,还要突破结点数n = 2 ”的限制。1 9 9 8 年, 第8 页 博士学位论文第1 章绪论 v i r g i n i a 大学的j l i e b e h e r r 教授等在研究可靠组播时,为了克服反馈风暴( a c k i m p l o s i o n ) 及树结构扩展性差的缺陷,提出了非完全超立方体的组播拓扑结构 1 4 0 l ,我们称之为l o g c u b e ,即允许结构的结点数h 2 “、结点的连接数也可以 不一样,如本文定义1 3 所定义的结构。文献 4 0 】的研究表明,l o g c u b e 具有很 好的结构可扩展性、支持大量结点的可靠组播应用。但由于l o g c u b e 中部分结 点的联接数较少,大大降低了整个结构的容错性。2 0 0 2 年,r f r i e d m a n 等人在 研究稳定性检测协议时,提出了新的称为逻辑超立方体的结构m 】,我们称之为 f u l l c u b e 结构,即一方面允许可靠结构的结点数竹吵,另一方面在结点联接 时考虑物理联接与逻辑联接,即按照如本文定义1 4 的定义建立结点间的物理 联接,逻辑联接采用专门的建立算法补充因结点缺失所造成的物理联接减少。 f u l l c u b e 在保持结构可扩展性好的基础上,增强了整体结构的容错性能,但 f u l l c u b e 结构建立逻辑联接所采用的算法较复杂,所花的代价较大。我们在2 0 0 3 年提出了一种新的结构- - c o m c a s t ,详细的将在第4 章说明。 1 4 基于c u b e 的容错性及容错路由算法的研究与进展 随着计算机网络规模的不断扩大,网络中不可避免地将出现错误结点,因 此,人们必须研究计算机网络的容错问题,即保证网络在有结点出错的情况下 仍能正常工作。这方面研究得特别广泛的是网络容错模型与容错路由算法,其 中容错模型研究的是如何刻画超立方体网络中出错的规律及整个网络的容错性 分析。网络容错路由问题是在含有错
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高三化学工业合成氨反应条件优化教学设计
- 高三思想政治选择性必修一第六课走进经济全球化教学设计
- 高中德育《冬季防火 生命至上》主题班会教学设计
- 小学五年级心理健康教育“换个想法心情好”教学设计
- 初中英语七年级下册Unit 1并列连词语法教学设计与分层习题
- 第二单元-主题活动三《我是环保宣传员》教学设计-2026-2027学年内蒙古版小学综合实践活动四年级上册
- 船舶动力装置高效运行指导书
- 物流仓储货物清点标准指南
- 关于调整西区运输线路布局的通知4篇范本
- 儿科医生考核指标表
- 中国国际展览中心集团笔试考点2026
- 经营主体信用监管标准体系研究报告2026蓝皮书
- 发展对象入党答辩常见问题与参考答案
- 2026油田化学品行业市场发展分析及前景趋势与勘探开发投资研究
- 外墙真石漆施工安全
- 2026年学校资助管理员招聘笔试试题及答案
- 沅江亘胜生物年产16万吨芦苇(秸秆)粗纤维建设项目环境影响报告表
- 小学语文教师晋升高级职称答辩试题汇编及答案详解
- 2026年4月自考00227公司法试题及答案含评分参考
- 水果部门内部规章制度
- 人教版(新版)三年级下册英语全册教案(完整版)教学设计
评论
0/150
提交评论