TCP拥塞控制算法研究

文章编号:1006-9348(2010)10-0124-04

计󰀁算󰀁机󰀁仿󰀁真

2010年10月󰀁󰀁

TCP拥塞控制算法研究

代丽娴,黄宏本

(广西梧州学院计算机科学系,广西梧州543002)

摘要:研究无线传输优化问题,随着用户的迅速增长,使网络负载大于网络资源容量,引起拥塞、传输延时和丢包等问题。采用传统的TCP拥塞控制算法,使网络发生拥塞的可能性增大,甚至导致网络崩溃。为了解决当前的网络拥塞问题,提出了一种改进的TCP拥塞控制算法。算法根据网络拥塞跟回路响应时间的大小成正比的关系,在源端检测回路响应时间值,同时在网络拥塞产生的临界区域,采取拥塞窗口线性减小的方法,使网络远离该区域,大大降低了拥塞产生概率,避免了传统TCP算法中拥塞窗口值得大幅振荡。经仿真证实:算法比传统TCP算法有较低的丢包率,且吞吐量得到了较大的提高,改进算法能够在一定程度上缩短拥塞恢复时间,降低网络的振荡,提高网络的传输质量。关键词:拥塞控制;丢包率;吞吐量中图分类号:TP393󰀁08󰀁󰀁文献标识码:B

ResearchonTCPCongestionControlArithmetic

DAILi-xian,HUANGHong-ben

(DepartmentofComputerScienceandTechnology,WuzhouBranchGuangxiUniversity,

WuzhouGuangxi543002,China)

ABSTRACT:ThereisalotofcongestionphenomenonintheInternet.Aimatthat,weneedsafe,reliableQualityofServiceintheInternet.BasedonstudyingtheprincipleofTCP/IPcongestioncontro,lthispaperanalysesaRTT-basedarithmeticforsolvingthecongestioncontro.lInviewofthepossibilityofcongestionwiththeRTTincrease,thearithmeticjoinsthesideonthedetectionofRTTvalues,andinaccordancewiththerelevantpolicycontrolcwndval󰀂uewithinreasonablelimits.UsingNS2,thisarithmeticislowerpacketlossratesthanTCPbyobservationanalysis.ItcanimprovethethroughputoftheTCPconnectionandavailablebandwidth.Thenanalysisofresultprovesthatthenovelcongestioncontro1algorithmcanspeedcongestionrecoverycontrolonacertainextent,anddecreasethevibra󰀂tion.

KEYWORDS:Congestioncontro;lPacketlossrates;Throughput

题,吞吐量往往不能达到应用的实际需求[2]。其中的TCP

1󰀁引言

因特网的迅速发展带来了严重的网络拥塞问题。其根本原因在于用户提供给网络的负载大于网络资源容量和处理能力,网络拥塞发生时,一般会出现数据包时延增加,丢包概率增加,网络吞吐量下降,网络效率下降,严重的网络拥塞会造成网络拥塞崩溃[1]。

TCP/IP协议所采用的拥塞控制算法是保证当今网络不断发展同时又避免拥塞崩溃的主要方法,传统TCP所采用的拥塞控制算法已经被广泛地应用到互联网上。然而,当它应用于高带宽环境下的数据传输,由于传统TCP协议自身的问

基金项目:2006年广西教育厅科研项目(187)收稿日期:2010-05-08󰀁修回日期:2010-06-17

Reno算法是目前网络上广泛应用的算法[3],由于TCPReno在拥塞发生之后进行处理,不能有效地预防网络拥塞的发生,此外,TCPReno总是尽可能多地增加拥塞窗口来占有带宽,其拥塞窗口从一个报文段丢失恢复到最大值需要多达几十秒钟的时间,这样带宽利用率相当低,随着网络带宽的增大,TCPReno机制方法已经越来越不能适应网络的变化了[4,5]。

针对传统的TCP拥塞控制算法的不足,本文提出一种基于回路响应时间的TCP拥塞控制算法。该算法根据拥塞产生与回路响应时间(RTT)的大小成正比的关系,由源端检测RTT的值,采取相关的策略控制拥塞窗口值在合理范围内振动,使网络远离拥塞产生的临界区域,降低了拥塞产生的可能性并易于摆脱拥塞。

󰀂124󰀂

塞,但cwnd的振荡幅度较大,造成了网络资源的浪费。针对

2󰀁网络拥塞控制

2.1󰀁网络拥塞控制原理

拥塞的发生如图1所示,当负载较小时,吞吐量的增长和负载相比基本呈线性关系,延迟增长缓慢;在负载超过膝点之后,吞吐量增长缓慢,延迟增长较快;当负载超过崖点之后,吞吐量急剧下降,延迟急剧上升。可以看出,负载在膝点附近时网络的使用效率是最高的。

