（通信与信息系统专业论文）组播路由算法仿真平台设计.pdf

大连理工大学硕+ 学位论文 摘要 保证服务质量的q o s 组播路由( q u a l i t y o f s e r v i c e r o u t i n g ) 是网络中解决q o si 口- j 题 的一项关键技术，其主要日标是为多用户网络业务选择满足服务质量要求的传输路径， 同时保证整个网络资源的有效利用。在q o s 组播路由的研究过程中，需要进行严密的理 论分析和足够的实验验证，目前，这一过程中普遍存在以下两个主要问题：第一，难以 建立符合实际的仿真网络拓扑模型；第二，算法的优化目标多样，评估标准也往往不尽 相同，研究人员难以对算法进行客观的评价。 本文提出了一种改进的t r a n s i t s t u b 分层网络拓扑模型，该模型是t n t c m e t 路由级拓 扑模型，其产生的拓扑结构可直接应用于各种组播路由算法的仿真。拓扑的平均访问直 径分布特性更符合真实网络的特征度量，优于传统的w a x m a n 平面随机模型及原有的分 层模型。在此基础上，还建立了新的网络参数模型，该模型独立于各类网络算法，改进 了原有参数模型中单纯的链路加权特性，更适于网络q o s 机制的描述。 本文还提出了一种基于线性能量函数的缀播路由算法综合评价策略_ i e s m r ，该 策略通过线性能量函数将待评价组播算法的各项q o s 性能转化为单一度量值，通过考察 其偏离极跟最优能量值的偏差半径，将落点频度统计曲线作为算法综合性能的度量指 标。该评价策略能够同时对算法的多个优化目标进行均衡评价，提高了评价的客观性和 可信性。 以上述核心算法为基础，本文设计了一个q o s 组播路由算法集成仿真平台架构，并 实现了系统原型。该平台能够完成仿真环境生成、算法仿真、性能评价等多项功能，集 图形显示、数据分析于一体，可专用于q o s 组播路由算法的测试和性能分析。同时，平 台还提供标准的接口规范，所有符合规范的o o s 路由算法程序都可以集成到仿真平台进 行仿真实验。 关键词：0 0 $ 组播路由；分层网络拓扑：线性能量函数；算法评价；集成仿真平台 大连理工大学硕士学位论文 m u l t i c a s tr o u t i n ga l g o r i t h m s s i m u l a t i o np l a t f o r md e s i g n i n g a b s tr a c t q o sm u l t i c a s tr o u t i n gi so n eo ft h ek e yt e c h n o l o g i e st op r o v i d eq u a l i t yo fs e m i t ei n f u t u r en e t w o r k s t h eg o a l so fo o sm u l t i c a s tr o u t i n ga r et os e l e c tf e a s i b l ep a t h st h a tm e e t q o sc o n s t r a i n t sa n dt om a k ee f f i c i e n tu t i l i z a t i o no ft h en e t w o r kr e s o u r c ef o rm u l t i p l e u s e r s n e t w o r ka p p l i c a t i o n s i nt h er e s e a r c ho fq o sm u l t i c a s tr o u t i n g , s t r i c tt h e o r ya n a l y s i sa n d e n o u g he x p e r i m e n t sa r en e e d e d n o w a d a y s ，t w op r i m a r yp r o b l e m se x i s ti nt h er e s e a r c h p r o c e s s ：f i r s t ，i t sh a r dt ob u i l dt o p o l o g ym o d e l sr e f l e c t i n gt h er e a ln e t w o r k s p r o p e r t i e s ； s e c o n d l y , t h e r ea r ed i v e r s i f i e so ft h eo p t i m i z i n ga i m sa n de v a l u a t i n gs t a n d a r d s ，w h i c hm a k ei t h a r df o rr e s c a r c h e mt ot h ea n a l y s i sa l g o r i t h m s p e r f o r m a n c ea c c u r a t e l y t h i sp a p e rp r o p o s e sa ni m p r o v e dt r a n s i t s t u bt o p o l o g ym o d e l i ti so nt h er o u t i n gl e v e l o ft h ei n t e r a c t ，s ot h a tt h et o p o l o g i e sc r e a t e dc o u l db ed i r e c t l ya p p l i e di nt h er o u t i n g a l g o r i t h m s s i m u l a t i o n t h ea v e r a g eo ft h ep a t hl e n g t hc h a r a c t e r i s t i co ft h i sm o d e li sm o r e a c c o r d i n gw i t ht h ei n t e r a c t ，b e t t e rt h a nt h et r a d i t i o n a lw a x m a nr a n d o mm o d e la n dt h e q u o n d a mh i e r a r c h i c a lm o d e l an e wn e t w o r kp a r a m e t e rm o d e lw h i c hi si n d e p e n d e n tf r o m n e t w o r ka l g o r i t h m si s g i v e nb a s e d o n t h a t ，i t o v e r c o m e st h es i m p l e l i n k w e i g h t e d d i s a d v a n t a g ea n dc o u l db em o r ea p p r o p r i a t et od e s c r i b et h en e t w o r kq o sm e c h a n i s m t h i sp a p e rs u g g e s t sa ne v a l u a t i o ns t r a t e g yo fm u l t i c a s tr o u t i n ga l g o r i t h m sb a s e do nt h e l i n e a re n e r g yf u n c t i o n i e s m r i tt r a n s f o r m sa l lt h eq o sp e r f o r m a n c ep a r a m e t e r si n t oo n e s i n 出e v a l u eu s i n gl i n e a r e n e r g yf u n c t i o n sa n dc a l c u l a t e st h eo f f s e t r a d i u sf r o mt h e u t m o s t b e s t s o l u t i o n ，t h e nm a k e st h ep o i n t o f - f a l lf r e q u e n c yc n t v ea st h ei n t e g r a t i v e m e a s l l r e m e n to fe v a l u a t i o n b ya p p r a i s i n gm u l t io p t i m i z i n ga i m so ft h ea l g o r i t h ma to n et i m e ， t h i ss t r a t e g yi n c r e a s e so b j e c t i v i t ya n dr e l i a b i l i t yo ft h ee v a l u a t i o n b a s e do nt h o s ea l g o r i t h m sa b o v e ，t h ep a p e rd e s i g n sas k e l e t o no fq o sm u l t i c a s tr o u t i n g a l g o r i t h mp l a t f o r ma n dr e a l i z e st h es y s t e mp r o t o c 0 1 t h i sp l a t f o r mc a na c c o m p l i s hs e v e r a l f u n c t i o n si n c l u d i n gs i m u l a t i n ge n v i r o n m e n t g e n e r a t i o n ，a l g o r i t h m s i m u l a f i o na n d p e r f o r m a n c ee v a l u a t i o n i ti n t e g r a t e st h eg r a p h i c sd i s p l a ya n dt h ed a t aa n a l y s i s ，c a nb e s p e c i a l l yu s e df o rr o u t i n ga l g o r i t h m s s i m u l a t i n ga n de v a l u a t i n g b e s i d e s ，t h ep l a t f o r m s u p p o r t ss t a n d a r di n t e r f a c e s ，a l lt h ea l g o r i t h m sw i t ht h ei n t e r f a c ec a nb ei n t e g r a t e di nf o r s i m u l a t i n ge x p e r i m e n t s k e yw o r d s ：q o sm u l t i c a s tr o u t i n g ；h i e r a r c h i c a ln e t w o r kt o p o l o g y ；l i n e a re n e r g y f u n c t i o n ；e v a l u a t i o n ；i n t e g r a t i v es i m u l a t i o np l a t f o r m i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕j j 、博上学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者虢陵2 垫盘 导师签名： 迎6 年一t _ _ l lj q 监日 大连理工大学硕士学位论文 1 绪论 1 1 引言 随着网络技术飞速发展，许多网络应用应运而生，如视频会议、v o d 点播、远程教 学、大规模协作计算、游戏和仿真、为用户群进行软件升级等，这些应用大都依赖于一 个主机向多个主机或者多个主机向多个主机发送同一信息的能力。 传统的点对点单播通信，在发送方和每个接受方之间需要单独的数据通道，当有多 个用户希望同时接受数据时，发送源就必须向每个希望接受数据包的用户发送一份单独 的数据报拷贝，这种巨大的冗余会带来很大的传输代价。首先，会加重数据源端的负担， 因为它必须对每个要求都作出响应，这使得主机负担过于沉重，响应时间大大延长；其 次，对路由器和交换机的性能也提出了更高的要求，管理人员被迫购买不必要的硬件和 带宽来保证一定的服务质量。而传统的广播通信在解决此类问题时，会将数据发送给一 个网段中的所有主机，这样会消耗所有主机上的资源，即数据要被网络中的大多数主机 所丢弃，而且，m 广播通信通常是被限制在本地的子网内的。 介于单播和广播之间的组播通信【1 - 2 】，能使主机发送的信息包传送到网络中任何一 组特定的主机上，这些主机都由一个特定的组播地址来标示，称之为口组播组地址。 支持组播的路由器会转发组播信息包至所有该组播地址的接口上。这样，重复的数据流 被单一传送所代替，从而使得网络带宽得到了更有效的利用，也大大减小了需要转发和 处理的数据量，降低了对网络服务器的性能要求。 此外，各种多媒体和实时业务对网络服务质量也提出了要求商业客户希望网络 始终提供有保证的服务；运营商渴望细分用户群，提供不同的服务，收取不同的费用。 现有的i n t e m e t 路由协议是基于尽力而为( b e s te f f o r t ) 服务的，对于所有业务请求都会 接受，并且只要具有相同的源地址和目的地址就会在同一路径上传输，这样极易导致流 量的不均匀和网络阻塞。 据此，i e t f 首先提出了服务质量保证q o s ( q u a l i t yo fs e r v i c e ) 的概念1 3 j ，其核心 思想就是针对不同客户或不同业务特性的要求，尽可能的提供好的服务质量。q o s 有多 种定义方法，其中包含了对不同方面服务质量的要求，如性能、可靠性、安全性等，所 有这些要求都对保证整个网络的服务质量至关重要。从性能的角度出发，网络的q o s 具有以下参数：带宽( b a n d w i d t h ) 、延时( d e l a y ) 、延时抖动( d e l a yj i l t e r ) 和丢包率 等。根据这些参数，我们就可以获知目前网络的状态，从而采取一系列的q o s 保证机制。 组播路由算法仿真平台设计 q o s 系统由多个子系统共同组成，由于网络的复杂性，只有将这些子系统协调运作 才能取得好的q o s 性能，提供良好的网络环境。这些子系统通常包括网络的业务接入控 制( a d m i s s i o nc o n t r 0 1 ) 、节点排队的调度控制( q u e u i n ga l g o r i t h m ) 门、缓冲区管理 ( b u f f e r m a n a g e m e n t ) 和路由选择( r o u t i n g a l g o r i t h m ) 1 8 - 9 1 等，其中，路由选择算法是至 关重要的环节，是决定网络传输性能的主要因素之一l 埘。 综上所述，基于q o s 约束的组播路由算法研究对网络理论和应用都有重大意义，是 该领域重要的研究内容之一。目前，q o s 约束组播路由算法研究存在以下几个亟待解决 的问题【1 1 j ： ( 1 ) 缺乏路由模型，理论研究困难。 由于网络拓扑和业务特性的复杂多样，算法数学描述困难，目前多数路由算法研究 主要是针对某个问题设计的启发式算法，而不是基于某种模型从理论上推导算法特性和 性能。这种情况下，为分折算法性能，需要大量仿真工作，由于缺乏理论支持，在不同 的拓扑结构和业务特性下，算法性能可能差异较大，仿真所得到的结果缺乏说服力。 ( 2 ) 优化目标不同，评估标准不一致。 目前主要的优化目标包括q o s 组播代价和延时等加性参数，评估标准主要有业务接 入率、阻塞率、数据丢包率、带宽利用率、节点队列长度、代价、信令开销等。由于研 究者试图解决的问题不同，优化目标不同，评估标准也往往不尽一致。这种情况不利于 比较不同算法的性能，因此，制定出统一的q o s 组播路由性能评估标准对路由算法研究 具有重要的意义。 ( 3 ) 接入业务的变化对网络状态影响大。 现有的q o s 路由算法依据用户业务对服务质量的要求进行寻路，一旦存在满足要求 的路径就会将业务接入，并没有考虑该业务的接入对网络状态有多大的影响。可以说目 前的q o s 路由大都是基于服务质量要求的尽力而为的路由，在这种情况下，如果业务特 性变化过快，网络状态急剧变化，网络效率、阻塞率等特性都会受到很大影响。在算法 设计过程中，搭建算法仿真环境可以适当的解决这一问题，通过观察网络接入性能的变 化，将其作为算法处理业务接入的一个参考。 以上问题的解决都对设计出高性能的路由算法，更好地满足业务对服务质量的要 求，提高网络资源利用率，实现用户级q o s 至关重要。 本章将从目前互联网的路由现状谈起，对组播路由及网络q o s 进行简单描述，指出 其研究过程中存在的难点，初步阐明q o s 组播路由算法仿真平台搭建的必要性及意义。 最后对论文的总体结构进行概述。 大连理工大学硕士学位论文 1 2 组播路由 随着多媒体业务不断普及，网络需要提供“点到多点”或“多点到多点”的通信方 式进行必要的支持，凭借较单播传输和广播传输更为高效的网络资源利用率，组播传输 技术应运而生。 1 2 1 工作原理 组播，也称多播、组内广播等，它允许一个或多个发送者发送单一的数据包到多个 接收者，只在分支点才进行包复制，只有属于该组播组的主机才能接收到数据包，因此 组播提高了数据传送效率，大大节省了网络带宽，从而减少了主干网出现拥塞的可能性。 d 类地址空间是专为职组播而设定的，组播地址分布在2 2 4 0 0 0 到 2 5 5 2 5 5 2 5 5 2 5 5 。该地址空间中的一部分被保留用于特殊功能，其余地址可在需要进行 组播传送时动态分配。 组播技术的核心是选路问题，即为每一个组播组建立组播树，设计或选取合适的组 播选路算法对组播选路的有效实施非常重要。迄今为止，路径的建立还在使用一些基本 的算法。其中d i j k s t r a 算法、b e l l m a n f o r d 算法、f l o y d 算法、动态规划方法是针对最 短路径问题提出的；贪心算法、p r i m 算法、破圈法、k r u s k a l 算法是基本的最小生成树 算法；f m s t 算法、k m b 算法是基于最小生成树算法，经剪枝生成s t e i n e r 树的启发式 算法；n a i v e 算法、s p h 算法、s f h z 算法、k - s p h 算法、a d h 算法是利用最短路径 算法生成s t e i n e r 树的启发式算法。目前还出现了智能计算，包括人工神经网络技术f 体”】、 遗传算法1 1 4 。1 5 】、群集智能技术【1 6 1 、模拟退火【1 7 1 等方法。 1 2 2 静态组播和动态组播 组播路由可根据不同的角度、不同的准则来分类，根据组播路由算法的基本特性， 可以分为静态和动态两类f l s l 。 所谓静态组播，是指在通信开始之前指定组播成员。在通信过程中成员是相对固定 的，不发生变化，直至整个组播通信进程被撤销，组播流不管有没有用户接收都沿已规 划好的组播路径传输。静态组播路由算法不能根据当前组成员的实际变化情况做出选 择，信息只能够按照设计好的路径传送，不适用于动态环境。 动态是由于节点在通信过程中加入或离开组播组引起的，动态算法要处理成员加入 和离开后组播树的更新问题。通常可以通过路由重组和路由部分重组解决，因为路由重 组会对原有成员的通信产生干扰，所以动态算法中一般采用部分路由重组【1 9 2 0 1 。 组播路由算法仿真平台设计 1 ，2 3 集中式与分布式 按是否由一个节点集中运算或多个节点分布式运算分为集中式和分布式算法。 在集中式路由选择中，每个节点都具有全局的网络状态信息，源节点利用这此信息 进行计算并找出可行的路径。全局网络状态信息必须根据链路状态信息的变化进行频繁 刷新，每个路由器都需要维护整个网络的状态信息，然后根据网络的状态信息独立地计 算可行路径，形成路由表，并在该路径上传输数据。集中式路由简单灵活，源端可以独 立选择路由算法计算组播路由，不需要多个节点协同进行路由选择，可以避免分布式路 由中的死锁和环路等现象。在基于集中式发送的策略中，更容易设计出可实现的复杂度 较低的寻路算法。其主要的问题是寻路开销大，状态信息准确性不高，网络扩展受限， 这些问题都与节点需要保留全网状态信息有关。 分布式路由每个路由器只需了解其相邻路由器的状况，如时延或费用等，然后将此 信息向邻近路由器发布，通过整个网络的分布式计算在所有路由器中将得到一个转发路 由表。r i p 路由协议采用的就是这种算法。分布式路由的主要问题是环路问题，网络中 各个节点保留的其他节点状态信息不一致或者节点路由信息不准确，都可能引起环路或 路由收敛时间长。分布式路由的是算法的执行只限于组成员节点，并不是所有网络节点 都参与路由算法，且每个节点只用到局部信息，不需要存在一个存储有整个网络信息的 中心节点，算法所需的通信费用小，是大型网络确定路由的一个好方法。 目前，研究较多的是静态组播源路由算法f 2 1 - 2 2 ，分布式组播路由算法陶和动态组播 路由算法【刎的研究成果较少。 1 3o o s 组播路由 i n t e r n e t 面临的主要压力之一是当前的i p 服务从本质上讲没有服务质量，只能提供 尽力而为服务，面临各种新兴业务，例如话音和视频，现有的口技术是力不从心的。 因此，i n t e r n e t 面临着改进服务质量( q o s ) 的挑战。服务质量q o s 的加入使得组播通 信问题变得更为复杂，不仅要考虑不同业务的q o s 参数，还要考虑到同时满足不同接收 者的需要，能够满足服务质量约束的组播路由算法成为实现组播的关键。 本节首先介绍了q o s 的有关概念及模型，然后对q o s 组播路由算法及其发展现状 作了简单阐述。 1 3 1o o s 定义 服务质量q o s 是网络传输业务流时，业务流对网络服务的需求集合，其中业务流是 指与特定q o s 相关的从源到目的地的分组流【矧，也就是说，o o s 是应用业务对网络传 输服务所提出的一组可度量的要求，网络传输相应的数据业务时，必须满足这组要求。 大连理工大学硕士学位论文 o s i 模型中定义了网络服务提供者为网络用户应用应提供基于如下四种参数的基本的 q o s 业务类型：带宽，时延，时延抖动和丢包率l 卅。 ( 1 ) 对于网络应用的带宽保证是指网络应有足够的传输容量满足业务的吞吐量需 求。 佗1 时延是指一个用户数据报从发送节点到接收节点所经历的时间。这包括数据报 在网络链路上的传输时延和数据报在网络各转发节点经历的处理与排队时延。音频视频 等网络应用对时延有较严格要求。如果数据报过迟到达，则它不荐有用而被丢弃。这既 降低了对网络应用的服务质量，也浪费了网络带宽。 ( 3 ) 时延抖动是指数据报到达接收节点时经历的不同时延值的差异大小，时延抖动 对于音频视频业务同样有较大的质量影响。 f 4 ) 丢包率是指数据报在网络传输中由于传输错误或网络拥塞( 传输时延过大) 而 引起丢弃的概率。丢包率对于音频视频实时业务和数据传输业务都会产生质量下降的影 响。网络传输层的重传机制可以掩盖丢包对数据传输业务的影响，但是检查这种丢包错 误并重新传输数据报对于音视频这样的实时业务是不现实的。 1 3 2q o s 组播路由的数学模型 就q o s 组播路由而言，网络通常表示成一个加权图g 一，e ) ，v 代表节点集合，e 代表连接节点的链路集合，每条链路的关联参数就是该链路的q o s 度量。已提出的q o s 约束可分为两类i 明，链路约束和树约束。其中链路约束包括带宽、链路上可利用的缓存 等，树约束包括从源到所有目的地间的端到端时延、目的地间的性能度量变化的约束( 如 时延抖动1 等。根据树约束从链路约束得出的方法，可进一步把树约束分为如下三类： 可加性度量、可乘性度量和最小性度量。对于图g 中的路径p t “，v 。，1 ，。) ，若链路 岛m e p ( 其中f = 1 ，2 ，s 一1 ) ，将乞州的第，个属性记为嵋+ l ，整个路径p 的第，个属 性记为w ：，则以上三类度量的定义如下： 定义1 ：若以- ：屹。，则称路径p 的第j 个属性为可加性度量。 可加性度量包括时延、时延抖动、代价、转发跳数等。例如，一条路径p 的时延为 从源到目的地的所有链路时延的总和。 定义2 ：若以一f i 暑以+ l ，则称路径p 的第，个属性为可乘性度量。 例如丢包率为可乘性度量，其中链路丢包率o s 以。主1 。 定义3 ：若w 二一m i n 。2 ，。吆+ 1 则称路径p 的第，个属性为最小性度量。 组播路由算法仿真平台设计 例如带宽为最小性度量，即路径带宽为路径上瓶颈链路的带宽。对于求解 嵋一m a x 。一。 嵋+ ， 的问题可转化为一以一r a i n 。加。 一吆+ 。，问题。 对于不同类型的q o s 度量，以及多个q o s 度量的组合，其计算的代价是不同的。 约束组播路由算法目标就是寻找约束s t e i n e r 树z ，丁的组成员节点是组播请求r 的成员 节点，且r 中所有目的节点满足各个约束，同时在所有可能的生成树中，r 的代价最小， 即考虑下述优化问题： m 抽艺恤，f c ，力 ( 1 1 ) 这个问题是n p 完全问题i 弼j ，一般要通过启发式算法求得近似最优解。 组播树r 的代价定义为组播树中所有链路的代价和，即： c o s f 仃) - 峨c o s f ( o ( 1 2 ) 组播树r 的时延定义为由源节点s 到各目的节点m 路径时延最大值，即： d e l a y ( t ) - m a x 2 , 。e ( , , , , , d e l a y ( e ) ( 1 3 ) 组播树的时延抖动定义为任意两条到达组播目的节点的路径的时延之差，即： d e l a y 一肺衙仃) 爿。( d e l a y ( e ) 一。) d e l a y ( e ) ，v u , v e m ( 1 4 ) m 为组播目的节点集合。 1 3 3o o s 组播路由算法 ( 1 ) q o s 组播源路由算法 s t e i n e r 树问题：s t e i n e r 树是以组播源节点为根形成的最小费用树，是一个n p 完全 问题，下面介绍一些典型的s t e i n e r 树算法。 k o u e t a l 算法【2 9 】由k o u ，m a r k o w s k i 和b e r m a a 为解决s t e i n e r 树问题提出，也称k m b 算法。k m b 首先要从原来的网络拓扑图中构造一个完全图，将组播成员间的最短费用 路径抽象为完全图的边，然后在完全图的基础上的计算最小生成树，最后将树中的各边 还原为最短路径，并删除操作中形成的环路，得到s t e i n e r 树问题的近似解。 t a k a h a s h i m a t s u y a m a 算法1 3 0 首先找出距组播源节点费用最小的组播目的节点，并 用最小费用路径连接该组播目的节点与源节点，然后通过增量的方法连接其余组播节点 ( 即连接离己选组播树最近的目的节点) 。重复上述过程，直至连接所有的组播目的节点。 约束s t e i n e r 树问题：约束s t e i n e r 树即时延约束费用最小组播树问题，它是一个n p 完全问题。针对该问题，目前己有多种启发式算法。 一6 一 大连理工大学硕士学位论文 k o m p e l l a e t a l 算法1 3 l 】由k o m p e l l a 等提出，也称k p p 算法。算法首先创建完全图， 完全图顶点表示源节点和目的节点，边表示满足时延约束费用最小的路径。当算法假定 链路时延度量为整数，时延边界总是有界的条件下，求解完全图能在多项式复杂度内完 成。随后在完全图内构造一个时延约束的生成树，用时延约束费用最小路径扩展而成， 并在扩展过程中删除算法形成的环路。 z h u e t a l 算法【3 2 j a pb s m a 算法，由q z h u 和m p a r s a 提出，解决时延约束树的优化 问题。b s m a 采用d i j k s t r a 算法求出源节点至目的节点的最小时延路径形成最小时延树 后，用费用更低的路径取代原路径。 s u n l a n g e n d o f f e r 算法f 3 3 】也称c d k s 算法，由q s u n 和l a n g e n d o f f e r 提出，算法首 先利用d i j l 【s t r a 算法找出最小费用树，然后检查最小费用路径是否满足时延条件，如不 满足，就用源点到各目的节点的最小时延路径来代替。后来作者提出了改进算法c k m b ， c k m b 采用与c d k s 类似的方法建立各组播源节点和目的节点的连接，然后采用与k p p 算法类似的方法构造完全图，求解时延约束下的最小生成树，最后扩展生成树。 ( 2 ) 分布式组播路由算法 k o m p e l l a 路由算法1 3 4 j 是由v p k o m p e l l a ，j c p a s q u a l e 和g c p o l y z o 提出的分布式 启发算法，用于构造受限s t e i n e r 树。算法要求网络中的每个节点要维护到其他节点的 最小时延距离向量。算法从源节点开始每次增加一条网络链路，重复进行这种操作直至 所有的目的节点都在生成树中为止。 c h e n n a h r s t e d t 算法【3 5 l 由c h e n 和n a h r s t e d t 提出，首先路由源节点以扩散形式从源 节点到目的节点发送探测控制报文，该报文仅沿着能够满足q o s 要求且同时至少能到达 一个目的节点的路径传送。在传送控制报文的同时，组播树以分布方式构造。每个网络 节点仅需维护本地状态信息。 1 40 0 s 组播路由算法仿真 随着o o s 组播路由成为网络领域研究的热点，大量q o s 约束组播路由算法被不断 提出。这些算法在应用之前除了需要经过严格的论证外，还需要通过足够的实验进行验 证，因此，算法的测试与评价已成为研究人员亟待解决的问题。 1 4 1q o s 组播仿真技术发展现状 目前，对路由算法的仿真还缺乏行之有效的方法。传统的理论计算及依据经验的评 断往往是不充分的，甚至是不科学的；而物理实验方式通过建造实际的路由环境加载算 法进行仿真，也存在较大的局限性： ( 1 ) 由于巨大的经费消耗，建立起来的实验环境通常范围较小，算法在其上运行有 组播路由算法仿真平台设计 失普遍性，不能进行充分的验证。 ( 2 ) 对于大多数处于理论设计阶段的路由算法，在实际的环境中难以进行配置，甚 至有些新的思想和方法在现实的网络环境下无法测试【3 6 1 。 ( 3 ) 通常情况下，这类实验方法的流程为：实际网络搭建一路由配置一结果收集， 测试仿真周期较长。 ( 4 ) 由于待评测算法的不完善，真实路由实验可能对现有网络产生破坏，不宜广泛 开展。l a b o v i t z 等人发现在一次i n t e m e t 域间路由错误后，需要几十分钟才能再次达到 路由一致性 3 7 1 。此外，测试过程受实际网络状况的影响很大，只能局限在特定条件下。 在这种情况下，通过仿真平台对算法进行仿真分析就成为一种有效的手段，已被广 大研究人员普遍采纳并用于评价新的网络路由算法。n o r o n h a 研究进一步证明：路由算 法在随机生成的网络拓扑下的仿真性能与其实际应用性能几乎相刚3 8 】；e s t r i n 也提出， 采用建立网络测试模拟系统的方法虽然会丢失一些细节信息，但其具备更好的灵活性和 共享性p 曰。 。 q o s 组播路由算法仿真属于网络仿真技术的一部分，这种技术采用数学建模和统计 分析来模拟网络行为，从而获取特定的网络特性参数。研究人员可以通过特定的网络仿 真技术，建立反映真实网络特征的网络模型，模拟网络中的传输过程，并在此过程中获 取网络全局性能统计量、网络节点性能统计量、网络链路的流量延迟等网络特性参数。 网络仿真技术具有以下显著特点： 首先，仿真不是基于数学计算，而是基于统计模型，脱离了理论验证的局限性，待 评测对象的性能可以通过统计的随机性较为精确的再现。 其次，网络仿真技术利用拓扑模型，能够迅速的建立起具有一定规模的虚拟仿真环 境，并能够方便的修改模型重复仿真过程，这种全新的模拟实验机制，使得网络仿真非 常适用于反映和预测算法在真实网络中的应用性能。 1 4 2 网络仿真平台 在国外，网络仿真技术的研究和应用已经有1 0 多年的历史，主要用于网络协议和 网络设备的开发和研究，使用者大都是大学和研究院的研究和开发人员，网络仿真平台 的操作也相当复杂，使用者一般需要半年以上时间的培训和熟悉才能够熟练掌握。 在我国，网络仿真研究从9 0 年代后期起步，1 9 9 7 年，c e r n e t 网络中心开始开发 自己的网络仿真软件；1 9 9 8 年，北京邮电大学、广东省邮电科学技术研究院、原电子部 电科院、邮电部规划设计院等单位先后引进了先进的o p n e t 网络仿真软件，开展网络 协议开发、网络规划设计应用等方面的研究工作。 大连理工大学硕士学位论文 路由仿真平台一般可分为通用网络仿真器和专用的路由仿真平台两种。通用的网络 仿真器不是为路由仿真专门设计的，但大都具有路由仿真的功能，如加州大学伯克利分 校开发的n s 2 1 3 9 】以及m i l 3 公司的o p n e 一删。 ( 1 ) 美国v cb e r k e l e yn s 一2 n s 2 是由v c b e r k e l e y 开发的免费的网络仿真工具，其源码开放，在学术领域得到 广泛应用。最初的n s l 0 版本是由l b n l 网络研究组开发的，现在为v i n t - r 程的一部 分。在v i n t 工程之下，n s 2 0 版本也已经发布。v i n t 工程的目标在于评价所有层次 的广域互联网的正确性和其他性能，从路由协议到会话协议。 n s 2 是面向对象的、离散事件驱动的网络模拟器，由c + + 语言和o t c l 语言编写而 成，可以仿真不同类型的包交换网络，模拟了w i r e d ，w i r e l e s s ，l a n ，s a t e l l i t e 等各种 口网络环境，实现了t c p ，u d p ，r t p 等网络协议，单播路由，组播路由和数据源发 生器以及f t p ，t d n e t ，w e b ，c b r 和v b r 等多种业务源。n s 2 已实现组播协议有 c e n t r a l i z e dm u l t i c a s t ( 类似于p i m s m ) ，d e n s em o d e ( d v m r p ，p l m d m ) ，s h a r e dt r e e m o d e ( 简化的稀疏模式) 和b i - d i r e c t i o n a ls h a r e dt r e en o d e 。 从用户的角度来看，n s 是一个面向对象的t c l ( o t c l ) 脚本解释器，它包括仿真事 件的发生调度器，网络元件对象库和为各种网络情景建立的模块库。用户首先应该编写 o t c l 脚本语言，生成一个事件调度，建立起网络拓扑结构，并且调用所需的功能块， 定义流量何时发生和停止，从而模拟整个网络事件的实现。 n s 2 的仿真引擎是可扩展的、可配置、可编程的。当前的事件是单一线程的，即 在任何一个给定时间只有一个事件可被执行。它既不支持事件的部分执行也不支持事件 的优先执行。每个节点在内存中维持一个到网络中其它节点的路由表。随着网络节点数 量的增加，内存的开销也增加，因此，在面对大规模仿真时，还存在内存限制的问题。 由于n s 2 企图包罗万象，因而该系统的设计复杂，想加入新的协议、算法或网络 拓扑并不是一件容易的事情，“+ 和o t c l 两种语言的设计思路也使得理解该系统变得 更加困难。 ( 美国m i l 3 公司的o p n e t o p n e t ( t h e o p t i m i z e d n e t w o r k e n g i n e e r i n g t o o l s ) 网络仿真软件是m i l 3 公司的产 品，m i l 3 公司是由m i t ( 麻省理工学院) 的几位教师在1 9 8 6 年创建的，他们把在m r r 的研究成果产品化，开发出了m i l 3 公司的第一个产品m o d e l e r ，并在随后将其扩充、 完善为o p n e t 产品系列。o p n e t 作为第一个商业性的网络仿真平台，其价格昂贵，近 两年被第三方权威机构( 如n e t w o r kw o r l d 等) 评选为“世界级网络仿真软件” 一9 组播路由算法仿真平台设计 第一名。目前，全球有1 4 0 0 多个组织使用该软件，主要是一些大型机构，如美国军方 和著名电信公司。 o p n e t 可模拟u n ，w a n ，i s d n 及卫星通讯网络，可以模拟拥有几百个节点的 网络，但计算需要大量时间。该软件由几个工具组成，被划分为m o d e l e rp l a n n e r ，m o d e l l i b r a r y 和a n a l y s i st o o l 这几部分。o p n e t 采用离散事件驱动的模拟机制，其中“事件” 是指网络状态的变化，只有在网络状态变化时，模拟机才工作，网络状态不发生变化的 时段不执行任何模拟计算。因此，与时间驱动相比，离散事件驱动的模拟计算效率得到 很大提高。 o p n e t 具有丰富的统计量收集和分析功能。它可以直接收集常用的各个网络层次 的性能参数，并有多种统计参数的采集和处理方法，还可以通过底层的网络模型编程， 收集特殊的网络参数。o p n e t 还提供友善的图形界面设计工具，使用者能很快地建立 起网络模型，设定探测点，执行模拟计算与分析模拟结果。 o p n e t 模型分为n e t w o r k 、n o d e 和p r o c e s s 三个层次。n e t w o r k 模型是最高层次的 模型，由网络节点( n o d e ) 和连接网络节点的通信链路( l i n k ) 组成，由该层模型可以 直接建立起仿真网络的拓扑结构。n o d e 模型是网络中的对象，定义了网络中的节点模 型并描述其各种行为，n o d e 模型由多个模块及这些模块间连接组成，这些模块一般代 表应用业务、协议层和物理资源，如缓冲区、端口和总线。每个模块对应一个或多个 p r o c e s s 进程模型。p r o c e s s 模型由有限状态机( f s m ) 来描述，支持规范、协议、应用、 算法以及排队策略，使用c c + + 语言及专门的协议程序设计库函数编程。o p n e t 用户 可以在上述三个层次的任何地方切入编程，建立所需的n e t w o r k ，n o d e 或p r o c e s s 模型。 o p n e t 提供了一个比较齐全的基本模型库( 包括网络设备和链路) ，主要包括： e t h e m e t ，f d d i ，t r t c p i p 肖删 f r p s t n c e l l u l a rp h o n e w i r e l e s sn e t w o r k c l i e n t s e r v e r 目前，o p n e t 可模拟的组播协议只有p i m s m ，而且在平台操作方面，没有核心的 技术细节文档。 上述这些软件功能强大，使用复杂，都为大型综合性网络仿真平台，需要专门进行 业务培训才能掌握。专用的路由仿真平台功能单纯，使用方便，但这类软件商用较少， 大连理工大学硕士学位论文 多为大学开发的实验平台，如m a r s 4 “，q r s l 4 2 1 ，e q r s 4 3 】和m c r s i m ! “l 等。其中m a r s 是美国m a y l a n d 大学计算机系开发的专用路由仿真平台，主要用于测试和比较路由算法 的性能和效率，只局限于仿真尽力而为传输的路由算法及协议，不能对o o s 路由算法进 行仿真；o r s 和e q r s 是芬兰赫尔辛基大学通信技术实验室在m a r s 的基础上，专门 针对i n t e m e t 上的q o s 路由协议而设计，但不能全面反映路由算法的各项性能。m c r s i m 是由北卡罗莱纳州大学高级计算通信中心的s a l a m a 等人开发的基于a t m 网络的q o s 组播路由仿真器，也是目前公认性能较好的组播路由仿真平台，但m c r s i m 主要仿真 组播路由算法在a t m 网络中的性能，不能直接反映