（管理科学与工程专业论文）多速率组播策略研究.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：讯 导师签字： 学位论文版权使用授权书 滚9 一月牡 l 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 查l 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：么艺掀 导师签字：z9 - 月, 9 -导师签字： 亏，9 - 爿 签字日期：2 0 0 f f 年5 - , 9f 7 日 签字日期：2 0 0 口f 年，月夕日 山东师范大学硕士学位论文 摘要 异构性是i n t e r a c t 网络的固有特征，网络中资源分配的不均匀以及端系统处理能力 的差异是这种异构性存在的根源，并且随着未来越来越多不同种类的网络接入i n t e r a c t ， i n t e m e t 的规模不断扩大，异构性问题将更加突出。在这一前提下，按照组播传统意义上 的单速率机制的做法，数据信息被以相同的速率发送给所有的接收者，发送速率由最慢 的接收者决定，这使得所有接收者无论其接收能力如何都要受瓶颈接收者的速率的影响， 显然带来了接收者之间的严重的不公平性问题，也限制了该机制的可扩展性。而多速率 组播具有内在的会话内公平性特征，因此被认为是异构大规模网络中组播通信的有效手 段。 本文以多速率组播的分层解决策略为研究对象，针对制约组播在因特网中广泛实施 的公平性问题和流量控制问题展开研究，以获得满足m a x - m i n 公平性要求的流量控制机 制为主要目标，对多速率组播旧有的实现策略进行改进和优化，采用发送方和接收方混 合驱动的流量控制模式，提出了一种异构网络环境下满足公平性要求的、具有适应网络 状态豹灵敏性和资源利用的高效性的多速率组播分层实现方案f i m 。 文中我们首先介绍了组播的特点和发展背景，指出组播中现存的会话内、会话间公 平性间题以及端到端的流量控制机制中的不足之处，并在第2 章中针对会话内公平性的 要求和网络的异构性特点，给出多速率组播分层解决方案的实现机制，介绍了分层组播 的研究现状，并分析指出分层组播中存在的主要问题。 针对于分层组播中存在的组播会话间以及组播会话与t c p 会话间的公平性问题，我 们在第3 章中提出种适用于分层组播环境的、满足m a x m i n 公平性要求的速率分配计 算算法，用来在网络状态变化的情况下为共存于网络环境中的各虚会话进行公平资源分 配，并采用二分法对计算得到的、取值于连续数据集合上的速率分配集进行不同粒度上 的离散化整合，给出了具体的分层解决策略。这一公平速率分配算法将作为本文所设计 的分层多速率组播方案f l m 中网络流量控制机制的重要组成部分之一。 接下来我们通过分析在组织公平速率分配算法实施过程中存在的问题以及分层组播 协议策略中同步点的优化问题，在第四章中为f l m 设计了一种有路由器辅助的分层组 播流量控制方案，提出将一种主动队列管理( a q m ) 算法r e m 作为对端系统的辅助加 入到f l m 的流量控制策略当中来，源端利用从运行r e m 的路由器上收集到的网络状态 指示信息做出媚应决镶，触发m a x m m 公平速率分配算法的运行，劳对协调接收者加入 层或离开层行为的同步点设置进行动态调整，使得f l m 在保证会话内、会话间公平性 的前提下具备了合理有效的流量控制机制，提高了组播流对网络状态适应的灵敏性和稳 定性。 山东师范大学硕士学位论文 为了验证f l m 的合理性和有效性，我们在第5 章中利用网络模拟器n s 在多种拓扑 条件下开展一系列仿真实验来评价f l m 的性能，并与分层组播协议中有代表性的r l m 、 r l c 作了详细的比较。仿真结果表明，f l m 具有良好的公平性特征，提高了灵敏性，在 稳定性和可扩展性方面均有较大改善。 关键词：多速率组播，分层组播，流量控制，m a x - m i n 公平性，主动队列管理，r e m 分类号：t p 3 9 3 山东师范大学硕士学位论文 r e s e a r c h e s o ns t r a t e g i e s o fm u l - t i r a t e m u l t i c a s t a b s t r a c t i n t e m e ti sah e t e r o g e n e o u sc o l l e c t i o no f n e t w o r k sa n d e n d s y s t e m s r e c e i v e r sm a yp o s s e s s d i f f e r e n tc a p a b i l i t i e so rb ec o n n e c t e dt ot h en e t w o r kt h r o u g hav a r i e t yo fd i f f e r e n ta c c e s s s p e e d s u n d e rt h i sc i r c u m s t a n c e ，i fo n l yas i n g l et r a n s m i s s i o nr a t ei su s e di nm n l t i e a s t ( t h e u s u a lm e c h a n i s m ) ，t h ec o n f l i c t i n gr e q u i r e m e n t so fas e to f h e t e r o g e n e o u sr e c e i v e r sc a n n o tb e s a t i s f i e ds i m u l t a n e o u s l yb e c a u s eo f 也es i m p l er e a s o nt h a to n es i z ed o e sn o tf i ta 1 1 w br e f e rt o 血i sa si n t r a - s e s s i o nf a i r n e s sp r o b l e m n l el a r g es c a l ea n dc o m p l e x i t yo f t o d a y si n t e r n e tm a k e t h i n g se v e nw o r s e m u l t i r a t em u l t i c a s ti sr e c o m m e n d e da sa l li d e a ls o l u t i o nt ot h i sp r o b l e m i n s u c hp r o t o c o l s ，d a t ai sd e l i v e r e di nm u l t i p l el a y e r so v e rs e p a r a t em u l t i c a s tg r o u p s , r e c e i v e r s j o i na sm a n yl a y e r sa st h e yc a nh a n d l e ，a n dr e c e i v ed a t aa tr a t e sc o m l n e n s t l r a t ew i t ht h e i r c a p a c i t i e sa n da v a i l a b l eb a n d w i d t h e v e ns o t h e r ea r cs t i l ls o m ep r o b l e m st ob es o l v e di n m u l t i c a s t ，s u c ha si n t e r - s e s s i o nf a i m e s sp r o b l e ma n dt h ep o o rp e r f o r m a n c eo ft h ee n d - t o e n d t r a f f i cc o n t r o ls t r a t e g i e se r e i nt h i sp a p e r , w ef o c u so nt h er e s e a r c ho f l a y e r e dm u l t i r a t em u l t i c a s ts t r a t e g i c s ，a i m i n ga t s o l v i n gt h ep r o b l e m so fi n t e r - s e s s i o nf a i m e s sa n d 仃缅cc o n t r o lm e c h a n i s mt h a tb l o c k m u l t i r a t em u l t i c a s t sa d v a n c e ，i no r d e rt og e ta 嫡cc o n t r o lm e c h a n i s mt h a ts a t i s t i e st h e m a x - m i nf a i r n e s sr e q u i r e m e n t s ，w em a k es o m ei m p r o v e m e n t sa n do p t i m i z a t i o n si nt h e c u s t o m a r yi m p l e m e n t a t i o n so fm l l l f i r a t em n l f i c a s t f i n a l l y , w ed e v i s eam a x - m i nf a i r n e s s g u a r m a t e e dl a y e r e dm u i t i c a s ts c h e m ei nw h i c hr o u t e r sp a r t i c i p a t ei nt r a 伍c c o n t r 0 1b y m o n i t o r i n gt h ea v a i l a b l eb a n d w i d t ha n dm a r k i n gp a s s i n gp a c k e t st oe x p l i c i t l yi n d i c a t et h e c o n g e s t i o n ，w en a m ei tf l m c h a p t e r2g i v e sad i s c u s s i o no nt h ep r i n c i p l ea n dr e s e a r c hd e v e l o p m e n t so fl a y e r e d m u l t i r a t em u l t i c a s t t h e nw ep o i n to u tt h ee x i s t i n gp r o b l e m si ni t ，a n di nc h a p t e r3 ，t h r o u g h s o m ed e t a i l e de x a m p l e so fb a n d w i d t hs h a r i n gp r o b l e m si l l u s t r a t e dw i t hs i m u l a t i o n s ，w e a n a l y z et h en e c e s s i t yf o rl a y e r e dm u l t i c a s tt oe l l s u r ef a i rr e s o u r c es h a r i n ga m o n gc o m p e t i n g m u l t i c a s tf l o w sa n dt c pf l o w s s ow ep r o p o s ea c o m p u t a t i o na l g o r i t h mf o rm a x m i n f a i rr a t e a l l o c a t i o nw h i c hc a nb ea p p l i e di nt h ef a i rr e s o u r c ea l l o c a t i o ni nh e t e r o g e n e o u sn e t w o r k e n v i r o n m e n t a sac o m p l e m e n t ，w ea l s od e s i g na na l g o r i t h mt od i s c r e t e l yr e g u l a t et h eo b t a i n e d r a t e ss e ti nd i f f e r e n tg r a n u l a r i t yw i t ht h ea d o p t i o no fb i s e c t i o nm e t h o d t h e r e b yw ep r o v i d e g u a r a n t e ef o rt h ee f f e c t i v ei m p l e m e n t a t i o no fl a y e r e dm u l t i r a t em n l t i c a s t t 1 1 i sm a x - m i nf a i r r a t ea l l o c a t i o na l g o r i t h mi sa l li m p o r t a n tc o m p o n e n to ft h et r a f f i cc o n t r o ls c h e m ei 1 1o a r i a y e r e dm u l t i r a t em u l f i c a s ts c h e m ef l m ar o u t e r - a s s i s t e ds t r a t e g yo ft r a f f i cc o n t r o lf o rf l mi sd e v i s e di nc h a p t e r4 i nt h i ss t r a t e g y , w e p r o p o s et oa p p l yt h ea c t i v eq u e u em a n a g e m e n ta l g o f i t h m - - - r e mi nf l m b yu s i n gt h e c o n g e s t i o ni n d i c a t i o np r o v i d e db yr e m ，o n rp u r p o s ei s t om a k et h e r o u t e rd e t e c tt h e c o n g e s t i o no rs p a r es t a t eo fn e t w o r ka n dr e p o r tt h es t a t ei n f o r m a t i o nt oe n ds y s t e m s b a s e do n t h er e c e i v e di n f o r m a t i o n ，e n ds y s t e m sa d j u s tt h es y n c h r o n i z a t i o np o i n t ss t r a t e g yf o rd i f f e r e n t r e c e i v e r st oc o o r d i n a t et h e i ri o i na n dl c a v ea t t e m p t s n ei n f o r m a t i o nf r o mr o u t e r si sa l s ou s e d 5 山东师范大学硕士学位论文 t od r i v et h er a t ea l l o c a t i o na l g o r i t h mt of u n c t i o n t h em e c h a n i s m so fm a x m i nf a i ra l l o c a t i o n a n dr o u t e r - b a s e ds t r a t e g yt o g e t h e rc o n s t i t u t et h et r a f f i cc o n t r o ls c h e m eo ff l m s of l mc a l l a c c o m m o d a t et on e t w o r k ss t a t ef l u c t u a t i o nr a p i d l ya n de f f e c t i v e l y , e x h i b i t i n gf a v o r a b l e f a i r n e s sp r o p e r t i e s a t1 a s t w ec a r r yo ns o m en ss i m u l a t i o n sf o ral a r g ev a r i e t yo fs c e n a r i o st oe v a l u a t e f l m sp e r f o r m a n c e ，a n dm e a n w h i l e ，w ea l s os i m u l a t er l ma n di 也cf o rt h eb a s i cs c e n a r i o s t oc o m p a r et h e i rp e r f o r m a n c et of l m t h er e s u l t ss h o wt h a tf l mc o n v e r g e sf a s tt ot h ep r o p e r s u b s e r i p t i o nl e v e l ，i n d u c e sl e s sl o s st od i s c o v c ta n dt r a c kt h ea v a i l a b l eb a n d w i d t h ，e x h i b i t s a p p e a l i n gi n t e r - s e s s i o nf a i r n e s sa n dt c p f a i r n e s sp r o p e r t i e s ，a n ds c a l e sw i t hb o t ht h en u m b e r o f r e c e i v e r sa n dt h en u m b e ro f s e s s i o n s k e y w o r d s ：m u l f i r a t em u l t i c a s t ，l a y e r e dm u l t i c a s t ，t r a t i i cc o n t r o l ，m a x - m i nf a i r n e s s ，a q m ， r e m c l a s s i f i e a t i o n ：t p 3 9 3 6 山东师范大学硕士学位论文 第1 章绪论 组播作为种节约网络带宽、降低网络负载的有效手段，在当今网络资源仍然匮乏 的情况下，具有广阔的应用前景。且随着因特网基础设施的改善、端系统处理能力的不 断增强。尤其是因特网组播骨干网m - b o n e 的不断完善和发展，使组播应用日益变得可 行。应该说作为近些年来的研究热点，组播目前已经是比较成熟的技术。但组播的引入， 也给i n t e m e t 带来了许多潜在的问题，组播要真正在因特网中得到实施仍然是一个充满 挑战的研究领域。 1 1 关于lp 组播技术 图1 - t 利用i p 组播进行多点数据传输 组播是一种允许一个或多个发送 者( 组播源) 发送单一的数据包到多 个接收者的网络技术。组播源把数据 包发送到特定组播组，面只有属于该 组播组的地址才能接收到数据包。图 l l 是对采用i pm u l t i c a s t 协议进行数 据多点传输的基本说明。在i p 组播通 信中，无论有多少个目标地址，在整 个网络的任何一条链路上只传送单一 的数据包，所以可以大大地节省网络 带宽。 组播技术被认为是w w w 技术推 广之后出现的最激动人心的网络技术 之。1 9 9 2 年出现支持i p m u l t i c a s t 的 m b o n e 和m b o n e 桌面工具： 1 9 9 3 。1 9 9 6 年i p 组播成为业界关注的焦点，然而因发展条件不成熟使得i p 组播只为业界 所关注；进入1 9 9 9 年以来，l p 组播具备了发展的三个关键条件：支持组播的路由协议、 基于开放标准的可测试管理协议、商业发展机遇，因而进入高速发展阶段，又一次掀起 了组播实践的高潮。i p 组播技术得到硬件、软件厂商的广泛支持，比如新生产的以太网 卡几乎都支持组播；c i s c o 的路由器不仅支持d v m r p 、p i m 路由协议、i g m p 组管理协 议，而且支持c i s e o 专用组管理协议c g m p ；再如微软的w i n d o w s9 5 支持i p 组播和 i g m p v l ，从w i n d o w s9 8 开始还支持i g m p v 2 。这些说明在因特网中i p 组播技术的应用 环境已基本具各，目前组播通信主要是运行在m b o n e 上，它是由i e t f 开发的、运行 在i n t e m e t 上的试验网络，采用隧道( t u n n e l i n g ) 技术作为过渡方案来穿越尚不支持l p 组播传输的中间路由器和网络，m b o n e 跨越几个洲，用户数直在迅速增长着。此外， 山东师范大学硕士学位论文 下一代互联网络技术如i n t e m e t 2 、i p v 6 等也都为组播的应用创造了条件。 然而，要让i p 组播扩展到因特网的所有点，还需要开发出新的域间组播路由协议和 转发算法，以及向因特网服务提供商( i s p ) 提供他们所需要的与流量管理有关的控制， 必须要能够保证其在提供可靠的组播服务的同时也不会过分影响现有的单播服务。这些 都是制约组播在因特网范围内有效实施的关键性问题，我们从速率和流量控制的角度出 发，分析认为目前组播中尚存在如下文所述的些不足之处。 1 2 问题的提出 组播的特点决定了对其进行流量控制的复杂性【8 1 ，能否提出一种可扩展的、公平的 组播流量控制机制是组播协议在互联网中得以应用的关键前提。目前存在的主要向题有 以下几点： 1 2 1 会话内公平性问题 异构性是i n t e r n e t 网络的固有特 征。在整个i n t e m e t 网络当中，各予网 的网络资源分布不均匀，低层硬件平 台千差万别，所采用的网络协议也存 在着一些差异，因此用户通过不同的 。 通信子网传输数据时所经历的实际传 输速率、延时、丢失率等都会很不相 同，如图l 一2 所示。此外，不同用户 的设备处理能力方面往往也存在着非 常大的差异。 m o d e m ( 2 8 8 k b p s ) 图1 _ 2 网络的异构性 网络的异构性造成了组播中的不同用户可以获得的网络服务质量各不相同。而组播 应用是将同一份信息内容发送给处于不同子网段、不同网络接入方式以及不同类型的接 收方，在组播传统的单速率机制中，数据以相同的速率发送给所有的接收者，发送速率 是由具有最慢接收速率的接收者决定的，这使得所有接收者无论其接收能力如何都要受 瓶颈接收者的速率的影响，显然对具有较高带宽的接收者是不公平的，单速率组播极有 可能“淹没”慢接收者而又使快接收者“饥饿”，并且随着未来越来越多不同种类的网络 接入i n t e m e t ，i n t e r n e t 的规模不断扩大，异构性问题将更加严重。 那么如何以一种高效的方式控制数据流量传输、如何适应网络和用户设备的异构性 从而使得他们获得与其实际条件和需求相适应的接收质量，以保证网络资源的充分利用， 成为一个非常具有意义的研究课题。我们称此问题为会话内的公平性( i n l x a - s e s s i o n f a i m e s s ) 问题。解决这一问题的方法不止一种，本文我们将选择多速率组播的分层解决 山东师范大学硕士学位论文 方案作为研究对象。 1 2 2 会话间公平性问题 所谓会话间的公平性( i n t e r - s e s s i o nf a i l t l e s s ) 指的是网络资源在不同会话之间被公平 共享，包括组播流会话之间以及组播会话与t c p 会话之间的公平性，后者显得尤为突出。 这是因为目前l n t e m e t 超过8 0 的数据流量使用t c p 作为可靠传输协议，在网络拥塞时， 它们采用相同的拥塞控制机制对拥塞进行响应，因而可以保证它们在瓶颈链路上公平共 享带宽。而组播应用的广泛开展，引起了非t c p 通信量所占比重的增加，这些组播协议 典型地运行于u d p 之上，u d p 没有t c p 所具备的内建的拥塞控制机制，因此则可能会 对i n t e r n e t 产生巨大影响，特别是，没有拥塞控制机制的、尽最大努力交付的u d p 流可 能对竞争的t c p 流极不公平：当遇到拥塞时，所有参与的t c p 流立即减小它们的速率， 试图减轻拥塞，而非t c p 流继续以原速发送。这种极度不公平的情形会在瓶颈链路上遏 制t c p 通信，甚至导致拥塞崩溃p o j ，当网络中可利用的带宽被耗尽，所有的包在到达目 的地之前将会因拥塞而被丢弃。因而组播要想成功地在i n t e m e t 上应用，必须要流量控 制上保证能与t c p 友好共存，即保证与t c p 会话间公平性。 1 2 3 端到端流量控制的不足 目前，组播流量控制的研究集中于基于端到端的方案，由端系统的算法来实现，它 依赖于端系统的协调，网络层并不向源端提供任何显式拥塞指示，由于端系统无法了解 网络资源的使用情况，因此只能使用a c k 确认、r t o 定时器超时等隐含信号来推断网 络状态，控制注入网络的数据流量。但是这种机制对网络状态的响应速度较慢，因为它 从网络发生拥塞到端系统检测出数据包丢失并做出处理其时间大约滞后个r t t ，而在 这段时间内源端可能又向网络发送了大量数据，导致源端在做出处理之前己经丢失了更 多的数据包；同样如果网络上出现了空闲带宽，端系统也是难以很快获悉，导致网络资 源较长时间得不到充分利用。这样很难保证在组播的环境中解决扩展性、灵敏性和t c p 友好性问题，所以仅仅寄希望于所有应用都实现端到端的流量控制机制是不现实的也是 不够的，网络本身必须采用某种手段参与流量控制。 由于路由器是i n t e r n e t 的核心部件，是网络中不同流( f l o w s ) 的交汇处，也是 n t e m e t 网络状态最直接的感受者，所以网络层参与流量控制的最佳位置是路由器( r o u t e r ) 。所 以我们考虑将这一思想应用到组播当中，由i p 层参与资源的控制工作，在路由器中引入 相应的拥塞控制机制，作为对端系统的补充并与之协作，通过检测当前负载来要求端系 统增加或减少注入网络的流量，更能有效地对拥塞进行监测和预防，这将是解决组播流 量控制问题的更有效方法。 针对上述三个问题，我们分析认为由于多速率组播是组播环境中解决会话内公平性 9 山东师范大学硕士学位论文 问题的最有效、最有前途的办法，所以本文将多速率组播作为研究对象，在其基础上， 重点就组播中尚存在的会话间公平性问题以及端到端流量控制机制的不足之处进行研究 和改进，旨在获得满足公平性要求的、提高适应网络状态的灵敏性和资源利用的高效性 的流量控制方案。 1 3 本文的内容及主要的工作 本文针对上述问题，采用多速率组播作为解决组播会话内公平性问题的策略，并对 多速率组播! 日有的实现策路和流量控制机制进行改进和优化，采用发送方和接收方混合 驱动的流量控制模式，提出一种基于路由器辅助的、保证会话间m a x m i n 公平性的分层 多速率组播流量控制方案，并在网络模拟器n s l 5 5 】( n e t w o r ks i m u l a t o r ) 上对该方案进行 了详细的性能分析，实验结果表明该算法具有良好的可扩展性、稳定性和灵敏性，在公 平性方面显示出令人满意的效果。 本文的研究内容组织如下： 第二章多速率组播分层解决方案介绍。针对组播会话内公平性问题，讲述分层机制 的思想和有效实现会话内公平性方面的意义，给出现有工作，并分析比较了各种协议的 优缺点，指出了其中的不足之处。 第三章提出一种分层组播中的m a x m i n | 3 1 1 公平速率分配算法。通过一组仿真实验结 果分析现有分层多速率组播协议的基本速率控制机制对会话间公平性的不利影响，给出 m a x - m i n 公平速率分配的相关理论，提出一种分布式的、适用于分层组播环境的m a x - m i n 公平速率分配计算算法，以保证组播流会话之间以及组播流与t c p 单播流会话之间公平 共享网络资源，并设计出一种具体分层策略的便捷算法作为对计算算法的补充，将可行 速率分配集合从离散化的角度进行不月粒度上的整合。 第四章一种路由器辅助的分层组播流量控制方案的设计思想和实现。针对前面提出 的m a x m i a 公平速率分配算法在交付分层组搔协议中实旅时的一些问题，以及通过对分 层组播协议策略和同步点问题的分析，提出了一种有路由器上的主动队列管理算法 r e m l 5 1 】辅助的分层多速率组播流量控制策略，使路由器参与对网络拥塞或空闲状态的监 测与指示、辅助端系统进行流量控剑，源端利用路由器提供的网络状态信息来进行判断、 触发m a x m i n 公平速率分配算法的运行，并对现有多速率组播解决方案在同步协调接收 者加入或离开层的行为篆略上进行改进。 第五章仿真和性能分析。利用网络模拟器n s 2 对f l m 进行仿真实验，并通过观察 f l m 在灵敏性、可扩展性、公平性等方面的行为，分析了其有效性和合理性。仿真结果 表明，f l m 能对网络状态的变化能做出积极准确的响应，同时在会话内、会话间公平性 等方面均有良好的表现。 第六章结束语。论文工作总结，指出不足之处和未来的研究方向。 o 山东师范大学硕士学位论文 第2 章多速率组播的分层解决方案 本章介绍了多速率组播分层解决方案的实现机制，针对组播会话内公平性问题，讲 述分层策略的思想，给出现有工作，并分析比较了目前具有一定代表性的各种分层组播 协议的优缺点，指出了现存的问题。 2 1 会话内公平性问题的分析 会话内公平性( i n t r a s e s s i o nf a i r n e s s ) 问题是组播通信所特有的。在组播传统意义上 的单速率机制中，发送方根据最慢接收者的速率发送数据，这使得所有接收者无论其接收 能力如何都将以相同的速率接收数据，虽然可以较快地响应网络拥塞并精确地控制发送速 率，但在大规模异构网络中，由于组播分发树可能遍布于整个网络，其接收者往往具有异 构性，这种异 勾性主要表现在接收者的处理能力不同以及报文到达不同接收者所经历链路 的网络特性( 如带宽、延迟等) 不同，在这种情况下单速率机制显然对具有较高带宽的接收 者是不公平的，很大程度上降低了组播通信的效率，也限制了该机制的可扩展性。要实现 会话内公平性就是要求所有接收者在与组播源交互的过程中，均能接收到与其接收能力和 从组播源到接收者之间带宽相适合的数据流的接收速率，而不受同一应用中其它接收者速 率的限制，因此也称为接收者之间的公平性。 t _ j i a n g 给出了明确的接收者之间公平性的定义 2 2 1 1 5 9 】和评判组播会话内接收者之间公 平性的标准，假设一个组播组中有n 个接收者，接收者i 的期望吞吐量t i 为符合下述条件 的发送方速率： 1 从发送方到接收者i 的路径是组播树上发送方到接收者i 的同一条路径： 2 接收者得到的吞吐量不受其它接收者的影响。 显然，当接收者得到的实际吞吐量大于其期望吞吐量时，接收者接收数据的丢失率增 大；当接收者得到的实际吞吐量小于其期望吞吐量时，接收者路径的带宽没有有效利用。 我们假设接收者i 的实际吞吐量( 即组播发送方的发送速率) 为t ，定义接收者i 的公平函 数f ( f ) 满足： 1 f i ( t ) e 【0 0 ，1 0 l ； 2 f i ( t i ) = 1 0 ，t 。是接收者i 的期望吞吐量； 3 f i ( t ) 1 0 ，如果t h ； 4 f i ( t ) 在 0 ，t 】范围内是t 的非递减函数。即随着实际吞吐量增加，公平函数f ，( t ) 保 持不变或增大； 5 f t ) 在( t 。，0 0 ) 范围内是t 的非递增函数。即随着丢失率增加，公平函数f i ( t ) 保 山东师范大学硕士学位论文 持不变或减小。 一个满足上述条件的接收者i 的公平函数为：f i ( t ) = m i n ( t i ，t ) m a x ( t i ，t ) 。 在上述分析的基础上，接收者之间的公平性可定义为：i f r ( t ) 。：。f ，( t ) ，满足 ：，盘。= 1 t o l ，为各个接收者的权值，n 为接收者的数目，t 为各接收者的实际吞 吐量，f ，( t ) 为接收者i 的公平函数。 接收者间公平性的判定标准是：给定接收者i 的公平函数f i ( t ) ，权值强，可容忍的最 大丢失率l i ，如果组播协议使得组播流的实际吞吐量t + 满足：1 i f r ( t ) 取得最大值：2 所 有接收者的实际丢失率小于其可容忍的最大丢失率，则说该组播协议是接收者之间公平的 【5 9 l 从接收者间公平性( 即会话内公平性) 的角度出发，多速率组播( m u l t i r a t e m u l t i c a s t ) 则显然是异构网络环境下组播通信的有效手段。作为多速率组播典型实现方案的分层组播 ( 1 a y e r e d m u l f i c a s t ) ，是由发送方根据定的编码算法对数据流( 视频、音频信息或数据) 进行分层编码，并把得到的每一层数据编码用一个组播地址进行发送。接收者则根据从发 送方到其自身路径的可用带宽以及自身的处理能力独立地决定所能接收的层次，从而使得 同一个组播会话的不同接收者可以以不同的速率接收数据，能够比较理想地解决会话内公 平性问题。也就是说，多速率组播具有内在的会话内公平往特征。因此，分层组播是组播 机制中一种新的思路和方法，对分层组播的研究是当前网络界一个非常活跃的领域，我们 也相信分层组播在不久的将来会得到广泛的应用。 下文我们以组播的一种典型应用视频组播为例来详细介绍多速率组播的分层解 决方案。 2 2 关于组播视频传输 i n t e m e t 组播视频传输技术是众多的网络多媒体应用的基本组成模块，这些新涌现 的网络多媒体应用，包括网络电视台、远程教育、数字图书馆、电子商务等等，为人类 提供了一个更加丰富多彩、更加简单易用、价格更加低廉的信息获取和交流手段，因此 i n t e m e t 视频组播技术一经提出，就获得了广泛的关注和研究，取得了非常大的进展。 随着网络技术的发展和人们对实时视频服务需求的不断增长，视频如何在互联网上 进行高效、令人满意的实时传输成为国内外一个新的研究热点。视频的实时传输对带宽、 延时、包丢失率都有严格的要求，而目前的互联网是一个尽力而为( b e s te f f o r t ) 的网络， 并没有采取任何机制来保证服务质量( q o s ) ：同时，由于互联网上的主机性能的差异 和网络带宽的频繁变化，使得视频的实时传输变褥更加复杂。9 0 年代随着v i d e o c o n f e r e n c e 等应用的标准化，传统的t c p 、u d p 协议难以满足实时应用的需要，i n t e m e t 工程任务组( i e t f ) 在1 9 9 6 年特别制定了实时传输协议r t p r t c p f 2 ，其中r t p 是一个 山东师范丈学硕士学位论文 轻量级的协议，它建立在u d p 协议之上，r t p 数据报头部中的序号、时间戳、同步源标 识等信息为差错恢复、包丢失率估计、传输复用等监测手段提供了可能性，但是r t p 没 有在协议本身提供任何有关差错恢复、时延控制、抖动平抑、流量和拥塞控制等操作， 而把这些操作交由应用程序负责处理。今天的互联网常常因负荷过重而造成网络拥塞， 实时视频传输的高带宽低延迟使网络拥塞进一步加剧，因此，要解决视频在互联网上的 实时传输，就要解决如何有效利用网络带宽、降低时延和包丢失率等问题。 在视频组播异构性环境下，为兼顾多用户的带宽需求，速率控制上主要分为以下三 种方式： 2 2 1 单视频流组播 i n t e m e t 视频组播最基本的方式是单视频流组播f 5 8 j ( s i n g l e s t r e a mm u l t i c a s t ) 。在这种方 式下，发送方将一份视频流数据发送到一个i pm u l t i c a s t 通道，即一个i pm u l f i c a s t 地址。 所有的用户都加入这个i pm u l f i c a s t 组，接收这个通道的视频流，源只传输单一的视频编 码流，接收方负责向源发送反馈信息，如报文丢失率，源利用反馈信息来对视频编码输 出速率进行自适应控制。 单视频流组播的最典型例子是i v s ( i n r av i d e o c o n f e r e n c es y s t e m ) f 2 4 】。在i v s 中， 发送方将视频序列用h 2 6 1 协议进行压缩编码，然后打包成r t p 数据包序列，通过一个i p m u l t i c a s t 通道同时传送给多个接收者。接收者利用收到的r t p 数据包的序号估计出数据 丢失率，利用r t c p 将丢失率反馈给发送方。在大规模的视频组播应用中，为了防止大量 的用户反馈信息造成发送方网络的拥塞( 即所谓的“反馈爆炸”，f e e d b a c ki m p l o s i o n ) ， i v s 采用t a m m a r 在【2 5 】中提出的“概率性组播”( p r o b a b i l i s f i c m u l t i c a s t ) 技术控制了反 馈数据包的数量。发送方在统计了用户的反馈信息之后，动态地改变编码器的某些控制 参数，调整视频流的速率耻q 虽然单视频流组播方法可以达到一定的速率调整能力，但是存在着明显的缺陷。由 于i n t e m e t 是一个异构的网络环境，多个用户可以获得的实际数据传输速率存在着巨大 的差别，而单视频流组播方法在任意时刻，源只具有单一的视频信息输出速率，那些接 收能力高于当前视频输出速率的接收方无法获得公正待遇，而那些接收能力低于当前视 频输出速率的接收方又难以正确接收，无论怎样调整源输出速率，公平性都无法得到满 意解决。因此单视频流组播方式的速率控制算法远不能满足实际的需求。 2 2 2 多视频流重复组播 多视频流重复组播【5 引( r e p l i c a t e d s t r e a mm u l t i c a s t ) ，或称之为s i m u l c a s t ，是对单视 频流视频组播的一种扩展和改进，被认为是提供实用的i n t e m e t 视频组播服务的可选技 术，主要目的是解决异构性问题。 山东师范大学硕士学位论文 在该方式中，发送方在传输数据之前。将同一段视频内容编码成多个版本的视频流， 存储在流媒体服务器上，每个版本内容相同但是质量不同，因此传输速率也不一样。每 个流在不同的组播组中进行传输，接收方可以根据自己当前的网络服务质量选择加入适 合的组，获得与其网络带宽相适应的传输速率，接收同一流的所有接收方构成一个组。 一般情形下该方式利用一组独立的编码器对同一视频信号进行编码，不同的编码器具有 不同的输出速率。该方式虽在一定程度上解决了异构性问题，实现了一定的公平性，但 具有一个致命的弱点即：网络资源利用率低，它要求网络传输冗余信息，因此将耗费大 量带宽。 多视频流重复组播的典型代表是c h e u n g 、a m m a r 和l i 提出的d s g ( d e s t i n a t i o ns e t o m u p ) 方案【2 ”。d s g 方案还采用与i v s 一样的用户反馈源端自适应调整速率的方 法，所不同的是这里对每一个通道的视频流都需要建立独立的反馈控制通道，接收该视 频流的用户可以通过这个通道将观测到的网络服务质量信息传输给发送方，从而发送方 可以动态地对每个视频流的速率在一个给定的范围内独立地进行调整。如图2 1 示，在 d s g 方案中，发送方可以将原始视频序列压缩成低、中、高三种质量的视频流，它们分 别对应于低、中、高三种传输速率，这三个版本的视频流数据被发送到三个独立的i p m u l t i c a s l 通道中。图中所示的用户具有中等大小的网络带宽，因此它向网络申请接收中 等质量的视频流数据。在网络质量发生改变时，用户可以根据可用带宽的大小退出当前 的组播通道转而接收另一个速率更合适的组播通道中的视频流。 回 汐 圈岛国 囤 卜i i i i l c o d e dv i d e ov i d e os