TCP拥塞控制建模分析方法

夏爱民,刘 栋,张 帆

(1.南开大学信息技术科学学院,天津300071;2.中国电子设备系统工程公司研究所,北京100141;3.北京航天指挥控制中心,北京100094)

0 引言

近年来,互联网应用呈爆炸式发展,极大地改变了人们的生活方式。不过海量的网络应用带来了非常严重的网络拥塞问题[1-3]。现有的TCP拥塞控制思路、方法和技术在多目标的不同环境中更是面临着挑战。在TCP行为研究及协议设计中,如何得到较好的仿真结果是一个非常迫切的问题。不过现有的建模方法大多是在协议层面的研究,而不是对实际传输的网络情况进行研究。利用着色Petri网(Colored Petri Net,CPN)[4-6]建立TCP传输协议的拥塞控制模型是有效的解决途径之一。通过对模拟结果的分析,说明了该模型能够有效地刻画TCP的拥塞控制特性,从而指导拥塞避免算法的设计。

1 建模仿真

选择时间着色Petri网(Timed CPN,TCPN)来对TCP系统拥塞控制相关行为,包括窗口、延时和缓存等进行描述,拥塞窗口严格按照AIMD变化。此外,为简化分析,假设在发生拥塞时源端始终采用慢启动而不会采用避免阶段算法。

1.1 协议建模

变量的定义参考文献[4]。位置名的含义如下:S表示数据发送源端;Span表示数据发送端的发送间隔;I表示到达瓶颈路由器;B表示瓶颈路由器缓存;W表示等待队列;Wait表示位于等待队列中的数据包的发送间隔;M和R分别表示正在服务的数据包和接收端。另外,变迁名T1T6分别代表数据从源端发送为M发出的数据包贴上不同的时间标签、数据从路由器发送为W等待队列的数据包打上时间标签、数据包丢失、回复Ack、进入路由器以及离开路由器。用CPN对TCP传输控制协议进行建模的结果如图1所示。

图1 利用CPN对TCP建模结果

1.2 仿真过程

图1中数据包从S发出经过T2(该变迁只允许发送拥塞窗口大小的数据包)到达I。如果此时B中有空闲缓存,则实施变迁T4,进入等待队列W,否则实施T1通告丢包,窗口减半。位于等待队列W中的数据包经过T6后被依次标记上固定的间隔时间进入M,该间隔代表路由器对每个数据包的发送延时。变迁T5为每个包加上传输时延后进入R,随后经过T3,数据返回源端,拥塞窗口和确认窗口均增加1。

B、T4和T5以及之间的相互变迁,其作用相当于B到T1存在的一条抑止弧。位置Span的作用在于让每个经过T2变迁发送出去的数据包具有一个不同的时间戳(由于源端实际发送的发送延时)。同理,位置Wait的作用是为了把在等待队列中的数据包在离开时拥有不同时间戳(由于路由器的发送延时)。注意到T2、T1和T3在变迁实施时对拥塞窗口、当前窗口和已确认的最大窗口进行了调整,这是进行拥塞控制的关键。

2 性能分析

如图1所示的CPN模型经过等价变换,可以得到图2所示的网络模型。考虑一条单瓶颈链路,链路中只有一个路由器会发生拥塞,其出口速率为C,缓存大小为B。源端到路由器的延时为Tfw,路由器到收端再由收端返回发端的延时为Tfb。数据包的长度为定值L。

图2 网络模型

类似于经典的拇指规则(Rule of Thumbs)分析,可以获得:

给出了保持链路利用率100%的条件为B≥RTT×C/3,其中RTT=Tfw+Tfb表示往返时延。

式(1)表示源端在t时刻收到阻塞信息,此时的窗口大小等于已发报文的数量,包括路由器缓存中的,链路上传输的以及丢失的ε三部分。式(2)表示源端在窗口减半后停止发送,且须等待W(t)/2的报文被确认,拥塞窗口恢复到原来的位置时才能继续发送,在这一段时间内,路由器以速率C向外发送缓存数据。为保持链路利用率为100%,没有空闲,路由器向外发送的这一段时间应大于源端等待W(t)/2个报文确认的时间。由于采用慢启动算法,每一次确认导致发送端的拥塞窗口值和已被确认序号均增加1,所以要确认减半的W(t)/2个报文,实际只需要W(t)/4个Ack即可。

