（计算机应用技术专业论文）基于超立方体的容错性组播及路由仿真系统的研究.pdf

摘要 随着互联网规模和应用的飞速发展，视频会议等应用越来越广 泛，传统的单播通信已经无法满足这些应用的需求，基于互联网的组 播研究正方兴未艾。人们提出了控制拓扑的概念，支持大节点数的应 用。因此，研究性能稳定的组播控制拓扑及其协议也就成为了当今世 界上最前沿也最热门的课题之一，而超立方体又是其中的代表。 因为以往的控制拓扑具有较大的局限性，近年来超立方体结构被 提出并得到了广泛的研究。完全超立方体性能突出，但对节点数的严 格限制使其实用性有限。为此，人们提出了l o g c u b e 、f u l l c u b e 等逻 辑超立方体结构，它们消除了h ) ，p e r c u b e 的局限性，提高了结构的性 能，但仍存在较大的缺陷。针对这些不足，我们分析了一种新的结构 一组合超立方体结构：c o m c u b e ，并从理论上说明了c o m c u b e 在继 承发扬以往结构的优越性的同时，较好地克服了逻辑超立方体的一些 缺陷。 根据研究需要，我们深入研究了公认的优秀网络仿真软件n s 2 。 针对n s 2 以及超立方体结构的特点，开发了基于n s 2 的超立方体路 由仿真系统。该系统能够根据实验对象和实验要求，自动构建t c l 脚 本，运行模拟实验，分析统计实验结果以及显示实验的动态过程。该 系统具有良好的通用性、易用性和扩充性，能够极大提高超立方体模 拟实验的科学性和工作效率，使n s 2 能够被更广泛地应用于研究工 作中。 目前在实验中模拟组播与超立方体结构的结合，研究其性能，具 有前沿性的理论与实际意义。我们利用该仿真系统，对基于逻辑超立 方体的组播通信进行了模拟实验，研究不同节点出错率及节点出错位 置下，逻辑超立方体结构在组播通信中的性能。根据对统计结果曲线 图的分析研究，我们得到结论：逻辑超立方体在组播应用中，确实具 有良好的性能。该课题的研究展现了逻辑超立方体和c o m c u b e 的性 能优势，并成功设计开发了超立方体路由仿真系统：为继续深入研究 超立方体结构，使其更加完善和具有推广实用价值提供了有力的工具 并打下了良好的基础。 关键词：组播，超立方体，c o m c u b e ，n s 2 ，路由仿真 a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fm es i z eo fm t e m e ta n d a p p l i c a t i o n s ， m o r ea n dm o r e a p p l i c a t i o n ss u c h a sv i d e oc o n f e r e n c ea r ew i d e l y a p p l i e d u n i c a s ti s h a r d l y t o s u p p o r t t h e s e a p p l i c a t i o n s ，s o t l er e s e a r c ho n m u l t i c a l s ti si nt h ea s c e n d a 【n t p e o p l e p r o p o s e dm ec o n t r o lt o p 0 1 0 9 yt o s u p p o n m a s sn o d e s t h e r e f o r e ，t h ef e s e a r c ho nm u l t i c a s tc o n t r o l t o p o l o g y o fs t a b l ep e r f o m a n c eb e c o m eo n eo ft h em o s tp o p u l a ra 1 1 d 丘o me d g e p r o j e c t s ，m o r e o v e rh y p e r c u b e i sa d e l e g a t e b e c a u s eo ft 1 1 el i m i 伽o nm ef o 咖e r c o n 乜d l t o p o l o g i e su s u a l l yh a v e ， p e o p l ep r o p o s e dh y p e r c u b ea n d1 1 e s e a r c h 证gw i d e l yo ni t c o m p l e t e h y p e r a b e h a sb e t t e r p e r f o n i l a n c e b u ti t s p r a c t i c a b i l i t y i sl i m i t e d b e c a u s ei th a ss t r i c tc o n d i t i o no ft 1 1 en u m b 盯o fn o d e s s o s c h o l a r s p r o p o s e dl o g c u b e a n df u l l c u b e 、v h j c hi sb a s e do n l o g i c a l 叠，p e r c u b e t 1 1 e y e l i m i n a t e dt 1 1 e c o m p l e t eh y p e r c u b e s l i m i ta n d i m p r o v e d t 1 1 e p e r f b m a n c e o f s t r u c t u r e ，、池i l e 血e y s t i l lh a v e b i g g i s h l i m i t a t i o n s a i m i n ga tt h e s es h o n a g e s ，w ea n a l y z e dan e ws t r u c t u r e - c o m b i l l a t i o n a l h y p e r c u b e ，c o m c u b e a n d 、v es h o w e di nm e o r ym a ti to v e r c o m e ds o m e o fm ed e f i c i e n c i e so f l o g c u b es t m c t u r e sw h i l ei ti n l l e r i tt h ea d v a n t a g e s o f t l e m f o rt h er c q u i r e m e n t so fo u rr e s e a r c h ，w es t u d i e dn s 2w m c hi st h e a c k n o w l e d g e d e x c e l l e mo n eo ft l l en e t w o r ks i m u l a t i o ns o r w a r e a c c o r d i n g t ot 1 1 ec h a r a c t e r i s t i c so fn s 2a 1 1 dh ) ，p e 疋u b e ，、v ed e v e l o p e da h y p e 疋u b es i m u l a t i o ns y s t e mb a s e do nn s 2 t h i ss y s t e mc a l lc o n s t m c t t 1 1 et c ls c r i p ta u t o 】【t i c a l l y m nt h es i m u l a t i o n ，a 1 1 a l y z et h er e s u l t sa n d s h o wt h ed y n 锄i co f e x p e r i m e n t s i t i ss c a l a b l ea 1 1 dc a nb eu s e d g e n e r a l l y a 1 1 de a s i l y i tw i l lm a k en s 2b ew i d e l yu s e di nr e s e a r c h e s c u r r e n t l y ，i th a s f 而n te d g e m e a i l i n g i n m e o va n dp r a c t i c e t h a t c o m b i n et 1 1 em u l t i c a s ta n d h y p e r c u b e i ns i m u l a t i o na n d s t u d y t h e p e r f o 肿a n c e w i t h t h es i m u l a t i o n s y s t e m ，w ee x p e r i m e m e dm u i t i c a s t w i m l o g i c a lh y p e r c u b e i nm es c e n 撕o so fd i 行e r e n tr a t ea n d p o s i t i o n so f t h ef a u i t n o d e s a n a l y z e d 也e 鲈a p h so f 协es t a t i s t i c s ，w e 出a wm e c o n c l u s i o nm a tl o g i c a lh ) r p e r c u b eh a sg o o dp e r f o 加a 1 1 c ei 1 1m u l t i c a s t t h i s p r o j e c t d e m o n s t r a t e dm ea d v a n t a g e so fl o g i c a i h y p e r c u b e a 工l d c o m c u b e ，a n dd e s i g n e da n dr e a l i z e dt h eh y p e r c u b es i m u l a t i o ns y s t e m h s u c c e s s m l i y i tp r o v i d eav a l u a b l et o o i 锄db a s e m e n tt op e r f e c tl o g i c a i h y p e 疋u b ea j l dc o m c u b e ，a n dm a k em e m b em o r ep r a c t i c a li n 如恤e r r e s e a r c h k e yw o r d s ： m u l t i c a 瓯h y p e 疋u b e ，c o m c u b e ，n s 2 ，r o u t i n g s i m u l a 石o n i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在在论文中作了明确的说明。 作者签名：辨日期：巡年j 月皿日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根 据国家或湖南省有关部门规定送交学位论文。 作者签名：牲导师签名盥曰期：巡年乒月妇 硕士学位论文第一章绪论 第一章绪论 1 1可靠组播协议的控制拓扑的研究意义与现状 1 1 1 可靠组播协议控制拓扑的研究意义 当代社会已经进入信息时代，网络技术在飞速发展。由于视频会议、推送技 术、大规模协作计算、为用户群进行软件升级、用于培训和企业报告的共享白板 式的多媒体应用、网络代理、镜像和高速缓存站点等应用，都依赖于从一个主机 向多个主机或者从多个主机向多个主机发送同一信息的能力，而h t e m e t 上分发 的数目可能达数十万台，大大超出了单播通信路由的能力。单播通信路由在大节 点数的应用中，无论是节点负载，还是在网络带宽利用等方面都无法胜任。因此， 研究基于互联网上的组播不可避免【l j ，而且迫切需要高可靠的组播路由服务以确 保发送消息队列的可靠性，而现有的基于高层的口组播实现普遍缺少这种可靠 性保证。 在基本的组播服务中，一个用户加入一个组播组只简单表明他对传输组内的 数据感兴趣，每个发送给组内的数据包分发给组内的所有成员，成员是否都收到， 传输过程是否有错等控制信息都不是基本组播服务中的内容，而作为高级组播服 务则必须提供这些控制信息，确保组内的每个成员都正确接收信息。可靠扩展性 ( r e l i a b l e s c a l a b i l 畸) 研究是研究如何实现数据信息与控制信息在大规模节点中 的可靠传输，其中控制信息的可靠扩展性实现是坤组播实用化的关键。然而多 点组播的可靠性( r e l i a b i l i t y ) 与扩展性( s c a l a b i l i t ) r ) 间存在矛盾：一方面组播是 基于u d p 的不可靠传输，需要对信息尤其是控制信息的传输给予可靠性保证； 其基本思路是通过接收端( r e c e i v e r ) 向发送端( s e n d e r ) 发送“a c k ”( 接收正 确) 或“n a c k ”( 接收错误) 实现反馈重发：另一方面如果组播要获得高的效 率，就要实现节点有效扩展：大规模节点的反馈重发势必导致发送端“a c k ” “n a c k ”过载：而“a c k n a c k ”过载将使得发送端可靠性重发能力降低 和所在网络产生拥塞( a c ki i i l p l o s i o n ) ，网络拥塞将进一步产生“a c k ”“n a c k ” 过载，最终将使得可靠性控制机制崩溃【l ，2 ，”。研究者们对此提出了众多解决方 案，主要分为：基于层次结构的方案，如k e n n o d e 【4 】：基于反馈减少的方案， 如f l o y d 【5 】；基于轮询的方案，如w h e t t e n l “。这些方案部分解决了组播可靠性 与可扩展性间的矛盾，不过针对的均为非实时数据传输，不能完全满足i p 多点 组播数据传输的实时性要求。 硕十学位论文第一章绪论 随着i n t e m e t 上节点数的急剧增加，支持大节点数的可靠组播坍议才可能有 真正的实用价值。种新的方法随之产生，即可靠组播传输采用控制拓扑方式 ( c o n 舡o lt 0 p o i o g y ) 【7 ，8 9 - 1 叭，信息( 数据与控制) 沿着一个设定的拓扑结构传 送不必直接传送给各个节点，而反馈信息也沿着控制拓扑进行传递，中间节点 将对子结构内部的控制信息进行处理，大大减少发送点接收的反馈信息。因此在 研究组播时，由于互联网结构的任意性及节点数目的急速膨胀，将互联网结构映 射成为一个性能稳定的结构也就成为了当今世界上最前沿也最热门的课题之一。 早期提出的控制拓扑结构有环结构、树结构等，但随着组播成员数量的增加以及 成员的自由进出，环结构与树结构暴露了很多的缺陷，性能随着节点的增加呈快 速的下降趋势【2 ”，因此基于环结构与树结构的反馈信息控制远远不能满足 i n t e m e t 上支持大量节点的高可靠组播服务。为此，人们又提出了新的控制拓扑 结构如超立方体和类似于超立方体的非完全超立方体结构，克服了环结构与树结 构的一些缺陷，在结构可扩展性、传输路径长度、结构可维护性、容错性等方面 呈现了较好的性能，因此是值得研究一个方向。 此外，超立方体的算法及其分析的研究也具有重要的现实意义，如近年来美 国、日本、欧洲各国政府都高度重视高性能计算机领域的研究和发展【1 l 1 2 1 。美国 的高性能并行计算机系统的研究计划有“高性能计算和通信计划( h p c c p r o g m m ) ”、“加速战略计算创新计划( a s c ip r o g r a m ) ”和“千万亿次计算机计 划( p e 诅n o p sp r o j e c t ) ”，日本的“真实世界计算计划( r w cp m g r a m ) ”，欧洲的 “万亿次计算机计划( t e 姐n o p sp r o g 舳) ”，其主要目标都是研制万亿次量级的 高性能并行计算机系统，而超立方体是研究大型并行计算机系统的重要拓扑结构 之一，因此，其容错问题的研究在这一领域中也是非常必要的，国内对此也有一 些研究i ”11 6 1 。因此结合组播与超立方体结构( h y p e r c a s t ) 、研究其中的容错 问题具有重要的理论意义与现实意义。 1 1 2 国内外研究现状 1 9 8 8 年d e e r b l g 提出了将组播的功能机制增加到数据网i p 层的组播实现体 系结构，这种体系结构称为i p 组播( 口m u l d c a s t ) 。i e t fi t f c l l l 2 对i p 组播的 业务提供的方式和形式进行了描述和定义，被看成是i p 组播的标准业务模型的 定义【1 7 l 。 标准i p 组播业务模型定义了主机和路由器i p 层应有的功能机制和上层所看 到的组播业务的形式。主机组( h o s t g m u p ) 是i p 组播概念的核心，多个主机组 成主机组( 组播组) ，用一个i p 组播地址标识，以组地址为目的地址的组播数据 以i p 数据报的b e s t - e 肋n 方式转发到主机组的各个主机。组播路由器承担组播数 2 硕士学位论文第一章绪论 据的寻路和转发控制功能，这些路由器及链路在网络中形成了一个控制组播数据 传送的逻辑结构，称为组播转发结构( d e l i v e r ys m l c t i l r e ) ，这种结构般是树形 的结构，称为转发树在转发树上的组播路由器接收、复制、转发组播数据。 历经近2 0 年的研究和发展，i p 组播已经形成了较为完整的组播协议体系， 包括组播主机和网络的交互协议、组播路由协议、组播的地址管理协议等【l ”。 组播路由协议是i p 组播协议体系中最核心的功能。i p 组播路由协议的发展 分成域内( i n t r a d o m a i n ) 和域间( i n t e 卜d o m a m ) 两个阶段：最初的i p 组播路由 协议将网络看成没有层次结构的平面网络，组播路由算法采用广播方式交互协议 消息，因而只能应用在i p 网络的路由自治域内，称为域内路由协议：域问路由 协议的出现是为了解决在大型的、分层的i p 网络中组播路由问题，大型口网络 采用自治域结构形式组织网络，域问路由协议解决了分层结构网络的组播路由问 题。 1 9 9 2 年i p 组播实验网m b o n e 建立，从1 9 9 2 1 9 9 7 年，i p 组播的协议 标准和部署方法在m b o n e 中进行研究实验。1 9 9 7 年以后，分层结构网络域间组 播路由的标准化成为i p 组播研究的主要领域，域问路由协议体系的部署实验开 始在i n t 唧e t2 的两个骨干网( v b n s ，a b i l e n e ) 中进行，从1 9 9 9 年中开始采用 m b g p ，m s d p 和p i m s m 协议体系实现域间组播路由【1 8 ，1 9 】。 按照组播协议的分类在第三层的组播协议主要有d v m r p 、p i m 和i g m p 等， i g m p ( i m e m e t g r o u pm a n a g e m e mp m t o c 0 1 ) 即因特网群组管理协议，它通过一 个组播树来传送与反馈信息，组播树的中间节点没有信息处理能力，通过各节点 随机延时来防止反馈拥塞。而在第二层的组播协议主要用c g m p ( c i s c og r o u p m a l l a g e m e n tp r o t o c 0 1 ) 和i g m p 监听。第三层的组播协议主要用于组播信息的转 发，第二层组播协议主要用于抑制局域网上多余的组播信息，在路由器以及多层 交换机上一般实现第三层的组播协议，而在不具备多层交换的交换机上一般只能 实现第二层组播协议。 在广域网环境中还存在许多可靠组播协议，包括可靠组播协议孙o ( r e l i a b l e m u l t i c a s tp r o t o c 0 1 ) 、可扩展可靠组播s r m ( s c a l a b l er e l i a b l em u l t i c a s t ) 、基于日 志的可靠组播l b l t m ( l o g b a s e d r e i i a b l em u l t i c a s t ) 和可靠组播传输协议i t m t p ( r e l i 曲l em u l t i c a s tt r a n s p o r tp m t o c 0 1 ) 【剐。 这些协议的拓扑结构以树拓扑( 1 k et 0 p o l o g y ) 【2 0 ，2 2 2 2 3 1 为主，但也有可靠组 播采用其它结构如如星形拓扑( s t a r l 0 p o l o g y ) 、环拓扑( 砌n gt o p o 】o g y ) 2 5 1 、 m e s h 拓扑( m e s h t 0 p o l o g y ) 、逻辑超立方体拓扑( l o g c u b et o p o l o g y ) 等。其中， 树拓扑中控制信息沿着根聋成树( m o t e ds p a n n i i l gt r e e ) 传输，每个组播成员 ( m u l t i c a s tm 锄b e r ) 都有自己的生成树，树拓扑的缺点是要构造与维护树结构， 硕十学位论文第一章绪论 因为节点状态是动态变化的( 可能坏了、退出、随时加入等) ，因此树结构的维 护也将是动态的。在动态变化过程中，树的平衡性容易被打破，高度变化太快， 不易控制【l l ：环拓扑中主要是令牌持有者( t o k e nh o l d ) 拥有控制信息，系统的传 输速度与之性能直接相关，环拓扑的缺点是容易产生瓶颈( b 0 札l e n e c k ) l l 】。 h y p e r c a s t 是于19 9 8 年由美国r g i l l i a 大学计算机科学系的j j 曜l i e b e h e r r ( j q 鸳 箜：y 适g 垫i ：血) 提出来的，美国国家基金会( n s f ) 资助的项目。h y p e r c a s t 是h y p e 疋u b e 与m u i t i c a s t 两个单词的组合，是在研究基于互联网上的m u l t i c a s t 时提出的一种协议机制( p r o t o c o lm e c h a n j s m ) 。j l i e b e h e r r 与b s s e 出i 发表了多篇 论文【l 2 62 7 1 ，其中在as c a l a b i ec o n t r o lt o p 0 1 0 9 yf o rm u l t i c a s tc o m m 叽i c 舐o n 【1 1 中详 细研究了基于互联网的r n u l t i c a s t 协议的特点，引进超立方体( h y p e 庀u b e ) 控制 拓扑，将组播组( m u l t i c a s tg r o u p ) 作为逻辑的订维超立方体结构。基本形成思想 是将生成树嵌入到超立方体结构中。j 工i e b e h e r r 与b s s e t l l i 提出了生成树结构与 超立方体结构转换的方法，讨论非完全超立方体结构的问题及如何将树嵌入到超 立方体结构中保留父子关系的问题，他们还分析了用超立方体结构作为组播协议 控制拓扑的可扩展性( s c a l a b i l i t y ) 并与k 阶共享树( 尽a r ys h a r e d t r e e ) 作了比较。 研究表明超立方体网络在节点数增大时，其可扩展性最稳定。这正是基于互联网 的网络结构所需要的，因为互联网中的节点呈指数级增长，动态变化也快，如果 结构对节点变化太敏感，则可能导致不能用。 但j “e b e h e r r 与b s s e “没有研究逻辑的超立方体结构中的控制信息传输时 的容错模型，而事实上，由于逻辑的超立方体结构是动态变化的( 节点坏、退出、 加入等) ，而且也是不完全的结构。因此，容错性问题的研究相当必要( 坏了的 节点与结构不完全的点可以当成错点) 。r f r i e d n l 蛆等人对逻辑超立方体进行改 进，提出了f u l l c u b e 结构和c u b e f l d l d i s t 协议，针对缺失节点增加逻辑连接，弥 补了连通度的损失，提高了结构的容错性。但是f l l l l c u b e 需要对每一个缺失节点 进行计算，增加逻辑连接，且增加的逻辑连接利用率低，导致结构的形成复杂； r f r i e d m a l l 也未对结构的动态维护进行详细讨论。以上这些不足都是有必要进行 仔细研究的。 所以，目前研究的重点之一就是对它们的容错性等性能进行更深入的研究， 通过理论分析并结合模拟测试得到的数据，论证它们性能的优点，了解它们的机 制、算法等方面的不足。进一步改进以及提出更好的结构和协议，并对新的结构 和协议进行理论及仿真研究。以期使基于超立方体的组播协议及控制拓扑更加完 善，更加具有推广应用价值眺29 1 。 4 硕士学位论文第一章绪论 1 2 本文的主要研究内容与贡献 1 。2 1 本文的主要研究内容 虽然i p 组播的概念很早就被提出，但是直到现在它的能力才被充分认识。 目前组播技术应用的增长十分快速，而且这种趋势正在加快，是网络研究中一个 比较活跃的研究领域。但是口组播仍然是一项新出现的技术，虽然组播具有很 大的优点和长处，但是和所有新技术一样有其自身的局限性和一些问题，因此在 组播领域还需要进行大量的工作。目前研究主要集中在以下三个方面： ( 1 ) 异质性( h e t e m g e n e 时) 研究，研究不同性能终端和不同网络条件下的 组播接收与发送p 叫； ( 2 ) 可扩展性( s c a l a b i i i t y ) 研究，研究组播终端节点组规模的有效扩展川： ( 3 ) 可靠性( r e l i a b i l i t y ) 研究，研究组播不可靠传输下的数据可靠性传输 保证川。 近年来许多组播协议及控制拓扑被提出来，特别是基于超立方体的控制拓 扑。与其它许多性能较优越的协议及控制拓扑相比，基于超立方体的控制拓扑有 容错性、可扩展性和稳定性等突出的优势，但它们也不可避免地会存在一些自身 的不足。基于发掘超立方体结构良好性能潜力，完善逻辑超立方体结构，实现其 不断向实用化发展的考虑，本文主要研究内容有以下几个方面： 第一、基于可靠组播的逻辑超立方体结构及其传输模型与协议。随着超立方 体的提出，人们对它的研究越来越深入，不断提出更新的超立方体，目的在于发 掘超立方体的性能潜力，消除已往结构的缺陷。首先，详细分析已有的基于逻辑 超立方体的拓扑结构，研究它们的机制和算法。针对它们的缺陷进行优化和改进， 提出更好的控制拓扑。新的控制拓扑应该继承和提高已有逻辑超立方体结构的优 势，同时减少其缺点，推进逻辑超立方体结构的性能。然后，对包括新的控制拓 扑在内的逻辑超立方体结构进行理论分析，对比说明新的结构确实保有甚至提高 了已有结构的优点，并改进了它们固有的一些缺陷。 第二、基于n s 2 的超立方体路由仿真系统的设计与实现。为了更深入地研 究超立方体结构不仅要有理论上的结果，还要通过对该结构的模拟实现，掌握 大量第一手实验数据，验证超立方体结构的实际性能。在充分研究了多个网络仿 真软件的基础上，重点对n s 2 进行了研究，根据n s 2 以及超立方体结构的特点， 设计并实现了基于n s 2 的超立方体路由仿真系统。使n s 2 在对超立方体的可靠 组播研究中具有了良好的通用性与易用性。 第三、仿真结果的分析与研究。在仿真系统中，针对基于逻辑超立方体的组 播通信迸行模拟实验，统计仿真结果并以曲线图表示。研究实验指标的结果特性 硕士学位论文第一章绪论 并结合理论分析，最后对逻辑超立方体的组播通信性能做出总结。 1 2 2 本文的主要贡献 根据上述研究内容，本文的主要贡献有以下几个方面： 第一、在大量查阅国内外有关可靠组播通信、超立方体结构等方面的文献后， 深入、详细地分析了肝a r ys h a r e d 雠e 、h y p e 疋u b e 、l o g c u b e 和f m l c u b e 结构的 机制和算法，研究它们的优点和机制上的缺陷带来的不足。针对它们的不足，研 究了一种新的基于逻辑超立方体的可靠组播控制拓扑一组合超立方体结构， c o m c u b e 。通过理论上的分析，对比研究了尽a 呵s h a r c dt r e e 、l o g c u b e 、f m l c u b e 和c o m c u b e 这几种控制拓扑的性能，结果表明基于逻辑超立方体的控制拓扑确 实具有整体上的极大优势，其中又以c o m c u b e 的性能最为突出，并主要表现在 容错性和结构的建立、维护与稳定性方面。 第二、从研究的需要出发，通过对n s 2 以及i i c l 语言的细致研究，根据n s 2 和超立方体结构的特点，设计了基于n s 2 的超立方体路由仿真系统，并实现了 该仿真系统的完全超立方体、逻辑超立方体的单播、组播通信模拟功能。该系统 适用于超立方体结构，具有相当的通用性和易用性，极大地提高了模拟实验的科 学性和高效性，使n s 2 能够被更广泛地用于超立方体模拟研究。 第三、利用仿真系统进行网络模拟实验，研究基于逻辑超立方体控制拓扑的 组播通信在路径长度、信息量、队列长度等方面所体现出来的性能特点。通过对 实验结果曲线图的研究可以得出结论，逻辑超立方体确实具有较好的性能。实验 数据为理论研究提供了支持。 1 。3 论文的组织 论文全文共五章。第一章是绪论，第二章至第四章为论文的主体，第五章 为全文的结论。 第一章为绪论，介绍了可靠组播控制拓扑的研究意义，以及该研究在国内外 的历史和现状，并对本课题进行的主要工作和贡献进行了论述。 第二章介绍了路由的基本原理后，深入剖析了超立方体以及l o g c u b e 、 f u l l c u b e 两种基于逻辑超立方体的控制拓扑，针对它们的优缺点，研究了 c o m c u b e 结构。通过理论上的分析推导，说明了c o m c u b e 的优势。 第三章主要介绍的是基于n s 2 的超立方体路由仿真系统的设计与实现。首 先对比分析当前几种主流网络仿真软件，从中选择n s 2 作为我们的模拟工具。 根据实验和n s 2 的具体特点，设计了仿真系统的功能目标和体系结构。然后对 6 硕士学位论文 第一章绪论 各子系统及其功能模块的算法和实现进行详细的介绍。 第四章主要介绍的是利用仿真系统进行逻辑超立方体的模拟实验，并对结 果进行详细的分析。根据研究的对象和指标，进行实验设计并完成模拟实验。通 过统计数据，分析研究逻辑超立方体结构在不同节点错误率及不同节点错误位置 下的性能表现，证明超立方体的性能优势。 第五章是总结。对本课题所做的工作进行了总结，并阐述了进一步的研究 工作。 硕士学位论文 第二章可靠组播控制拓扑的研究 第二章可靠组播控制拓扑的研究 本章主要从路由的基本原理和理论入手，并介绍单播和组播路由以及它们各 自的特点和当前的适用情况。由于可靠性和可扩展性的要求，基于单播路由的控 制拓扑不够胜任互联网大规模用户的数据通讯，因此人们开始提出和研究组播控 制拓扑。以往提出的基于非超立方体的控制拓扑有树结构等，近几年基于超立方 体的控制拓扑被提出并得到研究。完全超立方体局限性很强，人们又提出 l o g c u b e 和f u l l c u b e ，它们逐步提高了节点连通度、结构容错性等，但仍然存在 不足。针对这些情况，我们研究了一种新的基于逻辑超立方体的组播控制拓扑： 组合超立方体结构，c o m c u b e 。随后我们详细分析对比这些控制拓扑的性能参数， 表明逻辑超立方体确实具有优越的性能，其中c o m c u b e 比l o g c u b e 和f u l l c u b e 更加完善，更具推广实用价值。 本章的结构如下：第一小节为概述，对路由的基本原理和理论，以及单播、 广播和组播路由进行简要的介绍；第二小节简单介绍树结构以及k 阶共享树； 第三小节阐述了超立方体结构的产生、原理和性能特点；第四小节首先比较详细 地介绍和分析l o g c u b e 、f u l l c u b e 两种基于逻辑超立方体的控制拓扑，因为它们 仍然具有较明显的缺陷，我们分析c o m c u b e 控制拓扑，并仔细阐述了c o m c u b e 的思想、机制和算法：第五小节中我们较深入地对比研究树结构以及包括 c o m c u b e 在内的三种结构的性能特点，从理论上分析逻辑超立方体及c o m c u b e 的优势：的第六小节为本章内容的总结。 2 1 概述 根据协议机制，可以将一种通信路由转化映射成某种控制拓扑。因此，在介 绍协议及控制拓扑之前，首先简要介绍路由的基本原理和理论。 2 1 1 路由的概念和组成 ( 1 ) 路由的概念 路由是把信息从源端穿过网络传递到目的端的行为，在传递的路径中至少遇 到一个中间( i n t e 彻e d i a t en o d e ) 节点【3 2 j 。 随着网络的不断发展，多媒体信息在网络中的应用越来越广泛，对网路所能 提供的服务质量也提出了更高的要求。因此满足服务质量的路由协议也随之出 现，并迅速发展起来，路由协议也需要通过更为复杂的模型使用多个量度 硕士学位论文 第二章可靠组播控制拓扑的研究 ( m u l t i d l em e t r i c s ) 来表示网络性能，如在网络负载、延迟和丢失率等方面表示 网络性能。 ( 2 ) 路由的组成 路由包含两个基本的动作：确定最佳路径和通过网络传输信息，后者也称为 ( 数据) 交换【3 2 】。交换相对来说比较简单，而选择路径很复杂。路径选择中的 量度是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度等。为 了帮助选路，路由算法初始化并维护包含路径信息的路由表，路径信息根据使用 的路由算法不同而不同。交换的算法相对而言较简单，对大多数路由协议而言是 相同的，多数情况下，某主机决定向另一个主机发送数据，通过某些方法获得路 由器的地址后，源主机发送指向该路由器的物理地址( m a c ) 的数据包，其协 议地址是指向目的主机的。当分组在网络斗流动时，它的物理地址在变，但其协 议地址始终不变。 2 1 2 单播路由、广播路由和组播路由 路由方式有单播、广播和组播等，它们有各自不同的特性，因此在不同的应 用领域，它们的性能表现也会有很大差别。同时，一个协议中可能会同时使用两 种或超过两种的路由方式。在什么情况下采用哪种路由方式，是根据算法机制的 需要以及路由方式的不同特点决定的。这一节，主要介绍了三种不同路由方式的 简单原理和特点。 ( 1 ) 单播路由( u n i c a s t ) 单播通信路由即点到点通信路由，是目前互联网应用得最广泛的数据传输方 式，比如电子邮件，网页浏览掣。在这种通信方式下，发送者和每一接收者需 要单独的数据通道，每个数据包只能传送给一个目标主机。在大节点数应用的应 用中，源主机必须向每个用户发送一份数据包拷贝，源主机和网络的负载会变得 难以承受。因此单播应用在大节点数的情况下具有很大的局限性。单播路由的两 种情况如图2 2 、图2 3 所示。 图2 2 一对一的单播通信路由 硕十学位论文第二章可靠组播控制拓扑的研究 图2 3 一对多的单播通信路由：有多余的单播数据包被发送给路由器。 ( 2 ) 广播路由( b r o a d c a s t ) 广播路由即源主机向一个网段中的所有主机发送信息包。广播包的目标地址 的主机部分被设置成全“l ”，网络部分设置成当前子网地址。除非特别配置，路 由器一般不会转发广播信息包，这样，广播通信通常被限制在本地的子网内。而 如果路由器转送这些广播，那么，路由回环将很可能引起一场严重的广播风暴。 广播的主要的缺点就是每个广播包都要发送至所有主机，消耗了所有主机上的资 源，即使数据要被网络中大多数机器所丢弃。 在 耐p e r c a s t 中，一个m u i t i c a s t 乒o u p 映射成为h y p e r c u b e 后其控制信息的 传递主要通过广播协议机制实现。 ( 3 ) 组播路由( m u l t i c a s t ) 组播介于单播和广播之间，能使主机发送信息包到网络中任何一组特定的主 机上。这些主机都具有一种特定的地址，称之为组播组地址。支持组播的路由器 会复制转发组播信息包至所有具有该组播地址的主机的接口上。因此组播发送方 只要发送一个信息包而不是很多个，能减少网络上传输的信息包的总量，单台服 务器能够对几十万台主机同时发送连续数据流而无延时。单播与组播的区别如图 2 4 所示。从图中可以看出，主机发送数据的一个拷贝在每个接收者的最后一个 路由器或主机复制它，在一个给定的网络上每个包只传送一次。 图2 - 4 组播通信路由：一个组播数据包发选给具有组播功能的路由器 与单播相比，使用组播技术分发信息常常能从本质上减少整个网络带宽的需 求，具体体现在以下几个方面： 硕士学位论文 第二章可靠组播控制拓扑的研究 网络负载 如果大量的用户经常要在大致相同的时间里访问相同的信息，使用i p 单播 会使网络带宽的消耗呈线性增长，用组播来发送节目使重复数据流被单一传送所 代替，降低带宽消耗。 节点负载 随着用户的增长，单播传送机制会导致主机负载迅速增加，直到不能再发出 信息流。组播通过大大减少需要转发和处理的数据量，从而降低了主机负载。 可扩展性 在i p 单播的情况下，随着需求与应用的增长，多点应用不太可能，因为单 播通信中的客户数量不能无限增长。而组播几乎不受客户数量增长的限制。 虽然i p 组播的概念很早就被提出，但是直到现在它的能力才被充分认识。 目前组播技术应用的增长十分迅速，而且这种趋势正在加快。 2 2 k 阶共享树( k - a 叫s h a r e dt r e e ) 在人们研究超立方体在可靠组播传输的应用之前，已经提出了许多不同的组 播控制拓扑。树结构能够比较有效地降低a c i 洲a c k 阻塞问题，每个节点的负 载只和它的子节点成比例，而不是和整个组播组的规模成比例，具有较好的可扩 展性。因此一个平衡的树结构具有较好的组播性能，如较平衡的节点负载和较短 的路径长度。但当树的根节点不是源节点或组播组中具有多个组播源时，树结构 就难以使用了。k 阶共享树允许具有多个组播源并进行相应重构【3 ”，k 阶共享树 的每个节点最多拥有个子节点。 2 3 超立方体结构 超立方体拓扑结构( h ) ，p e 圮u b e ) 是最近几年发展起来并得到研究与应用的。 由于以往控制拓扑的局限性，j l i e b e h e r r 与b s s e m i 提出了超立方体控制拓扑， 他们对超立方体的研究建立了超立方体控制拓扑的理论基础f 1 ，2 1 。 一个竹维完全超立方体有 ，- 2 ”个顶点( 节点) 和拧2 ”1 条边，每个节点都 从o 到2 “1 ，有一个长度为玎的唯一的二进制编号。当且仅当两个节点编号的二 进制码只有一位相异，即海明距离为1 时，它们之间用一个逻辑边相连。图2 5 所示为一个3 维的超立方体及其节点的二进制编号。 硕士学位论文 第二章可靠组播控制拓扑的研究 图2 53 维超立方体及其节点的二进制编号 一个”维的完全超立方体可以由两个行一l 维子立方体构成，结构中所有节点 二进制编号增加一位。在一个子立方体中节点的二进制编号首位前加一位“0 ”， 在另一个中节点的二进制编号首位前加一位“1 ”。然后连接分别位于两个子立方 体中且编号仅在首位相异的每一对节点。图2 6 显示的就是一个4 维超立方体的 构成。 图2 。6 一个4 维超立方体由两个3 维子立方体构成 使用超立方体作为控制拓扑有许多优点。例如图2 7 所示，树结构可以很容 易地被嵌入到超立方体中【1 ，2 1 ，由于超立方体的相对对称性，嵌入的树结构可以 以任何节点为根节点。因此，超立方体拥有树结构几乎全部的优点，同时避免了 树结构的最佳性能只表现在根节点唯一时的局限性。 硕士学位论文第二章可靠组播控制拓扑的研究 图2 7 超立方控制拓扑可以作为树结构使用 一个具有个节点的完全超立方体结构中的任意节点都有l 0 9 2 个节点( 相 当于l 0 9 2 _ v 个连接，其中l 0 9 2 为整数) 与之相邻，即l 0 9 2 个连接。超立方体 具有许多优点【3 4 ”3 6 ，如较多的并行路径，良好的连通性、容错性和较短的路 径长度等等，使得超立方体成为一种强大的控制拓扑。 以前的许多并行计算领域的研究已经提出了多种将树结构嵌入到超立方体 中的算法阢3 8 ，3 9 】。这些算法是基于稳定的超立方体的，超立方体中的节点是全 部已知并且不变的。此外，大部分的算法都假设超立方体是完全的，即超立方体 中的节点数是2 的整数次幂。但是，在实际组播应用中，不能够保证超立方体中 的节点完全稳定以及超立方体的完整性，因为组播组的成员可以任意加入或退 出，节点也存在出错的可能性。 2 4 现有的基于逻辑超立方体的控制拓扑 2 4 1 l o g c u b e 结构 ( 1 ) l o g c u b e 的形成 因为上一节所述的完全超立方体的局限性，j l i e b e h e r r 提出了”维逻辑超立 方体结构，消除了对节点数的限制条件。我们称之为l o g c u b e 拓扑结构。l 。g c u b e 是根据臣阶共享树，