（计算机软件与理论专业论文）基于qos的ip多播路由和同步问题研究.pdf

罩 摘要 、 摘要 随着计算机和i n t e m e t 网络的发展，网络中的w w w 以及多媒体应用对网络 带赶的需求越来越多，完全依靠单播方式传输数据已经无法满足用户需求。多播 通讯可以用束支持多个参加者之间同时进行多媒体的信息交换，代替了单播中一 列一交换的模式。因此在网络服务和网络通讯量快速增长的今天，利用多播可以 减少网络的总负载，节省大量的网络资源，提供有效的网络通讯服务。然而对 i n t e r n e t 来晓，多播通讯仍然处于起步阶段，有许多实际问题和理论上的难点需 要解决。 其中多播路由问题是实现多播通讯的关键，找到一种有q o s 保证、代价最小 的多播树成为人们追求的目标，但这样的问题是一个n p 完全问题，太过复杂， 1 1j h 仍没有找到有效的算法。另外，务播通讯面向的主要业务是 定多播，式下的多媒体同步问题，有冥重要的理论意义和应用价 m f | j 进行研究，并取得了一定成果。i 主要内容和贡献如下： 应用，研 嬉这两 叶埘视频点播等实时多媒体应用之类的多播业务，提出了一类多播路山篼 浊。该类算法解决了以往算法中对多播树代价和时延条件顾此失彼的缺点， 很好的权衡了它们之r b j 的关系，经实验比较，该类算法取得了很好的性能： 2 ) 针对网络会议之类的对站点间有严格同步要求的多播业务，提出了类多播 路由算法。由于动态构造满足时延抖动的最优多播树及其困难，根据作者目 日i 的调查，这是第一次提出动态的有时延抖动限制的最优多播路出算法，并 且算法的时恻复杂度低。 3 1 为实时多媒体多播系统提供了一个较为完整的同步控制机制，实现了组同 步、流内同步和流| 1 日j 同步，并且保持了媒体的实时性和连续性：同时具有较 幻，的实际应用价值。 关键字：多播，多播路由算法，服务质量，斯坦利树，多媒体同步。 a b s t r a c t m u l t i c a s t r o u t i n gi s t of i n dt h ep a t h sf r o mt h es o u r c et oa l lo ft h em u l t i c a s t d e s t i n a t i o n s m u l t i c a s ts e r v i c e sh a v eb e e ni n c r e a s i n g l yu s e db yv a r i o u sc o n t i n u o u s m e d i aa p p l i c a t i o n s t h eq o sr e q u i r e m e n t so ft h e s ec o n t i n u o u sm e d i aa p p l i c a t i o n s p r o m p t t h e n e c e s s i t y f o r q o s d r i v e n ，c o n s t r a i n e d - b a s e d m u l t i e a s t r o u t i n g t h e m u h i c a s tl l a s a l r e a d yb e c o m et h ef o c u so ft h en e t w o r kc o m m u n i c a t i o n m u l t i c a s t r o u t i n gc a n d e c r e a s et h en e t w o r kl o a d ，s a v et h en e t w o r kr e s o u r c ea n dp r o v i d ev a l i d a t e n e t w o r kc o n l n l u n i c a t i o ns e r v i c e s h o w e v e r ，t oi n t e m e t ，m u l t i c a s tc o m m u n i c a t i o ni s a ta no r i g i n a lp h a s e w es t i l l h a v e m a n yp r a c t i c a lp r o b l e m s a n dt h e o r e t i cd i f f i c u l t i e st o r e s o l v e q o s b a s e d m u l t i c a s t r o u t i n gp r o b l e m i st h e k e yp r o b l e m o ft h em u l t i c a s tc o m m u n i c a t i o n c o m p u t i n g aq o sc o n s t r a i n e do p t i m a lm u l t i c a s tt r e eb e c o m e st h eo b j e c tt h a tp e o p l e p u r s u i t t h i si s an p c o m p l e t ep r o b l e ma n dt o oc o m p l i c a t e d ，s on o b o d yf o u n dt h e e f f e c t i v ea l g o r i t h my e t o nt h eo t h e rh a n d ，m u l t i m e d i aa p p l i c a t i o ni so f t e nt r a n s p o r t e d b ym u l t i c a s tc o m m u n i c a t i o n ，s om u l t i m e d i as y n c h r o n i z a t i o n f o rm u l t i c a s t g r o u p s r e s e a r c hi sv e r yi m p o r t a n t i nt h i st h e s i s ，w ee m p h a s i z et h er e s e a r c ho nt h ep r o b l e mo f m u l t i c a s tr o u t i n ga n dm u l t i m e d i as y n c h r o n i z a t i o nm e c h a n i s mf o rm u l t i c a s tg r o u p s ， t h ec o n t e n tm a i n l yi n c l u d e s ： 1 ) p r e s e n t i n g as o r to fm u h i c a s tr o u t i n gf o r d e l a ya n db a n d v , , i d t h c o n s t r a i n e d m i n i m u m - c o s tt r e ea l g o r i t h m s t h e yc a ns o l v et h ec o n f l i c tb e t w e e nt h ec o s ta n d d e l a y o ft h em u l t i c a s tt r e e o u re x p e r i m e n tp r o v e st h e s ea l g o r i t h m sg e th i g h p e r f o r m a n c e 2 ) p r e s e n t i n gas o r to f m u l t i c a s tr o u t i n gf o rd e l a y , d e l a y - v a r i a t i o na n db a n d w i d t h c o n s t r a i n e dm i n i m u m - c o s tt r e ea l g o r i t h m s a c c o r d i n ga u t h o r ss u r v e y , t h i si s t h ef i r s tt i m et o p r o v i d ed y n a m i cd e l a y - v a r i a t i o nc o n s t r a i n e dm u l t i c a s t t r e e a l g o r i t h m m o r e o v e r , t h e t i m ec o m p l e x i t yi sr e l a t i v e l ys l o w 3 ) t os u p p o r tm u l t i c a s tc o m m u n i c a t i o n sf o r l i v em e d i a ，a u t h o rp r o p o s e sag r o u p s y n c h r o n i z a t i o nm e c h a n i s m ，w h i c h c o n s i s t so fi n t r a - s t r e a r n ，i n t e r - s t r e a ma n d g r o u p ( i n t e r - d e s t i n a t i o n ) s y n c h r o n i z a t i o nm e c h a n i s m s t h em e c h a n i s mn e e d n o t k n o wt h en e t w o r kd e l a yb o u n di na d v a n c e ，a n di tc a nd y n a m i c a l l ye s t i m a t et h e n e t w o r kd e l a ya n da d j u s tt h ee v a l u a t i o nb a s e do nt h ev a r i a t i o no ft h en e t w o r k d e l a y k e ) 1 v o r d s ：m u l t i c a s t ，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 y o f s e r v i c e ，s t e i n e rt r e e m u l t i m e d i as y n c h r o n i z a t i o n u 中国科学技术人学硕十论文第一章绪论 第一章绪论 1 1 多播技术的发展和现状 随着多媒体技术的飞速发展，i n t e m e t 上多媒体应用层出不穷，多媒体信息的 数量与同俱增。i n t e r n e t 已逐步由单一的数据传送网向数据、语音、图像等多媒 体信息的综合传输网演化，由此出现了大量的一点到多点( p o i n t t o m u l t i p o i n t ) ， 多点到多点( m u l t i p o i n t t o m u l t i p o i n t ) 的数据传输业务。传统的单播( u n i c a s t ) 方式己经刁；能胜任这类传输业务。 多播( m u l t i c a s t ) 【1 】也称组播，是i p 多播( i p m u l t i c a s t ) 的简称。i p 多播 的概念是s t e v ed e e r i n g 【2 】提出i pm u l t i c a s ta d d r e s s ( 多播地址) 的构想后出现 的它是对标准i p 网络层协议的扩展【3 】随后出现了多播最早的正式规范【4 】， 1 9 8 9 年它的详细说明【3 】也问世，并代替了原有的f 式规范。自从1 9 8 8 年 s e d e e r i n g 提出多播( m u l t i c a s t ) 模型，以及1 9 9 4 年h e r i k s i o n 【5 】将其推广 到i n t e m e t 以来，多播通讯吸引了大批用户和设计者双方的注意。多播通讯的使 用价值和重要性已经得到了全世界网络使用人员和设计人员的认可【6 ，7 】。多播 通讯可以用束支持多个参加者之删同时进行多媒体的信息交换，代替了单播中一 对交换的模式。因此在网络服务和网络通讯量快速增长的今天( 约三个月增长 一倍【8 】) 利用多播可以减少网络的总负载节省大量的网络资源提供有数 的i 叫络通讯服务。针对多播通讯减少网络负载的程度，c h u m l g 和s i r b u 【9 】进 “了量化分析，其结果表明在一棵连接m 个随机网络节点的多播树上所需的链 路数l ( m ) 证比于m 的0 8 次方。g p h i l l i p s 和s s h e n k e r 【1 0 】对此做了送一步 的理论分析和大量实验，再次验证了上述结论。 过去几年来，网络中的w w w 咀及多媒体应用等对多播服务的需求增长非 常显著。然而对i n t e r n e t 来说，多播通讯仍然处于起步阶段，有许多实际问题和 理论上的难点需要解决，归纳起来多播问题主要包括下面几个关键性问题： 1 1 组成员管理 组成员管理的主要任务是管理多播组成员的加入和退出多播组，目前i e t f 组织已经通过2 个组管理协议i g m p v l 【3 】( i n t e m e tg r o u p m u l t i c a s tp r o t o c o l v e r s i o n1 ) 和i g m p v 2 【1 1 】。 6 中国科学技术人学硕十论文 第一章绪论 2 ) 路由协议 在多播问题中，组织、设计和实现一个有效的可扩展的多播路由协议是最重 要和最为困难的。多播路由协议主要包括多播路由算法以及多播路由树的构造两 方面内容，其中多播路由算法是多播路由协议的核心。在多播问题研究之初，提 出的路出算法【1 2 1 5 】大多没有考虑q o s ( q u a l i t yo fs e r v i c e ) 保证，最近几年为 了满足用户需求和多媒体数据传输的特点，提出了许多基于q o s 偎证的多播路 由算法【1 6 2 2 】。 随着人们对多播问题的研究，i n t e m e t 工程任务组( i e t f ) 陆续发相了几个 ，j 、准的路出协议包括：1 ) 距离向量多路广播路由选择协议( d v m r p ) 【2 3 】； 2 ) 多路广播丌放式最短路径优先( m o s p f ) 【2 4 】协议，它是一个允许支持i p 多播的扩充的o s p f 【2 5 】；3 ) 协议独立多路广播一稀疏模式( p i m s m ) 【2 6 】。 1 9 9 5 年，c i s c o 和l u c e n t 丌始销售支持多播的路由器和交换机。一年后，依 赖多播的应用产品丌始上市，不过大多局限于试验阶段，性能不理想，特别是还 未实现服务质量( q o s ) 保证。从9 0 年代丌始美国、中国、日本、英国等国 家都设立了国家科学基余用于多播q o s 技术的研究，另外3 c o m 、l u c e n t 、c i s c o 等许多大的网络公司的研究玎发中心也投入了大量人力物力进行多播q o s 技术 的研究。虽然支持多播的产品已有问世，但是它们没有考虑q o s 保证和安全性 等问题，也不适合异质结构的广域网。因此q o s 驱动( q o s d r i v e n ) 的多播路由 i u j 题钉待继续f 叫：究，多播将继续成为人们关注的焦点。 3 ) 路由表结构和路由表的查找算法 出于多播组的存在，每个多播组在路由表中都有一项与之对应。因而，多播 通讯以及q o s 保证的要求可能会导致路由表的大小无限制地增长。这是因为 m u l t i c a s t 和o o s 保证的通讯不是由包的目的地址来确定发送的方向的。这意昧 着目的地址的分级结构不能保证在路由表中的各项也相应地分级，已有结论表明 m u l t i c a s t 路由表中的各项不能类聚。因此，研究路由表结构和路由表的l o o k u p 算法具有非常重要的意义也非常迫切。w - s e c h e n 等人对此已做了初步研究， 给出了一种具有较好可扩展功能的查找算法【2 7 】。 4 ) 同步问题 多媒体信息的实时、同步传输是多媒体通信中最关键的问题。虽然“同步” 返一术语出现在o s i 标准中，但o s i 标准并没有明确提出多媒体实时、连续和 同步的需要。目前，解决多媒体通信实时问题的途径【2 8 1 主要有：1 ) 增加网络 7 主旦堂垫查盔兰堡主丝塞 苎二童丝 带宽，从网络硬件上提高信息传输速率。2 ) 对多媒体信息进行压缩，例如采用 m p e g 、j p e g 压缩算法。3 ) 在视觉和听觉允许的情况下，降低视觉和听觉分辨 率，从而减少媒体信息的数据量。应该说，这三种方法已经比较有效地解决了多 媒体通信的实时问题。这样，同步问题在多媒体通信中就表现得尤为突出。目前， 多媒体应用主要局限于单机，媒体数据基本上采用单播传输，很少涉及多媒体信 息分布处理。对多媒体同步的研究也只是针对单机的情况和单播模式下，而对多 播多媒体通信的同步研究才刚刚起步。然而，多媒体应用进一步发展的趋势必然 是多媒体的分布式协作和交互处理。因此，分析和研究多播方式下的同步算法有 着重要的理论和实用价值。 1 2 多播路由技术简介 l 工l 多播路由同意 1 2 1 1 多播路由问题的分类 多播路由算法( m u l t i c a s tr o u t i n ga l g o r i t h m ) 就是探索一种算法或策略，在给 定网络拓扑结构和多播需求的情况下，找到一种链路连接方式，在保证q o s 条 件下，使网络资源能够得到有效利用。这些连接起来的链路通常构成了一棵分布 树，我们把它称之为多播树。多播路由优化的目标通常是使多播树的代价最小或 最大限度地利用其它网络资源。目前研究的各种q o s 要求实际上就是求出满足 相应限制条件的多播树，而限制条件通常分为两类：链路受限和树受限。 1 ) 链路受限( 1 i n k - c o n s t r a i n e d ) ：路由时被选中的链路必须严格满足一定的要求， 例如多播树【1 9 】的每条链路的带宽必须大于某个常数b 。 2 ) 树受限( t r e e - c o n s t r a i n e d ) ，它包括两种受限： a ) 从源点到目的点路径上的所有链路的某个性能度量参数的综合必须满足 某个条件。例如在实时应用【2 2 】中，要求源点到任意目的点的延迟不 超过，用数学公式表示： d ( p ( s ，d ) ) a ， v d d b ) 从同一源点到任两目的点的两条路径之间的某个性能度量参数的综合值 的差异必须在某个范围之内。例如在网络会议系统中站点问同步 【1 7 ，3 0 ，31 】，要求源点到任意两个目的点的延迟之差不超过d ，用数学公 式表示为： 8 中国科学技术人学硕十论文 第一章绪论 d ( p ( s ，d j ) ) 一d ( p ( s ，d 2 ) ) 峰占，v d l ，d 2 d 针对任意的路径p r ( u ，v ) = ( “，i ，k ，v ) 在树受限中链路性能m ( v ) 的计算 方式，树受限可以进一步细分为下面三类 3 2 】： 加法受限( a d d i t i v ec o n s t r a i n s ) ： m ( u ，v ) = m ( u ，i ) + m ( i ，j ) + 一+ m ( k ，v ) 乘法受限( m u l t i p l i c a t i v e c o n s t r a i n t s ) ： m ( u ，v ) = m ( u ，f ) m ( i ，j ) 十 m ( k ，v ) 凹受限( c o n c a v ec o n s t r a i n t s ) ： m ( u ，v ) = m i n e m ( u ，1 ) m ( i ，) ，m ( k ，v ) 】 根据各种受限和优化组合，可以将多播路由问题分为1 2 类1 2 9 1 如表l 所 表1 ：多播路由问题分类 无优化 | 链路优化树优化 无受限 1 链路优化2 树优化 ( 多项式刚h j )( n p 完仝糊题j i 链路受限3 链路受限5 链路受限，链路优化 6 链路受限，树优化 ( 多项式h er j )( 多项式叫m )n p 完全刚题) 4 多种链路受限 ( 多项式时) 村受限7 树受限9 对受嘏链路优化1 0 树受l ：b 讨优化 ( 多项式时f h )( 多项式h 州)( n p 定尘剐题) 8多种树受限 ( n p 完问题) 链路和树1 1 链路和树受限1 2 链路和树受限材优 受限化( n p 完全州题) ( 多项式时间) 现在我们来分析一下各种问题的时间复杂度。问题3 和问题4 显然可以在多 项式时间内解决，因为我们只需从网络拓扑结构中将不满足链路条件的链路删除 9 ! 蔓里型竺垫查查堂堡堡苎 苎二兰堕堡 即可。w a n g 和c r o w c r o f t 【3 2 1 已经证明找到满足两个或两个以上加法或乘法 受限的路径是n p 完全问题而凹受限和其它某个受限联合可以在多项式时问解 决。所以问题7 ，9 和1 1 可以在多项式时i n 内解决，而问题8 是n p 完全问题。 问题1 已经存在着一个多项式时间解决的算法【3 3 】，又易知问题5 可以很容易 转化为问题i ，因此问题5 也可以在多项式时i h l 内解决。其余的问题2 ( 斯坦纳 树问题) 、6 、1 0 和1 2 ，c a r e y 和j o h n s o n 【3 4 1 已经证明它们是n p 完全问题。 1 2 1 2 多播路由算法的基本策略 多播路由算法构造的分布树包括源根树( s o u r c e t r e e ) 和基于核的树 ( c o r e b a s e d t r e e ) 两类。这两种路由树都覆盖了所有多播成员，不同的是源根树是 以源点为根：而基于核的树是以一个选定的节点作为核并以此为根，并且浚组的 所有的源都共享这一棵树。在稀疏网络中，大多建立基于核的多播树，不过这种 树建立起来虽然高效，但是在核的附近容易造成网络传输瓶颈，而且核的选择也 比较困难，所以还是源根树较为普遍。多播树的优越性主要体现在两个方面： 数据可以通过树的分支并行的向多个目的点发送。 最低限度地降低信息的复制量，传送时仅需在树的分支处进行信息的复制。 从多播树的构造过程柬看，多播树的构造方法大致分为两类第一类是构造 之仞只有一棵初始化的子树，o ，然后不断的扩张丁o 直到包含所有的组成员： 第二类则以订棵初始化的子树丌始一一每个网络节点都被看作一棵初始的多播 子树，然后不断合并这些子树，直到某棵子树包含所有的组成员。 先看第一类方法，丁。可能是一个网络节点或者是一条从源点到一个目的点 的最短路径。构造覆盖所有组成员的多播树，一般采用迭代的方法，逐步扩张初 始树7 1 0 ，直到包含所有组成员。每次选择迭代加入的节点有两类，一类是组成 员节点另一类可以是任意的节点。树扩张的方法是先给出迭代加入的节点v ， 再确定连接到树上的接入节点日，最后将节点口到节点v 的最短路径连接到树上。 接入节点d 的确定是通过一个权值函数来计算，每次迭代时，选择权值函数值最 小的。常用的权值函数的定义归纳起来有下面五种【3 5 】： 1 ) w ( a ，- g ) = d ( v d ) ；口，v v 一 2 ) w ( a ，v ) = a ( v d ) ；d h ，v m 一( m n h ) 3 ) w ( a ，v ) = d ( v a ) + w m a x d ( s 一) l 如r a l l ( s s ) ；口i s , ， w 0 v m 一( m n h ) l o 中国科学技术人学硕+ 论文 第章绪论 4 ) w ( a ，v ) = d ( v 一口) + 2 w ( d ( a u ) l l 矿| ) ；口t 6 , ，v ，一( 彳n ) ，w o r 5 ) w ( a ，v ) = d ( v a ) + w m a x d ( e d ) l 扣，a l l ( e e ) ；v m 一( m n ) ，w 0 说明：是已建多播子树的所有h 点集台，s 是多源点多播中的所有源点集合。 再看第二类方法，浚方法初始化时有门棵子树，关键问题是如何合并这些树， 使得其中某棵子树包含所有的组成员。通常的做法是定义一个权值函数 厂p 7 j r 一( 或f ：e 叶r ) ，找到使厂取最小值的节点或边，然后将距离陔节 点或边最近的两棵子树用其最短路径连接起来，合并成一棵子树。权值函数的定 义归纳起来有下面三种形式【3 6 】： ，、f d ( v ，t 2 )如果v ”八2 m i 。：。，o ( 。，r j ) ( 女- 1 ) 其它 ：，八v ，= d ( v 。t 。i ) + d ( ：v ：, d t 2 。) 。，r 。一：，萋主只有两棵树 如果p t i 化。，+ i d ( ，】似一i ) 其它 髓叫：，3 ) 中的子树序列( 王r 疋一，l ) 是按照 点v ( 或边p 。) 刮千树的【! 离升 序 1 列的，边剑子树的距离指的是边的两个顶点剑子树的疑短距离。 1 2 1 3 多播路由算法的小结 多播路由算法一般有好几种分类方法，按照组成员是否可以动态加入到多播 组，可以分为动态多播算法和静态多播算法；按照源点的数目，可以分为多播算 法和群多播( g r o u p m u l t i c a s t ) 算法【1 9 】；按照多播树是否有核，分为基于核的 多播算法【3 7 ，3 8 】和无核的多播算法等分类。无论那种分类，算法的核心思想 集中在如何构造多播树，构造的方法一般是基于最短路径树【3 9 】、最小生成树 【3 9 1 和斯坦纳树【1 3 】的方法。当然也有些特殊的算法，例如基于遗传算法 【4 0 】和神经网络 4 1 】的方法，不过这类算法一般也可归为前面所说的三种算 法，只不过它们用特殊的方法找最短路径树或最小生成树等。在实际应用过程中， 对于那些受艰的复杂多播路由算法【1 8 ，2 0 1 ，通常结合这几种方法求出满足q o s 保证的多播树。下面按照最短路径树、最小生成树和斯坦纳树的分类方法对现有 的有代表性的多播路由算法进行一个小结，如表2 所示。 p n j m _【 中国科学技术大学硕士论文 第一章绪论 表2 ：多播路由算法分类 策略算法集中式动态时间复杂度问题解决 分布式静态 最 b e l l m a n - f o r d 4 2 1集中静态 0 0 e i - l o g n ) 树受限 短 路d i j k s 弧 3 9 】集中静态o ( le i 1 0 9 )树受限 径 c h a k r a b o r t y 4 3 1分布动态d ( 1 e i )树受限 r o u s k a s 3 0 l集中静态 o ( 1 - k m n 4 、 树受限( 时延，时延抖动) p i - r o n gs h e u 3 1 1集中静态o ( m h 二)树受限( 时延肘延抖动) 最 p r i m 3 9 集中静态0 0 e 【1 0 9 n )树优化 小 生 g a l l a g e r 1 2 1分布静态0 0 e l + n l o g n )树优化 成 树 们k m 1 3 集中静态 o 卸- n 。)树优化 曼 鼋 t m 1 4 】集中静态o ( m n 2 ) 树优化 树 r s 1 5 j集中静态 o ( m - n )树优化 m c t h 4 4 集中静态d ( ( m + 3 2 ) 一m ：n )树优化 受 c p c s 1 6 】分布动态 o ( n ：l o g n ) 带宽受限树优化 限 们 c e l o w t 7 】分布静态 o ( n )时延、时延抖动受限 量 乌树优化 树 m o h 1 8 集中动态 o ( n 1 l o g 帕时延受限书 优化( 带宽) c 卫l o w 19 】集中静态o ( m + n2 )带宽受限- 树优化 j d l m r 2 0 】集中静态d ( + 5 2 ) - n 2 一m 2 )时延受限书 优化 k p p 4 5 o集中静态o ( n )时延受限制优化 b a o x i a nz h a n g 2 1 】 集中 动，静o ( m n ) 时延受限树优化 x i a o h u a 3 i a l 2 2 】分布动态o ( 2 q + p )时延受限书f 优化 说明：i e i ：弼络链路数目；n ：网培节点数目；m ：多播组成员数目； q ：多播树链路数目；p ：发送消息的数目； ：时延常数； f ，| ：算法根据性能要求给出的常数。 1 2 中国科学技术人学硕十论文 第一章绪论 1 2 2 同步问题 在多媒体系统中，通常利用多种媒体从不同侧面来表达同一个主题。例如在 介绍某处旅游景点时，屏蔽的窗口中出现该点的录像，同时有声音在解晓，屏幕 的其他部位则显示有关的文字晚明、图表等等。此时媒体之削就存在着相互依存 的关系。实际上这种关系不只是显示时才有，在捕获、存储、传输和处理过程中 也是存在的。不同媒体对象之阳j 的相互依存关系可以概括为3 类： i ) 内容( c o n t e n t ) 关系：例如，根据某一组数据既可以列出表格同时又可以 画成曲线。那么，在计算机中只需要保存一份数据，而将表达这组数据的方 式另作定义，这称为指定数据间的内容关系。同一组数掘，可以对应于儿个 不同的内容关系。 2 ) 空阳j 关系：空间关系主要指不同媒体对象在显示时所处的相互位置关系。通 常它们分别在不同的窗口中显示，而每个窗口又容许有缩放、移动、激活等 功能，这些复杂的相对位置关系需要有一定的方法来描述。 3 ) 时f 日关系：电视中的伴音要求很好地和人的口形动作相吻合幻灯片的解说 词应浚与币在显示的图像相对应，这是媒体对象之划必须保持一定时间- 关系 的典型例子： 从广。义上讲，同步指的是上述3 种关系的确立。显然，在集成了多种媒体的 多媒体系统中，同步是一个关键性问题。系统的各个组成部分例如，操作系统、 数掘庠、文件系统、传输数掘的通信系统，以至于应用程序等，都需要在不同层 次t - _ 支持媒体的同步。 在多媒体通信中，出于网络固有的异步特性、传输冲撞，以及存储设备的潜 在影响，势必造成信息传输的随机延迟，从而破坏了多媒体信息中各媒体问的原 束的相互约束关系。因此，在多媒体通信中必须采用某种同步算法以确保传输 以后的多媒体信息仍然保持原来的约束关系。在上述3 种同步关系中，时削e l 关系 是最重要的一种，因为一个系统只有在集成进了与时间有关的媒体之后j 能称为 多媒体系统。因此，从狭义上来讲，同步指的是各类事件时删顺序的确立。 从所同步的对象柬分，同步问题通常包括流内同步、流i 日j 同步和节点削同步 三个方面。 1 ) 流内同步( i n t r a s t r e a ms y n c h r o n i z a t i o n ) 是指媒体表现的连续性，也就是在单 一连接上的单一媒体流内各个媒体单元( m u s ) 之间存在的时间关系。 1 3 。p 国科学技术人。学硕十论文 第一章绪论 2 ) 流州同步( i n t e r - s t r e a ms y n c h r o n i z a t i o n ) 是指在多个连接上的相关媒体流之i h j 存在的时l 日j 关系。人物口形移动和声音之唰的配合( 也就是视频和音频流之 间的时问关系) ，通常称为口形同步( 1 i p s y n ) ，是流问同步的典型例子。 3 ) 组同步( g r o u ps y n c h r o n i z a t i o n ) 或节点问同步 ( i n t e r d e s t i n a t i o n s s y n c h r o n i z a t i o n ) 。在多播通信中，例如网络会议，它要求每个与会者要同时 听到说话人的声音，这就需要音频流同时在各节点播放，这种描述媒体流在 各节点的时州关系的就叫做组同步，这是多播通信中常常需要考虑的问题。 1 3 本文主要内容 1 , 3 1 本文的研究背景与内容 多播q o s 技术的查找算法和同步问题研究是我们课题组承担的华为技术有 限公司北京预研所的科研项目主要目标是为该公司的下一代多播路由器研究多 播路由问题及其相关的多播q o s 技术。在多播通讯服务中，有大量的实时通讯 需求如多媒体数据的传送，电话会议，视频点播等，由于原有基于单播协议的 路由方法已无法满足多播的需求和对延时、同步等条件的要求，使得研究多播过 隧- 如何保证质量变得非常重要，这方面的研究与以往的质量保证的研究有所4 i 川：这方面的质量要求主要考虑在多播中所面临的问题，包括查找表的结构、查 找算法、站点问l 川步的要求、延时的质量保证、多播树的快速构造等等。浚谍题 针对如下问题展丌研究。 1 ) 多播路由算法的研究 研究多播树的快速构造算法，即在一定的延时、站点问同步、以及构造算法 本身成本三种时间限制的要求下寻找合适的快速算法。 2 ) 查找表结构及快速表查找算法的研究 研究多播路由表结构和路由表的l o o k u p 算法，以实现数据的快速转发。 3 ) 有关多媒体数掘同步问题的研究 研究多播环境下的多媒体系统如保证媒体数据的时序，保证同步问题。 中国科学技术人学硕十论文 第一章绪论 本文针对下面两方面问题展丌讨论： 多播路由算法 多播路由采用多播树的方式进行数据传输，多播树覆盖多播组中的各个结 点，通过传输时共享链路的方式减少对整个网络资源( 如时问和带宽) 的占用。 我们的任务就是找到合适的多播路由算法，多播路由算法负责计算满足一定的端 倒端延时、站点间同步等q o s 限制的近似最优多播树。在实时通讯中，如视频 点播，为满足用户的响应要求，必须在一定的时自j 限制内完成数据传输，这就要 求对多播的延时进行限定。而在电话会议中必须保证各个成员之削的同步，会 议l 能顺利进行。如果成员之阳j 的延迟差别太大，将会造成通讯的混乱。 找到一种满足q o s 保证、代价最小的多播树成为人们追求的目标，但这样的 l u 题是一个n p 完全问题，太过复杂，一般用启发式方法来寻求满足条件的多播 树。作者经过多播路由问题方面的广泛调研在总结、吸收6 u 人的已有成果的基 础上，展丌了深入的研究，提出了两类q o s 多播路由算法。 同步问题 研究在现有协议等条件下保证同步问题。这一问题的研究包括两个方面： 力+ 面是同步时延要求，保证成员之问的同步；另一方面是数据传输时序，保证数 掘的同步，即数据是按发送顺序到达接收端，先发送的数据被首先接收。埘r m u i t i c a s t ，由于系统是从减少延迟的策略出发，如何存贮丢失的包和控制i 刊络捌 术| u j 题尚未很好解决，故难以保证实时传送数据的因果时序和站点问的同步，因 此，如何在现有协议等条件下保证数据的时序，保证同步，从理沦上晓具肯较大 的难度，本文将在这方面进行初步探讨。 1 , 3 , 1 论文组织 本文安排如下： 第一章回顾多播技术的发展和现状，指出研究多播通讯的意义。简单介绍了 多播路由技术以及同步问题。最后介绍了本文的研究内容和重要工作。 第二章介绍本文作者提出的两类q o s 多播路由算法。与已有的算法相比，第 一类算法不仅降低了时空消耗，而且得到了很好的性能。第二类算法是针对时延 抖动要求严格的业务提出的，根据作者的调研，这是第一次提出满足时延抖动条 件的动态多播路由算法，并且它的时削复杂度比较低c 1 5 中国科学技术人学硕十论文 第一章绪论 第三章介绍在p c 机上模拟网络环境、实现多播路由算法分析多播路由算 法的性能。 第四章介绍在现有协议的基础上，在多播环境下作者提出的一个同步控制机 制，该机制满足实时多媒体系统的流间同步、流内同步和组间同步，并保持媒体 的实时陆。 第五章总结全文，并提出进一步的研究方向。 1 6 中国科学技术人学硕十论文 第一章q o s 多捕路由葬法 第二章q o s 多播路由算法 本文将要提出的多播路由算法分两类，包括四个算法，它们都是有q o s 保证 的多播路由算法。其中一类是时延、带宽受限的近似最小代价多播路由算法包 括两个算法：一个是动态分布式的，另个是动念集中式的。第二类是时延、时 延抖动和带宽受限的近似最小代价多播路由算法，它也包括两个算法：一个是静 态集中式的，另一个是动态集中式的。视频点播和实时数据传输之类的对时延要 求，格的多播可以采用第一类算法：而像视频会议之类的对站点f 自j 有严格的同步 要求的多播可以采用第二类算法。本章分为三部分，第一部分介绍路由算法选取 晌策略问题，以及各算法中共同关心的问题；第二部分，阐述第一类多播路由算 浊：第三部分蚓述第二类多播路由算法。 2 1 多播路由的网络模型 为了便于我们研究问题一个网络可以表示为无向圈g = ( 矿，) ：其中旷是 顶点( 节点) 的集合，包括月个顶点，每个顶点代表一个路由器；e 是边( 链路) 的集合，包括l e i 条边。链路上用一些参数柬刻划链路的当前状态。下面我们提 出的算法都要用到三个链路状态函数：链路带宽函数：6 ：e 斗r + ，链路代价函 数：p ：e 呻r 一，链路延迟函数d ：e 斗尺+ 。在多播通信中，m c v 是组通信的 1 i 点集合， 称为多播组，肘中的每个元素都是组内成员，我们不加区分的将 这蝗元素称之为成员节点或目的节点。一般多播路由算法就是要找到一棵多播树 7 ，它是图g 的一个子图，并覆盖了组内的所有成员，且叶结点均为组成员：源 节点s 发送多播数据时就沿着多播树将数据发送到多播组的所有成员，即 m f s 中的每个成员。 为了表述方便，对一棵q o s 受限的多播树，定义下面的一些术语： 1 1 节点时延：从多播树的根到该节点的路径上的所有链路的时延总和： 2 ) 路径时延：从该路径的起点到终点的所有链路时延的总和： 3 ) 多播树的最大时延：在多播树中，时延最大的成员节点的时延。由于多播树 的叶子节点都是成员节点，所以这个最大时延一定是某个叶子节点的时延， 7 主里型堂堡查查堂雯堡塞 篁三童旦旦! 童堡墅虫竺堡 因此又可以说多播树的最大时延是树中最长路径的时延： 4 ) 多播树的最小时延：在多播树中，时延最小的成员节点的时延： 5 ) 端到端的时延：通常用它来表示源结点到目的结点的时延。然而在基于核的 多播树构造算法中，端到端的时延通常指从多播树的根到目的节点的时延： 6 ) 时延抖动：多播树的最大时延减去多播树的最小时延： 7 ) 时延同步：通常指时延抖动小于等于某个阈值； 8 ) 路由路径：当一个节点要加入多播树时，首先用多播路由算法计算出该节点 加入多播树的路径，将这条路径链接到多播树后，该节点也就加入到多播树。 本文将这条路径称之为路由路径。 2 2 1 分布树的选取 2 2 策略选择分析 多播分抑树有三种基本类型【l 】：泛洪法( f l o o d i n g ) 、有源树、共享树，其 t = l 缺享树包括有核树( c b t ) 和s t e i n e r 树。 2 2 1 1 泛洪法 泛洪法【l 】是最简单的向前传送多播路由算法，它并不构造所谓的分弁j 树。 其基本原理如下：当多播路由器收到发往某个多播地址的数据包后，首先判断是 占是首次收到该数据包，如果是首次收到，那么将其转发到所有接口上，以确保 其最终能到达所有接收者；如果不是首次收到，则抛弃浚数据包。 泛洪法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数扼包 州表但无需维护路由表。它适合于对多播业务需求比较高的场合，并且能做到 即使传输出现错误，只要还存在一条到接收者的链路，则所有接收者都能接收到 多播数据包。然而，泛洪法不适合用于h a t e m e t ，因为它不考虑链路状态，并产 生大量的拷贝数据包。此外，对于高速网络而言，“首次收到”列表将会很长，占 用相当大的内存：尽管它能保证不对相同的数据包进行二次转发，但不能保证对 相同数据包只接收一次。它的另一个致命的缺点是不能建立满足一定q o s 条件 的多播树。 中国科学技术人学硕十论文 第一二章q o s 多播路由算法 2 2 1 2 共享树 共享树【l 】也称r p 树( r p t ) ，是指为每个多播组选定一个共用根( 汇合 点r p 或核心) ，以r p 为根建立的多播树。同一多播组的多播源将所要多播的数 据荦播到r p ，再由r p 向其它成员转发。目日i ，讨论最多同时也是最具代表性 的两种共享树是s t e i n e r 树和有核树。有核树是由根到所有组成员的最短路径合 ，j 二而成的树。 s t e i n e r 树问题【1 7 】就是创建最小代价的分布树的问题。若考虑资源总量被 丈量的组使用的情况，那么使用资源较少最终就会减少产生捌塞的i x l 险。s t e i n e r 树相当不稳定，树的形状随组中成员关系的改变而改变且对大型网络缺少通用 的解决方案。所以s t e i n e r 树只是一种理论模型，而非实用工具。目前，出现了 许多s t e i n e r 树的次优启发式生成算法。 共享树在路由器所需存储的状念信息的数量和路由树的总代价两个方面具 有较好的性能。当组的规模较大，而每个成员的数据发送率较