（控制理论与控制工程专业论文）端到端的internet拥塞控制研究(1).pdf

华中科技大学硕士学位论文 摘要 随着i n t e r n e t 用户和各种各样的网络服务的迅速发展，i n t e r n e t 变得日益繁忙， 流量急剧增加。由于网络资源的瓶颈约束以及i n t e r n e t 的流量突发性，很容易导致网 络产生拥塞现象。特别是i n t e r n e t 上基于t c p 协议地数据流约占据9 0 ，t c p 拥塞 控制对于确保网络的动态性能和稳定性具有十分重要的意义。此外，对于i n t e r n e t 这 样复杂的异构系统中，网络层必须参与资源的控制和分配，在路由器中采用队列调度 算法和缓存管理技术。 本文研究了几种主要的t c p 拥塞控制算法以及主动队列管理策略，并阐述了从经 典控制理论、现代控制理论和非线性不稳定现象的角度研究网络拥塞控制系统稳定性 的一些最新研究方法和研究成果。在前人的研究基础上，本文的工作如下： 1 在分别考虑单源单链路和多源单链路的网络拓扑条件下，采用网络仿真器n s 2 比较了不同版本t c p 协议的数据包丢失率、队列长度变化、不同回路时延的数据流带 宽竞争、不同t c p 协议版本之问的带宽竞争能力。针对t c pv e g a s 协议，改进了回路 时延计算方法，提高了t c pv e g a s 算法的具有更强的抑制瞬间流量扰动能力。并提出 了基于状态空间反馈的t c pv e g a s 算法，将网络层的主动队列管理策略的思想引入 t c p 拥塞控制算法中，使其性能对于队列管理和调度策略的依赖性降低，从而提高了 t c pv e g a s 的稳定性。 2 提出了基于模糊逻辑的主动队列管理策略，以队列长度和及其变化情况作为 输入，通过模糊推理计算出路由器缓冲区的数据包丢失率。仿真表明在通常的拓扑结 构、网络条件和网络连接数量的变化下，该算法具有较好的效果。 3 在前人工作的基础上，以经典控制理论为工具，针对t c pr e n o r e d 的数学 模型，分别考虑采样时间、回路时延、增益等参数变化时，系统的根轨迹变化情况。 本文还从参数变化引起的混沌和分叉现象出发，研究线性和非线性的丢包率函数的性 能比较，通过实验仿真研究不同的控制策略控制分叉和混沌的效果并给出确保系统 稳定性的控制参数取值范围。 4 针对最优化的网络流量控制系统，建立存在时变时滞、时滞相关的连续系统 数学模型，引入l y a p u n o v 函数，提出确保系统全局渐近稳定的条件，并阻孩稳定性 判据具有很小的计算复杂度。当网络中存在大量的t c p 数据流时，即使网络中同时存 在扰动的非响应数据流时，本文的稳定性结论仍然罡有效的。 关键字：英特网，拥塞控制，t c p 协议，主动队列管理，稳定性，非线性 华中科技大学硕士学位论文 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 fa p p l i c a t i o n s ，i n t e m e t t r a f f i ci sb 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 y d u et ot h er e s t r i c t i o no fi n t e r a c 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 t t r a f f i c t h ec u r r e n ti n t e r n e ti sb a s e do nc o n n e c t l e s si pa r c h i t e c t u r e ，w h i c ho n l yp r o v i d e s b e s t e f f o r ts e r v i c ea n dc a n n o tg u a r a n t e et h eq u a l i t y o fs e r v i c e s ( q o s ) t h u sh i g hl a y e r p r o t o c o l ss u c ha st c p a r eu t i l i z e dt og u a r a n t e et h ec o r r e c tt r a n s m i s s i o no fd a t ap a c k e t s 。 e s p e c i a l l yb e c a u s et c pf l o w so c c u p yn e a r l y9 0p e r c e n tt r a f f i co fc u r r e n ti n t e m e t ，t c p c o n g e s t i o nc o n t r o lp l a y s av e r yi m p o r t a n tr o l ei nm a i n t a i n i n gd y n a m i cp e r f o r m a n c eo f i n t e r n e ta sw e l la si t ss t a b i l i t y , r o b u s t n e s 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 。c h a p t e ro n ed e c r i b e s r e c e n tr e s e a r c hp r o g r e s si nt h ea r e ao f i n t e r a c tc o n g e s t i o nc o n t r o la n da n a l y z e ss e v e r a lp r o b l e m se x i s t i n gi nt h i sr e s e a r c ht o p i c 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 pc o n g e s t i o nc o n t r o la l g o r i s m s a n da c t i v eq u e u em a n a g e m e n t ( a q m ) s t r a t e g i e si nd e t a i l ，a n di n t r o d e c e ss o m en o v e l r e s e a r c hm e t h o d sa n dr e s u l t si nt h es t a b i l i t ya n a l y s i so fi n t e r n e tc o n g e s t i o nc o n t r o lw i t ht h e p 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 ，m o d e mc o n t r o ls y s t e ma n dn o n l i n e a ri n s t a b i l i t y p h e n o m e n a o nt h eb a s i so fp r e v i o u sr e s e a r c hw o r k s ，t h es t u d yi nt h i st h e s i si sl i s t e da s f o i i o w s ： 1 a d o p t sn e t w o r ks i m u l a t o r2t os i m u l a t et h ep e r f o r m a n c eo fv a r i o u st c pv e r s i o n s c o n s i d e r i n gb o t hs i n g l es o u r c es i n g l el i n ka n dm u l t i p l es o u r c e ss i n g l el l n k a i m i n ga tt h e i n s t a b i l i t yp h e n o m e n o nf r o ml a r g et r a n s m i s s i o nd e l a ya n db a n d w i d t h ，as t a t ef e e d b a c kt c p v e g a sa l g o r i t h mi sp r o p o s e di no r d e rt oa c h i e v eb e t t e rs t a b i l i t y , w h i c hc o n s u l t st h ea q m i d e ai nt h en e t w o r kr o u t e r a ni m p r o v e dr o u n dt r i pt i m e ( g y r ) c a l c u l a t i o ni nt c pv e g a s i sp r e s e n t e dt oo v e r c o m et h ei n f l u e n c eo fs h o r t - t i m ed i s t u r b i n gt r a f f i ca n dc b r f l o w s 2 p r e s e n t san o v e lf u z z yl o g i cm e t h o df o rc o n g e s t i o nc o n t r o li nt c pn e t w o r k s s t a t e s o fq u e u ea r et r a n s f o r m e di n t ol i n g u i s t i cv a l u e sa n dp a c k e td r o pp r o b a b i l i t yi sd e r i v e df r o m p r e d e f i n e df u z z yi n f e r e n c ee n g i n e s i m u l a t i o nr e s u l t sm a n i f e s ti t se f f e c t i v e n e s s 3 a n a l y z e st h ed y n a m i cc h a r a c t e r so fc u r r e n ti n t e r n e tt r a n s m i s s i o nc o n t r o lp r o t o c o l f r o , ) w i t hr e dg a t e w a yb yc o n c e n t r a t i n go ns i n g l el i n kn e t w o r kt o p o l o g y e x p l a i n st h a t t h er e d a l g o r i s mi ss u s c e p t i b l et ot h ev a r i a t i o no fp a r a m e t e r su s i n gm e t h o do fr o o tl o c u s n 华中科技大学硕士学位论文 o nt h ef o u n d a t i o no fc o n t i n u o u sc o n g e s t i o nc o n t r o lm o d e lb a s e do np r e v i o u sr e s e a r c h i n v e s t i g a t e sn o n l i n e a rb e h a v i o r so ft c pw i t hr e dg a t e w a y ss u c ha sb i f u r c a t i o n ，c h a o s c o n s i d e r i n gb o t hl i n e a ra n dn o n l i n e a rd r o pf u n c t i o n s a n a l y z e sa n dd e d u c e st h es t a b i l i t y c o n d i t i o n so fa d a p t i v er e da n dp r o p o r t i o n a ld e r i v a t i v er e da l g o r i s m sc o n t r o l l i n g b i f u r c a t i o n sa n dc h a o s s i m u l a t i o nr e s u l t se x p l i c i t l yc o m p a r eo u t c o m e so fa b o v et w o a l g o r i s m s 4 i n t r o d u c e sa na p p r o p r i a t el y a p u n o vf u n c t i o na i m i n ga tt h et i m e - d e p e n d e n tm o d e lo f d e t e r m i n i s t i cc o n t i n u o u sf l o wc o n t r o ls y s t e m g l o b a ls t a b i l i t yc o n d i t i o n so ff l o wc o n t r o l s y s t e ma r eb r o u 【g h tf o r w a r d w i t h o u tt i m ed e l a ya n dw i t hb o u n d e dt i m ev a r y i n gd e l a y s ， w h i c hs o l v e st h ed i f f i c u l t yo fp a r a m e t e rc o n f i g u r a t i o no ff l o wc o n t r o l l e ri nt h en e t w o r k t o u t e r sv e r yw e l l t h es t a b i l i t yr e s u l t sa r ea l s oe x t e n d e dt oag e n e r a ln e t w o r kt o p o l o g yi n t h ep r e s e n c eo fm a n yn o n - e l a s t i cf l o w s k e yw o r d s ：i n t e r a c t ，c o n g e s t i o nc o n t r o l ，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 ，a c l i v eq u e u e m a n a g e m e n t ，s t a b i l i t y , a n dn o n l i n e a rs y s t e m i 【 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出 贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明 的法律结果由本人承担。 学位论文作者签名：飧接荐、 日期：h 荜 年堂月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部 本论文属于 不保密口。 ( 请在以上方框内- 打“”) 孥位论文作者签名：棘般寿、 日期：价肇年多月7 白 f 指 日 华中科技大学硕士学位论文 1 绪论 本章首先介绍i n t e r n e t 的历史与现状概述，然后分别介绍网络拥塞现象及其产生 的本质原因与i n t e r n e t 拥塞控制的研究进展，通过从不同的角度探讨网络拥塞控制中 存在的问题和困难，指出本文的主要工作和论文的组织结构。 1 1i n t e r n e t 历史与现状概述 i n t e r a c t 的历史可以追溯到上个世纪6 0 年代的一个广域网计划。美国国防部的高 级研究计划署( a d v a n c e dr e s e a r c hp r o j e c ta g e n c y ，a r p a ) 为了能使一些异地计算机 相互共享数据，以利其开展研究工作，于是以一定的方式将这些计算机连接起来，实 现具有分散控制能力的数据传输网络，这就形成了i n t e m e t 的前身a r p a n e t 。a p p a n e t 的主要特点是实现了资源共享、分散控制、分组交换和分层的网络协议，这些特点被 认为是现代计算机网络的重要特征。a r p a n e t 成功的主要原因是因为它使用了传输控 制协议，网际协议( t c 聊p ) 标准网络协议。t c p f l p 是由a r p a 于1 9 7 7 年到1 9 7 9 年 推出的一种网络体系结构和协议规范。伴随着a r p a n e t 的成功，美国的国家科学基金 会n s f 也于1 9 8 6 年用t c p f i p 协议建立了n s f n e t ，使之与a r p a n e t 融合，并于1 9 8 9 年改名为i n t e r a c t 向公众开放。随着应用需求的增加以及t c p i p 技术研究的发展， i n t e m e t 的规模也越来越大。尤其是w w w 出现以来，i n t e r a c t 的网络规模、用户数量 以及业务量呈现爆炸式的增长。1 9 9 3 年9 月1 5 日，美国政府发布了具有世界性影响 的文件“国家信息基础结构( n i i ) 行动计划”，指出高速信息网是国家的信息基础结 构的重要组成部分。1 9 9 4 年美国又提出建立“全球信息基础结构( g i o ”，建议将各国 的n i l 互连起来组成世界范围内的信息基础结构，这也就是当前飞速发展的i n t e m e t 的雏形。同年美国的i n t e r a c t 由商业机构全面接管，使得i n t e m e t 从单纯的科研网络演 变成一个世界性的商业网络，从而加速了i n t e r a c t 的普及和发展，而且i n t e r n e t 商业化 的成功造就了2 0 世纪末以来的新经济潮流。 1 2 网络中的拥塞现象 计算机网络中的链路容量、网络节点中的缓存和处理器等都是网络的资源，在某 段时间内如果用户提供给网络的负载大于网络资源容量和网络节点的处理能力，网络 的便会产生阻塞，性能变坏，这就是网络拥塞( c o n g e s t i o n ) 现象。可以表示为如下 华中科技大学硕士学位论文 公式： v 资源需求 网络可用资源 网络产生拥塞时，网络的性能便会降低，具体表现在网络吞吐量和效率的降低、 路由器缓冲队列的急剧增加、报文时延的增加、报文的丢失、报文到达的时延抖动剧 烈等。拥塞一旦发生，如果没有有效的拥塞控制机制，拥塞会继续加重，最终导致网 络崩溃。例如在1 9 8 6 年1 0 月，由于拥塞崩溃的发生，美国l a w r e n c en a t i o n a ll a b o r a t o r y 至0 u n i v e r s i t yo f c a l i f o r n i a ，b e r k e l e y 的数据吞吐量从3 2k b p s 跌落n 4 0b p s 【1 】。在那之后， 在拥塞控制领域开展了大量的研究工作。 避教撼包赣量 图1 - 1 网络流量与效率的关系 图卜1 通常用来描述稳定状态通过网络的总和输入负载的函数关系，其中的吞吐 量和网络负载都作了归一化的处理。当负载较小时，吞吐量的增长和负载相比基本呈 线性关系：在网络负载超过最大负载能力之后，理想状态的吞吐量维持在网络的最大 吞吐量。理想情况是假定网络节点缓存无限大，并且与分组传输和拥塞控制相关的开 销也忽略不计。在一个缓存空间有限的网络中，当负载较轻时网络吞吐量以及利用 率随着输入负载的增加而增加。当到达某个临界值时，网络吞吐量和利用率的增长率 随着输入负载的增长而减慢，进入中等拥塞的状态，传输时延增加，并产生分组的丢 失。当网络上的负载继续增加时，各个节点的缓冲队列长度也不断增加，从而造成分 组的丢失和不必要的超时重传，整个网络逐渐变得饱和，吞吐量和利用率也不断减小， 甚至导致死锁，网络的有效吞吐量降低为零。 1 _ 3 网络拥塞产生的原因 网络产生拥塞的根本原因在于用户提供给网络的负载大于网络资源容量和处理 能力。文献【2 扮析了拥塞产生的直接原因，主要表现在三点： a ) 路由器存储空问不足：几个输入数据流共同通过同一个链路，如果流入速率之 醉特锶蔓 华中科技大学硕士学位论文 和大于流出速率，在这个缓冲区就会建立队列。如果没有足够的存储空间，数据包就 会被丢弃。单纯增加路由器缓冲存储空间并不能解决这个矛盾。 b ) 带宽容量相对不足：网络低速链路容易形成带宽瓶颈，从而造成网络拥塞现象。 c ) 处理器处理能力弱、速度慢：如果路由器的c p u 在执行排队缓存、更新路由 表等操作时，处理速度跟不上高速链路，也会产生拥塞。 1 4i n t e r n e t 拥塞控制的研究进展 随着网络用户和各种网络服务的飞速发展，i n t e r n e t 变得日益繁忙，通信业务量 的迅猛增长使得主干网络变得越来越拥塞。与此同时，各种各样的新型业务如视频服 务、语音服务等，对于网络的服务质量( q o s ) 提出了更高的要求。由于i n t c r n c t 中 9 0 左右的数据流使用t c p i p 协议，因而t c p i p 的拥塞控制机制是确保i n t e r n e t 的 稳定性和鲁棒性等方面的关键，也是i n t e r n e t 得到广泛应用的重要保证。 早期t c p 3 的实现只是使用累计确认、超时重传和后退n ( 源端检测到拥塞时， 重传从丢失数据包开始一直到检测到丢包时所发送的全部数据包) 等机制，而没有拥 塞控制。接收端利用t c p 报头将接收能力通知发送端，这样的控制机制只考虑了接 收端的接收能力，而没有考虑网络的传输能力。拥塞控制的研究开始于8 0 年代中期， 1 9 8 4 年，n a g l e 首次指出了复杂t c p i p 网络中存在的拥塞问题，特别是在由路由器 连接的带宽差异较大的网络中，容易发生“拥塞崩溃”( c o n g e s t i o nc o l l a p s e ) 现象。1 9 8 8 年，v a nj a c o b s o n 在著名的论文【1 忡指出了t c p 协议在拥塞控制上的不足，并提出“慢 启动”、“拥塞避免”和“快速重传”算法，并于1 9 9 0 年提出了“快速恢复”算法， 奠定了拥塞控制研究的基础。从8 0 年代至今，许多学者进行了更深入和细致的研究， 不断完善和改进t c p 拥塞控制存在的缺陷，相继提出5 个版本的t c p 拥塞控制算法： t a h o e 1 ，r e n o 4 , n e wr e n o 5 , s a c k 6 ，v e g a s 7 。 但是随着i n t e r n e t 技术的发展和网络条件的变化，仅仅依靠t c p 拥塞控制机制是 不能够确保q o s 的，此外，对于i n t e r n e t 这样复杂的异构系统中，网络层必须参与资 源的控制和分配，在路由器中采用队列调度算法和缓存管理技术，即i p 拥塞控制策 略。当路由器处理能力不足时，队列管理算法对来不及处理的数据包进行丢弃或者标 记，源端对数据包的丢失或者标记事件做出响应。而调度算法直接管理输出链路的带 宽资源。现有的这些路由器扩展功能，并没有与i n t e r n e t 将流状态信息保存在主机端 的早期设计理念相冲突嗍。传统的路由器缓冲管理“弃尾( d r o pt a i l ) ”策略，报 文到达时，如果缓冲队列已满，路由器则丢弃该报文。但是弃尾算法很容易产成持续 华中科技大学硕士学位论文 的满队列状态，甚至导致业务流对缓存的死锁和业务流的全局同步。 f l o y d 于1 9 9 3 年提出著名的随机早期拥塞r e d ( r a n d o me a r l yd e t e c t i o n ) 【8 】控制策略，有效的改 进了网络路由器常用的“弃尾”算法的缺陷。此后，许多学者进行深入的研究，提出 一系列新的主动队列管理策略( a q m ，a c t i v eq u e u em a n a g e m e n t ) 如比例比例积分 f p p 0 9 、s t a t ef e e d b a c k 1 0 、s m v s 1 1 、r e m 1 2 、a v q 1 3 、b l u e t l 4 等，用来 改善网络拥塞控制的效果，提高网络流量的公平性以及拥塞控制系统的稳定性和鲁棒 性。 调度规则决定数据分组接受服务的次序，传统的路由器采用“先来先服务” ( f c f s ) 的调度算法，但是它按照占用队列的多少分配带宽，无法实现公平性。f 1 5 1 提出了g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 的分组调度策略，数据分组位于不同的逻辑 队列，在有限的时间间隔，每一个非空队列都有机会接受服务。至少一次如果为队列 赋予一定的权值，接受的服务与权值成比例，那么g p s 便可以实现最大最f j , l t 例公平 性。g p s 策略的一些简单和近似的实现算法有轮询( r o u n dr o b i n ) ，加权公平排队 ( w e i g h t e df a i rq u e u i n g ) 【1 6 1 ，最劣情况w f q ( w o r s t c a s ew f q ) 【1 7 ，自时钟同步 公平排队( s e l f - c l o c k e df a i rq u e u i n g ) 【1 8 】等。此外，【1 9 】还指出网络中数据流的争夺 资源的自私本质，基于博弈论提出降权调度策略( d i m i n i s h i n gw e i g h ts c h e d u l e r ) ，惩 罚贪婪的数据流，并奖励具有良好行为的网络数据流。 从控制论角度出发拥塞控制可以分为开环控制和闭环控制。开环控制是预先设 计一个好的网络，确保它不会发生拥塞，而网络在运行过程中不再采取措施。比较典 型的例子就是资源预留协议( r s v p ) ，这类控制机制较适用于简单的音频和活动图像 业务。但是网络的业务流量通常时很难精确确定的，需要预蜜更多的网络资源，造成 网络资源利用率的低下，因而开环控制对于复杂的网络系统来说是远远不够的。闭环 控制能够根据网络中反馈至端系统的拥塞指示信息，依据一定的控制策略，及时调整 源端系统的数据传输速率，避免网络状况的恶化，既保证了传输的质量又能充分利用 网络资源。 对于一个控制系统来说，首要的性能指标是该系统是否具有良好的稳定性。近年 来，许多文献 2 0 - - 3 2 分别建立网络流量的随机模型和决定性模型，采用经典控制理论 和现代控制理论研究网络拥塞控制系统的稳定性和动态特性，针对不同的网络情况， 依据线性和非线性控制理论，提出确保网络拥塞控制系统的稳定性判据。3 3 3 7 1 更深 入研究网络拥塞中的非线性现象，如流量的自相似特性，混沌和分叉以及相变等。 上个世纪9 0 年代中期，视频组播数据流和可靠组播数据流的拥塞控制引起广泛 的关注。主要的思想就是引入流量速率控制机制，采用类似于t c p 的a i m d 算法对 4 华中科技大学硕士学位论文 流量进行调控，选择不同的a i m d 参数保证速率的稳定性。此外，尽可能使得设计拥 塞控制机制具有良好的可扩展性。【3 8 】提出以t c p 稳态速率为基础的速率控制思想， 清晰的阐明了t c p - - f r i e n d l y 的拥塞控制算法，保证下一代i n t e r n e t 中网络资源使用的 公平性。针对网络流量存在的不公平性，许多研究基于区分服务( d i f f s e r v ) 的体系结构， 在网络层解决流量的公平性问题。 1 5i n t e r n e t 拥塞控制研究中存在的问题 由网络拥塞产生的原因可知，虽然拥塞源于资源短缺，但单方面增加资源并不能 避免拥塞的发生，有时甚至会加重拥塞程度。例如：增加网关缓冲会增大报文通过网 关的延迟，当数据包经过长时间的排队完成转发时，它们早己超时，而源端认为这些 数据包已经被丢弃，重传这些数据包，但是它们仍在网络中传输，因而浪费网络资源， 加重网络拥塞。又如，处理机的处理速率太慢固然容易导致网络拥塞，单纯提高该处 理器的性能，网络的瓶颈又会转移到其他地方，导致整个系统各个部分的不匹配。总 而言之，拥塞控制算法的设计困难体现在以下几方面： ( 1 ) 算法的分布性：拥塞控制算法的实现分布不同的网络层次中，以及在多个网 络节点中。采用分布式的拥塞控制算法可以降低单个节点的处理复杂度和提高网络的 稳健性。 ( 2 ) 算法的可扩展性：i n t e m e t 中各处的网络性能有很大的差异，对于不同的网络 条件，如网络的规模变化，带宽的变化，链路传输时延的变化，不同的端系统状况， 以及存在多种数据流时，拥塞控制算法都应该具有相对较好的性能指标。 ( 3 ) 算法的性能要求【3 9 】：拥塞控制算法对性能有很高的要求，包括算法的公平性、 效率、稳定性、鲁棒性和收敛性。通常的拥塞控制策略只能达到部分的性能要求，需 要考虑这些性能指标的折衷。 ( 4 ) 算法的易实现性【3 9 】：设计的拥塞控制算法的实现要尽可能简单，不仅要尽量 减少附加的网络流量，而且要减少反馈信号的复杂度。同时拥塞控制算法的设计还必 须尽可能降低该算法在网络节点的计算量和实现的复杂度。 ( 5 ) 拥塞的复杂性：计算机网络已经发展成为一个庞大的复杂性系统，其复杂性 在于网络拓扑结构的复杂性，网络数据流的复杂性如自相似，自组织临界和拥塞相变 现象等。采用复杂性研究相关的一些理论和方法去研究网络拥塞等演化规律的网络动 力学已经发展成为新的跨学科领域。 华中科技大学硕士学位论文 1 6 本文的工作 本文针对i n t e r n e t 中的t c p i p 协议拥塞控制机制进行了深入的研究，通过实验仿 真详细研究前人提出的几种主要的t c p i p 拥塞控制策略，并分别从经典控制理论、 最优化理论、现代控制理论以及非线性理论的角度深入探讨网络拥塞现象，对于t c p 协议拥塞控制机制进行改进，提出新的基于模糊逻辑的主动队列管理机制，在最优化 理论的基础上，提出确保其在时滞不确定的时延情况下的网络流量控制系统的全局渐 近稳定的条件，最后结合非线性动力学的相关理论，通过实验仿真研究t c p i p 网络 拥塞控制策略的混沌与分叉现象。 1 7 论文组织 第二章：介绍几种t c p 拥塞控制策略，并通过实验仿真比较他们的性能差异，并 提出状态反馈的t c pv e g a s 拥塞控制算法和指数平均滑动的t c pv e g a s 时延计算方 法。 第三章：介绍近年来路由器主动队列管理算法的研究进展，通过实验仿真研究各 种主动队列管理策略的性能差异，并提出基于模糊逻辑的主动队列管理算法。 第四章：以t c pr e n o 协议为例，以经典控制理论和李雅普洛夫稳定性定理为工 具，深入研究t c p a q m 的频域特性，在最优化理论的基础上，提出确保其在时滞不 确定的时延情况下的全局渐近稳定的条件，依据网络离散动态模型的非线性动力学特 性，研究参数变化产生的混沌和分叉现象以及如何控制网络拥塞的混沌现象。 第五章：总结本文的工作，并展望未来的研究方向。 华中科技大学硕士学位论文 2t c p 拥塞控制策略及其改进 早期互联网的流量控$ 1 j 3 1 比较简单，采用了链路层的滑动窗口算法进行端到端的 流量控制，当网络发生拥塞的时候，源端的发送窗口并不减少，数据包的到达速率持 续大于网络的传输能力，导致路由器缓冲区队列增长，回路时延( r o u n dt r i pt i m e ) 增 大；如果超时，端系统还不断重传未确认而已成功到达对端的数据包，这更迸一步加 重了网络的拥塞，导致网络性能严重下降，以至可能造成拥塞崩溃( c o n g e s t i o n c o l l a p s e ) 。v a nj a c o b s o n 【l 】提出了基于t c p 的拥塞控制机制，它把数据包的丢失作为 网络拥塞的信号，通过减少发送窗口，降低发送速度，避免进一步的拥塞。这种基于 源端的拥塞控制具有高效、简单、比较公平的特点，成为互联网得到广泛应用的重要 保证。本章首先简单介绍了i n t e r n e t 中t c p 协议族体系，详述了几种不同的t c p 拥塞 控制机制，并通过仿真实验对它们的性能进行了分析比较，最后提出本文的改进算法。 2 1t c p i p 协议体系简介 t c p i p 起源于6 0 年代末美国政府资助的一个分组交换网络研究项目，到9 0 年代已 发展成为计算机之间最常应用的组网形式。t c p i p 是一个真正的开放系统，是因特网 ( i n t e m e t ) l 拘基础，通常被认为是一个四层协议系统1 4 0 1 。 1 ) 链路层通常包括操作系统中的设备驱动程序和计算机 中对应的网络接口卡等。 2 1 网络层处理分组在网络中的活动，例如分组的选路等。 在t c p i p 协议族中，网络层协议包括i p 协议，i c m p 协议， 以及i g m p 协议。 3 1 运输层主要为两台主机上的应用程序提供端到端的通 信。在t c p i p 协议族中，有两个互不相同的传输协议： 庸用层 传输层 网络层 链路层 图2 - 1t c p i p 协议体系 t c p ( 传输控制协议) 和u d p ( 用户数据报协议) 。t c p 协议是面向连接的，为两 台主机提供高可靠性的数据通信。而u d p 协议则是面向无连接的，它为应用层提 供一种非常简单的服务，任何必需的可靠性必须由应用层来提供。 4 ) 应用层负责处理特定的应用程序。女n t e l n e t ，f 1 p ，s n m p ，s m t p ，h 1 t r p 等。 华中科技大学硕士学位论文 2 2 几种主要的t c p 拥塞控制算法 早期t c p 的实现只考虑网络的流量控制，而没有拥塞控制。拥塞控制的研究开始 于1 9 8 4 年，n a g l e 首次指出了复杂t c p i p 网络中存在的拥塞问题。1 9 8 8 年，v a n j a c o b s o n 在著名的论文 1 l b b 指出了t c p 协议在拥塞控制上的不足，并提出“慢启动”、 “拥塞避免”和“快速重传”算法，并于1 9 9 0 年提出了“快速恢复”算法，奠定了 拥塞控制研究的基础。t c p 拥塞控制是一种自适应、分布式的控制系统，能够对网络 拥塞在一定程度上作出及时、有效的响应。t c p 拥塞控制采用的是基于窗口的端到端 的闭环控制方式，主要思想在于对于每个数据源决定分配多大可利用的带宽资源，根 据应答信号了解多少报文被安全传送或传输时延的变化判断拥塞的发生。从8 0 年代 至今，许多学者进行了更深入和细致的研究，不断完善和改进t c p 拥塞控制存在的缺 陷，相继提出5 个版本的t c p 拥塞控制算法：t a h o e 1 ，r e n o 4 ，n e w r e n o 5 ，s a c k 6 ， v e g a s 7 。 2 2 1t c pt a h o e 算法 v a nj a c o b s o n 【l 】提出了新算法用于t c p 的拥塞控制，其中有著名的慢启动( s l o w s t a r t ) 、快速重传( f a s tr e t r a n s m i 0 和拥塞避免( c o n g e s t i o na v o i d a n c e ) 。t c p 拥塞控制是 基于窗口的端到端的闭环控制，其核心思想是每个数据源探测链路中的可用带宽大 小，并根据此带宽大小发送可能安全到达的数据包。其算法如下f 4 1 1 缓慢启动t c p 发送端首先进入慢启动阶段，设嗣拥塞窗口大小为一个或两个数 据报的大小，并设置滑动窗口的慢启动上限值s s t h r e s h 。当收到一个对新报文的确认 消息，增大拥塞窗口长度加1 。在缓慢启动阶段，t c p 源端的发送速率是呈指数增长 趋势，这样可以快速地使传输速率达到与网络资源相适应的程度。 拥塞避免在慢启动阶段，当拥塞窗n ( c 、】v n d ) 超过滑动窗口的上限s s t h r e s h ，就进 入拥塞避免阶段，此时只有接收到拥塞窗口中的所有报文的应答信号时，拥塞窗口才 增加一个数据包的大小。当发生数据包丢失时，将拥塞窗1 2 长度减半，并设置慢启动 上限值s s t h r e s h 为当前拥塞窗口( c w n d ) 的一半，并进入快速恢复阶段。在拥塞避免阶 段，又称为和式增加积式减少阶段，在每个r t t 中，如果成功接收到c w n d 个麻答信 号，发送速率呈线性增加，如果发生数据包丢失，源端的发送速率减半，从丽有效的 避免拥塞现象的发生。 快速重传当t c p 源端一连串地收到3 个重复的a c k 信号时，很可能是一个报 文段丢失，就立即重传该数据包，并将拥塞窗口减半，而不必等待重传定时器超时， 华中科技大学硕士学位论文 避免了不必要的重传定时器超时，提高了网络的吞吐量。 2 2 2 t c p r e n o 算法 t c pt a h e o 1 在收到三个重复的确认消息，拥塞窗口减半，导致传输速率剧减， 网络流量出现较大波动，对于多个包丢失的情况，还可能导致重传已成功的数据报。 v a nj a c o b s o n 还提出了快速恢复( f a s t r e c o v e r y ) 【4 2 】的算法，改善了多个包丢失时拥塞 控制算法的性能 4 1 1 。 快速恢复当t c p 收到三个重复的确认消息后，设置慢启动的上限值s s t h r e s h o l d 为当前拥塞窗n ( c w n d ) 的一半，设置当前拥塞窗口为s s t h r e s h o l d + 3 ，以后每次收到另 一个重复的a c k 时，c w n d 增加1 个报文段大小并发送一个1 个分组，直到收到新的 确认消息，设置c w n d 为s s t h r e s h ，才退出快速恢复，进入拥塞避免状态。 与t a h o e 的慢启动不同，r e n o 的发送方用额外到达的应答来为后续包定时。发送 方的可用窗i = 1 变为m i n ( a w i n ，c w n d + n + d u p ) ，这里a w i n 是接收方的通知窗口，c w n d 是发送方的拥塞窗口，n * d u p 保持零值( 在重复的应答的数目达到门限值之前) ，因而 在快速恢复中，发送方根据收到的重复应答的数量来改变自己的窗口。相应地，每个 重复应答表示有一些数据包已被移出网络并且现在已经安全到达接收方。在进入快速 恢复并重传一个包之后，发送方就开始等待，直到一半窗口大小的重复应答被收到时， 然后对应每个额外重复的应答传出一个新包，当接收到新数据的应答时，发送方退出 快速恢复并设置n * d u p = 0 【4 4 】。 由于在快速恢复期间，传输当前窗口后的数据报，避免了重复的数据重传此外， 由于退出快速恢复后，不需进入慢启动，避免了网络流量的较大震荡，提高了t c p 协议的传输速度，这种采用快速恢复算法的t c p 协议被称为t c pr e n o ，是当前最为 广泛采用的t c p 实现版本。形象的算法描述如下： 当一个新数据包得到确认时： ( c w n d r w d )c w n d - c w n d + 1 ； s l o ws t a r tp h a s e e l s e c w n d - c w n d + i c w n d ； c o n g e s t i o na v o i d a n c ep h a s e 源端接收到的重复a c r 3 叠过一定闽值时： t w n d t w n d 2 ； c w n d t w n df a s tr e c o v e r yp h a s e 如果传输超时： t w n d = t w n d 2 ； c w n d = 1 有效l l = m i n 们w a r d ，c w n d ) a w n d ，c w d ，t w n d 分别表示通知窗口，拥塞窗口，缓慢启动阀值。 华中科技大学硕士学位论文 图2 - 2 慢启动和拥塞避免