传统TCP存在的上述问题,本文从网络拥塞的预防、发现、处理、恢复五个方面对网络拥塞控制算法进行改进,具体改进如下。

3󰀁TCP拥塞控制算法的改进

3.1󰀁拥塞的预防

在慢启动阶段,将拥塞窗口设置为1并呈指数级增长,经过一段过程才恢复到原有的吞吐率。这种特性对大延迟链路上的短小TCP流不公平而对大容量的网络却造成浪费。针对此问题,本文采用解决方法为用大的初始窗口,避免延迟ACK机制下单个报文段初始窗口的等待超时问题,缩短小TCP流的传输时间和大延迟链路上的慢启动时间。3.2󰀁拥塞的发现

传统TCP拥塞控制算法通过数据超时或收到3个相同ACK确认帧来发现拥塞。发送端设置一个超时重传定时器

图1󰀁负载与吞吐量间的关系曲线

(RTO),发送一个报文后,在一个RTO时间段内,若没有收到ACK,则认为报文丢失,拥塞发生。RTT(回路响应时间)是TCP协议的重要参数,也是影响DiffServe网络的拥塞控制和带宽保证的重要因素[9]。研究表明,在TCP网络中,假定TCP处于拥塞避免状态,TCP流实现的带宽:

RA=

c∀MsstRtt∀P(1)

拥塞发生的根源是 需求!大于 供给!,网络中有限的资源要由多个用户共享,源端的重传分组策略又会加重网络负担,而这样恶性循环的结果必定是网络性能的严重下降。拥塞控制的概念正是基于这种情况下被提出,用来控制网络流量,使网络的吞吐量达到一个最大的平衡值,使整个网络的性能达到最佳,并且保持稳定。2.2󰀁传统TCP拥塞控制

TCP/IP的拥塞控制分2个部分:TCP(传输层)的拥塞控制和IP(网络层)的拥塞控制。目前的Internet使用建立在TCP的窗口控制基础的拥塞控制。为避免网络数据的突发性导致网络拥塞、报文的丢失,TCP中设置了拥塞窗口机制

[6]

式中,c为常数;RA为测量带宽;Mss为数据包的尺;P是该数据包的丢失概。

从式(1)可知,拥塞的产生与RTT的大小密切相关,而且拥塞产生随RTT的增加而增大,呈正相关。所以本文通过在TCP拥塞控制算法的慢启动与拥塞避免两个阶段,加入源端对RTT值的检测,通过RTT的变化情况来决定cwnd的大小。即检控RTT的值,在拥塞可能产生的临界区域,采取降低cwnd值的方法,使网络逐渐远离该区域,从而降低拥塞产生的可能性。同时,通过控制cwnd值在合理范围内振动,来避免传统算法中cwnd值的大幅振荡。具体的方法为:

连接建立,最初的慢启动阶段,拥塞窗口cwnd初始化依旧和传统算法一样设置为1,设RTTmin=#,开始发送数据分组后,源端记录每一次的RTT值,RTT(i)为第i次传输的RTT值,RTTmin(i)为第i次传输后的RTTmin值,即:

RTTmin(i)=min{RTTmin(i-1),RTTi}

(2)

󰀁󰀁每次传输后计算RTTi-RTTmin(i)的差值并进行判断,若RTTi-RTTmin(i)<󰀁,cwnd呈指数增长;若󰀁 ,cwnd线性减少。其中,󰀁,󰀂, 为常数,是预先设定的三个门限阈值。若超时,取cwnd=min{wnd,cwnd}/8作为下一轮的输入窗口,再次进入慢启动,继续轮回控制。3.3󰀁拥塞的避免

传统TCP协议采用慢启动,当拥塞窗口>门限窗口时,

。使用了慢启动(slow-start),加速递减(multiplicative

decrease)和拥塞避免(congestionavoidance)3个技术。TCP拥塞控制的4个阶段为:慢启动阶段、拥塞避免阶段、快速重传和恢复阶段

[8]

。

在TCP协议中,连接一开始,进入慢启动阶段,每收到一个ACK,则将拥塞窗口加倍,按指数增长,所以对于RTT较小的TCP流的拥塞窗口在连接一开始增长速度很快;而对于RTT较大的TCP流(慢速连接)环路延迟较长,窗口增长较慢,若不采取有效的措施,这样经过一段时间后,快速连接几乎完全占用瓶颈可用网络带宽,而慢速连接几乎无法发送,导致慢速连接流被 饿死!的现象发生,引起严重的不公平。

