基于TCP_IP拥塞控制的算法研究

2005年第6期ShipElectronicEngineering　　88　

基于TCP/IP拥塞控制的算法研究

李学渊

(广东纺织技术学院　佛山　528041)

Ξ

摘　要:在WPAN上使用TCP的关键在于拥塞控制,根据TCP的拥塞控制机制,通过分析拥塞控制的闭环控制原理、

TCP/IP拥塞控制所使用的典型技术,研究TCP/IP拥塞控制在无线网上应用的算法。关键词:拥塞;数据包;TCP/IP;网络中图分类号:TP393

ResearchontheCongestControlAlgorithmofTCP/IP

LiXueyuan

(GuangdongTextilePolytechnic,University,Foshan　528041)

Abstract:OnWPAN,thekeyofusingTCPisthecongestcontrol,thispaperanalyzesandresearchesthecongestcontrolalgo2rithmofTCP/IPthatappliedonwirelessnet,byanalyzingtheclosed-loopcontrolprincipleofcongestcontrol,andthetypicaltechnologyusedincongestcontrolofTCP/IP.

Keywords:congest,datapack,TCP/IP,electricnetworkClassnumber:TP393

1　引言

网络产生拥塞的根本原因在于用户提供给网络的负载大于网络资源容量和处理能力。表现为数据包时延增加、丢弃概率增大、上层应用系统性能下降等。目前,拥塞产生的直接原因是:存储空间不足;带宽容量不足;处理器处理能力弱、速度慢。要避免拥塞的发生,需要对发生拥塞的原因综合考虑,得到一个效率性和公平性的TCP算法[1]。

题[2]。

2.1TCP拥塞控制机制

目前,在Internet(IPv4)使用的拥塞控制,基本上是建立在TCP的窗口控制基础之上的[3]。IP层(网络层)的路由器所起的作用比较小,因为对拥塞现象最切实的办法是减低数据传输速率。TCP的拥塞控制采用的是基于窗口的端到端的闭环控制方式,如图1所示。

2　TCP拥塞控制

从控制论的角度,对计算机网络这样复杂系统中拥塞问题的解释。一种是开环控制,其解决方案是何时接受新的通信,何时丢弃分组,以及丢弃哪些分组,包括在网络的不同点作计划表。由于开环控制不考虑当前网络变化状况,它并不是理想的选择。另一种是闭环控制,其解决方案是建立在反馈环路概念上的。当用于拥塞控制时,考虑监视系统,检测何时何地发生了拥塞,将此信息传送到可能采取行动的地方,调整系统操作以更正拥塞问

Ξ

图1　N个用户共享一个网络下拥塞的闭环控制系统

如果在时刻t,第i个用户的传送负载为Xi(t),那么输入网络的总负载应为∑Xi(t)。系统状态用n维向量X(t)={X1(t),X2(t),……,Xn(t)}表示。如果∑Xi(t)不大于网络承受能力Xgoal,所

基金项目:全国教育科学十五规划重点课题资助(项目编号:AYA010034)收稿日期:2005年4月23日,修回日期:2005年5月16日

2005年第6期　　　　　　　　　　　　　　　　　　舰船电子工程　　　　　　　　　　　　　　　　　　　　89

有用户的负载请求都会被接受。这样,Xi(t)也同时表示网络系统资源分配给每个用户的情况。用户与系统通过反馈控制函数y(t)相互作用,实时地改变传送负载大小。假定改变量为ui(t)则Xi(t+Δt)=Xi(t)+ui(t),变化ui(t)就代表了对第i个用户的控制。它是用户t时刻负载和系统反馈的函数ui(t)=f(Xi(t),y(t)),也就是Xi(t+Δt)=Xi(t)+f(Xi(t),y(t))。2.2TCP拥塞控制算法

(SlowTCP拥塞控制算法都要经过“慢启动”

(CongestionAvoidance)、Start)、“拥塞避免”“快速(FastRetransmit)、(FastRecov2重传”“快速恢复”ery)四个阶段[2]。2.2.1慢启动阶段慢启动,这会导致过大地减小发送窗口尺寸,降低TCP连接的吞吐量。

