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

哈尔滨丁程大学硕十学位论文 摘要 在计算机网络中，多播是指从源节点将同一份信息传送到多个目的节点 的技术。多播路由是网络层具备的功能，多播问题的关键在于多播路径的确 定。实现多播的一般方式是建立多播树，多播树是根为源节点，且覆盖所有 多播成员的一棵生成树。多播树的优点在于，首先信息以并行方式发送到不 同的多播成员，从而降低了信息传递的时延；其次信息的复制只在树权上进 行，能够节省网络带宽资源，减少拥塞。多播路由算法主要用来建立一棵性 能好的多播树，并使得它满足各种业务的服务质量需求。 目前，多播路由算法的研究大多都针对无约束多播路由问题和时延受限 多播路由问题，多采用启发式等方法。本论文研究如何将遗传算法这一新型 优化算法应用到多约束q o s 多播路由算法中，利用该算法的并行搜索、种群 优化的特点，为解决q o s 多播路由问题寻找新的途径。 首先，对计算机网络的多播通信进行了综述。主要介绍多播的概念、分 类、基本特点与应用；研究了多播技术及应用、多播路由技术、多播路由协 议，还介绍了q o s 的基本概念。 其次，研究q o s 多播路由问题。主要介绍了q o s 多播路由的基本概念、 描述参数、网络模型、优化准则和多播协议；分析了多播路由算法的研究现 状；研究了几个实用的多播路由算法。给出其执行过程。 再次，介绍遗传算法的基本思想、特点和应用；详细分析了遗传算法的 基本要素、遗传算法存在的问题；分析了遗传算法求解多播路由问题的现状 及发展趋势，对遗传算法的改进方法进行总结。 最后根据q o s 多播路由的特点，结合遗传算法的寻优特性，提出了一种 改进的d i j k s t r a 算法和一种基于改进遗传算法的多约束q o s 多播路由算法， 并对改进的多播路由算法进行了收敛性分析和仿真验证。与相关算法进行多 次比较实验证明，算法对解决多约束q o s 多播路由选择优化问题有一定改进， 尤其在网络规模较大的情况下，搜索速度较快。本文提出的算法是可行的、 有效的。 关键词：多播；多播树；多播路由算法：服务质量；遗传算法 哈尔滨l ：程人学硕士学位论文 a b s t r a c t i n c o m p u t e rn e t w o r k s ，m u l t i c a s tr o u t i n gi sn e t w o r k l a y e rf u n c t i o n st h a t c o n s t r u c t sp a t h s ，a l o n gw h i c ht h es a m em e s s a g ef r o ms o u f c en o d ec a l lb es e n tt o m u l t i p l e d e s t i n a t i o nn o d e s ，a n dt h e k e yo fm u l t i c a s tp r o b l e m l i e si nt h e d e t e r m i n a t i o no fm u l t i c a s tp a t h s t h eg e n e r mw a yt or e a l i z em u l t i c a s ti st o e s t a b l i s hm u l t i c a s tt r e e ，w h i c hi sas p a n n i n gt r e et h a tt a k et h er o o ta ss o u r c en o d e a n ds h a r em a n yl i n k s i nt r a n s m i t t i n gt h em e s s a g et ot h ed e s t i n a t i o ns e t 。t h e m u l t i c a s tt r e eh a st h r e ea d v a n t a g e s a tf i r s t ，t h em e s s a g ei st r a n s m i t t e dt od i f f e r e n t m u l t i c a s tm e m b e r s h i pb yp a r a l l e lm o d e ，t h u sd e c r e a s e i n gt h ed e l a yo fm e s s a g e t r a n s m i s s i o n t h es e c o n d ，t h em e s s a g eo n l yn e e dt ob er e p l i c a t e da tf o r k i n gn o d e s ， s oi ts a v e st h eb a n d w i d t h ，a n do p t i m i z e st h en e t w o r kp e r f o r m a n c e m u l t i c a s t r o u t i n ga l g o r i t h m sa r eu s e dt oc o m p u t em u l t i c a s tt r e e so fg o o dp e r f o r m a n c et h a t s a t i s f yq o sr e q u i r e m e n t sf o ra l lk i n d so fb u s i n e s s n o w , r e s e a r c h e so nm u l t i c a s tr o u t i n ga l g o r i t h mm a i n l yf o c u so nm u l t i c a s t i n g a l g o r i t h mw i t h o u tc o n s t r a i n t sa n dd e l a y c o n s t r a i n e dm u l t i c a s tr o u t i n ga n da l s ou s e h e u r i s t i ca l g o r i t h m h o wt h en e wo p t i m i z a t i o na l g o r i t h m - - g e n e t i ca l g o r i t h mw i l l b ea p p l i e dt oq o sm u l t i c a s tr o u t i n ga l g o r i t h mi st h ee m p h a s e so fr e s e a r c h an e w a p p r o a c ht or e s o l v eq o sm u l t i c a s tr o u t i n gp r o b l e mh a sb e e np r o v i d e dt h r o u g h p a r a l l e ls e a r c ha n dg r o u pi m p r o v e m e n to ft h ea l g o r i t h m f i r s t l y , t h ep a p e rs u m m a r i z e sm u l t i c a s t c o m m u n i c a t i o n si n c o m p u t e r n e t w o r k s ，p r e s e n t i n g t h eb a s i c c o n c e p t s ， c l a s s i f i c a t i o n ， f u n d a m e n t a l c h a r a c t e r i s t i c sa n da p p l i c a t i o n ，a n dt h e ns t u d i e st h em u l t i c a s tt e c h n o l o g ya n d a p p l i c a t i o n ，t h em u l t i c a s tr o u t i n gt e c h n o l o g ya n dt h em u l t i c a s tt o u t i n gp r o t o c 0 1 t h ep a p e ra l s oi n t r o d u c st h eb a s i cc o n c e p to fq o s s e c o n d l y , t h ep a p e rr e s e a r c h e st h em u l t i c a s tr o u t i n g i ti n t r o d u c e t h e f u n d a m e n t a l c o n c e p t s ，p a r a m e t e r s ，n e t w o r kp a r a m e t e r , n e t w o r km o d e l ， o p t i m i z a t i o nc r i t e r i o no ft h em u l t i c a s tr o u t i n g ；i ta n a l y s e st h ep r e s e n ts i t u a t i o no f m u l t i c a s t r o u t i n ga l g o r i t h m ；i ts t u d i e s s e v e r a lp r a c t i c a b l em u l t i c a s tr o u t i n g a l g o r i t h m sa n dp r e s e n tt h ee x e c u t i o np r o c e s s i i t h i r d l y , t h ep a p e rd e s c r i b e st h eb a s i cc o n c e p t ，c h a r a c t e r i s t i ca n da p p l i c a t i o n o fg e n e t i ca l g o r i t h m ，a n a l y z e si nd e t a i lt h ef u n d a m e n t a le l e m e n t so fg e n e t i c a l g o r i t h m s ，t h ep r o b l e m si ng e n e t i ca l g o r i t h ma n di t si m p r o v i n gm e t h o d ，a n di t a n a l y z e st h es i t u a t i o na n dd e v e l o p i n gt r e n do fg e n e t i ca l g o r i t h mt o m u l t i c a s t r o u t i n g l a s t l y , a c c o r d i n gt ot h ec h a r a c t e r so 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 m i o n c h a r a c t e ro fg e n e t i ca l g o r i t h m ，t h ep a p e re m p h a s i z e sa ni m p r o v e da l g o r i t h mo ft h e d i j k s t r aa l g o r i t h ma n dt h eq o sm u l t i c a s tr o u t i n ga l g o r i t h mb a s e do ng e n e t i c a l g o r i t h m sa n dp r o v i d et h ee m p i r i c a la n a l y s i sa n ds i m u l m i o nv a l i d a t i o n t h e i m p r o v e da l g o r i t h m f u r t h e rs o l v e sm u l t i - c o n s t r a i n tq o sm u l t i c a s t i n gr o u t i n g o p t i m i z a t i o nb yc o m p a r i n gw i t ho t h e ra l g o r i t h ma n de x p e r i m e n tt e s t ，a n di tw i l l b ef a s t e ri na p p l i c a t i o nt os e a r c h i n gi nt h en e t w o r ka tl a r g es c a l e a sar e s u l t ，t h e a l g o r i t h mm e n t i o n e di nt h i sp a p e ri sf e a s i b l ea n de f f e c t i v e k e y w o r d s ：m u l t i c a s t ；m u l t i c a s t i n gt r e e ；m u l t i c a s tr o u t i n ga l g o r i t h m ；q u a l i t yo f s e r v i c e ；g e n e t i ca l g o r i t h m i i i 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中己 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：么孙乡萄薄l 日期：洲多年月乡日 第1 章绪论 随着网络通信技术和计算机技术空前飞速发展，网络规模进一步扩大， i n t e r n e t 已成为信息社会的主要传播媒介。随着当前通信网络带宽和处理能力 的提高，网络已能够提供相当多的多媒体业务，比如股市行情发布、音视频 会议、视频点播、远程教学、大规模协作计算和网络游戏等，这也使得支持“点 到多点”或“多点到多点”的通信方式成为网络支持多媒体业务的主要形式。而 采用传统的“点到点”的单播通信方式或广播方式传输数据，不仅浪费大量的 网络带宽，而且效率很低，己无法满足当前大量网络信息传输的要求，多播 正是针对此类问题提出的一种新的、高效的网络传输方案【1 1 。 1 1 多播技术 多播提供了一种很重要的服务，它可以同时向多个接收者发送信息，且 不占用更多的网络资源。为此全球主要的网络设备厂商、电信运营公司和 i s p s 成立了个论坛型的组织“i p 多播倡议组织”，其目的是与i e t f ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ，i n t e m e t 工程任务组) 中的多播工作组一起制定碑多播 标准，并加速这些标准的采用。随着多播技术的进一步完善，以及更多高效、 实用的多播应用程序被开发出来，多播获得广泛的应用。多播通信的关键是 多播路由的选择，也就是如何构建一棵多播分布树。因此，找出满足各种业 务服务质量需求的多播路由，对保证多播应用系统的正常高效运行具有很重 要的意义。 1 1 1 多播的基本概念 多播是指从源节点将同一份信息传送到多个目的节点的过程。 多播源节点是指发起多播通信的节点。在“点对多点”通信模式中，一次 通信业务中只有一个多播源节点；在“多点对多点”的通信模式中，一次通信 业务中可以有多个多播源节点。 多播目的节点是指多播通信的接收者。通常，在一次多播通信中会有多 个多播目的节点。 多播组即多播目的节点的集合，将参与多播的多个目的节点组成一个多 1 一一 一 哈尔滨_ l i - 程1 1 大学硕十学位论文 播组。每个目的节点称为多播组成员。 多播树是指包含多播源节点、所有多播目的节点和使它们之间有效连通 的链路的集合。因其可看成是以源节点为根，以目的节点为叶子节点的的树 状结构，所以形象地称之为多播树。 1 1 2 多播树的分类 在m 多播中，多播源向某一组目的节点传递数据包，多播路由器必须知 道包的来源，而不是目的地。为向所有目的节点传递多播信息，一般采用多 播转发树来描述m 多播在网络中所经过的路径。多播转发树即多播树，一般 可分为洪泛法、有源树和共享树三种类型。 洪泛法是最简单的向前传送多播路由算法。其基本原理是当多播路由器 收到发往某个多播地址的数据包后，首先判断是否是首次收到该数据包，若 是首次收到，则将其转发到所有接口上，以确保其最终能到达所有接收者； 若不是首次收到，则抛弃该数据包。洪泛法实现的关键是“首次收到”检测。 这需要维护一个最近通过路由器的数据包列表，但无需维护路由表。它适合 对多播需求比较高的场合，并且能做到即使传输出现错误，只要还存在一条 到接收者的链路，则所有接收者都能接收到多播数据包。但洪泛法不适合用 于i n t e m e t ，因为它不考虑链路状态，并产生大量的拷贝数据包。此外，对 于高速网络而言，“首次收到”列表将会很长，占用相当大的内存，尽管它能 保证不对相同的数据包进行二次转发，但不能保证对相同数据包只接收一次。 有源树是以多播源节点为根，从根到所有目的节点路径都最短的多播树。 若组中有多个多播源，则必须为每个多播源构造一棵多播树。有源树有两种 形式。第一种是最短路径树。它以最短路径贯穿网络，即从源节点到所有目 的节点都是通过最短路径，但是全树的费用并不一定是最优的。这里树的费 用是指树中边的费用( 费用是一个广义上的概念，可以根据距离、信道带宽、 平均通信量、通信开销、队列平均长度、测量到的时延和其他一些因素的函 数计算出来) 之和。第二种是覆盖所有多播成员的一棵最优s t e i n e r 树。s t e i n e r 树问题是从图论中引申出来的一个优化问题，即在一个连通图中，给定一个 节点子集，要求在图中找到一棵覆盖给定节点子集的费用最小的生成树。 s t e i n e r 树的总费用最小，但是从源节点到每个目的节点不一定是最短路径。 2 哈尔滨工秆大学硕士学佗论文 当网络中的每个节点都具有多播功能时，求解费用最小的多播树问题与 s t e i n e r 树问题是等价的。若组中有多个节点存在多播需求，有源树要为每个 节点分别建立一棵以该节点为根的多播树，这会增加网络管理的开销。 共享树是指为每个多播组选定一个核心，以其为根建立多播树。多播源 要发送一个多播消息，主机先将它发往核心，再由核心沿着生成树发送消息。 采用这种方式，只需为多播组维护一棵生成树，能够降低存储开销，但付出 的代价是生成的多播树对某些多播源来说可能不是最优的，从而导致时延增 加。另外，共享树可能会将来自多个多播源的数据流量聚集在靠近核心的部 分链路上，造成网络拥塞，降低服务质量。有核树是共享树的一种，它是以 选定中心为根，由根到所有组成员的最短路径合并而成的树，所有发送节点 共享此树。 1 1 3 多播技术的基本特点与应用 自从d e e r i n g 博士1 9 8 8 年建立口多播模型以来，多播技术一直是人们 研究的一个热点问题。从1 9 9 2 年建立多播主干网，且i e t f 利用它成功地举 行第一次网络会议以来，随着多播支持的多媒体应用曰益增多，多播技术快 速发展，其应用也更加广泛。 多播技术的基本特点是源节点向网络中某特定节点子集发送数据包。它 利用树传送结构，数据分组仅在分枝节点处被复制，能够节约带宽、降低服 务器负载、降低网络负载和减少拥塞。同时在每条链路上仅转发一次，这份 数据中的目的地址为多播地址，多播组中的所有接收者都可以接收到同样的 数据拷贝，高效地将数据同时传送到各个多播组成员。 多播以其“一点( 多点) 传送多点接收”，即使用户数量成倍增加，主干 网络带宽也不需要随之增加这一独特的优点和特性成为当前网络中的研究热 点。很多专家认为它将成为下一代互联网的关键技术之一。其主要应用有如 下几方面。 1 1 数据分发。数据分发主要利用多播技术“一点传送，多点接收”的特性， 数据中心利用多播技术，只需次就可以将数据发送到多个目的地址，这样 就省去了重复传输的工作量。如大公司采用p u s h 的模式进行文件和数据库的 更新，以完成每天的远程办公信息发布和信息更新。 3 哈尔滨丁程大学硕十学位论文 2 ) 实时数据传播。向大量的主机组传输实时数据是使多播技术深受欢迎 的一个应用领域。典型的例子有股票信息实时发送到交易大厅的工作站，铁 路票务信息网上发布等。 3 ) 游戏和仿真。多播可以用于有大量参与者的游戏和仿真，参与的p c 机或工作站只需进入多播组，就可以开始发送和接受游戏及仿真数据，通过 不同的多播组可以将游戏加入者分为不同的游戏空间。现在互联网上的大小 游戏很多都是基于多播方式传输数据。 4 ) 多媒体应用。多媒体是当前多播技术的最重要的应用领域。随着网络 技术和多媒体技术的发展，利用网络来传输多媒体数据越来越普遍，例如多 媒体会议系统、v o d 系统等。 1 2 多播路由技术 1 2 1 多播路由产生背景 在8 0 年代初，多播技术主要应用在局域网环境，以太网和令牌环网等对 多播技术提供较好的支持，而通过桥扩展的局域网和互联网都不支持多播。 直到8 0 年代末，在研究了开放最短路径优先协议和路由信息协议等i p 路由 协议之后，s t e v ed e e r i n g 在他的博士论文中指出基于数据包的互联网单播机 制完全可以扩展用来支持多播【2 j ，奠定了多播的网络体系结构和路由协议的 基础，该文也成为i n t e m e t 组管理协议的原型。到1 9 9 2 年多播技术在多播骨 干网上得到应用，多播技术得以加速发展，逐渐成熟。 为使网络能实时传输连续多媒体数据，节省网络资源，提高网络传输速 度，进行有效的多播通信，确定一个多播路由是非常关键的。路由是计算机 网络中网络层的主要功能，也是决定网络传输性能的主要因素之一。多播路 由问题的目标是应用一种算法和策略，在给定网络和多播需要的情况下，寻 找一组从源节点到目的节点的有效路径，使网络资源能够得到有效利用。多 播源把数据发送到特定的多播组，只有属于该多播组的成员才能接收到该数 据，因此可以大大的节省网络带宽。而网络带宽正是制约实时和多媒体应用 发展的主要瓶颈，所以多播路由技术成为研究和应用的热点，成为解决带宽 瓶颈的法宝。而这类问题用最优方案来解决是不实际的，通常只寻找一种次 优的、在实际中可行的方案。研究多播路由算法的主要目标是在一个给定的 4 哈尔滨_ t 程大学硕士学位论文 网络中求一棵满足要求、代价最小的多播树。 目前实现多播通信最有效的一种方式就是构造多播树，而多播路由算法 就是研究如何在网络中建立一棵多播树。为了准确、有效地将信息送到多播 组，必须为它们确定路由，信息按选择的路由进行传送。作为多播通信的重 要组成部分和关键问题，寻找简单、高效、健壮的多播路由算法一直是网络 界致力研究但未完全解决的问题【3 】。 1 2 2 多播路由协议的基本类型 下面的图1 1 给出了多播路由协议的基本类型，并对不同类型的协议进 行了分类。 r 协议无关多播 i 协议无关多播 i 域内多播路由协议 距离矢量多播 li 多播路径最短 r 多播路由协议 o 有核树多播路 ii ll广多协议边界网 步接“l、域间多播路由协议 多点传输源网 多播协议、塌州夕馏阳山w 以1 梦腻1 彳硼讲一 jl s s m ( 稀疏模式p i m s m ) ( 稠密模式p i m d m ) 路由协议d v m r p 优先协议m o s f p 由协议c b t 关协议m b g p 关协议m s d p 【主机多播协议( = 兰嚣薯量嚣裂三墨s 删n g 图1 1 多播路由协议的基本类型 多播路由的一种常见的思路就是在多播组成员之间构造一棵连接该多播 组中所有节点的多播树，多播数据流通过该多播树从源节点传输到目的节点。 不同的d 多播路由协议使用不同的技术来构造这些多播树，一旦这个树构造 完成，所有的多播流量都将通过它来传播。 根据网络中多播组成员的分布，i p 多播路由协议可以分为以下两种基本 类型。第一种称作密集模式的多播路由协议。假设多播组成员密集地分布在 网络中，也就是说，网络大多数的子网都至少包含一个多播组成员，而且网 络带宽足够大，它依赖于广播技术来将数据“推”向网络中所有的路由器。密 集模式路由协议包括距离向量多播路由协议、多播开放最短路径优先协议和 协议无关多播密集模式协议等【4 】。第二种称作稀疏模式的多播路由协议。假 5 哈尔滨工程人学硕十学位论文 设多播组成员在网络中是稀疏分散的，并且网络不能提供足够的传输带宽， 比如i n t e m e t 上通过i s d n 线路连接分散在许多不同地区的大量用户。在这种 情况下，广播就会浪费许多不必要的网络带宽从而可能导致严重的网络性能 问题。于是稀疏模式多播路由协议必须依赖于具有路由选择能力的技术来建 立和维持多播树。稀疏模式主要有基于核心树的多播协议【5 】和协议无关多播 稀疏模式协议 6 1 。 1 2 3 多播路由协议介绍 为进行有效的多播通信，确定多播路由是非常关键的。网络的状态信息 包括网络的拓扑结构、链路和路由器的负载程度、链路和路由器的失效和有 效、网络中路由器的类别( 是否具有多播功能) 等，而这些信息的收集是由多 播路由协议来完成的。本节简要介绍几个实际应用中常用的多播路由协议， 并对设计多播路由算法和协议时应考虑的因素进行分析。 1 ) 距离向量多播路由协议 第一个支持多播功能的路由协议就是距离向量多播路由协议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 为每个发送源和多播组构建不同的多播树。每个多播树都是一 个以多播发送源为根，以多播目的节点为叶的最小扩展多播树。这个多播树 为发送源和组中每个目的节点之间提供了一个以“跳数”为单位的最短路径。 当发送源要向多播组中发送消息时，多播树就根据这个请求而建立，并且使 用“广播和修剪”的技术来维持这个扩展多播树。发送多播包的具体过程是当 一个路由器接收到一个多播包，路由器先检查它的单播路由表，查找到多播 组发送源的最短路径的接口，若这个接口就是这个多播包要到达的接口，则 路由器就将这个多播组信息记录到它的内部路由表( 指明该组数据包应该发 送的接口) ，并且将这个多播包向除了接收到该数据包的路由器以外的其他临 近路由器继续发送；若这个多播包的到达接口不是该路由器到发送源的最短 路径的接口，则这个包就被丢弃。这种机制被称为反向路径广播机制。 对子网中密集分布的多播组来说d v m i 冲能够很好的运作，但是对于在 范围比较大的区域上分散分布的多播组来说，周期性的广播行为会导致严重 6 一一一一 哈尔滨t 程大学硕士学位论文 的性能问题。d v m r p 不能支持大型网络中稀疏分散的多播组。 2 ) 多播开放最短路径优先协议 开放最短路径优先协议o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 是一个单播路由 协议，它将数据包在最小费用路径上传送。除了路径中的跳数以外，其他能 够影响路径开销的网络性能参数还有负载平衡信息、应用程序需要的服务质 量要求等。 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 ) 是为单播路由多播使用设计 的，并依赖o s p f 作为单播路由协议。在一个o s p f m o s p f 网络中，每个 路由器都维持一个最新的全网络拓扑结构图，这个“链路状态”信息被用来构 建多播树。每个m o s p f 路由器都通过i g m p 协议周期性的收集多播组成员 关系信息。这些信息和链路状态信息被发送到其路由域中的所有其他路由器， 路由器将根据它们从临近路由器接收到的这些信息更新他们的内部连接状态 信息。由于每个路由器都清楚整个网络的拓扑结构，就能够独立的计算出一 个最小开销扩展树，将多播发送源和多播组成员分别作为树的根和叶。 3 ) 协议无关多播密集模式协议 协议无关多播协议是一种标准的多播路由协议，并能够在i n t e m e t 上提 供可扩展的域间多播路由而不依赖于任何单播协议。它有两种运行模式：密 集分布多播组模式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 t d 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 t s p a r s em o d e ) 。 p i m d m 类似于d v m r p ，这两个协议都使用反向路径多播机制来构建 多播树。适用于发送者和接收者的距离很近，也适用于很少的发送者和很多 的接收者，以及流量很高的情况。p i m d m 的工作过程可以概括为邻居发现、 扩散一剪枝过程、嫁接三个阶段。p i m - d m 协议是数据驱动的，采用“扩散一 剪枝”机制，路由器某个接收端口接收到的多播数据包被发送到所有下行接 口，直到不需要的分枝从树中被修剪掉。p i m - d m 协议简单，易于理解和使 用，能够很好地与d v m r p 进行互通，用于发送方和接收方靠近，发送方较 少而接收方较多，多播通信量大而带宽资源较丰富的环境。 4 ) 基于核心树的多播协议 核心树的多播协议c b t ( c o r e b a s e dt r e e ) 构建一棵树给组中所有成员共 享，这棵树被称为共享树。不论发送源有多少或者在什么位置，整个多播组 7 哈尔滨t 程大学硕十学位论文 的通信量都在这棵共享树上进行收发。这种共享树的使用极大的减少了路由 器中的多播状态信息。 c b t 共享树以一个核心路由器来构建树。要加入的路由器发送加入请求 给这个核心路由器，核心路由器接收到加入请求后，沿反路径返回一个确认， 这样就构成了树的一个分枝。加入请求数据包在被确认之前不需要一直被传 送到核心路由器，如果加入请求数据包在到达核心路由器之前先到达共享树 上的某个路由器，则该路由器就接收下这个请求包并确认这个请求，而不继 续向前发送，发送请求的路由器就连接到共享树上了。c b t 将多播流量集中 在最少数量的链路而不是在一个基于发送源的共享树上。集中在核心路由器 上的流量可能会引起多播路由的某些问题，为解决这样的问题，某些版本的 c b t 支持多个多播核心的使用，和单个多播核心相比，多核心更能达到负载 平衡。 5 ) 独立多播稀疏模式协议 与c b t 相似，p i m s m 被设计成将多播限制在需要收发的路由器上， p i m s m 围绕一个被称为集中点的路由器构建多播树。接收者在集中点能查 找到新的发送源。p i m s m 中独立的接收者可以选择是构建组共享树还是最 短路径树。p i m - s m 最初先为多播组构建一个组共享树。这个树由连接到集 中点的发送者和接收者共同构建，组共享树建立以后，一个接受者可以选择 通过最短路径树改变到发送源的连接。 p i m - s m 没有单独的多播路由表，不必发送多播路由更新，因此开销小， 它可以切换到最短路径树，以减少通常与共享树有关的网络时延。采用显式 加入模式，更适合于在广域网链接末端有潜在成员的多播网络，组中接收者 比较少，发送者和接收者被隔离或比较稀疏，数据包的传播带宽资源不一定 是很丰富的环境。因此，p i m s m 是大多数通用多播网络域问路由协议的最 好选择。 1 3q o s 的基本概念 服务质量( q u a l i t yo fs e r v i c e ，q o s ) 是网络传输业务流对网络服务的需求 集合，是应用业务对网络传输服务所提出的一组可度量的要求。网络传输相 应业务时，必须满足这组要求。q o s 有多种等价和互补的定义形式。r f c 2 3 8 6 【7 j 8 哈尔滨t 稃人学硕十学位论文 中的q o s 描述为网络在传输数据流时要求满足的一系列服务请求，也是指数 据流通过网络时的性能要求，具体可以量化为带宽、时延、时延抖动、吞吐 量和包丢失率等。此处的服务是指数据包经过网络节点时所接收的传输服务， 强调端间或者网络边界的整体性。 目前，随着多播技术的发展，各种新型通信业务如视频点播、电视会议、 远程教学等一般涉及多个用户，且对q o s 有严格的要求，这正是多播路由技 术面临的挑战，即多播路由对q o s 的支持。在满足服务质量需求的情况下怎 样更好地实现多播功能，成为研究的热点。 1 3 1 赋权图模型 网络的拓扑结构和资源容量可以抽象为一个赋权图( 巧毋，其中y 代表网 络中的交换设备集合，即交换节点集：e 代表连接交换设备的传输链路。对 于大多数实际网络而言，传输链路一般都是不对称的。这里为了简化问题， 假设链路对称，因此赋权图的边是无向的。每一条链路都有一个对应于相关 q o s 度量的状态，每一个节点也有相应的状态，节点的状态信息可以单独表 示出来，或者也可以折算到与节点相连的链路状态中去。 1 3 2 状态信息 1 ) 本地信息。每一个节点都必须保持其最新的本地信息，包括链路传输 时延、排队时延、输出链路的剩余带宽及其他网络资源的可用信息。 2 ) 全局信息。所有节点的本地信息总和就构成了全局信息。每一个节点 可以用链路状态协议或者距离一向量协议来发布、取得全局信息。链路状态协 议通过让各节点广播其本地信息来确定网络的拓扑结构和各链路的状态。距 离一向量协议通过相邻节点定期交换其距离向量来取得并扩散全局信息。每一 个节点保持的全局信息，总是对现有网络状态的一种近似描述，这是由信息 传输时延造成的；而时延的不可避免性表明这种不确定性会随着网络规模的 增加而不断扩大。 3 1 状态信息的聚合。由于任何物理设备的资源存储和处理能力都是有限 的，这样对全局信息的精确保存，会带来扩展性问题。因此，降低全局信息 的规模就变得十分重要。可以通过把一个具有层次性结构的大型网络的局部 9 哈尔滨 t 程大学硕十学位论文 信息进行聚合，即把包含几个物理节点的组抽象为一个逻辑节点。而逻辑节 点又可以进一步聚合成更高一级的逻辑节点，如此反复下去来完成对全局信 息的精确保存。在聚合过程中，必须把下层节点的网络度量性能聚集为本层 逻辑节点的度量特性。这种过程是复杂的，而不同的聚集方法对状态信息的 影响也是一个开放性的问题。 1 3 3q o s 的度量 网络提供给用户的q o s 是由各种网络参数决定的，是由可用带宽、时延、 时延抖动、包丢失率等参数描述的分组传输特性。网络要满足用户的质量要 求，就必须满足用户要求的q o s 参数，下面介绍一些q o s 参数及其性质。 1 ) 带宽 带宽是单位时间内传送的d 包数量。通常指网络信道的传输能力，在不 同的时间段，这种能力可能是变化的。多媒体业务的数据传输量往往较大， 因此需要网络为其分配最小带宽。如标准电话为6 4 k b i t s ，压缩过的h d t v 为2 5 - 3 4 m b i t s ，视频会议为0 1 - 2 m b i f f s 等。 2 ) 时延 时延是指数据包从发送端到接收端的时间长度，它分为固定部分和可变 。部分。固定部分主要为传输时延和转发时延，而可变部分包括处理时延和排 队时延。实时业务往往是对时延敏感的，比如在虚拟现实应用中，由于语音 输入的响应时间被限制在l o o m s 之内，所以端到端时延应在4 0 m s 左右。而 有些非实时业务如e m a i l 等，却是对时延不敏感的，因此网络不需要对这类 业务提供时延保证。 3 l 时延抖动 时延抖动即时延变化，指在同一源节点沿不同路径发送数据到不同目的 节点的时间差异。它是由于时延的可变部分的变化导致的，流量的突发性、 不公平的队列调度方法都可能导致较大的时延抖动。当i p 包到达交换设备 时，若等待队列中没有别的i p 包，则它将以固定时延被转发出去。但是，若 等待队列中还有别的包，则它可能就需要等待，这时i p 包被交换的时延就等 于固定时延加上在队列中等待的时间。以上两种情况下时延的变化程度就是 时延抖动。 1 0 ， 哈尔滨t 稃大学硕十学位论文 4 ) 包丢失率 包丢失率是指特定的时间段丢失的包占传输包的总数的比例。数据包丢 失一般是由网络拥塞引起的。某些应用程序在包丢失后无法正常工作，因此 要求网络提供传输保障，这方面的典型例子就是t c p 。而某些多媒体业务如 i p 电话，个别包的丢失虽然会影响音频的质量，但用户往往可以容忍这种质 量的暂时下降。因此，只要包丢失率在一定的范围内，就不会影响业务的正 常进行。 5 ) 吞吐量 吞吐量是网络中发送数据包的速率，可用平均速率或峰值速率表示。 6 ) 路径长度 路径长度一般指数据从数据源传输到达目的地所经历的路由器的个数。 7 ) q o s 度量的分类 网络服务时被要求提供的服务质量。对于路径p = ( 口，b ，g ，埘，用配6 ) 表示对应链路( 口，6 ) 的度量，q o s 度量可以按性质分为以下三类： ( 1 ) 凹性q o s 度量。若d ( a , z ) = m i n 吠口，6 ) ，吠6 ，c ) 姒力 ，则度量由传输 通道中瓶颈决定，即此度量仅与路径上的某个瓶颈链路的q o s 度量有关，如 剩余带宽、流量、剩余缓存空间、链路速度等。 ( 2 ) 可加性q o s 度量。若如力= 地，6 ) + 吠6 ，d + + 彤力，则度量由传输 通道中所有链路的特性共同决定，如端到端的时延、时延抖动、费用等。 ( 3 ) 可乘性q o s 度量。若歹) = d ( a ，b ) 吠6 ，c ) m z ) ，即度量为所有 链路对应度量的乘积，如包丢失率、误差率、可靠性等。如取d ，( 口，b ) = t n d ( a ，6 ) 】， 则可乘性度量就传换为可加性度量。， 因此，按度量的性质q o s 路由可归结为基本的两大类：路径优化问题， 对应可加性q o s 度量；链路优化问题，对应凹性q o s 度量。 1 3 4q o s 设计的基本原则 服务质量除了包含用户和网络服务者之间的约定外，一般还包括用户之 间、网络中各节点之间q o s 的协商和管理的问题。当用户的q o s 要求太高， 网络无法提供相应的服务时，将要求用户降低其q o s 请求，甚至为了保证其 他用户的q o s 而拒绝某个用户的q o s 要求。用户与网络之间的q o s 协商通 哈尔滨l ：释人学硕十学何论文 常称为q o s 接纳控制。有时在网络内部的路由器、交换机的端口以及端主机 系统中，为了保证用户的q o s ，必须进行资源预留，需要相应的资源预留协 议和资源调度算法。将q o s 引入到网络系统，必须考虑下面五个原则。 1 ) 集成原则。该原则要求在系统的所有层上q o s 都必须是可配置、可 预测和可维护的。当多播信息流从源节点产生，向下经过源的协议栈，穿过 网络到达目的节点的相应层，所穿过的系统各个层次的资源模块都必须提供 q o s 的可配置性、资源担保和信息流的q o s 维护。 2 ) 分离原则。该原则描述了信息的传输、控制和管理是系统的不同功能 的行为，主要是区分系统传输的是控制信令还是数据。其中，控制信令的传 输要求低带宽、无抖动限制和高可靠的服务。 3 ) 透明原则。即低层复杂的q o s 控制和管理机制对应用必须是透明的。 透明的好处是可以将q o s 功能与应用设计分离，简化应用设计和增强可移植 性；可以为应用屏蔽低层网络的服务细节；可以将复杂的q o s 控制和管理任 务交给低层的网络实现。 4 ) 异步资源管理原则。指分布式通信中不同行为( 调度、流控、路由和 q o s 管理) 的产生不是同时的，这种异步使得模块能周期性地交换信息。 5 ) 性能原则。该原则指q o s 控制和管理机制的设计必须是以提高网络系 统的性能为目的。 1 3 5q o s 的研究范围 为网络中的应用提供q o s 保证是目前网络技术研究领域的焦点问题，更 是难点问题。大量的文献从不同的角度对网络q o s 问题进行了研究，这些研 究主要体现在以下五个方面。 1 ) 路由选择算法。路由选择是为发送报文分组而选择一条传输路径的过 程。路由选择算法设计的好坏关系到网络资源利用率和网络性能的高低。从 理论上讲，路由选择软件应当考虑网络负荷、数据报长度、数据报报头中规 定的服务类型等情况，但由于实现上的困难，通常以最短路由为前提进行路 由选择。 2 ) 流量控制和拥塞控制。网络流量控制是在网络正常工作时采取的一系 列措施，控制使网络发生拥塞的条件，避免造成网络拥塞。这些控制措施包 1 2 哈尔滨= 程大学硕+ 学位论文 括：网络资源管理、接入允许控制、流量参数控制、非一致性数据包的标记 和数据包的分流等。拥塞控制是网络拥塞时采取的一系列措施，从而使得网 络拥塞的强度、持续时间和扩散的影响减至最小。 3 ) 流量工程。流量工程的作用在于使数据流通过网络，以避免不均匀使 用网络而导致拥塞。而现在的动态路由协议总是选择最短路径转发包，导致 不均匀的通信分布。目前使用的方法是让网络管理员根据业务量的分布情况， 手工配置链路和路由，均匀地发配流量。这样的方法不适合业务量分布不稳 定和复杂网络的环境，因此流量工程实施需要能够自动化和适应业务流量分 布的变化，这样才能保证业务的q o s 。 4 ) 流量整形。流量整形是一种用来在接口上平缓通