TCP网络拥塞控制算法比较研究

陈 琳,双雪芹 (长江大学计算机科学学院,湖北荆州434023)

20世纪80年代中期,计算机网络经历了第1次由于网络拥塞引起的网络崩溃,在2个相距500m的网络之间,数据吞吐量从32kbps降到了40bps[1],网络拥塞控制问题便引起了研究者们的广泛关注,并在拥塞控制领域开展了大量的研究工作[2]。在众多研究文献中,采用的拥塞控制机制集中在2个方面:TCP拥塞控制和IP拥塞控制。笔者对TCP拥塞控制机制中的4种典型算法TCP Newreno、TCP Vegas、TCP Sack1、TCP Fack进行了研究,在NS仿真环境下进行了比较分析,得出了不同算法的优缺点,并指明了拥塞控制机制研究的下一步方向。

1 算法简介

1.1 TCP Newreno

TCP Newreno[3～5]是基于窗口反馈机制的端到端拥塞控制算法,即发送方根据接收到的反馈包(ACK包)所携带的信息,决定如何调整拥塞窗口的大小。该算法是对文献 [6]中快速恢复算法的改进,考虑了一个发送窗口内多个报文丢失的情况。在Reno快速恢复算法中,当发送方收到一个不重复的应答后就退出快速恢复状态,而在Newreno算法中,只有当所有报文都被应答后才退出快速恢复状态。

TCP Newreno利用一种Partial ACK包[3]在快速恢复阶段触发数据包的重传。Partial ACK包是指当一个窗口出现多个分组丢失时,确认了部分发送分组的重传分组的ACK包。数据传输过程中有多个分组丢失后,Newreno在快速恢复阶段每隔1个往返延迟 (RT T)重传1个丢失的分组,直到拥塞窗口的所有丢失分组都被重传。当在快速恢复阶段接收到第1个Partial ACK时,将重传定时器复位。

1.2 TCP Vegas

TCP Vegas[7]也是对Reno算法的改进,和Reno采用报文段丢失作为拥塞度量所不同的是,Vegas采用延迟作为拥塞度量,并且通过比较实际传输速率和期望传输速率之间的差值来预知拥塞的发生,并在重传机制和慢启动机制方面做了一定修改。其主要机制如下:

1)拥塞避免 期望传输速率E定义为:

其中,cwnd为拥塞窗口大小;BaseRT T为所观察到的最小的RT T。

实际传输速率A定义为:

其中,RT T为当前观察到的值。

Vegas将E与A的差值与门限值α和β比较(α＜β)[7],当差值小于α时,Vegas在下1个RTT中将拥塞窗口加1;当差值大于β时,Vegas则在下1个RT T中将拥塞窗口减1;否则拥塞窗口保持不变。

2)慢启动 在改进的慢启动算法中,每2个RT T时间间隔就将cwnd增加一倍。因此在2个RT T期间,在一个R TT内拥塞窗口不会变化,这样A和E的比较就较为准确。比较值同另一个门限值λ[7]作比较,当比较值达到门限值λ,Vegas就进入拥塞避免阶段。

3)快速重传/快速恢复 在发送数据段时,Vegas读取并记录下系统时间。当一个ACK包到达时,Vegas再次读取系统时钟并以该时间和先前记录下的时间来计算RTT。当接收到重复ACK时,Vegas检查当前RT T是否比超时值大,如果是,Vegas就立即重发相应的数据段,而不必等到第3个重复ACK包到来。当接收到非重复ACK时,如果它是重发之后的第1或第2个确认,Vegas将再次检测第1个未被确认的数据包发送的时间和此时的时间间隔是否大于超时值,如果是,Vegas将重发该数据段。

1.3 TCP Sack1

Sack1[8,9]也是基于算法Reno的改进。当检测到拥塞后,不用重传从数据包丢失到检测到丢失时发送的全部数据包,而是对这些数据包进行有选择的确认和重传,从而避免不必要的重传,减少时延,提高网络吞吐量。与Reno所不同的是,接收端的ACK包中包含了一些SACK块,每个SACK块表示了接收端收到的分组序列中缺少的分组段范围,这使得发送端可以明确地知道哪些分组应该进行重传。SACK算法的发送端在收到第2个重复的ACK包后,进入到快速恢复阶段,它设置了1个变量估计网络中正在传输的分组数量,只有该变量的值小于拥塞窗口时,发送端才被允许发送分组数据。发送端每收到1个重复的带有SACK信息的ACK包 (表明新的分组被接到),就将该变量减1;每次有新的或者重发的分组被发送,变量的值就被加1个分组的大小。同时,发送端维持1个称为计分板的数据结构,记录从SACK中得知的未被确认的分组,发送端如果被允许发送,就重传计分板中指示的最后的分组,如果计分板为空,就发送新的分组。当收到确认了所有的进入快速恢复之前未确认的分组的ACK后,便退出快速恢复阶段。可以看到,计分板指出了哪些分组需要重传,而上述所设置的变量决定了什么时候重传哪些分组。

1.4 TCP Fack

