（计算机软件与理论专业论文）组播网络性能影响因素及优化方法的研究.pdf

山东大学硕士学位论文 摘要 近年来，随着在i n t e r n e t 上流媒体、视频等业务的相继开展，i p 组播技术和应用开始快速发展。因组播技术能以高效，可扩展的方式发 送单点到多点、多点到多点的数据，能有效节省带宽和较少网络拥塞， 很多专家认为它将成为下一代互联网络的关键技术之一。分析组播网络 性能的影响因素，有着非常重要的意义，但由于网络本身的复杂性，研 究组播网络性能的影响因素显得比较困难。然而随着计算机技术和网络 拓扑生成器工具的发展，上述问题得到了很好解决。利用计算机技术结 合网络拓扑的生成进行模拟与仿真已经成为进行网络设计和网络性能评 估的有效手段n s - 2 是一个理想的仿真平台，它可以进行各种网络协议 的仿真比较，借助它可以进行组播的模拟与仿真，处理仿真结果可以分 析组播路由协议、网络拓扑以及组播组大小和数目对网络性能的影响。 当网络中有大量组播组存在时，组播的可扩展性是阻碍组播广泛应 用的主要因素，路由器的转发状态条目将随着组播组数目的增加而呈线 性增加，这些不断增长的转发条目将使得内存需求增加，同时转发过程 也将变馒。聚合组播是一项新技术，其主要目标是让多个组播组在同一 个域内共享同一棵组播树，通过减少网络中组播树的数目来减少转发状 态，从而可以大大提高网络性能。 本论文首先介绍了组播协议及组播的应用，分析n s - 2 的结构及主要 组件的实现规则和主要功能并介绍如何在n s - 2 中添加新协议，接着介绍 随机网络拓扑的相关知识，在此基础上重点分析了两种域内组播路由协 议p i m d m 和p i m s m 的原理，利用n s 一2 分多种情况对两者进行了仿真实 验，并对实验数据进行了分析，研究了组播路由协议、网络拓扑、组播 组大小、组播组数量对网络性能的影响。在第六章中针对聚合组播主要 分析了贪心算法存在的不足，并在此基础上给出了一种算法，这种算法 时间复杂度低，并且能够很好优化组播网络性能。 关键词：组播网络性能，网络拓扑，仿真，聚合组播 l 、 - 山东大学硕七学位论文 a b s t r a c t i nr e c e n ty e a r s ，a st h ed e v e l o p m e n ta n dw i d eu s eo fs t r e a mm e d i aa n d v i d e ob a s e do nt h ei n t e r n e t ，i pm u l t i c a s t i n gt e c h n o l o g yh a sb e e nq u i c k l y e x p a n d e d ，b e c a u s eo ft h a ti pm u l t i c a s t i n gc a ns e n dd a t at om u l t i p l er e c e i v e r s f r o mo n es o u r c eo rm o r ei na ne f f i c i e n ta n de x t e n d a b l ew a y , a n dt h a ti tc a n s a v eb a n d w i d t h sa n dr e d u c et h ep o s s i b i l i t yo fc o n g e s t i o n ，m a n ye x p e r t s b e l i e v et h a ti ti so n eo ft h em o s ti m p o r t a n tt e c h n o l o g i e so ft h en e x t g e n e r a t i o no fi n t e r n e t i ti sv e r yi m p o r t a n tt of i n dp a r a m e t e r st h a ta f f e c tt h e p e r f o r m a n c eo fm u l t i e a s tn e t w o r k h o w e v e r ，a st h en e t w o r ki t s e l fi sd e e p l y c o m p l e x ，i ti st o od i f f i c u l tt oa n a l y z ep a r a m e t e r st h a ta f f e c tt h ep e r f o r m a n c eo f m u l t i c a s tn e t w o r k w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n dn e t w o r k t o p o l o g yg e n e r a t i o nt o o l s ，t h ea b o v ep r o b l e mh a sb e e nw e l ld e a l t ，n e t w o r k s i m u l a t i o n ( n s ) b a s e do nt o p o l o g yg e n e r a t i o nh a sa l r e a d yb e e no n eo ft h e i m p o r t a n tw a y st od e s i g nn e t w o r ka n dt e s tp e r f o r m a n c e n s 一2i sa ni d e a lt e s tb e d t oc o m p a r ep r o t o c o l sb e c a u s ei tp r o v i d e sm a n yp u b l i c l ya v a i l a b l es i m u l a t o r sw i t h al a r g ep r o t o c o ll i b r a r y o n ec a nd om u l t i e a s ts i m u l a t i o nb yn s 一2 ，a n dt h r o u g h d e a l i n gw i t ht h er e s u l to fs i m u l a t i o n ，t h ee f f e c to fm u l t i c a s tr o u t i n gp r o t o c o l ， n e t w o r kt o p o l o g y ，m u l t i c a s tg r o u ps i z ea n dt h en u m b e ro fm u l t i e a s tg r o u p s t ot h ep e r f o r m a n c eo fm u l t i c a s tn e t w o r kc a nb es t u d i e d w h e nt h e r ea r el a r g en u m b e r so fg r o u p si nt h en e t w o r k ，t h es t a t e s c a l a b i l i t yi so n eo ft h em o s tc r i t i c a li s s u e st h a td e l a yt h ed e p l o y m e n to f m u l t i c a s t f o r w a r d i n gs t a t ew i l li n c r e a s el i n e a r l yw i t ht h en u m b e ro fg r o u p s g r o w i n g n u m b e ro f f o r w a r d i n g s t a t ee n t r i e sm e a n sm o r e m e m o r y r e q u i r e m e n ta n ds l o w e rf o r w a r d i n gp r o c e s s a g g r e g a t e dm u l t i e a s ti san e w t e c h n o l o g y , i t a i m st of o r c em u l t i p l em u l t i c a s t g r o u p s t os h a r eo n e d i s t r i b u t i o nt r e ei na ni n t r a d o m a i n t h i sw a y , t h en u m b e ro ft r e e si nt h e n e t w o r km a yb es i g n i f i c a n t l yr e d u c e d ，c o n s e q u e n t l y , f o r w a r d i n gs t a t ei sa l s o r e d u c e d ，a n dt h u st h ep e r f o r m a n c eo fm u l t i c a s tn e t w o r kc a nb eh i g h l y h e i g h t e n e d i nt h i sp a p e rm u l t i c a s tp r o t o c o l sa n dt h em a i na p p l i c a t i o no fm u l t i c a s t a r ef i r s td i s c u s s e d t h em a i no b j e c t sa n df u n c t i o n si nn s 2a n dh o wt oa d d n e wp r o t o c o la r e a n a l y z e d f u r t h e r m o r et h es t o c h a s t i cn e t w o r kt o p o l o g y i i j - ， 山东大学硕士学位论文 m o d e l sa r ei n t r o d u c e d b a s e do nt h ef o r m e rd i s c u s s i o n ，t w oi n t r a - d o m a l n m u l t i c a s t r o u t i n g p r o t o c o lp i m s ma n dp i m s mt h e o r ya n dt h e i r s i m u l a t i o n si nn s 一2a r ef o c u s e do n b yd e a l i n gw i t ht h es i m u l a t i o nr e s u l t ， t h ee f f e c to fm u l t i c a s tr o u t i n gp r o t o c o l ，n e t w o r kt o p o l o g y ，m u l t i c a s tg r o u p s i z ea n dt h en u m b e ro fm u l t i e a s tg r o u p st ot h ep e r f o r m a n c eo fm u l t i c a s t n e t w o r ka r ek n o w n i nc h a p t e r6a st oa g g r e g a t e dm u l t i c a s t ，b a s e do ns t u d y t h ed e f i c i e n c yo fg r e e d ya l g o r i t h m 。an e wa l g o r i t h mi sp r o p o s e d ，t h i s a l g o r i t h mh a sl o wt i m ec o m p l e x i t y , a n di t c a ns i g n i f i c a n t l yi m p r o v et h e p e r f o r m a n c eo fm u l t i c a s tn e t w o r k k o y w o r d s ：m u l t i c a s tn e t w o r kp e r f o r m a n c e ，n e t w o r kt o p o l o g y , s i m u l a t i o n ， a g g r e g a t e dm u l t i c a s t “i 一 。7 t 3 l 、 ? j 原创性声明 本人郑重声明：所呈交的学位论文，是本 行研究所取得的成果。除文中已经注明引用的 其他个人或集体已经发表或撰写过的科研成果 献的个人和集体，均已在文中以明确方式标明 承担。 ， 论文作者签名：墨坌日期： 目，一 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) “ 论文作者签名：监导师签名：巫日 期： 二。年辱8f 仓 t l 山东大学硕士学位论文 第1 章绪论 1 1 引言 自从d e e r i n g 博士“1 1 9 8 8 年建立i p 组播模型以来，i p 组播技术一直是人 们研究的一个热点问题。i p 组播是一种有效的支持点到多点、多点到多点通 信的机制，它利用树传送结构，其数据分组仅在分枝节点处被复制，同时在每 条链路上仅转发一次，这种方式使得i p 组播技术可以高效地将数据同时传送 到各个组播组成员，弗能有效支持大量组播组。组播网络性能如平均端到端延 ， ， 迟、带宽开销、路由器维持的转发状态数等受组播路由协议、网络模型、组播 组大小和组播组数日等因素的影响。不同的组播路由协议使用不同的机制建立 组播树，相应的维护和控制消息也不一样；组播路由协议对网络拓扑结构具有 较大的依赖性，由于网络模型中节点的分布机制不同，连接的概率不同，导致 其形状不同，也会影响到组播网络的性能；组播组的数目对组播网络也有很大 影响，组播组越多，路由器所维持的状态数也就越多。在网络规划和设计阶段 综合考虑以上因素对组播网络性能的影响，。对构建组播网络有非常重要的意 义。n s 一2 0 1 是一个很好的网络仿真平台，通过仿真及数据分析，可以看出不同 因素对网络性能的影响。 在组播中，当数据发送给组播组成员时，组播分发树上的路由器必须为这 个组维持一个转发状态，随着组播网络中组数目的增加，路由器所维持的状态 数也将呈线性增加，当组播中组的数目非常多时，每个路由器需要更多的状态 来维持它们，从而增加了路由器的存储开销，降低了数据转发的速率聚合组 播技术通过使多个组播组在一个域内共享同一棵组播树，从而减少了组播网络 中组播分发树的数目，相应的转发状态的数目也将减少，组播网络性能大大提 高。 1 1 1 网络技术研究的方法 对网络研究主要有分析方法、实验方法、仿真方法。1 三种。 分析方法，就是对所研究的对象和所依存的网络系统进行初步分析， 根据一定的限定条件和合理假设，对所研究的对象和系统进行描述，抽象出研 究对象的数据分析模型，利用数学分析模型对问题进行分析求解。但分析方法 的有效性和精确性受假设限制很大，当一个系统很复杂时就无法用一些限制性 山东大学硕七学位论文 假设对系统进行详细描述。 实验方法，就是设计出研究所需要的合理硬件和软件配置环境，建立 测试床和实验室，在现实的网络上实现对网络协议、网络行为和网络性能的研 究。实验方法的局限性在于成本太高，重新配置或共享资源很困难，实验床的 规模很难做的很大，只能针对小型网络，不能实现网络中的多种通信流量和拓 扑结构的融合。 仿真方法，就是运用网络仿真软件，建立所研究的网络系统的模拟模 型，借助计算机技术和仿真软件运行这个模型，并分析运行的输出结果。相比 而言，仿真方法在很大程度上可以弥补分析方法和实验方法的不足，仿真方法 可以应用在网络协议研究、网络性能研究和网络设计等多个方面。 1 1 2 国内外研究现状 在国内，由于网络仿真技术起步较晚，加上n s 一2 内容庞杂，还必须掌握 其他很多必备的相关知识以及应用工具才能使用，所以在国内n s 一2 的使用者 不是很多。另一方面，国内的许多研究者利用n s 一2 进行组播网络模拟时，大 部分是手工指定网络拓扑结构，且规模较小，研究不同网络拓扑模型下组播网 络的性能不是很多，在系统研究组播网络性能影响因素方面也比较欠缺。 如何减少组播网络中转发状态，近年来国外的一些研究者提出了几种策略 来解决此问题，包括通过聚合转发状态来减少组播网络中的转发状态、在路由 器上完全消除组播状态，将复杂性移到端节点上以及聚合组播“1 等方法。与前 两种方法截然不同的是聚合组播方法使多个组播组共享一棵组播分发树( 这棵 树称为聚合组播树) ，通过这种方式网络中组播树的数目将大大减少，因此转 发状态也随之减少，核心路由器只需要维护每棵聚合树的状态，而不需要维护 针对每个组的不同树的状态。聚合组播问题已经被证明是n p 完全问题，因其 复杂性国内研究的并不是很广泛，一些研究者只是给出了聚合组播的思想，并 没有算法实现和具体的实验仿真。 1 2 课题的目的和意义及论文结构 1 2 1 课题的目的和意义 本论文对n s 一2 的构件库进行了详细介绍，阐述了其主要作用，并分析 一2 中的具体实现机制。 j ， i 山乐大学硕士学位论文 第2 章组播概述 2 1 组播技术的产生和优越性 随着网络技术的飞速发展，在i n t e r n e t 上产生了许多高带宽的多媒体运 用，例如网络视频会议、网络音频视频广播、多媒体远程教育、远程会诊等 业务。这些业务的出现带来了带宽的急剧消耗和网络拥塞等问题。为了缓解网 络瓶颈，人们提出了多种解决方案：增加网络带宽；运用q o s 机制，控制不同 业务的带宽使用；服务器的分散与集群，减轻主干网的瓶颈：采用i p 组播技 术等。在所有这些方案中，i p 组播以其“一点传送多点接收”，即使用户数量 成倍增加，主干网络带宽也不需要随之增加这一独特的优越性成为当前网络技 术中的研究热点。 组播允许一个或多个发送者发送同一数据包到多个接收者，这组接收者被 称为组播组( m u l t i c a s tg r o u p ) 。组播源把数据包发送到特定的组播组，但只 有属于该组播组的地址才能收到数据包。无论有多少个组播报文接收者，网络 中任何一条链路只传送单一的报文，因此在有多个接收者的应用中，组播技术 提高了数据传送效率，有效地节省了带宽，减少了主干网出现拥塞的概率。 图2 - l 单播消息与组播消息发送的比较 图2 - 1 显示了单播消息和组播消息发送的区别，从中很容易看出组播的优 t 山东大学硕士学位论文 越性。单播方式需要发送者为每个单播接收者分别建立不同的数据流，而且路 由器也必须为同一消息在同一链路上重复传送多个流。采用组播技术后，组播 路由协议为组播数据包建立树型路由，被传递的信息在尽可能远的分叉路口才 开始复制和分发，因此信息能够被准确高效地传送到每个需要它的用户 2 2 组播协议分类 组播涉及到的协议主要有组播组管理协议和组播路由协议。组播组管理协 议目前使用的是作为i p 组播基本信令协议的因特网组播管理协议i g m p ”“”， 它运行在主机和路由器之间，作用是使路由器了解网段上有没有组播组成员。 组播路由协议运行在组播路由器之间，作用是建立和维护组播路由，完成正确、 高效地转发组播数据包目前使用的组播路由协议主要有p i m s m ”町嗍、 p i m d m m ”1 、d v m r p m 玎、m s d p 等，单播路由协议b g p 经过组播扩展后也可以 在域问传递组播路由信息。 2 2 1 因特网组管理协议 因特网组管理协议i g m p 是主机可以使用的唯一协议，它定义了主机与路 由器之间组播成员关系的建立和维护机制，是整个i p 组播的基础。主机通过 i g m p 通知路由器有关组成员的信息，并使路由器能通过和自己直接相连的主 机来了解组内其他成员的情况如果一个网络中有一个用户通过i g m p 宣布加 入某组播组，则网络中的组播路由器就将发到该组播组的信息通过组播路由协 议进行传播，最终将该网络作为一个分枝加入组播树。当主机作为某个组的成 员开始收到信息后，路由器就会周期性地对该组进行查询检查组内的成员是否 还参与其中，只要还有一个主机仍在参与，路由器就继续接收数据。当网络中 的所有用户退出该组播组后，相关的分枝就从组播树中删掉。 2 2 2 组播路由协议 组播路由建立了一个从数据源端到多个接收端的无环数据传输路径。组播 路由协议的任务就是构建分发树结构。组播路由器能采用多种方法来建立数据 传输的路径，即分发树。 组播路由协议分为域内和域间两大类。域内组播路由目静已经相当成熟， 在众多的域内路由协议中，p i m d m ( 协议独立组播一密集模式) 和p i m s m ( 协 议独立组播一稀疏模式) 是目前应用最多的协议。域f b 】路由的首要问题是路由 山东大学硕士学位论文 信息如何在自治系统之日j 传递，由于不同的a s 可能属于不同的运营商，因此 除了距离信息外，域问路由信息必须包含运营商的策略，这与域内路由信息是 不同的。 1 域内组播路由协议 ( 1 ) p i m d m ( p r o t o c o l i 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 ) d m 密集模式组播路由协议是专门为具有大量组播组成员的组播设计的。 它假设网络中的每个子网都存在至少一个对组播源感兴趣的接收站点，因此组 播数据包被扩散到网络中的所有点。与此伴随着相关资源( 带宽和路由器c p u 等) 的消耗。为了减少这些宝贵网络资源的消耗，密集模式组播路由协议对没 有组播数据转发的分枝进行剪枝操作，只保留包含接收站点的分枝。为了使剪 掉的分枝中有组播数据转发需求的接收站点可以接收组播数据流，剪掉的分枝 可以周期性地恢复成转发状态。为了减少等待剪枝分枝恢复转发状态的延时时 间，密集模式组播路由协议使用嫁接机制主动恢复组播报文的转发，这种周期 性的扩散和剪枝现象是密集模式协议的特征。在密集模式下数据包的转发路径 是以源为根组播组成员为枝叶的一棵有源树。由于有源树使用的是从组播源到 接收者的最短路径，因此也称为最短路径树s p t ( s h o r t e s tp a t ht r e e ) 。 ( 2 ) p i m - s m ( p r o t o c o l i n d e p e n d e n tm u l t i c a s ts p a r s em o d e ) p i m s m 被设计成将组播树限制在需要收发的路由器上。p i 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 。r p 接收到数据分组后， 取出其中的组播数据然后通过共享树转发出去。当源节点的发送速率超过了某 个特定的阈值时，路由器将向源节点发送j o i n 消息并向r p 发送p r u n e 消息， 于是共享树中靠近叶子节点的路由器将自动切换到有源树路由状态，实现r p t 向s p t 的切换。同时，源节点将继续发送分组拷贝给r p ，以防止有些成员仍 然使用r p 共享树接收数据。 p i m s m 协议使用了一些软状态机制来周期性地更新系统状态，使之适应 网络拓扑的改变和组成员的改变。虽然p i m 依赖于单播路由表来适应网络拓扑 的改变，但它不依赖于构造这些路由表的特定单播路由协议 现域间组播路由信息的传递，必须对b g p 一4 进行改造。为了构造域间组播路由 树，除了要知道单播路由信息外，还要知道网络中哪些部分是支持组播的，即 组播的网络拓扑情况。 在r f c 2 8 5 8 中规定了对b g p 进行多协议扩展的方法，扩展后的b g p ( m b g p ， 也写作b g p 一4 + ) 不仅能携带i p v 4 单播路由信息，也能携带其它网络层协议( 如 组播、i p v 6 等) 的路由信息，携带组播路由信息只是其中一个扩展功能。 有了m b g p 以后，单播和组播路由信息可以通过同一个进程交换，但是存 放在不同的路由表中。由于m b g p 协议是b g p - 4 协议的一个增强版本，因此b g p - 4 协议支持的常见的测量方法都可以用到组播中。 2 3 组播报文的转发 单播中，由于数据包只被传到一个目的主机，因此路由器可以通过网络沿 着单一路径从源主机向目的主机发送数据包，目的主机的i p 地址出现在i p 数 据包的指定地址字段。沿途各个路由器根据数据包的目的地址做出单播转发。 但在组播中，源主机向i p 数据包目的地址段内的组播组地址所表示的任意主 机传送数据。和单播相反，组播路由器不能以数据包中的目的地址来决定转发， 而必须把将组播数据包转发到多个外部接口上以便能传送到所有接收站点 2 3 1 反向路径转发 反向路径转发r p f ( r e v e r s ep a t hf o r w a r d i n g ) 是大部分组播路由协议 进行组播转发的基础。组播路由器利用到达的组播数据包的源地址来查询单播 路由表或者独立的组播路由表以确定此数据包到达的入接口处于接收站点至 7 _ 山东丈学硕士学位论文 源地址的最短路径上，因为是从路由器向源节点检查，所以叫“反向”。当组 播数掘包到达路由器时，路由器对数据包进行r p f 检查，其主要机制如下： l 、路由器检查到达组播数据报的源地址，以确定此信息包经过的是什么 接口，这些接口是否在从源节点到此的路径上； 2 、如果数据包在可返回源的接口上到达，则r p f 检查通过，数据包则按 照组播转发项进行转发； 3 、r p f 检查未通过，数据包被丢弃。 m u l t i c a s tp a c k e tf r o m s o u r c e1 5 1 1 0 3 2 1 n e t w o r ki n t e r f a c e 斟 1 5 1 i o o 0 1 s 】 【9 8 1 4 3 o 2 4 s o 2 0 4 1 1 6 o 2 z e o 图2 2r p f 检查失败示意图 图2 2 给出了一个r p f 检查出错的例子，按照单播路由表，从源 1 5 1 1 0 3 2 l 来的数据包应该从接口s l 处进入，所以数据包将被丢弃。 2 3 2 组播转发暂存 从路由器来看，每一个最短路径树或者共享树均可以表示为组播转发暂存 项( 也称组播路有表项) ，它将一个输入接口和零个或多个输出接口进行了关 联。( 双向共享树不需要区分输入和输出接口，因为数据能沿着树上下传送) 。 对每一个输入组播数据包都进行r p f 检查会导致较大的路由器性能损失。因 此，当组播暂存建立的时候，通常由路由器决定r p f 接口，然后r p f 接口转 变为组播暂存项的输入接1 2 1 。如果砌f 检查使用的路由表发生变化，那么必 须重新计算r p f 接口，并且对组播转发暂存项进行更新。输出接口具体由使 用的组播路由协议确定。 2 4 组播的应用 由于i p 组播技术具有“一次发送，多点传输”、节约网络带宽、降低网 络负载等优点和特性，近年来组播技术在数掘分发、实事数据传输、网络游戏、 山东大学硕七学位论文 多媒体应用等方面得到了广泛应用。 擞据分发：数据分发是组播应用的一个主要领域，这项技术允许公司 每天夜里向他们的远程分公司发布最新的消息，比如价格和产品消息等，以便 在下一个营业日有最新的消息。 实时数据传输：利用组播技术向大量的目的主机组传送实时数据是i p 组播得到广泛应用的又一领域。最典型的例子是将股票信息实时发送到交易大 厅的工作站。 网络游戏：i p 组播可以用于有大量参与者的游戏中，参与的p c 机或工 作站只需要加入i p 组播组就可以参与游戏，通过不同的组播组可以将游戏参 与者分为不同的游戏空间。 多媒体应用：多媒体是i p 组播技术最重要的应用领域，主要包括多媒 体会议、多媒体教学和远程教学等。非典期间，全国召开的多媒体会议是i p 组播技术在多媒体领域的典型应用。 9 山东大学硕士学位论文 供函数产生新事件，指定事件发生的时间。 3 2 2n s - 2 的构件库 有了离散事件模拟引擎，原则上用户可以自己完成对所要研究的系统的建 模工作，编写各种事件的处理代码，然后利用这个离散事件模拟器来完成对这 个系统的模拟。然而，这样做不能发挥n s 一2 的优势，针对网络模拟，n s 已经 预先做了大量的模型化工作。n s - 2 对网络系统中一些通用的实体已经进行了 建模，例如链路、队列，分组，节点等，并用对象来实现了这些实体的特征和 功能，这就是n s 的构件库 ， n s - 2 的构件又可分为简单构件和复合构件两类“”m “。 1 、n s o b j e c t 是所有基本构件的父类，而它本身的父类是t c l o b j e c t 类。 这个类的对象有一个基本功能就是处理数据包( p a c k e t ) 。所有的基本构件又 可以分为两类，即分类器( c l a s s i f i e r ) 和连接器( c o n n e c t o r ) 。 ( 1 ) 分类器：c l a s s i f i e r 是n s 一2 基本构件的一个大类。它的基本派生 类有地址分类器( a d d r c l a s s i f i e r ) 、组播分类器( m c a s t c l a s s i f i e r ) 等。分 类器类对象的主要作用是当收到一个分组后，检查分组的某些域，然后寻找与 这个域的值相匹配的接收者。分类器的主要特点是基于分类器的基本构件具有 一个或多个可能的数据输出路径，属于交换( s w i t c h ) 设备。 ( 2 ) 连接器；c o n n e c t o r 是n s - 2 基本构件的另一个大类。它的基本派生 类包括队列( q u e u e ) 、延迟( d e l a y ) 、各种产生和处理数据包的代理( a g e n t ) 和对象的跟踪器( t r a c e ) 。连接器的特点是基于连接器的基本构件只有一个可 能的数据包输出的路径，即单进单出的管道，这一点和分类器有一个或多个可 能的数据包输出路径( s w i t c h ) 是不同的。 2 、复合构件 n s 中常用的复合构件主要有n o d e 、l i n k 和a g e n t 等。 ( 1 ) n o d e 类 拓扑节点( n o d e ) 是由若干个分类器( c l a s s i f i e r ) 组成的一个复合对象 路由、传输层、应用层的模型都以a g e n t 的形式存在，附着在节点上实现其功 能。网络节点的功能是分配数据包。 ( 2 ) l i n k 类 山东大学硕士学位论文 拓扑节点连接类( l i n k ) 是n s 一2 中另一个主要的复合构件对象。一个节 点和另一个节点之间的连接( s i m p l e l i n k ) 是单向的。一个拓扑结构中的两个 节点之间的双向连接( d u p l e x l i n k ) 由两条单向连接组成。一个数据包进入l i n k 后，首先到达l i n kh e a d ，送到由它指向的数据缓冲队列。在l i n k 中从数据缓 冲队列( q u e u e ) 中被弹出( d e q u e u e ) 的包被传递到延迟处理对象( d e l a y ) 中 进行延迟仿真。在l i n k 中从数掘缓冲队列( q u e u e ) 中丢弃( d r o p p e d ) 的包， 被送到废弃处理对象中释放掉。 ( 3 ) a g e n t 类 。 a g e n t 类代表了在网络层中数据包的产生和消失的端点。同时也是各层网 络中各种协议的实现实体，是n s 一2 中最重要的一个构件，可大致认为它是传 输层的仿真。 3 2 3 分裂对象模型 n s 一2 的构件库是两种面向对象的语言编写的：c + + 和0 t c l 。0 t c l 是m i t 开发的0 b j e c t t c i ，即t c l 的面向对象的扩展。t c l 是一种灵活的交互式的脚 本语言，0 t c l 则是在t c l 中加入了类、实例、继承等面向对象的概念。n s 中 的构件通常都作为一个c + + 类来实现，同时有一个0 t c l 类与之对应。用户通 过编写0 t c l 脚本来对这些对象进行配置、组合，描述模拟过程，最后调用n s 一2 完成模拟。事实上，n s - 2 对外的表现就是一个o t c l 解释器。和一般的o t c l 解释器的不同在于n s 中预先多定义了一些命令和面向网络模拟的类。 n s 一2 中的构件一般都是由相关联的两个类来实现的，一个在c + + 中，一个 在0 t e l 中，这种方式被称为分裂对象模型。构件的主要功能通常在c + + 中实 现，0 t c l 中的类则主要提供面向用户的接口。用户可以通过0 t c l 来访问对应 的c + + 对象的成员变量和函数。c + + 对象和0 t c l 对象之间是通过t c l c l 的机制 关联起来的。 使用分裂对象模型，一方面，c + + 是高效的编译执行语言，使用c + + 实现 功能的模拟，可以使模拟过程的执行获得更好的性能。另一方面，0 t c l 是解 释执行的，用0 t c l 进行模拟配置，可以不必重新编译的情况下随意修改模拟 参数和模拟过程，提高了模拟效率。同时，这种分裂对象模型增强了构件库的 可扩展性和可组合性，用户通常只需要编写0 t c l 脚本就可以把一些构件组合 c l a s s p i n f o ( j 相应部分；改动t c l l i b n s d e f a u l t t c l 文件，定义t c l 对象 的缺省值；改动t c l l i b n s p a c k e t t c l 文件，在该文件中为新的分组增加一 个入口；改动m a l e f i l e 文件，将掌0 文件加入到该文件n s 对象文件列表中。 4 、在n s 目录下运行m a k ed e p e n d 和m a k e ，重新编译n s ，生成新的n s 。 山东大学硕士学位论文 第4 章网络拓扑 4 1 网络拓扑分类 研究路由协议，对于大部分研究者来讲，直接在商业网络上进行路由测试 是基本做不到的，并且在某个网络上测试会将测试结果局限于该网络上。此外， 在特定的网络上表现良好的路由协议，当该网络的拓扑结构发生变化或移植到 其他不同的网络时，不一定能表现出同样的性能。因此，路由协议通常先在不 同网络模型上进行测试。 从表面上看，网络中各节点的分布似乎是均匀的，主机的接入和断开具有 很大的随机性，因而，网络整体的拓扑结构应当呈现均匀分布的特性，或者说 其节点的度( d e g r e e ) 是均匀分布的( 度指连到特定节点的链路数目) 但是 通过对大量的实际数据研究表明，实际网络的度分布呈幂律“7 儿” ( p o w e r l a w ) 分布特性，这说明了在网络中既有大量连接松散的节点，也存 在一些连接紧密的节点，而且各个标度的节点都广泛存在。 现在主流的网络拓扑模型主要有随机型、层次型和幂律型三类。 ( 1 ) 随机型，即认为网络拓扑图处于一个完全无序的状态，在大尺度上是 均一的。最早的随机模型是由w a x m a n 咖1 提出来的。w a x m a n 认为节点之间的连 接概率与其距离相关，服从泊松分布，距离越近，概率越大。 指数分布建模方法 z e g u r a 和c a l v e r t 等人恤1 提出了两种概率函数更简单的随机建模方法。一种 是指数分布建模方法。这种建模方法中边存在的概率随着两点间距离的增大呈指 数下降，其概率函数如下所示： = ! ! ! ：! ! p ( “，y ) = p e 。一4 “， ( 4 3 ) 局部分布建模方法 局部分布建模方法也是由z e g u r a 和c a l v e r t 等人提出。这种方法中按照边长 度的不同，将边离散地分类，并给每类边分配不同的存在概率值。用r 作为界限 将边分为两类的概率函数为： p ( u ，v ) = 经i i f f 怒( 4 - 4 ) 局部分布建模方法的一个优点是，对( 纯) 随机拓扑图进行数学解析得出的 结果在这种方法中能够得到很好的扩展。在给出控制拓扑生成的顶点的合理数量 时，任何有限数量的分类都是被允许的。 4 2 ，2 模型特点 纯随机建模方法与其它方法明显不同，它生成的拓扑图的直径比其它方法 生成的拓扑图的直径长得多。因为随机建模对所生成拓扑图中边的长度不够敏 感，所以它更可能生成长边和长路径。 指数分布建模方法生成长路径的可能性仅次于纯随机建模方法。虽然在指 数分布建模方法的边存在的概率函数中包含了长度因素，但是与其它方法相 比，随着边的长度的增加，边存在的概率减少得相对慢。 w a x m a n 建模方法和局部分布建模方法十分相似。尽管它们给出了不同魄 边存在的概率函数，但是它们生成的拓扑图的特性却是相似的，边长度的分配 也是相似的而b a 建模方法主要重在于描述拓扑形成的机理。 4 3 拓扑生成器 拓扑生成器是拓扑生成算法的软件实现，是生成拓扑的工具，其设计目标 可归纳为3 点：( 1 ) 代表性，即生成的拓扑图要能够准确反映实际网络拓扑的 各个方面；( 2 ) 包含性，即将许多生成模型合并在一起，提供一个通用的拓扑 生成工具；( 3 ) 兼容性，即为网络模拟应用程序( 如n s 一2 ) 以及可视化工具( 如 山东丈学硕士学位论文 c a i d a 的o t t e r ) 提供接口。为了实现这些目标，一个拓扑生成器主要包括3 个 功能模块：( 1 ) 格式转换：由于目前没有统一的拓扑数据文件格式标准，所以拓 扑生成器要具有在各种拓扑测量数据，拓扑生成器输入输出数据以及网络模拟 软件输入数据之间进行文件格式转换的功能。( 2 ) 拓扑生成：这是拓扑生成器 的核心，除了根据已有的拓扑生成算法实现幂律之外，还要依据其他度量来产 生拓扑图。( 3 ) 拓扑分析：根据拓扑生成模块中所采用的度量来对拓扑数据进 行统计分析，给出度量的值。目前常用的拓扑生成器主要有： b r i t e 。3 i ，其特点在于“通用”。首先，它实现了w a x m a n 模型和b a 算 法，并可以用自顶向下和自底向上两种方法来产生层次模型；其次，它为多个 网络模拟程序提供接口，包括n s - 2 、s s f 、o m n e t + + 、j s i m ，并支持可视化工 具o t t e r 。b r i t e 产生路由器层、a s 层以及分层结构拓扑图，并可为连接分配 带宽和延迟，具有图形用户接口。 i n e t “，i n e t 是密歇根大学于1 9 9 9 - 2 0 0 2 年间开发的一个a s 级拓扑产 生器，最新发布的是3 0 版本。其特点是利用r o u t e - v i e w s o r e g o n - i x n e t 上 从1 9 9 7 年1 1 月到2 0 0 2 年2 月间的大量b g p 数据来确定拓扑度量的值，可信 性很高。i n e t 采用p l g r 算法。”与优先附着实现幂律，重视连通性( 最小节点 覆盖) 。i n e t 使用简便，只需在命令行输入拓扑图节点总数即可。 n e m ( n e t w o r km a n i p u l a t o r ) 啪1 ，n e m 是法国u l p s 大学( u n i v e r s i t yo f l o u i sp a s t e u rs t r a s b o u r g ) 于2 0 6 2 年开发的，其特点是具有通用性，并对拓 扑图在最短路径长度和树结构方面的度量进行优化。n e m 将拓扑特征分为5 类： 树、距离、连通性、节点对、最短路径数以及类别( c l a s s ，包括叶上节点数， 环上节点数等) ，可对这5 类特征进行分析，同时n e m 为网络模拟软件n s 一2 、 g l o m o s i m 和o p n e t 提供借口，以批处理文本文件作为用户接口。 1 7 山东大学硕士学位论文 第5 章组播路由协议在n s 2 中的仿真及分析 5 1 组播路由协议原理 7 这里只阐述p i m d m 和p i m s m 两种域内组播路由协议的原理。 5 1 1p i m - d m 协议原理 p i m - d m 的工作过程可以概括为：邻居发现、扩散一剪枝过程和嫁接。 邻居发现 p i i d - d m 路由器刚开始启动时，需要使用h e l l o 报文来发现邻居。运行p i m d m 的各网络节点之间使用h e l l o 报文保持联系。p i i d - d m 的h e l l o 报文是周期性发送 的。 扩