（通信与信息系统专业论文）ip组播技术及iptv在epon系统中的实现.pdf

上海大学攻读硕士学位论文 m 组播技术及瑾t v 在e p o n 系统中的实现 摘要 随着宽带视频应用的迅速发展和宽带接入用户的爆炸式增长，口组播技术 已成为口骨干网和i p 城域网的重要传输技术之一。i p 组播实现了网络中点到多 点的高效数据传输，能够有效地节约网络带宽和降低网络负载。然而，在以太无 源光网络( e t h e r n c tp o n ) 中，若组播数据以广播方式发送给各光网络o n u 单 元和用户，会大大增加e p o n 网络的负担，在组播业务大量存在的情况下，甚 至可能导致整个e p o n 系统瘫痪。本文研究了从核心网到p o n 接入网的组播通 信方式，全文的主要内容由三部分组成，具体如下： 第一部分首先介绍了i p t v 的系统组成、关键技术和发展现状，分析了i p t v 业务采用组播技术的必要性和特殊性。然后在研究各种基于q o s 约束的p 组播 算法基础上，总结链路选择函数在组播路由算法中的作用和重要性。并由此，提 出了一种基于链路选择函数的新型目的地驱动的组播路由算法( i d d s p ) 。 第二部分重点研究了e p o n 系统中组播实现方案。首先分析了二层交换机 中i g m p 监听、代理协议的运行机制，提出了e p o n 系统中i g m pp r o x y i n g 功能 的实现方案。然后在总结e p o n 中各种组播方案优缺点的基础上，提出了一种 基于l l i d 的e p o n 系统组播实现方案，该方案在o l t 和o n u 上同时部署监听 ( s n o o p i n g ) 和代理( p r o x y ) 功能，并且通过将组播v l a n 映射到l l i d ，在 r s 子层就可以根据组播l l i d 准确过滤数据。 第三部分首先总结各种w d m p o n 系统方案及其优缺点，然后从降低 w d m ，p o n 系统成本的角度出发，总结了三种混合p o n 系统结构，并指出各系 统的优缺点。最后考虑到混合p o n 系统的多波长特性，提出了用广播波长通道 传输广播组播业务的实现方案，该方案大大减少了单播通道处理组播数据的负 担，合理有效地利用了系统中的波长资源。 关键词：e p o n ，组播，混合p o n ，m t 、，i g m p 监听代理 上海大学攻读硕士学位论文i p 组播技术及口w 在e p o n 系统中的实现 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dp o p u l a r i z a t i o no f b r o a d b a n dv i d e oa p p l i c a t i o n s ， i pm u l t i c a s th a sb e c o m ef i l l i m p o r t a n tt r a n s m i s s i o nt e c h n o l o g yi n i pb a c k b o n e n e t w o r k i pm u l t i c a s tr e a l i z e sah i g h l ye f f i c i e n tp o i n t - t o m u l t i p o i n td a t at r a n s m i s s i o n t oe f f e c t i v e l ys a v en e t w o r kb a n d w i d t ha n dr e d u c en e t w o r kl o a d h o w e v e r , i nt h e e t h e r n e tp a s s i v eo p t i c a ln e t w o r k , m u l t i c a s td a t aa r eb r o a d c a s tt ot h eo n um o d u l e s a n du s e i st h a tw i l lg r e a t l yi n c r e a s et h eb u r d e no fe p o n ，i nt h ep r e s e n c eo fal a r g e n u m b e ro f m u l t i c a s td a t a , t h i se v e nl e a d st op a r a l y s i so f t h ee n t i r ee p o ns y s t e m t h i s p a p e rs t u d i e sm u l t i c a s tc o m m u n i c a t i o nf r o mt h ec o r en e t w o r kt ot h ep e n a c c e s sa n d c o n s i s t so f t h r e ep a r t s ，a sf o l l o w s ： t h ef i r s tp a r ti n t r o d u c e st h e 口t 、，s y s t e mc o m p o n e n t s k e yt e c h n o l o g i e sa n d d e v e l o p m e n ts t a t u s a n da n a l y z e sn e c e s s i t ya n dp a r t i c u l a r i t yo fm u l t i c a s ti n 口t v t h e nb a s e do nk i n d so fq o s c o n s t r a i n e di pr o u t i n ga l g o r i t h m s ，t h er o l ea n d i m p o r t a n c eo fl i n ks e l e c t i o nf u n c t i o na r ec o n c l u d e d a sr e s u l lan e wd e s t i n a t i o n d r i v e nm u l t i c a s tr o u t i n ga l g o r i t h m ( i d d s p ) i sp r e s e n t e d t h es e c o n dp a r tf o c u s e so ni m p l e m e o t a t i o no f m u l t i c a s ti ne p o n f i r s t ，b a s e do n a n a l y s i so fi g m ps n o o p i n ga n dp r o x yo ft h el a y e r2s w i t c h , i g m pp r o x yo fe p o n s y s t e mh a sb e e np r e s e n t e da n da n a l y z e d t h e n , a f t e rt h ec o n c l u s i o no f t h ea d v a n t a g e s a n dd i s a d v a n t a g e so f v a r i o u sm u l t i c a s ti m p l e m e n t a t i o ni ne p o n ，t h i st h e s i sp r e s e n t sa n e wm u l t i c a s ti m p l e m e n t a t i o nb a s e do nl l i da n dt h i si m p l e m e n t a t i o nr e a l i z e si g m p s n o o p i n g p r o x yo no l ta n do n u b ym a p p i n gm u l t i c a s tv l a ni dt ol l i d ，o n u c a n a c c u r a t e l yf i l t e rd a t aa c c o r d i n g t ol l i da tt h er ss u b - l a y e r t h et l l i r dp a r tf i r s t l yi n t r o d u c e sv a r i o u sw d m - p e ns y s t e ma n di t sa d v a n t a g e s a n dd i s a d v a n t a g e s t h e nf r o mt h ev i e wo f r e d u c i n gt h ec o s to f w d m p e n ，t h i st h e s i s s u m su pt h r e eh y b r i d - p e ns t r u c t u r e sa n dp o i n t so u tt h ea d v a n t a g e sa n dd i s a d v a n t a g e s o fe a c hs y s t e m f i n a l l y , g i v e nm u l t i w a v e l e n g t hc h a r a c t e r i s t i c so fh y b r i d p e n s y s t e m s an e w b r o a d c a s t m u l t i c a s ti m p l e m e n t a t i o nh a sb e e np r o p o s e db yt h eu s ee r a b r o a d c a s tw a v e l e n g t h t h i si m p l e m e n t a t i o ns i g n i f i c a n t l yr e d u c e st h eb u r d e no fd a t a p r o c e s s i n go fu n i e a s tc h a n n e la n df u l l yu t i l i z e st h ew a v e l e n g t hr e s o u r c e s i nt h e h y b r i d p e ns y s t e m s k e yw o r d s ：e p o n ，m u l t i c a s t , h y b r i d - p o n ，i p t v , i g m ps n o o p i n g p r o x y u 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文 及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容。 ( 保密的论文在解密后应遵守此规定) 签名：辈垒整导师签名旌燧日期：丝! 乞生： 上海大学攻读硕士学位论文 m 组播技术及i p t v 在e p o n 系统中的实现 第一章绪论 1 1i p 组播路由的概念和算法综述 随着全球互联网的迅猛发展，上网人数正以几何级数快速增长，以因特网技 术为主导的数据通信在通信业务总量中的比例迅速上升，同时网上应用业务越来 越多，特别是视音频压缩技术的发展和成熟，使得网上视音频业务成为i n t e m e t 上的重要业务之一。在i n t e r n e t 上实现的网络电视( i p t v ) 、视频点播( v o d ) 、 可视电话、视频会议等视音频业务与一般业务相比，有着数据量大、时延敏感性 强、持续时间长等特点。因此有效地传输和解决视音频业务所要求的网络利用率 高、传输速度快、实时性强的问题，就要采用不同于传统单播、广播机制的转发 技术及q o s 服务保证机制，而口组播技术就是解决这些问题的关键。 1 1 1i p 组播路由的基本概念 口组播技术是一种允许一台或多台主机( 组播源) 发送单一数据包到多台 主机( 一次的、同时的) 的t c p i p 网络技术。组播作为一点对多点的通信，是 节省网络带宽、降低网络负载的有效方法之一。 在口组播路由实现的过程中涉及到四个问题： i p 组播数据发送给谁的问题。 口组播的地址是采用d 类口地址确定组播组，其范围是从2 2 4 0 0 0 到 2 3 9 2 5 5 2 5 5 2 5 5 ，每个组播地址代表一个组播组。发送者在发送一份口组播数 据包之前，确定一个合适的组播地址作为发送的目的妒地址。 局域网段的用户主机如何接收口组播数据的问题。 局域网段的用户主机接收m 组播数据的问题取决于两方面的因素：一是用 户主机通过发送i n t e r n e t 组管理协议i g m p 报文到本网段上的路由器，申请加入 某一组播组，并不断侦听和接收该组播数据。二是局域网路由器根据接收到的组 播申请报文，转发并转换相应的组播数据包的数据链路层地址，发送给相连的局 域网。 6 上海大学攻读硕士学位论文i p 组播技术及i p l v 在e p o n 系统中的实现 用户主机如何通知组播路由器离开某一组播组的问题。 如果用户主机使用的是i g m p v 2 ，会主动地通知路由器离开；如果使用的是 i g m p v l ，离开某一组播组不会通知路由器，这时路由器要在一定时间后向本局 域网段发送查询报文，相应组播组中的主机发送应答报文，若无用户应答，路由 器就认为不再有接收者，不会再向该网段转发组擂信息。 组播路由器之间如何建立组播转发树的问题。 根据所使用的组播路由协议建立组播转发树。根据该转发树进行组播信息的 转发，当某个处于转发树中的路由器收到一个组播信息后，对要转发的组播包进 行拷贝和转发。如果路由器为最后一跳，组播包就以广播的方式传送到该网段中 各主机接收者。 综上所述，要实现口组播传输，口组播模型主要有3 个特点： 兼容口服务。使用u d p ( u s c rd a t a g r a mp r o t o c 0 1 ) 协议传送组播包，提 供尽力而为( b e s t - - e f f o r t ) 服务。 开放的组。组播源节点无须知道组播组成员的信息，也不要求主机一定 是组播组的成员。 动态的组。任意节点可以随时加入或离开组播组。 1 1 2 组播路由问题的定义与分类 1 1 2 1 组搔路由问题的网络模型 首先我们必须明确如下两个概念 1 i ： ( 1 ) 网络总代价：在组播路由计算过程中，由于组播机制自身的特点，其业 务流只在分叉节点处进行复制，而在公用路径上能做到资源共享，因此网络的总 代价应为所构造的生成树的所有边的代价之总和，而非源点到所有目的点的代价 的总和。 ( 2 ) 网络时延：在组播生成树中，网络时延指的是从源点到各目的结点时延 的最大值。此外也必须考虑到这样一个现象，在很多实时应用过程中，往往存在 一个时间限制，并不需要我们到每个目的地的路径时延最短，但必须保证从源点 到任一端点的时延都不超过一个界限。 7 上海大学攻读硕士学位论文m 组播技术及i p t v 在e p o n 系统中的实现 从而，此问题就变为给定一个组播源点和一系列目的结点，要求在满足任一 源点到目的结点时延均不超过某一时延上限的条件下，求出一棵总代价最小的 s t e i n e r 树，即受限s t e i n e 树( c s t ，c o n s t r a i ns t e i n et r e e ) 问题。它可模型化为 一个图论问题，网络相当于一简单无向连通图g = ；v 为图中点的集合，代 表组播通信的所有端点，并指定其中的某点s 为源点；e 为图中所有边的集合， 代表实际通信过程中的所有链路。对于g 中的每一条边( 巧) e ，均对应两个正 实数加权值c o s t ( i j ) 或简记为c ( i j ) ，d e l a y ( i o ) 或简记为d ( i j ) 。c o s t ( i d ) 定义了边( 功) 的代价，其值与该边的资源使用情况有关。d e l a y ( i , j ) 定义了边( i j ) 的信息传送延 时，该延时包括排队延时、交换延时和传输延时等。组播路由问题可描述为在图 g 中寻找一棵包含发送节点及所有接收节点的c s t 树t = ( 巧，岛) ，( r g ) 。 并满足网络总代价最小化： r a i n ( c o s t ( i ，_ ，) ) ( f 历西 及网络时延约束条件： c l e t a y ( i ，) a ，v v m ( f ，j ) e 异( j ， 其中为时延上限( 或称时延约束) ，该参量定义了实时业务的传送延时要求。 毋( s ，v ) 为树t 中从发送源s 到接收点v 的路径，m 为接收点的集合。 1 1 2 2 组播路由算法的问题描述1 2 】 1 、优化目标：通常以最小化组播树的代价( c o s t ) 的形式定义，代价可以 是整个组播树使用的带宽或者其他网络利用率的单调非减函数。 2 、约束条件：可以分为两类： 链路约束。链路约束是路由选择时对链路的一些限制条件。例如，要求 某条链路的带宽大于等于某个预定值。 树约束。树约束又可分为两种情况。一种是沿着组播树从源到接收者的 路径的限制条件，例如，从源到所有接收者的路径的端到端的延迟上界；另一种 情况是从相同的源到任意两个不同的接收者的路径之间区别的限制条件，例如， 两个不同的接收者从同一个源接收时端到端延迟之间的抖动。 根据树约束如何从链路参数中获得，树约束又可以进一步分成三类： 可加性树约束。例如，从节点u 到节点v 的端到端的延迟c l ( u , v ) 等于路 径上每条链路的延迟之和。 可乘性树约束。例如，从节点u 到v 的端到端的转发概率1 - - p l ( u ，v ) 等 于路径上每条链路的转发概率1 一p l ( 功) 之乘积，其中p l ( i j ) 表示链路( i j ) 的包丢 8 上海大学攻读硕士学位论文m 组播技术及i p t v 在e p o n 系统中的实现 失率。 最小性树约束。例如，从节点u 到节点v 路径上的最小带宽等于该路径 上带宽最小的链路的带宽。 3 、组播路由算法的问题定义：给定一个组播组m 、一组优化目标函数o 和 q o s 约束条件c ，组播路由的功能就是根据网络拓扑结构和当前的网络状态建 构一棵使目标函数最优的组播树t 。q o s 约束条件可以包括端到端的延迟上界， 延迟抖动上界，最小带宽，丢失概率等。 1 1 2 3 组播路由算问题的分类 依据不同的q o s 约束和不同的优化目标函数，组播路由问题可分为以下几 判3 】： l 、单链路约束问题：在寻找可行的组播树过程中考虑单个链路约束( 如基 于带宽约束路由问题) ； 2 、多链路约束问题：在构建可行的组播树过程中考虑多个链路约束( 如基 于带宽及缓存约束的路由问题) ； 3 、单树约束问题：在构建可行的组播树时考虑单个树约束( 如基于端到端 延时约束的路由问题) ； 4 、多树约束问题：在构建可行的组播树时考虑多个树约束( 如基于延时及 延时抖动约束的路由问题) ； 5 、链路及树约束问题：在构建可行的组播树时考虑一个链路约束及一个树 约束( 如基于延时及带宽约束的路由问题) ； 6 、链路最优化问题：使用链路最优化函数构建最优的组播树( 如求组播树 上链路带宽最大的路由问题) ； 7 、树最优化问题：使用树最优化函数构建最优的组播树( 如组播树费用最 小化问题) ，这类问题又称为s t e i n c r 树问题； 8 、链路约束链路最优化问题：使用链路最优化函数构建满足一个链路约束 的最优化组播树( 如基于带宽约束的缓存最优化问题) ； 9 、链路约束树最优化问题：使用树最优化函数构建满足一个链路约束的最 优化组播树( 如基于带宽约束s t e i n e r 树问题) ； 1 0 、树约束链路最优化问题：使用链路最优化函数构建符合一个树约束条件 的最优化组播树( 如基于延迟约束的带宽最优化问题) ； 1 1 、树约束树最优化问题：使用树最优化函数构建符合一个树约束条件的最 优化组播树( 如基于延迟约束的s t e i n c r 树问题) ； 1 2 、链路约束及树约束树最优化问题：使用树最优化函数构建符合一个链路 9 上海大学攻读硕士学位论文碑组播技术及i p l v 在e p o n 系统中的实现 约束和一个树约束条件的最优化多播树( 如基于带宽及延迟约束s t c i n c r 树问题) 。 通过从网络拓扑图中删去不满足约束条件的链路，第1 、2 类问题可以很容 易处理。w a n g 和c r o w e r o f f 已证明寻找一条路径使之满足两个或多个相互独立 的相加和或相乘的约束条件以及它们的任意组合是n p 完全( n p - - c o m p l e t e ) 的【4 1 ，因此第3 、5 类问题在多项式时间内是可解的，而第4 类问题则是n p 完全 的问题。文献 5 1 针对第6 类问题提出了一个多项式复杂度的算法。如果从网络 拓扑结构中移去不满足约束条件的链路，则第8 、1 0 类问题可转化为第6 类问题， 因此第8 、1 0 类问题在多项式时间内也是可解的。而第7 类问题( s t e i n e r 树问题) 和第9 、l l 、1 2 类问题( 基于约束的s t e i n e r 树问题) 已被证明是n p 完全的。 1 1 3 组播路由算法综述 目前，针对不同的基于q o s 约束的组播路由问题，已提出许多相应的路由 算法1 6 j 。 1 、最短路径树算法 最短路径算法是使组播树中从源节点到目的节点的每条路径上链路权值之 和最小。若所有链路的权值均为1 ，则算法所获得的组播树即为最小跳数( h o p ) 树；若权值代表链路延时，则算法将获得一棵最小延时树。b e l l m a n - f o r d 算法和 d i j k s t r a 算法是两个最著名的最短路径算法，其时间复杂度分别为o ( n 3 ) 和 o ( n 2 1 。最短路径算法可用来解决树约束问题( 例如基于延时约束的组播路由问 题) 。 2 、最小生成树算法 最小生成树是一棵覆盖图中所有节点并且树权重最小的树。著名的集中式最 小生成树算法是p r i m 算法，而g a l l a g e r 等则提出了解决最小生成树问题的一个 分布式算法。在p r i m 算法中，从任意一个根节点开始构建整棵树，直到其扩展 到网络中所有节点。在每一步中，连接已选择节点与末选择节点的权重最小的边 被加入到树中。算法采用了贪婪策略，在树的增长过程中，每次选择的边都是使 树权重增加最少的边。最小生成树算法可用来解决树的最优化问题。 3 、s t e i n e r 树算法i 刀 基于s t e i n e r 树的组播路由问题是构建一棵总费用最小的组播树。如果组播 树包含了图中所有节点，则s t e i n e r 树问题便转化为最小生成树问题。s t c i n c r 树 算法可用来解决树最优化问题，但对于有约束的应用，该类算法却很难满足端到 端的约束条件。w i n t e r y 和h w a n g 分别深入研究了启发式s t e i n e r 树算法。s a l a m a 和r e e v e s 等通过对已有的启发式算法的大量仿真指出由k o u m a r k o w s l d 和 1 0 上海大学攻读硕士学位论文 伊组播技术及i p t v 在e p o n 系统中的实现 b e r m a n 提出的k m b 算法具有较好的性能，是一个较为有效的算法，其所获得 的组播树的平均费用仅高于s t e i n e r 树费用的5 ，而其算法的时间复杂度为 d ( 1 g | 1 矿1 2 ) 。 k m b t 8 1 ( 由k o u 、m a r k o w s k i 和b e r m a n 提出) 算法的主要思想如下： 利用原始的网络图g 产生一个新的完全图h 建立h 的最小生成树u 把u 中的所有节点转换成其等价的最短路径图v v 中，用最小生成树算法建立一棵生成树 去掉非目的叶子节点，得最终树t 完全图h 是一个只包含组播点的完全图，而完全图中边的代价即为原图中 相应节点间的最短路径的代价。然后最小生成树算法被应用到完全图上，再将最 小生成树上的边用原图中相应的最短路径代替，即求得近优s t e i n e r 树。偶尔会 有扩展的结果不是树，而是带有环路的图，这些环路能够被再一次运用最小生成 树算法而消除。 4 、q o s 约束s t o n e r 树算法 q o s 约束s t e i n e r 树算法就是根据给定的q o s 参数，选择有足够网络资源的 链路，构建一棵从源点到多个目的节点的最小费用的组播树，来传送组播数据。 根据约束条件的不同，基于服务质量的s t e i n e r 树算法问题可分为时延约束的组 播路由问题，带宽约束的组播路由问题，时延抖动约束的组播路由问题等。其中， 带时延约束的组播路由算法往往更能够满足现实的要求，特别对于一些具有实时 要求的应用来说是如此。到目前为止，己经提出一些此类算法，在此论文中选择 了几个最具有代表性及特点的算法论述如下： b s m a 算法 b s m a 算法( b o u n d e ds h o r t e s tm u l t i c a s ta l g o r i t h m ) 是由q i n gz h u 等人提 出的( 9 1 ，是一种所生成树代价最小的时延约束组播路由优化算法。这一算法的主 要特点是：( 1 ) 对不同的目的节点，其时延约束条件可以不同：( 2 ) 与k p p 算法相 比，其链路代价值、链路时延值可以是任意实数；( 3 ) 与以往算法一次性通过不同， b s m a 算法可以重复执行，使组播树的代价达到最小。 b s m a 算法首先在给定的源节点与目的节点之间计算出一棵最小时延树，然 后在不违背时延约束的条件下，用不在树上的低代价超边( “超边”是树上两个 分枝点之间的一条路径，它或者连接两个组播节点，或者连接一个组播节点和一 个分枝节点) 去替代在树上的超边，直到树的总代价不能进一步削减为止。b s m a 算法使用求k 条最短路径的算法去发现低代价的超边。k 的值预先不能确定，由 算法的运行结果来决定，这样，在大的稠密的网络中k 的值也许非常大，很难达 到可以接受的运行时间。但是b s m a 算法总是能发现一棵受时延约束的s t e i n e r 上海大学攻读硕士学位论文m 组播技术及叮v 在e p o n 系统中的实现 树( 如果它存在的话) ，因为它开始于一棵最短时延路径树( l d 树) 。在运行b s m a 算法时，可以折衷树的代价来获得较快的运行速度，这或者通过减少阶数k ，或 者通过限制超边替换的数量来达到。 虽然b s m a 算法的时间复杂度比较高，可是它却能获得最好结果的近优解。 c d k s 算法 q s u n 和 l l a n g c n d o e r f e r 提出了一种受时延约束的最短路径算法，由于该算 法是基于d i j k s t r a 最短路径算法，因此，称之为c d k s 算法【1 0 ( c o n s t r a i n e dd i j k s t r a h e u r i s t i c ) 。c d k s 算法是一个综合性能比较均衡的算法，一方面，它的时间复 杂度不高；另一方面，它的解的质量基本可以接受。它的基本思想是：首先用 d i j k s t r a 算法计算出一棵无约束的最小代价树，然后判断这棵树上从源节点到成 员节点的时延是否满足时延约束条件，若不满足时延约束，则再用d i j k s t r a 算法 计算最小时延树。最后，合并这两棵树，并消除可能存在的回路。 算法主要步骤如下： ( 1 ) 尝试去计算一棵最小代价生成树t i = ( v 1 ，e 1 ) ，它以源点为根，同时跨 越尽可能多的目的节点，计算中使用d i j k s t r a 的最短路径算法，但产生的每条路 径均满足时延约束。 ( 2 ) 计算一棵最短时延路径树t 2 = ( v 2 ，e 2 ) ，它跨越所有t l 中没有包含的目 的节点。 ( 3 ) 组合t 1 与t 2 而得到一棵多播树。 注意在组合t 1 与1 r 2 时也许会产生环路，在最坏的情况下，t l 中所有边必 须被移去。如果存在的满足时延约束的组播树，c d k s 算法一定能找到。 k p p 算法 k p p 算法【1 1 1 是最早解决受时延约束的组播路由问题的启发式算法，它假设链 路的时延和时延约束条件为正整数，而链路的代价为任意正实数。该算法的主 要思想是：首先构造满足时延要求的完全图，然后在完全图中用最小生成树算法 得到一棵最小生成树，再用原始图中的具有时延约束的最小代价路径替换生成树 中的边，并移去相应的回路，最后得到组播树。 下面描述k p p 算法的主要步骤： ( 1 ) 构造完全图g ，其中完全图g 中的顶点是集合s u m 的中的节点，完全图 g 中的边是这些节结点之间的满足时延约束的最短路径。 ( 2 ) 在时延约束下求完全图g 的最小生成树。与p r i m 算法相似，每次将代价 最小的边加入到生成树，但各边的代价按如下的规则取值： 如d = 曲翟汁州 k a 上海大学攻读硕士学位论文 口组播技术及i p t v 在e p o n 系统中的实现 厶( 叩) = o 。篡圳蜘和一k a 其中f ( u ，v ) 是链路选择函数，c “w ) 是完全图g 中边( v ，w ) 上的代价，d ( v ，w ) 是完 全图g 中边( v ，w ) 上的时延。 ( 3 ) 把生成树的边还原成具有时延约束的最小代价路径。 ( 4 ) 扩展后的路由树不一定是真正的路由树，因为它可能含有回路。故算法 在扩展过程中必须消除存在的回路，最终得到一棵满足时延需求的组播树。k p p 算法的时间复杂度主要由寻找完全图的过程决定，在最坏的情况下时间复杂度为 d ( 知3 ) 。如果的值是固定的，并且链路上的时延和时延约束都是正整数，以及 存在满足时延约束的组播树，那么l ( p p 算法能够在线性时间找到这样的树。 1 1 4 组播路由算法研究中存在的问题 尽管己经提出了许多组播路由算法，但仍然没有形成统一的标准，现有的算 法在目标和机制上存在很大的差异。由于组播路由表现为一个非常动态化的问 题，如何设计一个有效的算法以适应这种动态性仍然有待探讨。探索的前提之一 就是弄清目前组播路由算法研究中存在的主要问题。 l 、连接成功率有待提高 目前所有投入运行的组播路由协议是不支持q o s 的( 如d v m r p 、p i m 、 m o s p f 等) ，这些协议不考虑用户的q o s 请求，往往通过最短路径把新成员连 接到组播树上，因此当新成员的加入请求带有多个q o s 参数时，最短路径可能 在带宽、丢包率、延时抖动，甚至在延时上不能满足加入者的要求。而在各种己 经提出的q o s 组播路由协议中，采用单路径策略的算法连接成功率也有限，特 别在网络负载较重，资源竞争加剧时，单路径算法的成功率会进一步下降。 鉴于上述观察，一些学者基于理论和试验分析认为单路径算法不能很好地支 持q o s 。多路径路由算法较单路径路由算法在支持q o s 、提高连接成功率、缩短 加入时间等方面有较大的优势，但它的控制报文开销较大，如果能找到有效办法 降低这种开销，多路径路由是更有前途的算法。 2 、片面优化路由 组播路由优化有两个方向，一个是优化组播路由的网络费用( n e t w o r k s c o s t s ) ，另一个是优化目的费用( d e s t i n a t i o n c o s t ) 。已有的组播路由算法要么强 调网络费用优化，要么强调目的费用优化，考虑综合优化的研究尚不多。 3 、算法或协议在实际部署上存在困难 口组播从提出到现在已经十多年了，目前它面临所谓的”慢启动”( s l o w 上海大学攻读硕士学位论文 毋组播技术及i p t v 在e p o n 系统中的实现 t a k e o f f ) 问题u ”。 这里面存在很多原因，除了地址分配、域间组播路由的困难外，很多新提出 的组播路由算法和协议在实际部署上存在困难。一些协议要求对标准路由协议作 太多的改动，另一些协议则缺乏动态性，它们要求在整个网络传播成员关系或者 在计算路由之前知道全部成员节点的地址，这是很不现实的，也不符合口组播 模型的基本特征一组播的动态性。目前研究人员多半倾向把组播协议建立在现存 的标准单播路由协议基础上，因为这样作有助于减少组播协议的复杂性，加快组 播的部署，降低对现存网络结构的影响【1 3 1 。 4 、尚未形成q o s 组播路由的标准 前面己经提到，很多q o s 组播路由问题是n p 完全问题，因此发展了若干启 发式算法，但是由于追求的目标不同，各种算法之间存在很大的差异。所以，在 计算效率、控制报文开销、节点存储开销、信息老化、部署的难易程度、组播树 的性能等等方面，仍然有很大的探索空间。 面对上面这些问题，分布式算法是一个合乎逻辑的选择。因为集中式算法虽 然具有无环、控制方便的特点，但它往往要求路由器了解全局拓扑和状态信息， 这使得集中算法的规模伸缩性较差，计算负担也较重，而且在整个网络传播状态 信息甚至成员关系信息是不明智的，因为这加重了路由器的负担，通信量对网络 的冲击也很大。分布式算法则可以有效分摊计算负担，便于采用基于局部信息的 策略，所以，分布式算法的规模伸缩性比较好，但容易导致环的出现。如果能够 处理好环问题，分布式算法有更好的发展前途。 目前组播路由算法的困境主要体现在： 第一是算法复杂。一些算法时间复杂度的阶数为三次方以上，如由m e h r d a d p a r s a 1 4 】提出的限乔最短组播算法、b s m a 算法，有的算法甚至还是指数性时间 的，如k o m p e l l a 等提出的k p p 算法；复杂性的另一个方面是算法本身结构的复 杂，算法过于复杂，将导致实现上的困难，特别是在分布式的条件下。 第二是由于时延约束的存在，目前的一些算法仍然脱离不了最短路径算法。 有的算法在时延无法满足时就用最短路径来代替，而有的算法则是在最短路径树 的基础上进行改造，以减小代价。 第三是一些不依赖于最短路径的算法，由于在求解路由过程中发生阻塞，将 导致回溯或试探等过程的出现，这又是我们所不希望看到的，因为回溯过程不但 导致运行时间变长，而且会带来无法预见性，这在分布式的情况下是无法容忍的。 总之，组播路由算法和协议的研究仍然相当热门。由于组播路由算法有丰富 的类型，组播协议也表现出不同的形式，这些不同类型的算法和不同形式的协议 相互交叉组合可以产生很多种不同的组播方案，它们强调不同的需求，针对不同 的目标，使得组播路由研究呈现出蔚为大观的多样性和复杂性。 上海大学攻读硕士学位论文m 组播技术及口t v 在e p o n 系统中的实现 1 2e p o n 系统研究概述 1 2 1e p o n 的网络体系结构 现代主流的光纤接入网以太无源光网( e p o n ) 由o l t 、o n u 、o s 三部 分组成。o l t ( o p i l e a ll i n e t e r m i n a l ) 称为光线路终端，一般放在中心机房( c o ) 。 o n u ( o p t i c a ln e t w o r ku n i t ) 称为光网络单元，一般放在用户端。o s ( o p t i c a l s p l i t t e r ) 称为无源光纤分路器，是一个连接o l t 和o n u 的无源器件。 在一个e p o n 系统中，o l t 既是一个交换机又是一个多业务提供平台 ( m s p p ) ，它提供面向无源光纤网络的光纤接口，是整个e p o n 系统的核心部 件。主要完成的功能有： 以广播方式向o n u 发送以太数据包； 发起并控制o n u 注册和测距过程，记录测距信息： 针对用户的q o s 要求为o n u 分配带宽，即控制o n u 发送数据的起始时 刻和发送时间窗口的大小； 其它相关的以太网功能。 根据以太网向城域和广域发展的趋势，o l t 可以提供多个g b p s 的以太接口。 o l t 还可以支持其他流行的协议如a t m 、f r 及e 3 、s t m 1 等速率的t d m 连 接。除了提供网络集中和接入的功能外，o l t 还要进行网络管理。 o n u 是用户接口单元，主要完成的功能有： 选择接收o l t 发送的广播数据包； 响应o l t 发出的注册和测距命令； 对用户的以太网数据进行缓存，向o l t 报告缓存的队列情况并在o l t 分 配的上行发送窗口中发送。 其它相关的以太网功能。 因为都使用以太网协议，o n u 不需要协议转换就实现对用户数据的透明传 送。o n u 也可以支持传统的t d m 协议，提供t l e 1 接口。 o s 是一个简单设备，它不需要电源，可以置于全天候的环境中，一般一个 o s 的分线率为1 4 、1 8 、1 1 6 或1 3 2 ，并可以多级级联。在e p o n 中，o l t 到 o n u 间的距离最大可达2 0 k i n 。 1 5 上海大学攻读硕士学位论文 p 组播技术及i p t v 在e p o n 系统中的实现 1 2 2e p o n 的工作原理 o l t 到o n u o n t 的方向为下行方向，反之为上行方向。e p o n 只在i e e e 8 0 2 3 的以太数据帧格式上做必要的改动，如在以太帧中加入时间戳( t i m e s t a m p ) ，l l i d ( 逻辑连接i d ) 等内容。如图1 - 1 所示，e p o n 下行采用纯广播 的方式，注册后，o l t 为已注册的o n u 分配l l i d ，由各个o n u 监测到达帧的 l l i d 来决定是否接收该帧，如果该帧所含l l i d 和自己的l l i d 相同则接收该帧， 反之丢弃，传输速率可达1 2 5 g p s 。上行采用时分多址接入( t d m a ) 技术，如 图1 - 2 所示，给每个o n u 分配一个上行时隙，每个时隙中包含多个未拆分的以 太数据包，每个数据包由包头、可变长度净荷和误码检测域组成【”】。 图1 - 1e p o n 下行工作方式 图1 2e p o nt d m a 上行接入方式 1 2 38 0 2 3 a he p o n 协议 2 0 0 0 年1 1 月2 0 0 4 年6 月，i e e e8 0 2 3 e f m ( e t h e m e ti nt h ef i r s tm i l e ，以 太第一英里) t 作组，完成了以太接入网的标准i e e e 8 0 2 3 a h t l 6 1 。一点到多点的 e p o n 协议是该标准的主体部分。 1 6 上海大学攻读硕士学位论文p 组播技术及i p t v 在e p o n 系统中的实现 e p o n 的标准化战略是在现有i e e e 8 0 2 3 协议的基础上，通过较小的修改扩 展相应的功能，支持点对多点的无源光网络o e 上下行数据不同的传送机制，实现 有效地传送以太网数据帧，从而很好地支持基于口的各种业务。 0 6 1 l a h f e r c e l 僻 图1 38 0 2 3 a l l 协议栈 e p o n 的8 0 2 3 a h 协议栈对千兆以太网协议栈作了修改和扩展。如图l - 3 所 示，8 0 2 3 a h 协议栈增添了多点m a c 控制( m u l t i p o i n tm a cc o n t r 0 1 ) 、运行管 理维护( o p e r a t i o n ，a d m i n i s t r a t i o na n dm a i n t e n n a n e e ) 两个子层，同时在原有的 调和子层( r e c o n c i l i a t i o ns u b l a y e r ) 增添了点到点仿真( p 2 pe m u l a t i o n ) 功能。 点到点仿真实现e p o n 协议与以太网的8 0 2 1 d 网桥协议的兼容。通过调和 子层在m a c 帧的帧头( p r e a m b l e ) 添加或去除逻辑链路标识符( l l i d ) ，从而 实现以太帧的过滤。当下行数据为单播时，下行比特流广播到各个o n u ，各个 o n u 识别l l i d ，若为本地l l i d ，则接收，否则丢弃。当o n u 经过o l t 的桥 接功能发送广播数据帧给相邻的其他o n u 时，该o n u 本身在物理层也会接收 到自己发出的帧，识别l l i d 为广播l l i d ，便在自己的调和层隔离这些帧。 m a c ( m e d i u m a c c e s sc o n t r 0 1 ) 子层的基本功能是组帧。该子层除沿用了原 8 0 2 3 数据帧和p a u s e 控制帧外，还在其上增添了多点m a c 控制子层，负责 o n u 注册、测距和动态带宽分配。采用申请一授权( r e p o r t - g r a n t ) 机制，执行 多点m a c 控制协议( m p c p ) 。多点m a c 控制子层产生和处理6 种控制帧：注 册过程使用的g a t e ( d i s c o v e r y 类型) ，r e g i s t e r 、 和_req r e g i s t e r r e g i s t e r