（计算机应用技术专业论文）基于智能算法的qos约束组播路由算法研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 随着i n t e r n e t 的飞速发展，涌现出许多新型的通信需求，如视频点播、多媒体会议、 远程教学等。这类应用一般涉及多个用户，需要网络提供组播支持，并且高效的q o s 支持 变得越来越重要。而路由机制是实现q o s 保证的关键之一，因而成为研究热点。 q o s 组播路由问题的求解方法包括启发式算法和遗传算法，本文主要研究了遗传算法 在组播路由问题中的应用。遗传算法是一种全局寻优技术。适合于在复杂而庞大的搜索空 间中寻找最优解，它原理简单，易于并行，广泛用于许多n p 难度求解的领域。因此，遗 传算法为q o s 组播路由问题的求解提供了新的途径。传统的遗传算法具有容易陷入局部最 优解的缺点。这里提出一种改进的遗传算法，该算法对两个基本的遗传操作进行了改进， 使得算法能够尽可能全局搜索。 图论是研究网络理论的数学基础之一，图论的k 一最短路径算法是目前各种成熟路由技 术的基础。本文第四章回顾了图论的一些基本概念，介绍了几种相关算法，并提出了一种 计算k 一最短路径的新算法，跟传统算法比具有时间复杂度更低的优点。 针对多个q o s 约束( 包括时延、带宽、时延抖动、丢包率) 的组播路由问题，根据q o s 组播路由的特点，结合遗传算法的寻优特性，采用改进的混和遗传算法，能在较好的费用 性能和时间性能下获得满足约束的组播树。仿真实验表明，该混和算法性能稳定，具有较 快的收敛速度。 最后，对全文进行总结，并对下一步研究提出了展望。 关键词：组播路由，q o s ，遗传算法，s t e i n e r 树 南京邮电人学颂t ：t 口f 究生学位论文a b s t r a c t a b s t r a c t t h ed e v e l o p m e n to fi n t e m e th a sg i v e nr i s et oal o to f n e wc o m m u n i c a t i o ns e r v i c e ss u c ha s v i d e ob r o a d c a s t i n g , m u l t i m e d i ac o n f e r e n c e ，r e m o t ee d u c a t i o n i ng e n e r a l ，t h e s ea p p l i c a t i o n s r e q u i r et h en e t w o r kt op r o v i d em u l t i c a s ts u p p o r t ，a n de f f e c t i v ea n de f f i c i e n tq o s ( q u a l i t yo f s e r v i c e s ) s u p p o r th a sb e c o m i n gm o r ea n dm o r ei m p o r t a n t q o sm u l t i c a s tr o u t i n gi st h ek e y t e c h n o l o g yi nt h e s ea p p l i c a t i o n sa n db e c o m et h ef o c u so f r e s e a r c h t h ec u r r e n ta p p r o a c h e sf o rm u l t i c a s tr o u t i n gp r o b l e mi n c l u d eh e u r i s t i ca l g o r i t h m sa n d g e n e t i ca l g o r i t h m i nt h i st h e s i s ，t h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mi nt h eq o sm u l t i c a s t p r o b l e mi ss t u d i e d t h eg e n e t i ca l g o r i t t w ai sag l o b a lo p t i m i z a t i o nm e t h o dw h i c hc a np e r f o r m s e a r c hi nc o m p l e xa n dl a r g es p a c e d u et oi t sa d v a n t a g e so fs i m p l ei m p l e m e n t a t i o na n d p a r a l l e l i z a t i o n ，g e n e t i ca l g o r i t h mh a sb e e na p p l i e ds u c c e s s f u l l yi nm a n y f i e l d so f n pc o m p l e t e p r o b l e m s ，t h e r e f o r e ，g e n e t i ca l g o r i t h mp r o v i d e sa n e wd i r e c t i o nf o r t h eq o sm u l t i c a s tp r o b l e m h o w e v e rc o n v e n t i o n a lg e n e t i ca l g o r i t h mh a si t ss h o r t c o m i n g ：e a s yt ob et r a p p e di nl o c a lm i n i m a a ni m p r o v e dg e n e t i ca l g o r i t h mi sp r o p o s e dh e r e ，t h ek e yi st oi m p r o v et h em a i n l yt w ok i n d so f g e n e t i co p e r a t o r s ，n a m e l yc r o s s o v e ra n dm u t a t i o n ，w h i c hw i l lm a k e i t sb e s tt od oag l o b a l s c a r e h e s ， t h eg r a p ht h e o r yi so n eo f t h em a t h e m a t i c a lf o u n d a t i o n si ns t u d y i n gn e t w o r k t h ek - s h o r t e s tp a t hp r o b l e ma n dt h e i ra l g o r i t h m sa l et h eb a s eo f r o u t i n ga l g o r i t h m su s e dc o m m o n l y c h a p t e r4r e v i e w ss o m eb a s i ck n o w l e d g e o fg r a p ht h e o r y ，a n di n t r o d u c e ss o m ea l g o r i t h m st h a t a r er e l a t i v et oo u rw o r k a l s o ，w ep r o p o s e da na l g o r i t h mf o rt h ek s h o r t e s tp a t h ，w h i c hh a sl e s s t i m ec o m p l e x i t yc o m p a r ew i t ht h et r a d i t i o n a lo n e a c c o r d i n gt ot h ec h a r a c t e ro fq o sm u l t i c a s tr o u t i n ga n do p t i m i z ec h a r a c t e ro fg e n e t i c a l g o r i t h m an e wa p p r o a c hb a s e do nh y b r i dg e n e t i ca l g o r i t h mi sp r o p o s e dt o s o l v em u l t i q o s c o n s t r a i n e dm u l t i c a s tr o u t i n gp r o b l e m ，w h i c hc a ng e t al o wc o s tm u l t i c a s tt r e ew i t h o u t v i o l a t i n gt h eq o sc o n s t r a i n t ，s i m u l a t i o n ss h o wt h a tt h ea l g o r i t h mh a ss t a b l ep e r f o r m a n c ea n d f a s tc o n v e r g e n c es p e e d f i n a l l y ，t h ep a p e r i ss u m m a r i z e da n dt h ef u t u r er e s e a r c hw o r ki sp r o s p e c t e d k e yw o r d s ：m u l t i c a s tr o u t i n g ，q o s ，g e n e t i ca l g o r i t h m ，s t e i n e r t r e e 1 i 南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机应用技术 研究方向：计算机在遥信中的应用 作 者：三堕级研究生 田永辉 指导教师塑垡垂 题目： 基于智能算法的q o s 约束组播路由算法研究 英文题目：r e s e a r c h0 1 1q o sm u l t i c a s tr o u t i n gp r o b l e mb a s e do n i n t e l l i g e n ta l g o r i t h m 主题词：组播路由q o s k e y w o r d s ： m u l t i c a s tr o u t i n g s t e i n e rt r e e 遗传算法s t e i n e r 树 q o s g e n e t i ca l g o r i t h m 南京邮电大学学位论文独创性声明 y8 5 1 0 9 4 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：鳟日期：盟 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：衄导师签名：j 盐赶日期：二蛆 南京邮电大学颈士研究生学位论文 第一章绪论 第一章绪论 从上个世纪末到本世纪初是网络技术大发展的时代，特别是以因特网为代表的i p 网络 更是日新月异。因特网上的用户数量持续呈爆炸性增长，许多新型的通信业务大量涌现， 如电视会议、视频点播、邮件群发、网络游戏、远程教学等。这类业务一般涉及到多个用 户，并且对带宽等网络资源的消耗极大。组播作为优化带宽的一种重要手段而受到越来越 多的关注。 1 1 网络数据的三种传输方式 网络数据目前主要有三种传播方式，即单播、组播和广播。 单播( u n i c a s t ) 传输：在发送者和每一接收者之间实现点对点网络连接。如果一台发 送者同时给多个的接收者传输相同的数据，也必须相应的复制多份的相同数据包。如果有 大量主机希望获得数据包的同一份拷贝时，将导致发送者负担沉重、延迟长、网络拥塞： 为保证一定的服务质量需增加硬件和带宽。 组播( m u l t i c a s t ) 传输；在发送者和每一个接收者之间实现点对多网络连接，需要将 一份数据同时发送给多个用户。它提高了数据传送效率，减少了骨干网络出现拥塞的可能 性。具有带宽利用率高、减轻主机负担、避免目的地址不明确所引起的麻烦等优点。 广播( b r o a d c a s t ) 传输：是指在i p 子网内广播数据包，所有在子网内部的主机都将收 到这些数据包。广播意味着网络向子网每一个主机都投递一份数据包，而不管对方是否需 要。广播的使用范围非常小，只在本地予网内有效，因为路由器会封锁广播通信；同时广 播传输增加非接收者的开销，如判断是否为所需信息包所需的时间等。 1 2 组播技术 1 2 i 简介 组播技术可形象的描述如下：假设一个企业分布于各地的子公司之间需要通过 i n t e r n e t 进行实时的交换信息( 数据、声音、图象) ，他们的计算机可能不属于同一个物 理网络，甚至不属于同一自治系统，这种通信的特点是“多点式”的。子公司发出的数据 希望其他子公司都能收到，而总部发出的指示全体子公司都应当收到。这种多点通信方式 i 塑塞塑皇查兰堡圭竺塞生鲎垡丝苎 篁二! 堕篓 为组内广播，即组播技术( 多播技术) 。 组播首先要解决发送给谁的问题。按不同应用项目( 如体育、文艺、娱乐、学习等) 进行分组，组成员要通过因特网组管理协议i g m p 向组播路由器进行注册登记，用户主机 发出请示，提出具体组播地址。为发送一份i p 组播数据包，发送者要确定一个合适的组 播地址，这个地址代表一个组。然后，组播数据通过普通的i p 发送操作发送出去。 其次要解决的问题是如何接收组播信息。为了能够正确地接收感兴趣的组播信息数据 包，主机上的应用首先要根据组播路由协议申请特定组播组的成员。路由器把由发送方送 来的组播数据包一跳一跳地发送到有接收者的网段上的路由器，局域网路由器根据组播信 息包中的组地址转换出与它相关的数据链路层地址，并用这个地址建立数据链路层的报 文。接受方收到该组播包后，将i p 层的组播数据包取出，传向上层t c p i p 协议堆栈，从 而使数据适合用户的应用。 第三个问题是用户主机在注销对某个组的兴趣时如何通知组播路由器。如果接收方使 用的是i g m p v 2 ，会主动地通知路由器注销对该组的兴趣。但是接收组播的用户如果是 i g m p v l 主机，注销就不会通知路由器，这时服务器要在一定时间后向本网段发出查询，接 收主机的应答，若无用户应答，认为无接收者，不再向该网段上转发组播信息。 第四个问题是组播信息的转发，要根据所使用的组播路由协议建立组播转发树。根据 该转发树进行组播信息的转发，当某个处于转发树中的路由器收到一个组播信息后，对要 转发的组搔包进行拷贝和转发。如果路由器为最后一跳，组播包就以广播的方式传送到该 网段中各主机接收者。 1 2 2i p 组播的优点 体现在以下几个方面： 1 、带宽 对于音频与视频网来说，大量的用户经常要在大致相同的时间里访问相同的信息，如 果使用单播。网络带宽的消耗就会呈线性增长。由于典型的m p e g 一2 视频信息流需要大约 1 m b p s 5 m b p s 的带宽用于流畅且逼真的影像，显然用组播来发送节目是一种明智的选 择。因为重复数据流被单一传送所替代，从而使得网络带宽得到了更有效地使用。 2 、服务器负载 如果音频与视频网的网络运营商继续使用单播传送机制，随着用户的增长，它将需要 不断增加它的实时音频服务器的能力和数量以满足连接用户的增长。当服务器负载增加到 2 妻塞些皂：；苎兰堡主婴塞圭堂些丝苎 苎= 苎笪堡 一定程度，服务器就不能再发出信息流。如果运营商使用组播来发布它们的节目，那么就 不需要购买越来越多高性能的服务器以满足客户数目的增长。很明显组播提供的主要优势 在于通过大大减少需要转发和处理的数据量，从而降低了所需服务器性能。 3 、分布式应用 在单播的情况下，随着需求与应用的增长，多点应用不太可能，因为单播通信中的客 户数量不能无限增长。而组播几乎不受客户数量增长的限制。 1 3 组播路由协议 要确定组播路由，首先要收集网络中的相关状态信息。路由算法就是在这些信息的基 础上确定路由的。网络的状态信息包括：网络的拓扑结构、链路和路由器的负载情况、链 路和路由器的有效与失效情况等。这些信息的收集是由路由协议( r o u t i n gp r o t o c 0 1 ) 来完 成的 i ，2 。 根据网络中组播组成员的分布，i p 组播路由协议可分为密集模式组播路由协议和稀疏 模式组播路由协议两种基本类型 3 ，4 ，5 ，6 3 。密集模式组播路由协议假设组播组成员密集 地分布在网络中，也就是说，具有组播组用户的子网数量在子网总数中占很高的比例。它 依赖于广播技术将数据“推”向网络中所有的路由器。密集模式路由协议包括：d v m r p 、 m o s p f 、p i t 卜d m 。 稀疏模式组播路由协议则假设组播组成员在网络中是稀疏分散的，且网络不能提供足 够的带宽。在这种情况下，广播就会浪费很多不必要的网络带宽从而可能导致严重的网络 性能问题。因此，必须依靠具有路由选择能力的技术来建立和维护组播树。稀疏模式的路 由协议主要有：c b t 、p i m s m 。 1 3 1 密集模式的组播路由协议 1 组播开放式最短路优先协议( m o s p f m u l t i c a s to p e ns h o r t e s tp a t hf i r s t ) m o s p f 是利用点到点的链路状态数据库，以o s p fv 2 为基础的组播路由协议。由于o s p f 采用d i j k s t r a s 算法进行路由选择，因此每个节点都要保持全网的拓扑信息，所有节点对 网络的看法是一致的。由于每个路由器都清楚整个网络的拓扑结构且周期性地共享链路状 态信息，所以它们就能独立地计算出相同的最小费用组播树。为减少计算量m o s p f 可以按 需执行算法，即路由器只需在它接收到第一个组播数据包时再进行扩展树的计算，一旦这 个扩展树被计算出来，其信息就被存储下来用于后继数据包的路由。因此，m o s p f 会对第 壹塞塑皇查堂堡主壁塞竺堂垡堡苎曼= 量些望 一个分组带来较大的延时。 m o s p f 是享有o s p f 对网络拓扑的变动的快速反应能力，然而这个能力是以对路由器c p u 资源的巨大消耗为代价的。随着网络中组播组数量的不断增加，这种消耗也在迅速增加。 2 距离矢量组播路由协议( d v m r p d i s t a n c ev e c t o rm u l t i c a s tr o u t i n gp r o t o c 0 1 ) d v m r p 是第一个支持组播功能的路由协议，它已被广泛应用在具有组播能力的骨干网 ( m b o n e ) 上。d v m r p 属于数据驱动型协议，以“跳数”为量度为每个组播组构建不同的组播 树，每个组播树都是以源节点为根目的节点为叶的最小扩展树，即这个扩展树在源节点与 每个目的节点之间提供一条跳数最少的路径。当源节点向组播组发送消息时，d v m r p 使用 “广播与修剪”技术根据请求建立并维护组播树。由于组播组成员可以在任意时刻加入， 并且这些新成员可能并不在已有的组播树上，因此，d v m r p 会周期性的重建组播树。 3 独立组播密集模式协议( p i m d m ) p i m d m ：协议无关组播协议一密集模式( p r o t o c a li n d e p e n d e n tm u l t i c a s td e n s e - m o d e ) 。它不需要单独的组播协议，利用路由器上单播路由协议的路由表作反向路径转发 检查，由此获得组播分布树。相比另两种协议，p i m - d m 的开销小得多，它用于组播源和目 的非常靠近、接收者数量大于发送者数量并且组播流量比较大得环境中效果很好。 1 3 2 稀疏模式的组播路由协议 i 基于核心树的组播协议( c b t ) c b t 是双向共享树。即发送者可通过树中任一节点向组播树发送数据，组播树中节点 将收到的组播数据报向除此之外的每个相邻节点传送。因此，节点必须为c b t 协议建立双 向转发状态。c b t 能够极大地减少路由器中的组播状态信息，且由于每一个节点都可以直 接转发组播数据报，因而会有较短的平均传送时延和较少的传送开销，并且核不会成为数 据传送的瓶颈。但c b t 却无法有效地解决对发送源的接纳控制问题。 2 协议无关组播协议一稀疏模式( p i m s m ) 工作原理与p i m d m 类似，但专门针对稀疏环境变化。适用于组播组中接收者少、间歇 性组播流量得情况。不同的是它定义了一个集合点( r p ) ，所有接收者在r p 注册，组播分组 由r p 转发给接收者。 1 4 组播路由算法 组播路由算法就是用来确定组播树。组播树是通过在每个路由器设置路由表建立的， 4 堕塞墅皇查兰矍主堕墨兰竺堡竺奎 苎二童箜堡 路由表上给出了为使信息传送到组成员，此路由器应选择哪个邻接节点。一般用树的“费 用”来衡量组播树的好坏，组播树的费用是指树中所有链路费用的总和 7 。 组播分布树有三种基本类型：泛洪法、有源树、共享树( 有核树署1 s t e i n e r 树) 。 1 4 1 泛洪法( f l o o d i n g ) 这是最简单的向前传送组播路由算法，并不构造所谓的分布树。其基本原理如下：当 组播路由器收到发往某个组播地址的数据包后，首先判断是否是首次收到该数据包，如果 是首次收到，那么将其转发到所有接口上，以确保其最终能到达所有接收者；如果不是首 次收到，则抛弃该数据包。 泛洪法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数据包列表， 但无需维护路由表。它适合于对组播需求比较高的场合，并且能做到即使传输出现错误， 只要还存在一条到接收者的链路则所有接收者都能接收到组播数据包。然而，泛洪法不适 合用于i n t e r n e t ，因为它不考虑链路状态，并产生大量的拷贝数据包。此外，对于高速 网络而言，“首次收到”列表将会很长，占用相当大的内存；尽管它能保证不对相同的数 据包进行二次转发，但不能保证对相同数据包只接收一次。 1 4 2 有源树 有源树也称为基于信源的树或最短路径树( s h o r t e s tp a t ht r e e ，s p t ) 。它是以组 播源为根构造的从根到所有接收者路径都最短的分布树。如果组中有多个组播源，则必须 为每个组播源构造一棵组播树。由于不同组播源发出的数据包被分散到各自分离的组播树 上，因此采用s p t 有利于网络中数据流量的均衡。同时，因为从组播源到每个接收者的 路径最短，所以端到端( e n d t o e n d ) 的时延性能较好，有利于流量大、时延性能要求较 高的实时媒体应用。s p t 的缺点是：要为每个组播源构造各自的分布树，这样的话，当数 据流量不大时，构造s p t 的开销相对较大。 1 4 3 共享树 共享树也称r p 树( r p t ) ，是指为每个组播选定一个共用根( 汇合点r p 或核心) ，以 r p 为根建立的组播树。同一组播组的组播源将所要组播的数据单播到r p ，再由r p 向其它成 员转发。最具代表性的两种共享树是s t e i n e r 树和有核树( c b t ) 。 壹塞墅皇查兰堡主塑塞生兰垡兰兰 墨= 兰丝兰 s t e i n e r 树是总代价最小的分布树，它使连接特定图( g r a p h ) 中特定组的成员所需 的链路数目最少。若考虑资源总量被大量的组使用的情况，那么使用资源较少最终就会减 少产生拥塞的风险。s t e i n e r 树相当不稳定，树的形状随组中成员关系的改变而改变，且 对大型网络缺少通用的解决方案。所以s t e i n e r 树只是一种理论模型，而非实用工具。 目前，出现了许多s t e i n e r 树的次优启发式生成算法 8 ：包括距离网络法( d n h ) ( 即 k m b 9 ) 、最短路径法( m p h ) 、平均距离法( a d h ) 。 有核树是由根到所有组成员的最短路径合并而成的树。a b a l l a r d i e 在1 9 9 7 年9 月 的基于核的组播路由体系结构 1 0 ，1 1 中介绍了有核树。 共享树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好的 性能。当组的规模较大，而每个成员的数据发送效率较低时，使用共享树比较合适。但当 通信量大时，使用共享树将导致流量集中及根( r p ) 附近的瓶颈。 1 5 本文的内容概要 本文主要研究一种改进的遗传算法以及遗传算法在q o s 组播路由问题中的应用，首先 对计算机网络的组播通信进行了综述，主要介绍组播的特点、组播技术，还叙述了组播路 由协议以及组播路由算法。 第二章介绍组播树的理论基础和一些相应算法，并提出q o s 组播的数学模型。 第三章重点介绍了遗传算法的基本原理和步骤，然后提出一种改进的遗传算法，并对 改进后的算法进行了详细分析和仿真验证。 第四章介绍了图论中k 一最短路径的计算方法，并详细描述了基于d i j k s t r a 的传统 k - s h o r t e s t 算法，然后提出一种更有效的计算方法，对该算法进行仿真分析。 第五章提出一种能用于解决q o s 组播路由问题的混和遗传算法，详细介绍了其求解步 骤，并进行仿真实验，和其他常用的组播路由算法进行了比较。 最后总结了全文，并对下一步研究提出展望。 南京邮电大学硕士研究生学位论文第二章组播树理论基础和基本算法 第二章组播树理论基础和基本算法 上一章讲到，对于组播路由问题，一般要建立费用最小的组播树，即求解最优s t e i n e r 树。为此本章介绍有关s t e i n e r 树问题的理论，其中包括求解s t e i n e r 树问题的启发式算法； 算法的复杂度、性能。然后介绍q o s 组播相关概念，以及q o s 组播的数学模型。 2 。1s t e i n e r 树的定义 建立最优s t e i n e r 树被认为是实现组播通信的最好办法之一，s t e i n e r 树理论及其算法 也成为求解组播树的基础。s t e i n e r 树问题的应用不仅在通信方面，在电路图的自动布线、 交通线路的经济规划、车辆的调度和编组、通信线路的铺设等方面都有应用。s t e i n e r 树 问题有很多种类型，如嗣格( g r i d ) 上的s t e i n e r 树问题、e u c l i d e a n 平面上的s t e i n e r 树问 题、一般连通图中的s t e i n e r 树问题等。下面首先给出无向带权连通图上s t e j n e r 树问题的 定义。 首先将计算机网络抽象为无向连通图g = f v ，e ) ，其中v 为网络节点( 路由器) 的集合， e 为边( 通信链路) 的集合，在每条边e e 上定义一个权值函数c ( e ) ：e r + ，表示每条边的费 用，给定一个节点子集q e v ，这里q 对应为组播组成员，s t e i n e r 树问题就是要寻找一棵 覆盖给定节点集合q 且费用最小的最优s t e i n e r 树。 从最优s t e i n e r 树的定义可知，最优s t e i n e r 树中的叶子节点都应是q 中的节点，一般 称0 中的节点为基本节点：最优s t e i n e r 树中除基本节点外的其它节点被称为s t e i n e r 节点， 圈g 中所有可能成为s t e i n e r 节点的节点集合记为s ，易知q n s = m v = q u s 。 最小生成树和最短路问题都是s t e i n e r 树问题的特例。当q = v 时，s t e i n e r 树问题就 转化为最小生成树问题，当给定节点集合中只包含两个节点时，即l q l = 2 时，就变为最短路 问题。最小生成树问题和最短路问题都存在多项式时间的最优解法，但目前s t e i n e r 树问 题不存在多项式时间的最优解法，它是一个n p 完全问题。一个合理的目标是寻找该问题的 一个启发式算法，使我们能在一个低阶多项式时间内得到一个“接近”最优的解，为此对 s t e i n e r 树问题一般讨论解决它的启发式算法。启发式算法并不保证给出最优解，那么如 何评价启发式算法的好坏呢? 主要是基于两个方面的考虑：首先是时间复杂性方面的要 求，即要求有一个多项式时间界；其次是性能方面的要求，即希望所求的近似解尽可能“接 近”最优解。可以从不同角度来评价启发式算法的性能，大体上可分为三类：第一类是以 堕塞! ! ! ! ! 生叁堂堡主堑塞生堂丝堡塞 塑三童里塑塑里堡萎璺! ! 塑茎奎簦垄 算法在最坏情况下的行为为标准，研究算法得到的近似解与最优解的接近程度，越接近越 好：第二类是以算法的平均行为为标准，研究得到最优解的概率：第三类是局部搜索算法， 寻找局部最优解，这种方法有时很好，有时很差，只能通过实践加以评定。对于算法最坏 情况下的性能比，可以从理论上给出一个上界，但最坏情况下的性能不能说明算法的实际 性能如何，因为在实际应用中，算法体现出来的是平均性能，最坏情况很少发生，而算法 的平均性能是较难从理论上给出的，为此要通过仿真实验来研究算法的平均性能。 2 2 组播树启发算法 2 2 1 无约束最短路径算法 所谓最短路径算法以分别最小化连接源节点和组成员的各条路径的长度为目标。最短 路径树( s p t ) 的性质根据衡量链路的标准不问，分别以下几种： 1 最小跳数( m i n i m u m - h o p ) 树，每条链路都设为单位长度。 2 最短路径费用( l c ：l e a s t c o s t ) 树，长度设为该链路费用，此时最短路径算法& f l l c 算法，其目标函数可用下式表示。 m i n ( c o st ( p r ( j ，g ) ) ) v g q 这里，t 是一棵根为信源节点s 并且覆盖组成员集合q 的树，其总费用不一定是最优的。 3 最短路径费用( l d ：l e a s t d e l a y ) 树，目标函数如下式。 m i n ( d e l a y ( 耳( j ，g ) ) ) v g q 其参数意义同l c ，只是链路代价变成了时延( d e l a y ) 。 b e l l m a n - f o r d 算法 1 2 、d i j k s t r a 算法 1 3 是两个最著名的最短路径算法，这两种算 法都可以在多项式时间内收敛。b e l l m a n f o r d 算法的最差时间复杂度为o ( i v l3 ) ，这m l v l m 的是网络节点的总数。文献 1 4 给出了分布式b e l l m a n - f o r d 算法。它的计算仅需要保留 在各个网络节点中有限的网络信息即可。但a w e r b u e h 等人 1 5 证明了在最坏情况下分布式 b e l l m a n f o r d 算法的计算复杂度有可能随网络节点数的增加而呈指数级增长，因此提出了 该算法的两种不同的分布式版本，有效的解决了计算复杂度过大的问题。d i j k s t r a 最短路 径算法没有分布式计算的版本，它的最坏时间复杂度为o ( i v l 2 ) 。文献 1 6 给出两种算法运 行时间的比较。这两种算法都能很好的运行在非对称网络上。 另一种最短路径算法是由d a l a l 和m e t c a l f e 1 7 提出的反向路径算法( r p f ：t h e r 卫蔓型皇盔堂堡主婴塑兰竺些堕苎 篁三兰里塑塑翌堡苎塾塑苎查笺鎏 r e v e r s ep a t hf o r w a r d i n g ) 。它首先由源节点向整个网络发出广播信息，当其它节点收到 该信息后，则建立反向最短路径，源节点的信息就沿该反向路径发往各网络节点。r p f 只 能运行在对称网络上。d e e r i n g 1 8 ，1 9 将r p f 应用于广播及组播问题提出了t r p b ( t h e t r u n c a t e dr e v e r s ep a t hb r o a d c a s t i n g ) 算法和r p m ( t h er e v e r s ep a t hm u l t i c a s t i n g ) 算法。 2 2 2 无约束最小生成树算法 其目标函数如下： m i n ( e o s t ( t ( s ，q ) ) ) t ( s ，q ) 表示覆盖源节点和组成员的一棵生成树。该问题是n p 完全问题 2 0 ，无约束s t e i n e r 算法并不能优化端到端时延，因此也许并不适合实时网络的应用。最著名的无约束最小 s t e i n e r 树算法有k m b 算法 9 ，t m 启发式算法 2 1 ，以及r s 启发式算法 2 2 。 l ( m b 算法在计算过程中使用了p r i m 算法。蹴b 算法的最坏时间复杂度为o ( 1 q l l v l 2 ) ，在文 献 2 3 中，w a l l 提出了k m b 算法的分布式计算的版本。由k m b 算法在对称网络上得到的组播 树的费用一般只比最优s t e i n e r 树 2 4 要高5 。 t m 算法构建组播树时，一开始令树中只包含源节点，然后逐次加入组成员节点。每次 将形成的组播树与树外的一个组成员节点通过树与该节点之间的l c 路径相连，直到所有的 组成员都已经包含在树中才结束算法。t m 算法的最坏时间复杂度为o ( i o l l v l2 ) 。 r s 算法以包含不同组成员的森林开始，逐个连接两棵距离最近的树，直到原来的森林 只剩下一棵树为止。r a y w a r d s m i t h 和c l a r e 通过仿真证明 2 5 ，r s 算法得到的组播树的费 用要比k m b 算法* n t m 算法更接近最优结果。然而，r s 算法开始也只是被设计用来解决无向 网络中的问题的，目前还没有将r s 算法实现与有向网络中的方法。 j i a n g 2 6 对k m b 算法和r s 算法提出了改进，改进后的算法比着原始算法得到的组播树 的代价要小了很多，随后j i a n g 又提出了改进后算法的分布式版本 2 7 。 最近，r a m a n a t h a n 2 8 又提出了一种解决不对称网络的最优s t e i n e r 树的启发式算法。 相较前几种算法，该算法更为灵活，它通过一个可选参数k 来平衡算法的执行时间和树代 价，作者显示t d i j k s t r a 最短路径算法，l i m b 算法，t m 算法分别是参数k 等于1 ，( i g + 1 ) 和 l v i 的情况。 其它的启发式算法参见c h o w 2 9 ，l e u n g 和y u m 3 0 ，b a u e r 和v a r m a l 3 1 。 q 南京1 f i l i i uj ( 学颂i 研究生学位论文 第= 章组插树理跑然础和基本算法 2 3q o s 的相关概念 2 3 1q o s 的应用需求 随着高速网络技术和多媒体技术的飞速发展，人们越来越多地提出了包括多媒体通信 在内的综合服务要求。传统的分组交换网络，如i n t e r n e t ，是面向非实时的数据通信( 如 f t p 和e m a i 。l 的传输) 而设计的，采用的t c p i p 协议主要是为了优化整个网络的数据吞吐 量并保证数据通信的可靠性。而当今分布式多媒体应用( 如视频会议、视频点播、i p 可视 电话、远程教育) 不仅包括文本数据信息，还包括语音、图形、图象、动画这些类型的多 媒体信息。分布式多媒体应用不但对网络有很高的带宽要求，而且要求信息传输的低延迟 和低抖动等。同时，这些应用都能够忍受一定程度的信息丢失和错误。 一些典型应用的q o s 需求如表2 3 卜1 所示。 表2 3 卜1 典型应用的q o s 需求 应用类型q o s 要求参数范围 f t p 带宽 0 2 l o m b p s t e l n e t 相应延迟 8 0 0 m s 带宽1 6 k b p s 端到端延迟 0 1 5 0 m s 电话 端到端延迟抖动 l m s 分组丢失率 1 0 。 带宽1 8 6 m b p s 端到端延迟 2 5 0 m s m p e g l 端到端延迟抖动 l m s 1 0 4 ( 末压缩视频) 分组丢失率 1 0 1 ( 压缩视频) i 曲表可见当今商速网络中的多媒体应用对网络提出了不同于数据应用的服务质量的要 求，需要提供端到端的q o s 控制和保证。 2 3 2 服务质量的基本概念 q o s 即服务质量( q u a l i t yo fs e r v i c e ) ，指发送和接收信息的用户之间以及用户与传 1 0 南京邮电大学硕士研宄生学位论文 第二章组播树理论基础和基本算法 输信息的服务网络之间关于信息传输的质量约定。q o s 包括用户需求和网络服务提供者的 行为两个方面。主要包括带宽、端到端延迟、分组丢失率、抖动、花费的代价等。 q o s 度量通常有三种，对于路径p = ( a ，b ，c ，f ，g ) ，用d ( a ，b ) 表示对应链路( a ，b ) 的度量，则可以分为以下三类； ( 1 ) 凸性q o s 度量 如果d ( a ，g ) = m i n d ( a ，b ) ，d ( b ，c ) ，d ( f ，g ) ) ，那么度量由传输通道中的瓶颈决定， 即此度量仅与路径上的某个瓶颈链路的q o s 度量有关，如剩余带宽、剩余缓存空间、链 路速率等。 ( 2 ) 加性q o s 度量 如果d ( a ，g ) = d ( a ，b ) + d ( b ，c ) + + d ( f ，g ) ，那么度量由传输通道中所有链路的特性菸同 决定，如时延、时延抖动、费用等。 ( 3 ) 乘性q o s 度量 如果d ( a ，g ) = d ( a ，b ) d ( b ，c ) d ( f ，g ) ，即度量为所有链路对应度量的乘积，如 可靠性等。如取d ( a ，b ) = h a d ( a ，b ) ，则乘性度量就转换为加性度量。 q o s 路由选择的任务就是要从源节点到目的节点找到一条具有足够资源的路径来满足 端到端服务质量，按照最近的研究热点来看，有关q o s 路由选择问题可以分为两类，即基 于源节点的路由选择和分布式路由选择，基于源节点的路由选择是指每个节点都具有全局 的网络状态信息，源节点利用这些信息进行计算并找出可行的路径，全局网络状态信息将 通过链路状态协议周期性的刷新；分布式路由选择是指每个节点只了解它的局部信息，并 通过在节点之间周期性的交换控制信息找到可行路径。基于源节点的路由选择存在以下几 个问题：( 1 ) 全局网络状态信息必须频繁地刷新，否则不能正确地反映网络的变化，因此 需要大量的通信开销；( 2 ) 由于大量的通信开销和控制信息的传播时延问题，基于源节点 的路由选择方案只能提供近似的全局信息，全局信息的不准确性可能造成o o s 路由选择的 失败；( 3 ) 由于链路状态协议本身的局限性，因此任何一个单节点不可能接入所有节点和 链路的详细状态信息，尽管等级路由选择方案可以解决这个问题，但是状态信息的组合却 加重了信息的不准确性；( 4 ) 考虑n o o s 路由选择是基于每个连接的，所以当涉及多个限制 时，可自2 造成源节点的计算开销过大。 分布式路由选择可以把路径选择的计算开销分配给源节点到目的节点之间的所有中 间节点，因此，该方法可以缩短路由选择的响应时间。路由选择性能还依赖于状态信息的 准确性，因此，这和基于源的路由选择存在同样的问题。分布式多媒体应用通常有比较严 格q o s 需求，研究基于q o s 的路由选择机制既有理论意义也有应用意义。 1 1 堕型皇：茎兰堡主堑塑圭兰焦堡苎 墨三至丝垫丝墨丝墨! ! ! ! 塑苎查篓鲨 2 3 3q o s 组播路由问题的数学模型 设n ( v ，e ) 表示网络，其中v 表示网络节点集，e 表示双向链路集，s e v 为组播源节点， m v 一 毋 为组播终点集，r + 表示正实数集，胄+ 表示非负实数集，对于任一链路e e ，定义4 种度量 3 2 ： 延时函数：d e l a y ( e ) ：e _ r + ； 费用函数：c o s t ( e ) ：e 呻r ； 带宽函数：b a n d w i d t h ( e ) ：e - - r 。； 延时抖动函数：d e l a y j i t t e r ( e ) ：e - - r + ； 对于任一网络节点n e v ，也定义4 种度量： 延时函数：d e l a y ( n ) ：v 斗r ； 费用函数：c o s t ( n ) ：v j r ； 延时抖动函数：d e l a y j i t t e r ( n ) ：v r + ； 丢包率函数：p a c k e r _ _ l o s s ( n ) ：v 斗r + ； 则对于给定的源节点带宽函数：s v ；