（计算机系统结构专业论文）源确定组播路由协议的研究与实现.pdf

1 at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e ra r c h i t e c t u r e r e s e a r c ha n d i m p l e m e n t a t i o no fs o u r c e s p e c i f i cm u l t i c a s t r o u t i n g p r o t o c o l b yz h a n gy a n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rx i al i n o r t h e a s t e r nu n i v e r s i t y d e c e m b e r2 0 0 7 i i m眦l删282晏兰4洲8 iiii1y 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名： 络梅 | 签字日期： 如护占2 ， 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 导师签名： 签字日期： 孙1 撕，8 二1 嗲叫 锰 “ 7 誓， 扎 ： 名 文 签 玑 懿 期 作 日 文 了一 跚 字 位 签 学 东北大学硕士学位论文 摘要 源确定组播路由协议的研究与实现 摘要 随着i n t e m e t 的发展和普及，网络应用趋于多元化，同时对网络的带宽和多媒体化 提出了越来越高的要求。带宽的增加使得许多高带宽的应用如远程教学、视频会议、网 络集体游戏、视频点播、分布式集群的数据同步等成为可能。这些应用又带来了新的带 宽的急剧消耗，从而加剧了网络的拥塞。这些应用的典型特点就是高带宽和群发，解决 这类问题的一个好的思路就是发展口组播技术。 本文对各种不同的组播算法、组播路由协议及转发策略进行了分析与比较，指出了 各自的特点及不同的适用场合；传统的组播模型与协议提出已有十几年了，但由于其存 在的可扩展性差等问题，至今未能在i n t e m e t 得到广泛应用。新型的s s m 组播服务模型， 能克服传统组播模型的缺点，有望在不远的将来在i n t e m e t 上得到广泛应用。本文介绍 了当前i n t e m e t 的组播体系结构及其存在的问题，在p i m s m 组播协议基础上，深入研 究s s m 协议的机制，对s s m 组播服务模型的实用性、可扩展性、访问控制等方面做了 全面的分析，为这种新型组播服务模型的应用打好基础；研究了网络仿真软件n s - 2 的 组成与内部架构，及如何利用它进行网络协议的分析与研究，着重研究了其内部组播仿 真机制，在此基础上扩展实现了p i m s s m 组播协议模块，实现了p i m s s m 的仿真，对 其在延迟、路由、丢包率三个方面的实验结果进行了分析，并与p i m s m 进行比较。 本文介绍了组播技术，组播路由协议等基本概念，对其中的p i m s m 组播模型进行 了研究，在此基础上分析s s m 组播服务模型，并通过n s 模块的扩展，对s s m 模型进 行仿真，将其结果与p i m s m 模型进行性能比较，为对组播技术的进一步研究奠定了一 定的基础，并对s s m 的实际应用有一定的参考价值。 关键词：组播，源确定组播协议，p i m s m ，网络仿真 i i _ i 一 - 东北大学硕士学位论文 a b s t r a c t r e s e a r c ha n di m p l e m e n t a t i o no fs o u r c e s p e c i f i cm u l t i c a s t r o u t i n gp r o t o c o l a b s t r a c t w i t ht h ed e v e l o p m e n ta n dp o p u l a r i t yo fi n t e r n e t ，t h en e t w o r ki sa p p l i e dt ov a r i o u sf i e l d s m e a n w h i l e ，i tr e q u i r e sm o r ea n dm o r eb a n d w i d t ht om e e tt h ed e m a n do fm u l t i m e d i a a p p l i c a t i o n s t h ei n c r e a s eo fn e t w o r kb a n d w i d t hm a k e si tp o s s i b l ef o rm a n yh i 曲b a n d w i d t h a p p l i c a t i o n ss u c ha sr e m o t ee d u c a t i o n , v i d e oc o n f e r e n c en e t w o r kg a m e s ，v o da n dd a t a s y n c h r o n i z a t i o no fd i s t r i b u t e dc l u s t e r s t h e s ea p p l i c a t i o n si nr e t u r nr e q u i r eh i g h e rb a n d w i d t h a n dm a k en e t w o r kc o n g e s t i o nw o r s e t y p i c a lc h a r a c t e r i s t i c so ft h e s ea p p l i c a t i o n sa r eh i 曲 b a n d w i d t ha n dm u l t i c a s t , a n dab r i l l i a n ti d e at os o l v et h ei s s u ei st od e p l o yi pm u l t i c a s t t e c h n o l o g y t h i st h e s i sr e s e a r c h e sa n dc o m p a r e sv a r i e sm u l t i c a s ta l g o r i t h m s ，m u l t i c a s tp r o t o c o l sa n d f o r w a r d i n gs t r a t e g i e s ，a l o n g 丽t l lt h e i r f e a t u r e sa n du s e s t r a d i t i o n a lm u l t i c a s tm o d e lw a s p r o p o s e di n19 8 0 s ，b u th a s n tb e e na p p l i e dw i d e l yi ni n t e r n e tb e c a u s eo fi t ss h o r t a g e s n e w s s mm u l f i c a s ts e r v i c em o d e l ，w h i c hc a no v e r c o m et h es h o r t a g e so ft r a d i t i o n a lm u l t i c a s t m o d e l ，h o p e f u l l yc o u l db ew i d e l yd e p l o y e do ni n t e r a c ti nt h en e a rf u t u r e t o d a y si n t e r n e t m u l t i c a s ta r c h i t e c t u r ea n dp r o b l e m so fi ta r ed i s c u s s e d ，o fw h i c hp i m s mm o d e li s f u l l y r e s e a r c h e d ，s s mi ss a i d t ob ee a s y t o - i m p l e m e n t ，e x t e n d a b l ea n da c c e s sc o n t r o l l a b l en e w s e r v i c em o d e l ；t h e s ea r ef o u n d a t i o no ft h ea p p l y i n go fn e wm u l t i c a s tm o d e l n s 一2s i m u l a t o r s o f t w a r e ，i t si n t e r n a ls t r u c t u r ea n dh o wt ou s ei tt or e s e a r c hn e t w o r kp r o t o c o l sa r e i n v e s t i g a t e d ，e m p h a s i so nt h ei m p l e m e n t a t i o nm e c h a n i s mo f i t sm u l t i c a s ts i m u l a t i o n ；b a s e do n n s - 2 ，t h en e wp i m s s mm u l t i c a s tm o d e la r ei m p l e m e n t e d ，a n ds i m u l a t ep i m s s m 谢t l l i t ，a n a l y z et h er e s u l t so fi t si m p l e m e n t a t i o n so nd e l a y i n g ，r o u t i n ga n dl o s sr a t e ，a n dc o m p a r ei t 谢t 1 1p i m s m t h i st h e s i si n t r o d u c em u l t i c a s tt e c h n i q u e s ，m u l t i c a s tr o u t i n gp r o t o c o l sa n do t h e rb a s i c c o n c e p t s ，a n dr e s e a r c ht h ep i m s mm u l t i c a s tm o d e l o nt h eb a s eo fi t ，s s mm u l t i c a s tm o d e li s a n a l y z e d t h r o u g ht h ee x t e n c eo fn s ，t h es s m i si m p l e m e n t e d t h er e s u l t sa r ec o m p a r e dw i t h p i m - s m ；t h i sl a ys o m ef o u n d a t i o nf o rf u r t h e rr e s e a r c ho fs s m ，a n dc a nb eu s e df o rr e f e r e n c e b ys s mp r a c t i c a la p p l i c a t i o n k e yw o r d s ：m u l t i c a s t ；s o u r c es p e c i f i cm u l t i c a s t ；p i m - s s m ；n e t w o r ks i m u l a t i o n i i i ， t - 。 东北大学硕士学位论文目录 目录 独创性声明i 摘要 a b s t r a c t i i i 第一章绪论：1 1 1 研究背景1 1 2 组播概述2 1 3s s m 概述3 1 4 国内外研究现状4 1 5 本文完成的主要工作：5 第二章组播技术7 2 1 组播地址一。7 2 2 组播路由算法：i 8 2 2 1 组播路由算法的分类8 2 2 2 逆向路径转发算法9 2 3 组播路由协议1 1 2 3 1 密集模式。1 1 2 3 2 稀疏模式1 2 2 4 数据报转发策略1 3 2 5 互联网组管理协议1 5 2 6 小结1 8 第三章源确定组播的研究1 9 3 1p i m s m 协议1 9 3 1 1 组播数据的转发1 9 3 1 2 共享树的建立2 0 3 1 3 组播源的注册21 3 1 4 共享树和最短路径树的切换2 3 3 1 5 剪枝2 4 3 1 6 “声明消息的传递2 5 3 1 7p i m s m 控制消息封装2 6 3 1 8p i m s m 控制消息包格式2 6 3 2p i m s s m 协议2 7 3 2 1p i m s s m 协议相对p i m s m 协议的变化2 7 3 2 2s s m 地址范围2 8 i v 东北大学硕士学位论文 目录 3 2 3s s m 地址的语义2 8 3 2 4 主机的要求2 9 3 2 5 路由器的要求。3 l 3 3 小结3 2 第四章p 口s s m 的实现3 3 4 1n s 内协议的实现3 3 4 1 1n s 中的组播协议3 3 4 1 2n s 中实现组播的类3 4 4 2p i m s m 的实现3 7 东北大学硕士学位论文第一章绪论 第一章绪论弟一早三否 下匕 1 1 研究背景 随着宽带多媒体网络的不断发展，各种宽带网络应用层出不穷。i pt v 、视频会议、 数据和资料分发、网络音频应用、网络视频应用、多媒体远程教育等宽带应用都对现有 宽带多媒体网络的承载能力提出了挑战。采用单播技术构建的传统网络已经无法满足新 兴宽带网络应用在带宽和网络服务质量方面的要求，随之而来的是网络延时、数据丢失 等等问题。此时通过引入i p 组播技术，有助于解决以上问题。组播网络中，即使组播用 户数量成倍增长，骨干网络中网络带宽也无需增加。简单来说，成百上千的组播应用用 户和一个组播应用用户消耗的骨干网带宽是一样的，从而最大限度的解决目前宽带应用 对带宽和网络服务质量的要求。 自从1 9 8 8 年s t e p h e nd e e r i n g 建立d 组播模型( 即任意源组播a n y - s o u r c em u l t i c a s t ， a s m ) 以来，组播技术一直未能在i n t e r a c t 上大规模的实现。一些存在的问题制约了它的 发展，例如可扩展性、地址分配、计费和安全性等。在众多的解决方法中，s s m ( s o u r c e s p e c i f i cm u l t i c a s t ) 1 j 【2 】单信源的应用是被普遍认可的，因为i p 组播中9 9 以上的应用，如文 件传输和流媒体等，都是单信息源的应用。s s m 是对p i m s m 协议的扩展，以便在一对 多的通信中能更有效的传送数据。s s m 使得接受者客户机一旦通过目录服务了解到某个 组播信源的信息，就直接从该信源获得数据包，而不是从共享汇聚点r p 获得数据包。 s s m 中，组播通信的路由完全由信源树完成，不需要共享树，也不需要r p 。s s m 能够明 确指定包含或者排除特定信源，提供了一定程度的安全性。s s m 还解决了一对多应用中 的p 组播地址冲突的问题，两个组织在两个不同的应用中使用相同的组播目标地址时， 就会产生冲突。和a s m 比较，s s m 是一种简单有效的组播模型，它可以减轻地址分配、 计费、安全性等许多实现中的问题。 组播协议分为主机一路由器之间的组成员关系协议和路由器一路由器协议。组成员 关系协议包括i g m p ( 互联网组管理协议) 。组播路由协议分为域内组播路由协议及域间组 播路由协议。域内组播路由协议包括距离矢量组播路由协议( d v m r p ，d i s t a n c ev e c t o r m u l t i c a s tr o u t i n gp r o t o c 0 1 ) ，开放式组播最短路径优先协议( m o s p f ，m u l t i c a s te x t e n s u sf o r o p e ns h o m s tp a t hf i r s t ) ，( c b t ，c o r e b a s e dt r e e s ) ，与协议无关的组播一密集模式 ( p i m d m ，p r o t o c o li n d e p e n d e n tm u l t i c a s td e n s em o d e ) ，与协议无关的组播一稀疏模式 ( p i m s m ，p r o t o c o li n d e p e n d e n tm u l t i c a s ts p a r s e m o d e ) 等协议【引。这些组播路由协议对网 络吞吐量、数据传输延迟、丢包率等网络性能指标产生很大影响，在数据网络规划和设 东北大学硕士学位论文第一章绪论 计时合理的应用这些组播路由协议对构建网络起到重要的作用。通过网络仿真的方法来 测试组播路由协议，分析计算机局域网、广域网及接入因特网的性能，使得在设计阶段 就能对所设计的网络的性能做出预测，合理地修改其设计，从而选择一个符合要求的性 价比较优的方案。与此同时，源代码开放的网络仿真软1 ：$ n s - 2 ( n e t w o r ks i m u l a t o r2 ) 是 国际上最广泛的用来评价现有网络( 协议) 性能，进行现实中难以实现的大规模仿真实验 的网络仿真软件，它主要应用在科研和教学上【4 】。因此，采用n s 2 网络仿真软件研究网 络( 协议) 性能具有非常重要的现实意义和潜在的应用价值，为仿真软件的推广应用打下 良好的基础。 1 2 组播概述 组播技术是t c p i p 传送方式的一种，t c p i p 有三种传输方式：单播、组播、广播。 传统的m 通信是在一个源口主机和一个目标p 主机之间( 单播) 或者一个源主机和网 络中所有的p 主机之间( 广播) 进行的。要将信息发送给网络中的多个而非所有口主机， 采用传统的d 通信技术只有两种方法可以选择：采用广播方式或者由源p 主机分别向 网络中的多个目标口主机单播发送p 包。广播方式会将信息发送给不需要的m 主机而 浪费带宽，而且可能的路由回环会引起广播风暴。单播方式由于d 包的重复发送会浪费 掉大量带宽，同时也增加了服务器的负载。可见，传统的i p 技术不能有效地解决单点发 送多点接收的问题，而口组播却很好的解决了这个问题【5 j 。 p 组播是指在p 网络中数据包以尽力而为传送的形式发送到所有网络节点的某个 确定子集，这个子集称为组播组。i p 组播的基本思想是源i p 主机只发送一份数据，然 后经过路由器或交换机拷贝发送数据到一个或多个接收者。即允许源i p 主机向网络上所 有主机的一部分( 子集) 发送i p 分组，只有该子集内的主机( 目标主机) 可以接收该分组， 而网络中其他主机不能收到该分组。这种逻辑上的子集就是组播组，用d 类p 地址 ( 2 2 4 0 0 0 - - 2 3 9 2 5 5 2 5 5 2 5 5 ) 来标识1 6 】。i p 组播技术有效地解决了业务中的单点发送多点 接收，多点发送多点接收的问题，实现了口网络中点到多点高效数据传输，有效地节约 了带宽，降低了网络负载。 在i p 组播路由网络中，p 组播路由算法和组播路由协议是口组播技术的关键，其 克服了利用单播通信模型传递组播信息带来的带宽瓶颈，减少了发送相同数据到多个接 收者的通信费用，节省了网络带宽和资源，时延小，具有可升级性。但在提高带宽利用 率的同时，还需要考虑服务质量的其他方面，如吞吐量、延迟、抖动、丢包等，才能更 好地满足多媒体业务的需要。 一2 一 东北大学硕士学位论文第一章绪论 1 3s s m 概述 s s m 是i p 组播技术中的一项新兴技术，这项技术针对组播业务的特点进行了设计， 提供了更优化的网络性能。 s s m 是从e x p r e s s 演变而来的组播协议。s s m 的组地址范围规定如下：对于i p v 4 网 络，在2 3 2 0 0 0 2 3 2 0 0 2 2 5 内，对i p v 6 网络，在f f 3 x ：4 0 0 0 ：0 0 0 0 f f 3 x ：7 f f f ：f f f f 内。在 s s m 模式下，由单源( 组属主) 向s m m 地址范围内的一个组播地址发送i p 组播数据包。( s ，g ) 表示一个s s m 组，通常也称为一个s s m 频道。s s m 频道是特定源相关的，o p ( s 1 ，g ) 、( s 2 ，g ) 是两个不同的s s m 频道。主机通过某种方式( 如目录服务或w e b 页) 得知活动的s s m 频道 后，即可通过i g m p v 3 ( 对i p v 4 网络) 或m l d 2 ( 对i p v 6 网络) 消息报告对该频道的兴趣，通过 i g m p v 3 或m l d 2 与该主机直连的最后一跳路由器可以知道主机对该频道的兴趣，然后， 路由器向源s 方向发出( s ，g ) j o i n 消息并在沿途的路由器建立相应的( s ，g ) 状态，从而建立 一个以s 为根，通向各个接收方的单向最短路径树，由s 发出的组播流量将沿该树传送到 接收方7 】【8 】。 s s m 是一种区别于传统组播的的新的业务模型，它使用组播组地址和组播源地址同。j 时来标识一个组播会话，而不是像传统的组播服务那样只使用组播组地址来标识一个组 播会话。s s m 保留了传统p i m s m 模式【3 j 【4 j 中的主机显式加入组播组的高效性，但是跳过 了p h m s m 模式中的共享树和r p ( r e n d e z v o u sp o i n t ) 规程。在传统p i m s m 模式中，共享树 和r p 规程使用( ，g ) 组对来表示一个组播会话，其中g 表示一个特定的i p 组播组，而宰表 示发向组播组g 的任何一个源。s s m 直接建立由( s ，g ) 标识的一个组播最短路径树专 ( s p t ：s h o r t e s tp a t ht r e e ) ，其中g 表示一个特定的i p 组播组地址，而s 表示发向组播组g 的 特定源的i p 地址。s s m 的一个( s ，g ) 对也被称为一个频道( c h a n n e l ) ，以区分传统p i m s m 组播中的任意源组播组( a s m ，a n ys o u r c e m u l t i c a s t ) 。由于a s m 支持点到多点和多点到 多点两种组播业务模式，因此源的发现过程是a s m 复杂性的原因，例如在p i m s m 模式 中，用户点击浏览器中的组播内容，接收端设备只被通知到组播组的内容，而没有被通 知到组播源的信息。而在s s m 模式中，用户端将同时接收到组播源和组播组信息。因此， s s m 特别适合于点到多点的组播服务，例如网络娱乐频道、网络新闻频道、网络体育频 道等业务，但如果要求多点到多点组播服务则需要a s m 模式。 s s m 是对p i m 协议的扩展，以便在一对多的通信中能更有效地传送数据。s s m 使得 接受者客户机旦通过目录服务了解到某个组播信源的信息，就直接从该信源获得数据 包，而不是从共享汇聚点r p 获得数据包。s s m 不需要使用组播源发现协议m s d p 来发现 其他p i m 域内的活动信源。s s m 中，组播通信的路由完全由信源树完成，不需要共享树， 也不需要r p 。s s m 能够明确指定包含或者排除特定信源，提供了一定程度的安全性。s s m o 东北大学硕士学位论文 第一章绪论 还解决了一对多应用中的i p 组播地址冲突的问题，两个组织在两个不同的应用中使用相 同的组播目标地址时，就会产生冲突。处在s s m 模式下的路由器根据完整的( s ，g ) 地址 来对数据流进行选路。只要信源有i n t e m e t 上可以发送的惟一的i p 地址，来自该信源的 任何( s ，g ) 就都是惟一的例。 s s m 协议具有简单、安全性好、频道地址无冲突等优点，被认为是目前推进组播实 施、提供域间、移动组播的首选组播协议之一，在s s m 模型下提供多源组播通信也成为 目前的研究热点。 1 4 国内外研究现状 源确定组播( s s m ) 在近年来引起了广泛的注意，一大批研究人员在对它进行研究。 2 0 0 3 年7 月，s b h a t t a c h a r y y a 提交了r f c3 5 6 9 t 5 1 ，在其中对源确定组播服务模型进 行了概述，在与传统的组播模型( a s m ：a n y s o u r c em u l t i c a s t ) 进行对比时，指出了源确定 组播模型的一些优点，如：解决了地址分配，缺乏访问控制，处理周知源效率低等问题。 还提出了源确定组播服务的实现框架，以及探讨了如何使用现有的协议p i m s m 和 i g m p m l d 部署s s m 服务。 2 0 0 5 年1 0 月，i e t f 工作组提出了“s o u r c e s p e c i f i cm u l t i c a s tf o ri p 草案 6 1 ，该草 案明确指出了为s s m 组播预留的i p v 4 和i p v 6 的i p 组播地址范围，详细的描述了运用 源确定组播技术的一些优点。提出要支持源确定组播的一些需求及扩展：节点主机 ( h o s o ，i p 路由模块及其接口和s s m 地址分配；路由器( r o u t e r ) ，数据包转发和路由协 议。也提到了利用现有组播路由协议p i m s m 做一些修改，使其支持源确定组播 口i m s s m ) 。此外，还讨论了使用源确定组播可以带来的安全方面的优点。 2 0 0 6 年3 月，i e t f 对r f c 2 3 6 2 3 】进行了一些修改和补充，提出了p r o t o c o li n d e p e n d e n t m u l f i c a s t s p a r s em o d e ( p i m s m ) ：p r o t o c o ls p e c i f i c a t i o n 草案，在该草案里，工作组成员除 了详细说明了p i m s m 的实现规范，还详细的讨论了在p i m s m 协议的基础上如何进行 修改使其支持s s m 和如何进行删减使协议单独支持s s m ( p i m s s l v ot l o 】【1 1 1 。 进行网络性能研究有很多方法，包括分析建模、实验测试和网络仿真等【l2 1 。它们各 有其优缺点和适用范围。 分析方法：建立分析模型对所研究的对象( 例! t n w e b 应用) 和所依存的网络系统( 例如 i n t e r a c t ) 进行初步分析，根据一定的限定条件和合理假设，对研究对象和系统进行描述， 抽象出研究对象的数学分析模型。通过数学推理证明，或与现实实例对照，或与仿真的 结果比较等方法，来验证模型的有效性和精确性，对模型进行校验修正。最后利用求解 后的数学分析模型对问题进行解答。这种方法的优点是具有灵活性，不受硬件或软件性 能等物质资源的限制，但模型的有效性和精确性受假设限制很大，当一个系统很复杂时， 4 - 东北大学硕士学位论文第一章绪论 无法用一些限制性假设来对系统进行详细描述。这种方法适用于网络结点协议实现理论 的研究和简单的网络行为分析。 实验方法：建立测试床和实验室对所研究的对象( 例女i w e b 应用) 和所依存的网络系 统( 例如i n t e m e t ) 进行初步分析，设计出研究所需要的合理硬件和软件配置环境，建立有 特定特性的实际网络，在现实的网络上实现对网络协议、网络行为和网络性能的研究。 这种方法具有针对性，可以获得更真实的数据，不会丢失重要的详细资料。缺点是成本 较高，重新配置或共享资源更难，运用起来不灵活，只适用于小规模的网络性能评估， 不能实现网络中的多种通信流量和拓扑的融合。 仿真方法：应用网络仿真软件对所研究的对象( 例如w e b 应用) 和所依存的网络系统 ( 例如i n t e r n e t ) 进行初步分析，自己开发或选用一个网络仿真工具，设计一个实际的或理 论的网络系统的仿真模型，在计算机上运行这个模型，并分析运行的输出结果。仿真法 很灵活，可以根据需要设计所需的网络模型，以用相对很少的时间和费用了解网络在不 同条件下的各种特性，获取网络研究的有效数据。缺点是受软硬件资源的限制，无法同 时展现现实网络的全部特性。仿真方法适用于网络协议研究、网络性能研究和网络设计。 国外对虚拟网络实验的研究己有一段时间，比较全面和通用的是由美国国防部高级 研究计划局( d a i 冲a ) 立项，南加利福尼亚劳伦斯伯克利国家实验室( l b n l ) 、加利福尼亚 的伯克利大学cb e r k e l e y ) 、美国施乐公司的p a l oa l t o 研究中一巴, ( x e r o xp s r c ) 和南加利 福尼亚信息科学院( u s c i c i ) 联合设计的网络仿真器n s 2 。目前正以n s 2 为引擎，开发一 个虚拟互联网络测试平台系统v i n t ( v i t u a li n t e r n e t w o r kt e s t b e d ) ，提供给专业网络设计人 员作为网络性能测试工具，目前己在2 0 0 多家科研机构和大专院校使用【1 4 】。 1 5 本文完成的主要工作 对现有的i n t e m e t 组播路由算法、协议和转发策略进行研究，分析它们的优缺点以 及各自不同的适用场合，着重研究了s s m 这种新型组播服务模型及其密切相关的 p i m s m 组播服务模型。研究n s 2 开源网络仿真软件的组成与结构，以及其内部组播仿 真的实现细节。在此基础上探讨与研究s s m 组播服务模型及基于n s 2 的仿真实现机制。 本课题研究的主要内容： ( 1 ) 研究s s m 组播模型及其密切相关p i m s m 组播服务模型。 ( 2 ) 网络仿真软件1 1 8 的构成，以及其内部组播仿真的实现机制。 ( 3 ) 在n s 中组播仿真的基础上，实现s s m 组播服务模型。 ( 4 ) 利用所实现的s s m 组播仿真协议进行仿真实验。 本文的组织安排： 第二章介绍了组播地址、路由算法、路由协议和转发策略，以及因特网组播管理协 一5 一 东北大学硕士学位论文 第一章绪论 议i g m p o 第三章首先研究了p i m s m 协议，然后研究p i m s s m 协议，并对两个协议进行了 比较。 第四章研究了n s 2 网络仿真软件的构成与内部结构及利用其进行网络协议研究的 一般步骤，在p i m s m 组播仿真实现细节的基础上，扩展实现了s s m 组播，即p i m - s s m 。 第五章对p i m s s m 组播与p i m s m 组播进行对比仿真测试，并对仿真结果进行了 分析。 结论部分是对整个论文工作的总结以及下一步工作的展望，指出我们工作中有待改 进的地方，同时指明了下一步的研究方向。 东北大学硕士学位论文 第二章组播技术 第二章组播技术 近年来，随着i n t e m e t 的迅速普及和爆炸性发展，在i n t e m e t 上产生了许多新的应用， 其中不少是高带宽的多媒体应用，如网络视频会议、网络音频视频广播、a o d v o d 、 股市行情发布、多媒体远程教育、协同计算、远程会诊等。这就带来了带宽的急剧消耗 和网络拥挤问题。为了缓解网络瓶颈，人们提出各种方案：增加带宽，改变网络流量结 构，应用q o s 机制及以妒组播技术。其中采用不同于传统单播的婵组播技术是解决这 些问题的关键技术之一。 本章主要对组播技术所要涉及的基础理论加以概述，包括组播地址、组播路由算法、 组播路由协议、数据包转发策略及互联网组管理协议( i g m p ) 。 2 1 组播地址 在组播通信中，需要两种地址：一个p 组播地址和一个e t h e m e t 组播地址。其中， i p 组播地址标识一个组播组。由于所有p 数据分组都封装在e t h e m e t 帧中，所以还需要 一个组播e t h e m e t 地址。为使组播正常工作，主机应能同时接收单播和组播数据，这意 味着主机需要多个口和e t h e m e t 地址。 p 地址方案专门为组播划出一个地址范围，在i p v 4 中为d 类地址，范围是2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 ，并将d 类地址划分为局部链接组播地址、预留组播地址、管理权限 组播地址【7 】；在i p v 6 中为组播地址提供了许多新的标识功能【8 】oi p v 4 的组播地址格式如 图2 1 所示，i p v 6 的组播地址如图2 2 所示。 0l233 1 1110 g r o u pi d 图2 1i p v 4 组播地址格式 f i g 2 1a d r e s sf o r m a to fi p v 4m u l t i c a s t 0 781 1 1 21 5 1 6 1 2 7 1 1 1 1 1 1 1 1 if l a g ls c o p i c t o 呷i d 图2 2l p v 6 组播地址格式 f i g 2 2a d r e s sf o r m a to fi p v 6m u l t i c a s t i p v 4 组播地址又可分为局部链接组播地址、预留组播地址、管理权限组播地址。 ( 1 ) 局部链接地址：2 2 4 0 0 0 2 2 4 0 0 2 5 5 ，用于局域网，路由器不转发属于此范围 的i p 包。 o 一 东北大学硕士学位论文 第二章组播技术 ( 2 ) 预留组播地址：2 2 4 0 1 0 - - - 2 3 8 2 5 5 2 5 5 2 5 5 ，用于全球范围或网络协议。 ( 3 ) 管理权限地址：2 3 9 0 0 0 - - - 2 3 9 2 5 5 2 5 5 2 5 5 ，组织内部使用，用于限制组播范围。 组播地址的最后2 8 位没有结构化，即没有网络d 和主机i d 之分。响应某一个m 组播地址的主机构成一个主机组，主机组可跨越多个网络。i p v 6 中特殊的定义见表2 1 。 表2 1m v 6 中特殊域定义 t a b l e2 1s p e c i a ld e f i n i t i o ni ni p v 6 域 标志( f l a g s ) 范n ( s c o p e ) 值 0 0 0 00 0 0 10 0 0 10 0 1 00 1 0 1 1 0 0 01 1 1 0 其他 永久组动态组 本地本地本地本地全局组保留或 含义 播地址播地址节点链路 网点组织播地址末指定 2 2 组播路由算法 由于一个组播组的成员可以分布在互联网的各个角落，为了能让组播源发出的数据 到达组播组的所有成员，组播路由的选择方法至关重要。组播路由算法决定组播树的建 立过程，指明经过什么样的操作步骤使组播路由器建立起组播转发表。 2 2 1 组播路由算法的分类 组播路由算法可以从不同的角度、不同的准则来分类例。 按是否允许网络成员随时加入或离开组播组分为静态路由算法和动态路由算法。静 态组播路由算法中，组播组成员是固定的，路由计算一次性完成，并且在一次连接过程 中组播成员和路由树都不发生改变。而动态组播路由算法则允许组成员动态加入或离开， 组播树在一次连接中一般会发生改变。 按是否有q o s 约束分为无约束算法和有约束算法。许多现有的算法是为非实时网络 设计的无约束组播路由算法，它们往往只试图优化树的费用，但实时应用对q o s 提出要 求，有约束的组播路由算法通常是在给定q o s 约束的条件下使树的费用最小。 按是否由一个节点集中运算或分布式运算分为集中式和分布式算法。集中式算法往 往简单、快速，但是由一个节点维护整个网络的状态，其开销有可能会非常大，并且当 网络大时，搜集整个网络的状态会变得很困难。但是在许多情况下j 这些算法可以作为 其它算法比较的工具，具有一定的理论意义，吸引着广大研究者去深入研究。在分布式 算法中，网络中的每个节点都参与运算，这些节点只掌握网络的部分信息，通过节点间 相互交换信息来计算路由。分布式算法相对于集中式算法较复杂且速度慢，但是它有一 个显著的优点：就是任何节点都不用保持整个网络的状态。到日前为止，集中式算法的 研究较多，分布式算法的研究较少。 一8 一 东北大学硕士学位论文第二章组播技术 实际上，一种算法可以同时属于以上一种或几种分类方法，如某种组播路由算法可 以是集中式静态无约束算法。 总的来说，目前对静态的集中式组播路由算法( 包括无约束和有约束两种情况) 己有 许多研究，而分布式组播路由算法、动态组播路由算法的研究成果较少，且目前大部分 算法的复杂度较高，无法用于实际网络。 静态有约束算法可以定义为给定信源( 集) s 和信宿( 集) r 、一组q o s 参数上限c 和可 能的优化目标，寻找满足约束条件c 下覆盖s 和r 中所有节点的最佳可行树。根据约束 条件的不同，静态有约束算法中的约束条件可以是路径约束，即源到信宿的路径上相应 约束参量满足约束上限( 如时延) ，或源到任意两个信宿的路径上某一度量的差值( 如时延 差) ；也可以是链路约束，即链路上的约束参量满足约束条件，如链路带宽约束；还可以是 节点约束，即节点上的约束参量满足约束条件，如节点度数约束。典型的时延约束算法 有k p p 算法、b s m a 算法、c d k s 算法、q d m r 算法等。时延和时延差约束的算法有 d v m a 算法等。带宽约束是一类相对简单的问题，只要把带宽不足的链路去掉即可。 静态无约束算法有三类：最短路径、s t e i n e r 树、中心树。最短路径算法的典型算法 有d i j k s t r a 算法、b e l l m a nf o r d 算法、逆向最短路径转发算法r p f 1 0 】。s t e i n e r 树的典型 算法有k m b 算法、m p h 算法、a d h 算法、d d m c 算法【l l 】。中心树的主要问题是选择 中心点，典型的中心点选择方案有最佳中心点