（控制理论与控制工程专业论文）基于模型的网络拥塞控制研究.pdf

硕士论文 基于模型的网络拥塞控制研究 摘要 随着i n t e m e t 用户和各种各样的网络服务的迅速发展，i n t e m e t 变得日益繁忙，流量 急剧增加。由于网络资源的瓶颈约束以及i n t e m e t 的流量突发性，很容易导致网络产生 拥塞现象。因此如何更好地预防和控制拥塞一直是近年来国际上网络研究领域的热点问 题。 本文描述了网络拥塞控制现象及其产生本质。研究了几种主要的t c p i p 拥塞控制算 法，并阐述了从经典控制理论的角度研究网络拥塞控制。本文的工作如下： 1 、针对r e d 及其改进算法存在依赖于直觉，没有全面系统地从理论上对算法加以 分析研究的问题，本文基于m i s r av 提出的流体流理论，详细推导了网络的t c p a q m 简化模型。 2 、基于该模型，分析了p 控制器在拥塞控制中应用，比较了在不同的k 条件下队 列变化的曲线，并进行了频域分析。 3 、针对p 控制下系统存在稳态误差的情况，引入了p i 控制器，通过仿真曲线比较 了和p 控制器的差别。 4 、针对p i 控制下系统稳态误差减小，但系统响应速度降低的情况，引入了p d 控 制器，通过仿真曲线分别和p 、p i 控制器的控制性能进行了比较。 5 、通过实验表明p d 控制器具有可以减少系统的超调，响应速度快，但队列曲线波 动的特点。 6 、根据链路的数据包丢失率是动态的，p i 控制器需要动态调整配置参数，才能保 证算法有更快的收敛速度和更小的队列抖动、保证对网络状态变化的快速响应、提高缓 冲区的利用率的情况。本文提出了自适应a q m 算法_ a p i v 控制器，理论分析和仿真 表明，a p i v 算法在动态网络环境下，性能优于p i 算法及其改进算法。 关键字：i n t e m e t ，网络模型，拥塞控制，主动队列管理，控制理论，a p 卜- v a b s t r a c t 硕士论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fn e t w o r ku s e r sa n da l lk i n d so f a p p l i c a t i o n s ，i n t e r n e tt r a f f i ci s b e c o m i n ge x t r o d i n a r yb u s i e rn o w a d a y s c o n g e s t i o np h e n o m e n a no c c u r se a s i l yd u et ot h e r e s t r i c t i o no fi n t e r n e tr e s o u r c eb o t t l e n e c k sa n dt h eb u r s t yn a t u r eo fi n t e r n e tt r a f f i c s oh o w t o p r e v e n ta n dc o n t r o lc o n g e s t i o ni so n eo ft h em o s ta c t i v ef i e l d si nt h ec o m p u t e rn e t w o r k s t h eb a c k g r o u n d sa n dc a u s e so fi n t e r n e tc o n g e s t i o np h e n o m e n o na r ei n t r o d u c e di nt h e b e g i n n i n go ft h i st h e s i s t h i st h e s i sa l s od e s c r i b e sa n dc o m p a r e ss o m es i g n i f i c a n tt c p i p c o n g e s t i o nc o n t r o la l g o r i s m si nd e t a i l ，a n dr e s e a r c h e ss o m en o v e lr e s e a r c hm e t h o d sa n dr e s u l t s i nt h ei n t e m e tc o n g e s t i o nc o n t r o lw i t ht h ep e r s p e c t i v eo fc l a s s i cc o n t r o ls y s t e m t h es t u d yi n t h i st h e s i si sl i s t e da sf o l l o w s ： 1 b e c a u s er e da n di t sm o d i f i e da l g o r i t h md e p e n do nt h e i n t u i t i o n ，t h e ya r el a c ko f s y s t e m a t i c a la n dt h e o r e t i c a l ，t h et h e s i si n f e r r e st h es i m p l i f i c a t i o nm o d e lb a s e do nt h ef l u i d s t r e a mt h e o r yp r o p o s e db yo nm i s r avh a sb e e n 2 b a s e do nt h i sm o d e l ，t h epc o n t r o l l e ri sa p p l i e di nt h ec o n g e s t i o nc o n t r 0 1 t h et h e s i s c o m p a r e s 诵mt h eq u e u ec u r v eu n d e r t h ed i f f e r e n tkc o n d i t i o n ，a n dc a r r i e so nt h e 仔e q u e n c y r a n g ea n a l y s i s 3 i nv i e wo ft h es y s t e me x i s t i n gs t a t i ce r r o ru n d e rt h epc o n t r o l ，t h ep ic o n t r o l l e ri s i n t r o d u c e d t h et h e s i sh a sc o m p a r e dw i t ht h epc o n t r o l l e rt h r o u g ht h es i m u l a t i o nc u r v e 4 i nv i e wo ft h es y s t e ms t a t i ce r r o rr e d u c i n gu n d e rt h ep ic o n t r o l ，b u tt h es y s t e ms p e e do f r e s p o n s er e d u c i n g ，t h ep dc o n t r o l l e ri si n t r o d u c e d c o n t r o lp e r f o r m a n c ec a u s e db yp ia n dp d c o n t r o l l e rh a sb e e nc a r r i e do nt h ec o m p a r i s o nt h r o u g ht h es i m u l a t i o nc u r v e 5 t h ee x p e r i m e n ti n d i c a t e st h ep dc o n t r o l l e rc a nr e d u c et h eo v e r m o d u l a t i o no ft h es y s t e m ， i m p r o v et h es p e e do fr e s p o n s e ，b u tt h eq u e u ec u r v ev i b r a t e s 6 a c c o r d i n gt ot h el o s sr a t eo fd a t ap a c k e ti sd y n a m i c ，t h ep ic o n t r o l l e rn e e d sa d j u s tt h e p a r a m e t e rd y n a m i c a l l yt og u a r a n t e et h ea l g o r i t h mh a st h eq u i c k e rc o n v e r g e n c er a t ea n dt h e s m a l l e rv i b r a t i o n , a n df a s tr e s p o n s et ot h en e t w o r kc h a n g e ，e n h a n c i n gt h eu s ef a c t o ro ft h e b u f f e r t h ea u t o a d a p t e da q ma l g o r i t h m - - a p i vc o n t r o l l e ri sp u r p o s e d t h et h e o r e t i c a l a n a l y s i sa n dt h es i m u l a t i o ni n d i c a t et h a tt h ep e r f o r m a n c eo ft h ea p i - va l g o r i t h ms u r p a s s e st h e p ia l g o r i t h ma n di t sm o d i f i e da l g o r i t h mu n d e rt h ed y n a m i cn e t w o r ke n v i r o n m e n t k e y w o r d s ：i n t e m e t ，m o d e lo fn e t w o r k s ，c o n g e s t i o nc o n t r o l ，a c t i v eq u e u e m a n a g e m e n t ( a q m ) ，c o n t r o lt h e o r y , a p i _ - v 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位 论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布过的 研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料。 与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明确的说 明。 r 一一7 研究生签名：主二望堕 2 酗扩年7 月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上网 公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权其保 存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文，按保密 的有关规定和程序处理。 研究生签名： 如辑 月日 硕士论文 基于模型的网络拥塞控制研究 1 绪论 本章首先介绍网络拥塞的含义及其产生的本质原因，然后分别介绍网络拥塞算法的 分类，阐述了目前国内外网络拥塞控制研究的，指出本文研究的主要内容和论文的章节 安排。 1 1 网络拥塞及其产生原因 过去的十几年中计算机网络在经历了爆炸式的增长，随着网络规模的不断扩大，网 上业务量的增长，当网络中存在过多的数据包时，网络的性能就会下降，这种现象被称 为拥塞。在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃 【1 捌( c o n g e s t i o n c o l l a p s e ) 。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量 ( g o o d p u t ) 急剧下降。 鬈 吐 量 l鬣嘴c i【e _ p 一一 一 k 矗o u ：! r l 掰络灸馥罔终负筑 ( 基)c b ) 网带贝曩 ( c ) 图1 1网络负载与吞吐量、响应时间及网络性能的关系 图1 1 描述了网络负载与吞吐量、响应时间及网络性能的关系f 3 j 。由图可见，当网络 中负载较小时，吞吐量基本上随负载的增长而增长，呈线性关系，响应时间增长缓慢； 在负载达到网络容量时，吞吐量增长缓慢，响应时间急剧增加，这一点称之为膝点 ( k n e e ) ；如果负载继续增加，路由器开始丢包，当负载超过一定量时，吞吐量开始急剧 下降，这一点称为崖点( c l i f f ) 。通常将膝点附近称为拥塞避免区间；膝点到崖点之间是 拥塞恢复区间；崖点之外是拥塞崩溃区间。可以看出，负载在膝点附近时网络的使用效 率最高。 l 绪论 硕士论文 网络产生拥塞的根本原因在于用户( 或叫端系统) 提供给网络的负载大于网络资源容 量和处理能力。表现为数据包延时增加、丢弃概率增大、上层应用系统性能下降等，拥 塞产生的直接原因有以下三点【4 】： r ( 1 ) 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个端口就会建 立排队。如果没有足够的存储空间存储，数据包就会丢弃。对突发数据流更是如此。增 加存储空间在某种程度上可以缓解这矛盾，但如果路由器有无限存储量时，拥塞只会 变得更坏，而不是更好，因为在网络里数据包经过长时间排队完成转发时，它们早已超 时，源端认为它们己经被丢弃，而这些数据包还会继续向下一路由器转发，从而浪费网 络资源，加重网络拥塞。 ( 2 ) 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据香农信息理 论，任何信道带宽最大值即信道容量c = b * i 0 9 2 ( 1 + s n ) ( n 为信道白噪声的平均功率，s 为信源的平均功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容量c 。 如果r c ，则在理论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽 瓶颈，当其满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢也能引起拥塞。如果路由器的c p u 在执行排队缓 存，更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路 对高速c p u 也会产生拥塞。 从上匾我们可以看出，拥塞现象的发生是对网络的需求大于供给。有限的资源由多 个用户使用。没有相应的机制对用户的数量产生控制。不断增长的需求数量，必然会导 致拥塞的发生。拥塞控制本质是一个如何共享资源的问题。在包交换网络中，所有的激 活终端共享网络资源。这些资源包括节点处理能力、缓存空间和通信链路带宽。在这三 者中的任意一个都可能成为潜在的瓶颈，从而导致网络拥塞。拥塞导致的直接后果是分 组丢失率增加，端到端延迟加大。 在面对网络产生拥塞时发现，上述原因不能单独考虑，因为提高链路速率而不改变 处理器，只会转移网络瓶颈，而不能避免拥塞。增加缓存空间到一定程度时，只会加重 拥塞，而不是减轻拥塞。另外，增加链路带宽及提高处理器能力也不能解决拥塞问题。 所以对以上三点原因需综合考虑，单纯地增加网络资源不能解决拥塞问题。拥塞本身是 一个动态问题，它不可能只靠静态的方案来解决，而需要协议能够在网络出现拥塞时保 护网络的正常运行。 i 2 网络拥塞控制及其研究目的 网络拥塞控制策略包括拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制( c o n g e s t i o n c o n t r 0 1 ) 这两种不同的机制。拥塞避免是“预防机制，它的目标是避免网络进入拥塞状 态，使网络运行在高吞吐量、低延迟的状态下。拥塞控制是“恢复 机制，它用于把网 2 硕士论文基于模型的网络拥塞控制研究 络从拥塞状态中恢复出来。在网络控制的研究中，拥塞控制和流量控制是网络的经典问 题1 4 ，但它们两个的概念比较容易混淆。拥塞控制必须确保网络能进行数据传输，这是 全局性的问题，涉及到所有主机、路由器以及所有其他将导致削弱网络负荷能力的因素。 而流量控制只与发送者和接受者之间的点到点的数据传输有关，它的任务是确保一个快 速发送方的发送速率不超过接收方的最大接受速度。可以看到，流量控制的功能实现位 于网络的传输层，实现比较简单；而拥塞控制从广义上讲，涉及网络的所有层次，在具 体的实现中，拥塞控制一般通过网络层和传输层相互协调来完成。从不同的角度，拥塞 控制可以被分为很多类。 拥塞控制的研究目的不是要完全避免拥塞，而是研究怎样的拥塞程度是合适的。这 是因为：t c p i p 网络采用分组交换技术来提高网络链路的利用率，造成路由器的队列缓 存经常被占；如果路由器的队列缓存总是空的，虽然传输延迟小，但是网络的利用率也 低；如果路由器队列缓存总是被占，传输延迟变大，但是网络利用效率也高。拥塞控制 的目标是实现网络利用率和传输延迟等综合性能指标的最优化。由此可以看到，通过网 络的拥塞控制，可以提高网络的总体性能，保证网络系统长期的稳定性和鲁棒性。 1 3 网络拥塞控制系统算法的分类 拥塞控制算法根据其实现位置的不同，可以分为两大类：链路算法【5 - 7 和源算法【8 1 ( 图 1 2 ) 。链路算法是指算法是在网络中间设备如路由器或交换机上实施的，目前研究正集 中在“主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 【9 l o ，1 1 1 算法方面；源算法是指在 端系统中运行的算法。 l 绪论 硕士论文 旗f 窗霸 镎法 捌鬻控制 辣法 添算法if 链路辣法 蘩子速率 铱法 鳃攘饽i 凌 p j n b o w 难播算竣 r a p l n a + t f r c t e a r 珂l 播算浚 r l c f l i d d l i j s t f r p m 10 a 调度 机制 数列求】缓 稃静理 歇列传理 1 越i d r o p d r a p f r o m - f r o 吐 r a n d o m 如p 图1 2 控制算法分类 1 3 1 源算法 源算法在主机和网络边缘设备中执行，作用是根据反馈信息，调整发送速率。源算 法中除t c p 协议本身的拥塞控制算法，如已经广泛运用于现实网络中的和式增加积式减 少( a i m d ) 【忆】机制外，还有大量的算法被广泛的研究。源算法中使用最广泛的是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 3 】。近年来，t c p 中采用了很多 新的算法【1 4 1 ，包括慢启动( 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 ) 、快速重传( f a s t r 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 a c t 稳定性的重要因素。 在源算法【1 5 以9 】中，我们使用基于不同的对拥塞进行响应的方式作为分类的标准将源 算法分为两类：基于窗口和基于速率的源算法，而第三级分类标准则是基于单播或基于 组播。下面我们将分别介绍我们列出的算法。 速度适应协议( r a p ：r a t ea d a p t i o np r o t o c 0 1 ) 2 0 堤一个简单的应用于单播数据流的 4 铱 限 率 甜p 棼 速 k a 嘲 辫一 埘理 动黻器胍 奠鳓旺旺札甜 理 旷晒譬龟 列o q 黜附呻咐孵 硕士论文基于模型的网络拥塞控制研究 a i m d 机制，每一个分组都必须被接收者应答( a c k n o w l e d g e d ) 。a c k 分组被用来探测拥 塞和推算r t t ，当探测到拥塞，发送方将当前的拥塞窗口减半。在没有分组丢失亦 即没有出现拥塞的时候，协议在每个i m 后将拥塞窗口总加1 。协议在每个r 1 盯之后决 定速率的变化增加或减少，取决于当前的网络状况。r a p 在发送行为上与a i m d 机 制非常相似，但它没有考虑超时的情况。因此当网络拥塞主要导致超时发生时，r a p 将 表现得更具侵略性。 基于丢失一延迟的适应算法( l d a + ：l o s s d e l a yb a s e d a d a p t i o n a l g o r i t h m ) 【2 1 j 与其它 的机制不同，它没有设计自身的反馈机制来控制发送速率，而是仅仅依靠实时传输协议 ( 砌p ：r e a l t i m et r a n s p o r tc o n t r o lp r o t o c 0 1 ) 提供的反馈信息进行调节。l d a + 同样是以 a i m d 为基础的，但是它增加了一些影响因素。a i m d 的增加和减少因子是随着网络状 况而调节的。它通过分组对来判断瓶颈链路的带宽，从而来决定当前网络是否拥塞，进 而决定采取的行动。速率的增加是如下三个相互独立因子的最小者： 带宽低的数据流的增加速率可以比带宽高的数据流快 数据流不能超过估计的瓶颈带宽 数据流增加带宽的速率不能比t c p 连接快 当接收方报告分组丢失的时候，发送速率就以( 1 一( j ) ) 为因子积式减少，其中z 是 分组丢失率。模拟显示l d a + 与t c p 在给定的环境中公平竞争。t c p 友好速率控制协议 ( t f r c ：t c p - f r i e n d l yr a t ec o n t r o lp r o t o c 0 1 ) 2 2 1 是专门设计用来进行单播传输的，它通过 对公式( 1 1 ) 2 3 】的计算来调节发送速率。公式( 1 1 ) 是一个t c p 的吞吐量公式，r 代表回 路时间r 盯，r m 代表重传超时值，b 是发送分组的大小，用字节表示，p 是丢包率，既 是拥塞窗口的最大值，b 代表每次a c k 确认的分组个数。t f r c 使用了复杂的方法来收 集需要的参数，其中包括使用衰减加权方法来计算平均丢包间隔，从而降低久的丢包事 件对平均丢包率的影响。通过反馈到发送方的时间戳来计算i m 。t f r c 使用与t c p 相 似的方式进行慢启动，当出现丢包时，慢启动结束。在每个r t t 中，一旦t f r c 接收方 更新了参数并发送一个报告给发送方时，发送方就会利用这些参数计算一个新的公平速 率并以此为依据调整发送速率。t f r c 的一个主要的优点就是有一个相对稳定的发送速 率，并且仍然提供对竞争的充分的响应。 弭驴砒p ，荐一卜， 接收端t c p 模拟t e a r ( t c p e m u l a t i o n a t r e c e i v e r ) ( 2 4 1 是一个基于窗口和基于速率混 合的拥塞控制机制。t e a r 接收端计算一个直接的接收速率并将它发送到发送方，发送 l 绪论硕士论文 方然后据此调整它的发送速率。在t e a r 中，接收方维护着一个类似于t c p 拥塞窗口的 修改了的拥塞窗口。由于t c p 的拥塞窗口是位于t c p 发送方的，因此t e a r 接收方必 须通过接收到的分组来决定是增大还是减小当前的拥塞窗口尺寸。重复a c k 是容易模 拟的，但是，超时事件只有依靠粗略的估计。与t c p 相比，t e a r 协议不直接使用拥塞 窗口来决定发送分组的数量，而是计算相应的t c p 发送速率。为了避免锯齿状的发送速 率，t e a r 使用了加权平均的方法来决定一个时期内的平均发送速率。由于接近t c p 短 期行为的模型，t e a r 在避免t c p 的频繁改变速率的同时，表现了很好的t c p 友好行为。 1 3 2 链路算法 链路算法在网络设备( 如路由器和交换机) 上执行，作用是检测网络拥塞的发生，采 取一定的措施缓减拥塞状况，产生拥塞反馈信息以使发送端采取适当的措施避免拥塞恶 化。该算法主要分为两类：调度机制和队列缓存管理f 2 熨。事实上，调度机制和队列管理 都是一种缓存管理机制，而队列管理又是调度机制和缓存管理的补充，同时也是二者的 交叉结合。 调度机制又称为排队和调度机制、队列调度机制，其作用是控制分组选择发送的输 出链路。输入流量被置于一个排队系统中，一般情况下，这个排队系统由一个或多个队 列和一个调度器组成。一个有效的队列调度机制应能够保证公平性、时延特性、对恶意 业务流的隔离能力以及好的链路带宽利用率等。 缓存管理的任务【2 4 - 2 7 1 是决定如何在经过网关( 特定情况下，共用一个输出接口) 的不 同数据流之间分配缓存空间。缓存分配的策略有很多，包括各种动态或静态策略，这些 策略基于不同标准、基于数据流数量、基于当前或过去的带宽分配以及基于缓存占有量 等。而最广为人知的两种缓存管理机制就是共享缓存池( s h a r e db u f f e rp 0 0 1 ) 和单一流分配 机制( p e r - f l o wa l l o c a t i o n ) 。共享缓存池机制是以先到先服务为基础的，个数据流通过 尽可能快的发送速率可以占有整个缓存空间从而导致其他数据流处于“饥饿 状态，因 此这种机制缺乏数据流之间的保护，但是，由于简单和高的执行效率，这种机制在当今 i n t e m e t 路由器上非常普遍。单一流分配机制为每一个数据流建立一个缓存使用情况纪 录，基于每一个流的缓存占用水平来丢弃分组，从而起到了保护各个流的作用，但是由 于这样的处理过程太耗费资源，因而无法在骨干路由器上大规模推广。 队列管理的任务是通过选择丢弃分组以及丢弃时机来控制队列的长度和调度流。队 列管理是调度机制和缓存管理的补充，同时也是二者的交叉结合。该机制最重要的目标 是保证当链路可用时处于稳定状态的队列长度最小，或避免出现由于某个连接后流量 独占队列空间，而使其它流量被拒绝的现象。 目前i n t e m e t 中普遍采用的队列管理【1 6 1 9 ，2 8 3 2 1 方式是在路由器中设鹭每个队列长度 的最大值，并在队列长度达到这一最大值时就丢弃进入路由器的数据包，从而将队列长 6 硕士论文 基于模型的网络拥塞控制研究 度控制在一定值之内。但是，这种队列管理对于网络出现的突发数据流无能为力，会导 致大量分组丢失，网络吞吐量剧烈波动。因此，一种更加有效的队列管理方式主动 队列管理( a q m ) 被提出以解决这个问题。然而，必须指出的是，传统上t c p 将分组丢 失作为拥塞指示，因此，队列管理机制同样通过丢报或标记来生成拥塞反馈。在链路超 载的情况下，如果源端不响应拥塞的话，队列管理比调度机制有更强的控制能力。 和传统的队尾丢弃( d r o pt a i l ) 相比，a q m 在网络设备的缓冲溢出之前就丢弃或标记 报文。a q m 的主要优点是： ( 1 ) 减少网关的报文丢失。使用a q m 可以保持较小的队列长度，从而增强网关容 纳突发流量的能力。 ( 2 ) 减小报文通过网关的延迟。减小平均队列长度可以有效地减小报文在网络设备 中的排队延迟。 ( 3 ) 避免l o c k o u t 行为的发生。 1 4 网络拥塞控制研究的现状 近年来，国内外关于网络拥塞控制研究方面的成果很多，从已经发表的相关文献来 看，关于网络拥塞控制的研究主要集中在网络拥塞控制系统模型、主动队列管理算法等 几个方面。 在网络拥塞控制系统模型研究方面，r o y 等【3 3 】基于时滞微分方程建立了一个 t c p 瓜e n o 的流量模型，但没有考虑排队延时；p a d h y e 掣3 4 】提出了一个t c p 吞吐量模型， 并用这个模型导出了吞吐量和丢弃率的关系；a l t m a n 等f 3 5 】给出了一个多个t c p 连接有 不同回路响应时间的拥塞控制系统的数学模型，但也没有考虑排队延时；清华大学的魏 敏等【3 6 】针对网络中海量数据传输的网络拥塞控制问题，对网络流量稳定性控制的非线性 模型进行了分析和模拟：浙江大学的吴铁军教授等【37 】用混杂系统描述t c p 带有拥塞控制 策略的数据传输过程，建立了t c p i p 网络的动态模型；中国科学院的谭民教授等【3 8 】将 i n t e m e t 的拥塞控制看作为离散事件与连续变量相互作用的混杂动态过程，采用含有一个 状态的随机混杂模型，描述了t c p 拥塞控制过程中的a i m d 过程；同济大学的张树京教 授等【3 9 】在t c p 拥塞控制建模方面作了很多工作；华中科技大学的朱耀庭教授等【4 0 】提出 了一个高网络负荷下t c p 吞吐量的改进p a d h y e 模型；北京邮电大学的吴伟陵教授等【4 l 】 在分析实际采集数据的基础上，建立了h t t p 业务流量模型。这些模型在某些方面都还 有一些限制和不足，有些是模型太过复杂难以推广使用，有些模型未考虑超时阶段的影 响，有些模型未考虑其他如声明接收窗口大小等限制因素，因此，网络拥塞控制的建模 还要更深入的研究。 为持续有效地控制i n t e m e t 拥塞，许多学者一方面要继续改进已有的t c p 拥塞控制 算法，并要求所有用户采用兼容的端到端拥塞控制【4 2 】；另一方面，网络( 路由器) 也应采 7 1 绪论硕士论文 用适当的调度算法与队列管理策略，以便有效地避免拥塞。目前路由器中使用最广泛的 是简单的先进先出( f i f o ) 包调度算法结合“去尾 队列管理策略【4 3 】，即当路由器缓存已 存满时，丢弃后续到达的数据包。对f i f o 算法的改进包括公平排队算法( f q ) 、加权公 平排队算法( w f q ) 和基于类的排队算法( c b q ) 等。 “去尾”队列管理策略的主要缺点是会产生闭塞和满队列现象，造成大量的数据包 丢失而导致网络的效率降低和性能下降，没有解决持续的满队列问题。这促使网络专家 建议在路由器中采用“主动队列管理”( a q m ) 策略，即在驮列满之前就按一定概率丢弃 或标记少量数据包，从而使得在缓存溢出之前端点就能对拥塞做出响应。主动队列管理 ( a q m ) 是近年来端到端拥塞控制研究中的一个热点。a q m 与e c n ( 显示拥塞通告) 结合， 通告拥塞的信号不再是唯一的分组丢弃，而可以采用标记分组来通知信源减速，这样会 进一步提高连接的有效吞吐量。a q m 的目标是使路由器能控制平均排队长度，减少数 据包丢弃数。 关于主动队列管理算法的研究很多。随机早期检测( r e d ) 是最早提出的主动队列管 理算法 4 4 1 。r e d 的主要问题在于参数配置的困难，而配置不当则会引起网络不稳定和性 能下降。因此，尽管新的c i s c o 路由器中都包含了r e d 选项，但迄今r e d 还极少在实 际中使用。近期，人们对r e d 提出了多种改进方案，包括自适应r e d ( u 也d ) 、公平 r e d ( f r e d ) 、稳定r e d ( s r e d ) 等。同时，也有不少新的主动队列管理算法问世，如 r e m 4 5 1 、b l u e 4 6 1 、g r e e n l 4 刀等基于流量的主动队列管理算法；p i 算法【4 羽、d r e d l 4 9 1 、 f u z z y 控制算法【5 0 】等基于队列的主动队列管理算法等。 尽管已提出不少主动队列管理算法，但这些算法绝大多数是从直觉的角度来研究拥 塞控制问题的，缺乏理论依据。部分算法虽然是从控制的角度提出的，但算法的有效性、 稳定性、鲁棒性等还有待进一步分析和验证。因此，还需要研究有理论依据的主动队列 管理算法并进行详细的分析和多方面的性能验证。 1 5 本论文研究的主要内容及章节安排 本文研究了网络拥塞产生的原因和目前流行的t c p i p 拥塞控制策略。针对r e d 及 其改进算法存在的问题，详细推导了网络的t c p a q m 简化模型，通过n s 2 仿真曲线 分析和对比了p 、p i 、p d 、a p i v 等控制算法在网络拥塞控制中的控制性能。 各章节的内容组织如下： 第1 章描述了网络拥塞控制现象及其产生原因和研究目的，对网络拥塞控制系统 算法进行分类，介绍网络拥塞控制研究现状； 第2 章详细阐述了t c i i p 目前流行的拥塞控制策略； 第3 章基于m i s r a v 提出的流体流理论，详细推导了网络的t c p a q m 简化模型。 蓦手该模型，分析了p 、p i 、p d 控制器在拥塞控制中应用，比较了控制性能； 冀 第4 章根据p i 控制器在网络拥塞控制中的不足之处，提出了自适应a q m 算法一 a p i v 控制器，理论分析和仿真表明，a p i v 算法在动态网络环境下，性能优于p i 算法 及其改进算法； 第5 章结束语。 9 2t c p i p 拥塞控制策略 硕士论文 2t c p i p 拥塞控制策略 t c p i p 协议簇作为当今互联网的基石，有力地推动了网络技术的发展。i n t e r n e t 的 成功很大程度上取决于拥塞控制的有效执行。本章在第一章的基础上，对此机制进行了 进步的研究，主要分析基于源端的t c p 拥塞控制机制和中间节点的口拥塞控制机制， 并指出各自存在的问题。 2 1t c p i p 协议概述 t c p i p 协议簇己经成为计算机网络世界开发系统互联的事实标准。t c p i p 起源于 6 0 年代末美国政府资助的一个分组交互网络研究项目，到9 0 年代已发展成为计算机 之间最常用的组网形式。t c p i p 是一个真正的开放系统，是i n t e r a c t 的基础，通常被 认为是一个四层协议系统，如表2 1 所示，包括应用层、传输层、网络层和链路层。 表2 1t c p i p 协议模型 应用层( t e l n e t ，f t p 和e m a i l 等) 传输层( t c p 和i j l ) p ) 网络层( 口，i c m p 和i g m p ) 链路层( 设备驱动程序及接口卡) 链路层；为网络层提供设计良好的服务接口，把物理层提供的位流转换成供网络层 使用的帧流，处理传输差错，调整帧的流速，不至于使慢速接收方被快速发送方淹没。 网络层：定义了正式的分组格式和协议，即i p 协议( i n t e r a c tp r o t o c 0 1 ) 。它的功能就 是传输由其它用户发送的口分组，并发送到正确的目的机。网络层往往是载体和用户的 接1 2 。 传输层：整个协议层次结构的核心，t c p 协议( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 就是在 这里定义的端到端协议之一，它是一个面向连接的协议。传输层的任务是为从发送端到 目的端提供可靠、有效的数据传输服务，而与当前网络或使用的网络无关。它可以使发 送端和目的端主机上的对等实体进行会话。同时，它还要处理流量控制，以避免高速发 送方向低速接收方发送过多报文而导致接收方无法处理。 应用层：享受以下各层为它提供可靠的传输，它包含所有的高层协议。如虚拟终端 协议( t e l n e t ) 、文件传输协议( f t p ) 和电子邮件协议( s m t p ) 等。 t c p i p 作为一种因特网互联通信协议，目的是将各种异构计算机网络或主机通过该 协议实现互联。现有的互联网包括成几十万个的全球范围内的局域网，这些局域网通过 主干广域网进行互连。 1 0 硕士论文 基于模型的网络拥塞控制研究 2 2t c p 拥塞控制策略 t c p 协议是目前在i n t e m e t 中使用最为广泛的传输协议。据统计，i n t e m e t 上9 0 的 数据流使用的是t c p 协议。t c p 协议中使用的拥塞控制算法己经成为了保证i n t e m e t 正 常运行的重要因素。近年来，很多新的算法被引入到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 ) 、快速重传( 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 ) 5 1 , 5 2 】。同时提出了不同的t c p 实现版本，如 t c pt a h o e 、t c pr e n o 等。 t c p 拥塞控制技术最基本特征是基于窗口的闭环控制方式，即为“和式增加积式减 少( 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 v e d e c r e a s e ，a i m ) ) 。在介绍拥塞避免的算法前首先介 绍一下t c p 拥塞控制的几个重要参数，将各参数的含义显示在表2 2 中。 表2 2 拥塞控制参数表 控镪参数禽冀 摊塞棠日 通告窗瞪细糖毋 发送宦n 伽埘 馒痿动孵值( 鬟幽嗍 圜路响窟黠鲤嘲 超对震俦专滋嚣a 鼹劭 恢逮童传瞬缀蹲m t m m m i t 删 畿遴翊在搠褰控钥馋况下一移啜多娩发送分 组鲍数量 是揍牧端给援遴端凌设豹发送宙弱太小，只 在1 疆瘫蓉建立豹翘始翁爱留柞缮 般逶端每次实嚣笈送数据翁宙盈大小 是拥警羟期中经瘩确辫覆和秘塞避免阶段的 努努意耪i 奇链运需设为稻硒5 钾墩 十1 珊分缳筑发送螭发i 基嚣裟载端直至襞 避缨收鬟接数謦确认角c 较鲍时翊闻辆 接适分组麸震避巍失效约罾雩阎向隔燕搿辑分 组丢失与否麓终是否拥褒的氯要参数通常设 为期藏棚 是艇麓发倏遵譬铸豹发送璐毅劐重复礁歆包 a x 的个羹鸯超过瓣值对跨络统进入快德 重馋瓣致，懿省越为3 t c p 拥塞控制分为四个阶段：由慢启动、拥塞避免、快速重传和快速恢复四个核心 算法组成5 1 翊，t c p 源端拥塞窗口变化情况如图2 1 所示。 2t c p i p 拥塞控制策略 硕士论文 c l 瞄正 c 州2 图2 1t c p 源端拥塞窗口变化情况 ( 1 ) 慢启动阶段： 当主机开始发送数据时，如果立即将较大的发送窗口中的全部数据字节都注入到网 络中，那么由于此时不了解网络的状况，因而可能引起网络拥塞。经验证明，较好的方 法是试探一下，即由小到大逐渐增大发送端的拥塞窗口数值。通常在刚刚开始发送报文 段时可先将拥塞窗口c w n d 设置为一个最大报文段m s s 的数值。而在每收到一个对新的 报文段的确认后，将拥塞窗口增加至多一个m s s 的数值。用这样的方法逐步增大发送端 的拥塞窗口c w n d ，可以使分组注入到网络中的速率更加合理。慢启动算法为每个连接设 置两个变量：c w n d 和s s t h r e s h ，在一开始，发送端先设置c w n d = l ( 缺省为51 2 或5 3 6 b y t e s ) ， 发送端按c w n d 大小发送数据，每收到一个a c k 确认，c w n d 就增加一个数据包发送量， 这样c w n d 就将随着回路响应时间r t t 呈指数增长，发送端向网络发送的数据量将急剧 增加。事实上，慢启动算法并不是指e w n d 的增长速率慢，但即使c w n d 增长的很快，和 一开始就将c w n d 设置为较大的数值相比，使用慢启动算法可以使发送端在开始发送时 向网络注入的分组数大大减小，对防止网络拥塞是个非常有力的措施。 ( 2 ) 拥塞避免阶段： 如果t c p 连接的发送端发现超时或收到3 个相同的a c k 副本时，即认为网络发生 了拥塞( 主要是因为由传输引起的数据包损坏和丢失的概率很小1 ) 。此时就进入拥塞 避免阶段，慢启动门限设置为当前拥塞窗口大小的一半：如果超时，拥塞窗口被置1 ； 如果c w n d s s t h r e s h ，t c p 就执行拥塞避免算法，此时，c w n d 在每次收到个a c k 时只 增加1 c w n d 个数据包。这样，在一个r t t 内，c w n d 将增加1 ，所以在拥塞避免阶段， c w n d 不是呈指数增长，而是线性增长，无论在慢启动阶段还是在拥塞避免阶段，只要发 送端发现网络出现拥塞，就要将慢启动门限s s t h r e s h 设置为出现拥塞时的发送窗口值的 一半( 但不能小于2 ) 。这样设置的考虑就是：既然出现了网络拥塞，那就要减少向网络 注入的分组数，然后将拥塞窗口c w n d 重新设置为i ，并执行慢启动算法。这样做的目的 就是要迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列 中积压的分组处理完毕。 1 2 硕士论文 基于模型的网络拥塞控制研究 在r e n ot c p 中，慢启动和拥塞避免算法是一起实现的，算法描述如下： 初始化：c w n d = l ； s s t h r e s h = 6 5 5 3 5b y t e s ；( 缺省值) w i n - - m i n ( e w n d ，a w n d ) ； 当新的a c k 确认到达时，执行以下算法： f o re v e r ya r r i v e dp a c k e t s i f ( c w n d s s t h r e s h ) c w n d = c w n d + l ：严s l o ws t a r t * e l s e e w n d = c w n d + m s s 幸m s s c w n d ； * c o n g e s t i o na v o i d a n c e 宰 检测到丢包时，发送端执行下