图2　慢启动和拥塞避免当建立连接时,发送方将拥塞窗口大小初始化为该连接所用的最大数据段的长度值,并随后发送

一个最大长度的数据段(通常为536或512bytes)。如果该数据段在定时器超时之前得到了确认,那么发送方会在原拥塞窗口的基础上,再增加一个数据段的字节字,使其为两倍最大数据段的大小,然后再发送两个数据段。当这些数据段中的每一个都被确认后,拥塞窗口大小就再增加一个最大数据段的长度。当拥塞窗口是n个数据段的大小时,如果发送的所有n个数据段都被及时确认,那么将拥塞窗口大小增加n个数据段首对应的字节数目。很显然,cwnd的增长将随RTT呈指数级(exponen2tial)增长:1个、2个、4个、8个......。源端向网络中发送的数据量将急剧增加。拥塞窗口保持指数规律增大,直到数据传输超时或者达到接受方设定的窗口大小。2.2.2拥塞避免阶段

图3　快速重传和恢复

因此快速重传和恢复就是在源端收到3个或3个以上重复ACK时,就断定数据包已经丢失,重

传数据包,同时将ssthresh置为当前cwnd的一半,

而不必等到RTO超时。直到收到一个新的ACK(恢复ACK)确认才退出快速重传,在一个往返时间内最多重发一个报文,如图2、3所示,反映了拥塞控制窗口随时间在四个阶段的变化情况(图中各点不代表真实数据)。其TCP拥塞控制的算法:

初始化:

win=min(cwnd,awin)cwnd=1;

ssthresh=65535bytes(缺省值);

当新确认包ACK到达时:

If(cwnd当发现超时或收到3个相同ACK确认帧时,网络即发生拥塞。TCP这一假定是基于由传输引起的数据包损坏和丢失的概率很小(小于1%),对于这一点并不适合于网络差错率较高的无线网络。慢启动阈值(ssthresh)被设置为当前cwnd的一半,如果是超时,cwnd还要被置1。如果此时cwnd≤ssthresh,TCP就重新进入慢启动过程;如果cwnd>ssthresh,TCP就执行拥塞避免算法,cwnd在每次收到一个ACK时只增加1/cwnd个数据包(这里将数据包大小segsize假定为1),所以在拥塞避免算法中cwnd的增长不是指数的,而是线性的(linear)。

2.2.3快速重传和恢复阶段

当数据包超时时,cwnd要被置为1,重新进入

　/SlowStart/　cwnd=cwnd32

Else

　/CongestionAvoidance/　cwnd=cwnd+1

Endif

win=min(cwnd,awin)

　//当收到3个以上相同的ACK确认包时　//FastRetransmit&FastRecovery　ssthresh=max(2,min(cwnd/2,awin))　cwnd=cwnd/2

超时:

ssthresh=max(2,min(cwnd/2,awin));cwnd=1;

　　　　　　　　　　　　　　　　李学渊:基于TCP/IP拥塞控制的算法研究　　　　　　　　　　　　　　总第150期90

3　TCP拥塞控制的估计值函数

在大多数TCP实现中,RTO计数器的值被认为是均值和方差估计值函数。而准确估计值并不是一件容易的事,最简洁的估计方法,是应用旧值和新采样值的求加权和[4],如式(1):

　RTT=(a×OldRTT)+(1-a)×New

RTT

Sample)

(1)

其中,a为加权因子且0Φa<1。当a接近1时,RTT值在最近采样的短时间内几乎不发生变化;当a接近0时,RTT对时延变化的反应就非常灵敏。理论上RTT的测量比较简单。它只是数据包从发出到确认CK返回源端的时间。但由于TCP使用的是用一个CK确认所有已收到数据的“累积”确认方式,所以RTT的估计在实际中往往很复杂。由于RTT值与网络运行情况有密切关系,本文利用RTT控制拥塞的Vegas算法[4]。Ve2gas就是通过观察以前的TCP连接中RTT值改变

