一种平滑的基于AIMD的TCP拥塞控制算法——SISD*

刘永立

(北京财贸职业学院信息物流系,北京 101101)



一种平滑的基于AIMD的TCP拥塞控制算法——SISD*

刘永立*

(北京财贸职业学院信息物流系,北京 101101)

摘要:提出一种基于AMID(Additive Increase Multiplicative Decrease)的双平滑TCP拥塞控制算法,即SISD(Smooth Increase Smooth Decrease)。SISD算法在数据包发送方面采用一个单调递减函数作为提升速度的增量函数。当检测到网络拥塞时,依据历史拥塞窗口的大小调整发送窗口大小,避免了不必要的网络抖动。仿真结果显示,当UDP、TCP协议并存时,SISD可以为UDP协议提供稳定、平滑的服务,且具备较好的稳定性、公平性,同时提高网络带宽的利用率。

关键词:拥塞控制;双平滑拥塞控制;NS2仿真;加法增乘法减算法

UDP协议不提供可靠数据传输;相反,TCP协议根据数据包反馈和确认机制,可以提供面向链接的可靠数据传输服务。由于像IP语音技术、视频会议等应用不需要数据包的可靠传输服务,因此,在这些应用中,数据传输一般是基于UDP协议的。由于UDP没有拥塞控制机制,网络出现拥塞时,基于UDP协议的应用仍然会持续的按照固定速度发送数据(有时还会提升发送数据的速度),随着应用的增多,网络带宽会非常容易被这些UDP数据流耗尽,还会引起整个网络的瘫痪。由于TCP会随着网络环境灵活调整拥塞窗口,一旦出现拥塞或即将出现拥塞,TCP会降低数据包发送速度;可是,UDP会一直试图争夺带宽,这样便失去公平性[1]。

TCP采用了加法增乘法减AIMD(Additive Increase Multiplicative Decrease)算法的冲突处理机制[2]。其规则是:在链路带宽允许的情况下,以加法速度提升发包速度;在链路带宽耗尽或拥塞出现时,以乘法速度迅速递减发包速度。虽然此方法简单实用,但是当链路中包含大量音频、视频数据流(这些数据流需要持续不断的位传输),非常容易引起速度方面的抖动[3]。为了解决这一问题,本文在AIMD算法基础上提出一个新的拥塞控制算法,称之为双平滑拥塞控制SISD(Smooth Increase Smooth Decrease)。该算法在连接建立阶段,将与发包速度提升相关的参数值设置得较大;随着时间的推移,参数值递减(发包速度仍然提升,只是提升的幅度减低);当检测到拥塞时,参照历史窗口的大小来调整拥塞窗口,而不是简单地大幅度减小窗口大小。该算法在窗口大小的调整上采用一个平滑单调递减的函数,可以有效避免抖动。

1　SISD算法

SISD算法的基本思想来自于经典AIMD算法,并对之进行了修改。在“加法增”时,发包速度平滑提升所依据的是当前速率[4];在“乘法减”时,发包速度平滑降低所依据的是历史窗口的大小[5]。详细说明如下。

X+β(X)→X(β(X)→0,当X→+∞)

(1)

式(1)是基于固定时间间隔,如往返时延RTT(RoundTripTime)的。同时,利用式(2)(jain公平性指数)来评估多数据流情况下的公平性[6]。

(2)

其中,n是数据流数目,xi是第i个数据流在平衡点处的发包速率。FI是一个介于1和0之间的数值。FI=1是最理想的情况。通过下面介绍的方法我们可以达到这样的效果:FI随着xi数值的增大(按照式(1))而增大;随着xi的减小,FI不受影响。这就说明,FI可以作为衡量不同数据流之间公平性的重要指标。图1显示了SAID算法与快速TCP算法(HighSpeedTCP)、可扩展TCP算法(ScalableTCP)、TCPReno算法的对比效果。

图1　SISD算法与TCP其他改进算法的比较

SISD算法中的β(X)函数必须满足如下条件才可以确保算法的有效性并减少网络抖动:当X=0时,β(X)的数值可以很大;当X增大时,β(X)必须快速递减。分段函数β(X)的变化情形如图2所示。图2中的曲线是辅助线,分段函数β(X)由图中的横线段组成。

分段函数β(X)的第1个阶段显示SISD算法检测有效带宽的速度,该阶段的长度也表明该算法的激进程度。随后的每个阶段该函数有较小的增量,这样在平衡点处减小了发送数据包的抖动现象[7]。

图2　分段函数β(X)