产生上述现象的原因主要是:传统的TCP拥塞控制机制能有效地避免拥塞崩溃的发生,但没有行之有效的方法避免拥塞的产生。对TCP的网络模型分析可知,在TCP拥塞控制算法中慢启动与拥塞避免阶段,由于cwnd指数增长与cwnd线性急剧增加,最终结果注定会导致网络拥塞。另外,加速递减后,拥塞窗口下降为1,同时将门限窗口降为原先也是窗口的一半,重新进入慢启动阶段,虽然,快速处理了拥

󰀂125󰀂拥塞窗口按线性规律增长来避免拥塞。但此法只能减缓拥塞,不能避免拥塞。本文采用随机检测算法(RandomEarlyDetection,RED)是传统避免拥塞算法采用的标准方法。使用RED算法,每个路由器监控分组排队长度,并在它没有完全用尽缓冲区之前按一定的概率丢弃进入路由器的数组分组,通过TCP拥塞控制协议,源端发现超时或重复ACK,从而减少速度,使发送方进入拥塞避免阶段,从而很好避免网络拥塞的发生。3.4󰀁拥塞的处理

TCP协议采用加速递减技术,将拥塞窗口(cwnd)降为1,同时将门限窗口降为原先拥塞窗口的一半,重新进入慢启动阶段,快速处理了拥塞,但cwnd的振荡幅度较大,造成了网络资源的浪费,针对此问题,本文具体解决方法如下:

在连接建立时,DUAL将最大与最小的RTT值设置为0与#,即RTTMAX=0,RTTMIN=#源端记录每次传输的rtt值,并计算RTTMAX=max{RTTMAX,rtt};RTTMIN=min{RTTMIN,rtt},至少计算两次后,可设置回路响应时间rtt的门限值为:

RTT=󰀁*RTTMAX+(1-󰀁)RTTMIN,

其中0∃󰀁<1,通常取󰀁为0󰀁5;

即下次检测的rtt值不能超过本次计算的门限值RTT。源端继续记录每次传输的rtt值,并判断,若rtt大于门限值RTT,则取下一轮慢启动的拥塞窗口cwnd=min{wnd,cwnd}/8,其中wnd为接收方窗口。在DUAL控制算法中,cwnd大小保持相对稳定,加快了拥塞的处理,提高了网络运行效率。3.5󰀁拥塞的恢复

传统TCP协议采用快速重传和快速恢复,但发送端收到多个重复应答而不等RTO到,提前重发应答之后的报文,使网络迅速恢复正常工作。本文采用确定的Sack算法。选择应答Sack的算法中有一个称作选择域(Option)的数据段,Sack的选择域包含许多Sack块,它们报告一组已经到达和排序的非拥塞的数据。第1块需要报告接受方最近接受的数据,其他块重复最新报告过的数据块。一般来说每一个选择域包含Sack3个块。Sack算法较好地解决了同一数据窗口中多包丢弃的问题,源端监测到拥塞后,对报文进行有选择的确认和重传,即对已正确传到接收端的报文不需重传。从而减少了重传和时延,提高了网络的吞吐能力。3.6󰀁算法的具体实现

基于RTT的拥塞控制算法为:1)初始化:

win=min(cwnd,awin),󰀁

cwnd=1;󰀁RTTmin=#;选定󰀁,󰀂, 的值。

2)当新确定包ACK到达时:(检测往返时间RTT的值)RTTmin=min{RTTmin,RTT};

i

If(RTTi-RTTm<󰀁)in

󰀁󰀁cwnd=cwnd+1;

/*CongestionAcoidance*/

i

Elseif(󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁

cwnd=cwnd+1/cwnd;cwnd=cwnd;

cwnd=cwnd-1/cwnd;

iElseif(󰀂iElseif(RTTi-RTTmin> )

3)超时:

cwnd=min{wnd,cwnd}/8。

4󰀁仿真研究

4.1󰀁实验设计

通过网络仿真软件NS[10]对基于RTT的TCP拥塞控制算法与传统的TCPReno算法(包含TCP的四个核心部分)相比较,进行性能分析。实验网络拓扑结构如图2所示。实验采用NS网络模拟器进行。

图2中10个源端和10个目的端之间各有一个TCP流,均为持久的FTP数据流。路由器R1、R2为瓶颈链路,链路带宽和延迟分别设为5Mbps,10ms。其它的所有的链路带宽和延迟分别设为10Mbps,10ms。路由器采用FIFO&DropTail队列管理算法,所有节点缓冲区的队列长度为40segments,数据包的大小统一为1000bytes。

图2󰀁仿真实验网络拓扑结构

4.2󰀁结果与分析

在相同的网络环境下,实验分别做5次测试,基于RTT的TCP拥塞控制算法与TCPReno算法的性能。实验结果如下:

1)丢包数。如表1所示,基于RTT的TCP拥塞控制算法的平均丢包数为36,TCPReno算法的平均丢包数为82。相比较可知,基于RTT的TCP拥塞控制算法丢包数远远低于TCPReno算法丢包数,这样因为,TCPReno算法丢包现象严重发生,所以要重传数据包,减少了吞吐量,浪费了网络资源;而本文的提出的TCP算法对其进行了改进,提前通知源端降低发送速率,避免了不必要的包的丢失,减少了重传包的次数,大大提高了网络的效率。

