（计算机应用技术专业论文）自适应拥塞控制协议pi速率控制器的实现与实验研究.pdf

摘要 在过去的二十多年里，i n t e m e t 得到迅猛的发展，大量的网络商务应用、多 媒体应用应运而生。随着网络流量的大幅增长，网络拥塞日益严重，但是对于这 个问题，至今还没有一个完美解决方案。 t c p 所采用的拥塞控制算法控制不够平稳。由于协议自身局限性，t c p 协 议不适用于高时延环境，不能有效利用链路带宽。针对现有问题，根据现代控制 理论提出的自适应比例积分( p i ) 速率控制协议，通过在中间结点引入拥塞控制 器，可达到较高的链路利用率，较低的排队时延，较小的丢包率和极好的公平性。 本文针对p i 速率控制协议机制进行了详细的理论分析；并在控制系统模型 的指导下，根据理论公式，使用严格的数学理论进行化简，得出较为简洁高效的 表达式，以切合实际编程使用；同时，本文分析了在l i n u x 内核下实现该协议所 需要解决的关键问题，如：选择何种内核版本，如何进行模块化实现，协议栈层 次设计，如何实现内核浮点数计算，如何选择控制时机等，并给出了解决方案， 同时将该协议与x c p 协议进行了比较。随后，本文给出了在搭建实验床过程中 若干问题的解决方案，并设计实验场景，以便研究真实环境下p i 速率控制器的 性能以及存在的问题。实验结果表明该协议控制准确有效，具有较高的带宽利用 率，良好的稳定性、公平性、收敛性和鲁棒性。 最后本文指出了该协议下一步改进的方向。 关键词：拥塞控制自适应p i 控制器 a b s t r a c t i nt h ep a s tt w e n t yy e a r s ，i n t e m e th a sd e v e l o p e dw i t hf a s ts p e e d ，a n dag r e a t v a r i e t yo fa p p l i c a t i o n su p o nt h ei n t e r a c t ，l i k ee l e c t r o n i cb u s i n e s sa n dn e t w o r k m u l t i m e d i a , e m e r g ea st h et i m e sr e q u i r e w i t ht h ei n c r e a s i n gt r a f f i co fn e t w o r k , c o n g e s t i o nc o n t r o lt u r n so u tt ob et h em o s ti m p o r t a n ti s s u ei nt h er e s e a r c ho fn e t w o r k n ee x i s t e dc o n g e s t i o nc o n t r o la l g o r i t h m sa r ea b l et oa l l e v i a t ec o n g e s t i o nt os o m e a s p e c t ，b u ts t i l lt h e r e sn op e r f e c ts o l u t i o n t h ec o n g e s t i o nc o n t r o la l g o r i t h mt h a tt c pa d o p t si sn o ts m o o t he n o u g h a n d m o r e o v e r , b e c a u s eo fi t si n h e r e n tl i m i t a t i o n ，t c pi sn o ts u i t a b l ef o rn e t w o r kw i t hh i g h d e l a y , s i n c ei tc o u l dn o tm a k ef u l lu s eo ft h eb a n d w i d t h i no r d e rt os o l v et h e s e p r o b l e m s ，s e l f - t u n ep r o p o r t i o n a l i n t e g r a lr a t ec o n t r o lp r o t o c o l ( p ip r o t o c 0 1 ) i s p r o p o s e da c c o r d i n gt ot h em o d e mc o n t r o lt h e o r yt oa c h i e v eh i g hl i n ku t i l i z a t i o n ，l o w q u e u i n gd e l a y , s m a l lp a c k e t s l o s s r a t ea n de x c e l l e n tf a i m e s sb y i n t r o d u c i n g c o n g e s t i o nc o n t r o l l e rt oi n t e r m e d i a t en o d e s 。 i n 饿i sp a p e r , w eh a v el o o k e di n t ot h et h e o r yb e h i n dt h ed e v e l o p m e n to fp i p r o t o c o l ，a n dg u i d e db ys y s t e mc o n t r o lm o d e la n dt h e o r e t i cf o r m u l a s ，w es i m p l i f i e d t h ee x p r e s s i o n sf o l l o w i n gs t r i c tm a t h e m a t i c a lt h e o r y , s om a tt h e yw o u l db ef i t t i n gf o r t h e u s eo fp r o g r a m m i n g w ea l s oa n a l y z e do t h e ri m p o r t a n ti s s u e st h a tn e e dt os o l v e b e f o r ew ec o u l di m p l e m e n tt h ep r o t o c o li nl i n u xk e r n e l ，l i k eh o wt oc h o o s ek e r n e l v e r s i o n ，h o wt om a k eu s eo fk e r n e lm o d u l e ，h o wt od e s i g np r o t o c o ls t a c kl a y e r , h o w t os o l v ef l o a t i n gp o i n tc a l c u l a t i o np r o b l e mi nt h ek e r n e l ，h o wt od e c i d et h ec o n t r o l l i n g t i m ea n ds oo n a l s o ，w ec o m p a r e dp ip r o t o c o lw i t hx c p p r o t o c 0 1 t h e n ，w eb u i l t 叩 at e s tb e da f t e rs o l v i n gt h ep r o b l e m s ，a n dd e s i g n e das p e c i f i ce x p e r i m e n t a ls c e n a r i ot o t e s tt h ep e r f o r m a n c eo ft h ep r o t o c o la n dt of i n da n yp r o b l e m st h a te x i s t 1 1 1 er e s u l t s s h o w e dt h a tc o n t r o l l i n gp r o c e s so fp ip r o t o c o lw a sa c c u r a t ea n de f f i c i e n t ，w i t hh i g h b a n d w i d t hu t i l i z a t i o na n dp r e f e r a b l es t a b i l i t y , f a i r n e s s ，c o n v e r g e n c ea n dr o b u s t n e s s a tt h el a s tp a r to ft h i sp a p e rw ep o i n to u tt h ed i r e c t i o nf o ri m p r o v i n gt h ep i p r o t o c 0 1 k e y w o r d s ：c o n g e s t i o nc o n t r o l ，s e l f - t u n e ，p ic o n t r o l l e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：别垮彩签字日期：沙刁 年石月乡日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：剐号甜 导师签名： 走幻 签字日期：岬年多月，歹日签字日期：砷年f 月肜日 第一章绪论 第一章绪论 本章介绍了i n t e m e t 发展趋势及设计机制，对目前网络中所存在的拥塞问题 进行了描述，并定义了拥塞控制这一概念，分析了拥塞产生的原因，从而总结了 拥塞控制策略研究的意义及其目的所在。在此基础上，给出了论文的研究内容和 总体结构。 1 1 本文的研究背景 近年来，网络技术的发展日新月异，网络规模迅速扩大，特别是进入九十年 代后，i n t e m e t 呈爆炸式增长，己经逐渐发展成为全球性的信息基础设施【2 1 。 随着新型网络应用的不断涌现和用户数量的迅速增加，i n t e m e t 的流量急剧 增长，其中除了传统的w w w ，f t p ，t e l n e t 等数据流外，还出现了大量的实时 多媒体数据流。网络中不同的数据流在路由器处交汇，给路由节点造成很大的负 担，越来越严重的网络拥塞问题逐渐暴露出来。 在网络通信中，拥塞容易造成延迟和吞吐量等q o s ( q u a l i t yo fs e r v i c e ) 性 能指标下降，是影响带宽、缓存等网络资源利用率的关键因素，因此有效解决拥 塞问题对于提高网络性能具有重要意义。 网络中的拥塞【3 】来源于网络资源和网络流量分布的不均衡性，拥塞不会随着 网络处理能力的提高而消除。所以，拥塞控制算法是尽量避免拥塞以及在拥塞发 生时进行有效控制并加以消除的重要手段，它对保证i n t e r n e t 的稳定起着至关重 要的作用。 多年来，人们已经对拥塞控制进行了大量研究，提出或改进了多种多样的拥 塞控制算法，版本不少于2 0 0 多种。这一方面表明拥塞控制是网络研究领域的一 个热点问题；另一方面也说明由于拥塞控制算法的分布性、网络的复杂性和对拥 塞控制算法的性能要求，拥塞控制算法设计具有很高的难度。到目前为止，拥塞 问题还没有得到很好的解决。 1 2 拥塞控制的概念及意义 网络中的链路容量( 即带宽) 、交换节点中的缓存和处理器等都是网络资源。 第一章绪论 在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网 络的性能就要变坏，这种情况叫做拥塞1 3 圳。可以用如下关系式表示： 对资源的需求 可用资源 拥塞导致的直接结果是分组丢失率提高，端到端时延增大，甚至有可能使整 个系统发生崩溃。当网络处于拥塞崩溃状态时，网络运行在c l i f f 附近，如图1 1 ， 微小的负载增量都将使网络的有效吞吐量急剧下降。 拥塞控制就是指通过积极的措施来避免拥塞的发生或者在拥塞发生以后能 尽快恢复到平稳状态。拥塞控制算法实际上包含拥塞避免( c o n g e s t i o na v o i d a n c e ， c a ) 和拥塞控制( c o n g e s t i o nc o n t r o l ，c c ) 两种不同的机制。前者是一种“预防” 措施，使网络运行在k n e e 附近，维持网络的高吞吐量、低延时状态，避免拥塞 的发生；后者是一种“恢复措施，保持网络运行在c l i f f 的左侧区域，使网络 从拥塞中恢复过来，进入正常的运行状态。 翟 = d 们 g 舞 蛊 趾e e c 11f f 。 图1 - 1 网络负载与吞吐量及响应时间之间的关系1 1 】 网络中的拥塞是不可避免的，这是因为为了提高链路的利用效率，网络传输 采用分组交换，这样路由器的缓存中经常用于存储等待转发的数据包。如果路由 器缓存中总是只存放少量数据包或者空闲，虽然传输时延低，但是网络的利用效 率也低；如果路由器缓存总是满负载存储，则传输时延高，但是网络利用效率也 高。因此，拥塞控制的研究目的不是要完全避免拥塞，而是研究怎样的拥塞程度 是合适的。 通过网络的拥塞控制，可以提高网络的总体性能，保证网络长期的稳定性和 鲁棒性。 1 3 本文所做的工作 本文研究了基于现代控制理论的，具有自适应性的网络拥塞控制算法，以期 提高网络传输过程中的带宽利用率，更好的解决日益严重的网络拥塞问题。 从理论上讲本课题的意义在于，它不再是单纯依赖于主观猜想提出的算法， 2 p，量jo主卜 第一章绪论 不再采用由猜测到模拟的分析方法，而是以成熟的控制理论为基础，以期达到更 稳定更合理的控制。 应用上讲本课题的意义在于，如果该算法能够达到预期的效果，将可能应用 于未来网络拥塞控制中，提高网络的利用率，给网络的使用者带来极大的便利。 1 4 论文结构 本文第一章给出了对自适应拥塞控制协议p i 速率控制器的实现与实验研究 的背景和意义。 第二章介绍了网络拥塞概念及其产生的原因，并介绍了目前相关的理论与技 术基础，深入讨论了控制网络拥塞有效手段及其分类。 第三章分析了自适应式p i 速率控制算法的整体框架，并对该算法与已有网 络拥塞控制算法进行了比较分析。给出了在l i n u x 内核下实现该算法所需要解决 的关键问题，如：选择何种内核版本，如何进行模块化实现，协议栈层次设计， 如何进行内核浮点数计算，如何选择控制时机等。 笫四章利用实验室现有资源搭建了实验床。 第五章在真实环境下对p i 速率控制器的性能进行测试，并就实验中出现的 现象及其成因进行了分析。 第六章对p i 速率控制器的进一步研究和改进提出一些建议和意见，最后指 出今后研究中需要解决的一些问题。 第二章拥塞控制理论与研究现状 第二章拥塞控制理论与研究现状 在i n t e m e t 中，路由器的处理速度、通信信道及缓存空间通常既是网络中所 有主机共享的资源，也是网络系统潜在的瓶颈。随着网络中主机数和数据业务量 的不断增加，瓶颈处就会发生资源竞争，从而导致网络拥塞。网络拥塞控制的基 本思想是在共享资源管理的基础上，按一定的算法控制发送端的数据发送量，合 理使用网络资源，保证网络的稳定性。 2 1 拥塞控制理论 拥塞发生时，网络中存在过多的数据包，网络的性能急剧下降，网络吞吐量 ( t h r o u g h p u t ) 下降，拥塞过于严重会导致“拥塞崩溃”( c o n g e s t i o nc o l l a p s e ) 现 象发生，此时，微小的负载增量都会使网络的吞吐量急剧下降。1 9 8 4 年，n a g e l 【3 】报告了由于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 ) 连接中不必要的重传所诱发 的拥塞崩溃。1 9 8 6 到1 9 8 7 年问，这种现象曾多次发生，严重时一度使l b l 到 u cb e r k e l e y 之间的数据吞吐量从3 2 k b p s 跌落到4 0 b p s 6 。 2 1 1 互联网网络模型 网络拥塞问题的出现，与i n t e m e t 网络模型本身的特点密切相关。因此，分 析i n t e m e t 的特点对研究拥塞控制算法大有裨益。i n t e r n e t 网络模型【7 j 可以用以下 几点来简单概括： 1 、分组交换网络：分组交换也称包交换，它是将用户传送的数据划分成一 定的长度，每个部分叫做一个分组。在每个分组的前面加上一个分组头，用以指 明该分组发往何地址，然后由交换机根据每个分组的地址标志，将它们转发至目 的地，到达接收端，再去掉分组头将各数据字段按顺序重新装配成完整的报文， 这一过程称为分组交换。进行分组交换的通信网称为分组交换网。分组交换兼有 电路交换和报文交换的优点。分组交换比电路交换的电路利用率高，比报文交换 的传输时延小，交互性好。因此，将来的网络将向全i p 网络的方向发展，未来 的i p 网将集成电信网、i n t e m e t 和电视网三大网络。 2 、无连接网络：在i n t e r n e t 的节点之间传输数据时，每个分组都携带完整的 目的地址，各分组在系统中是独立传送的，数据传输过程不需要三次握手。但是， 4 第二章拥塞控制理论与研究现状 由于无连接发送的不同分组可能经历不同路径到达目的主机，所以先发送的不一 定先到，因此无连接的数据分组传输过程中，目的主机接收的数据分组可能出现 乱序、重复与丢失的现象。无连接的可靠性不是很好，但因其省去许多保证机制， 因此通信协议相对简单，通信效率较高。 3 、b e s t e f f o r t 服务模型：b e s t - e f f o r t 是最简单的服务模型。应用程序可以在 任何时候，发出任意数量的报文，而不需要事先获得批准，也不需要通知网络。 网络尽最大的努力来发送报文，但对时延、可靠性等性能不提供任何保证。尽管 最近几年提出了很多的方案( 如：集成服务、区分服务等服务模型) b e s t e f f o r t 服务仍是现在i n t e m e t 的缺省服务模型，适用于绝大多数网络应用，在当前和未 来的网络中占有重要的比重。 4 、广泛使用的t c p i p 协议：t c p i p 作为当今i n t e m e t 的主要协议，它使得 世界上不同体系结构的计算机网络互连在一起，形成一个全球性的广域网络 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 协议己经非常流行并己经 成为计算机网络通信协议的事实标准。 2 1 2 拥塞产生的原因 拥塞发生的主要原因在于“需求”大于“供给”，端系统提供给网络的负载 大于网络资源容量和处理能力。网络中有限的资源由多个用户共享使用，由于没 有准入控制算法，网络无法根据资源的情况限制用户数量；由于缺乏中央控制机 制，网络也无法控制用户使用资源的数量。目前i n t e m e t 上用户和应用的数量迅 速增长，如果不使用某种机制协调资源的使用，必然会导致网络拥塞【8 。1 。拥塞 产生的直接原因有如下几个方面： 1 、存储空间不足。当一个端口收到几个输入端的报文时，接收的报文就会 在这个端口的缓存区中排队。如果没有足够的存储空问存储，当缓存区占满时， 报文就会被丢弃。增加存储空间在某种程度上可以缓解这一矛盾。 2 、带宽容量不足。根据香农信息理论，任何信道带宽最大值即为信道容量 c = b l 0 9 2 ( 1 + s m ) ( n 为信道白噪声的平均功率，s 为信源的平均功率，b 为信 道带宽) ，所有信源发送的速率r 必须小于或等于信道容量c 。如果r c ，在理 论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其 满足不了通过它的所有资源带宽要求时，网络就会发生拥塞。 3 、c p u 处理速度慢。如果结点的c p u 在执行缓存区排队、路由选择时， 处理速度跟不上链路速度，也会导致拥塞。同样，如果只提高处理器速度，而不 相应提高链路速率，只会转移网络瓶颈，而不能避免拥塞。 第二章拥塞控制理论与研究现状 4 、用户恶意攻击造成的网络拥塞。在近年频繁发生的黑客攻击事件中，使 用较多的一种攻击方式为d d o s ( d i s t r i b u t ed e n i a lo fs e r v i c e ) 。该攻击通过向被 攻击的站点发送大量的信息包使之不堪重负，从而不能为合法用户提供正常的服 务。 5 、不合理的网络拓扑结构及路由选择也会导致网络拥塞。 虽然随着科技的发展，网络设备的处理速度不断加快、网络带宽持续增长， 但是硬件的建设的速度有时赶不上应用需求的增长。而且，在许多情况下，简单 地增加硬件资源，如将节点缓存的存储空间扩大、或者将链路更换为更高速的链 路、或者将结点处理器的运算速度提高等，非但不能解决拥塞问题，而且还可能 使网络的性能更坏。 因为问题的关键在于整个系统的各部分资源不匹配。因为拥塞总是发生在网 络中资源“相对”短缺的地方，这反映了互连网络的不均衡性。这种不均衡性一 方面表现在资源的不均衡，如图2 1 ( a ) 中带宽分布不均衡：当s 以1 0 0 m b p s 的速 率向d 发送数据时，在路由器r 处会发生拥塞。另一方面是由于流量的不均衡， 如图2 1 ( b ) 中带宽分布是均衡的，但当s l 和s 2 都以1 m b p s 的速率向d 1 发送数 据时，在路由器r 也会发生拥塞。i n t e m e t 中资源和流量分布的不均衡是广泛存 在的，由此导致的拥塞不能通过增加资源的方法解决。 ( a ) 带宽分配不均匀( b ) 流量分配不均衡 图2 1 网络互联的不均衡性 但是即使系统的各部分都平衡了，问题也不会解决。事实上，且不说更换所 有设备的经济可行性，网络数据传输的突发性和网络传输中许多的不确定性因素 都需要一个管理控制机制来加以约束，才有可能使网络发挥其最大功效。拥塞控 制是一个全局性的过程，涉及到所有与网络传输性能相关的因素。“瓶颈”是永 远都存在的，因此拥塞控制必不可少。 2 1 3 拥塞控制的分类 按照不同的分类方法拥塞控制协议和算法可以分为不同的类型 1 2 - 1 4 】。 从控制理论的角度，拥塞控制算法分为开环控制和闭环控制两大类t 1 5 - 1 6 。当 6 第二章拥塞控制理论与研究现状 流量特征可以准确规定、性能要求可以事先获得时，适于使用开环控制；当流量 特征不能准确描述或者当系统不提供资源预留时，适于使用闭环控制。1 n t e r n e t 中主要采用闭环控制方式。本论文所完成的p i 速率控制属于闭环控制。闭环的 拥塞控制分为以下3 个阶段：检测网络中拥塞的发生；将拥塞信息报告到拥塞控 制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。闭环的拥塞控制可以动态 地适应网络的变化，但它的一个缺陷是算法性能受到反馈延迟的严重影响。当拥 塞发生点和控制点之问的延迟很大时，算法性能可能会有所下降。 根据实施控制的类型，拥塞控制可以分为基于窗口( w i n d o w - b a s e x i ) 和基于 速率( r a t e b a s e d ) 两种类型。t c p 采用的是典型的基于窗口的控制方式，t c p 通过调整滑动窗口的大小控制发送到网络的数据量。基于窗口的控制易于实现， 并且可以限制注入网络的最大流量。基于速率的控制方式则是通过每秒发送的比 特数来控制数据流的发送，如果传输率能够匹配网络可用带宽，就可以减少路由 器的缓存区长度，所以它本质上更适合于多媒体数据流的传输。p i 速率控制顾 名思义属于后一种控制手段，更适应于含有大量多媒体数据流的这种网络状况。 根据推断网络状态的反馈信息的类型，拥塞控制可以分为显式拥塞控制 ( e x p l i c i tc o n g e s t i o nc o n t r 0 1 ) 和隐式拥塞控制( i m p l i c i tc o n g e s t i o nc o n t r 0 1 ) 。在显 式控制方式中，网络使用显式信号向执行流量控制的端点通告其状态( 有效带宽 a n d o r 缓存容量等) ；如果控制端能够测量或者通过诸如超时、重复a c k 等隐含 信号来推断网络状态则为隐式控制方式。t c p 协议是典型的隐式控制协议，而 x c p 及本文所实现的p i 速率控制协议则是典型的显式控制协议。 根据算法的实现位置，可以将拥塞控制算法分为两大类：链路算法( 1 i n k a 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 拥塞控制算法的各种改进都属于 源算法类型，而x c p 及p i 速率控制都属于链路算法。 2 1 4 拥塞控制算法评价标准 拥塞控制算法需要考虑的主要性能标准有：效率、公平性、分布性和收敛性。 1 、效率：资源使用效率定义为总体负载接近点k n e e ( 如图1 1 所示) 的程度。 设x g 。1 是在k n e e 点期望的负载，那么只要总体分配田砂= 而何接近于x g o a l ， 则认为资源使用是有效率的。过载或者负载不足都不是所期望的，被认为是效率 第二章拥塞控制理论与研究现状 低。总体资源在各个用户之间的分配则是由公平性标准来衡量的。 2 、公平性：公平性作为衡量拥塞控制算法性能的一个重要指标，已被广泛 研究。最大最小公平性标准是在多个用户共享多个资源时普遍使用的衡量标准。 考虑一个网络，设链路的集合为f ，其中每个链路，f ，容量为c ， 0 。每个 流同一个路径关联，该路径为f 的子集。当路径r 经过链路，时，表示为， r 表示路径的集合。 ，表示路径，所分配到的带宽。最大最小公平性就是要， 在满足容量限制的条件下，最大化最小的厂a ，。可行集内增加a ，必然导致a ，的 减少，从而a ， a ，因此得出以下约束条件：对于每个路径，至少有一个链 路l r 。队丽，对于全体t r ，ar c l ，且ar = m a xfa l r o 3 、分布性：集中控制的方案需要对系统状态完全了解，这种方案实现复杂， 而且会给系统增加很大的负担。因此一些只需要少量信息的分布式控制方案更具 有实用价值。 4 、收敛性：拥塞控制方案还需要很快收敛。收敛性通常是以系统从一个初 始状态到达目的状态所需要的时问来衡量的。但是系统通常不会收敛到唯一的稳 定状态，而是会到达一个平衡态，并在平衡态附近振荡。到达平衡态的时问和振 荡大小决定了收敛性。到达平衡的时间决定了灵敏性，而振荡的大小则决定了控 制的平滑性，如图2 2 。 弼 绻 负 载 雾事瓣 图2 - 2 灵敏性和平滑性 2 2 拥塞控制算法研究现状 当前研究一部分旨在修改现有的t c p 协议参数以满足新的需求；一部分旨 第二章拥塞控制理论与研究现状 在提出新的协议以满足未来的综合网络环境和q o s 等新的应用需求。同时随着 网络复杂性的不断增加，i n t e m e t 能否持续稳定地发展已成为一个令人关注的问 题。良好的工程环境与仿真实验固然必不可少，但也需要更好的系统的分析与设 计手段。因此国外部分原来进行控制理论和非线性动力学的研究人员也相继转而 进行网络的拥塞控制研究，并且在这方面取得很大的成绩。 2 2 1 源端的拥塞控制 在众多的基于源端的拥塞控制算法中，t c p 拥塞控制算法是目前使用最为普 遍、最为成功的拥塞控制算法。本节重点关注该类源端拥塞控制算法及其改进策 略。 t c p 使用了序列号、校验和、确认以及超时重传等机制提供了可靠数据传输。 许多流行的应用程序如t e l n e t ，h t t p ，f t p 和s m t p 等都使用t c p 。根据m c i 的统 计，网络中总字节数的9 5 和总报文数的9 0 使用t c p 传输。 最初的t c p 协议只有基于窗口的流控制( f l o wc o n t r 0 1 ) 算法而没有拥塞控 制算法。流控制作为接收端管理发送端发送数据的方式，用来防止接收端可用的 数据缓存空间溢出。但流控制是一种局部控制机制，其参与者仅仅是发送端和接 收端，它只考虑了接收端的接收能力，而没有考虑到网络的传输能力。正因为流 控制的这种局限性，从而导致了拥塞崩溃现象的发生。 1 9 8 6 年初，j a c o b s o n 开发了现在t c p 的拥塞控制算法f 6 0 7 - z s 】。运行在端节 点主机中的这些算法使得t c p 连接在网络发生拥塞时回退( b a c ko f f ) ，也就是说 t c p 源端会对网络发出的拥塞指示( c o n g e s t i o nn o t i f i c a t i o n ) ，如丢包、重复的 a c k 等，作出响应。1 9 8 8 年j a e 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 n a v o i d a n c e ) 算法。1 9 9 0 年出现的t c pr e n o 版本增加了“快速重传”( 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 w - r e n o 和选择性应答t c ps a c k ( s e l e c t i v ea c k n o w l e d g e m e n t ) 等。正是 这些拥塞控制机制防止了今天网络的拥塞崩溃。 l 、慢启动算法：过去的t c p 在刚刚建立一个连接时，源端会立即向网络注 入大量的数据包，直到超过接收端宣称的通告窗口大小。当两个主机在一个局域 网上时，这种做法是可行的。但对于i n t e m e t 来说，路由器必须对数据包进行排 队，这样很容易导致路由器缓存空问耗尽，网络发生拥塞，使得t c p 连接的吞 吐量急剧下降。因此新建立的t c p 连接不能一开始就发送大量数据，而只能逐 步增加每次发送的数据量，以避免上述现象的发生。慢启动算法的思想就是源端 9 第二章拥塞控制理论与研究现状 发送数据包的速度应该等于目的端返回a c k 的速度。当建立一个新的连接时， 拥塞窗口( c w n d ) 被初始化为一个数据包的大小( 缺省值通常为5 1 2 或5 3 6 字 节) 。源端按e w n d 的大小发送数据，每收到一个a c k 确认，e w n d 就增加一个 数据包的发送量。刚开始，源端发送一个数据包便等待a c k 确认，当确认被接 收后，发送的数据包就增加到两个，接着又是四个，等等。c w n d 便随r t t 呈指 数增长。当c w n d 达到网络的负载时，中间的路由器开始丢弃数据包，这就告诉 源端c w n d 过大了。慢启动算法要达到每r 1 r r 发送w 个数据包所需时间为l m l o g w 。由于在发生拥塞时，拥塞窗口会减半或降到1 ( 降到l 是针对超时这种 情况而言) ，因此慢启动确保了源端的发送速率最多是链路带宽的两倍。 2 、拥塞避免( c o n g e s t i o na v o i d a n c e ) 算法：慢启动算法是在一个连接上发 起数据流的方法，当数据流耗尽了中间路由器的缓存区时，数据包就被丢弃。拥 塞避免算法就是一种处理丢失数据包的方法。慢启动和拥塞避免是两个目的不同 的独立算法。一般来说，存在两种因为网络拥塞而丢失数据包的暗示：发生超时 和接收到重复a c k 。当拥塞发生时，需要降低数据包进入网络的传输速度，可 以通过慢启动来做到这一点。实际应用中这两个算法是在一起实现的，过程如下： 对于一个新建立的连接，初始化c w n d 为一个数据包的大小，慢启动阂值 ( s l o ws t a r tt h r e s h o l d ，简称s s t h r e s h ) 为6 5 5 3 5 个字节。发送的数据包不能超过 c w n d 和目的端通告窗口( a w i n ) 的大小。当拥塞发生时( 超时或收到重复a c k ) ， s s t h r e s h 被设置为当前窗口大小的一半，但最少为两个数据包大小。此外，如果 是超时引起拥塞，则c w n d 设置为1 个数据包大小( 这就是慢启动) 。当新的数 据被对方确认时，就增加c w n d 。但增加的方法依赖于c w n d 与s s t h r e s h 的大小关 系。若c w n d 大于等于s s t h r e s h ，则在慢启动阶段，拥塞窗口指数增长；否则处 于拥塞避免阶段，拥塞窗口线性增长。 3 、快速重传：j a c o b s o n 提出了对拥塞避免算法的改进，实现了当收到一个 乱序包时，接收端发送一个重复a c k 。这个a c k 的目的是告诉发送端有乱序包 并且这个包的序列号是多少。t c p 并不知道重复a c k 是由于丢失包引起的，还 是由于包乱序引起的。但认为如果是乱序所引起的，则在乱序包处理前应当只有 1 个或者2 个a c k 。如果有3 个或者超过3 个重复a c k 收到，则认为是由于丢 包引起的，因此重传数据包而不等重传计时器超时。这种机制就是快速重传机制。 4 、快速恢复：重传了丢失的数据包后，执行拥塞避免算法而不是慢启动算 法，这就是快速恢复算法，这样可以在中等程度拥塞的情况下支持高输出。快速 恢复是基于“管道”模型( p i p em o d e l ) 的“数据包守恒”的原则( c o n s e r v a t i o no f p a c k e t sp r i n c i p l e ) ，即同一时刻在网络中传输的数据包数量是恒定的，只有当旧 的数据包离开网络后，才能发送新的数据包进入网络。 1 0 第二章拥塞控制理论与研究现状 快速重传和快速恢复算法通常一起执行，过程如下：当收到第三个重复的 a c k 时，将s s t h r e s h 设置为当前c w n d 的一半。然后重传丢失的数据包，并且设 置c w n d 为s s t h r e s h 加上3 倍的数据包大小。每次收到另一个重复的a c k 时，c w n d 增加一个数据包大小并发送一个分组( 如果新的c w n d 允许发送) 。当下一个确 认新数据的a c k 到达时，设置c w n d 为s s t h r e s h 。这个a c k 应该是对丢失的分 组和收到的第一个重复的a c k 之间的所有的中间数据包的确认。这一步采用的 是拥塞避免，因为分组丢失时将当前速度减半。 冀鼻毒。 一向 图2 - 3t c p 拥塞控制机制 这四种算法基本涵盖了各种拥塞的情况，在长时间内被广泛的采用。经过十 多年的发展，目前t c p 协议主要包含有四个版本：t c pt a h o e ，t c pr e n o ，t c p n e w r e n o 和t c ps a c k 。 。 t c pt a h o 1 7 】是早期的t c p 版本，它包括了3 个最基本的拥塞控制算法：慢 启动、拥塞避免和快速重传。 t c pr e n o ”】在t c pt a h o e 基础上增加了快速恢复算法，但是一个拥塞窗口 中有多个数据包丢失时，t c pr e n o 会面临性能恶化。t c pn e w r e n o t l 9 对t c p r e n o 中的快速恢复算法进行了修正，它考虑了一个发送窗口内多个数据包丢失 的情况。在t c pr e n o 版本中，发送端收到一个新的a c k 后就退出“快速恢复” 阶段，而在n e w r e n o 中，只有当所有的数据包都被确认后，才退出“快速恢复” 阶段。 t c ps a c k t 2 0 】关注的也是一个窗口内多个数据包丢失的情况，它避免了之前 版本的t c p 在重传一个窗口内所有数据包时所遇到的问题，不重传那些已经被 接收端正确接收的数据包，而仅仅重传被丢弃的数据包。 除了以上几种t c p 外，b r a k m o 等还提出了t c p v e g a s 2 。v e g a s 是一种基 于延迟( d e l a y b a s e d ) 的协议。t c p v e g a s 采用了三种技术来增加输出和降低丢 包率。首先，采用新的重传机制来决定何时重传数据包，另外使t c p 有能力预 第二章拥塞控制理论与研究现状 测即将发生的拥塞，并调整重传速率。这主要是通过对比实际的输出和预期的输 出的差异来预测拥塞，并调整发送速率。定义b a s ei 册，这个i 酊为不发生拥 塞时的r t t 值，实际使用时，则取这个值为所有i 岍的最小值。预期的输出为 e x p e c t e d = w i n d o ws i z e b a s e r 7 7 其次，计算当前的实际发送速率，这是通过 计算一个特别的数据段的发送时间来得到的。这种计算是在每个r t t 时问进行 一次。最后，对比预期和实际，从而调整发送速率。定义d i f f = e x p e c t e d a c t u a l ， 另外定义两个阈值口和夕( 口 夕) 。当d i f f 时，则减小拥塞窗口；口 m i n 口n e w b 口d l a 。而适应机构的主要功 能就是根据新的变化重新计算参数局、晦的值。 然后，系统通过适应机构来改变系统参数，或者产生一个辅助的控制输入量， 累加到系统上，以保证系统跟踪上给定的最优性能指标，使系统处于最优或次优 的工作状态。p i 速率控制器的主要计算参数k j 、k e 都是根据适应机构判断的情 况来做相应的计算和改变，这就可以使系统随时都做好准备应付任何突发情况， 而不需要人为改变或设定参数。 2 1 第三章p i 速率控制协议理论分析及实施方案 自适应系统与其它系统的显著区别在于它包含有性能指标闭环。从本质上 讲，自适应控制应具有“辨识决策一修改 的功能，即： 辨识：不断地测取系统( 被控对象) 的信号和参数，并加以处理，以获得系 统状态。决策：根据所辩识的系统状态和事先给定的准则作出决断。决策包括系 统的自适应算法。辨识是获得对系统的认识，而决策则是由此得出具体的控制规 律。修改：对决策所计算出来的控制参量必须不断地适当修正，并由相应的执行 装置来实现。也就是说，控制律必须与参数调整律相配合( 自适应) 。以使系统 不断地趋向最优或要求的状态。 自适应控制大致可分为增益自适应控制、模型参考自适应控制( m o d e l r e f e r e n c ea d a p t i v ec o n t r o l ，m r a c ) 、自校正控制( s e l f - t u n i n gc o n t r o l ，s t c ) 、 直接优化目标函数自适应控制。以下着重分析与本文p i 速率控制器相关的自校 正控制系统。 自校正控制系统也可以看作由两个控制回路组成：内环由被控对象和常规的 控制器组成：外环由参数估计器和控制器设计计算两部分组成。参数估计和控制 器设计必须在线地实现，因为这个参数是随着系统的变化实时变化的，