TCP协议乱序数据包处理算法综述

摘要:TCP协议是互联网中最为重要的协议之一。然而,由于诸如多路由,并行处理,链路层重传等原因,乱序数据包成为互联网中不可避免的现象。本文首先分析了乱序数据包对于TCP协议的影响,然后分析比较了目前国内外学者提出各种解决方案,指出了各种方案的优点与不足,指明了TCP协议中乱序数据包处理算法的研究方向。

关键词:TCP;拥塞控制;乱序数据包;快速重传

1 引言

作为互联网上最为核心的通信协议之一,TCP协议最早于1974年由Vinton Cerf和Robert Kahn共同提出。最初,TCP协议设计的主要目的是如何在异构的主机之间可靠地传输数据,因此主要包括基于窗口的流量控制,丢包恢复等功能。上个世纪80年代,由于互联网用户和流量的激增,互联网经历了多次严重的拥塞崩溃事件。为了解决这一问题,上世纪80年代后期,Van Jacobson等人首次把拥塞控制应用到TCP协议当中,从而极大地改善了Internet上端到端连接的性能和稳定性,保证了整个互联网的稳定运行[1]。TCP是目前互联网中使用最广泛的传输协议。非常多的应用,如FTP,Web,Email等,都采用了TCP协议。根据2009年11月份的最新统计,互联网总字节数的90%和总报文数的87%均使用TCP协议进行传输[2]。

随着互联网的飞速发展,各种新技术被应用到互联网中,如多路由技术,并行处理技术,链路层重传技术等。这些技术在提升互联网性能的同时,也导致了传输层乱序数据包的出现。大量的研究表明,乱序数据包会使位于传输层的TCP协议性能大幅下降。国内外众多学者已经提出了各种不同的方法来提高TCP协议在面临乱序数据包时的性能。

本文首先分析了乱序数据包造成TCP性能下降的主要原因,然后讨论了各国学者所提出的不同解决方案;在此基础上给出了在面临乱序数据包时,提高TCP协议性能的几个研究方向。

2 乱序数据包对TCP协议的影响

TCP协议拥塞控制的基本原理是:当网络发生拥塞时,发送端应减小发送速率。实际上,位于通信连接末端的TCP拥塞控制算法无法了解网络中究竟是否真的发生了拥塞,只能根据接收端收到的信息推测网络状态。因此设定了一个假设前提,即分组丢失意味网络拥塞。即使这样,TCP协议还是无法确切了解是否真的发生了分组丢失事件,只能根据确认指示推测分组是否丢失。现行的TCP协议可以通过两种方式来判定数据包的丢失[3]。

(1)重传定时器超时。

(2)接收端收到一定数量的重复应答(通常为3个)。

TCP通过数据包的序列号来保证数据包的正确,按序交付。假设序列号为 的数据包丢失,接收端每收到一个序列号大于 的数据包都会认为这是一个乱序数据包,在数据包 被正确接收之前,每收到一个这样的数据包,都将产生一个对于 的重复应答。如果发送端收到一定数量的重复应答,将认为该数据包丢失,并由此推测网络发生了拥塞。此时,重传丢失的数据包,并将拥塞窗口减半。

这种丢包判定方式有效的前提是:网络结构稳定,同属一个连接的所有数据包按照同一路径到达接收端,并且中间路由采用先到先服务和FIFO的原则。在以上条件成立的情况下,数据包的到达遵循“先发先到”的原则。数据包如果没有按序到达则意味着丢失。然而,这种丢包判定方式容易受到网络中持续的乱序数据包的影响。

乱序数据包是一种数据包到达顺序与发送顺序不一致的网络现象。许多针对网络中数据包的乱序问题的观察、测量和本质研究指出:数据包的乱序并不是网络的病态行为,而是作为一种普遍现象伴随着网络一直存在。统计显示约有0.1%-2%的数据包会经历乱序事件[4]。

乱序数据包的出现会给TCP协议带来很大影响:(1)不必要的传输层重传,浪费带宽;(2)拥塞窗口不必要的减小,降低网络利用率。

3 现有的解决方案分析

针对乱序数据包对于传输层TCP协议的影响,众多学者提出了不同的解决方案,主要包括以下三种。

3.1 增大触发快速重传的门限值

一些学者指出,将触发快速重传的门限值(dupthresh)固定为3,会使得TCP协议对于乱序数据包的容忍程度太低,容易诱发不必要的重传。因此提出改变dupthresh的取值[5]。目前主要有三种dupthresh设定算法:

(1)当乱序数据包出现时,通过固定参数K增大dupthresh的取值。

该算法的主要思路是:当乱序数据包出现时,将快速重传门限值dupthresh增大为dupthresh+K。为此,需要在接收端检测乱序数据包事件。检测过程如下:如果数据包在dupthresh之后到达,即,已经被判定为丢失的数据包到达接收端,则认为这是一个乱序数据包事件。此时,将dupthresh增大为dupthresh+K。此后,将按照新的dupthresh进行丢包判断。

这种方法的优点是实现简单,缺点也很明显,接收端可能需要多个周期,才能将dupthresh设定为合理值。这个收敛过程和整个算法的性能依赖于K的选择。

(2)将dupthresh动态设定为当前值与乱序数据包长度和的一半。

该算法的主要思路是:当接收端检测到数据包缺失时,开始记录乱序到达的数据包数量,称为乱序数据包长度,记为L,直到缺失的数据包到达。此时,将快速重传的门限值dupthresh修改为(dupthresh+L)/2。

这种方法的优点是,它能够较第一种算法更为迅速地使dupthresh根据网络状态收敛于理想值。缺点在于一个偶然的较大的乱序数据包长度可能造成dupthresh过大,影响TCP协议的性能。