(2)当收到负反馈信息,发送速率将会降低。可以采用TCP的窗口机制,通过调整拥塞窗口变量(CWND)的大小来改变发送速率。为了达到此目标,可以按照如式(3)计算窗口变量(CWND)的值。该公式基于Bilinear Transformation的连续型低通过滤器(低通过滤器适用于冲突控制策略[8]),并在其基础上进行离散化。

(CWND_sampletk+CWND_sampletk-1)

(3)

其中,CWNDtk是当t=tk时的拥塞窗口数值。过滤器的截至频率是1/τ,tk-tk-1是2个连续的包丢失事件之间的时间间隔。CWND_sampletk是在时刻tk处的取样数值。在一般的轻度冲突时,CWND_sampletk被设置为CWND/2;在重度冲突时(超时发生时)CWND_sampletk被设置为1。CWND_sampletk-1是在时刻tk-1处的取样数值。

式(3)中,CWNDtk的值依赖于历史数据,包括CWNDtk-1、CWND_sampletk、CWND_sampletk-1以及连续两次包丢失的时间间隔。

为了描述方便,假定δk=tk-tk-1,α=(2τ-δk)/(2τ+δk)。因此,式(3)可以改写为式(4)。

(CWND_sampletk+CWND_sampletk-1)

(4)

从式(4)可见,如果δk(两次包丢失之间的时间间隔)递增,α递减,意味着CWNDtk的值更多地依赖于当前取样数据(相比于历史数据而言)。换句话说,当丢包时间间隔增大,历史数据(CWNDtk-1)对CWNDtk的影响将会降低;相反,若丢包时间间隔减小,α的数值随之增大,CWNDtk的数值将会在更大程度上依赖于历史数据CWNDtk-1,而不是当前取样数据。从而使得拥塞窗口数值的变化呈现平滑过渡的态势。

另外,过滤器的取样频率在公式中也是一个重要因素[9]。过滤器(式(3))有一个截止频率1/τ,这意味着所有频率超过1/τ的频率分量会被过滤掉。基于奈奎斯特频率采样理论,一个信号的采样频率必须不低于它的最大频率分量的两倍[10]。因此,为了按照1/τ的频率对信号采样,采样间隔要小于或等于τ/2。换句话说,CWNDtk必须在τ/2 s之内进行更新。在此情形下,式(3)中的CWND_sampletk可以用当前窗口大小代替。

图3中显示出SISD算法与传统TCP算法在窗口数值计算上的不同。图中黑色实线表示SISD算法窗口变化情况,虚线表示传统TCP窗口变化情况,它们都是分段函数;与时间轴相交的垂直虚线代表算法的更新周期,相邻的2个垂直虚线之间的时间长度是τ/2s(每经过一个更新周期,数值重新计算一次)。图中黑色方框代表通过式(3)计算得到的窗口数值CWNDtk,白色方框代表式(3)中的CWND_sampletk和CWND_sampletk-1,黑色椭圆代表取样数值,在式(3)中该数值用于计算CWND_sampletk。当非严重拥塞发生时,CWND_sampletk是取样数值的一半;严重拥塞发生时,CWND_sampletk=1。

图3　SISD算法描述

图3涉及如下3种情况:

(1)在τ/2 s内出现超时或数据包丢失。过滤器利用历史数据计算新的窗口大小(黑色方框),而不是直接将其降低为拥塞窗口的一半大小。图3中的第1和第2个区间就是这种情况。

(2)超时或丢包发生在2个不同但是连续的τ/2 s内(图3中第2和第3个区间是这种情况)。此时算法通过式(3)计算出窗口大小CWNDtk+2,而不是像传统TCP算法那样将其大小直接降为1。

(3)在τ/2 s内没有数据包丢失(此种情况并未

在图中显示出来)。此种情况下窗口大小的计算采用上一次调度运行时使用的数值;另外,由于没有丢包和超时出现,因此tk-tk-1=τ/2,因此式(3)可以简化为式(5)。在这种情况下,CWND_sampletk数值的获取来自于算法调度,实际上就是当前窗口大小。如果较长一段时间没有发生丢包和超时现象,则窗口值将按照前面所述β(X)的方式持续递增,从而使得发包速度平滑增长。

(CWND_sampletk+CWND_sampletk-1)

(5)

2　性能指标评估

为了评估SISD算法的性能,在NS2模拟器中实现该算法。主要针对SISD、TCP SACK、Scalable TCP、UDP共存情况下,各个算法在平滑性、公平性、稳定性等方面进行比较。

仿真实验的网络拓扑以及参数如图4所示。图中包含2个发送节点、2个接收节点,以及两台2个路由器。它们以瓶颈链路方式相连。

图4　仿真实验网络拓扑

