改进的TCP拥塞控制慢启动策略及仿真.doc

第8A期杨喜权等：改进的TCP拥塞控制慢启动策略及仿真171改进的TCP拥塞控制慢启动策略及仿真杨喜权1，闫洪森2，王大勇1(1.东北师范大学 计算机学院，吉林 长春 130024;2.长春大学 电子信息工程学院，吉林 长春 130022）摘 要：针对现有TCP拥塞控制算法的慢启动策略会使拥塞窗口呈指数级增长，导致一个窗口中出现多个包丢失的情况，提出了一种能使拥塞窗口平滑地增长到慢启动阈值的新策略。该策略实现连接的平滑接入并能相对平滑的过渡到拥塞避免阶段。通过NS2仿真，新策略不仅能明显减少丢失包的数量还能有效地管理路由器缓冲区中的队列。关键词：自相似；TCP拥塞控制；慢启动；NS2中图分类号：TP39 文献标识码：A 文章编号：1000-436X(2007)8A-0168-04Improving and simulating of slow-start for TCP congestion control schemes using NS2YANG Xi-quan1, YAN Hong-sen2, WANG Da-yong1(1.School of Computer Science, Northeast Normal University, Changchun 130024, China;2.Electronic Information Institute, Changchun University, Changchun 130022, China)Abstract: The current slow-start of TCP congestion control schemes was presented. A new strategy was presented to improve the old slow-start. It can increase the congestion window gradually. And the simulation results of the NS2 show that modified conventional congestion control algorithm not only reduce packet loss but also will be the good helper for the solution of unfairness to long RTT and burstization of traffic , the stability of the TCP protocol and network utility was improved.Key words: self-similar; TCP congestion control; slow-start algorithm; NS21 引言收稿日期：2007-06-12基金项目：国家自然科学基金资助项目（60473042）Foundation Item: The National Natural Science Foundation of China (60473042)计算机网络是当今社会生活中的一个重要组成部分。其中TCP拥塞控制是Internet稳定发展的重要因素。自从Internet首次发生崩溃以来1，这20年的时间里，人们对TCP拥塞控制进行了深入而广泛的研究25，提出了各种TCP拥塞控制算法，如确认ACK算法、队列控制算法、时延RTT算法等。虽然TCP拥塞控制算法种类繁多，但大体上由4个算法组成6： 慢启动、拥塞避免、快速重传和快速恢复。 上述算法的基本思想是1988年 Jacobsons 提出的AIMD7(additive increase and multiplicative decrease)。当时网络的数据流量少而且单一，今天网络流量增长迅猛并且种类多样。根据数据传输连接所经历的时间长短将连接分为长生存期连接和短生存期连接。研究表明8，Internet中的数据传输大多数是短生存期连接（如WEB）,但是数量占少数的长生存期连接（如FTP）则传送了大部分的数据量。短的连接往往在还没有进入稳定状态就已经终止，这就意味着短连接经常处于慢启动阶段。所以说，慢启动机制的性能直接影响了短连接的传输效率。对于长生存期的连接，慢启动机制作用于连接启动阶段和分组超时的重传阶段，所以慢启动机制的性能对长连接也有一定的影响。因此，改善和提高慢启动的性能对于提高Internet的性能具有重要的意义。本文将分3个部分对慢启动进行研究，首先从理论上说明TCP流的自相似特性，其次分析现有算法及其缺点并提出一种改进的慢启动策略，最后通过网络仿真软件NS2对新策略进行仿真并与原算法在某些性能方面进行比较。2 TCP流自相似特性利用ON/OFF模型从理论上解释TCP拥塞控制机制导致自相似现象的原因。通常TCP流是由N个(N=1,i,N)源聚合的ON/OFF过程，单个源i的窗口对应于第i个ON/OFF过程，那么在ON期间内，以某个速率发送个分组，而OFF期间则对应于没有分组发送的期间。如果ON/OFF持续时间具有重尾分布,则互补累积分布函数(CCDF)Fc(x)为Fc(x)lx- L(x)，l0是常数，L(x)表示慢变函数。假设这N个ON/OFF过程互相独立，设F1c(x)，F2c(x)，1(x)，2(x)，12，22表示互补累积函数CCDF，ON/OFF持续时间的均值s(x)和方差s2。这里的s表示两个状态ON和OFF。则有F1c(x)l1x-1L(x)，l0；F2c(x)l2x-2L(x)，l0。因为L(x)表示慢变函数，则当t0时，有设A=t2-111，则0A，设min=1=2,，L=L2；当A=0或时，L=Lmin这样当T和N较大时，在0，Tt时间内累积的流量其统计特性为当N，T趋于无穷时，聚合流量表示为其中H=(3)/2，表示分形布朗运动。这表明当无限多个独立的有重尾分布的ON/OFF过程的叠加弱收敛于分形布朗运动,因而表现出自相似性。3 一种改进的慢启动策略慢启动有效避免在连接建立时向网络发送过多的分组而导致不必要的分组丢失和产生网络拥塞。慢启动在连接建立阶段和分组传输超时的重传阶段被触发。建立连接后，源将拥塞窗口cwnd(congestion window)初始化为一个分组大小，当这个分组的确认信号到达源时，TCP将cwnd加1，然后发送两个分组，再次收到这两个分组的确认后cwnd加2，然后发送4个分组。这样使TCP在每个RTT(rount-trip time)内将传送的分组加倍。最终这种方法将会导致窗口在很短时间内就会达到网络允许的最大带宽，然后将触发第二种使用慢启动的情况，此时将最近一个分组丢失前的cwnd作为ssthresh（拥塞阈值）。然后cwnd被重置为一个分组，以后就以指数方式增长直到再次发生拥塞，进而进入拥塞避免阶段。慢启动的本意是避免在连接建立后由于产生突发数据流量而导致拥塞。但认真研究慢启动算法后可以发现按照cwnd的指数增长方式到了后期会一次性发送过多的分组，产生比较大的数据流，导致拥塞的发生。针对TCP流的自相似性和慢启动存在的问题，我们提出一种改进的慢启动算法。原来的方法是以指数方式增长到ssthresh，现在将这个过程分为两个阶段，第一个阶段是按照原来的指数方式增长到ssthresh/2；第二个阶段是采用二分法的思想使拥塞窗口(cwnd)增长的速度降低，越到后期增长的越平缓。具体是：拥塞窗口增长到ssthresh/2后，让cwnd的值等于(cwnd+ssthresh)/2，可以得出cwnd每次增加的值cwnd=(ssthresh-cwnd)/2，cwnd将会随着cwnd的增大而减小，也就是说，越到后期，每个RTT时间内向网络中注入的数据流量的增量越小，发生拥塞的可能性也越小，该算法描述如下：for every ACK if (cwnd ssthresh/2 & cwnd ssthresh)cwnd = (cwnd+ssthresh)/2;下面从理论上来比较标准慢启动和改进的慢启动的窗口变化情况，为了比较的方便我们假设所有的分组都能正确应答，也就是假设在此过程中没有发生拥塞。同时还要假设所有的RTT均相当。如图1所示，拥塞窗口cwnd从1到ssthresh/2这个过程是这两种方法共同经过的阶段。加粗的曲线表示标准慢启动的拥塞窗口从ssthresh/2增长到ssthresh的过程。虚线表示改进后的慢启动算法拥塞窗口的增长过程。可以看出标准慢启动的窗口在一个RTT内的最大增量是ssthresh/2，在第n个RTT内也增长了ssthresh/4。现在的高速网络的拥塞窗口都比较大，使用标准慢启动算法的网络的突发流量将对网络的稳定性造成极大影响，导致分组丢失的加快，网络性能大幅下降。而观察虚线可以发现，在一个RTT内窗口的最大增量是ssthersh/4，之后窗口每次的增量是前一个窗口增量的1/2，即ssthresh/8，ssthersh/16。由此可见，改进的算法越到后期窗口的增量越小，产生突发数据流的可能性也越小，这样发生拥塞的可能性就会降低，在一定程度上提高了网络的性能。与原有慢启动算法相比，新算法有几个如下的优点：1) 减少网络中的突发数据流量，并减小了瞬时负载。图1 拥塞窗口的变化比较2) 虽然不能完全避免拥塞的发生，但由于cwnd在后期增长的速度趋于缓慢，所以可以延迟拥塞的发生。3) 使慢启动阶段的分组丢失数量减小，降低了路由器缓存溢出的风险。4 NS2仿真与性能分析为了验证改进慢启动算法的性能，利用NS29进行了性能仿真。网络拓扑结构如图2所示。这是一个单瓶颈链路的拓扑结构，其中S为源端，RE为接收端，源端链路L1和接收端链路L2带宽为10Mbit/s，延迟分别为2ms和3ms,与路由器分别相连。假设有N个连接经过一段共享链路，路由器R1、R2构成的链路L3为这N个连接的共同瓶颈。L3带宽为1.5Mbit/s延迟45ms。分组大小为1024Bytes，路由器的缓存为20个分组大小，仿真以FTP作为数据流。图2 网络拓扑结构在仿真中采用的是已经得到广泛使用得Reno算法，路由器队列管理采用的是常见的DropTail分组丢弃策略。仿真开始后对FTP持续发送1Mbit/s的数据进行仿真，分别比较了在不同连接数的条件下，原有慢启动算法与改进过的算法在分组丢弃以及路由器队列管理方面的性能。图3表示了不同连接数条件下分组的丢失情况，可以看出改进后的算法在减少分组丢失方面有一定的改善。由于丢弃分组的减少，重传及超时也会随之减少，并能减小网络的负载，进而可以提高网络传输的性能。最后，将路由器管理策略从DropTail改为RED10(random early detection)。图4表示了两种算法在仿真过程中路由器上缓冲区瞬时队列长度的比较。可以看出新的算法在改善队列管理性能方面也有所提高。降低了缓冲区中的队列长度，有效地减少了丢弃分组。图3 分组丢弃数比较图4 路由器缓冲区队列比较5 结束语随着网络用户的迅猛增长，当网络流量超过网络的容量时不仅有效地进行拥塞控制,而且提高拥塞控制的质量。因此，对传统慢启动算法进行了改进，以提高网络拥塞控制的动态性和自适应性。本文提出的一种改进的慢启动算法可以有效地减小网络拥塞时的丢包率。该算法通过调整拥塞窗口的增长方式，将拥塞窗口的后期增长与拥塞避免阶段进行平滑过渡，有利于网络的拥塞控制，并通过NS2仿真证明了该算法的有效性。参考文献：1JACOBSON V. Congestion avoidance and controlJ.ACM Computer Communications Review, 1988, 18(4): 314-329.2FALL K, FLOYD S. Simulation-based comparisions of tahoe, reno and SACK TCPJ. Computer Communication Review,July 1996, 26(3):5-21.3CHEN J, ZHENG M C, MENG Q. A network congestion control algorithm based history connections and its performance analysisJ.Journal of Computer Research and Development, 2003, 40(10): 1470-1475.4WANG H, XIN H, REEVES D S, et al. A simple refinement of slow2start of TCP congestion control C . Sherif, S H, ed Proceedings of the IEEE Symposium on Computers and Communications (ISCC 2000). Los A lam ito s, CA: IEEE Computer Society, 2000.5BRAKMO L S, PERTERSON L LTCP vegas；end-to-end congestion avoidance on a global InternetJIEEE Journal on Selected Areas in Communication, 1955. 6林闯，罗万明. TCP IP 拥塞控制研究J.计算机学报，2001, (1)：218-224.LIN C, LUO W M. Study on TCP/IP congestion control J. Journal of Computer Science, 2001, (1): 218-224.7CHIU D, JAIN R. Analysis of the increase and decrease algorithm for congestion avoidance in computer networksJ. Journal of Computer Networks and ISDN, 1989, 17(1): 1-14.8THOMPSON K, MILER G J, WILDER R. Wide-area Internet traffic patterns and characteristics J. IEEE