（通信与信息系统专业论文）慢减速避免的高速tcp及公平性研究.pdf

南京i l j j j i u 人学颂i j 研究生学位论义 摘要 摘要 随着网络技术的发展，出现了带宽大于1 g b p s ，甚至1 0 g b p s 的高速网络。在高速网络中， 当| j 广为使用的标准t c p 的拥塞控制算法己经不能满足高速网络中数据传输的需要，因此 研究改善高速网络数据传输性能的拥塞控制算法就有重要意义。 本论文主要是关于高速t c p 拥塞控制算法的性能分析与研究。它从拥塞控制算法的必 要性以及t c p 拥塞控制算法的发展现状入手，指出了现有的拥塞控制算法的局限性，在此 基础上介绍了s f l o y d 提出的高速t c p ( h i g hs p e e dt c p ) 。h s t c p 根据当前窗1 2 1 大小调整 其拥塞窗口，目d h s t c p 的窗口增加函数比标准t c p 算法的增加函数变化更快，而减小的时候 又变化的更慢，捐j 塞窗口在下降过程中变化过于缓慢导致了不公平性。 本文在分析h s t c p 的不公平性问题的基础上，提出了慢减速避免的h s t c p 的改进方 案，用于改善同时使用h s t c p 算法的t c p 流间的不公平性。通过引入下除计数和累计窗口 递减两个参数，来改变h s t c p 的拥塞窗口在下降过程中的变化规律，即避免拥塞窗口在下 降过程中变化过于缓慢，使不同r t t 的流的拥塞窗口趋于相等。使用n s 2 作为仿真平台，使 用公平因子作为衡量公平性的准则，对h s t c p 算法和提出的慢减速避免的h s t c p 进行了仿 真。实验结果表明，在瓶颈带宽为1 g b p s 的网络环境下，本文提出的慢减速避免的h s t c p 的公平因子由改进帆的o 3 l 提升到了0 7 0 ，证实了慢减速避免算法的效果。 关键词：t c p 拥塞控制，h s t c p ，慢减速避免，公平因子 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g y ，m a n yh i g h s p e e dn e t w o r k sw i t hb a n d w i d t h l a r g e rt h a n1g b p s ，o re v e n10 g b p sh a sa p p e a r e d a sad a t at r a n s f e rp r o t o c o li nc u r r e n ti n t e r n e t ， t c pp e r f o r m sb a d l yi nh i g h s p e e dn e t w o r k sb e c a u s eo fi t sc o n g e s t i o nc o n t r o la l g o r i t h m s o m e n e wc o n g e s t i o nc o n t r o la l g o r i t h m sh a v eb e e np r o p o s e d t h i st h e s i si st h ea n a l y s i sa n ds t u d yo ft c pc o n g e s t i o nc o n t r o la l g o r i t h m s t a n d a r dt c p c 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 ef i r s ti n t r o d u c e db r i e f l y t h e n ，w ep o i n to u tt h el i m i t a t i o no f s t a n d a r dt c pc o n g e s t i o nc o n t r o la l g o r i t h m s an e wa l g o r i t h m ，h i 曲s p e e dt c p ( h s t c p ) ，i s t h e ni n t r o d u c e d i no r d e rt o g a i nl a r g et h r o u g h p u ti nh i g h - s p e e da n dl a r g e - d e l a yn e t w o r k s ， h s t c pu s e st h ec u r r e n tc o n g e s t i o nw i n d o ws i z ea sar e f e r e n c et oa d j u s ti t sc o n g e s t i o nw i n d o w t h a ti st os a y , h s t c pw i l li n c r e a s ei t sc o n g e s t i o nw i n d o wm o r eq u i c k l ya n dd e c r e a s e si tm o r e s l o w l y ，w h i c hi st h ei m p o r t a n tc a u s eo f t h ep r o b l e mo f t h eh s t c p su n f a i m e s s b a s e do nt h ea n a l y s i so ft h eh s t c p sr t tu n f a i m e s s ，as o l u t i o nt ot h i si s s u ec a l l e ds l o w d e c r e m e n ta v o i d e dh s t c pi sp r o p o s e d i t sm a i ni d e ai st oa d dt w op a r a m e t e r s ，o n ef o rt h e n u m b e ro fd e c r e m e n ta n dt h eo t h e rf o rt h es i z eo fa c c u m u l a t e dd e c r e m e n to fw i n d o ws i z e ，t o c h a n g eh s t c p sc o n g e s t i o nw i n d o w t h a tw i l lm a k ed i f f e r e n tr t tf l o w sg e te q u a lc o n g e s t i o n w i n d o w t h eh s t c p a l g o r i t h ma n dt h es l o wd e c r e m e n ta v o i d e dh s t c p a r es i m u l a t e di nn s 2 t h ef a i r n e s si n d e xi su s e dt om e a s u r ef a i r n e s s i ti ss h o w e dt h a tt h ef a i r n e s si n d e x e sr i s ef r o m 0 31f o rt h eo r d i n a r yh s t c pt oo 7 0f o rt h ep r o p o s e dh s t c p i tc a nb ec o n c l u d e dt h a tt h e f a i r n e s sc a nb er e a c h e db yt h es l o wd e c r e m e n ta v o i d e dh s t c p k e yw o r d s ：t c pc o n g e s t i o nc o n t r o l ，h s t c p ，s l o wd e c r e m e n t a v o i d e d ，f a i r n e s si n d e x 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：垄兰! 逮日期：塑墨：坚f ， 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生始姒导师签名理堕日期i 丝竖竺：! 南京邮电大学硕士研究生学位论文第一章绪论 第一章绪论 1 1 高速链路中研究t c p 算法的意义 因特网最初来源于美国国防部的a r p a n e t ，其最大特点是采用无连接的端到端的包 交换服务。在过去的十几年中，因特网逐步发展成为全球互连的网络，它使得用户在世界 范围内进行通信成为了可能。随着因特网的快速发展，人类社会发生了巨大的变革。但就 在因特网深刻影响着人类历史发展进程的同时，其自身的发展却面临着种种困难，其中之 一就是网络拥塞【2 j 。虽然因特网的相关技术日趋成熟，但网络拥塞却仍未得到很好解决， 反而随着因特网的规模的不断扩大、用户和应用的急剧增加，网络拥塞问题日益严重。 据统计因特网上9 5 的数据流使用的是t c p i p 协议【5 】，并通过传输层协议保障通信双 方数据传输的可靠性，t c p h p 传输层最主要的协议是t c p 和u d p 。文献 1 4 中指出，t c p 是一种通过累积确认判断报文是否传输成功，并以此为依据调整发送速率或进行重传，保 障通信数据完整性的协议。t c p 为通信双方提供可靠的数据连接，t c p 协议包括端到端的 流量控制和错误检测机制，使它能够自动适应网上的各种变化，保证了传输的有效性、可 靠性和稳定性。u d p 则是一种简单的，不进行接收确认和流量控制的协议。这两种传输协 议具有不同的特性，在网络中承载不同的业务，前者多用于数据的可靠传输，后者则主要 应用于实时业务的承载。 t c p i p 传输层协议虽然可以简单高效地完成通信数据的传输，但由于端到端控制策略 自身的局限性以及i p 层路由的不确定性，无论t c p 协议还是u d p 协议，都会给网络带来难 以预料的拥塞，无法单独提供服务质量保障，因而限制了新兴业务与网络自身的发展。为 了使现有网络可以提供一定程度的质量保障，业界已经开展了大量研究工作，在网络的不 同层面上提出了多种方案，用来改善网络的性能。 在网络层中，诸血h r e d ( r a n d o me a r l yd i s c a r d ) 之类的队列管理策略被用来提高网络利 用率并降低排队迟延，w f q ( w e i g h t e df a i rq u e u i n g ) 等调度策略用于保证数据流之间的公 平性并提高链路带宽使用的效率；i s ( i n t e g r a t e ds e r v i c e s ) 和d s ( d i f e r e n t i a t e ds e r v i c e s ) 模型提 出了业务分类的概念，通过对业务区分处理，网络可以在一定程度上满足业务对服务质量 的需求。 j 在传输层上，基于现有的t c p 协议，人们进行了多种改进，用来缓解网络拥塞的发生 或者在网络拥塞发生后，缩短网络恢复的时间，从而提高网络的传输性能。在u d p q l 务方 1 南京邮电大学硕士研究生学位论文第一章绪论 面，为了使不具有流量控制能力的u d p 业务适合在网络上进行传输，一些基于端到端的流 量控制策略应运而生，这些方案大多使用r t c p 协议的反馈信息作为发端调整信息速率的 依据。 从总体上来看，尽管网络层的解决方案能够在宏观上对资源进行调配管理、保障传输 质量，但是受限于设备的复杂度，无法做到逐连接管理，因而无法保障端到端的服务质量。 基于终端的传输层解决方案虽然可以精细地控制每一个连接甚至每一次会话，但是由于缺 乏对网络总体状态的了解，其控制策略具有局限性和盲目性，在较大规模的应用环境中并 不能满足业务对传输质量的需求。 因特网技术的各个研究领域虽然有了较大的发展，但是由于网络复杂性和业务需求的 多样性，目前尚没有统一的构架将各个领域的技术结合起来，在实际网络中提供满意的 服务质量保障。 从1 9 8 6 年1 0 月，因特网第一次出现了严重的“拥塞崩溃，网络拥塞问题就一直困扰 着因特网。尤其是近几年来，光通信的发展大大提高了因特网的速度，但因特网的部分子 网的带宽还非常有限，中继路由器的缓存容量也十分有限，那么这些地方就有可能成为网 络瓶颈处，很容易因为带宽的有限和缓存容量的不足导致数据包的丢失，从而产生网络拥 塞。进一步导致网络吞吐量的急剧下降，从而影响整个网络的性能。 综上所述，随着信息传送量的逐渐增大和网络组成的日益复杂，网络发生拥塞的可能 性也越来越大，网络拥塞问题正逐渐成为影响网络性能的重要因素之一，如果不对网络拥 塞进行有效的控制或者在网络发生拥塞后使网络不能及时恢复到正常状态，就会造成严重 的网络拥塞。网络发生拥塞时，大量用户数据丢失，网络的吞吐量下降，用户信息传送的 时延加长，甚至导致网络崩溃。因此，网络拥塞的避免和控制成为越来越重要的急需解决 的问题，其相应的拥塞避免及拥塞控制算法的研究与改进更加重要和急迫。 网络拥塞问题的研究主要集中在t c p i p 的拥塞控制，因为在因特网中，拥塞控制的大 部分工作都是由t c p 来完成的。拥塞发生的主要原因在于网络能够提供的资源不足，满足 不了用户的需求，这些资源包括缓存空间、链路带宽容量和中间节点的处理能力等等。因 特网“尽力而为 的服务在网络资源不足时不能限制用户数量，而只能靠降低服务质量来 继续为用户服务，并且早期的t c p 协议也只有基于窗口的流量控制机制，而没有拥塞控制 机制，因而很容易导致网络拥塞。 目前，标准的t c p 协议实现都包含了一些避免和控制网络拥塞的算法。可以说，今天 因特网的成功很大程度上得益于t c p 拥塞控制算法的引进，但是，现有的标准的拥塞控制 算法都存在一定的局限性。特别是在网络环境日益变化的今天，网络的发展要求不再仅仅 2 南京邮电大学硕士研究生学位论文第一章绪论 是规模的扩大，更重要的是如何在现有的网络中增加更多的增值业务，同时对这些业务提 供必要的q o s 保障，而其中的关键是进行拥塞控制。在大量的数据报文传送时如何提高网 络的传输速率，在网络拥塞时如何有效利用网络带宽，这些都是拥塞控制机制应该解决的 问题。实践表明因特网的飞速发展也得益于t c p i p 的拥塞控制机制。t c p i p 中使用的拥塞 控制算法已经成为保证因特网稳定性的重要因素【b l 。因此，对t c p 拥塞控制算法进行进一 步的研究具有重要的理论和应用价值。 1 2 网络拥塞的基本概念 1 2 1 拥塞 拥塞崩溃最先在1 9 8 0 年中叶提出【4 】，当网络中存的数据包超过了网络的处理能力时， 会使得网络的性能下降，这种现象称为拥塞。在网络发生拥塞时，会导致吞吐量减小，如 果用户仍不断的提出对网络资源的需求，更增加了网络的负担，严重时会发生“拥塞崩溃” ( c o n g e s t i o nc o l l a p s e ) 现象，这主要是由于t c p 不必要地重传那些正在传送或己经被接收方 接收了的数据包。 我们可以进_ 步用图1 1 来描述拥塞现象。当网络负载较小时，吞吐量基本上随着负 、，一j 载的增长而增长，呈线性关系，响应时间增长缓慢。当负载达到网络容量时，吞吐量呈现 出缓慢增长，而响应时间急剧增加，这一点称为k n e e 。如果负载继续增加，路由器开始丢 包，当负载超过一定量时，吞吐量开始急剧下降，这一点称为c l i f f 。拥塞控制机制实际上 包含捐j 塞避免( c o n g e s t i o na v o i d a n c e ) 幂1 拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种策略。前者的目的 是使网络运行在k n e e 附近，避免拥塞的发生；而后者则是使得网络运行在c l i 确左侧区域。 前者是一种“预防”措施，维持网络的高吞吐量、低延迟状态，避免进入拥塞；后者是一 种“恢复措施，使网络从拥塞中恢复过来，进入正常的运行状态。 3 南京邮电火学硕上研究生学位论文 第一章绪论 捌 古l 伸 网络负载 星 留 倒 墨 网络负载 图1 1 网络吞吐量和响应时间与网络负载的关系 1 2 2 拥塞产生的原因 拥塞产生的直接原因有以下3 剧6 】： 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个端口就会建立排队。 如果没有足够的存储空间存储，数据包就会丢弃。对突发数据流更是如此。增加存储空间 在某种程度上可以缓解这一矛盾，但如果路由器有无限存储量时，拥塞只会变得更坏，而 不是更好，因为在网络里数据包经过长时间排队完成转发时，它们早己超时，源端认为它 们己经被丢弃，而这些数据包还会继续向下一路由器转发，从而浪费网络资源，加重网络 拥塞。 。 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据仙农信息理论，任 何信道带宽最大值即信道容量c = b l o g ( 1 + s n ) ( 为信道白噪声的平均功率，s 为信源 的平均功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容量c 。如果 r c ，则在理论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈， 当其满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。 处理器处理能力弱、速度慢也能引起拥塞。如果路由器的c p u 在执行排队缓存，更新 路出表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路对高速c p u 也会产生拥塞。 要避免拥塞的发生，对以上3 点原因需综合考虑。例如，提高链路速率而不改变处理 器，只会转移网络瓶颈，而不能避免拥塞。所以拥塞往往也是系统各部分不匹配的结果。 拥塞一旦发生往往会形成一个不断加重的过程。如果路由器没有空余的缓存，它就必须丢 弃新到的数据包。当数据包丢弃时，源端会超时，重传该包。由于没有得到确认，源端只 4 南京邮电大学硕士研究生学位论文第一章绪论 能保留数据包，结果缓存会进一步消耗，加重拥塞。目前在因特网( i p v 4 ) l - _ 实际使用的拥 塞控制基本上是建立在t c p 的窗口控制基础之上的。 1 2 3t c p 拥塞控制需要解决的主要问题 要改善t c p 传输的稳定性，减少拥塞的发生，或者要与非标准t c p 应用在同一网络中 共存需要采取一定的拥塞控制机制，拥塞控制机制需要解决的主要问题有： 第一、满足低的报文丢弃率的要求，提高带宽利用率。 第二、高t c p 传输的稳定性，减少网络状态的振荡。 第三j 保证t c p 公平，p , i t c p 友好特性。 1 3t c p 拥塞控制算法研究背景知识介绍 1 3 1t c p 协议简介 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 c p i p 家族的重要成员。t c p 协议主要由差错控制机制和拥塞控制机制组成，它能够自动 适应网络状况的变化。 t c p 协议引入差错控制机制的目的是保障端到端传输的可靠性，为无连接的i p 网络提 供基于连接的传输服务。事实上，i p 网络本身不能保证将数据报文无损地传输到信宿，网 络中的误码和拥塞都会导致报文在传输过程中被丢弃。为了解决这一问题，t c p 协议通过 累积确认( c u m u l a t i v ea c k n o w l e d g e m e n t ) 的方式对于报文接收情况进行监督：t c p 的发送端 采用报文序列号( s e q u e n c en u m b e d 对发送的报文进行标识，接收端采用发送确认序列号 ( a c k n o w l e d g e m e n tn u m b e r ) 对于接收到的报文进行确认( 此报文被称为应答报文，以下简称 a c k 报文) ；如果某一个t c p 报文在规定时间内未被接收方确认则说明此报文在传输过程中 丢失；t c p 发端一旦认定某报文已经丢失就会尝试重传该报文，直到此报文正确地传输到 接收端为止。 t c p 拥塞控制机制的意义更为重大，它可以根据网络状况对发送速率进行调节，避免 拥塞的扩大，这使得互联网络的正常运行成为可能。早期的t c p 协议缺少必要的拥塞控制 机制，因而由过量数据引发的拥塞极容易导致整个网络的瘫痪。为了解决这一问题，科研 工作者进行了不懈的努力：1 9 8 8 年j 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 ) 算法：1 9 9 0 年出现的r e n ot c p 版本则增 5 南京邮电大学硕士研究生学位论文第一章绪论 加了快速重传( f a s tr e t r a n s m i t ) 和快速恢复( f a s tr e c o v e r y ) 以提高t c p 传输的顽健性； n e w r e n ot c p 增加了恢复应答( r e c o v e r ya c k ) 以提高t c p 带宽恢复能力等等。经过十余年 的发展，t c p 拥塞控制算法己经拥有了多个改进版本，t c p 协议的传输性能也因此得到了 不断的提高。 由于t c p 矛n l p 报头相加后的总长度大于4 0 字节，为了提高传输效率，t c p 终端把待发 送数据收集至缓冲区中，使之汇聚成较大的片断( s e g m e n t ) ，然后逐片断进行发送。这样， 实际当中t c p 连接所传输的报文长度往往是相等的，其长度被称为最大报文发送长度 ( s e n d e rm a x i m u ms e g m e n ts i z e ) 。当然，t c p 发端的缓冲处理在提高传输效率的同时也会引 入附加时延，这对于某些对传输时延敏感的数据业务来讲是不可接受的。为了解决这一问 题，t c p 协议添加了p u s h 操作，该操作会强锘i j t c p 终端在缓冲区未满的情况下直接发送报 文，从而提高了t c p 协议的实时性能。 1 3 2t o p 拥塞控制算法概述 t c p 协议所采用的拥塞控制算法本质上是一种窗1 3 上限可变的滑窗( s l i d i n g w i n d o w ) 式流量控制方法，是对滑窗流控算法的继承和发展。 传统的滑窗式流控算法的窗口上限是固定的，发端每发送一个报文其发送窗口减小一 个单位，而每接收到一个报文的确认发送窗口增加一个单位，这样终端一个轮次中能够发 送报文的最大个数是确定的，因此，在链路带宽充足的情况下，发端的传输能力将受到发 送窗口上限的限制。t c p 流控算法对滑窗算法进行扩展，根据网络状况对窗口上限进行调 节。在t c p 算法中，窗口上限由发送端的发送窗口和接收端的广播窗口共同决定( 取两者中 的最小值) 。这样，在网络正常工作时，t c p 发端可以通过增大窗口上限尽可能多地占用网 络空闲带宽；而当网络发生拥塞时，t c p 发端可以通过减小发送窗口上限的方式降低发送 速率从而起到缓解拥塞的作用。 t c p 协议采用滑动窗口( 单位为字节) 对流量进行控制。由于滑动窗口大小的设定与网 络传输情况和接收端缓冲区的大小有关，因1 1 3 5 t c p 拥塞控制算法的特点就在于滑动窗e l 上 限的设定方式和修正策略。不同版本的t c p 拥塞算法具有不同的窗口调整策略，但绝大多 数版本的t c p 算法都采用了加增长乘减小a i m d ( a d d i t i v ei 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 e ) 的思想对窗口进行调整。一般来说，t c p 算法在通信建立之初采用倍增发送窗口的方式迅 速占用空闲带宽，这一过程被称为m 匣启动”阶段；在慢启动完成后，t c p 算法通过线性 增加发送窗口的方式( 加增长) 在充分利用带宽的同时避免拥塞发生，此阶段被称为“拥塞 6 南京邮电大学硕士研究生学位论文 第一章绪论 避免”；当网络拥塞引起报文丢失时，t c p 终端将把发送窗口减半( 乘减小) ，并重传被网 络丢弃的报文，这被称为“恢复”阶段。 1 3 3 拥塞控制算法的必要性 根据f l o y d 的定义，拥塞控制算法是一个基于网络上的具有相互竞争关系的用户上运行 的分布式算法，该算法用于在竞争用户之间合理分配网络资源。由于网络中可用资源和竞 争情况的随机性，如何有效地分配资源非常重要。拥塞控制算法正是各个网络用户用来依 据网络环境变化所提供的反馈信息自适应地调整其网络行为，以达到整个网络系统的最佳 运行性能的分布式算法。 此外，网络系统中的一些网络节点( 如路由器) 也参与到这种调节行为中来，所以，整 个算法体系包含两部分，发送方和接收方上的t c p 算法，以及链路上( 如路由器) 的a q m 算 法，在本论文中，我们的讨论重点将放在t c p 拥塞控制算法上。 1 4 传统拥塞控制算法的局限性 网络中的拥塞来源于网络资源和网络流量分布的不均衡性。拥塞不会随着网络处理能 力的捉高而消除。拥塞控制算法的分布性、网络的复杂性和对拥塞控制算法的性能要求又 使拥塞控制算法的设计具有很高的难度。 随着i n t e m e t 的发展，其拥塞控制机制也应该不断改进以适应网络的发展。技术的发 展趋势预示着未来的网络将包含了极多的高带宽的链路，同时还会出现越来越多的卫星及 无线通信等高延迟的网络。数学分析表明，不管采用何种队列机制，传统的t c p 拥塞控制 算法都将无法适应这些高带宽或高延迟的情况。 传统的t c p 拥塞控制算法在高带宽的网络上不仅会不稳定，而且其性能也会下降。由 于采用加性增长机制，传统的t c p 拥塞控制算法在每个础 t 中增加发送的包过于缓慢，这 在高带宽的网络环境下会浪费若干r t t 才能充分利用网络带宽。另外，当在卫星通信和无 线w a n 中的流数目增加时，公平性也会上升为一个严重的问题。 本文将着重讨论高速网络环境下传统t c p 拥塞控制算法的改进方案h i g h s p e e dt c p 算 法的性能以及其改进方案。 7 南京邮电人学硕士研究生学位论文第二章高速t c p 算法简介 2 1 问题的提出 第二章高速t c p 算法简介 2 1 1 传统t c p 的局限性 传统t c p 所采用的拥塞控制算法已经被广泛地应用到互联网上。实践证明，当其应用 于低带宽环境下的数据传输时，能够满足应用对吞吐量的需求。然而，当它应用于在高带 宽环境下的数据传输时( g b i t 以太网数据备份，数据库同步) ，由于传统t c p 协议自身的问题， 吞吐量往往因此不能达到应用的实际需求。s f l o y d 对r e n ot c p 的拥塞控制算法进行了 研究【1 6 1 ，得出了吞吐量，包丢失时间间隔，平均拥塞窗口大小，包丢失率间的关系： i = b r ( 1 2 d ) ( 2 1 ) w = b r ( 8 d ) ( 2 2 ) ：尸二。1 5 w 2 ( 2 3 ) 其中，表示丢包事件间隔的r t t 的个数，口表示吞吐量，斤表示网络延迟，刃表示包的 大小，表示平均拥塞窗口，尸表示稳定状态下的包丢失率。根据上述3 个公式，可以得 到吞吐量、包丢失间隔、平均拥塞窗口和包丢失率的几组关系，如表2 1 所示。 表2 1r e n ot c p 吞吐量，包丢失间隔，平均拥塞窗口大小，包丢失率之f f i 】的关系 ( 包大小为1 5 0 0 字节，往返时延为l o o m s ) t c p 吞吐量包丢失间隔平均拥塞窗口大包丢失率 ( m b p s ) ( r 1 v r 个数)小( 报文段个数) l5 58 3o 0 2 1 05 5 58 3 30 0 0 0 2 1 0 05 5 5 58 3 3 30 0 0 0 0 0 2 1 0 0 05 5 5 5 58 3 3 3 30 0 0 0 0 0 0 0 2 1 0 0 0 05 5 5 5 5 58 3 3 3 3 3o 0 0 0 0 0 0 0 0 0 2 根据表2 1 ，如果在1 0 g b p s 的在高速链路上，使用传统t c p ( r e n ot c p ) 进行通讯，其 每个包的大小为1 5 0 0 字节，往返时间r t t 为1 0 0 m s ，那么所需要的平均拥塞窗口大小为8 3 3 3 3 个报文段长度，其对应的包丢失率必须低于2 1 0 1 0 ，该包丢失率大大低于目前路由水平和 8 南京邮电人学硕士研究生学位论文第二章高速t c p 算法简介 光纤所能达到的包丢失率。而且，网络上发生丢包事件后，需要经过5 5 5 5 5 5 个r t t ，也就 是需要经过5 5 5 5 s 才能恢复到拥塞前的吞吐量。这样的恢复速度在实际使用过程中是不可 忍受的，且由于网络数据流量的突发性，要在5 5 5 5 s 内保持良好的网络状况也是不现实的。 因此，目前所采用的标准t c pr e n o 无法在高速大时延环境下获得高的吞吐量，其主要原因 在于在拥塞避免阶段，每个r t t 的时间间隔仅增长一个数据段大小太慢了，而在丢失每个 报文段时倍数级的减小又太快了。 2 1 2hig h s p e e dt c p 的弓i 入 基于上一节传统t c pr e n o 在高带宽大时延环境下的局限性，s f l o y d 在2 0 0 3 年1 2 月正 式提出 h i g hs p e e dt c p 算法【l 】。h i g hs p e e dt c p ( 下面简称h st c p ) 的目的主要是通过对 传统t c pr e n o 的修改，在高带宽大时延网络环境下达到尽可能大的吞吐量。h st c p 的基 本思想是在拥塞避免阶段采用不同的窗口大小控制机制。和t c pr e n o 相比，h st c p 在拥 塞窗口的增加上更加迅速，而在拥塞窗口的减少上更为缓慢，并最终保持一个比较大的拥 塞窗口以充分利用网络的带宽。 2 2i et c p 的拥塞控制算法描述 为了克服传统t c p 在高速环境下的局限性，提高t c p 连接的吞吐量，就必须改进t c p 在高速网络环境下的拥塞控制算法，当网络带宽充分的时候拥塞窗口采用更为快捷的增长 策略，当网络发生拥塞的情况下采用较为缓和的递减策略。高速t c p 协议( h i g hs p e e dt c p ) 的i d 策略( i n c r e a s i n g d e c r e a s i n g ) 与传统t c p 相同点在于，都是基于加法增加乘法递减 ( a i m d ) 模型的，不同的是两者在拥塞避免阶段每个r t t 选用的i d 参数不同。 与传统的t c p 拥塞控制算法相同，高速t c p 的拥塞控制也是由报文段丢失事件触发。 为了方便介绍，我们根据拥塞事件发生的频度将高速t c p 划分为若干循环周期：定义从第 ( ，一1 ) 个包丢失事件开始到第i 个包丢失事件结束的这段时间为第f 个循环周期，定义第f 个循环周期的第，个r t t 的拥塞窗口为w h s ( i ，j ) 。 高速t c p 使用一组参数来描述，如表2 2 所示。 9 南京邮电大学硕士研究生学位论文第二章高速t c p 算法简介 表2 2 高速t c p 参数列表 参数名称参数含义 口( 川 拥塞避免阶段的拥塞窗口增加因子 6 ( 检测到包丢失后的拥塞窗口减小因子 b h l 咖 在高带宽环境下的递减系数 圪础对应于拥塞窗口动的丢包率 进入高速t c p 的阈值 磷 高带宽所要求的平均拥塞窗口 s h s ( o 第j 个循环周期的慢启动阈值 为了保持与传统t c p 协议的兼容性，高速t c p 根据当前拥塞窗口与高速t c p 阈值之间 的关系，选用不同的i d 策略：如果当前的拥塞窗口小于高速t c p 阈值，高速t c p 采用和传 统t c p ) f 目同的捌塞窗口i d 策略；如果当前的拥塞窗口大于高速t c p 阈值，就采用更快捷的 拥塞窗口递增策略和更缓和的拥塞窗口递减策略。由于t c p 拥塞控制工作在自时钟 ( s e l f - c l o c k i n g ) 方式，每个事件( 例如发送数据包或计算超时) 都完全由过去决定，即系统的 未来可以由过去描述。拥塞窗口的i d 程度取决于当前的拥塞窗口值：如果拥塞窗口的值较 大，高速t c p 增加的就较快，递减的也更慢。根据上述改进原则，高速t c p 可以达到更高 的平均拥塞窗口值，因此能够获得较传统t c p 更高的吞吐量。 在每个r t t 中，高速t c p 的拥塞窗口递增因子为口( 叻，递减因子为6 ( 川。也就是说， 如果当前拥塞窗口值为w ，经过一个r t t ，在没有丢包的情况下，高速t c p 增加拥塞窗口 值为 w + 口( w ) w 当接收到拥塞事件，如收到3 个重复的a c k 后，将拥塞窗口的值递减为 w ( 1 6 ( w ) ) 高速t c p 在慢启动和拥塞避免阶段的公式描述如下： 当每个a c k 应答到来的时候，h st c p 增加它的拥塞窗口值w 为： ：w 卜w + 盟 ( 2 4 ) w 当拥塞事件发生时，h st c p 减少它的拥塞窗口值w 为： 1 0 南京邮电大学硕士研究生学位论文第二章高速t c p 算法简介 w 卜w ( 1 - b ( w ) ) 其中，a ( w ) 和6 ( 们的值分别为： ( 2 5 ) 口( 叻= 1 2 w 2 b 百( w ) p ( w ) ( 2 6 ) 怫c 分o s ，嚣鬻+ o 5 ， 其中，历衲呒，劝和为h st c p i 拘参数。 在公式( 2 6 ) 和公式( 2 7 ) 中，反枘，呒动和形o w 的典型值分别为o 1 ，8 3 0 0 0 和1 3 8 。 h st c p 如果在低于或高- 于s h s 时收到超时报文段时间，其处理方法与传统t c p 相 同，都是在重传定时器超时后，将慢启动阈值和拥塞窗口值设为当前值的一半，然后开始 下一轮的拥塞控制。 图2 1 显示了口( 们和6 ( w ) 如何随着拥塞窗口变化的。其中我们可以清楚的看到，随着 拥塞窗口的增大，递增因子a ( w ) 不断变大，而递减因子b ( w ) 不断变小。通过这种方式， h st c p 可以保持一个比较大的拥塞窗i z l 并充分利用网络的带宽。 a ( 讷6 0 4 d i = ：器 l _ 一 。f i | ，一 |。 、 ， 、 、 、 _ 。- - 拥塞控制窗口( p k t s ) 图2 1 口( w ) 和6 ( 们随拥塞窗口变化曲线图 南京邮电大学硕，l 二研究生学位论文 第二章高速t c p 算法简介 2 3h st c p 的响应函数 响应函数反映了在每个r t t 中，平稳状态下的包丢失率和t c p 平均发送率即平均拥塞 窗口大小的数学关系。传统t c p 拥塞控制算法的响应函数为： 1 ， w = ，= 二 ( 2 8 ) 4 p ( w ) 表示了以m s s 标准大小的报文段为单位的平均拥塞窗口大小与稳定状态下的平均丢 包率p ( w ) 之间的函数关系。该t c p 响应函数是t c p 的a i m d 机制的直接体现( a i m d ，u p o n 性增长乘性减少，在没有拥塞发生时，拥塞窗口每个r t t 增加一个报文段大小，并在拥塞 事件发生时让拥塞窗口随着r t t 乘性减少) 。表2 3 反映了理论上标准t c p 在包丢失率约为 1 0 一2 的常见网络环境下的响应函数。在通常情况下，拥塞窗口的变化范围一般是平均拥塞 窗口的2 3 至4 3 ，而标准t c p 下丢失事件的间隔时间一般为2 3 个r t t 。 表2 3 包丢失率p ，拥塞窗口形，丢失事件间隔对应表 包丢失率p 拥塞窗口大小丢失时间间隔( r r t ) 1 0 一2 1 28 1 0 - 3 3 82 5 1 0 - 4 1 2 08 0 1 0 一5 3 7 92 5 2 1 0 “ 1 2 0 08 0 0 1 0 3 7 9 5 2 5 3 0 ， 1 0 1 2 0 0 08 0 0 0 1 0 9 3 7 9 4 82 5 2 9 8 1 0 一1 0 1 2 0 0 0 08 0 0 0 0 t n t q 绍h st c p 的响应函数。我们先定义三个参数：j 呒劬和e 劝，意义分别为 进入高速t c p 的阈值，高带宽所要求的平均拥塞窗口和表示对应于拥塞窗口恸的丢包率 ( 见表2 2 ) 。考虑到兼容性问题，当目前的拥塞窗口尚未达到时，h st c p 的响应函数 1 2 南京邮电人学硕上研究生学位论文第二章高速t c p 算法简介 和上述标准t c p 的响应函数相同；当拥塞窗口超过时才采用自己的响应函数。在s f l o y d l 拘r f c3 6 4 9 q h ，被设为3 8 个报文段长，对应了一般典型的t c p 包丢失率1 0 一。为 了确定h st c p i j 向应函数的上限值，我们假定h s t c p 取得的平均拥塞窗口大小为8 3 0 0 0 个报 文段，这个数据大约是在默认的包大, j , $ - l j r t t - f ，保持l o g b p s 的吞吐量所需要的窗口大小。 当动为8 3 0 0 0 1 j v j ，我们规定咒劝值为1 0 ；也就是说在1 0 7 的包丢失率下我们允许h st c p 达到8 3 0 0 0 报文段的拥塞窗1 2 1 。r f c 3 6 4 9 之所以如此设定，是因为，当h st c p 和传统t c p ( 丢 包率1 0 _ 4 至1 0 。5 ) 共存的情况下，在可以接受的公平性范围内，h st c p 在完全利用高速网 络带宽的同时有能力达到1 0 。7 的丢包率水平。 为了简单起见，h st c p 的响应函数和传统t c p 一样，在对数二维坐标上保持线性特性。 r f c 3 6 4 9 定义在拥塞窗口大于的情况下响应函数为： w ：譬既。 ( 2 9 ) 圪。” 、。 且当p 为时候w 为上式中s 定义如下： s = ( 1 0 9 w h 动一l o g w t o 。) ( 1 0 9 p h 动一l o g 圮。) 所以，根据我们在前面提到的网络环境，即为3 8 ，为1 0 ；当呢动为8 3 0 0 0 ， 动为1 0 。7 时，我们能得到下面的公式： w = 而0 萨1 2 ( 2 1 c 0 ) w = ：斋f 2 1 ) p ( w ) u ” 、 表2 4 反映了上述公式得出的形和p ( w ) 的对应关系，其中对于h st c p 而言，当拥塞窗 口大于3 8 个报文段时，包丢失事件的间隔为1 ( p ( w ) w ) ，也可以记为1 2 7 w 仉2 。 1 3 南京邮电大学硕士研究生学位论文第二章高速t c p 算法简介 表2 4 包丢失率p ，拥塞窗口w ，丢失事件间隔对应表 包丢失率p 拥塞窗口大小形丢失时间间隔( r t t ) 1 0 一2 1 28 1 0 一3 3 82 5 1 0 - 4 ： 2 6 33 8 1 0 一5 1 7 9 55 7 1 0 巧 1 2 2 7 98 3 1 0 7 8 3 9 8 l1 2 3 1 0 - 3 5 7 4 3 5 61 8 0 1 0 9 3 9 2 8 0 8 82 6 4 1 0 1 0 2 6 8 6 4 6 5 33 8 8 根据h s t c p 的响应函数，我们又可以得到其反函数： ，、0 0 7 8 p ( w ) = 了广 w 1 + 。 1 0 0 0 0 0 1 0 0 0 0 10 0 0 10 0 10 1 e 1 01 e - 91 e 一81 e 一71 e 61 e 51 e 一41 e 30 0 1 0 1 包丢失率p 图2 2h s t c p 的响应函数图 ( 2 1 1 ) 从图2 2 中我们可以看到，h s t c p 与t c pr e n o 相比，前者在包丢失率和拥塞窗口大小 _l_l芟d)辟躐毅蜒 南京邮电人学硕士研究生学位论文第二章高速t c p 算法简介 之间的限制更加宽松。例如，当包丢失率p = 1 0 - 7 进入稳定状态时，h s t c p 的包发送速度能 达到8 3 0 0 0 p k t s r t t ，而t c pr e n o 只能达到大约4 0 0 0p k t s r t t 。显而易见，h s t c p 即使是 在高丢失率的网络下仍然能获得较大的拥塞窗口。 2 4 高速网络环境下其他拥塞控制算法简介 针对高速网络下传统t c p 的缺陷，业界还提出了除h st c p 以外的其他几种高速网络环 境下的拥塞控制算法： 2 4 1f a s tt o p f a s tt c p 6 1 的体系结构如图2 3 所示，包