TCP Fack[10]是基于对TCP Sack1的修改。Fack引入3个TCP发送端状态参数:未确认分组中的第1个序号、待发送的第1个分组的序号、接收端收到的最新的分组序号,在恢复阶段发送端估计网络中的分组数 (待发送的第1个分组的序号减去接收端收到的最新的分组序号,并加上正在网络中重传的分组数),当发送端估计的分组数小于拥塞窗口时,发送端被允许发送或者重发分组。

2 仿真比较与分析

笔者在NS[11]仿真环境下进行仿真,仿真采用基于图1的哑铃拓扑结构,对Newreno、Vegas、Sack1、Fack 4种算法进行了仿真,得到每个算法在图1场景下的拥塞窗口、吞吐量、丢失率和平均队列变化曲线图。图1中si为源端,di为接收端,R1、R2为路由器,采用RED队列策略,由n个连接共享一段由R1、R2构成的瓶颈链路。瓶颈链路的带宽为1.5Mbps,传播延迟为20ms。分组的大小设为552Bytes,端点带宽分别是10Mbps,延迟为5ms。网络传输的数据流类型为FTP。

图1 网络拓扑结构

从图2可以看出,在相同的环境下,Newreno、Sack1和Fack的3种算法的拥塞窗口曲线在平衡状态后均呈锯齿状,所不同的是,Fack在超时后把拥塞窗口置1,经历慢启动后达到一个平衡状态。3种算法的共同点是都必须周期性地丢失报文段以维持这种平衡。实验表明在低带宽的环境下,这对传输速率还不会造成很大影响,传输速率在达到平衡状态后周期性变化。Vegas在20s以后拥塞窗口变成直线,说明窗口维持在一个定值。这是因为用α和β两个常数来控制拥塞窗口的变化,当发送传输速率和期望传输速率之差介于α和β之间,窗口不变化了,使链接达到稳定点后传输速率维持在较高的水平。

图3是4种算法的吞吐量曲线。由图3可以看出,Vegas在后期拥塞窗口维持在一个较高的平衡状态,吞吐量也保持在一个高的水平;Newreno和Sack1两种算法在平衡状态的吞吐量也是非常接近的,波动比较小。Fack在超时后是把窗口置为1,经历慢启动后才达到一个平衡状态,使得其吞吐量曲线波动较大,但总体还是处于一个平稳状态。

图2 拥塞窗口对比

图3 吞吐量对比

从图4显示的丢失率对比可以看出,在开始的4s内,Vegas、Sack1、New reno和Fack的4个算法的丢失率从小到大排列。Vegas算法的丢失率最少,而Fack算法的丢失率最大。这是因为Vegas采用延迟作为拥塞度量,并且通过比较实际传输速率和期望传输速率之间的差值来预知拥塞的发生,而Sack1、Newreno、Fack的3种算法采用了报文段丢失作为拥塞度量。在网络环境比较平稳的条件下,Vegas算法就体现了其优越性,能更准确地预知网络拥塞的情况,从而及时采取拥塞控制措施。当网络发生拥塞时Fack把窗口置1,窗口突然减少到1,产生报文发送振荡使得网络拥塞无法及时缓解,造成丢失报文增加。

图5为平均队列长度对比变化曲线图。由图5可见,Vegas算法的平均队列长度较小,对链路的利用率最高,Fack算法次之。

图4 丢失率对比

图5 平均队列长度对比

3 结 语

仿真结果表明,Vegas算法采用时间延迟作为拥塞度量,使用RT T的变化来判断网络可用带宽,能较好地预测网络带宽使用情况,其吞吐量、链路利用率都较好,数据包丢失率小、缓存队列长度较小,具有良好的应用前景。由于Fack算法数据包丢失率最大,将来可以改进其拥塞超时策略以提高算法性能。Vegas算法在各方面都优于其他3种算法,但由于判断条件依赖于RT T的估算,因此设计一个性能良好的RT T估算算法变得尤为重要,这也是笔者下一步研究的方向。

[1]Jacobson V.Congestion avoidance and control[J].Proceeding of SIGCOMM'88,1988.314～329.

[2]罗万明,林闯,阎保平.TCP/IP拥塞控制研究 [J].计算机学报,2001,24(1):1～18.

[3]Floyd S,Henderson T.The New reno modification to T CP's fast recovery algorithm[J].RFC 2582,1999.

[4]Clark D,Hoe J.Start-up dy namics of TCP's congestion control and avoidance schemes[J].Presentation to Internet End-to-End research Group,1995.

[5]Grieco L A,Mascolo S.Performance evaluation and comparison of Westwood+,New Reno,and Vegas TCP congestion control[J].Computer Communication Review,2004,34(2):25～38.

[6]Jacobson V.M odified T CP congestion avoidance Algorithm.http://ftp.ee.lbl.gov/

[7]Brakino L S.TCP vegas.New techniques for congestion detection&avoidance[C].Proc SIGGCOM M,1999.

[8]M atthew W,Jamshid W,Sally F,et al.TCP selective acknowledgement options[J].RFC 2081,1996.

[9]刘拥民,年晓红.对SACK拥塞控制算法的研究 [J].信息技术,2003,(9):55～58.

[10]Matllls M,Mahdavi J.Forward acknowledgement(FACK):refiningTCP congestion control[J].Proc SIGCOMM,1996.281～291.

[11]The Network Simulator-ns-2.http://www.isi.edu/nsnam/ns/2004.