仿真过程中,路由器的缓冲大小设置为带宽延迟积BDP(Bandwidth-Delay Product)的二倍,管理策略采用RED处理机制,RED的最大和最小阀值分别是1.4*BDP和0.4*BDP[11]。另一个重要参数是变量τ,它与低通过滤器的截止频率(1/τ)和调度算法的时钟间隔(τ/2)有紧密的联系。一般而言,τ不能设置得太小。因为在一个很小的时间段内不一定会发生丢包,若将τ设置得太小,会造成调度算法频繁运行。因此,建议将τ/2设置为等于一个往返时延。

通过图5可以发现,SISD算法可以实现拥塞窗口的调整,同时发现,TCP SACK、Scalable TCP算法在调整窗口大小时出现了较大的抖动。通过图6可以发现,当多数据流并存时,SISD算法可以实现数据包发送的平稳过渡。这样,当它为UDP数据流提供持续不断的服务时,就可以满足基于UDP协议应用程序对持续位传输的强烈要求。

图5　单数据流拥塞窗口变化

图6　多数据流拥塞窗口变化

3　结论

本文在研究传统TCP数据流的拥塞控制算法基础上,通过借鉴AIMD算法,提出一个新的拥塞控制算法,命名为SISD。该算法在TCP连接建立阶段,通过控制拥塞窗口的变化,使其初始增速平滑增大;当数据包发送速度接近可用带宽极限且检测到网络拥塞时,算法利用拥塞窗口的历史数据修正窗口大小,使其在拥塞窗口数值增速递减的过程中也同样能够保持平稳。仿真结果显示SISD算法减少了拥塞窗口的抖动,该算法不但能够保持数据包发送速度的相对平稳,而且在TCP、UDP数据流同时存在时,该算法可以确保网络带宽占用的公平性。

参考文献:

[1]刘群,张立娇.无线传感器网络中基于拍卖博弈的数据包转发算法[J].传感技术学报,2013(7):991-996.

[2]吴元保,刘振盛,张文良.基于学习的扩展AIMD拥塞控制机制[J].计算机工程,2008,34(9):232-234.

[3]张丽娟,杨晓萍,陈虹,等.基于自适应参数设置的AIMD算法[J].吉林大学学报,2010,28(1):77-83.

[4]刘俊,谢华.一种改进的TCP拥塞控制算法[J].计算机工程,2011,37(13):95-106.

[5]陈旭,宋爱国.蚂蚁算法与免疫算法结合求解TSP问题[J].传感技术学报.2006(2):504-507.

[6]Marco Dorigo,Thomas Stuitizle.Ant Colony Optimization.[M].北京:清华大学出版社,2007:30-51.

[7]孙文胜,赵玉江.IPv6网络接入控制方法研究与实现.[J].电子器件,2009(5):981-984+988

[8]金纯,陈林星,杨吉云,等.IEEE802.11无线局域网[M].北京:电子工业出版社,2004:1-54.

[9]周洁.基于WIFI传输与接入技术的发展[J].信息通信,2012(2):115-116.

[10]Abdel-Moniem A M,Mohamed M H,Hedar A R,et al.An Ant Colony Optimization Algorithm for the Mobile Ad Hoc Network Routing Problem Based on AODV Protocol[C]//Proceedings of ISDA’10.2010:1332-1337.

[11]黄卫平.TCP/IP协议中拥塞控制算法探讨[J].广西工学院学报,2003,14(2):71-73.

刘永立(1970-),男,汉族,河北涿州市人,北京财贸职业学院教师,软件工程硕士,研究方向为模式识别、人工智能,cgyliu@126.com。

ASmoothTCPCongestionControlAlgorithmBasedonAIMD—SISD*

LIUYongli*

(Beijing Vocational College of Finance and Commerce,Beijing 101101,China)

Abstract:SISD(Smooth Increase Smooth Decrease),a dual smooth TCP congestion control algorithm based on AIMD(Additive Increase Multiplicative Decrease)is presented.SISD uses a decreasing function as the increment in the speed of sending and when the congestion is detected,the current sending rate is changed smoothly referred the historical value of CWND,thus the oscillatory of sending speed is improved.The simulation results show that when the UDP and TCP co-exist,SISD provides a smooth services for UDP,and it has good fairness and stability,meanwhile it can improve the utilization of bandwidth.

Key words:congestion control;SISD;NS2 simulation;AIMD algorithm

doi:EEACC:7210G10.3969/j.issn.1005-9490.2014.04.019

中图分类号:TP393.3

文献标识码:A

文章编号:1005-9490(2014)04-0665-04

收稿日期:2013-09-23修改日期:2013-10-15

项目来源:国家自然科学基金项目(61272350)