3 性能测试结果

令C=1Mb/s,B=8 pkt,Tfw=0,Tfb=200 ms,L=1 500 byte。忽略超时重传,并且在路由器使用ECN,即一旦丢包立刻通知源端。对应于CPN模型,位置B的初始标志为8,T3为路由器的服务时间间隔1/μ=12 pkt/ms,在T8到R的弧上要消耗200 ms之后确认信息发回至源端。计算得到B≥5.6≈6 pkts,CPN/Tools模拟结果如图3所示。

图3(a)表示拥塞窗口变化过程,图3(b)表示缓存队列长度变化过程。图中路由器缓存B为3个包大小。可以看到传输的开始阶段因为慢启动,拥塞窗口呈现指数形式的增长,相应的缓存队列长度也有一个逐渐振荡增长的过程。经过一段时间后发生拥塞,可以看到:当缓存小于临界值6时,窗口的变化不规律,稳定性较差,缓存队列在空和满之间剧烈振荡;当缓存为临界值时窗口变化趋于规律的锯齿形,缓存队列也趋向规律振荡,在最小值处恰为0;而当缓存大于临界值时,窗口变化呈现出规律的锯齿形,缓存队列也按规律的V字锯齿形变化,队长始终大于0,即队列不为空,链路利用率为100%。

另外,注意到曲线中有的变化发生于同一时刻,这种现象有2个方面的原因:①因为Petri网能够描述并发,因此同一时刻发生的多次变化能够被记录下来;②当路由器的缓存十分小时,振荡更为剧烈,丢包也更为频繁,因此发送端拥塞窗口值也保持在较低值变化,而由于刻度的关系所以显得更为明显。

图3 拥塞窗口和缓存队列长度变化示意图

因此,在设计拥塞避免机制的过程中,应综合考虑拥塞窗口大小和缓存队列长度。在拥塞比较小的情况下,应该增大拥塞窗口,提高发送速率,同时减小缓存队列,减少排队延迟,从而增大带宽利用率。而在拥塞严重的情况下,应该减小拥塞窗口以减轻对网络的负担,同时增大缓存队列长度,减少拥塞的发生。

4 结束语

在计算机网络传输协议的应用中,CPN具备的模型能力与有效性为计算机网络的Petri网模型方法提供了有益的启示。利用着色Petri网对TCP协议的传输控制进行模拟,形象刻画了协议运行过程中传输控制的各种动作以及协议与网络相互影响的过程。通过模拟发现该模型能够比较准确地体现TCP协议拥塞控制的基本特性,而且由于Petri网对并发过程具备自然的描述能力,网络的并发特性能够得到体现。作为一个TCP拥塞控制的基本模型,由于没有引入额外细节,从而避免了多余的复杂性。该模型可用来模拟和分析各种网络参数,能为协议或者算法设计提供有效的参考。

[1]JACOBSON V.Congestion Avoidance and Control[J].IEEE/ACM Transaction Networking,1998,6(3):314-329.

[2]Caserri C,Meo M.A New Approach to Model the Stationary Behavior of TCP Connections[C].In:Proc IEEE IN FOCOM 2000,Tel Aviv,Israel,2000:367-375.

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

[4]林 闯.计算机网络和计算机系统的性能评价[M]:北京:清华大学出版社,2001.

[5]JENSEN K,COLORED P N.CONCEPTS B.Analysis Methods and Practical Use,Basic Concepts[M].NewYork:Springer-Verlag,1997:25-30.

[6]SUN Xin,FEI Mei-ri,SUN You-xian.The Application of Colored Petri Nets in Systems Analysis[C].Shanghai:Proceedings of The 4th World Congress on Intelligent Control and Automation,2002:582-586.