（计算机应用技术专业论文）组播拥塞控制中相关问题的研究.pdf

摘要 j y 5 7 3 3 12 随着视频点播、电视会议、远程教育、网络交互式游戏等实时性业务的兴起， 组播技术得到了广泛的应用。这些实时业务一般在i p 组播之上，采用u d p 协议 进行传输。然而，由于u d p 协议和i p 组播都不提供拥塞控制机制，导致这些业 务和t a p 业务共存时出现了带宽占用的不公平性，因此组播拥塞控制便成为一项 重要的研究课题。 本文就组撬拥塞控制中的拥塞快速响应，反馈抑制，协议的公平性三个方面 的问题进行了分析和研究。 第一部分针对网络拥塞的快速响应，从路由器队列管理的角度，提出一种新 的算法。所提出的算法在平均队列长度超过一个参考值之后，根据数据包到达队 列的速度来进行丢包和标记，这样它能及时发现拥塞，通知发送方进行速率调整， 而且该算法具有更好的稳定性和对网络状态的自适应性。 第二部分针对组播应用中的反馈爆炸问题，改进路由器的功能，提出一种新 的反馈抑制算法。该算法由主动路由器参与拥塞控制，结合了反馈延时法和主动 路由器的反馈汇聚方法来解决反馈爆炸问题：由于主动路由器可以缓存数据进行 局部恢复，所以该算法可以应用于可靠组播，且它和一些经典的可靠组播算法相 比较，具有更高的带宽利用率和更小的传输延时。 第三部分研究协议的公平性，在现有的t c p 友好协议t f m c c 的基础上，针 对传送实时流媒体时出现的链路振荡问题，提出改进算法。改进的算法根据丢包 率和t c p 友好性来调整传输速度，并且对传输速度的调整步长进行了平滑。该算 法能更好的解决链路振荡问题、满足协议的公平性和t c p 友好性。 最后，利用n s 网络模拟器对前面三部分提出的各种算法进行了仿真，并且 验证了其结果的正确性。 关键词：组播，拥塞控制，反馈抑制，主动队列管理，主动网络 a b s t r a c t w i t ht h es p r i n g i n gu po fr e a l - t i m es e r v i c e s ，s u c ha sv o d ( v i d e o0 nd e m a n d ) ， v i d e o c o n f e r e n c i n g ，d i s t a n c el e a r n i n g ，n e t w o r k i n t e r a c t i o n g a m e ，m u l t i c a s t i s c o n s i d e r e dt oo n eo ft h ew i d e l yu s e dt e c h n o l o g i e s b u tm u l t i c a s tb a s e do nu d p c a n n o to f f e rc o n g e s t i o nc o n t r 0 1 a tt h ep r e s e n tt i m e ，t h a te x i s t i n gt c p a p p l i c a t i o n s ，a s t h em a i na p p l i c a t i o n si nt h ei n t e r n e t ，o f f e rc o n g e s t i o nc o n t r o lh a v em a d ei ti m p o r t a n t t oe n s u r et h ef a i r n e s sw h e nm u l t i c a s tc o e x i s t sw i t ht c p p r o t o c o l s t h e r e f o r es t u d yo f c o n g e s t i o nc o n t r o la b o u tm u l t i c a s ti sb e c o m i n g a n i m p o r t a n ts u b j e c t t h ep a p e rs o l v e st h r e e p r o b l e m s o fm u l t i c a s t c o n g e s t i o nc o n t r o l ：q u i c k l y r e s p o n s et on e t w o r kc o n g e s t i o n ，f e e d b a c ks u p p r e s s e da n d f a i r n e s so f p r o t o c 0 1 f i r s t l y , a i m i n g a t q u i c k l yr e s p o n s et o n e t w o r kc o n g e s t i o n ，t h ep a p e ra n a l y s e s s o m e e x i s t i n g a c t i v e q u e u em a n a g e m e n ta l g o r i t h m a n d b r i n g s f o r w a r dan e w a l g o r i t h m w h e na v e r a g el e n g t ho fq u e u ee x c e e d sar e f e r e n c ev a l u e ，t h ea l g o r i t h m a d j u s t st h er a t eo fp a c k e tl o s sp e r c e n t a g ea c c o r d i n gt ot h ep a c k e ta r r i v i n gr a t e i t s q u e u el e n g t hk e e p s a r o u n dt h er e f e r e n c e v a l u e ，s o i th a sm o r e s t a b i l i t y a n d s e l f - a d a p t a b i l i t yt on e t w o r kc o n g e s t i o n s e c o n d l y ，t a k i n gf e e d b a c ki m p l o s i o ni n t oa c c o u n t ，t h ep a p e ru s e s t h ea c t i v e n e t w o r kt e c h n i q u ef o r i m p r o v i n gr o u t e r s f u n c t i o n sa n db r i n g sf o r w a r dak i n do f c o n g e s t i o n c o n t r o lt h a ti sc o n c e r n e dw i t ht h er o u t e r , w h i c hi m p l e m e n t sf e e d b a c k a g g r e g a t i o na n dl o c a lr e c o v e ro f l o s tp a c k e t h a v i n gb e e ns i m u l a t e da n d a n a l y z e d ，t h e a l g o r i t h mh a s b e e nt e s t i f i e dt oh a v eb e t t e rs c a l a b i l i t ya n du t i l i z a t i o no fb a n d w i d t h t h i r d l y , a i m i n g a tf a i r n e s so f p r o t o c o l ，t h ep a p e r b a s e d o nt h e e x i s t i n g t c p f r i e n d l ym u l t i c a s tc o n g e s t i o nc o n t r o l ( t f m c c ) ，c o n s i d e mt h ep r o b l e mo ft h e d i t h e r i n g o ft r a n s m i s s i o nr a t ew h e nt h em u l t i m e d i as t r e a mi st r a n s f e r r e d ，a n dp r o p o s e s a l l i m p r o v e da l g o r i t h m t h ei m p r o v e da l g o r i t h ma d j u s t s i t s t r a n s m i s s i o nr a t e a c c o r d i n g t ot h ep r o b a b i l i t yo f p a c k e tl o s sa n dt c p - f r i e n d l i n e s s ，a n ds m o o t h e si t sr a t e a d a p t a t i o n t h ea l g o r i t h mc a np r e f e r a b l ya l l e v i a t et h ed i t h e r i n go ft r a n s m i s s i o nr a t e a n de n s u r e i n t r a p r o t o c o l sf a i r n e s sa n dm e e t t c p f r i e n d l i n e s s f i n a l l y , n s ，aw i d e l y u s e dn e t w o r ks i m u l a t i o nt o o l ，i su s e dt o a n a l y s e sa n d v a l i d a t e st h e p e r f o r m a n c e o ff o r e n a m e d a l g o r i t h m s k e y w o r d s ：m u l t i c a s t ，c o n g e s t i o nc o n t r o l ，f e e d b a c ks u p p r e s s e d ，a c t i v e q u e u e m a n a g e m e n t ，a c t i v en e t w o r k l i 第一章绪言 近年来互联网的飞速发展产生了很多新应用，特别是高带宽需求的多媒体应用， 视频传输带来的网络带宽问题更为突出。为了缓解网络的瓶颈问题，减轻主干网的 负担，组播( m u l t i c a s t ) 技术由此产生。 组播报文是通过u d p ( 用户数据报协议) 进行传输的，所以它缺乏t c p 传输控制 协议所提供的可靠传输的功能。所以必须对组播传输进行差错控制和拥塞控制 1 1 , 2 , 3 a , 5 , 6 1 ，本文主要讨论组播的拥塞控制问题。 1 1 组播传输机制概述 1 1 1组播产生的背景 为了缓解网络“瓶颈”问题，业内提出了以下4 种主要解决方案：增加网络带宽； 采用q o s ( t 务质量) 机制，控制不同业务的带宽使用：服务器的分散和集群，以改变 网络流量结构，减轻主干网的瓶颈；i p 组播( i pm u l t i c a s t ) 技术。其中，坤组播技术由 于它所具有的独特优越性在口组播网络中，即使用户数量成倍增加，主干网络 的带宽不需要随之增加，而成为通行的网络技术之一。 图1 1 为有组播和没有组播的情况下的数据传输图，很明显组播大大改善了单播 形式下所造成的大量网络资源浪费的问题。 图1 1u n i c a s t 和m u l t i c a s t 的数据传输图 1 1 2 组播传输机制 组播技术是一种将数据从一个成员发出，然后传输给其它一个或者多个成员的 通信技术。组播传输保证每条链路上只有一条数据流，即使用户数量成倍增加，主 干网络带宽不需要随之增加。 1 1 组播是指一个报文向一个“主机组”的传送，这个包含零个或多个主机的主机 组由一个单独的口地址标识。主机组地址也称为“组播地址”，或者d 类地址。除了 目的地址部分，组播报文与普通报文没有区别。主机组的成员可以动态变化，主机 有权选择加入或者退出某个主机组。 2 1 主机可以加入多个主机组，也可以向自己没有加入的主机组发送数据。主机 组有两种：永久组和临时组。永久组的i p 地址是众所周知的，由i n t e r a c t 管理机构 分配，是保留地址。临时组的地址则使用除永久组地址外的非保留d 类地址。 3 1 组播分组在互联网上的转发由支持组播的路由器来处理。主机发出的m 组播 分组在本子网内被所有主机组成员接收，同时与该子网直接相连的组播路由器会把 组播报文转发到所有包含该主机组成员的网络上。组播报文传递的范围由报文的生 存期值( t mt i m e t o l i v e ) 决定，如果t t l 值等于或者小于设置的路由器端口1 几 门限值( t r l t h r e s h o m ) ，路由器将不再转发该报文。 4 ) 组播报文是通过u d p ( 用户数据报协议) 进行传输的，所以它缺乏t c p ( 传输控 制协议) 所提供的可靠传输的功能。所以组播的引入虽然节约了网络的资源，减少网 络管理的费用，但是组播的拥塞控制问题是所有问题中最重要而又难以解决的也是 最令人关注的问题。 1 1 3组播拥塞控制的研究现状 在计算机网络中，如果某一时刻网络负载超过了可用的资源或者网络出现故障， 那么拥塞就会发生。此时会有数据包丢失，传输延迟增大，网络吞吐量下降等现象。 在组播传输过程中，与传统的口相同，i p 组播不提供速率控制。因此，组播流 可能消耗光所有的网络资源，导致网络拥塞。为组播设计合适的拥塞控制成为迫切 需要解决的问题。i e t f 将组播分成两种模式：一对多，多对多。后者在组播树生成 和组管理等方面存在较大的难度，在i n t e r a c t 上推广的希望不大，所以文本仅讨论一 对多的情况。 直观上，解决网络拥塞应当从两方面入手：一是尽量避免拥塞发生；二是在网 络拥塞发生时采取措施消除拥塞。前者是为了预防，力图使网络维持在最佳状态， 避免拥塞，后者是为了补救，进行拥塞恢复。 2 近年来对组播技术的拥塞控制算法进行大量研究工作m 】，可将其分为端系统上 使用的源算法和在网络设备上使用的链路算法两种：端系统上使用的源算法分为基 于发送方和基于接收方的拥塞控制算法【9 】，而网络设备上的拥塞控制算法又分为路由 器的包调度和主动网络技术等。 基于发送方的方法是指发送方检测接收方的a c k 数，若此数小于阀值，则认为 有包丢失需重发数据包。基于接收方的方法是指由接收方检测数据包的丢失，并向 发送方发送请求重发的数据包，此类数据包标记为“n a k ”。前者，若所有的接收者 同时发送a c k s ，则会使发送方处于a c k 的内爆中，导致阻塞和延迟；后者，当大 多数接收者没有收到数据时，它们可能同时发送n a k , 希望发送方能重发此消息，从 而使发送方和网络处于n a k 的内瀑中，导致拥塞和延迟。通过对上面两种方法的分 析，可以发现基于接收方的比基于发送方的方法具有更好的伸缩性。故般采用基 于接收方的方法，但由此导致n a k 内爆。 对于视频流，速率控制【1 0 】是其重要的一个方面。速率控制的目的是基于预测的 网络带宽决定发送速率。有两种基本的速率控制手段，基于发送方的速率控制和基 于接受方的速率控制。基于发送方的组播速率控制算法，由发送方根据接收方反馈 的信息来调整其发送数据的速率，对每个发出去的数据包发送方维持一个定时器， 当定时器超时，还没有收到接收者的反馈信息，发送方就重发此数据。前者主要基 于反馈信息进行速率调节。可以适用于单播的方式或组播的方式。对于单播的方式， 有两种速率控制方法，基于探测的方法( p r o b e - b a s e d ) 和基于模型的方法 ( m o d e l - b a s e d ) 。基于探测的方法通过不断调整速率使得包的丢失率低于一个固定的 概率值。基于模型的方法直接利用t c p 的吞吐率模型计算速率。因此，模型法也被 称为t c p 友好的速率控制方法。 在发送方的速率调整方面，由于它一般根据接收者反馈的信息进行调整，组播 成员的增加可能导致网络反馈信息的急剧增加，而淹没发送方。如何有效的控制反 馈信息成为组播能否得到广泛应用的关键问题。 1 2 主动网络技术 主动网络( a c t i v en e t w o r k s ) 6 , 1 1 l 概念的提出主要针对当时网络发展过程中遇到 的几个问题：即，把新的技术和标准引入现有网络中的困难：由于几个网络协议层 的冗余操作而使网络性能下降；在已存在的结构模块中加入新服务困难。主动网络 方案使网络节点不仅能够转发报文而且可以通过执行附加程序来对报文进行处理。 整个网络上的节点也都是可以编程的，可以执行用户定义的报文处理程序。 3 主动网络是相对于现有的网络比较而言的。现有的网络由于不对报文进行处理 或计算，因此可以称之为被动网络( p a s s i v en e t w o r k s ) 。虽然现有的网络中路由器和 交换机也可以改变报文的报头，但它们对真正的用户数据却不做任何处理，原封不 动地转发用户数据是它们的宗旨。即使对报头的改变和相关路由处理也是独立于用 户处理和产生这些报文的组播应用。相比之下，在主动网络中的路由器和交换机可 以对网络报文进行用户自定义的计算。 现有很多的算法把主动网络技术应用到组播算法中，如文献m 2 】中使用主动网络 的思想来解决组播通信的问题，它在端到端的基础上引入主动网络节点。 1 3 路由器上的队列管理算法 随着网络规模越来越庞大，结构日趋复杂，仅仅依靠端到端的拥塞控制是不够 的，网络设备也必须参与资源的控制工作。网络设备拥塞控制策略是指在路由器中 采用包调度算法和缓存管理技术。目前的研究主要集中在“主动队列管理” a q m ( a c t i v eq u e u em a n a g e m e n t ) ，a q m 与传统的“队尾丢弃”( d r o p t a i l ) 算法不同 之处在于，a q m 在网络设备的缓冲溢出之前就丢弃或者标记报文1 1 3 1 ，并把早期拥 塞出现通知发送方，这样发送方可以在队列溢出之前调整数据的传输速度，避免更 严重的拥塞状况的发生，以降低丢包率。 随机早期检测r e d ( r a n d o m e a r l yd e t e c t i o n ) f 1 4 】就是一种主动的队列管理技术， 它根据一定的概率判断拥塞的出现，对到达的包进行标记或者丢弃作为拥塞指示通 知发送方，丢包或标记的概率依据平均的队列长度。 其它的一些a q m 算法包括a r e d l l 5 】、s p e d l l 6 】、b l u e1 1 7 等，它们的主要思 想是根据网络中负载的情况对标记丢失概率进行调整；而r e m ( r a n d o me a r l v m a r k i n g ) i t s 】、p i 【1 9 】、a v q ( a d a p t i v ev i r t u a lq u e u e ) 2 0 1 等，它们的基本思想都是在 a q m 中使用p i 控制器【2 l 】。 1 4n s 网络模拟器 在计算机领域提出一种新的协议和算法后，要对其进行性能进行测试和评价存 在有以下三种方法： 1 利用数学方法建立数学模型，然后进行数学论证得到理论分析结果。 2 搭建实地环境，在实际的网络环境下进行测试，用得到的实际数据来分析协 议的性能。 4 3 利用软件方法自编程序或借助一些已有的模拟器来模拟实现新方案，再将模 拟的结果进行分析得到性能参数。 本文中主要用到第一种和第三种方法，对能够以数学模型进行分析的，可以得 到其结果，并且由此评价其性能，但是本文有些算法是很难用一条数学公式和方程 能表示的，而且在现有的网络，和搭建实际的环境都是不太可能事情。所以，利用 u s c f l s i ，x e r o x ，p a r c ，l b n l 和u c b e r k e l e y 等联合研究开发的网络模拟器n s 2 ” 进行仿真模拟。n s 是一种支持多协议的模拟器，很多的研究多是建立在此模拟器的 基础之上的。 1 4 1 n s 的结构 n s 是一个面向对象的仿真器，由编译和解释两个层次组成，编译层次包括c + + 类库，而解释层包括对应的o t c l 类，用户以o t c l 解释器作为前台使用n s 。n s 内部 大部分是t c l o b j e c t 的子类，用户在解释器环境创建新仿真对象，然后镜像到对应的 编译层次。这样，在不影响效率的前提下，通过o t c l 解释器来使用n s 提供极大的 灵活性和方便性。 图2 2 n s 的部分类图 图2 2 是n s 中的部分类酬捌，t c l 类包含了用c + + 代码访问解释程序的方法。 t c l o b j e c t 类是为反映在经过编译的分层中仿真器对象服务的基本类。t c l c l a s s 类定义 了经过解释的类分层和用户用来例示t e l o b j e c t s 的方法。t c l c o m m a n d 类用来定义解 释程序简单的全局命令。e m b e d d e d 类包括了装入更高层内置命令的方法，这些命令 使得配置仿真变得更加容易。最后是i n s t v a r 类包含了访问像o t c l 实例变量一样的 c + + 成员变量方法。基类c o n n e c t o r 派生出很多的子类，s n o o p q u e u e 用来监视队列的 到达，发出，丢弃和统计数据及平均值：q u e u e 中包含各种队列调度算法：在d e l a y 设置队列的延时；在a g e n t 中生成各种代理，来实现相应的协议或者其它模型的仿真， 如t c p 代理，和在t c p 基础之上的各种代理，如：t c p r e n o 、t c p n e w r e n o 、 t c p v e g a s 、t c p s a c k l 等；t r a c e 中用来跟踪各种仿真数据，记录单个包在队列或链 路的到达f e n q ) 、离开( d e q ) 、丢弃( d r o p ) 。 1 4 2n s 模拟方法 n s 歧持单播和组播的传输模式，支持t c p 、s r m 、r t p 、u d p 等传输协议，支 持d r o p t m l ，r e d ，r i o ，f q ，p i 等队列管理模式，用户可以在任意层扩展自己的功能 和编制新的协议。而且可以编写各种t c l 脚本来对各种协议和算法进行仿真和模拟， 可以对协议的一些变量进行跟踪，对队列和流进行跟踪和监视。而且由于n a m 是一 个基于动画工具的t c l 工具包，用它来将n s 仿真过程和实际网络数据包跟踪数据的 可视化。使用n a m 的第一步是产生一个n a m 跟踪文件。动态跟踪文件应包括拓扑信 息如结点、链路、队列、链接结点等也包括数据包跟踪信息。 运行仿真之前，首先要分析涉及仿真的那一个层次。一个是基于o t c l 编程的配 置、构造层次，利用n s 已有的网络仿真元素实现仿真，无需对n s 本身进行修改， 只要编写o t c l 仿真脚本。另外一个层次是c + + 和o t c l 编程的编译、配置层次，如果 n s 中没有所需的仿真元素，n s 提供让用户自己建立新的协议和修改协议的技术， 其实现的步骤为设计协议细节实现，把新的协议代码生成新的n s ，生产t c l 的脚本 来运行n s 仿真，对运行的结果实现分析和评价。 o t d 脚本的实现过程： 1 生成仿真器并建立网络拓扑结构，并且根据需要确定基本的链路特点，如延 时，带宽和队列参数等。 2 建立协议代理，包括端节点的协议绑定和通信量模型的建立。 3 对节点的参数进行配置，根据仿真的具体要求对节点进行代理，路由协议等 的初始化。 4 建立跟踪或者监视模型，把仿真的结果输出并存到指定的文件之中，然后编 写a w k 代码，用来得到需要的数据。 5 建立可视化的观察工具，如x g r a p h 、n a m 对仿真的过程和结果进行观察和 分析。 6 6 设置仿真时间，运行仿真，处理仿真结果。 1 4 3n s 的特点 n s 作为一种具有强大功能的网络仿真工具，和现存的多种仿真工具相比较，它 具有以下特点： 1 灵活性( f l e x i b l e ) ：可控制性就是说可以忽略实现细节部分，而只对要进行 研究的那一部分进行模拟。这样缩短掌握n s 仿真器的周期，节约时间。 2 仿真性( e m u l a t i o n ) ：n s 模拟器不仅能够实现对网络中协议等的模拟，还有 与现实网络进行连接的仿真接口，可与现实的网络进行接口，在二者之间进 行数据的传送和处理。 3 可视性( v i s u a l i z a t i o n ) ：n s 中有一个称为n a m 的组件，把拓扑结构的变化， 路由路线的变化，传送速率的变化，数据丢失等情况都可表现出来；n s 中 的x g r a p h 组件还可以将模拟结果以曲线图的方式表现出来；当然还可以在 c + + 中把一些重要参数p r i n t f 出来。 4 可扩展性( e x t e n s i b i l i t y ) ：n s 基于事件驱动模型，支持协议广泛，采用开放 的体系结构，用户很容易根据自己的需要开发新的协议。 5 可重现性( r e c u r r i n g ) ：和现实的网络环境不同，仿真环境是人为搭建的， 参数都是根据需要设置的，所以它具有可重现的特点。 1 5 本文所做的工作 本文的研究重点在组播的拥塞控制，主要工作归纳如下： 1 分析了组播传输机制中的主要问题，提出组播拥塞控制的几个研究难点，为 本文的研究工作奠定基础。 2 比较系统全面的掌握了n s 网络模拟器的使用，通过修改或者添加n s 的协 议模块，来实现一种新的算法，并通过编写t c l 脚步语言来模拟其性能的 实现。 3 对现有的各种队列管理算法进行了分析和讨论，在此基础上提出了新的算 法，该算法根据平均队列长度和数据包到达队列的速度来调整丢包率，能对 网络拥塞状态进行快速响应。 4 利用主动网络技术，提出一种由主动路由器参与拥塞控制的机制。由主动路 由器来进行反馈包的汇聚和丢包的局部恢复，来解决反馈爆炸问题，并把它 应用于可靠组播中。 7 5 从现有的t c p 友好的组播拥塞控制的基础上，考虑到传送实时的流媒体所 需考虑的链路振荡问题，提出改进的算法，平滑了其速率调整的步长，该算 法能较好的解决链路的振荡问题和满足协议的公平性。 本文包含以下五个个章节：第一章引言主要讨论了组播产生的背景、组播拥 塞控制的现状、主动网络技术和主动队列管理技术、网络模拟器n s 的介绍以及本文 所做的主要工作：第二章组播拥塞控制的研究提出需解决的三个关键问题：对网 络拥塞的快速响应、反馈爆炸和协议公平性；第三章基于包到达速率的主动队列管 理算法分析了现有的主要队列管理算法并模拟了其在各种条件下的性能，并提出一 种新的主动队列管理算法并分析了它的性能；第四章组播传输中反馈抑制研究基 于现有组播协议的反馈抑制问题，提出一种结合路由器进行反馈抑制的算法：第五 章t c p 友好的组播拥塞控制研究主要讨论了t f m c c 的协议性能及其在传输多媒 体数据时的缺点，提出一种改进的算法；第六章结论和将来的工作主要总结了本 文所做的工作和提出了继续研究的方向。 8 第二章组播拥塞控制的研究 本章所做的主要工作为，对组播应用中的关键技术进行了分析，确认了组播拥 塞控制中的核心问题：怎么样才能及时发现和避免拥塞；由于速率控制机制或可靠 组播中差错控制机制引起的反馈风暴问题；协议的公平性问题。并且对已有的经典 协议进行了分析，为本文后面的研究奠定了基础。 2 1 引言 现代生活中，人们都会经历交通阻塞的情况，当在十字路口等待绿灯的汽车排 成了长龙，那就是拥塞。同样的道理，对计算机网络来说。当用户提供的负荷超过 了网络的设计限制，即人们对资源的需求超过了可用的资源时，拥塞就会发生。近 年来，随着网络技术的发展，在i n t e r n e t 上产生了许多新的应用，其中不少是高带宽 的多媒体应用，譬如网络视频会议、网络音频，视频广播、多媒体远程教育、远程会 诊。而传统网络最初是为数据可靠传输而设计的，是典型的点对点通信模式，所用 的传输协议多为点到点的协议。其所具有的特点将增加网络负载，带来网络延时。 这就造成带宽的急剧消耗和网络拥挤问题，讲组插和拥塞控制是优化带宽的重要通 信手段。 组播技术是将数据同时传送给多个接收者的一种有效方法，它能大大提高网络 带宽的利用率，被广泛应用于包含多个用户的多媒体系统中，由于多媒体数据传输 实时性的要求，底层支持协议采用不提供任何拥塞控制机制的u d p 协议，当大量的 多媒体数据在网络中以组插的方式传输时，网络上其它具有拥塞机制的数据流，如 t c p 数据流，会根据网络的拥塞情况自动减小其发送速率，而基于u d p 协议的数据 流并不根据网络的拥塞情况而调整其相应的发送速率，导致u d p 数据流挤占t c p 等 具有拥塞控制机制的数据流的带宽。为了保证网络的效率，各个数据流之间应该友 好共享带宽，所以要在组插技术中提供拥塞控制机制。 由于组播的接收者数目大，且对各种数据的要求也存在差异，所以组播拥塞控 制研究比u n i c a s t 下拥塞控制难得多。本章分析了组播拥塞控制机制，并总结出来几 个应该解决关键问题。 2 2i p 组播及拥塞控制技术 文献【2 3 1 中使用图2 1 来描述拥塞，网络负载较小时，吞吐量与网络负载基本保持 9 线性关系，网络延迟缓慢增加，网络负载超过第一个关键点k n e e 后，网络吞吐量增 长变慢，网络延迟增长变快，网络负载超过第二个c l i f f 后，网络的吞吐量急剧下降， 网络延迟迅速增加，拥塞控制的目标就是使网络在关键点k n e e 附近工作。 图2 1 拥塞发生时的吞吐量和响应图 在拥塞控制这个过程中，我们首先要知道网络拥塞一般发生在哪里? 网络发生 拥塞时会出现什么现象? 网络拥塞主要发生在包交换机或者路由器，每个包交换机 或者路由器都有输入和输出缓冲，若包到达路由器的速率接近或者超过包处理和转 发速率，包就会在缓冲处堆积而排起队来。这时包会经历很大的时延，包交换机或 者路由器出现队列就是出现拥塞。拥塞现象就是包的时延变得很大，特别当队列溢 出，即无缓冲区可用时，必须丢弃包，对于有差错控制的可靠传输来说，丢弃就会 引起超时重发，重发可使拥塞加剧，于是，可能导致网络吞吐量突然下降，从而形 成拥塞崩溃。 另外，拥塞控制需要保证流量之间的公平性，公平性问题与拥塞密切相关，在 低负载情况下，每个用户对资源的请求都能得到满足，这时不需要考虑资源的分配 公平性问题，当资源紧缺，网络拥塞时，公平性才成为需要考虑的问题。因为目前 网络中的主要传送使用8 0 的t c p 作为其可靠传输协议，如果设计出来的组播协议 不具有t c p 友好性的话，可能导致它们不能共享网络带宽，而使t c p 流饿死，最终 导致整个网络崩溃。所以本文讨论组播拥塞控制中的几个重点问题：对拥塞的快速 响应问题、反馈爆炸问题，协议的公平性问题。 2 2 1 对拥塞的快速响应 当网络发生拥塞的时候，我们希望发送方尽快知道拥塞的出现，并采取一定的 措施来避免或者减轻网络拥塞的状况。发送方一般是根据丢包来确认网络是否出现 了拥塞，但是如何及时的发现拥塞和怎样进行拥塞避免，却是一个值得研究的问题。 1 0 虽然在发送端可以进行拥塞的检测和回避，但最有效的拥塞检测和回避是在路 由器中实现的，这是因为只有路由器才能准确根据分组到达的速率和路由器中队列 的长度来决定网络的拥塞状况。 2 2 2 反馈爆炸问题 反馈爆炸【2 4 2 5 】( f e e d b a c k i m p l o s i o n ) 指的是在组播通信中，由于所有的接收者 ( r e c e i v e r ) 同时向发送者( s e n d e r ) 发送反馈信息，这对具有大规模接收群的组播 应用来说会给发送者造成严重的危害，并且带来重传报文数量的上升，影响协议的 可扩展性。 始数据流 馈信息流 图2 2 组播的反馈示意图 为了解决反馈爆炸问题，人们主要提出了以下几种方案：延时反馈，轮询法， 基于概率的方法和基于代表的方法。这些方案虽然在一定程度上能减少反馈报文的 数目，但并没有从根本上解决协议的可扩展性问题，除此以外，基于发送方的拥塞 控制也将所有接收者组成一个环或者树结构，并在中间选定接收代表，来收集反馈 信息以达到反馈抑制的目的。 2 2 3 协议的公平性 公平性【冽是组播拥塞控制机制能否得到广泛应用的基础，也是每个组播拥塞控 制算法所追求的设计目标之一。组播拥塞控制的公平性主要体现在以下两个方面。 一是协议问的公平性( i n t e r - p r o t o c o lf a i r n e s s ) ，主要是指组播数据传输时与t c p 流共 享瓶颈链路时，能公平占用网络带宽，即组播流是t c p 友好的( t c p f r i e n d l y ) 。另 外一个方面就是组播传输时的协议内部公平性( i n t r a - p r o t o c o lf a i r n e s s ) 。i n t e r n e t 之 所以能够稳定健康地运行，很大一部分是由于t c p 拥塞控制根据网络的状态调整其 发送速率，满足协议间和协议内部的公平性。而组播传输机制是一种尽力而为的服 务，它不满足t c p 友好性，导致它与t c p 流在共享带宽时的不公平性，而使t c p 流饿死，最终导致网络崩溃。 所以组播拥塞控制般采用类t c p 2 7 的响应机制来提供协议的公平性，目前主 要有基于速率和基于窗口的速率调整方法，为了实现与t c p 公平共享网络带宽，基 于速率的组播拥塞控制调节算法一般采用稳当状态下t c p 速率响应函数作为其响应 函数，公式( 2 1 ) 和( 2 2 ) 分别为t c p 友好的流量通信模型，式( 2 2 ) 能更好的适应网络 环境和流量特性。 口( s , t r t t ) 2 。t 。 ( 2 1 ) 盹钿卜习季习s 孺而面 亿2 ) 基于窗口的速率控锖4 算法采用类t c p 速率调节算法，即在发送方保证未被所有 接收者确认的报文个数小于窗口大小。 2 3 已有的算法及其存在的问题 当网络发生拥塞时。我们希望数据发送源能够快速对网络状态做出反应，目前 除了由接收方根据接收方的反馈信息来进行判断外，就是由主干网路由器来对拥塞 状况的进行判断，以来及早的通知发送方调整发送速率，以减轻网络的拥塞状况。 随机早期检测r e d e c n ( r a n d o m e a r l yd e t e c t i o n ) 是目前常使用的一种p 拥塞控制 算法。它根据一定的丢包概率丢弃进入网络的数据包，并且避免了属于同一连接的 连续数据包，从而提高连接的吞吐量。但是因为它根据瓶颈队列长度指示拥塞，对 网络的状态变化不具备适应能力，当连接的数目增加时，它可能达到满队列的状态。 在规模比较大的组播应用里，组播的反馈抑制通常主要采用两种方法：随机延 时方案( r a n d o m i z 甜b a c k o f fs c h e m e s ) 和分层方案( h i e r a r c h i c a ls c h e m e s ) 。下面讨 论者两类可靠性的实现对可扩展性能的影响。 对于随机延时方案，如s r m l l j 中采用的反馈抑制方法，它能够较好的抑制反馈 包的数目，但是由于它是在拥塞发生后等待一段时间来反馈信息，所以它不能及时 的把反馈信息报告给发送源，所以也不能及时的对网络的拥塞进行响应。 对于分层方案，其中经典的算法有r m t p 2 ，它由指定的接收代表( 父节点) 来 对它的下游节点( 子节点) 的反馈信息进行汇聚，以此来减少反馈信息，但是其中 存在的一个问题就是当接收代表( 父节点) 选择不当，有可能使接收代表被淹没， 而且这种算法由于它需要事先选定接收代表，所以实现起来开销比较大。 i e t f 制定的t f m c c 协议在r f c 3 0 4 8 中定义，它是把t f r c l 2 9 1 拥塞控制思想 用于组播通信。其基本的实现就是由接收方负责所有的参数测量，包括丢失事件率 和到发送方的往返时间r 1 广r ，并利用测量的结果根据p a d h y e 等人提出的方程( 如式 2 2 ) 来计算出的期望传输速率，将其反馈给发送方。发送方只需要根据接收方的反 馈信息来调整速率，而不需要了解具体的模型参数。发送方根据接收方反馈的信息 来确定接收代表c l r ( c u r r e n tl i m i t i n gr e c e i v e r ) ，往往接收代表是反馈发送速率最小 的节点。为了减少不必要的反馈信息，发送方把当前的最小速率和c l r 的m 号在 数据包中捎带过去，接收方不会发送反馈信息除非它计算出来的速率值小于当前的 速率；并且接收方中设置定时器来延迟反馈，调整反馈定时器，使之有利于速率低 的接收者，来达到反馈抑制的目的。 但是它存在的问题就是当接收方估算出的丢失率为0 的情况下，它就以当前速率 的两倍来调整发送速率。当目标速率低于当前速率时，发送方直接将速率降为目标 速率，这样速率的变化可能会比较大。 2 4 解决问题的思路 由于r e d 的设计目标不是在任何条件下都能达到的，在拥塞十分严重的条件下， 平均队列长度并没有正确的指示拥塞。r e d 能够达到的理想运行状态当且仅当是正 确的配置并拥有足够的缓存。所以本文如果能够在算法中能根据数据包的到达速率 来进行丢包和标记的话，那么主动队列管理技术就能更好的，更及时的发现拥塞， 达到拥塞避免的目的。 由前面的分析可以知道，单纯的延时法和单纯的分层方法都不是能很好的解决 反馈的爆炸问题，所以本文考虑把两种思想结合起来，就是在接收方设定延时器来 进行反馈抑制，在中间节点对反馈的信息进行汇聚，从而来解决反馈爆炸问题。 在2 3 节中我们分析了t c p 友好的组播协议，它能够满足t c p 友好性，但是在 传输实时的多媒体信息流时，却存在一些问题，所以本文打算平滑速率的调整步长 来更好的满足协议的公平性和传输多媒体信息的需要。 2 5 小结 组播是一种非常有效的数据分发机制，但是在实际的推广时遇到了两大难点： 拥塞控制和数据恢复，本章分析了组播拥塞控制中存在的难点及基本的问题，然后 从讨论几种经典的算法及其存在的问题，所以，本文认为组播拥塞控制中有以下几 个问题亟待解决：对拥塞控制的响应速度，协议的公平性问题，反馈爆炸问题。 1 4 第三章基于包到达速率的主动队列管理算法 本章通过理论分析和实验性能评价，分析和评价了现存的多种主动队列管理技术 及其存在的优缺点，并在此基础上提出了一种新的主动队列管理技术。它在队列长 度超过参考值时根据队列的到达速率进行标记或者丢包，从而使发送方能更好的了 解网络的拥塞状况，它比r e d 算法具有更高的稳定性，并对网络状态的变化具有很 好的适应能力。 3 1 引言 主动队列管理技术它作为一种新兴的i p 层拥塞控制策略，对于提高i n t e m e t 的服 务质量起到关键的作用。随着i n t e m e t 的发展，网上业务变得日益繁忙，通信量的迅 猛增长使得主干网拥塞日益趋于严重，网络已经成为一个亟待解决的问题，为了解 决这些问题，主干网路由器就必须采取一定的策略来避免和控制网络拥塞。当网络 发生拥塞时，比较容易想到的方法是设置一个大容量的缓冲区，把所有新到达又来 不及处理的分组都保存在缓冲区中，当系统空闲时再处理这些保存起来的分组。然 而实际上缓冲区的容量总是有限的，当网络持续拥塞时，缓冲区总会填满。缓冲区 填满后，新的分组到达时就只能丢弃，称之为队尾丢弃，但它会导致全局同步问题【1 4 1 ( g l o b a ls y n c h r o n i z a t i o n ) 。i e t f 提出的随机早期探测r e d e c n 1 3 】算法，它根据路 由器中队列的长度调整数据包的丢弃( d r o p p i n g ) 或标记( m a r k i n g ) 概率，从而对 网络状态的变化具备适应能力。但该算法对参数的设置十分敏感，而且随着网络中 流的增加，平均队列长度会随之增加。 本章在r e d 的基础上，综合考虑到队列长度和数据包的到达速率来调整数据包 的丢弃或者标记概率，该算法可以根据网络的实际的状况来调节参数，使路由器中 的队列长度在不同的网络状况下都能稳定在参考值附近，通过n s 2 网络模拟平台上 进行实验分析和评价其性能优于r e d 。 3 2 现有的工作描述 随机早期检测r e d e c n 算法【1 4 州是一种防止网络拥塞的主动队列管理机制，对 每一个队列设置两个门限 m i n ，m 。和一个分组丢弃概率p m 。在每个路由器记 录数据包的排队长度，在缓存占满之前，即当平均队列长度超过t h m i 。就按一定的概 率p 。“丢弃进入路由器的数据包或者使用e c 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 ) 通知 数据源，这样就可以及早使发送方减少拥塞窗口，以减少进入网络的数据流量。r e d 对于t c p 和类t c p 的流来说就可以避免丢弃属于同一连接的连续数据包。从而避免 多个数据流同步，提高网络连接的吞吐量。r e d 算法主要分为以下两个部分： 1 )