（计算机应用技术专业论文）基于qos的多播路由算法及仿真研究(1).pdf

武汉理工大学硕士学位论文 摘要 多播技术作为一种可大大节省网络资源的技术在多媒体业务中有着广 泛的应用。目前的i n t e r n e t 只提供尽力传送服务，在进行路由选择时一般只考 虑网络路由的跳数或时延，但为了支持各种q o s 需求，还应该考虑如带宽、时 延抖动、丢失率等参数。从而出现了满足o o s 多播路由优化问题的研究。 本文首先阐述了基本的路由技术，并对典型的路由协议作了介绍，论述 了基于i p 的q o s 研究体系，讨论了支持q o s 的多播路由算法的数学模型。在 介绍多播路由技术以及o o s 技术的基础上，对支持o o s 的多播路由算法进行 了比较洋细的探讨，并提出了新的支持q o s 多播路由算法。在同现有算法对 比的基础上，用n s 2 仿真软件对该算法进行了性能分析。最后总结了本论文 所做的工作，并指出本课题领域有待于进一步研究的问题。 本文总共分为七章，其内容如下： 第l 章，主要引入了路由的概念，简单介绍了路由协议的基本思想和几 个经典的路由协议，并介绍了本课题的来源及研究的意义。 第2 章，详细的介绍了路由的基本原理，q o s 技术的体系结构，并讨论了 支持q o s 的多播理论。 第3 章，引入了网络仿真的概念，着重介绍了一种免费开源的网络仿真 器n s 2 的发展情况，n s 2 的使用及在网路仿真的应用。 第4 章，讨论了基于最小生成树的多播路由算法，对现有的一些常用算 法进行了分析比较，在此基础上提出了一种改进的算法，并仿真之。 第5 章，讨论了支持q o s 的多播路由算法的数学模型，对支持q o s 的多播 路由算法进行了分析比较，并提出了一种改进的启发式算法，最后仿真之。 第6 章，讨论了支持q o s 多播路由的基于最小生成树算法的理论模型并 提出一种新的算法，试验仿真结果证明了它的效率会比传统算法大大提高。 第7 章，给出了本文的总结，并对下一步的工作作了展望。 本文得到国家自然科学基金项目( 批准号：6 0 1 7 2 0 3 5 ，9 0 3 0 4 0 1 8 ) 的资助。 关键词：路由，多播，q o s ，最小生成树，网络仿真 武汉理工大学硕： = 学位论文 a b s t r a c t i nm u l t i m e d i ac o m m u n i c a t i o n n e t w o r k s ，m u l t i c a s ti sb e c o m i n gi n c r e a s i n g l y i m p o r t a n t i no r d e rt os u p p o r tm u l t i c a s t ，e f f i c i e n tm u l t i c a s tr o u t i n gi s c r u c i a l m u l t i c a s t ，w h i c hc a ns a v ei m m e n s en e t w o r kr e s o u r c e ，h a sb e e nw i d e l ya p p l i e d i nm u l t i m e d i ac o m m u n i c a t i o n af u n d a m e n t a li s s u ei nm u l t i c a s tc o m m u n i c a t i o n i sh o wt od e t e r m i n ea ne f f i c i e n tm e s s a g er o u t e ( m u l t i c a s tr o u t i n g ) a tp r e s e n t ， i n t e r n e to n l yp r o v i d e sb e s te f f o r ts e r v i c e s ，c o n s i d e r i n gh o pt i m e so rd e l a yi n r o u t es e l e c t i n g i no r d e rt os u p p o r tq o s ，w es h o u l dc o n s i d e ro t h e rp a r a m e t e r s s u c ha sb a n d w i d t h ，d e l a y , d e l a y j i t t e r ，l o s sr a t ea n d s oo n n o wr e s e a r c h e so nm u l t i e 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 m w i t h o u tc o n s t r a i n s t h i s p a p e r f i r s td e s c r i b e st h eb a s i c r o u t i n g t e c h n o l o g y a n d i n t r o d u c i n gt y p i c a lr o u t i n gp r o t o c o l ，e x p a t i a t i n gq o s r e s e a r c h i n gs y s t e m t h a tb a s e do ni hd i s c u s s i n gm a t h e m a t i c a lm o d e lo fm u l t i c a s t r o u t i n go fs u p p o r t i n gq o s o nt h eb a s i so fi n t r o d u c i n gm u l t i c a s tr o u t i n ga n dq o st e c h n o l o g i e s ，t h i s p a p e rd i s c u s s e sm u l t i c a s tr o u t i n ga l g o r i t h m so fs u p p o r t i n gq o si nd e t a i l ，a n d p r e s e n t st h r e ea l g o r i t h m so fs u p p o r t i n gq o s o nt h ef o u n d a t i o no fc o m p a r i n g t h ee x i s t i n ga l g o r i t h m s ，n s 2i su s e dt oa n a l y z et h e i rp e r f o r m a n c e t h es t u d y s h o w st h a tt h en e w a l g o r i t h m sa r em o r ee f f i c i e n c y f i n a l l y , c o n c l u s i o n so f t h i s p a p e ra n ds u g g e s t i o n s f o rf u t u r er e s e a r c ha r eg i v e n t h i sa r t i c l eh a ss e v e n c h a p t e r s c h a p t e r 1d e s c r i b e st h ec o n c e p to fr o u t i n g ，s i m p l yi n t r o d u c e st h eb a s i c s t a t u so f r o u t i n gp r o t o c o la n ds o m et y p i c a lr o u t i n gp r o t o c o l ，a l s oi n t r o d u c e st h e s o u r c ea n dr e s e a r c hm e a n i n go ft h i sa r t i c l e c h a p t e r 2i n t r o d u c e s d e t a i l e d l y t h eb a s i c p r i n c i p l e o f r o u t i n g ，q o s t e c h n o l o g ya r c h i t e c t u r e ；d i s c u s s e st h em u l t i e a s tt h e o r y t h a ts u p p o r t i n gq o s c h a p t e r3b r i n g s t h ec o n c e p to fn e t w o r ks i m u l a t o r ，i n t r o d u c e st h ef r e e s o f t w a r en s 2a n di t su t i l i t i e s c h a p t e r4d i s c u s s e sam s ta l g o r i t h mo fs u p p o r t i n gm u l t i c a s tr o u t i n g ，a n d t h e nc o m p a r e st h ea l g o r i t h m st h a ts u p p o r t i n gm u l t i c a s tr o u t i n ga n ds i m u l a t e si t b y n s 2 1 i 武汉理t 大学硕士学位论文 c h a p t e r 5d i s c u s s e sam a t h e m a t i c a lm o d e l i n go fr o u t i n g p r o t o c o l t h a t s u p p o r t i n gq o sm u l t i c a s t ，c o m p a r e s t h e a l g o r i t h m s t h a t s u p p o r t i n gq o s m u l t i c a s tr o u t i n ga n dt h es i m u l a t i n gr e s u l t ss h o wt h a ti tw a sm o r ee f f i c i e n c y t h a nt h et r a d i t i o n a la l g o r i t h m s c h a p t e r6d i s c u s s e sam o d e l i n go f t h em s t a l g o r i t h mo fs u p p o r t i n gq o s m u l t i c a s tr o u t i n g ，p u t sf o r w a r dan e wa l g o r i t h m ，s i m u l a t e si ta n dg e t st h er e s u l t s t h eu r o o f o f c o r r e c t n e s sa n dc o m p l e x i t ya n a l y s i so f t h en e wa l g o r i t h m a r eg i v e n ， c h a p t e r7s u m m a r i z e st h i sp a p e r ，a tt h es a m et i m e ，s u g g e s t i o n sf o rf u t u r e r e s e a r c ha r eg i v e n ， t h i s p r o j e c t i s s u p p o r t e db y n a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no f c h i n a ( p r o j e c t sn o ，6 0 1 7 2 0 3 5 ，9 0 3 0 4 0 1 8 ) k e yw o r d s ：r o u t i n ga l g o r i t h m ，m u l t i c a s t ，q o s ，m s t , n e t w o r k s i m u l a t o r i i i 武汉理i i ：大学硕士学位论文 1 1 引言 第1 章绪论 近年来，在高性能网络上传输实时多媒体业务的需求日益高涨。随着 i n t e r n e t 规模的不断增大，各种各样的网络服务争相涌现，先进的多媒体系 统层出不穷。由于实时业务对网络的传输时延，延时抖动等特性比较敏感， 当网络上有突发性高的f t p 或者含有图象文件的h t t p 等业务时，实时业务 就会受到很大影响，另一方面，多媒体业务占去了大量的带宽，这样，现有 的网络要保证的关键业务就难以得到可靠的传输。解决这些问题的最简单的 办法是增大带宽，但由于代价高昂，所以并不十分可行。于是各种服务质量 ( q o s q u a l i t yo f s e r v i c e ) 技术应运而生，它们通过对数据包进行排队，对某 些特定的数据包赋予较高的优先级等方式，来满足各种业务的q o s 需求。 在城域网i n t e r n e t 中，采用单播方式将相同的数据包发送给网络中的多个而 不是全部接收者时，由于需要复制分组给每一个接收端点，随着接收者数量 的增多，需要发出的包数也会线形增加，这使得发送主机、路由设备及带宽 资源总体负担很重，效率受到极大影响。随着多点电视会议、群组通信应用 等需求的增长，为提高资源利用率，多播方式日益成为多点通信中普遍采用 的传输方式。而多播业务对服务质量的要求也随着应用的发展而越来越明显 支持q o s 的多播路由成为当今研究的一个热点，本文着重讨论了支持q o s 的 多播路由算法。“ 1 2 路由的相关概念 路由是指为发送报文分组选择一条路径的过程，在i n t e r n e t 中通过路由 器完成这种选择。路径选择算法的好坏关系到网络资源的利用率和网络性能 的高低。从理论上讲，路由选择软件应当考虑网络负荷、数据报长度、数据 报报头中规定的服务类型等情况，但由于实现上的困难，通常以最短路径为 前提进行路由选择。 一般来说，路由选择可以分为两种形式：直接路由选择与间接路由选择。 武汉理工大学硕士学位论文 直接路由选择使一个数据报从一台计算机直接传送到另一台计算机，它是支 撑i n t e r n e t 所有通信的基础。这种路由选择是用一种基本物理传输系统完成 的。f 刚接路由选择是指报宿( 接收信息的一端) 不在报源( 一次通信中产生和 发送信息的一端) 直接连接的网络上，发送者必须把数据传给一个路由器， 然后数据报在路由器之间进行传递，直到可以通过一个物理网络直接递交给 报宿为止。 i n t e r n e t 中的路由选择算法通常使用路由选择表，表中的每一项是一对 地址( n 。r ) ，其中n 是报宿网络地址，而r 是下一个路由器的i p 地址。计算 机使用的路由选择表中列出的所有路由器都必须在该计算机直接连接的各 个网络上，这样，该计算机就可以直接到达这些路由器。”3 路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了 最终的寻径结果，因此选择路由算法一定要仔细。通常需要综合考虑以下几 个设计目标： ( 1 ) 最优化：指路由算法选择最佳路径的能力。 ( 2 ) 简洁性：算法设计简洁，利用最少的开销，提供最有效的功能。 ( 3 ) 坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、 负载过高或操作失误时，都能正确运行。由于路由器分布在网络联接点上， 所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的 考验，并在各种网络环境下被证实是可靠的。 ( 4 ) 快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过 程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路 由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一 致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 ( 5 ) 灵活性：路由算法可以快速、准确地适应各种网络环境。例如，某 个网段发生故障，路由算法要能很快发现故障，并为使用该网段的所有路由 选择另一条最佳路径。“1 1 3 路由选择方式及协议 典型的路由选择方式有两神：静态路由和动态路由。 静态路由是在路由器中设置的固定的路由表。除非网络管理员干预，否 则静态路由不会发生变化。由于静态路由不能对网络的改变作出反映，一般 用于网络规模不大、拓扑结构固定的网络中。静态路由的优点是简单、高效、 武汉理一j j 大学硕士学位论文 可靠。在所有的路由中，静态路由优先级最高。当动态路由与静态路由发生 冲突时，以静态路由为准。“1 动态路由是网络中的路由器之间相互通信，传递路由信息，利用收到的 路由信息更新路由器表的过程。它能实时地适应网络结构的变化。如果路由 更新信息表明发生了网络变化，路由选择软件就会重新计算路由，并发出新 的路由更新信息。这些信息通过各个网络，引起各路由器重新启动其路由算 法，并更新各自的路由表以动态地反映网络拓扑变化。动态路由适用于网络 规模大、网络拓扑复杂的网络。当然，各种动态路由协议会不同程度地占用 网络带宽和c p u 资源。 静态路由和动态路由有各自的特点和适用范围，因此在网络中动态路由 通常作为静态路由的补充。当一个分组在路由器中进行寻径时，路由器首先 查找静态路由，如果查到则根据相应的静态路由转发分组；否则再查找动态 路由。 根据是否在一个自治域内部使用，动态路由协议分为内部网关协议( i g p ) 和外部网关协议( e g p ) 。这里的自治域指一个具有统一管理机构、统一路由 策略的网络。自治域内部采用的路由选择协议称为内部网关协议，常用的有 r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 、o s p f ( o p e ns h o r t e s tp a t hf i r s t ) ；外部 网关协议主要用于多个自治域之间的路由选择，常用的是b o p ( b o r d e r g a t e w a yp r o t o c 0 1 ) 和b g p 一4 。下面分别进行简要介绍。“3 1 3 1r i p 路由协议 r i p 协议最初是为x e r o x 网络系统的x e r o xp a r c 通用协议而设计的，是 i n t e r n e t 中常用的路由协议。r i p 采用距离向量算法，即路由器根据距离选择 路出，所以也称为距离向量协议。路由器收集所有可到达目的地的不同路径， 并且保存有关到达每个目的地的最少站点数的路径信息，除到达目的地的最 佳路径外，任何其它信息均予以丢弃。同时路由器也把所收集的路由信息用 r i p 协议通知相邻的其它路由器。这样，正确的路由信息逐渐扩散到了全网。 【5 】 r i p 使用非常广泛，它简单、可靠，便于配置。但是r i p 只适用于小型 的同构网络，因为它允许的最大站点数为1 5 ，任何超过1 5 个站点的目的地 均被标记为不可达。而且r i p 每隔3 0 s 一次的路由信息广播也是造成网络的 广播风暴的重要原因之一。 武汉理工大学硕士学位论文 1 3 2o s p f 路由协议 8 0 年代中期，r i p 已不能适应大规模异构网络的互连，o s p f 随之产生。 它是i n t e r n e t 工程任务组( 1 e t f i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 的内部网关 协议工作组为i p 网络而开发的一种路由协议。3 0 s p f 是一种基于链路状态的路由协议，需要每个路由器向其同一管理 域的所有其它路由器发送链路状态广播信息。在0 s p f 的链路状态广播中包 括所有接口信息、所有的量度和其它一些变量。利用0 s p f 的路由器首先必 须收集有关的链路状态信息，并根据一定的算法计算出到每个节点的最短路 径，基于距离向量的路由协议仅向其邻接路由器发送有关路由更新信息。“” 与r i p 不同，o s p f 将一个自治域再划分为区，相应地即有两种类型的 路由选择方式：当源和目的地在同一区时，采用区内路由选择；当源和目的 地在不同区时，则采用区间路由选择。这就大大减少了网络开销，并增加了 网络的稳定性。当一个区内的路由器出了故障时并不影响自治域内其它区路 由器的正常工作，这也给网络的管理、维护带来方便。“ 1 3 3b g p 和b g p 4 路由协议 b g p 是为t c p i p 互联网设计的外部网关协议，用于多个自治域之间。 它既不是基于纯粹的链路状态算法，也不是基于纯粹的距离向量算法。它的 主要功能是与其它自治域的b g p 交换网络可达信息。各个自治域可以运行不 同的内部网关协议。b g p 更新信息包括网络号自治域路径的成对信息。自 治域路径包括到达某个特定网络须经过的自治域串，这些更新信息通过t c p 传送出去，以保证传输的可靠性。 为了满足i n t e r n e t 日益扩大的需要，b g p 还在不断地发展。在最新的b g p 一4 中，还可以将相似路由合并为一条路由。 1 4 本课题来源及研究意义 在q o s 的早期研究中，许多q o s 的研究着眼于调度，拥塞控制，资源 预留，而对q o s 路由研究得不多。近几年得研究表明网络q o s 多播路由的 算法对保证服务质量起到关键的作用。研究基于i n t e r n e t 的q o s 路由算法， 以获得较好的网络服务质量和高的网络资源利用率具有十分重要的研究意 义。” 4 武汉理一r 大学硕士学位论文 基于多播的音频视频流媒体应用如晚会和音乐会实况转播、i p 网络视 频会议、远程教学等都是i p 多播的重要应用领域。它们是通过摄录制作多 媒体文件，经编码设备编码后用多播方式以最小的带宽开销发送给希望接收 和观看这些内容的组用户，为了适应不同网络用户的连接带宽不同，其所能 支持的视频音频质量的差异，可以采用根据媒体带宽划分组地址或用户选 择接收方式解决。另外利用双向和n 向多播或者多多播地址方式还可以实现 交互式应用，可以进一步扩展多播的应用范围。现阶段我国宽带城域网的建 设发展较快，x d s l 、f t t x + l a n 、c a b l em o d e m 等宽带接入技术广泛采用， 为基于多播的流媒体应用提供了必要条件。另外，基于i p 多播技术还可以 开发聊天组、交互式仿真、大众游戏、网上路演等应用。目前国内外许多 i s p 和研究机构已在小范围内试验或部署了一些基于i p 多播的应用，i e t f 等组织也将i p 多播作为一个重要的研究领域，随着i p 网络功能和性能的不 断完善、多播技术和协议的改进成熟、带宽接入用户的逐渐普及，i p 多播 将会有更广泛的应用。” 目前，人们正期待着各种能满足o o s 的宽带服务，例如：视频点播、i p 电话、视频会议等等。而目前的i n t e r n e t 只能提供在带宽与延迟方面不提供 任何的保证的尽力而为的服务，这就意味着它只能尽力转发用户的数据包。 虽然这种服务非常适用于传统的应用，但是随着i n t e r n e t ，移动i n t e r n e t 等高 性能网络技术的不断发展演进，基于q o s 的路由协议、基于q o s 的多播路 由协议的设计理论与方法的研究，已经成为网络领域的一类重要的课题。 本文得到了国家自然科学基金项目( 批准号：6 0 1 7 2 0 3 5 ，9 0 3 0 4 0 1 8 ) 的资 助。 武汉理一 大学硕士学位论文 第2 章支持o o s 的多播路由理论 2 1 路由的基本原理 当i p 子网中的一台主机发送i p 分组给同i p 子网的另一台主机时， 它将直接把i p 分组送到网络上，对方就能收到。而要送给不同i p 于网上的 主机时，它要选择一个能到达目的子网上的路由器，把i p 分组送给该路由 器，山路由器负责把i p 分组送到目的地。如果没有找到这样的路由器，主 机就把i p 分组送给个称为“缺省网关( d e f a u l tg a t e w a y ) ”的路由器上。“缺 省网关”是每台主机上的一个配置参数，它是接在同一个网络上的某个路由 器端口的i p 地址。路由器转发i p 分组时，只根据i p 分组目的i p 地址的网 络号部分，选择合适的端口，把i p 分组送出去。同主机一样，路由器也要 判定端口所接的是否是目的予网，如果是，就直接把分组通过端口送到网络 上，否则，也要选择下一个路由器来传送分组。路由器也有它的缺省网关， 用来传送不知道往哪儿送的i p 分组。这样，通过路由器把知道如何传送的 i p 分组正确转发出去，不知道的i p 分组送给“缺省网关”路由器，这样 级级地传送，i p 分组最终将送到目的地，送不到目的地的i p 分组则被网络 丢弃了。目前t c p i p 网络，全部是通过路由器互连起来的，i n t e r n e t 就是成 千卜 万个i p 子网通过路由器互连起来的国际性网络。这种网络称为以路由 器为基础的网络，形成了以路由器为节点的“网际网“，在“网际网”中， 路由器不仅负责对i p 分组的转发，还要负责与别的路由器进行联络，共同 确定“网际网”的路由选择和维护路由表。路由动作包括两项基本内容：寻 径和转发。寻径即判定到达目的地的最佳路径，由路由选择算法来实现。由 于涉及到不同的路由选择协议和路由选择算法，要相对复杂一些。为了判定 最佳路径，路由选择算法必须启动并维护包含路由信息的路由表。其中路由 信息依赖于所用的路由选择算法而不尽相同。路由选择算法将收集到的不同 信息填入路由表中，根据路由表可将目的网络与下一跳的关系告诉路由器。 路由器问互通信息进行路由更新，更新维护路由表使之正确反映网络的拓扑 变化，并由路由器根据量度来决定最佳路径。“”这就是路由选择协议，例如 路由信息协议( r i p ) 、开放式最短路径优先协议( o s p f ) 和边界网关协议 6 武汉理一r 大学硕士学位论文 ( b g p ) 等。转发即沿寻径好的最佳路径传送信息分组。路由器首先在路由表 中查找，判明是否知道如何将分组发送到下一个站点( 路由器或主机) ，如果 路由器不知道如何发送分组，通常将该分组丢弃；否则就根据路由表的相应 表项将分组发送到下一个站点，如果目的网络直接与路由器相连，路由器就 把分组直接送到相应的端口上。这就是路由转发协议。路由转发协议和路由 选择协议是相互配合又相互独立的概念，前者使用后者维护的路由表，同时 后者要利用前者提供的功能来发布路由协议数据分组。下文中提到的路由协 议，除非特别说明，都是指路由选择协议，这也是普遍的习惯。 路由算法按照种类可分为以下几种：静态和动态、单路和多路、平等和 分级、源路由和透明路由、域内和域间、链路状态和距离向量。链路状态算 法( 也称最短路径算法) 发送路由信息到互联网上所有的结点，然而对于每个 路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。距离向量 算法( 也称为b e l l m a n f o r d 算法) 则要求每个路由器发送其路由表全部或部 分信息，但仅发送到邻近结点上。从本质上来说，链路状态算法将少量更新 信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由器。由 于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生 路出循环。但另一方面，链路状态算法要求比距离向量算法有更强的c p u 能 力和更多的内存空阃，因此链路状态算法将会在实现时显得更昂贵一些。除 了这些区别，两种算法在大多数环境下都能很好地运行。最后需要指出的是， 路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可 能采用多种度量来选择路由，通过一定的加权运算，将它们合并为单个的复 合度量、再填入路由表中，作为寻径的标准。通常所使用的度量有：路径长 度、可靠性、时延、带宽、负载、通信成本等。“” 2 2 多播路由技术 在计算机网络中，多播是目前研究最多，应用最广的连接方式。多播涉 及将同一信息从源接点传送至4 网络中的多个节点( 不一定是网络中的所有节 点) 。涉及多播技术的应用很多，如多媒体会议，远程教育，数据分发等。 视频会议应用需要多播的支持，就是说，只有加入会议的才需要视频数据， 而不能向所有的节点广播。这里介绍一下单播、广播、多播技术的优缺点： 单播技术是点到点的传输，如果有多个点需要就要传输多次；广播一次就可 以传输给所有的节点，但是对于不需要的节点也会收到相应的广播；而只有 武汉理工大学硕士学位论文 多播才能比较好地解决视频的需求，它可以一次传输给所有需要数据的节 点，而不会发给不需要数据的节点。和单播相比多播效率要高得多；和广播 相比，控制了网络流量，节省了带宽丌销。多播路由是网络层具备的功能， 它的特点主要体现在三个方面：第一，带宽。运用多播技术分发信息常常能 从本质上减少整个网络带宽的需求，与单薄技术( 点到点通信方式) 相比，其 带宽的需求不会随着用户数量的增多而增加。第二，服务器负载。采用多播 技术降低了服务器的负载。第三，网络负载。当将相同的内容传送给多个用 户时，多播能明显地减少带宽需求，带宽消耗的降低等同于路由器上的负载 降低。多播问题的关键在于多播路径的确定。实现多播的一般方法是建立多 播树。”多播树是根为源节点，且覆盖所有多播成员的一棵生成树，多播树 的优点在于，首先信息以并行方式沿着树枝发送到不同的多播成员，从而降 低了信息传递的延迟，其次信息的复制只在树枝分叉处上进行，因此网络中 需要传送的复制信息最少，从而节省网络带宽资源，减少拥塞。多播路由算 法主要用来建立一棵性能好的多播树。目前多播路由算法的研究大多都针对 无约束多播路由问题和时延受限多播路由问题。 2 2 1 多播组地址 在i p v 4 中，d 类地址( 从2 2 4 o o o 到2 3 9 2 5 5 2 5 5 2 5 5 ) 用于i p 多播。 多播组地址与单播地址不一样，它不是代表一个特定主机，一个多播组地址 代表该多播组中所有接收多播分组的主机或者路由器。如图2 所示，i p 多 播地址前四位( 二进制表示) 均是1 1 1 0 。 l八位组1八位组2八位组3八位组4 l1 1 1 0 x x x xx x x x x x x xx x x x x x x xx x x x x x x x 图2 1i p v 4 的d 类i p 地址格式 多播是一个开放的模型，任何人可以属于一个多播组，不需要授权认证； 非多播组成员可以向多播组中发送多播分组，多播组是动态的，任何主机可 以随时加入或者退出，而且主机可以加入多个多播组，源或者接收者都不能 得知该多播组的成员数量。 武汉理工大学硕士学位论文 2 2 2i g m p 协议 i n t e r n e t 组管理协议( i g m p ，i n t e r n e t g r o u pm a n a g e m e n tp r o t o c 0 1 ) 是最基 本的主机成员关系协议，一般用于路由器与其直接相连的主机之间进行有关 多播组成员状态的通信。它主要提供主机加入多播组、主机退出多播组、指 定组查询等功能。i g m p 采用查询一响应模式，i g m p 消息在i p 数据包内传送， 其t t i 。值为1 ，即i g m p 消息不会直接被路由器转送出本地子网。目前已经 标准化的有i g m p v l ( r f c l l l 2 ) 和i g m p v 2 ( r f c 2 2 3 6 ) 两个版本。” 加入多播组一当子网中某个主机希望加入到某一个多播组时，它通过立 即发送或者是在收到i g m p 多播路由器的成员关系查询消息后发送“成员关 系报告”消息，来通知其i g m p 多播路由器，并准备接收来自该多播组的多 播数据。当同一i p 子网中有多个主机希望加入同一个多播组时，多播路由 器只需要接收其中至少一个主机的报告即可，其他主机抑制自己的报告消 息。 离丌多播组一i g m p v l 和i g m p v 2 对处理主机离开的方式有些差别。在 i g b l pv l 中当主机离开某一个多播组时，它不会通知i g m p 多播路由器而悄 悄退出，多播路由器仍定时向i p 子网发送“成员关系查询”消息，如果i g m p 多播路由器的计时器超时但没有收到子网主机的“成员关系报告”消息时， 将不再向子网转发该组的多播信息，并从其分发树中删掉相关的多播路由 器。这种方式将存在一定的离开延迟时间。在i g m p v 2 中，对此进行了改进， 当主机离开某一个多播组时将立即发送离开组消息，子网多播路由器会马上 向i p 子网中发送组查询消息，查询组中是否还有活动的组成员，在没有收 到子网主机的应答后，就停发多播信息并从该多播组的分发树中删掉相关的 多播路由器。 2 2 3 多播转发路由 多播路由不同于单播路由。单播是通过判断目的主机的地址来进行转发 选路，单播路由由网络的拓扑结构所决定。对于多播，多播源是向多播组发 送数据包而不是单播模型中的具体的目的主机，多播路由器不可能根据i p 包中的目标地址来决定转发路径，多播路由是由多播分发树确定，多播转发 是通过判断源地址、使用r p f ( 逆向路径转发) 机制来实现。当多播数据包到 达路由器时，路由器对包作r p f 检查，即多播路由器检查所收到的多播数据 包的源地址，以确定该数据包经过了哪些接口，这些接口是否在从源到此的 9 武汉理工大学硕士学位论文 路径上：”如果该数据包是在可返回源主机的接口上到达的，则r p f 检查成 功，路由器将该数据包转发到输出接口表中的所有接口，否则r p f 检查失败， 丢弃该数据包。 2 2 4i p 多播技术的硬件支持 要实现i p 多播通信，要求介于多播源和接收者之间的路由器、集线器、 交换机以及主机均需支持i p 多播。目前，i p 多播技术已得到硬件、软件厂 商的广泛支持。 ( 1 ) 主机 支持i p 多播通信的平台包括w i n d o w sc e2 1 、w i n d o w s9 5 、w i n d o w s 9 8 、w i n d o w sn t4 和w i n d o w s2 0 0 0 等，运行这些操作系统的主机都可以 进行i p 多播通信。此外，新生产的网卡也几乎都提供了对i p 多播的支持。 ( 2 ) 集线器和交换机 目前大多数集线器、交换机只是简单地把多播数据当成广播来发送接 收，但一些中、高档交换机提供了对i p 多播的支持。例如，在3 c o m s u p e r s t a c k3 s w i t h3 3 0 0 交换机上可启用8 0 2 1 p 或i g m p 多播过滤功能，只 为已侦测到i g m p 数据包的端口转发多播数据包。 ( 3 ) 路由器 多播通信要求多播源节点和目的节点之间的所有路由器必须提供对 i n t e r n e t 组管理协议( i g m p ) 、多播路由协议( 如p i m 、d v m r p 等) 的支持。 当一台主机欲加入某个多播组时，会发出“主机成员报告”的i g m p 消 息通知多播路由器。当多播路由器接收到发给那个多播组的数据时，便会将 其转发给所有的多播主机。多播路由器还会周期性地发出“主机成员查询” 的i g m p 消息，向子网查询多播主机，若发现某个多播组已没有任何成员， 则停止转发该多播组的数据。此外，当支持i g m p v 2 的主机( 如w i n d o w s 9 8 2 0 0 0 计算机) 退出某个多播组时，还会向路由器发送一条“离开组”的 i g m p 消息，以通知路由器停止转发该多播组的数据。但只有当子网上所有 主机都退出某个多播组时，路由器才停止向该子网转发该多播组的数据。“7 3 使用多播路由协议，路由器可建立起从多播源节点到所有目的节点的多 播路由表，从而实现在子网间转发多播数据包。例如，协议独立多播( p i 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 e m o d e ) 和密集模式( d e n s e m o d e ) 。以c i s c o2 6 2 1 路由器为 1 0 武汉理：大学硕十学位论文 例，启用i p 多播转发功能的基本设置如下： c 2 6 2 1 ( c o n f i g ) # i pm u l t i c a s t - r o u t i n g 启动i p 多播，使路由器成为个多 播路由器。 c 2 6 2 1 ( c o n f i g ) # i n t f 0 0 配置快速以太网端口。 c 2 6 2 1 ( c o n f i g i f ) 撑i pp i md e n s e m o d e ( 或s p a r s e m o d e ) 启动p i m ，同时激活 i g m p 协议。 c 2 6 2 1 ( c o n f i g i f ) # i mf o 1 配置快速以太网端口。 c 2 6 2 1 ( c o n f i g i n 拌i pp i md e n s e - m o d e ( 或s p a r s e m o d e ) a 2 2 5 多播路由协议现状 目前已经提出很多的协议，而且有不少已经应用于i n t e r n e t 网络。根据 网络中多播组成员的分布，多播路由协议可分为密集模式多播路由协议和稀 疏模式多播路由协议两种基本类型。根据多播树的实现方式，它又可以分为 基于源的多播生成树路由协议和基于核( 又称为汇集点，r e n d e z v o u sp o i n t ) 的多播生成树路由协议。密集模式多播路由协议假设多播组成员密集地分布 在网络中，也就是说，网络大多数的子网都至少包含一个多播组成员，而且 网络带宽足够大，它依赖于广播技术将数据“推”向网络中所有的路由器。 密集模式路由协议包括距离向量多播路由协议( 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 0 s p f ，m u l t i c a s t o p e ns h o r t e s tp a t hf i r s t ) 和协议独立多播密集模式协议等。稀疏模式多播路 由协议则假设多播组成员在网络中是稀疏分散的，并且网络不能提供足够的 传输带宽，在这种情况下，广播就会浪费许多不必要的网络带宽从而可能导 致严熏的网络性能问题，必须依赖于具有路由选择能力的技术来建立和维持 多播树。稀疏模式主要有基于核，0 树的c b t 协议和协议独立多播稀疏模式 p i m s m 协议。m 1 225 1 密集模式多播路由协议 ( 1 ) 距离向量多播路由协议( d v m r p ) 第一个支持多播功能的路由协议就是距离向量多播路由协议。它已经被 广泛地应用在多播骨干网 , i b o n e 上。d v m r p 为每个发送源和目的主机组构 建不同的分布树。每个分布树都是一个以多播发送源作为根，以多播接受目 的主机作为叶的最小扩展分布树。这个分布树为发送源和组中每个多播接受 者之间提供了一个最短路径，这个以“跳数”为单位的最短路径就是 武汉理工大学硕士学位论文 d v m r p 的量度。当一个发送源要向多播组中发送消息时，一个扩展分布树 就根据这个请求而建立，并且使用“广播和修剪”的技术来维持这个扩展分 布树。 要简单的描述d v m r p ，我们首先假设网络中所有的路由器都支持 d v m r p 协议。使用d v m r p 的前提是假设网络中所有的主机都是多播组中的 一部分。子网中指定的路由器( 就是用来处理子网中所有主机的路由的路由 器) 先向所有的临近路由器发送一个多播包。这些路由器有选择性的将这个 数据包向前传送，直到这个数据包传送到多播组中的每个成员。 扩展分布树构建过程中的选择性发送多播包的具体运作是：当一个路由 器接收到一个多播包，它先检查它的单播路由表来查找到多播组发送源的最 短路径的接口，如果这个接口就是这个多播包到达的接口，那么路由器就将 这个多播组信息记录到它的内部路由表( 指明该组数据包应该发送的接口) ， 并且将这个多播包向除了接受到该数据包的路由器以外的其他临近路由器 继续发送。如果这个多播包的到达接口不是该路由器到发送源的最短路径的 接口，这个包就被丢弃。这种机制被称为“反向路径广播”( r e v e r s e p a t h b r o a d c a s t i n g ) 机制，保证了构建的树中不会出现环，而且从发送源到所有接 受者都是最短路径。这是这个协议中的广播技术部分。“ d v m r p 实际应用的路由算法使用了单播路由协议的某些信息，比上面 描述的路由算法能更加具有选择性的进行路由( 这表明d v m r p 必须包含它 自己的单播路由协议) 。一个d v m r p 路由器( 暂称为m r l ) 的单播路由表中 的某些信息使得它可以判定一个临近的d v m r p 路由器( 暂称为m r 2 ) 是否能 够将m r l 确认为返回多播源的最短路径。这使得只有m r 2 能够被构建入多 播树中时m r l 才传送多播包到m r 2 。这种机制能够很可观的减少构建树时 的广播消息。 协议的修剪功能可以将不能到达多播组成员的扩展分布树的分枝拆除。 在主机和其直接相邻的路由器之间运作的i n t e r n e t 组管理协议( i g m p ) 可以 用来维持路由器中的组成员关系数据。当一个路由器发现在它所属的分枝上 没