源Xgoal,那么这种算法就是效率高的。超载(X(t)

>Xgoal)或负载不足(X(t)在发生拥塞时各源端(或同一源端建立的不同TCP连接或UDP数据报)能公平地共享同一网络资源(如带宽、缓存等),处于相同级别的源端应该得到相同数量的网络资源。产生公平性的根本原因在于拥塞发生必然导致数据包丢失,而数据包丢失会导致各数据流之间为争抢有限的网络资源发生竞争,争抢能力弱的数据流将受到更多损害。所以说没有拥塞,也就没有公平性问题。在图1中,如果每个源端优先级相同,则Xi(t)=Xj(t)(对任意i,j)。如果所有源端没有得到相同的分配,网络就是缺乏公平的。公平性可由式(3)定义:

(∑Xi)2

(3)F(X)=

n(∑Xi2)显然,完全公平时F(X)=1(100%),此时所有

Xi平均分配;当所有资源只提供给一个源端时,F(X)=1/n达最小,当n→∞时,F(X)=0;如果n个

情况来控制拥塞窗口cwnd,如果发现RTT变大,Vegas就认为网络发生拥塞,并开始减小cwnd;如

果发现RTT变小,Vegas就解除拥塞,再次增加cwnd。这样,cwnd在理想情况下就会稳定在一个

合适的值上。这样做的最大好处在于拥塞机制的触发只与RTT的改变有关,而与包的具体传输时

延无关。在拥塞避免阶段,cwnd值由式(2)决定:

cwnd(t)+1,如果diff<(a/base

rtt)

βcwnd(1+Δt)=cwnd(t),如果a/baserttΦdiffΦ/basertt

cwnd(t)-1,如果β/basertt(2)

源端中只有k个平均共享资源,其他n-k个源端

没有得到任何资源,则F(X)=k/n。

以上是结合图1给出的拥塞闭环控制模型的公平性定义。事实上在不同的应用背景中,可以给出不同的定义公式,结合路由中几种包调度算法,以网络中第i个数据流(flow)在公平分配带宽时ρi=BW

bwij=1

∑bwj

n

应得到的带宽来定义公平性:其中

其中,diff=cwnd(t)/basertt-cwnd(t)/rtt,rtt是观察到的回路响应时间,basertt是所观察到所有

rtt的最小值α,和β是两个常数。式(1)表明如果所有数据包的RTT稳定不变,拥塞窗口cwnd将不变。由于它没有采用包丢失来判断网络可用带宽,而改以RTT的改变来判断,所以能较好地预测网络带宽使用情况,并且对小缓存(smallbuffer)的适应性较强,其公平性、效率都较好。

BW为该数据流经过链路的总带宽,bwi为第i数

据流的要求带宽,这一定义实质上与式(3)是一致

的。总之,解决TCP拥塞控制公平性问题的根本出路在于Internet上全面实行端到端拥塞控制和融合了IP层拥塞控制的新算法。

5　小结

TCP/IP拥塞控制的设计和实现面临着众多

4　TCP拥塞控制的分析

评价一个TCP算法的性能主要是由效率性和

公平性(fairness)两方面来考虑[5]。4.1效率牲

网络资源的使用效率是源端要求的总资源与网络资源的接近程度决定的。在图1中,如果源端总资源X(t)=∑Xi(t)接近或等于网络所能提供资

的折中,不可能有一种设计和实现在所有环境中都

是“最好的”。现有的拥塞控制思路、方法和技术在不同环境中的效率有着很大的区别,因此它们还有许多要改进的地方,因此对具体网络的TCP拥塞控制算法必须具体分析选择合适的方法发挥最大的性能。

参考文献

[1]PahlavanK,XinrongLi,

(下转第118页)

　　　　　　　　　　　　　孟晓宁等:甚低频通信系统的自适应算术数据压缩研究　　　　　　　　　　总第150期118

缩比提高到0.576,将最终数据传输率增加值减少到仅有74%。

表2　用(255,233)RSFEC码的算术

编码压缩结果(平均值)

最初压缩比前导码开销RS码开销有效压缩比除去位元总共压缩比卷积码支出最终压缩比

0.526[1.90]+0.015+0.0640.605[1.65]

高50%,那么用0.526+3×0.02=0.586这个值将保证六个信道大约在99%的时间里均可以使用。表3用这个更保守的压缩比重复表1的计算,使最终数据传输率增长58%。

8　结论

本文为甚低频通信系统设计了一个自适应算术编码压缩方案,根据甚低频通信系统的需求,我们选择了59位的报头前导码,39位的正文前导码,以及(255,233)RS码。自适应算术编码能使甚低频通信系统的数据传输率平均增加90%,考虑了前导码和RS码开销后,数据传输率的平均增值降到了65%。若我们在压缩时,将开始位和结束位除去,即便误码率相当高时加了码速为3/4的卷积码,也会使数据传输率有74%的增值,这比我们的目标值50%要高。

参考文献

[1]Clark,GeorgeC.,Jr.,J.B.Cain.Error-CorrectionCodingforDigitalCommunications[M].NewYork,NewYork:PlenumPress,1981

[2]DanielW.SharpandDavidS.Roth.AdaptiveDataCompressionforaVLFCommunicationSystem[J].IEEETransactionsonCommunication,1990,(6)

[3]刘立柱编著.数字传真通信[M].成都:电子科技大

×0.714[1.40]0.432[2.31]×1.333

0.576[1.74]

　　如果所增加的数据传输率被当作是给现有的四个信道增加的信息,那么平均压缩就是一个合适的度量。然而,我们希望考虑在四个原有50波特的信道又补充两个额外的50波特的信道。在这种情况下,平均压缩比就不适合,因为如果在一段时间内压缩效果比一般情况要差(这会经常发生的),那么附加的两个信道中就会有一个信道消失一会儿。通过一段50波特的标准广播信息,我们计算了压缩比的标准偏差,这个标准偏差值为0.02。平均压缩比加上三个标准偏差会得到一个新的压

表3　用(255,233)RSFEC码的算术

编码压缩结果(保守值)

最初压缩比前导码开销RS码开销有效的压缩比除去位元总共压缩比卷积码支出最终压缩比

0.586[1.71]+0.015+0.0640.665[1.50]

学出版社,2000

[4]Ramabadran,TenkasiV.AnAdaptiveAlgorithmfortheCompressionofComputerData[J].IEEETransactionsonCommunications,1989,COM-37(4)

[5]Rissanen,JormaJ.AUniversalDataCompressionSystem[J].IEEETransactionsonInformationTheory,1983,INFO-29(5)

[6](美)RichardB.Wells著,尹长川等译.工程应用编

×0.714[1.40]0.475[2.11]×1.333

0.633[1.58]

缩比,对一个广播数据的压缩比这个新压缩值还差的概率为0.2%(假定一个正态分布)。这样六个信道中至少有一个不能很好地压缩的概率为1.2%。如果最终压缩值仍然能使数据传输率至少提

码与信息理论[M].北京:机械工业出版社,2003

[7]Wu,WillianW.ElementofDigitalSatelliteCommu2nications,Rockville[M].Md:ComputerSciencePress,1984

(上接第90页)

　　Makela,etal.Indoorgeolocationscienceandtechnology[J].IEEECommunicationsMagazine,2002,40(2):112～

118

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

[3]ChuiT.Y,Thaler.F,Scanlon.W.G.BiterrorraterelatedloadconstraintsforBluetoothbasebandpackets[J].ElectronicsLetters,2002,38(3):137～138

[4]ChatschikB.AnoverviewoftheBluetoothwirelesstechnology[J].IEEECommunicationsMagazine,2003,29(12):86～94

[5]MarksR.B,GiffordI.C,O’HaraB.StandardsinIEEE802unleashthewirelessInternet[J].IEEEMicrowaveMagazine,2004,2(2):46～56

[6]ITU-T,ISO/IECRecommendationX.902,Inter2nationalStandard10746-2.ODPReferenceModel:Descrip2tiveMode,2004