(3)根据乱序数据包长度,利用指数加权移动平均算法设定dupthresh。

为了克服上述两种算法的缺陷,Leung等人在文献[6]中提出利用指数加权移动平均算法(EWMA:Exponentially Weighted Moving Average)动态设定dupthresh。同第二种设定算法一样,当接收端检测到数据包缺失时,开始记录乱序数据包的长度L,直到缺失的数据包到达。此时,根据以下公式,计算平均乱序数据包长度:

if L > avg

avg = (1-α)*avg + α*L

else

avg = (1-α*x)*avg + (α*x)*L

其中,α为EWMA因子,通常取1/3,x为乘性因子,通常取4。

随后,将dupthresh设定为平均乱序数据包长度avg。这种算法的优点在于dupthresh可以根据网络状态动态更新,并且,避免了第二种算法中单个过大的乱序数据包长度对dupthresh造成的过大影响。缺点在于接收端需要增加统计变量,并且随时更新乱序数据包长度也会对接收端的性能造成一定影响。

3.2 Eifel算法

R. Ludwig和R. Katz提出使用Eifel算法来减少由乱序数据包引发的伪超时与伪重传对TCP协议的影响[7]。Eifel的原理如图1所示,发送端在T1时刻发送报文S时,将时间戳插入TCP头部。在T2时刻,发送端检测到S丢失,重传S,并执行拥塞控制算法。重传的S与原始发送的S相比,包含不同的时间戳T2。当接收端收到原始的S后,发送应答时,包含原始S的发送时间T1。当此应答到达发送端时,发送端发现此应答包含的时间信息T1小于存储与Retransmit TS变量中的T2,由此判断此重传为假重传。当检测到假重传时,发送端会将拥塞窗口和慢启动门限值恢复到错误重传前的值,然后如同没有发生错误重传一样继续发送数据分组。

Eiefl算法的优点在于能够在很短的时间内检测出假重传,从而避免了后续不必要的重传和拥塞回退机制。Eiefl算法还可以解决分组乱序、分组重复等问题。Eifel算法的缺陷在于,Eifel算法必须使用TCP协议的数据段参数来进行错误重传判断,并且Eifel算法仅仅是在检测到伪重传时避免了拥塞窗口的减小,并不能减少伪重传的数据包数量,因此不能减少伪重传对带宽的消耗。

3.3 DSACK机制

重复选择确认机制(DSACK)通过扩展TCP协议的SACK选项来克服乱序数据包的影响[8]。

DSACK算法的原理如图2所示,发送端发送S1-S4数据包。由于网络原因造成S1数据包乱序,它在S4数据包之后到达接收端。因此S2,S3,S4数据包均会产生对S1的重复应答。在收到这3个重复应答后,发送端将重传S1。当重传的S1到达接收端后,会产生一个对于S5的重复应答,同时SACK信息会指明此重复应答是由S1引起的。当此应答到达发送端后,发送端就可以判断出刚才对于S1的重传是假重传。

DSACK算法要求发送端维护检测到分组丢失时的拥塞窗口和慢启动门限值等信息,发送端根据DSACK信息检测到假重传时,将拥塞窗口和慢启动门限值恢复到错误重传前的值。虽然没有增加分组的开销,但是它无法解决网络中的分组重复和ACK丢失等问题。如果包含DSACK信息的应答丢失,则接收端无法进行恢复。并且,由于DSACK信息在丢失恢复结束后才到达发送端,因此发送端在丢失恢复阶段无法检测到假重传。

4 结束语

本文总结了目前国内外学者提出的几种典型的TCP协议乱序数据包处理算法,并对这些算法进行了详细的分析和比较。综上所述,该领域仍存在着一些亟待解决的问题,未来的研究可以考虑从以下方面展开:

(1)充分利用TCP数据包头部的闲置字段,描述链接及网络状态,接收端可以利用这些状态参数,判断缺失的数据包是否是由于网络拥塞导致。

(2)设计更加合理的快速重传门限值设定算法,使其能够以较快的速度收敛于真实网络状态,同时算法应尽量减轻接收端的计算量和存储空间开销。

(3)利用接收端已知参数,如往返时延,重传超时时间等,在不增加接收端开销的基础上,判断乱序数据包的出现。

参考文献

[1] Nagle J. RFC896: Congestion control in IP/TCP Internet works. Internet Engineering Task Force, 1984.

[2] Internet2 NetFlow: Weekly reports. netflow.internet2.edu/weekly/. 2009, 11.

[3] Allman M, Paxson V, Stevens W. RFC 2581: TCP Congestion Control. Internet Engineering Task Force, 1999.

[4] Bennett J C R, Partridge C, Shectman N. Packet Reordering is Not Pathological Network Behavior [J]. IEEE/ACM Transactions on Networking, 1999, 7 (6): 789-798.

[5] Chaudhary R, Jacob L. Corruption and Reordering Robust TCP-Friendly Rate Contro l [J]. Computer Communications, 2005, 28: 97-107.

[6] Leung K C, Ma C. Enhancing TCP Performance to Persistent Packet Reordering [J]. Journal of Communication and Networks, 2005, 7(3):385-393.

[7] Ludwig R, Katz R. The Eifel Algorithm: Making TCP Robust Against Spurious Retransmissions [J]. Computer Communication Review, 2000, 30(1): 30-36.

[8]Floyd S, Mahdavi J, Mathis M. RFC 2883: An Extension to the Selective Acknowledgement (SACK) Option for TCP, Internet Engineering Task Force, 2000.