（通信与信息系统专业论文）自适应动态分层多播拥塞控制算法研究和实现.pdf

南京邮电大学博士研究生学位论文 自适应动态分层多播拥塞控制算法研究和实现 摘要 异构性是i n t e r n e t 的固有特征，接入网络的多样性以及端系统处理能力的差异 是这种异构性存在的根源，并且随着i n t e m e t 规模的不断扩大，异构性问题将更加 突出。分层多播的提出为异构网络环境部署多媒体多播应用提供了可行的方案， 然而，它对网络流量状况的动态变化以及带宽资源需求无法得到保证的状况依然 缺乏解决办法。与此同时，当前i n t e m e t 上的大部分流量都是来自于t c p 应用，这 就要求分层多播应用应具有自适应能力以满足网络的动态变化，还能与t c p 流友好 相处，满足会话间公平性。针对上述问题，本文提出了适用于分层多播的具有较 强适应能力和满足公平性的拥塞控制方案a d l m ，并对a d l m 涉及的协议机制进行 了全面的剖析。论文的主要研究工作和所取得的成果如下： ( 1 ) 提出了自适应动态分层多播拥塞控制方案a d l m 。a d l m 是发送者和 接收者共同驱动，由路由器辅助流量控制的拥塞控制方案。a d l m 通过把发送者 的动态分层和接收者的自适应速率调整有机结合起来，不仅增强了分层多播的适 应能力，提高了系统的吞吐量，同时满足加权m a x m i n 公平性，较好地满足了t c p 友好性。 ( 2 ) 在a d l m 发送方的分层算法中，以接收者可用带宽为依据，提出了满 足加权m a x m i n 公平的速率分配算法，通过该算法得出接收者满足加权m a x m i n 公平的公平速率。在分层层速率分配方面，以系统吞吐量为指标，提出了基于最 优吞吐量的分层层速率分配算法，给出了算法的实现方法。 ( 3 ) a d l m 发送方的分层算法中，发送方是以接收方反馈的可用带宽为依 据进行分层算法的计算的，接收者也根据自己的能力调整接收层次，而两者的行 为都依赖于接收者估算的可用带宽。论文在可用带宽估算方面，在以满足t c p 友 好公式为基础的带宽估算方法基础上，对往返传输时间i 玎t 的测量方法进行了研 究，提出了i 汀t 和单向延时联合测量来估算r 1 r t 的新方法。 ( 4 ) 在流量控制机制方面，为了解决多播中存在的反馈内爆问题，针对接收 南京邮电大学博士研究生学位论文自适应动态分层多播拥塞控制算法研究和实现 方，在数理统计基础上提出了适合a d l m 的反馈抑制算法。同时为了避免发送者 频繁进行分层算法计算而导致网络的不稳定，提出了由路由器辅助流量控制的方 案，即由运行在路由器上的主动队列管理算法r e m 来辅助流量控制，发送方根 据经路由器处理的反馈信息对网络带宽进行判断，在满足一定条件的情况下触发 分层算法的运行。这两方面的措施保证了接收方不会频繁进行分层速率的调整， 提高了系统稳定性。 关键词：分层多播，拥塞控制，流量控制，反馈控制，公平性，t c p 友好，主动 队列管理，带宽估算 南京邮电人学博七研究生学位论文 自适应动态分层多播拥寒控制算法研究和实现 a b s t r a c t i n t e m e ts u f f e r sf r o mt h ep r o b l e mo fh e t e r o g e n e i t yd u et ot h ed i v e r s i t yo fa c c e s s n e t w o r k sa n dt h ed i f f e r e n c e si ne n ds y s t e m s c o m p u t i n gc a p a c i t y t h ep r o b l e mi se v e n a g g r a v a t e da si n t e m e tg r o w si ns c a l e l a y e r e dm u l t i c a s ti so n eo ft h es o l u t i o n st ot h e d e p l o y m e n to fm u l t i m e d i am u l t i c a s ta p p l i c a t i o n si nh e t e r o g e n e o u sn e t w o r k h o w e v e r , l a y e r e dm u l t i c a s tc a nn e i t h e rd e a lw i t ht h ed y n a m i c so fn e t w o r kt r a f f i cn o rm e e tt h e b a n d w i d t hr e q u i r e m e n t s m e a n w h i l e ，a st c p a p p l i c a t i o n sc o n t r i b u t e dal a r g ea m o u n t t oi n t e r n e tt r a f f i c ，o no n eh a n d ，l a y e r e dm u l t i c a s tn e e d st ob ea d a p t i v et on e t w o r k f l u c t u a t i o n s ，o nt h eo t h e rh a n d ，i ta l s on e e d st oc o e x i s tw i t ht c pi naf r i e n d l ym a n l i e r s u c ht h a ti n t e r - s e s s i o nf a i r n e s si sg u a r a n t e e d t oa d d r e s st h em e n t i o n e dp r o b l e m s ，a n a d a p t i v e l a y e r e dm u l t i c a s tc o n g e s t i o nc o n t r o ls c h e m e ，a d l m ，i sp r o p o s e di n t h i s d i s s e r t a t i o n t h eo p e r a t i o nm e c h a n i s mo fa d l mi sa l s os t u d i e di nd e t a i l t h em a i n c o n t r i b n t i o n so f t h ed i s s e r t a t i o na l ea sf o l l o w s ： ( 1 ) a na d a p t i v el a y e r e dm u l t i c a s tc o n g e s t i o ns c h e m e ，a d l mi sp r o p o s e d a d l m i saj o i n ts e n d e r - r e c e i v e rd r i v e na n dr o u t e r - a s s i s t e dc o n g e s t i o nc o n t r o ls c h e m e b y c o m b i n i n gt h ed y n a m i cl a y e r i n gt e c h n i q u ea ts e n d e ra n dt h ea d a p t i v er a t ec o n t r o la t r e c e i v e r , a d l mn o to n l yi m p r o v e st h ea d a p t i v e n e s sa n dt h r o u g h p u t ，b u ta l s os a t i s f i e s t h ew e i g h t e dm a x m i nf a i m e s sa n dt c p f r i e n d l i n e s s ( 2 ) u n d e ra d l m ，ar a t ec o n t r o la l g o r i t h m ，w h i c hs a t i s f i e sw e i g h t e dm a x - m i n f a i r n e s s ，i sp r o p o s e da tt h es e n d e rs i d ea c c o r d i n gt oe a c hr e c e i v e r sa v a i l a b l e b a n d w i d t h t h ea l g o r i t h mc a ng i v eaf a i rr a t ew h i c hs a t i s f i e sw e i g h t e dm a x - m i n f a i r n e s s i na d d i t i o n ，a no p t i m a l l a y e rr a t ea s s i g n m e n ta l g o r i t h mi sp r o p o s e dt o o p t i m i z et h es y s t e mt h r o u g h p u t t h ea l g o r i t h mi m p l e m e n t a t i o ni sa l s op r e s e n t e d ( 3 ) u n d e ra d l m ，t h es e n d e ra s s i g n si t sl a y e rr a t eu s i n gt h er e c e i v e r sf e e d b a c ko n a v a i l a b l eb a n d w i d t h t h er e c e i v e ra l s oa d j u s t si t sl a y e rs u b s c r i p t i o na c c o r d i n gt oi t s i i i 南京邮电大学博士研究生学位论文自适应动态分层多播拥塞控制算法研究和实现 c a p a c i t y b o t hd e c i s i o n sd e p e n do nt h er e c e i v e r se s t i m a t e da v a i l a b l eb a n d w i d t h t o e s t i m a t et h ea v a i l a b l eb a n d w i d t h ，t c p e q u a t i o ni sag e n e r a l l yu s e dm e t r i c i nt h i s d i s s e r t a t i o n ，an o v e lr t te s t i m a t em e t h o di sp r o p o s e d ，w h i c hc o m b i n e so n e w a yd e l a y w i t hm ( 4 ) u n d e ra d l m ，af e e d b a c ks u p p r e s s i o na l g o r i t h ma tr e c e i v e rs i d ei sp r o p o s e d t o c o p e w i t ht h ef e e d b a c k i m p l o s i o np r o b l e m i nm u l t i c a s t m e a n w h i l e ，a r o u t e r - a s s i s t e dt r a f f i cc o n t r o ls c h e m ei sp r o p o s e dt oa v o i df r e q u e n tl a y e rr a t ec h a n g e s a ts e n d e rw h i c hm a yr e s u l t i nn e t w o r kf l u c t u a t i o n t h er o u t e r su s ea c t i v e q u e u e m a n a g e m e n tr e m t oa s s i s tt r a f f i cc o n t r 0 1 t h es e n d e rw i l lf i r s tc h e c kt h er o u t e r s f e e d b a c ki n f o r m a t i o n w h e ns o m er e q u i r e m e n t sa r em e t ，t h el a y e r e dr a t ea s s i g n m e n t a l g o r i t h mi st r i g g e r e d t h ea b o v em e n t i o n e dm e t h o d sc a na v o i dr e c e i v e r sf r e q u e n t l a y e rr a t ec h a n g e sa n dt h e r e f o r ei m p r o v es y s t e m sr o b u s t n e s s k e y w o r d s ：l a y e r e dm u l t i c a s t ，c o n g e s t i o nc o n t r o l ，t r a f f i cc o n t r o l ，f e e d b a c kc o n t r o l ， f a i r n e s s ，t c pf r i e n d l y , a q m ，b a n d w i d t he s t i m a t i o n i v 南京邮i 乜大学博f ：研究生学位论义 臼适应动态分层多播拥寒控制算法研究和实现 a b r a d s l a i m d a t m c e c l r d c t d r r e c n f c f s f i f o f q j p e g h r r i e t f i g m p i s d n l d p l f p n s 缩略语词表 a v a i l a b l eb i tr a t e a s y m m e t r i c a ld i g i t a ls u b s c r i b e rl o o p a d d i t i v e i n c r e a s e - m u l t i p l i c a t i v e - d e c r e a s e a s y n c h r o n o u st r a n s f e rm o d e c o n g e s t i o ne x p e r i e n c e d c u r r e n tl i m i t i n gr e c e i v e r d i s c r e t ec o s i n et r a n s f o r m a t i o n d e f i c i tr o u n dr o b i n e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n f i r s tc o m ef i r s ts e r v e d f i r s t i n f i r s t 0 u t f a i rq u e u e i n g j o i n tp h o t o g r a p h i ce x p e r t sg r o u p h i e r a r c h i c a lr o u n dr o b i n 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 n t e r n tg r o u pm a n a g e m e n tp r o t o c o l i n t e g r a t e ds e r v i c e sd i g i t a ln e t w o r k l o s sr a t ed if 琵r e n t i m i o np a r a m e t e r l o s sr a t ef a i r n e s sp a r a m e t e r s n e t w o r ks i m u l a t o r 1 1 7 可用比特率 对称用户线环路 和式增加积式减 少 异步传输模式 经历拥塞 当前受限接收者 离散余弦变换 逆差轮循 显式拥塞指示 先到先服务 先入先出 公平队列 联合图像专家组 分级轮循 i n t e r n e t 工程部 因特网组管理协 议 综合业务数字网 丢失率区分参数 丢失率公平参数 网络仿真器 南京邮l 乜人学博。i ：i i j f 究生学位论文 臼适心动态分层多播拥塞控制算法研究和实现 n t p p h b r s v p l 玎c p r t p s p t c p v o d n e t w o r kt i m ep r o t o c o l p e r - h o p b e h a v i o r r e s o u r c er e s e r v a t i o np r o t o c o l l 玎pc o n t r o lp r o t o c o l r e a l t i m et r a n s p o r tp r o t o c o l s y n c h r o n i z a t i o np o i n t t r a n s m i s s i o nc o n t r o lp r o t o c o l v i d e oo nd e m a n d 1 1 8 网络时间协议 逐跳行为 资源预留协议 r t p 控制协议 实时传输协议 同步点 传输控制协议 视频点播 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作和取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写的研究成果，也不包含为获得南京邮电大学或 其它教育机构的学位论文或证书而使用过的材料。与我一同工作的同志对本 研究工作所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆保留本人所送交 学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论 文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内 容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：导师签名 南京邮电人学博士研究生学位论文自适应动态分层多播拥寨控制算法研究和实现 第一章引言 近年来，随着因特网( i n t e m e t ) 的快速发展，出现了视频点播、电视会议、 远程教学和学习、计算机协同工作等新业务，如果依靠传统的点到点通信方式来 传送这些新业务，不仅浪费了大量的网络带宽，而且效率很低。针对这个问题， 能有效利用现有网络带宽的多播技术便随之出现并得到了迅速发展。多播是一种 点到多点( 或多点到多点) 的通信方式，即多个接收者同时接收发送源发送的相同 信息。由于多播能较好地满足接收者的异构性，因此多播技术的出现推动了各种 计算机网络中媒体业务的应用，多播拥塞控制技术因此也成为了当前研究的热门。 1 1i p 多播技术介绍 单播( u n i c a s t ) 是发送者与接收者点到点的连接，信息的发送和传递只在发 送者和接收者两个节点间进行。 多播( m u l t i c a s t ) 是一种允许一个或多个发送者( 多播源) 发送单一的数据 包到多个接收者的网络技术。多播源把数据包发送到特定多播组，而只有属于该 多播组的地址才能接收到数据包。在i p 多播通信中，无论有多少个目标地址， 在整个网络的任何一条链路上只传送单一的数据包，所以可以大大地节省网络带 宽。多播同时是一个基于接收的概念：接收者加入一个特定的多播组，信息是通 过网络的底层传输到组旱的每个成员；发送端不用维护接收者的列表：任何网络 中的连接只会有一个多播信息包通过，当网络连接在路由器处分岔时信息包则被 复制到不同的分岔上去。这样，通过使用i p 多播技术，网络传输的性能得以改 进，端到端的网络带宽也得以保护。单播传输和多播传输的示意图如图1 1 所示。 南京邮电大学博士研究生学位论文自适应动态分层多播拥塞控制算法研究和实现 1 只播馋齄 多摇佟搪 图1 1 单捅传输和多播传输的示意图 点到多点的多播通信研究的目的是为了支持多个接收者同时接入信息源服 务，典型的点到多点的多播应用包括v o d 点播、会议电视、远程教学等。 m a x e m c h u k t l l 认为，多播通信需要适应未来的有偿服务，且应面向多个接收者不 同需求而提供服务，多播异构性( h e t e r o g e n e i t y ) 问题就是在这种情况下被提出来 的。 异构性指的是由于多播组成员自身的接收能力以及网络可用带宽的不同而造 成的发送者与每个接收者各连接的不对等性。多播通信中的异构性问题主要表现 为两种。一种是网络异构性：在目前的网络环境下，用户的接入设备多种多样， 如采用i s d n 基本速率的链路，数据链路速率只有1 2 8 k b s ，而采用x d s l 接入 的设备，下行数据链路速率可高达每秒几十兆比特。当各个用户通过不同接入设 备接入信息源服务时，必然存在如何根据用户不同的接入网络传输速率、不同的 终端处理能力来完成从信息源到接收者的数据传输问题；另一种是接收者异构性 需求问题：即使接收者的网络接入设备相同，但各用户的服务需求也会有所不同， 特别对于有偿信息服务的情况，多播服务应根据用户的不同服务需求提供按需和 按质服务。在这种情况下，若按照最大处理能力或者最高服务需求的用户要求提 供服务，则将导致低需求用户无法得到服务。而若按照最低用户需求提供服务， 2 南京邮电大学博士研究生学位论文自适应动态分层多播拥塞控制算法研究和实现 则高需求用户将无法得到期望的服务。这个问题将导致在多播会话中，接收者无 法得到公平服务。 为了更好地解决多播通信中的异构性问题，多播拥塞控制方案中出现了分层 多播技术。分层多播以分层编码技术为基础，分层编码可以将信源信息逐层划分 成多个离散子码流：对低层子码流解码得到的是低质量的接收信息；而当收到多 层子码流时，解码器将这些码流组合解码可得到更高质量的接收信息。在分层多 播协议的实施方案中，发送者采用分层编码的方式将视频和音频数据进行编码并 同时向多个多播组传输，接收者根据自己的接收能力加入到相应的分层接收数据， 当可用带宽发生变化时，接收者通过加入或离开多播分层的方式实现适应性的自 我调节。 现有的分层多播拥塞控制方案虽然在一定程度上满足了网络的异构性，但也 存在一些问题： ( 1 ) 接收者驱动的分层多播特点决定了接收者要定期地加入和离开多播组来 适应网络状态的变化，这样随着网络动态性的增加，会出现多播路由和接收者速 率自适应的负担过重、整体视频接收质量不稳定的问题。并且发送者每层编码速 率不变，不能很好地适应接收者可用带宽的变化，网络带宽利用率不高。 ( 2 ) 端到端拥塞控制依赖于端系统的协调，网络层并不向源端提供任何显式 拥塞指示。由于端系统无法了解网络资源的使用情况，只能使用a c k 确认、r t o 定时器超时等隐含信号来推断网络状态，控制注入网络的数据流量，因此对网络 拥塞响应缓慢，特别是对网络内部的短暂拥塞响应更为迟钝。这主要是由于分层 多播依赖接收者通过不断加入和退出多播组来判断和适应网络状态的变化。而 i g m p 离开操作本身具有较大的延时，所以离开操作的收敛速度较慢，并且会导 致多播树结构经常变化，加重路由器的负担。 通过对典型的分层多播拥塞控制技术的研究，我们发现分层多播虽然较好地 满足了接收者的异构性，但其静态的分层策略( 发送的分层数目和分层的各层速 率都是固定不变的) 并不能很好地满足接收者接收能力变化或网络可用带宽变化 的要求。因此本文针对静态分层和接收者驱动拥塞控制所带来的问题，提出了自 适应动态分层多播拥塞控制算法，并对算法的控制机制进行了深入研究。 南京邮电大学博士研究生学位论文自适应动态分层多播拥塞控制算法研究和实现 1 2 论文研究的关键问题 分层多播因为能较好地满足接收者的异构性，因而为多媒体多播应用在因特 网上的部署提供了有效的手段。然而不合理的静态分层策略非但不能提高应用系 统的工作效率，反而可能导致网络长期处于低效状态。本文即是针对该问题展开 研究，提出具有自适应能力的分层多播拥塞控制算法。为了使算法切实可行，我 们在给出算法总框架的基础上，依照发送方、接收方和中间路由器在算法中的功 能把算法细分到各子模块，对各子模块进行分析研究。论文需要解决的问题包括： ( 1 ) 会话间公平性问题 会话间公平性即多会话接收者之间的公平性是多播拥塞控制方案设计过程中 一个很重要的问题。由于t c p 在因特网中的主导地位，会话间公平性首先需要 保证的是多播流与t c p 流问的公平性，即t c p 友好性。任何多播协议要得到 广泛应用必须确保与i n t e m e t 中占主导地位的t c p 流友好、公平地共享链路资 源，因此选择一种合理的公平性原则是解决会话间公平性问题的关键，也是本文 研究的重点。 ( 2 ) 分层层速率分配问题 采用静态分层、固定层速率的策略虽然能在一定程度上解决异构性问题，但 却无法使得系统性能达到最优，特别是对发送速率与接收者的可用带宽不能较好 匹配的情况。层速率分配算法即是考虑在给定接收者可用带宽的情况下，如何合 理分配各分层的传输速率从而使得系统性能尽可能地达到最优。考察系统性能的 指标可以有多个，如吞吐率、链路利用率、时延等等。因此在选择某种性能指标 的前提下，提出能使系统性能得到优化的分层层速率分配算法也是本文研究的重 点。， ( 3 ) 可用带宽的估算问题 在我们的拥塞控制算法中，发送方是以接收方反馈的可用带宽为依据进行分 层算法计算的，接收者也根据自己的能力调整接收层次，两者的行为都依赖于接 收者估算得到的可用带宽。因此，合理、及时地测量出可用带宽也是我们需要解 决的一个关键问题。 ( 4 ) 流量控制问题 在我们的算法中，发送方依据接收者所发回的反馈信息进行分层算法计算。 4 南京邮电大学博士研究生学位论文 自适应动态分层多播拥塞控制算法研究和实现 在接收者数目较多、网络带宽变化频繁的情况下必然会出现大量反馈信息返回给 发送者的情形，从而导致反馈内爆。如果简单地要求接收者降低反馈频度，则必 将意味着发送者的适应度降低。为此，我们将对这一问题进行研究，提出合理的 流量控制策略以解决该问题。 1 3 论文的组织结构 论文的主要内容如下： 第一章引言，对论文提出的背景和所要解决的问题进行了总结。 第二章对现有多播拥塞控制方案进行了综述。介绍了多播拥塞控制的机制， 对现有典型的多播拥塞控制算法进行了分类和介绍，分析了多播拥塞控制算法的 评价标准。最后指出了多播拥塞控制存在的问题，提出了多播拥塞控制算法的设 计原则。在对现有分层多播方案分析的基础上，本章提出了自适应动态分层多播 拥塞控制方案。明确了算法的研究背景和研究目标，给出了算法实现框图，介绍 了方案所需要解决的问题：( 1 ) 发送者分层算法；( 2 ) 可用带宽估算；( 3 ) 流量 控制。 第三章研究在已知接收者可用带宽情况下的层速率分配问题，提出了满足加 权m a x m i n 公平的基于最优吞吐量的层速率分配算法。 第四章重点分析了接收方可用带宽的估算方法。首先分析了现有的可用带宽 计算方法，然后提出了满足t c p 友好的可用带宽计算方法，对估算可用带宽所需 要的参数进行了研究，提出了这些参数的计算方法。 第五章研究了拥塞控制方案所需要的流量控制。提出了在网络中由路由器辅 助流量控制的方案。同时论文也将数理统计的成果引入到接收方进行反馈控制。 第六章对控制方案在网络仿真软件n s 平台上进行了仿真。通过观察我们的 方案在系统吞吐量、公平性、灵敏性等方面的行为，分析了其有效性和合理性。 仿真结果表明，该方案能对网络状态的变化做出积极准确的响应，同时在公平性、 提高吞吐量等方面均有良好的表现。 第七章结束语。总结论文的工作，给出了对相关领域今后进一步发展的展望 和研究思路。 南京邮电大学博士研究生学位论文 自适应动态分层多播拥塞控制算法研究和实现 1 4 论文的主要贡献 论文的主要贡献可以概括为以下几点： ( 1 ) 提出了自适应动态分层多播拥塞控制方案a d l m 。a d l m 是发送者和 接收者共同驱动，由路由器辅助流量控制的拥塞控制方案。a d l m 克服了接收者 驱动和端到端拥塞控制所带来的问题，增强了分层多播的自适应能力，提高了系 统的带宽利用率，同时它也较好地满足了t c p 友好性。 ( 2 ) 提出了满足加权m a x m i n 公平的速率分配算法。以系统吞吐量为指标， 提出了基于最优吞吐量的分层速率分配算法，给出了算法的实现方法。 ( 3 ) 可用带宽估算方面，在满足t c p 友好公式的带宽估算方法基础上，对 r t t 的测量方法进行了研究，提出了r t t 和单向延时联合测量来估算r 1 盯的新 方法。 ( 4 ) 流量控制机制方面，提出了路由器辅助流量控制的方案，由路由器上的 主动队列管理算法r e m 来辅助流量控制。针对接收方，基于数理统计基础上提 出了适合a d l m 的反馈抑制算法。这两方面的措施保证了发送方不会频繁进行层 速率的调整，提高了系统稳定性和可靠性。 6 南京邮电大学博七研究生学位论文 自适应动态分层多播拥塞控制算法研究和实现 第二章多播拥塞控制综述与自适应 动态分层多播拥塞方案介绍 本章首先对现有的多播拥塞控制方案进行了总结，分析了现有多播拥塞控制 方案的一般特性，分析了多播协议设计的要求，总结出目前的研究进展。然后对 现有典型的多播拥塞控制方案进行了分类，介绍了各方案的特点。分析了多播拥 塞控制方案的评价标准，并对各介绍方案进行了评价。最后总结了多播拥塞控制 中存在的问题，提出了一般解决方法，归纳出多播拥塞控制算法的设计原则。 针对现有分层多播控制算法中存在的问题，本章提出了自适应动态分层多播 拥塞控制方案a d l m ，提出了研究背景，给出了a d l m 算法的系统框图，最后 对算法的协议机制进行了分析。 2 1 多播拥塞控制概述 单播和多播都需要通信量调节以避免和控制拥塞，与多播拥塞控制相关的问 题包括通信量调节、多播组管理、数据分层和编码、路由器功能，而在其中通信 量调节是最关键的问题。 2 1 1 通信量调节 在t c p 会话中，拥塞控制只通过通信量调节来完成。t c p 通信量调节的四个 属性分别是：窗口大小，发送者，反馈a c k ，a i m d e 2 j 。同样多播的通信量调节 也可以定义为一个四元组( r p ，r i ，c i ，r a ) 。 端到端多播拥塞控制的通信量调节可以用四个属性描述：调节参数 ( r e g u l a t i o np a r a m e t e r ，r p ) 、调节者( r e g u l a t i o ni n i t i a t o r ，r i ) 、拥塞信号( c o n g e s t i o n i n d i c a t o r ，c i ) 、调节算法( r e g u l a t i o na l g o r i t h m ，r a ) 。这四个属性足以描述调 节过程，当c i 显示网络拥塞时，多播拥塞控制方案在刚处通过调节r p 来实现 7 南京邮电大学博士研究生学位论文自适应动态分层多播拥塞控制算法研究和实现 r a 以进行拥塞控制。 ( 1 ) 调节参数 调节参数指的是在拥塞发生时，需要进行调整的参数。这个参数可以是窗口 大小，也可以为传输速率。基于窗口的算法使用一个拥塞窗口来保持未确认的数 据分组的数量低于给定的大小，也就是说只有当拥塞窗口还有未分配空间时，发 送者才可以向网络发送新数据。同样地，基于速率的算法通过调节传输的速率来 控制拥塞。对于流媒体而言，考虑到其连续性和基于速率算法的平滑调节，使用 基于速率的算法要比基于窗口的算法更为适合。 ( 2 ) 调节者 调节者是指执行调节算法的主体，它可以是发送者也可以是接收者。发方驱 动的方案是由发送者检测拥塞发生，并且调节相应的参数，发方驱动具有设计简 单的特点。收方驱动的方案将调节算法的执行转移到接收者一边。对多播而言， 由于通信量调节被分布到多个接收者之间，采用收方驱动的方案具有更好的可扩 展性。而发方收方联合驱动的方案被提出以提供更好的可扩展性。 ( 3 ) 拥塞信号 拥塞信号指示网络中发生了拥塞，该信号可以是显式的( e x p l i c i t ) 也可以是隐 式的( i m p l i c i t ) 。当拥塞发生时，等待路由器转发的数据分组数量超过路由器的缓 存的大小，于是溢出的分组被丢弃。显式的拥塞信号需要路由器的支持。具有检 测初始拥塞发生功能的路由器可以对分组头的c e 位进行标记，指示拥塞发生。 由于目前i n t e m e t 路由器大都不支持显式拥塞信号，因此端到端的多播拥塞 控制方案主要采用隐式拥塞信号。隐式拥塞信号包括分组丢失( p a c k e tl o s s ) 、丢 失率( 1 0 s sr a t e ) 、分组延时( p a c k e tq u e u e d ) 等。分组丢失是拥塞发生的最直接表 _ 1 k 现，a c k 和n a k 都可以反映分组丢失。a c k 指示正确收到分组，n a k 指示没 有收到分组。但a c 妁，n a k 只能反映即时的网络状态。丢失率也可以指示拥塞， 它是丢失的分组与总的传输的分组的比率。与a c k n a k 相比较，丢失率更能反 映一段相对长时间内的网络拥塞状态。但是考虑到适当的计算间隔很难确定，丢 失率并不像a c k n a k 那样容易检测，间隔太短不能消除猝发性( b u r s t y ) ，而间隔 8 南京邮电大学博士研究生学位论文自适应动态分层多捅拥寨控制算法研究和实现 太长又可能使调节没有效果。分组延时也可以作为拥塞信号，作为拥塞的结果， 已经传输的分组被缓存在网络中，如果最近一次的往返时间( r t t ) 超过平均的 r 1 盯，那么暗示网络中可能存在拥塞。然而，由于通信量猝发性的存在，也有可 能产生突发的i h t 延时。过了这个r r t 延时，r t t 又恢复正常。因此这种情况 下的调节是不必要的。如何确定延时是突发的还是持久的，也是一个难题。 ( 4 ) 调节算法 调节算法的作用是根据反馈，改变调节参数的值。调节算法可以在收端也可 以在发端执行。调节参数的不同导致调节算法在细节上的实现也不同。基于窗口 的算法保持未确认的分组数量低于拥塞窗口的大小。最简单的基于速率的算法就 是保持瞬时的传输速率低于由反馈计算得到的值，这类算法类似于t c p 采用的 a i m d 算法，数据传输速率的波动很大。基于速率的调节算法可以根据反馈，调 节参数，使速率满足t c p 的吞吐量方程。更复杂的基于方程的改变速率的算法 可以消除短期的波动性。 2 1 2 多播组管理 多播组管理定义了多播的组成员和组通信的模型。组通信模型可以分为一对 多( o n et om a n y ) 和多对多( m a n y t om a n y ) ，前一种可以认为是后种的特殊情况。 组成员在多播连接中可以是动态的也可以是静态的。静态的组成员模型要求一旦 连接建立后，就不允许新的接收者加入，也不允许已连接的成员离开。动态组成 员模型中，任何接收者都可以加入和离开。从接收者的观点来看，多播组成员的 资格可以是被接收者自己取消，也可能是被多播会话取消。组成员的不确定性使 得多播拥塞控制算法的设计更加复杂，但同时也有益于算法设计：一方面动态的 组成员带来了新问题，如所有接收者接收一个特定的数据包是否合适；另方面， 多播会话可以将某些接收者取消来避免拥塞。多播组管理也和数据分层与编码有 密切联系。 9 南京邮电大学博士研究生学位论文自适应动态分层多播拥塞控制算法研究和实现 2 1 3 数据分层和编码 多播组成员的异构性是一个相当实际的问题。不同的接收者具有不同带宽， 如果发送者以同一速率发送数据，低带宽的接收者可能遭受拥塞，而高带宽的接 收者仍然没有充分利用其可用带宽。 数据分层技术就被用来解决异构性问题。源数据被编码成若干层，这些层之 间可以是相关的也可以是非相关的。相关型层可以组合起来提供逐步渐进的接收 质量。不同层的数据被发送到不同的多播地址，接收者可以根据自己的带宽限制 接收尽可能多的层。相关型层还可以进一步分为累加型( c u m u l a t i v e ) 层和非累加 ( n o n c u m u l a t i v e ) ) = 罢 3 1 。累加型层的各层之间的数据需要的带宽是相同，接收者 需要按顺序预定和取消不同的层。非累加型层不限于此，层之间的数据所需的带 宽可以是不同的。非相关型层方案中，各层提供不同的速率，这些层不能累加， 每个接收者只能根据自己的带宽限制接收一个合适的层。非相关型层会传送一些 冗余数据。 除了分层技术外，编码转换( t r a n s e o d i n g ) 也被用来实现不同带宽的接收者获得 不同的速率。源发送者以能满足最快的接收者的速率发送数据，在每一个中间节 点( 可以是路由器，也可以是接收者) ，速率被重新编码转换以适应下行链路最快 的接收者，这样不同带宽的接收者就可以得到其合适的接收速率。 2 1 4 路由器功能 根据i s o o s i 的参考模型，拥塞控制在网络层和传输层都可以实现。可是在 i n t e m e t 的i p 层中，只提供尽力而为( b e s t e f f o r t ) 的每跳转发，要在i p 层进行拥 塞控制，就必须对i p 协议加入新的协议组件。r s v p 4 】就增加了路由器支持功能 来提供q o s 保证，这点类似虚电路的数据传送。价格机制( p r i c i n gm e c h a n i s m ) p j 同样需要路由器额外支持( r o u t e r - s u p p o r t e d ) 以达到“付出越多收获越多”的原 则。在i p 层加入e c n 6 也可以避免拥塞。以上的拥塞控制机制可以定义为需要路 由器支持的拥塞控制方案。然而目前的网络并没有广泛部署具有这些功能的路由 器，因此传统的在传输层实现端到端的拥塞控制方案是目前主要采用的方案。 在拥塞算法中路由器功能主要分为：队列管理( q u e u em a n a g e m e n t ) 和队列 l o 南京邮电大学博士研究生学位论文自适应动态分层多播拥寨控制算法研究和实现 调度( q u e u es c h e d u l i n g ) 。当网络发生拥塞时，路由器必须丢弃一些分组，这个问 题的解决首先必须实施有效的队列管理机制( 或缓冲区管理策略) 。在队列管理算 法中，r e d t 7 】算法具有较低的排队时延、较高的分组通过度( o o o d p u t ) 和较好的公 平性，其主要思想是：路由器计算平均排队长度，当平均排队长度超过某一门限 时，路由器按照某一概率丢弃到达的分组，而这个丢弃概率是与平均排队长度成 正比的。r e d 算法允许短时的分组突发，因而可以避免因为网络负荷变化造成的 分组丢弃。同时它能避免多t c p 连接时的超时重传，从而保持高带宽利用率。队 列调度的功能就是路由器如何从多个( 或一个) 队列中选择下一个待转发的分组， 这与队列管理机制有着本质的区别。根据不同的服务规则，队列调度算法可以分 为以下几种：先到先服务、循环调度、处理机共享、优先级服务、随机服务等。 除了队列管理和队列调度，一些多播拥塞控制方案还需要路由器提供一些其 他功能，如r 1 陌估计、反馈聚集等等，来满足这些方案对多播拥塞的控制。 如果一个多播拥塞控制方案仅需要路由器提供d r o p t a i l 队列和f i f o ( 先到先 服务) 调度，那么我们称这种方案是不需要额外路由器支持的方案。 2 1 5 多播拥塞控制所遇到的难点 随着接收者数目的增大，计算机终端系统和网络的异构性会使得多播拥塞控 制变得更为复杂和困难。在设计一套合适的多播拥塞控制方案时，许多问题( 如 设计者能否将t c p 拥塞控制机制应用在多播拥塞控制中、设计的控制方案是否稳 健、能否与现有的t c p 共存) 不可避免地都要加以考虑。更重要的是，不同应用 的多播需要不同要求的拥塞控制。可靠多播，如文件传输，需要传输稳定可靠， 因此拥塞控制必须要处理差错恢复以满足这个要求；实时流多播应用，如视频会 议，对延时和带宽比较敏感，但对可靠性要求不高。因此设计不同应用的多播拥 塞控制方案时都要把这些因素加以考虑。 2 2 多播拥塞控制方案分类 针对不同的应用，目前出现了许多多播拥塞控制方案。我们可以根据上节讨 论的多播拥塞控制组件( 通信量调节、多播组管理、数据分层和编码、路由器功 南京邮电大学博士研究生学位论文自适应动态分层多播拥寨控制算法研究和实现 能) 对这些方案进行分类。在这四个控制组件中，数据分层和编码是最重要的分 类标准。根据这个标准，我们把多播拥塞控制方案分为两类：单速率( s i n g l e - r a t e ) 拥塞控制方案和多速率( m u l i r a t e ) 拥塞控制方案。 2 2 1 单速率多播拥塞控制方案 在单速率拥塞控制算法中，发送者以相同速率发送数据包给接收者。其优点 在于无需特定编码、容易实现。其缺点在于由于发送速率取决于瓶颈链路带宽最 小的接收者，所以不能适用于异构性强的接收组，系统的带宽利用率不高，扩展 性不好。下面我们