（计算机系统结构专业论文）网络拥塞控制算法的设计与实现.pdf

哈尔滨工程大学硕士学位论文 摘要 随着计算机网络的发展，对网络服务质量的需求越来越高，不但对网络 有很高的带宽要求，而且要求信息传输的低延迟和低抖动等。网络拥塞是影 响网络服务质量的重要因素，避免拥塞、加强拥塞控制以保证服务质量已经 成为当前的计算机网络的研究热点。主动式队列管理算法通过评估网络状态、 预测早期拥塞的方法有目的地对分组进行丢弃，从而可以使源端更及时地了 解到网络状况并调整发送速率。r e d ( r a n d o me a r l yd e t e c t i o n ) 算法是 i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，i n t e r n e t 工程任务组) 推荐的主动 式队列管理算法的唯一候选算法，然而该算法在响应速度、稳定性、对动态 网络环境的适应性及参数设置等方面仍有不足。 针对r e d 算法对参数设置敏感的问题，提出一种基于平均队列长度和发送 速率的改进的r e d 算法，使得r e d 算法最大丢包概率能够根据发包速率和链路 带宽进行动态的调整，从而改进网络拥塞的现象。在网络仿真器n s 2 上对算法 的验证表明，改进的r e d 算法能有效地适应网络流量的变化，保持队列长度的 稳定，减少队列溢出和空闲现象的发生。 针对r e d 算法在业务的突发度较强或流量抖动较大时，不能获得满意的吞 吐性能的问题，提出一种基于平均队列长度和平均队列长度变化的模糊控制 r e d 算法，该算法不再对每个队列设置固定的门限，而是根据当前网络流量的 状况动态地推理出数据包的丢弃概率。仿真研究表明，该算法可以改善t c p 流量的吞吐性能，并且在流量抖动较大时，在短时间内可以使t c p 流量的抖动 变得平缓，能够对多媒体应用提供较为理想的性能改进。 关键词：网络服务质量；拥塞控制；模糊控制；r e d 算法 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t e rn e t w o r k , t h ed e m a n df o rt h eq u a l i t y o ft h es e r v i c eo fn e t w o r ki n c l u d i n gt h el a r g eb a n d 谢d t ho fn e t w o r k ，t h el o wd e l a y a n dt h el o wv i b r a t i o ni s g r o w i n g t h en e t w o r kc o n g e s t i o ni s ag r e a tf a c t o r a f f e c t i n gt h en e t w o r kq u a l i t yo fs e r v i c e a v o i d i n gc o n g e s t i o na n de n h a n c i n gt h e c o n g e s t i o nc o n t r o lt oe n s u r et h eq u a l i t yo fs e r v i c eh a v eb e c o m et h ef o c u so ft h e n e t w o r kr e s e a r c h b ye v a l u a t i n gt h en e t w o r ks t a t ea n dp r e d i c t i n gt h ei n c i p i e n t c o n g e s t i o n ，a q m ( a c t i v eq u e u em a n a g e m e n t ) c o u l dd r o pp a c k e t sp u r p o s e f u l l y ， t h u ss o u r c e sc a nb ew e l li n f o r m e dt h en e t w o r ks t a t ea n dt h e n a d j u s ti t s s e n d i n g r a t e t h er e da l g o r i t h mi sr e c o m m e n d e db yi e t fa st h eo n l yc a n d i d a t e a l g o r i t h m ，i ti sn 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 y ，t h ea d a p t a b i l i t yo f d y n a m i cn e t w o r ke n v i r o n m e n ta n dp a r a m e t e r ss e t t i n g d u et ot h er e da l g o r i t h mi ss e n s i t i v et op a r a m e t e r ss e t t i n g ，a l li m p r o v e d r e da l g o r i t h mc o m b i n e sw i mq u e u el e n g t ha n ds e n d i n g r a t e i n s p e c t i o nw a s p r o p o s e d ，t h i sa l g o r i t h mm o d i f i e dt h em a x i m u md r o p p i n gp r o b a b i l i t ya c c o r d i n g t ot h es e n d i n g r a t eo ft h es o u r c en o d ea n dt h eb a n d w i d t ho ft h el i n k t h u s ，i t i m p r o v e dt h en e t w o r kc o n g e s t i o np h e n o m e n o n t h i sa l g o r i t h mw a sv e r i f i e di n n s 2n e t w o r ks i m u l a t o r t h er e s u l ts h o w e dt h a tt h ei m p r o v e dr e dc o u l da d a p tt h e c h a n g eo fn e t w o r kt r a f f i ce f f e c t i v e l y , k e 印t h eq u e u el e n g t hs t e a d y ，r e d u c et h e p h e n o m e n o no ft h eq u e u eo v e r f l o wo rt h ei d l eq u e u eg r e a t l y d u et ot h ep a r o x y s m a lb u s i n e s so rt h ev i b r a t e df l o w s ，t h et h r o u g h p u ti sn o t s a t i s f i e d ，af u z z yc o n t r o lr e da l g 面t h mb a s e do na v e r a g eq u e u el e n g t ha n dt h e v a r i a n c eo fa v e r a g eq u e u el e n g t hw a sp r o p o s e di nt h i st h e s i s ，t h i sa l g o r i t h mn o l o n g e rs e tt h ef i x e dt h r e s h o l df o re a c hq u e u e ，b u ti n f e r r e dt h ep a c k e t sd r o p p i n g p r o b a b i l i t yd y n a m i c a l l ya c c o r d i n gt ot h en e t w o r kt r a f f i c s i m u l a t i o n ss h o w e dt h a t t h i s a l g o r i t h mc o u l di m p r o v et h et h r o u g h p u tp e r f o r m a n c eo ft h et c pt r a f f i c 哈尔滨工程大学硕士学位论文 w h e nt h et r a f f i cv i b r a t e da c u t e l y ，i tc o u l dm a k et h et c pt r a f f i cb e c o m eg e n t l ei n as h o r tt i m ea n dp r o v i d et h ei d e a lp e r f o r m a n c ei m p r o v e m e n tf o rm u l t i m e d i a a p p l i c a t i o n s k e y w o r d s ：n e t w o r kq u a l i t yo fs e r v i c e ；c o n g e s t i o nc o n t r o l ；f t t z z yc o n t r o l ；r e d 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中已 往明引用的内容外，本论文不包含任何其他个人或集体己 盎公升胍、h 勺作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担： 作者( 签字) ： 日期：d 8 年弓月，乒日 哈尔滨丁程大学硕十学位论文 1 1 课题的背景和意义 第1 章绪论 t c p i p ( t r a n s m i s s i o nc o n t r o lp r o t o c o la n di n t e r n e tp r o t o c o l ，传输控制协议 因特网协议) 协议使任何具有计算机、网卡和i n t e m e t 艮务提供者的用户能访问 和共享i n t e m e t 上的信息。用户每天产生流量非常大的信息，其中绝大部分在 i n t e r n e t 上传输，是t c p s p 协议保证数以百万计的信息传输。 1 9 8 4 年，n a g l e 首次指出了复杂t c p 1 p 网络中存在的拥塞问题：路由器连 接的带宽差异较大的网络中，容易发生“拥塞崩溃 现象。1 9 8 6 年1 0 月，i n t e m e t 首次出现了一系列的拥塞崩溃现象，网络吞吐量急剧下降，严重时一度使l b l n u cb e r k e l e y 的数据流量从3 2 k b p s 降到t 4 0 b p s ，许多分散在各地的网点被 迫长时间停止服务。此后，j a c o b s o n 等人开始对此进行系统研究，发现这是 由于在网络拥塞状态下t c p 的行为失常所致。为此j a c o b s o n 在t c p 中增加了拥 塞控制算法即( t c pt a h o e ) ，于1 9 8 8 年提出了著名的虬匣启动”( 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 ) ， 1 9 9 0 年的t c pr e n o 版本增加了“快速恢复 ( f a s tr e c o v e r y ) 算法n 1 ，避免了网 络拥塞不够严重时采用虮厦启动”而造成大幅度减小发送窗口尺寸的现象。 上述四个算法是当前i n t e r a c t 上主要使用的端系统拥塞控制机制。当网络出现 拥塞时，t c p 连接通过丢包发现拥塞，调整发送窗口，降低发送流量。t c p 拥塞控制机制在i n t e m e t 中的执行有效地避免了拥塞崩溃现象的发生。 进入9 0 年代以来，i n t e m e t 成为一个重要的和无处不在的基础设施，以网 络协议i p 为基础的i n t e m e t 呈爆炸式增长，使i n t e m e t 的流量急剧增加，由此引 发的网络拥塞已经成为制约网络发展和应用的关键问题。网络拥塞会引起数 据传输延迟和延迟抖动等服务质i q o s ( q u a l i t yo fs e r v i c e ) 沼3 等性能指标下降， 并严重影响了带宽、缓存、吞吐量等网络资源的利用率，因此有效地解决拥 哈尔滨工程大学硕士学位论文 塞问题对于提高网络性能具有重要意义。预防和控制网络拥塞一直是近年来 国内外网络研究领域的热点问题。目前虽然拥塞得到一定的控制，但是拥塞 现象并没有得到彻底解决。 传统网络中采用的是“尽力而为 ( b e s t e f f o r t ) 的服务模式。这是由于传 统的网络应用主要是f t p ，t e l n e t ，s m t p 等对网络性能( 带宽、延迟、丢失 率等) 的变化不敏感，b e s t e f f o r t 模型可以满足需要。随着网络发展，应用领 域不断拓展，应用模式不断丰富，对网络延迟、传输速率等网络性能比较敏 感。传统的b e s t e f f o r t 模型已不能很好地满足其应用需求。加之商业化进程等 的推动，越来越需要对网络所传输的业务类型有一个较为具体和明确的定义， 需要在恰当的层次和粒度上对流量进行必要的管理，包括接纳控制、流量成 形、队列管理、调度和拥塞控制等各个方面1 。 因此，引进更多、更合理的控制机制、防止网络出现拥塞崩溃对己有网 络的稳定运行是至关重要的。由于互联网上9 0 以上的数据流使用的是 t c p i p 协议，所以t c p 佃拥塞控制机制对控制网络拥塞具有特别重要的意义。 此外，拥塞控制是确保互联网鲁棒性的关键因素，也是各种管理控制机制和 应用( 如多媒体通信中q o s 控制、区分服务) 的基础，通过网络的拥塞控制， 可以提高网络的总体性能，保证网络系统长期的稳定性和鲁棒性。拥塞控制 研究的目标是达到网络资源利用率和传输延迟等综合性能指标的最优化。 1 2 国内外相关的研究现状 为了保证网络的稳定性和鲁棒性，1 9 8 8 年v j a c o b s o n 提出了基于滑动窗 口的t c p 端到端的拥塞控制算法h 1 。这是一种和式增加积式减少( 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 ed e c r e a s ea m i d ) 的控制算法。“积式减少”是指不论在 慢开始阶段还是拥塞避免阶段，只要出现一次超时( 即出现网络拥塞) ，就 将慢开始门限s m 嘴s h 设置为当前的拥塞窗口值乘以0 5 。当网络频繁出现拥塞 时，s s t h r e s h 值就下降很快，以大大减少注入到网络中的分组数。而“和式增 加是指执行拥塞避免算法后，当收到对所有发送出的报文段的确认就将拥 2 哈尔滨t 程大学硕士学位论文 塞窗k ! c w n d 增加一个m s s ( m a x i m u ms e g m e n ts i z e ，最大报文长度) 大小， 使拥塞窗口缓慢增大，以防止网络过早出现拥塞。但在端到端的拥塞控制机 制中，数据发送方和接收方对网络的拥塞程度一无所知，因此仅仅依赖端到 端的拥塞控制很难为网络用户提供良好的q o s 保证。网络传输中的大部分丢 包事件是由于路由器节点的缓冲区溢出造成的，只有路由器才对网络的拥塞 程度有最直接的了解。而现有i p 路由器的主要功能是进行数据包的转发，不 具备对网络的拥塞进行检测和控制功能。所以要提高网络服务质量，减少拥 塞的发生，网关或路由器必须参与资源的控制工作。 1 9 9 8 年，b r a d e n 等人在i e t f 提出在路由器中使用主动队列管理技术 a q m 哺1 ，采用排队算法和数据包丢弃策略监控路由器缓冲区队列，提前检测 拥塞的到来并通知数据发送方。这样发送方可以在路由器缓冲区溢出之前调 整数据的发送速率，避免更严重的拥塞发生，并降低丢包率和提高链路利用 率。s f l o y d 等人提出的r e d 1 算法作为最早提出的主动队列管理算法，已被 广泛用来提高系统的综合性能。但是r e d 算法的性能对算法参数设置相当敏 感，随后又有很多改进r e d 算法和新算法相继被提出，比较有代表性的有 a r e d ( a d a p t i v er e d ) 、d r e d ( d y n a m i cr e d ) 、b l u e n 0 1 1 1 、r e m ( r a n d o m e x p o n e n t i a lm a r k i n g ) 扫列等等，不过这些算法的提出都是基于启发式思维和仿 真，缺乏系统的方法，因此算法的稳定性和鲁棒性较差，一般只适用于特定 的网络环境。 c h o l l o t 等人在2 0 0 1 年将经典控制理论引入到t a q m 算法的设计中，并 利用频域校正法设计t p i ( p r o p o r t i o n a li n t e g r a l ) 控制器n 3 r h l 。由于p i 控制器的调 节时间太长，于是又有人将带有反映队列变化速率的微分环节的p i d n 副、p d 控制器应用于a q m ，以期获得更佳的性能，后来又出现了采用非线性控制理 论的变结构控制器。随着智能控制理论的发展，智能控制的应用领域也得到 不断扩大，将智能控制理论应用于a q m 的设计也得到了不断尝试，比如文献 【1 6 提出的一种基于神经网络i 拘a q m 算法，能根据不同数据流的优先级动态 调整丢包概率；文献 1 7 提出的一种基于单神经元的p i 控制算法，可将现有多 哈尔滨1 = 程大学硕士学位论文 种a q m 算法视为它在某种情况下的特例。 控制理论的发展和应用，为主动队列管理算法的设计开辟了一条崭新的 道路，使得a q m 算法的设计可以转化成一种控制器的设计。通过给出一个包 含t c p 源端和路由器动态特性的网络受控模型，可以方便地进行算法性能分 析和控制器设计，并且可以根据控制目标进行参数整定，从而有效地提高拥 塞控制效果。 由于网络是一个复杂的非线性随机系统，应用控制理论还有很多问题需 要解决： ( 1 ) 提高网络受控模型的精度，使之能更好地应用于队列管理。 ( 2 ) 改善控制器参数的鲁棒性，通过一些自适应控制方案的研究，使系 统能适应网络负载和多种类型流共存等各种扰动。 ( 3 ) 实现a q m 高级策略，引入新的智能控制算法如模糊控制、遗传算法、 神经网络或者是几种智能控制算法的结合，以提高控制器的鲁棒性。 1 3 本文的主要工作 在对i n t e m e t 中的t c p i p 拥塞控制机制研究的基础上，针对i p 拥塞控制 策略中r e d 算法存在的问题，提出了相应的解决方案，在网络中间节点处实 现了r e d 算法的改进算法。与传统的随机丢弃算法不同，在新算法下，网络 中间节点通过预测网络状态及拥塞的出现，对数据包进行有目的的“主动 丢弃，从而可以使发送端更及时地了解到网络状况并调整发送速率，从而避 免更严重的网络拥塞。并在网络模拟器n s 2 ( n e t w o r ks i m u l a t o r - 2 ) q b 进行了仿 真实验，实验表明，所提出的算法能够较好地改进原算法的性能。 本文各章节的内容组织如下： 第1 章对网络拥塞相关的基本概念进行陈述，简要介绍国内外研究状况。 第2 章介绍i n t e m e t 中t c p 基于窗口的端到端拥塞控制方法以及i p 层采 用的拥塞控制机制。重点介绍了r e d 算法的基本原理，分析了近年来学术界 提出的r e d 变形算法，归纳总结这些变形算法的优劣。 4 哈尔滨工程大学硕士学位论文 第3 章针对r e d 算法对参数设置敏感的问题，采用使发送速率和平均队 列长度匹配的方法对r e d 算法中的参数m a x 。进行改进，并用n s 2 进行仿真 实验，实验表明，改进的算法能提高吞吐量和减少丢包率。 第4 章提出一种新的基于平均队列长度和平均队列长度变化的模糊控制 r e d 管理算法，该算法依赖专家经验进行控制，无需得到网络精确模型，多 种网络环境下的仿真研究表明，该算法能在保持较小丢弃概率的同时将队列 长度稳定在目标队列长度附近，具有较强的稳定性和鲁棒性。 结论部分对本文的主要工作进行概括，并指出下一步的研究重点。 哈尔滨t 程大学硕士学位论文 第2 章t c p i p 拥塞控制策略 2 1 网络拥塞概述 2 1 1 拥塞和拥塞控制 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥 塞。网络产生拥塞的根本原因在于用户( 或端系统) 提供给网络的负载大于 网络资源容量和处理能力，从而表现出数据包时延增加、丢弃概率增大、上 层应用系统性能下降等问题，严重时甚至可能导致整个网络的崩溃，迫使整 个通信网络停止运行。拥塞的发生如图2 1 所示n 钔。当负载较小时，吞吐量 的增长和负载相比基本呈线性关系，延迟增长缓慢；在负载超过膝点之后， 吞吐量增长缓慢，延迟增长较快：当负载超过崖点之后，吞吐量急剧下降， 延迟急剧上升。可以看出，负载在膝点附近时网络的使用效率最高。拥塞控 制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发生做出反应。 吞 吐 量 图2 1 负载与吞吐量的关系 拥塞产生的直接原因有以下三点： ( 1 ) 存储空间不足。几个输入数据流共同需要同一个输入端口，在这个 端口就会建立排队，如果没有足够的存储空间，数据包就会丢弃，对突发数 6 哈尔滨下程大学硕士学位论文 据流更是如此。增加存储空间在一定程度上可以缓解这一矛盾，但如果路由 器有无限存储空间量，拥塞只可能变得更坏，而不是更好，因为网络里的数 据包经过长时间排队后才通过路由器完成转发，会浪费网络资源，加重网络 拥塞。 ( 2 ) 带宽不足。低速链路对高速数据流的输入也会产生拥塞。根据香农 信息理论，在网络低速链路处会形成带宽瓶颈，当其满足不了所有信源带宽 要求时，网络就会发生拥塞。 ( 3 ) 处理器能力弱、速度慢。如果路由器的c p u 在执行排队缓存、更新 路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链 路对高速c p u 也会产生拥塞。 拥塞控制是以管理相互竞争的发送数据源合理分享有限的传输带宽资源 为目的，达到能有效避免拥塞的发生，抑制拥塞的发展，当拥塞发生时，能 将网络尽快从拥塞状态中恢复过来的一种控制机制。虽然拥塞现象源于网络 资源的不足，但是单靠增大资源并不能缓解这一现象，甚至可能加重拥塞。 2 1 2 拥塞崩溃现象及表现 拥塞崩溃最早是在上世纪八十年代被报告的，主要有由于t c p 连接不必 要的重传那些己经在传输中或者己经被接收端接收的分组。把由于不必要的 分组重传导致的拥塞崩溃称为经典拥塞崩溃( c l a s s i c a lc o n g e s t i o nc o l l a p s e ) 。关 于经典拥塞崩溃的问题已经通过现在的t c p 中的时钟和拥塞控制机制得到 基本解决。 拥塞崩溃的第二种形式是，未送达分组导致的崩溃( c o n g e s t i o nc o l l a p s e f r o mu n d e l i v e r e dp a c k e t s ) 。这种崩溃源于那些浪费了网络带宽的分组在到达最 终目的地前被丢弃了。普遍认为这是当前i n t e m e t 拥塞崩溃中最大的且没有 解决的危险。未送达分组导致的崩溃主要是由于当前的一些不支持端到端拥 塞控制的开环应用程序的大量应用。更具破坏性的应该是一些尽最大努力服 务应用程序对于丢包率的响应方式，这些程序在丢包率增加的情况下会增加 7 哈尔滨工程大学硕士学位论文 它们的发送速率。 t c p i p 协议族作为当今互联网的基石，有力地推动了网络技术的发展。 i n t e m e t 的成功很大程度上取决于拥塞控制的有效执行。本章主要分析基于源 端的t c p 拥塞控制机制和基于中间节点的i p 拥塞控制机制，并对两者进行 了对比分析。 2 1 3 拥塞控制算法的评价标准 在研究拥塞控制算法的过程中，评价方法和评价标准是分析算法可行性、 可靠性以及效率等的关键。拥塞控制算法的评价指标包括端系统的吞吐率、 连接的丢失率和延迟等。拥塞控制算法则从整个系统的角度出发进行考虑。 ( 1 ) 资源分配的公平性 由于公平性是针对资源分配而言的，所以在评价前首先要确定“资源 的含义。目前大多数研究在评价公平性时都针对吞吐量，这是从用户的角度 出发考虑的，并不完全适合网络中的资源状况。网络中的资源包括链路带宽、 网关的缓冲和网关的处理能力等，在考察公平性时应当将这些资源的分配情 况综合考虑。 公平性是指在网络发生拥塞时各连接能公平地共享网络资源。产生公平 性的根本原因在于拥塞发生必然导致数据包丢失，而数据包丢失会导致各数 据流之间为争抢有限的网络资源发生竞争，竞争能力强的数据流将到更多网 络资源，从而损害了其它流的利益。所以说没有拥塞，也就没有公平性问题。 公平性阀题表现在两方面： 一是拥塞响应的t c p 流和非拥塞响应的u d p 流之间资源享用不公平， 这是在发生拥塞时对拥塞指示做出的不同反应造成的。由于t c p 流具有拥塞 控制机制，在收到拥塞指示后，源端会主动降低发送速率；而u d p 流由于没 有端到端的拥塞控制机制，因此在收到拥塞指示后，u d p 不会降低数据发送 速率。结果在网络拥塞时，拥塞响应的t c p 流得到的资源越来越少，非拥塞 响应的u d p 得到的资源越来越多，从而导致了网络资源分配的不公平。网络 哈尔滨工程大学硕士学位论文 资源分配的不公平反过来会加重拥塞情况，甚至可能导致拥塞崩溃。 二是t c p 流之间资源享用的不公平。研究表明，不同的窗口大小、r t t 值及数据包的尺寸都会影响t c p 流对带宽的占用。窗口较大，或者r t t 较 小，或者数据包较大的流往往能占用更多的带宽。 ( 2 ) 资源分配的效率 拥塞控制算法的目的就在于有效的管理网络资源，使有限的资源能够得 到合理运用以达到资源最大化，因此资源分配的效率就是评价拥塞控制算法 有效性的一个重要的指标。 资源分配的效率可以用p o w e r 函数来评价。p o w e r 函数定义为： p o w e r = t h r o u g h p u t 4 r e s p o n s e t i m e ( 2 1 ) t h r o u g h p u t 为吞吐量，r e s p o n s e t i m e 为响应时间。式( 2 1 ) 中，一般取a = l 。 如果评价偏重吞吐量，则取a l ；如果评价偏重反应时间，则取a l 。但是 p o w e r 函数更加侧重于单一资源分配的合理性问题，因而对于整个网络的拥 塞控制的有效性不能给出一个好的评价。 2 2t c p i p 协议 i s o 制定的o s i 参考模型的过于庞大、复杂招致了许多批评。与此对照， 由技术人员自己开发的t c p i p 协议栈获得了更为广泛的应用n 引。图2 2 是 t c p i p 参考模型和o s i 参考模型的对比示意图。 t c p i p 协议簇己经成为计算机网络世界开发系统互联的事实标准。 t c p i p 代表了一系列因特网互联协议，是具有相似特征的一簇协议的总称。 它定义了通过i n t e m e t 进行传输交换，处理传输中发生的故障，管理传输路 径等功能。t c p i p 体系结构和o s i r m 体系结构类似，采用了分层体系结构， 每一层完成特定的功能，各层之间采用标准接口传送数据。和拥塞控制相关 的有网络层、传输层、和应用层。 9 哈尔滨工程大学硕士学位论文 图2 2 t c p i p 参考模型 网络层：定义了正式的分组格式和协议，即i p 协议。它的功能就是传输 由其它用户发送的i p 分组，并发送到正确的目的机。网络层往往是载体和用 户的接口。 传输层：整个协议层次结构的核心，t c p 协议就是在这里定义的端到端 传输协议之一，它是一个面向连接的协议。传输层的任务是从发送端到目的 端提供可靠、有效的数据传输服务，而与当前网络或使用的网络无关。它可 以使发送端和目的端主机上的对等实体进行会话。同时，它还要处理流量控 制，以避免高速发送方向低速接收方发送过多报文而导致接收方无法处理。 应用层：享受以下各层为它提供可靠的传输，它包含所有的高层协议。 对用户来说，它是一些实际应用。最早引入的应用包括虚拟终端协议 ( t e l n e t ) 、文件传输协议( f t p ) 和电子邮件协议( s m t p ) 。 2 3 传输层拥塞控制策略 2 3 1 传输层拥塞控制概述 t c p 协议是目前在i n t e m e t 中使用最为广泛的传输协议。据统计，i n t e m e t 1 0 哈尔滨丁程大学硕士学位论文 上9 0 的数据流使用的是t c p 协议。t c p 协议中使用的拥塞控制算法己成为 保证i n t e m e t 正常运行的重要因素。t c p 采用基于窗口的速率控制机制，根 据网络反馈信息、增加或减小发送速率，利用分组丢失作为隐式的拥塞信号， 从源端对数据传送的速率进行限制。近年来，很多新的算法被引入到t c p 的 传输控制中，算法包括慢启动、拥塞避免、快速重传和快速恢复等。 2 3 2 慢启动算法 当主机开始发送数据时，如果立即将较大的发送窗口中的全部数据字节 都注入到网络，那么由于这时还不清楚网络的状况，因而就有可能引起网络 拥塞。经验证明，较好的方法是由小到大逐渐增大发送端的拥塞窗口数值， 这种避免拥塞发生的算法就是慢启动算法。 慢启动算法为每个连接设置两个参数：拥塞窗口( c w n d ) 和慢启动阈值 ( s s t h r e s h ) 。当建立新的t c p 连接时，c w n d 被初始化为一个数据包大小( 一 个数据包缺省值为5 1 2 或5 3 6 b y t e s ) ，实际发送窗口w i n 取拥塞窗口和通告窗 n ( a w n d ) 中的较小值，即w i n = m i n ( c w n d ，a w n d ) ，源端按w i n 大小发送数据， 每收到一个a c k 确认，c w n d 就增加一个数据包发送量，结果c w n d 随r t t 呈指数增长：1 个、2 个、4 个、8 个，因此，源端向网络中发送的数据量 将急剧增加。直到拥塞窗口达到慢启动阈值( 通常设为6 4 k 字节) ，就进入 拥塞避免阶段。 2 3 3 拥塞避免 拥塞避免算法2 们使发送端的拥塞窗口c w n d 每经过一个往返时延r 订 就增加一个最大报文段的大小( 而不管在时间r 盯收到了几个a c k ) 。这 样，拥塞窗口e w n d 按线性规律缓慢增长，比慢开始算法的拥塞窗口增长速 率缓慢得多。 无论在慢开始阶段还是在拥塞避免阶段，只要发送端发现网络出现拥塞 ( 其根据就是没有按时收到a c k 或收到了重复的a c k ) ，就要将慢开始门 哈尔滨工程大学硕士学何论文 限s s t h r e s h 设置为出现拥塞时的发送窗口值( 即接收端窗口和拥塞窗口中数 值较小的一个) 的一半( 但不能小于2 ) 。这样设置的原因：既然出现了网 络拥塞，那就要减少向网络注入的分组数。然后将拥塞窗口c w n d 重新设置 为1 ，并执行慢开始算法。这样做的目的就是要迅速减少主机发送到网络中 的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。 拥塞避免和慢启动是两个具有小同目标的独立算法，在r e n ot c p 中，慢启 动和拥塞避免算法乜3 1 是一起实现的，算法描述如下： 初始化： c w n d - - 1 s s t h r e s h = 6 5 5 3 5b y t e s w i n - - m i n ( c 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 fc w n d 3 ) ，则将c w n d 设置为s s t h r e s h + n m s s 。 ( 4 ) 若发送窗口值还容许发送报文段，就按拥塞避免算法继续发送报文 段。 ( 5 ) 若收到确认新的报文段的a c k ，就将c w n d 缩小到s s t h r e s h 。 2 3 5t c p 拥塞控制存在的问题 t c p 拥塞控制机制在i n t e m e t 中发挥了行之有效的作用，但t c p 拥塞控 制算法自身存在的问题也是不容忽视的。 ( 1 ) 端系统从发生拥塞到实施控制之间有着明显的时延，而且端系统缺 乏对数据传输过程的动态了解，无法预知网络资源的使用情况，目前主要是 通过降低发送到网络的数据流量来减小网络负载从而缓解拥塞。 ( 2 ) a c kc o m p r e s s i o n 现象：t c p 源端使用了a c k 自计时技术控制数据 包的发送速度，发送方根据接收到的a c k 确认来触发新数据的发送。所以 a c k 的行为也直接影响了发送方的速度，但是a c k 自计时技术在非对称网 中往往会失效。正常情况下，a c k 返回到源端的间隔为该链路上数据包的传 输时间，如果在返回路径中a c k 聚集在路由器的缓冲区中，这样a c k 到达 源端的间隔就成为a c k 的传输时间，由于a c k 比数据包要小得多，所以会 1 3 哈尔滨丁程大学硕七学位论文 造成源端以超出路由器承受能力的速度向网络发送数据包。 ( 3 ) 慢启动算法中存在的问题尤为突出，首先，由于慢启动阶段发送方 无法了解瓶颈链路带宽，每个回路响应时间( r t t ) i 勾都会将c w n d 增加一倍， 如果s s t h r e s h 较大，那么发送方窗口增加到足够大时，会丢失接近一半的数 据包；其次，t c p 慢启动是按照事先设定好的参数开始数据传输的，c w n d ， s s t h r e s h 分别取1 个和6 4 个数据包大小，t c p 连接在闲置一段时间后也使用 慢启动算法重新开始通信，在网络可用带宽较大时，会造成网络资源利用率 降低及延迟增加；再次，t c p 基于窗口的拥塞控制机制对于传输大批量文件 具有良好的适应性，但是为w w w 应用等短小数据流服务时性能较差，往往 需要几个r t t 时间探测合适的网络带宽，传输延迟较大。 ( 4 ) t c pr e n o 算法在源端检测到拥塞后，重传从丢失数据包至检测到丢 失时发送的全部数据包，而实际上其中有些数据包是正确传到接收端的，不 必重传；t c pr e n o 在检测到单个包丢失时效果不错，但是如果在一个数据发 送窗口中出现多个包丢失，由于一个r 1 盯只能重传一个数据包，因此它必须 等待重传超时才能继续传输数据，导致它在性能上具有较大的局限性。 ( 5 ) 网络数据传输延迟较大，延迟抖动也较大。网络中的路由器对队列 管理采用“去尾 方式，对排队长度没有约束，而t c p 对于带宽的需求是“贪 得无厌 的，因此队列的平均长度较大且变化幅度也大，这将对延迟时间敏 感的多媒体数据流的传输质量有很大的影响。 ( 6 ) 公平性问题：i n t e m e t 采取的基于源端的拥塞控制策略是不公平的， t c p 拥塞控制中的公平性问题主要表现在以下两个方面： 首先，t c p 中拥塞窗口大小可以表示为r t t 的函数，比如慢启动阶段 c w n d 随r t t 呈指数级增长，拥塞避免阶段c w n d 随r 盯线性增长，这样对 于长延迟的连接来讲，由于其窗口增长速度慢，因而在同样的条件下获得的 带宽也就越少，特别是在慢启动过程中，r t t 长的连接的劣势就更为明显。 其次，t c p 提供端到端的可靠传输服务，在检测到拥塞后会自觉地降低 发送速度，随着网络中不遵守t c p 协议的各种数据流的出现，t c p 流在与这 1 4 哈尔滨工程大学硕士学何论文 些数据流共存时，其竞争一力较弱，往往会丧失应有的带宽，因此公平地共 享网络带宽也是一个需要密切关注的问题。 ( 7 ) 进一步提高网络性能、满足传输质量q o s 要求，特别是近年提出的 区分服务( d i f f e r e n t i a t e ds e r v i c e s ，简写为d i f f s e r v ) 脾羽，只依靠t c p 拥塞控制 机制是无法完成的。由于t c p 拥塞控制机制存在上述自身无法解决的问题， 人们将拥塞控制研究扩大到网络的中间环节，出现了许多基于路由器的拥塞 控制策略。当前在i n t e m e t 中i p 层实施的控制过于简单，“弃尾”算法容易 使缓冲区长时间处于满状态，这时到达路由器的数据包会因为缓冲区溢出而 全部丢弃，各源端在检测到包丢失后同时降低发送速率，导致网络吞吐量急 剧下降，而在检测到网络空闲时又会同时增加发送速率，这就是所谓的“全 局同步 ( g l o b a ls y n c h r o n i z a t i o n ) 现象，最终的结果是导致网络拥塞，甚至出 现拥塞崩溃。为了更加有效的控制网络中的拥塞现象，公平排队算法f l a i r q u e u i n g ，f q ) 、随机早期检测算法r e d 等相继被提出，从理论上对解决拥塞 问题起到了一定的指导作用，算法的有效性是以其实现的复杂性为代价的， 虽然r e d 算法以其有效性开始在i n t e m e t 中部署实施，但是真正让路由器在 i n t e m e t 中有效地参与拥塞控制仍需要相当长的时间，层拥塞控制还有许多 问题有待于进一步研究。 2 3 6t c p 拥塞的改进 近年来，针对t c p 拥塞控制中存在的问题进行了诸多改进瞳，以便使它 能够更好的符合各种网络应用的需要、适应网络动态变化，使网络运行在最 佳状态。 t c p 慢启动算法在传输短小数据流或当网络可用带宽较大时，容易带来 网络资源利用率降低及延迟增加等问题。大初始窗1 2 1 ( l a r g ei n i t i a lw i n d o w ) 技 术对此作了改进，将初始窗口设为i w = m i n ( 4 * m s s ，m a x ( 2 * m s s ，4 3 8 0b y t e s ) ) ， 其中：m s s 为发送端能发送的最大数据段的尺寸。这样t c p 发送端在刚开 始就可以发送3 个1 4 6 0 字节或4 个5 1 2 字节的分组，减少了发送方等待的时 哈尔滨工程大学硕士学位论文 间，改善了慢启动的性能。 文献 2 5 】提出了二种s m o o t h - s t a r t 算法，建议以s s t h r e s h 2 为界限将慢启 动分为两个阶段，c w n d 小于s s t h r e s h 2 时为第一阶段，这时执行慢启动算法， 每收到一个a c k 确认拥塞窗1 2 1 增l ；进入第一阶段后，拥塞窗口的增长速度 减慢，收到多个a c k 时拥塞窗口才会增加。 文献 2 6 1 讨论了通过调整初始发送窗口的拥塞参数值来改进慢启动算法 性能的几种策略，为改善网络吞吐量、提高链路利用率进行了探索。 慢启动阈值( s s t h r e s h ) 的适当选择对整个慢启动阶段有着至关重要的影 响。通过观察t c p 拥塞控制算法在起始阶段的表现，文 2 7 】中提出了根据 p a c k e t p a i r 算法测量a c k 间隔，用带宽时延积( d e l a y * b a n d w i d t h ) 来估计 s s t h r e s h 的初值。 针对r e n ot c p 快速重传及丢失恢复算法中存在的问题，n e w - r e n o ， s a c k 和f a c k 等算法提出了相应的解决方案。n e w - r e n o 算法小依赖于重 传定时器，利用一个a c k 确认部分发送窗口，立即重传余下的数据包，尽 力避免在快速恢复阶段的许多重传超时：s a c k 算法对数据包进行有选择的 确认和重传，避免不必要的重传，减少时延，但是s a c k 需要修改t c p 协议。 文【2 8 】提出了一种快速重传的改进算法，可以不必等待重传超时就能够从多 包丢失中恢复。文 2 5 】建议在发生拥塞时，使用一种动态恢复机制代替快速 恢复算法从丢包中恢复。一些研究人员发现，当发送方的拥塞窗1 2 1 较小时， t c p 的丢失恢复策略不能很好的工作。例如，由于发送的数据量有限，或受 到接收方通告窗口的限制等，对此，文献 2 9 】提出了相应的解决方案，指出 可以在快速恢复阶段发送方接收到两个连续的重复a c k 时发送一个新的数 据包。 不同于t c p 基于包丢失率的拥塞控制机制，t c p v a g a s 算法通过在源端 监测r t t 的改变来控制拥塞窗口c w n d ，如果发现r t t 显著增加，便认为网 络发生拥塞，减小c w n d ；如果r t t 变小，就认为拥塞已经解除，从而再次 增加c w n d 。v e g a s 算法在接收到一个重复a c k 后，如果检测到这时的r 1 陌 1 6 哈尔滨工程大学硕十学位论文 估值大于超时定时器的值，就重传这个数据包，避免没有足够的a c