拥塞缓存设置

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
19,No.
6,June2008,pp.
14991507http://www.
jos.
org.
cnDOI:10.
3724/SP.
J.
1001.
2008.
01499Tel/Fax:+86-10-625625632008byJournalofSoftware.
Allrightsreserved.
TCP流竞争拥塞及拥塞链路的缓存需求研究李玉峰1,2+,邱菡1,兰巨龙1,汪斌强11(国家数字交换系统工程技术研究中心,河南郑州450002)2(防空兵指挥学院信息控制系,河南郑州450052)StudyonTCPFlow-CompetingCongestionandBufferRequirementoftheCongestedLinksLIYu-Feng1,2+,QIUHan1,LANJu-Long1,WANGBin-Qiang11(NationalDigitalSwitchingSystemEngineeringandTechnologicalResearchCenter,Zhengzhou450002,China)2(DepartmentofInformationandControl,AirDefenseCommandCollege,Zhengzhou450052,China)+Correspondingauthor:E-mail:lyf@mail.
ndsc.
com.
cnLiYF,QiuH,LanJL,WangBQ.
StudyonTCPflow-competingcongestionandbufferrequirementofthecongestedlinks.
JournalofSoftware,2008,19(6):14991507.
http://www.
jos.
org.
cn/1000-9825/19/1499.
htmAbstract:Thispaperfirstpresentsananalysismodelnamedflow-competingcongestionmodel(FCCM)forthistypeofcongestion.
BasedonFCCM,thepaperderivesthedistributionofcompetingflowsatthecongestedlink,andanalyzestheconditionsunderwhichtheflow-competingcongestionwouldhappen.
Thispaperalsoexploreshowmuchbuffersacongestedlinkrequirestokeepfulllinkutilizationwhentheflow-competingcongestionoccurs.
Thispaperprovesthatwhensizingbuffersforacongestedinternetlinkwiththeaimofkeepingfulllinkutilization,thebufferrequirementoftheflow-competingcongestionisnotbiggerthantheminimumbufferrequirementofthefamousBSCL(buffersizingforcongestedinternetlinks)scheme.
Keywords:TCPflow;flow-competingcongestion;bufferrequirement;competingflow摘要:针对流竞争拥塞,提出了一种拥塞分析模型FCCM(flow-competingcongestionmodel),给出了TCP竞争流在拥塞链路上的分布特性,推导了流竞争拥塞发生的条件,进而分析了在流竞争拥塞发生时,路由器为维持拥塞链路100%利用率所需的最小缓存.
分析结果表明,当流数目不确定时,应对流竞争拥塞所需的缓存将不大于流数目确定时经典BSCL(buffersizingforcongestedinternetlinks)方案中的最小缓存需求.
关键词:TCP流;流竞争拥塞;缓存需求;竞争流中图法分类号:TP393文献标识码:A路由器是一种存储转发设备,其内部的缓存是分组网络的重要组成部分.
一方面,设置大容量的路由器缓存能够更好地吸收链路上突发性变速率到达的业务,当链路上发生拥塞时,能够对新进入的数据包进行暂存,降低丢包率,维持高链路利用率;另一方面,过大的路由器缓存将导致数据包排队时延的增大,引起时延抖动,降低TCP(transmissioncontrolprotocol)流的吞吐率;此外,小缓存的路由器还能推动全光路由器的建设,降低了路由SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.
2005AA121210(国家高技术研究发展计划(863));theNationalBasicResearchProgramofChinaunderGrantNo.
2007CB307102(国家重点基础研究发展计划(973))Received2006-11-20;Accepted2007-02-081500JournalofSoftware软件学报Vol.
19,No.
6,June2008器的设计复杂度,增加了路由器的可扩展性[13].
因此,研究路由器所需的缓存容量不仅能够优化路由器的设计,提高路由器的性能,提高整个网络的性能,还将对于全光路由器设计中光缓存难题的解决具有重要意义.
然而到目前为止,关于路由器的缓存容量需求问题仍未有科学的结论[4,5].
1994年,Villamizar和Song在文献[6]中给出了路由器缓存需求的经典结论,即著名的带宽时延乘积规则(bandwidth-delayproduct,简称BDP).
多年以来,这个规则一直指导着路由器的设计.
BDP规则就是:为了提高拥塞链路的利用率,路由器所需的缓存容量应当满足BRTTC=*.
其中,B为路由器所需的缓存,RTT是一个TCP连接的平均往返时间(roundtriptime),C为拥塞链路的带宽.
GuidoAppenzeller等人在2004年提出了一种缓存分析模型——斯坦佛模型.
斯坦佛模型的关键思想在于:当拥塞链路上TCP流的数目足够大且非同步时,路由器仅需少量的缓存便可追求链路的高利用率.
其中,文献[7,8,10]认为:骨干网上核心路由器的缓存仅需满足BRTTCN=*即可维持100%的链路利用率,从而将BDP规则的缓存需求大为降低,其中,N代表拥塞链路中长TCP流的数目.
文献[7]中定义的那些从未离开过慢启动阶段的TCP流为短TCP流,反之则为长TCP流.
更进一步地,Enachescu等人在文献[9]中提出:在牺牲少量链路利用率的条件下,少于20个包的缓存容量就能够保证链路实现高吞吐率.
斯坦佛模型对路由器缓存需求的分析是基于链路利用率单个分析目标进行的.
与斯坦佛模型不同,文献[11]探讨了在维持100%链路利用率并且满足确定的丢包率上限值的双重目标上,路由器为应对链路拥塞所需的最小缓存值,也就是路由器缓存分析中著名的BSCL(buffersizingforcongestedinternetlinks)方案.
假设W是拥塞发生前一刻TCP流的平均窗口值,明显地,当NWRTTC≥满足时,链路将发生拥塞.
设B为拥塞链路的缓存需求,则为了应对拥塞应满足BNWRTTC=.
不失一般性,假设拥塞链路的带宽C和平均往返时间RTT为定值,则流数目N和窗口值W就成为影响B值的关键因素.
概括而言,斯坦佛模型和BSCL方案在分析路由器缓存需求的过程中,都是以长的TCP流为研究对象,假定拥塞链路上存在N个长TCP流并且这些TCP流永久存在,在此条件下,链路上拥塞的发生将仅由窗口值W的增长而导致.
实际上,每一个TCP流都有一个有限的传输持续时间和长度,拥塞链路上TCP流的数目N也并不固定,而是一个变量.
尤其需要指出的是,N的突发性增大本身就能导致拥塞的发生.
本文中,我们称这种由于目的输出链路相同的TCP流的数目的突发性增大超过了目的输出链路的处理能力而引起拥塞为"流竞争拥塞".
那么,流竞争拥塞发生的条件是什么路由器为应对流竞争拥塞应设置多大的缓存斯坦佛模型和BSCL方案由于所假定的研究条件的局限性,不可能对这些问题给出答案.
本文中,我们给出了一种新的分析模型——FCCM(flow-competingcongestionmodel),借助该模型,我们推导得出如下3点结论:1)当输入链路上的TCP流数目N和路由器的输入端口数目M都足够大时,若N/M≤5,则目标链路上聚合后的TCP竞争流的流数目服从泊松分布;若N/M>5,则服从正态分布.
2)当路由器的输入端口数目M足够大时,目标链路上由M个输入链路聚合后的TCP竞争流的流数目分布与M无关.
3)在维持目标链路100%链路利用率条件下,应对目标链路上流竞争拥塞所需的最小缓存BFCCM满足BFCCM5,则服从正态分布.
证明:以Xi表示输入链路为li并且目的输出链路为Li的TCP流的数目,其取值范围为{0,1,…,N}.
由于li上的各个TCP流都是独立的,并且在M个输出链路上服从均匀分布,因此,Xi~Bin(N,P),具体为{}knkiNPXkPqk==,其中,P=1/M,q=1P,Xi的均值和方差为E(Xi)=NP,Var(Xi)=NP(1P).
若我们对上式取极限,N→∞,P→0,并且取NP=λ,则将得到0lime!
kkNkPNNPNPqkkλλλ→→∞→=(1)式(1)表明,若N和M足够大,以至于满足条件N→∞,P=1/M→0和NP→λ时,Xi可认为服从泊松分布.
经验上,当NP≤5时,用式(1)取得的计算效果比较理想,而当NP>5时,二项分布取正态分布为极限分布将取得更好的计算效果[13].
总之,李玉峰等:TCP流竞争拥塞及拥塞链路的缓存需求研究1503(),/5~(,(1)),/5iNPNMXNormalNPNPPNMπ≤>.
若以X表示目标链路Li上的TCP竞争流数目,则有1MiiXX==∑.
显然,路由器各个输入链路间相互独立,即Xi(i=1,2,…,M)相互独立.
从而有式(2)成立.
(),/5~(,(1)),/5MNPNMXNormalMNPMNPPNMπ≤>(2)定理1得证.
网络传输速率和业务的快速增长促进了路由器端口速率的快速提高,目前,高端路由器的端口速率通常都达到了10Gb/s.
如此高的端口速率决定了输入链路上TCP流的数目N必然是一个较大的值.
在此基础上,定理1表明,若路由器端口数目M巨大,则路由器的大容量端口交换结构本身就使得目标链路上的TCP流服从泊松分布或者正态分布.
定理2.
当路由器的输入端口数目M足够大时,目标链路上由M个输入链路聚合后的TCP竞争流的流数目分布与M无关.
证明:当P满足P=1/M→0时,式(2)可以变换成(3)(),/5~5NNMXNormalNNNMπ≤>式(3)表明,当M足够大时,目标链路上聚合后的TCP竞争流的数目将与M无关,定理2成立.
同时,式(3)还表明,流竞争拥塞将仅与输入链路上承载的TCP流数目N有关,直观上理解,路由器的输入链路数目M越大,流竞争拥塞将越严重的观点并不成立.
实际上,从长期统计平均上来看,只有每一条输入链路上的TCP流数目N越大,目标链路上聚合后的TCP竞争流数目的均值和方差才越大,流竞争拥塞的可能性也才越大.
3流竞争拥塞发生时目标链路的缓存需求分析本节将以维持目标链路的100%利用率为目的,研究应对流竞争拥塞所需的最佳缓存值.
首先分析流竞争拥塞发生的条件.
3.
1流竞争拥塞发生的条件引理1.
当N>9,M>1且输入链路的链路利用率满足13NNNρ≥≥+时,目标链路上可能发生流竞争拥塞.
证明:在实际的高端路由器中,输入链路上的TCP流数目N和路由器的输入端口数目M基本上都能自然满足N/M>5和P=1/M→0这两个条件,因此在下面的分析中,我们将选择X~Normal(N,N),0≤X≤MN,并以fX(x)作为X的概率密度函数,从而可以得到:0()d1MNXfxx=∫.
若以w′代表能够恰好充满目标链路所需的TCP流数目,近似地,我们可以得到:Nwρ′=(4)设β=Pro{目标链路上发生流竞争拥塞},则有01()d,0wfxxxwβ′′=≤∫≤.
若引入新的虚变量Y满足Y~Normal(N,N),∞≤Y≤+∞,则其概率密度函数为2()21()e,2yNNfyyNπ.
从而有1504JournalofSoftware软件学报Vol.
19,No.
6,June2008~(0YNZNormalN=,1).
由标准正态分布的特性可知,当39且M>1成立时,033NNYNNMN成立.
比较变量X和虚变量Y可知,当N>9且M>1成立时,f(x)可相应地定义为2()21e,33()20,elsexNNNNXNfxNπN(5)此时,β可相应地定义为2()2011ed,32xNwN3xNNxNNβ′π∫N(6)w′代表的是恰好能够充满目标链路的TCP流数目,因此有3NNw′0,w′应满足:3wNN′9且M>1成立,且式(9)满足时β>0,引理1得证.
此外,还可推导:111erferf2222NNNNρβ.
上述3个条件中,N>9且M>1在路由器中可自然成立,我们着重对式(9)的条件进行分析.
首先,该条件表明,只有当输入链路的链路利用率足够大以至于满足式(9)时,目标链路上才有可能发生流竞争拥塞.
其次,该条件还表明,当路由器输入链路的速率降低时,即输入链路上所能承载的TCP流数目N减少时,目标链路上将更容易发生流竞争拥塞;反之,当路由器输入链路的速率升高时,即目标链路上所能承载的TCP流数目N增大时,目标链路上将愈难发生流竞争拥塞.
图4给出了目标链路上发生流竞争拥塞的条件曲线.
明显地,当N0.
77就可能引起目标链路上流竞争拥塞的发生;而当N>1000时,输入链路的链路利用率只有满足ρ>0.
92才有可能导致流竞争拥塞的发生.
对现有网络大量的测量显示,大多数的数据丢失事件都发生在网络的边缘,并非是网络的高速干线上的骨干节点,而现有网络发生数据包丢失事件的主要原因是网络拥塞事件.
因此可以断定,网络的拥塞事件主要发生在接入链路而非核心链路.
式(9)所示的条件为这一拥塞现象提供了有力的证据.
0.
950.
900.
850.
800.
750.
700.
650.
600.
550.
50ρ1002003004005006007008009001000NFig.
4Thesituationlineofflow-competingcongestionhappening图4流竞争拥塞的条件曲线3.
2流竞争拥塞发生时的缓存需求分析以维持100%链路利用率为目的,当目标链路上发生流竞争拥塞时,需要多大的缓存才能应对拥塞本节给出定理3可作为答案.
李玉峰等:TCP流竞争拥塞及拥塞链路的缓存需求研究1505定理3.
在维持目标链路100%链路利用率的条件下,应对目标链路上流竞争拥塞所需的最小缓存BFCCM满足BFCCM5,则服从正态分布.
随后,本文证明了当路由器的输入链路数目M足够大时,目标链路上由M个输入链路聚合后的TCP竞争流的流数目分布与M无关这一结论.
结合前面的结论,本文最后部分分析并给出了流竞争拥塞发生的条件,证明了在维持链路100%利用率目标下,应对流竞争拥塞所需的最小缓存将不大于BSCL方案中的最小缓存需求这一结论,从而为路由器的缓存设置提供了理论指导.
本文中针对流竞争拥塞的缓存分析是以维持链路100%利用率为目标进行的.
在下一步工作中,我们将以丢李玉峰等:TCP流竞争拥塞及拥塞链路的缓存需求研究1507包率和时延为分析目标,探讨路由器的缓存需求,对路由器的缓存设置给出更科学、更全面的理论指导.
References:[1]BeheshtiN,GanjaliY,RajadurayR,BlumenthalD,McKeownN.
Buffersizinginall-opticalpacketswitches.
In:Proc.
oftheOFC/NFOEC.
2006.
36.
http://yuba.
stanford.
edu/buffersizing/[2]AppenzellerG,McKeownN,SommersJ,BarfordP.
Recentresultsonsizingrouterbuffers.
In:Proc.
oftheNetworkSystemsDesignConf.
2004.
1820.
http://tiny-tera.
stanford.
edu/~nickm/papers/index.
html.
[3]GorinskyS,KantawalaA,TurnerJS.
Linkbuffersizing:Anewlookattheoldproblem.
In:Proc.
oftheISCC2005.
Washington:IEEEComputerSociety,2005.
507514.
[4]DhamdhereA,DovrolisC.
Openissuesinrouterbuffersizing.
ACMSIGCOMMComputerCommunicationsReview,2006,36(1):8792.
[5]WischikD.
Bufferrequirementsforhigh-speedrouters.
In:Proc.
oftheECOC2005.
2005.
2326.
http://www.
cs.
ucl.
ac.
uk/staff/D.
Wischik/Research/[6]VillamizarC,SongC.
HighperformanceTCPinANSNET.
ACMComputerCommunicationReview,1994,24(5):4560.
[7]AppenzellerG,KeslassyI,McKeownN.
Sizingrouterbuffers.
ACM/SIGCOMMComputerCommunicationReview,2005,34(4):281292.
[8]RainaG,TowsleyD,WischikD.
PartII:Controltheoryforbuffersizing.
ACM/SIGCOMMComputerCommunicationReview,2005,35(3):7982.
[9]EnachescuM,GanjaliY,GoelA,McKeownN,RoughgardenT.
PartIII:Routerswithverysmallbuffers.
ACM/SIGCOMMComputerCommunicationReview,2005,35(3):8390.
[10]WischikD,McKeownN.
PartI:Buffersizesforcorerouters.
ACM/SIGCOMMComputerCommunicationReview,2005,35(3):7578.
[11]DhamdhereA,JiangH,DovrolisC.
Buffersizingforcongestedinternetlinks.
In:Proc.
oftheIEEEINFOCOM2005.
2005.
10721083.
[12]KarolM,HluchyjM,MorganS.
Inputversusoutputqueueingonaspace-divisionswitch.
IEEETrans.
onCommunications,1999,17(6):10301039.
[13]DevoreJL.
ProbabilityandStatisticsforEngineeringandtheSciences.
6thed.
,SanLuisObispo:BrooksCole,2004.
[14]ChiuD,JainR.
Analysisoftheincreaseanddecreasealgorithmsforcongestionavoidanceincomputernetworks.
ComputerNetworksandISDNSystems,1989,17(1):114.
[15]XuK,XiongYQ,WuJP.
AnalysisofBroadbandIPRouterArchitecture.
JournalofSoftware,2000,11(2):179186(inChinesewithEnglishabstract).
附中文参考文献:[15]徐恪,熊勇强,吴建平.
宽带IP路由器的体系结构分析.
软件学报,2000,11(2):179186.
李玉峰(1976-),男,山东烟台人,博士生,助教,主要研究领域为宽带信息网络,高速路由器核心技术.
兰巨龙(1962-),男,博士,教授,博士生导师,主要研究领域为宽带信息网络,高速路由器核心技术.
邱菡(1981-),女,博士生,助教,主要研究领域为宽带信息网络,流媒体技术.
汪斌强(1973-),男,博士生,助教,主要研究领域为宽带信息网络,高速路由器核心技术.