（运筹学与控制论专业论文）internet网络拥塞控制研究.pdf

鲁东大学硕士学位论文 摘要 随着互联网规模的增长，拥塞已经成为一个十分重要的问题。i n t e r n e t 主要依赖于 t c p 端到端拥塞控制来避免网络拥塞，但它在很多方面已经不能满足复杂网络中各种应 用的需求。在路由器中引入适当的队列管理机制，可有效地对网络进行监测和预防，但 现有算法在响应速度、稳定性及环境敏感性等方面仍有缺陷。 本文从端系统和路由器两个层次详细研究了当前i p 网络中的拥塞控制策略，针对 i p 网络实际应用需求展丌了系统深入的研究。本文研究的主要内容及创新点如下： 1 ) 针对i n t e r n e t 网络中一些现有算法在具有传输延时以及由于用户数的动态和网 络时延变化而引起的高频扰动和测量误差因素的情况下，算法稳定性急剧下降或产生振 荡的缺点，设计了一种预测拥塞控制算法，使网络传输中由时变延迟和量化引起的不可 测扰动极小化。 2 ) 采用预测控制的方法来调节p i d 控制器的参数。利用预测控制方法求得控制增 量，然后对控制增量进行前向加权求得即时控制率，然后根据求得的控制率设计p i d 控 制器的参数。仿真试验表明，设计的控制器提高了网络性能。 3 ) 采用了神经网络的预测方法。我们利用相邻两个时刻的队列长度差值和的变化 趋势来预测下一时刻队列长度差值，从而得到下时刻队列长度的预测值。根据下一时 刻队列长度的预测值与期望值之差来设计控制增益，使网络能及时对流量的变化做出反 应，以防j 卜拥塞的发生。该方法可以使路由器中队列长度值稳定在一个期望值附近。 4 ) 利用模糊预测的方法来研究网络拥塞的问题，利用网络在过去两个时刻队列长 度的变化值来预洲下一个时刻的队列长度。这种采用相邻两个时刻队列长度变化值来预 测下一时刻队列长度的方法能更精确的反映山队列的变化趋势。从而对队列长度的变化 及时做h 反应，使缓冲区中队列长度值稳定在期望值附近。仿真结果证明了算法的有效 性。 关键词：棚摩托嘴4 ；主z j s l ；x y q 管理；预测 ：= f 批模糊控制：神经网络 鲁东大学硕士学位论文 a b s t r a c t n e t w o r kc o n g e s t i o nh a sb e c o m ea ni m p o r t a n ti s s u ew i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e t i n t e m e tp r i m a r i l yr e l i e so nt c pe n d t o e n dc o n g e s t i o nc o n t r o lt oa v o i dn e t w o r kc o n g e s t i o nb u tt c p s t r a t e g i e sc o u l d n tm e e tm a n yv a r i o u sd e m a n d so fe v e r ya p p l i c a t i o no nt h ec o m p l e xn e t w o r k i nf a c t ，i t w i l lb em o r ee f f e c t i v ef o rd e t e c t i n ga n dp r e v e n t i n gc o n g e s t i o ni ft h er o u t e r sp e r f o r mq u e u em a n a g e m e n t s c h e m e sb u tt h ec u r r e n ta l g o r i t h m sa r es t i l ln o tp e r f e c ti nt e r m so fr e s p o n s et i m e ，s t a b i l i t ya n ds e n s i t i v i t y t ot h ee n v i r o n m e n t c o n g e s t i o nc o n t r o ls t r a t e g i e sf o ri pb a s e dn e t w o r k sa r ei n t r o d u c e di nd e t a i lf r o mt w od i f f e r e n tl a y e r s o fr o u t e r sa n de n dh o s t s y s t e m a t i cr e s e a r c ht om e e tp r a c t i c a lr e q u i r e m e n t so fi pb a s e dn e t w o r k si s p e r f o r m e di nd e p t h t h ep r i m a r yw o r k sa n di n n o v a t i o n so f t h i sp a p e ri n c l u d eb u tn o tl i m i t e dt o ： 1 ) d u et ot i m e - v a r y i n gc h a r a c t e r i s t i c so ft r a n s m i s s i o nd e l a y , ap r e d i c t i v ec o n g e s t i o na l g o r i t h mb a s e d o ns t a t es p a c em o d e li sp r o p o s e d ，w h i c he n h a n c et h er o b u s t n e s so ft h ec l o s e dl o o ps y s t e m s t h ed e t a i l s t a t e m e n to ft h i s a l g o r i t h mi sg i v e n t h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o di sd e m o n s t r a t e db y s , i m u l a t i o nr e s u l t s 2 ) w eu s eg e n e r a l i z e dp r e d i c t i v ec o n t r o lt op r o p o s eap r e d i c t i v ep 1 dc o n t r o l l e rf o ra q mr o u t e r a s y s t e m a t i cm e t h o di ns e l e c t i n gag r o u po fp a r a m e t e r sf o rt h ec o n t r o l l e rt og u a r a n t e et h es t a b i l i z a t i o ni s g i v e n t h es i m u l a t i o ns h o w st h a tt h en e t w o r kh a sb e t t e rd y n a m i cp e r f o r m a n c ea n dg u a r a n t e e st h eq u a l i t yo f s e r v i c e 3 ) d i s c u s s i n gt h ec o n t r o lq u e s t i o no f t h ec o n g e s t i o nc o n t r o li ni n t e r n e tn e t w o r k s ap r e d i c t i v ec o n t r o l a l g o r i t h mi sp r o p o s e dt os o l v et h ep r o b l e mn s i n gt h en e u r a ln e t w o r k s t h i sm e t h o dc a ns t a b i l i z et i l eq u e u e l e n g t hn e a rt h ee x p e c t e dv a l u e t h er e s u l t so ft h es i m u l a t i o nd e m o n s t r a t et h a tt h i sa l g o r i t h mc a ne n s u r et h e s t a b l et r a n s m i s s i o no ft h en e t w o r k 4 ) d i s c u s s i n gt h ec o n t r o lq u e s t i o no ft h en e t w o r kc o n g e s t i o nb a s e do nf l l z z yp r e d i c t i v et h ep r o p o s e d m e t h o dp r e s e n t sn l o r ea c c u r a t ee s t i m a l e dm e a s n r eo f t h eq n e n el e n g t hu s i n gt h er a l co fc h a n g eo ft h et r a m c l o a di nt w or e c e n tt i m es l o t st h ec o n t r o l l e rc a ne n s u r et h es t a b l et r a n s m i s s i o no ft i l en e t w o r ki n f o n l l a t i o n a v a i l a b l y t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o d sa r ee f f e c t i v e k e y w o r d s ：c o n g e s t i o nc o n t r o l ；a q m ( a c t i v eq u e u em a n a g e m e n t ) ；p r e d i c t i v ec o n t r o l ；f u z z y c o n t r o kn e u r a ln e t w o r k 鲁东大学位论文原创性声明和使用授权说明 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成 果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律后果由本人承担。 名：磊铷叫眺“多舻日 尸 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权烟 台师范学院可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密口。 ( 请在以上相应方框内打“”) 作行签名：勺知 剥f 签名：- 孽圣钠：。 印饶 同期：一年) 月t r 1 日期：加。6 年6 ，月夕p 1 鲁东大学硕士学位论文 第一章绪论 i n t e r n e t 在过去几十年里按指数方式进行增长。现在i n t e r n e t 已经成为最重要的信息 交流手段。人们利用i n t e m e t 接受教育、娱乐、处理个人财务、购物等。i n t e m e t 变得越 来越重要，人们对i n t e r n e t 的要求也越来越高。用户需要更宽的带宽，更好的服务质量， 更高的安全性。 随着新型网络应用的不断涌现和用户数量的迅速增长，使得i n t e r n e t 的流量急剧增 长，其中除了传统的w w w 、f t p 、t e l n e t 等数据流外，还出现了大量的实时多媒体流， 由于网络中不同的数据流在路由器中交汇，因而给网络的路由节点造成很大负担，越来 越严重的网络拥塞问题逐渐暴露出来。网络拥塞问题是i n t e r n e t 网络发展中亟待解决的 问题。 1 1 网络拥塞和拥塞控制 当通信子网中存在过多的报文时，网络性能就会下降，这种现象称为捌塞 叭2 1 ( c o n g e s t i o n ) 。在矧络发生拥塞时，会导致端到端时延( d e l a y ) 的急剧增加，并造成大量 的分组丢失( p a c k e tl o s s ) ，使吞吐量下降，严重时会发生“j 抖j 塞崩溃”( c o n g e s t i o nc o l l a p s e ) 现象13 1 。图1 1 描述了网络负载与吞吐量、响应时间及网络性能的关系。当网络负载较 小时，吞吐量基本上随着负载的增长而增长，呈线性关系，响应时问增长缓慢。当负载 达到蚓络容量时，吞吐量呈现出缓慢增长，而响应时问急剧增加，这一点称为k n e e 。 如果负载继续增加，路山器丌始丢包，当负载超过一定量时，吞吐量开始急剧下降，这 一点称为c l i f f 。通常将k n e e 点附近称为捌塞避免区问。k n c e 和c l i f f 之叫是拥摩恢复 区i l l 。c l i f f 之外是捌塞崩溃区间。为了最大限度的利用资源，网络工作在轻度j 7 j 塞状态 时澎喙足较为理想的，但这也增加了滑i h l - j t l 塞崩溃的可能性。因此，需要一定的拥塞控 制机制束加以约束平限制。 洲塞控制就是刚络节点采取措施来避免拥塞的发生或者对捌塞的发生做出反应。它 实际卜包禽捌塞避免( c o n g e s t i o na v o i d a n c e ) ： t l 捌塞控f i l l ( c o n g e s t i o nc o n t r 0 1 ) 两种不同的机 制14 i 。 t t l 摩避免是预防策略，它的目的是使网络运行在k n e e 附近，避免网络捌塞的发 生，使网络在高吞吐量低延迟的状态；拥塞控制是恢复策略，它用于把网络从拥塞状态 中恢复出来，使得网络运行在c l i f f 的左侧区域，进入j 下常的运行状态。- 7 1 理想的拥 鲁东大学硕士学位论文 塞控制算法应尽可能具有以下特点：一是高效性，在满足控制目标前提下，尽可能充分 利用网络资源；第二是很好的扩展性，当网络连接数增多时，算法开销不会成为影响网 络性能的一个主要因素；第三应具有公平性，防止一些网络过度占用网络资源而导致另 一些网络连接不能公平使用网络资源；最后，应具有稳定性，当网络带宽基本不变时 使各网络连接发送速率快速收敛于稳态。 吞 吐 姑 ( a ) 网络负载 网 络 性 能 响 应 时 间 - k e ec l l f f 、 负载 网络负载 ( b ) ( c ) 圈1 1 网络负载与吞吐量、响应时间及网络性能的关系 1 2 拥塞控制的研究意义 在刚刚过去的几年中，自棚j 1 多的研究都试吲扩展i n t e r n e t 的体系结构，为了即将 火量 n 玑的实时多媒体应用提供服务质量( q o s ) 保证，有关q o s 的研究引起了不少争议， 一些基于网络一 ，问节点上单个流状态的业务模型通常具有较复杂的实现机制，可扩展性 足该类业务模型存在的严重问题；另外一些研究认为在具有充足资源的尽力传输( b e s t e f l b r t ) 厩 络中，所有的问题都会迎刃而解，这种观点难以令人置信。多数人认为更多更 鲁东大学硕士学位论文 合理的控制机制刈已有删络的稳定运行无疑将是至关重要的。其中一个最基本和最重要 的要求就是防i f ：网络出现拥塞崩溃，使网络运行在轻度拥塞的最佳状态，同时保证一定 的公平性；在现有的网络体系结构中采用恰当的控制机制也是可能引入一定的区分业务 级等级，这种思路强调已取得较大成功的i n t e r n e t 固有的本质属性和最初的设计原则， 而不是一味地放大现有体系结构中存在的不足与缺陷，这应该是一种较为合理的工程技 术途径。 最初设计的i n t e r n e t 是非面向连接的分组交换网络，所有的业务分组被不加区分的 在网络中传输，网络能给出的唯一承诺就是尽自己最大的努力传输进入网络的每一个分 组，但它无法给出一个定量的性能指标，譬如，吞吐量、端到端时延和分组丢失率等参 量的界。相应地，用户也无需进行业务许可的请求，因此网络的性能不仅仅是其本身可 以确定的，还受用户施加负载的影响，很显然，这种网络体系结构缺乏一定的隔离和保 护机制，但是建立在这种体系结构上的传统网络应用与网络协议具有较强的灵活性和适 应性。 随着网络的发展，其应用领域不断扩展，应用模式不断丰富，加之商业化进程的推 动，越来越需要对网络所传输的业务类型有一个较为具体和明确的定义，即所谓的网络 业务模型。从早期的i s d n ，到i n t s e r v ，再到后来的d i f f s e r v ，这些都是结合应用的需 要和技术发展提出来的。无论最终采用哪一种业务体系结构，其技术的核心都需要在恰 当的层次和力度上对流量进行必要的管理，其中包括接纳控制、流量成形、队列管理、 调度和拥塞控制等诸多方面，但最基本和最核心的应该依旧是拥塞控制，因为很难想象 一个时常有可能出现严重拥塞且无法及时加以恢复的网络能够实现良好的q o s 保证。实 施拼| 塞控制应该是其它q o s 机制正常工作的必要前提。 当然，j j 塞控制的研究并非山q o s 保证引起，它直是分组交换网络中倍受关注的 一个技术热点。对于它的研究，除了具有延续性的技术意义之外，在强调业务模型的新 网络体系结构中，如何通过增强的拥塞k i l n 为q o s 的实现提供了一定的便利，也是猢塞 控制研究的目标之一。 拥摩是一种持续过载的网络状态，j i - l h , 用户对刚络资源( 包括链路带宽、存储空州 和处理器的处理能力等) 的需求超过了其固有的容量。就i n t e r n e t 的体系结构而音，j f | 褒的发生是其固有的属性。闪为在事先没有任何协商和请求许可机制的资源兆享网络 q 、，几个i p 分组同时到达路由器，并期望经同一个输出端口转发的可能性足存在的， 显然，不是所有分组可以同时接受处理，必须有一个服务顺序中删节点上的缓存为等 候服务的分组提供一定的保护。然而，如果此状况具有一定的持续性，当缓存空叫被耗 鲁东大学硕士学位论文 尽时，路由器只有丢弃分组。表面上，增大缓存总可以防止由于拥塞引起的分组丢弃， 但随着缓存的增加，端到端的时延也相应增大，因为分组的持续时间( 1 i f e t i m e ) 是有限的， 超时的分组同样需要重传。因此，过大的缓存空间反而有可能妨碍拥塞的恢复，因为有 些分组白白浪费了网络的可用带宽。 捌塞导致的直接结果是分组丢失率的提高，端到端时延加大，甚至有可能使整个系 统发生崩溃。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量 ( g o o d p u t ) 急剧下降。拥塞崩溃对i n t e m e t 的威胁可以追溯到其早期的发展中，1 9 8 4 年 n a g l e 3 l 报告了由于t c p 连接中没必要重传所诱发的拥塞崩溃，1 9 8 6 1 9 8 7 年间这种现 象曾经发生多次，严重时度使l b l 到u c b e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落 到了4 0 b p s 5 i 。除此之外，还有其他一些诱发网络拥塞崩溃的原因，例如，不可达分组 ( u n d e l i v e r e dp a c k e t s ) 导致了网络崩溃，它与前一种有所不同，不是一种稳定状态，当网 络用户在减小时，拥塞可以自动恢复。f l o y d t6 1 也报告了一种拥塞崩溃现象，即分片拥 塞崩溃，网络传输了大量的分组分片，但因为无法在接受端重装成有效的分组而只好将 它们丢弃。网络传输大量的用户不再需要的陈旧分组( s t a b l ep a c k e t s ) 会导致另一种形式的 拥塞崩溃现象。图1 2 刻画了负载与吞吐量之间的关系，当负载较小时，吞吐量与负载 之间呈线性关系，到达膝点( k n e e ) 之后，随负载的增加，吞吐量的增量逐渐变小。当负 载越过崖点( p r e c i p i c e ) 之后，吞吐量却急剧下降。通常将k n e e 点附近称为拥塞避免区间； k n e e 和p r e c i p i c e 之间是拥塞恢复区间；p r e c i p i c e 之外是拥塞崩溃区间。为了最大限度 地利用资源，网络工作在轻度拥塞状态时应该是较为理想的，但这也增加了滑向拥塞崩 溃的可能性，因此需要一定的拥塞控制机制来加以约束和限制，这是研究拥塞控制最本 质的意义。 p 。r f 0 叼8 “。 ih r 。u s h u t 咝! ! ：二! ! 皿l k n e ep o i n t p r e c i p i c ep o i n t l o a d 图1 2 负载与吞吐量间的关系曲线 鲁东大学硕士学位论文 1 3 拥塞控制的研究概况 从控制理论角度，拥塞控带4 算法可以分为开环控制和闭环控制两大类。当流量特 征可以准确规定、性能要求可以事先获得时，适用开环控制：当流量特征不能准确描述 或者当系统不能提供预留资源时，适用闭环控制，i n t e m e t 中主要采用闭环控制方式。 闭环的拥塞控制分为以下3 个阶段【8 l ：检测网络中拥塞的发生；将拥塞信息报告到 拥塞控制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。闭环的捌塞控制可以动态 地适应网络的变化，但它的一个缺陷是算法性能受到反馈延迟的严重影响。当拥塞发生 点和控制点之问的延迟很大时，算法性能会严重下降。 根据算法的实现位置，可以将拥塞控制算法分为两大类：链路算法( 1 i n ka l g o r i t h m ) 和源算法( s o u r c ea l g o r i t h m ) 。链路算法在网络设备( 如路由器和交换机) 中执行，作用 是检测网络拥塞的发生，产生拥塞反馈信息。源算法在主机网络边缘设备中执行，作用 是根据反馈信息调整发送速率。拥塞控制算法设计的关键问题是如何生成反馈信息和如 何对反馈信息进行响应。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是目前i n t e r a c t 中使用 最广泛的传输协议。根据m c i 的统计，总字节数的9 5 和总报文数的9 0 使用t c p 传输”1 。近年来，t c p 中采用了很多新的算法1 1 0 i ，包括慢启动( s l o ws t a r t ) 、拥塞避免、 快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应答( s a c k ) 等，大大提高了 网络的传输性能。t c p 使用的拥塞控制算法已经成为保证i n t e r n e t 稳定性的重要因素【6 j 。 链路算法的研究目前集中在主动队列管n ( 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 pt a i l ) 相比，a q m 在网络设备的缓冲溢出之前就丢弃或 标记报文u l l 。a q m 的主要优点是： ( 1 ) 减少网关的报文丢弃。使用a q m 可以保持较小的队列长度，从而增强网关容纳 突发流量的能力。 f 2 ) 减小报文通过网关的延迟。减小平均队列长度可以有效地减小报文在网络没备 中的排队延迟。 ( 3 ) 避免l o c k o u t 行为u 2 的发生。 a q m 的一个代表是r e d ( r a n d o me a r l yd e t e c t i o n ) 。研究表明，r e d 比d r o pt a i l 具 有更好的性能。但是，r e d 的性能对算法的参数设置十分敏感，至今没有在i n t e m e t 中 得到广泛的使用。 对于a q m 的研究，大多采用依赖于直觉的肩发设计加通过仿真试验验证的模式来 鲁东大学硕士学位论文 进行。不可否认，这种模式为网络设计积累了不少经验，发掘了不少新的方法与策略。 在体系结构、协议和机制的研究中无疑是一种最为理想的方式。但在有关算法的研究中， 我们有理由怀疑这种模式的有效性，因为启发式的设计不免带有盲目性和片面性。r e d 算法两次修正设计参数m 1 的事实充分说明了这一点。 近年来，非线性规划理论 1 4 1 、系统理论1 = 5 , t 6 和优化控制理论1 被引入到拥塞控制 中来，一些研究者尝试使用严格的数学模型来描述由端系统和网关共同组成的系统，例 如c h o l l o t 等人利用小信号分析的方法呻i ，在工作点处线性化v m i s r a 给出的t c p a q m 控制模型，并根据这个模型，理论分析了r e d 稳定性 1 9 , 1 5 1 。这些研究推动了拥塞控制 的研究。 一些新的a q m 算法，如r e m ( p , a n d o me x p o n e n t i a lm a r k i n g ) ”。”、v q ( v i r t u a l q u e u e ) i5 , 2 3 1 、p i i 2 4 , 2 5 1 、p d ”i 、p i d 2 6 2 7 2 8 1 适用于大时滞系统的内模补偿算法等不断涌现， 但是它们缺乏在实际网络中的测试。 1 4 论文的主要工作及结构安排 i n t e r n e t 网络的复杂环境及系统本身的非线性、时滞、不确定的因素，使得流量控 制问题变得环境复杂。正因为如此，网络控制问题成为人们研究的热点和难点。人们已 经提出了很多具有不同特点的方案，并不断有新的方案出现。 a q m 策略在高吞吐量和低时延之问做出合理平衡的关键在于始终将队列长度维持 在一个较小的期望值，从控制系统的角度分析，这是典型的调节系统的技术目标。控制 理论是- - f q ? h 当成熟的系统理论，有相当多的方法可以用来对现有拥塞控制的稳态与动 态性能进行分析以及设计新的拥塞控制算法。论文的主要工作及结构安排如下： 笫一章为绪论，介绍了网络拥塞和拥塞控制的基本概念，简单介绍了拥塞控制的研 究概况： 笫二章为i n t e r n e t 捌塞控制机制研究，介绍了i n t e r n e t 中端到端的棚塞控制和i p 层 r r 、j t j 褒控制机制进行回顾； 第二章为土动：扶刿管理算法，介绍了几种主动队列苫理祝制，剥儿科算法进行了分 析和比较。 第四章为t c p i p 网络模型研究进展，主要介绍了基于t c p 拥塞控制主动队列管理 的解析法建模和分析方法。 鲁东大学硕士学位论文 第1 上章为基于状态空间模型的预测拥塞控制算法，针对i n t e r n e t 网络中一些现有 算法在具有传输延时以及由于用户数的动态和网络时延变化而引起的高频扰动和测量 误差因素的情况下，算法稳定性急剧下降或产生振荡的缺点，设计了一种预测拥塞控制 算法，使网络传输中由时变延迟和量化引起的不可测扰动极小化。 第六章为基于预测的p i d 控制算法，采用预测控制的方法来调节p i d 控制器的参 数。利用预测控制的方法求得控制增量，然后对控制增量进行前向加权求得即时控制率， 然后根据求得的控制律设计p i d 控制器的参数。仿真试验表明，设计的控制器提高了网 络性能。 第七章为基于神经网络的预测拥塞控制算法，提出了一种神经网络的预测方法。我 们利用相邻两个时刻的队列长度差值和的变化趋势来预测下一时刻队列长度差值，从而 得到下一时刻队列长度的预测值。根据下一时刻队列长度的预测值与期望值之差来设计 控制增益，使网络能及时对流量的变化做出反应，以防止拥塞的发生。该方法可以使路 由器中队列长度值稳定在个期望值附近。 第八章为基于模糊控制的网络拥塞控制算法，利用模糊预测的方法来研究网络拥塞 的问题，利用网络在过去两个时刻队列长度的变化值来预测下一个时刻的队列长度。这 种采用相邻两个时刻队列长度变化值来预测下一时刻队列长度的方法能更精确的反映 出队列的变化趋势。从而对队列长度的变化及时做出反应，使缓冲区中队列长度值稳定 在期望值附近。最后仿真结果证明了算法的有效性。 第九章为结论与展望，总结了本文所作的工作并且提出了以后网络研究中需要做的 研究工作。 鲁东大学硕士学位论文 2 1 基本概念 第二章in t e r n e t 拥塞控制机制 2 ；1 1 拥塞产生的原因 拥塞产生的直接原因有以下三点： ( 1 ) 存储空问不足。几个输入数据流共同需要一个输入端口，在这个端口就会建立排 队，如果没有足够的存储空间存储数据包就会丢弃，对突发数据流更是如此，增加存 储空间在一定程度上可以缓解这一矛盾，但如果路由器有无限的存储量时，拥塞只能变 得更坏，而不是更好，因为在网络罩数据包经过长时间排队完成转发时，它们早已超时， 源端认为它们已经被丢弃，而这些数据包还会继续向下一路由器转发，从而浪费网络资 源，加重网络拥塞。 ( 2 ) 带宽容量不足，低速链路对高速数据流的输入也会产生拥塞。根据香农信息理 论，任何信道带宽最大值即信道容量c = b l 0 9 2 ( 1 + s r ) ( 为信道白噪声的平均功率， s 为信元的最大功率，b 为信道带宽) 。所有信元发生的速率凡必须小于或等于信道容量 c 。如果r c ，则在理论上无差错传输就是不能的。所以在网络低速链路处就会形成 带宽瓶颈，当其满足不了所有信元带宽要求时，网络就会发生拥塞。 ( 3 ) 处理器能力弱，速度慢也能引起拥塞。如果路由器的c p u 在执行排队缓存、更 新路幽表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高速 c p u 也会产生捌塞。 要避免拥塞的发生，对以上三点原因需综合考虑。例如，提高链路速率而不改变处 理器，只会转移网络瓶颈，而不能避免拥塞，所以拥塞往往也是系统各部分不匹配的结 粜。 2 1 2 捆塞控制算法的评价方法 仡设计和比较棚塞控制算法时。需要一定的评价方法。从用户的角度出发。可以比 较端系统的吞吐率、丢失率和延迟等指标，这些是用户所关心的。由于捌塞控制算法对 整个网络系统都有影响，在评价算法刑更应该从整个网络系统的角度出发进行考虑。两 鲁东大学硕士学位论文 个重要的评价指标是资源分配的效率性和资源分配的公平性。 1 资源分配的效率。资源分配的效率可以用p o w e r 函数来评价 2 9 , 3 0 1 。p o w e r 函数定 义为 p o w e r = t h r o u g h p u t 。r e s p o n s e t i m e 在上式中，一般取口= l 。如果评价偏重于吞吐量，则取口 1 ；如果评价偏重响应 时问，则取口 1 。研究表明，当负载位于拐点k n e e 时，p o w e r 取最大值。使用p o w e r 函数有一定的局限性，它主要基于m m 1 队列的网络，并假设队列长度为无穷。p o w e r 函数一般在单资源、单用户的情况下。 2 资源分配的公平性。在多用户情况下，需要考虑资源分配的公平性。公平性评价 的主要方法有最大一最d , ( m a x m i nf a i m e s s i ”) 、公平指数( f a i r n e s s i n d e x i ”i ) 和比例公平 1 3 3 等。 m a x m i n f a i r n e s s 定义为：每个用户的吞吐量至少和其它共享相同瓶颈资源的用户 的吞吐量相同。m a x m i nf a i r n e s s 是一种理想的状况，但是它不能给出公平的程度。 公平指数( f a i r n e s si n d e x ) 提供了一个计算公式，可以计算公平的程度。它定义为 砸，= 端 f a i r n e s si n d e x 的计算结果位于0 和l 之间，并且结果不受衡量单位的影响。它的 一个性质是：如果n 个用户中只有k 个用户平均共享资源，而另p l ( n k ) 个用户没有任何 资源，则公平指数为k n 。公平度是连续函数，任何负载的变化都会立即影响到公平度 的变化。 一些研究者认为，如果考虑用户的“效用函数”( u t i l i t y f u n c t i o n ) ，在一些情况下使用 m a x m i nf a i r n e s s 评价并不是最理想的。针对对数的效用函数，文献 8 引入了 p r o p o r t i o n a lf a i r n e s s 的概念。p r o p o r t i o n a lf a i r n e s s 定义为： 向量x 满足p r o p o r t i o n a lf a i r n e s s ，如果对于其他任何向量y 都满足 v 兰! 二三! 0 -x 由于公平度是针对资源分配而苦的，所以在i 5 t 。：- y 介前日先要确定“资源”的含义，日前 人多数研究神：评价公平性时都针对吞吐量，这是从用户的角度出发考虑的，并不完全适 合网络中资源状况，网络中资源包括链路带宽、网笑的缓冲和网芙的处理能力等，在考 察公平性时应当对这些资源的分配情况综合加以考虑。 鲁东大学硕士学位论文 2 2 端到端的拥塞控制研究 目前在i n t e r n e t 上采用t c p i p 协议，实际使用的拥塞控制基本上是建立在t c p 的 窗口控制基础之上的，i p 层( 网络层) 的路由器所起的作用相对较小，但现在在i p 层 控制拥塞的研究逐渐增多，已经形成了一个新的研究热点。 2 2 1 端到端拥塞控制的发展 端到端的拥塞控制是从数据传输的角度出发，增强网络终端的流量控制功能，从而 控制网络中间节点的状态，提供给应用一个具有一定质量的连接。早期的拥塞控制方式， 路由器通过丢弃分组或显示拥塞通告( 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 e c n ) 来向源端指 示拥塞的发生，路由器是相对被动的，源端系统对这些拥塞信号进行响应。这种路由器 被动而终端主机主动的端到端拥塞控制机制遵守了两个主要原理：( 1 ) 实现流控自同步 ( s e l f - c l o c k i n g ) 的分组守恒定理，它基本确定了什么时候必须改变窗口大小，什么时候应 该传输分组：( 2 ) “和式增加积式减少”( a d d i t i v e i n c r e a s em u l t i p l i c a t i o n d e c r e a s ea 1 m d ) 的窗口管理策略。a i m d 依赖简洁的实现机制，在多个相互冲突的目标之间实现了较为 理想的平衡与协调。虽然无法保证具有不同属性的终端系统( 比如不同r t t 时间、不 同分组大小、经历不同跳数的拥塞链路等) 能够分配到等量的带宽，但却能够确保大致 相似的用户得到基本相等的网络资源。 t c p 拥塞控制机制是端到端的流量控制的最主要手段。早期的拥塞控制研究主要 集中在t c p 的1 井i 塞控制，近年来各种非t c p 流的拥塞控制研究逐渐丰富。由于t c p 的 捌塞控制对具有相似的r 1 1 时问、分组大小和拥塞程度终端能做出大致相似的响应。 因此，能够确保大致相似的用户分配到大致相等的网络资源，从这个角度看，t c p 具有 公平性，这是t c p 拥塞控制最本质、最重要的特性。随着i n t e r n e t 的不断发展，各种应 用越来越多、越来越广泛。不仅传统的基于t c p 的得到广泛应j t j ( 如i i t t p , s m7 r r l q p 等) ，而且新兴的非t c p 应用l i 断得到增长，特别足在实时多媒体应j i - j 和多播( m u l t i c a s t ) 等方面。i c p0 0a i m d 机制，：门+ 王火敏感而时堑了：歇感的应用l i | l - ”i ij 适合，而对时延敏感， 但彳i 要求可靠传输的实时应用则硝i 能满足需要。在探测空闲带宽和响应棚塞的过程中， r l c p 的 j 塞控制算法造成r 信源速率的大幅度变化。虽然有些“尽力传输”的业务能够 很好地适应这种变化，但其它应t = j 显得极不适应，比如流媒体业务更希望拥塞控制机制 对于拥塞的响应能够缓慢一些，从而有一个较为平滑的带宽占用来更好地匹配实时生成 鲁东大学硕士学位论文 的业务。因此，许多多媒体应用为保证服务质量，以固定速率发送数据，这样就会造成 t c p 流得不到公平的带宽。在组播业务中，t c p 的拥塞控制更显得不恰当。由此带来了 新的问题。一方面，需要一致的t c p 拥塞控制来达到公平的带宽分配。另一方面，为 了适应业务的特点而期望放弃t c p 的拥塞控制机制。这种尴尬的两难局面促使研究者 提出了新的拥塞控制机制，于是有了两个相近的概念：t c p 兼容性( c o m a t i b i l i t y ) 平l lt c p 友好一 生( f r i e n d l i n e s s ) 。近年来出现了许多t c p 友好的拥塞控制算法的研究。 一些专门针对网络的多媒体应用传输控制协议也在迅速发展中。t c p 协议提供可靠 的端到端的传输控制，但是它的传输速率抖动大，并且多媒体流不需要完全可靠的传输； u d p 协议简单实用，但是不提供拥塞控制，不能和t c p 友好共存，容易引起网络的拥 塞，t c p 友好拥塞控制机制的研究为流媒体的控制作了一定的准备。实时传输协议r t p 、 流媒体传输控制协议s t c p 、数据报拥塞控制协议d c c p ( d a t a g r a mc o n g e s t i o nc o n t r o l p r o t o c 0 1 ) 等是业界最近讨论的热点。 2 2 2t o p 拥塞控制 t c p 搠塞控制是通过控制一些重要的参数的改变实现的。t c p 用于拥塞控制的参 数主要有： ( 1 ) 拥塞窗口( c w n d ) ：描述源端在棚塞控制情况下最多能发送数据包的数量： ( 2 ) 通告窗v j ( a w i n ) ：是接收端给源端预设的发送窗口大小，它只在t c p 连接建立的 初始阶段使用： ( 3 ) 发送窗1 2 1 ( w i n ) ：是源端每次实际发送的数据的窗口大小： ( 4 ) 慢启动阈值( s s t h r e s h ) ：是拥塞控制中慢启动阶段和搠塞避免阶段的分界点，初始 值通常设为6 5 5 3 5 b y t e s ； ( 5 ) 同路响应时问( r t t ) ：一个t c p 数据包从源端发送到接收端，源端收到接收端确 认的时问i n l 隔： ( 6 ) 超时重传计数器( r t o ) ：描述数搦包从发送到失效的州f 叫m 隔，通常设为2 r t t 或j 1 t ： ( 7 ) 快速重传闷值( t c p r e x m t t h r e s h ) ：是能触发快速重传的源端收到重复确认的包 a c k 的个数。当此个数超过t c p r e x m t t h r e s h 时，网络就进入快速重传阶段，其缺省值为 3 ： 基于源端的拥塞控制策略中，使用最为广泛的是t c p 协议巾的拥塞控制策略，t c p 鲁东大学硕士学位论文 的拼j 塞控制采用的是基于窗口的端到端的闭环控制方式。t c p 协议是目前互联网中使用 最为广泛的传输协议。 t c p 协议的目的是为上层应用提供可靠的服务，其主要特征在于：( 1 ) 确保各流享 用带宽的公平性。( 2 ) 动态发现当前可利用的带宽。( 3 ) 拥塞避免及控制机制以避免捌塞 崩溃( c o n g e s t i o nc o l l a p s e ) 的发生。 标准版本的t c p 使用的是一种和式增加积式减d , ( a i m d ) 的基于窗口的控制发送速 率机制。发送端每收到一个确认，就对拥塞窗口加1 。当源端监测到丢包事件，则将当 前的拥塞窗口减半，降低发送速率，并重传丢失的数据包。t c p 采用a m i d 以保证稳定 性及带宽享用的公平性。大量的实践证明这种拥塞控制机制对i n t e m e t 上大量文件传输 等b e s te f f o r t 型服务具有较好的适应性。但人们认为它们依旧不够完善，需要新的策略 与算法来完善研究与应用中的新问题。 早期的t c p 协议只有基于窗e l 的流控制( f l o wc o n t r 0 1 ) 机制而没有拥塞控制机制，因 而易导致网络拥塞。1 9 8 8 年v a nj a c o b s o n 针对t c p 在网络拥塞控制方面的不足，提出 了“慢启动”( s l o ws t a r t ) 和“拥塞避免”( c o n g e s t i o na v o i d a n c e ) 算法。它们被所有的i n t e r n e t 主机支持，在很长一段时问内，接收端驱动t c p 流量控制是唯一可行的捐j 塞控制方法。 1 9 9 0 年出现了t c pr e n 0 1 3 4 1 版本增加了“快速重传”( f a s tr e t r a n s m i t ) 、“快速恢复”( f a s t r e c o v e r y ) 算法，避免了网络拥塞不够严重时采用“慢启动”算法而造成过度减少发送窗 口尺寸的现象，这样t c p 的拥塞控制就有这4 个核心部分组成。前几年又出现了t c p 的改进版本如t c pn e