󰀂

󰀁󰀁󰀁

126󰀂

/*SlowStart*/

表1󰀁两种算法的丢包数比较

实验12345

TCPRTT3540373533

TCPReno

8583788084

塞跟RTT的大小成正比的关系,由源端检测RTT的值,在网络拥塞产生的临界区域,采取cwnd线性减小的方法,使网络远离该区域,大大降低了拥塞产生的可能性。在没有突发性分组的情况下,使产生的可能性降到最低。即便遇到超时,同等情况下,网络拥塞程度比采用TCPReno算法的拥塞程度低,易于摆脱拥塞。另外,超时时,将cwnd降低到原值与wnd的较小值的1/8,而非降到最低。使网络在快速脱离拥塞的同时,避免了TCPReno算法中cwnd值得大幅振荡。经仿真实验证实:该算法比TCPReno算法的丢包率要低得多,且大大提高了吞吐能力、带宽的利用率,提高了网络的运行效率。参考文献:

[1]󰀁罗万明,林闯,阎保平.TCP/IP拥塞控制研究[J].计算机学

TCPReno8󰀁218󰀁277󰀁568󰀁348󰀁198󰀁10

报,2001,(1):1-18.

[2]󰀁MarcheseM.Proposalofamodifiedversionoftheslowstartalgo󰀂

rithmtoimproveTCPperformanceoverlargedelaysatellitechan󰀂nels[J].

IEEEInternationalConferenceonCommunications,

2001,10:3145-3149.

[3]󰀁MAllman,CHayes,SOstermann.AnevaluationofTCPwithlar󰀂

gerinitialwindows[J].ACMComputerCommunicationReview,1998,28(5):41-52.

[4]󰀁WangHaining.Asimplerefinementofslow-startofTCPconges󰀂

tioncontrol[J].IEEESymposiumonComputersandCommunica󰀂tions,2000,5:98-105.

[5]󰀁刘凤格.基于RED算法的改进研究[J].计算机仿真,2009,

(5).

[6]󰀁林林,陈魏鑫,张鹏.基于强度控制的并行TCP拥塞控制策略

研究[J].计算机应用,2008,(4).

[7]󰀁严伟荣,蔡士杰.带宽保证环境下TCP算法改进及其模型分析

[J].计算机应用,2003,23(9):8-11.

[8]󰀁杨燕,谭连生,熊乃学.一种新的多瓶颈网络环境下的TCP拥

塞控制算法[J].小型微型计算机系统,2005,26(2):186-191.

[9]󰀁汪雁,黄本雄.DiffServe网络的拥塞控制和带宽保证[J].计算

机工程与应用,2003,(3):177-180.

[10]󰀁秦楠,郑应平.基于TCPVegas与TCPReno的一种改进拥塞

控制算法[J].计算机工程与科学,2007,29(11):23-25.

󰀁󰀁2)吞吐量。如表2所示,基于RTT的TCP拥塞控制算法的平均吞吐量为10󰀁43Mbps,TCPReno算法的平均吞吐量为8󰀁15Mbps。相比较可知,在相同的参数下,基于RTT的TCP拥塞控制算法能获得比TCPReno算法高得多的吞吐量,提高了网络的利用率。

表2󰀁两种算法吞吐量(Mbps)的比较实验12345平均

TCPRTT10󰀁7510󰀁4010󰀁4211󰀁2610󰀁3310󰀁35

󰀁󰀁图3和图4分别是改进前和改进后的一组测试曲线。

[作者简介]

代丽娴(1966-),女(汉族),湖北武汉市人,工学

硕士,讲师,主要研究方向为计算机网络控制和科

从图3和图4可知,改进前发生了大量丢包,吞吐量变化大,而改进后吞吐量表现平稳,吞吐量大,能够从网络拥塞中快速恢复,能够最大限度利用带宽。

据挖掘。

学计算。

黄宏本(1977-),男(汉族),广西梧州市人,工学

硕士,讲师,主要研究方向为计算机网络控制和数

5󰀁结束语

针对传统的TCPReno算法存在的网络拥塞缺点,本文设计了一种的基于RTT的TCP拥塞控制算法,根据网络拥

󰀂127󰀂