Routers with Very Small Buffers_免费下载

STANFORDHPNGTECHNICALREPORTTR05-HPNG-0606061

RouterswithVerySmallBuffers

MihaelaEnachescu,YasharGanjali,AshishGoel,NickMcKeown,andTimRoughgarden

∗†‡†∗

∗

DepartmentofComputerScience,StanfordUniversity

{}

mihaela,timr@

†

DepartmentofElectricalEngineering,StanfordUniversity

{}

yganjali,nickm@

‡

DeptofManagementScienceandEngineering,StanfordUniversity

ashishg@

Abstract—Internetroutersrequirebufferstoholdpackets

duringtimesofcongestion.Thebuffersneedtobefast,and

soideallytheyshouldbesmallenoughtoufastmemory

technologiessuchasSRAMorall-opticalbuffering.Unfortu-

nately,awidelyudrule-of-thumbsaysweneedabandwidth-

delayproductofbufferingateachroutersoasnottololink

utilization.Thiscanbeprohibitivelylarge.Inarecentpaper,

Appenzelleretal.challengedthisrule-of-thumbandshowedthat

forabackbonenetwork,thebuffersizecanbedividedbyN

√

withoutsacrificingthroughput,whereNisthenumberofflows

sharingthebottleneck.Inthispaper,weexplorehowbuffersin

thebackbonecanbesignificantlyreducedevenmore,toaslittleas

afewdozenpackets,ifwearewillingtosacrificeasmallamount

oflinkcapacity.WearguethatiftheTCPsourcesarenotoverly

bursty,thenfewerthantwentypacketbuffersaresufficientfor

highthroughput.Specifically,wearguethatO(logW)buffersare

sufficient,whereWisthewindowsizeofeachflow.Wesupport

ourclaimwithanalysisandavarietyofsimulations.Thechange

weneedtomaketoTCPisminimal—eachnderjustneeds

topacepacketinjectionsfromitswindow.Moreover,thereis

someevidencethatsuchsmallbuffersaresufficientevenifwe

don’tmodifytheTCPsourcessolongastheaccessnetworkis

muchslowerthanthebackbone,whichistruetodayandlikely

toremaintrueinthefuture.

Weconcludethatbufferscanbemadesmallenoughforall-

opticalrouterswithsmallintegratedopticalbuffers.

I.MI

OTIVATIONANDNTRODUCTION

Untilquiterecently,Internetrouterswerewidelybelievedto

needlargebuffers.Commercialrouterstodayhavehugepacket

buffers,oftenstoringmillionsofpackets,undertheassumption

thatlargebuffersleadtogoodstatisticalmultiplexingand

henceefficientuofexpensivelong-haullinks.Awidely-ud

rule-of-thumbstatesthat,becauofthedynamicsofTCP’s

congestioncontrolmechanism,arouterneedsabandwidth-

delayproductofbuffering,B=RTT×C,inordertofully

utilizebottlenecklinks[5],[6],[16].Here,Cisthecapacityof

thebottlenecklink,Bisthesizeofthebufferinthebottleneck

router,andRTTistheaverageround-trippropagationdelayof

aTCPflowthroughthebottlenecklink.Recently,Appenzeller

etal.propodusingtheruleB=RTT×C/Ninstead,

√

whereNisthenumberofflowsthroughthebottleneck

link[3].Inabackbonenetworktoday,Nisofteninthe

thousandsorthetensofthousands,andsothesizingrule

B=RTT×C/Nresultsinsignificantlyfewerbuffers.

√

Inthispaper,weexploreifandhowwecouldbuildaWeassumethateachTCPflowdeterminesitswindowsize

networkwithmuchsmallerbuffersstill—perhapswithonlyusingthestandardTCPAIMDscheme.However,ifthecurrent

afewdozenpacketbuffersineachrouter,andperhapsatthe

expenof100%linkutilization.Whilethisisaninteresting

intellectualexerciinitsownright,therewouldbepractical

conquencesifitwerepossible.

First,itcouldfacilitatethebuildingofall-opticalrouters.

Withrecentadvances[8],[9],[13],itisnowpossibleto

performall-opticalswitching,openingthedoortorouterswith

hugecapacityandlowerpowerthanelectronicrouters.Recent

advancesintechnologymakepossibleopticalFCFSpacket

buffersthatcanholdafewdozenpacketsinanintegrated

opto-electronicchip[13].Largerall-opticalbuffersremain

infeasible,exceptwithunwieldyspoolsofopticalfiber(that

canonlyimplementdelaylines,nottrueFCFSpacketbuffers).

Weareinterestedinexploringthefeasibilityofanoperational

all-opticalnetworkwithjustafewdozenopticalpacketbuffers

ineachrouter.

Second,ifbigelectronicroutersrequiredonlyafewdozen

packetbuffers,itcouldreducetheircomplexity,makingthem

easiertobuildandeasiertoscale.Atypical10Gb/srouter

linecardtodaycontainsaboutonemillionpacketbuffers,using

manyexternalDRAMchips.TheboardspacetheDRAMs

occupy,thepinstheyrequire,andthepowertheydissipateall

limitthecapacityoftherouter[3].Ifafewdozenpacket

bufferssuffice,thenpacketbufferscouldbeincorporated

insidethenetworkprocessor(orASIC)inasmallon-chip

SRAM;infact,thebufferswouldonlyoccupyatinyportion

ofthechip.Notonlywouldexternalmemoriesberemoved,

butitwouldallowtheuoffaston-chipSRAM,whichscales

inspeedmuchfasterthanDRAM.

OurmainresultisthatminormodificationstoTCPwould

indeedallowustoreducebuffer-sizestodozensofpackets

withtheexpenofslightlyreducedlinkutilization.Weobtain

thisresultinasuccessionofsteps.Wewillstartbyadopting

twostrongassumptions:(1)Thatwecouldmodifytheway

packetsaretransmittedbyTCPnders,and(2)Thatthe

networkisover-provisioned.However,wewillsoonrelax

theassumptions.

Westartbyaskingthefollowingquestion:Whatifwe

kepttheAIMD(AdditiveIncreaMultiplicativeDecrea)

dynamicsofTCPwindowcontrol,butchangedtheTCP

transmissionschemeto“spaceout”packettransmissionsfrom

theTCPnder,therebymakingpacketarrivalslessbursty?

STANFORDHPNGTECHNICALREPORTTR05-HPNG-0606062

windowsizeattimetisWandthecurrentround-tripestimatethenetworkbeingover-provisioned.Weconsiderasingle

isRTT,thenweassumetheTCPnderndsaccordingtobottlenecklink,andassumethatifeachflowweretondat

aPoissonprocessofrateW/RTTattimet.Thisresultsinitsmaximumwindowsize,thenthelinkwouldbeverely

thesameaveragerateasndingWpacketsperRTT.Whilecongested.Inoursimulations(prentedinSectionIV),

thisisaslightlyunrealisticassumption(itcanresultinthePacedTCPresultsinhighthroughput(around70-80%)with

windowsizebeingviolatedandsomightalterTCPbehaviortherelativelysmallbuffers(10-20)predictedbythesimple

inundesirableways),thisscenarioyieldsimportantcluesabout

thefeasibilityofverysmallbuffers.toextendourformalanalysistotheunder-provisionednetwork

Wearealsogoingtoassumethatthenetworkisover-

provisioned—evenifeachflowisndingatitsmaximum

windowsize,thenetworkwillnotbecongested.Underthe

1

assumptions,weshowthatabuffersizeofO(logW)

max

packetsissufficienttoobtainclotopeakthroughput,where

Wisthemaximumwindowsizeinpackets.Someelements

max

oftheproofareinterestingintheirownright.Theexact

2

scenarioisexplainedinSectionIIandtheproofitlfisin

AppendixI.

Togetsomefeelforthenumbers,considerthescenario

where1000flowssharealinkofcapacity10Gbps.Assume

thateachflowhasanRTTof100ms,amaximumwindow

sizeof64KB,andapacketsizeof1KB.Thepeakrateis

roughly5Gbps.Thebandwidth-delayproductrule-of-thumb

suggestsabuffersizeof125MB,oraround125,000packets.

C/TheRTT×Nrulesuggestsabuffersizeofaround3950

√

packets.Ouranalysissuggestsabuffersizeoftwelvepackets

plussomesmalladditiveconstant,whichbringsthebuffersize

downtotherealmwhereopticalbufferscanbebuiltinthe

nearfuture.

Wethensystematicallyremovethetwoassumptionswe

madeabove,usingacombinationofsimulationsandanalysis.

WefirsttackletheassumptionthatTCPndspacketsina

locallyPoissonfashion.Intuitively,ndingpacketsatfixed

(ratherthanrandom)intervalsshouldgiveusthesamebenefit

(orbetter)asndingpacketsataPoissonrate.Accordingly,

westudythemorereasonablecawheretheTCPnding

agent“paces”itspacketsdeterministicallyoveranentire

RTT.PacedTCPhasbeenstudiedbefore[2],anddoesnot

sufferfromtheproblemofovershootingthewindowsize.

WeperformanextensivesimulationstudyofpacedTCP

withsmallbuffers.Whenthenetworkisover-provisioned,

theperformanceofpacedTCPclolymirrorsouranalytical

boundofO(logW)forPoissonsources.Thisholdsfor

max

awiderangeofcapacitiesandnumberofflows,andnot

justintheregimewhereonemightexpecttheaggregate

arrivalprocessattheroutertorembleaPoissonprocess[4].

TheresultsareprentedinSectionIII.InappendixII,we

provideadditionalintuitionforthisresult:ifmanypacedflows

aresuperimpodafterarandomjitter,thenthepacketdrop

probabilityisassmallaswithPoissontraffic.

Thenextassumptionweattempttoremoveisthatof

1

Thisassumptionislessrestrictivethanitmightappear.CurrentTCP

implementationsusuallycapwindowsizesat32KBor64KB[10],andit

iswidelybelievedthatthereisnocongestioninthecoreoftheInternet.All

opticalnetworks,inparticular,arelikelytobesignificantlyover-provisioned.

Laterwewillrelaxthisassumption,too.

2

Forexample,wedonotneedtoassumetheTCPequation[12]oraggregate

Poissonarrivals[14]—hencewedonotrelyonthesimplifyingassumptions

aboutTCPdynamicsandaboutalargenumberofflowsthatarerequiredfor

thetworesults.

Poisson-transmissionsanalysis.Whilewehavenotbeenable

ca,someanalyticalintuitioncanalsobeobtained:ifwe

assumethattheTCPequation[12]holdsandthattherouter

queuefollowstheM/M/1/Bdynamics,thenbuffersofsize

O(logW)sufficetoutilizeaconstantfractionofthelink

max

capacity.

Ourresultsarequalitativelydifferentfromthebandwidth-

delayrule-of-thumborfromtheresultsofAppenzelleret

al.Onthepositiveside,wehavecompletelyremovedthe

dependenceofthebuffersizeonthebandwidth-delayproduct.

Tounderstandtheimportanceofthis,considerthescaling

wheretheRTTisheldfixedatτ,butthemaximumwindow

sizeW,thenumberofflowsN,andthecapacityCall

max

goto∞suchthatC=NW/τ.Thisisaveryreasonable

max

scalingsinceτislimitedbythespeedoflight,whereasC,N,

andWareallexpectedtokeepgrowingasInternettraffic

max

scales.Underthisscaling,thesizingruleofAppenzelleret

al.suggeststhatthebuffersizeshouldgrowas

√

NW,

max

whereasourresultssuggestthatthebuffersizeneedstogrow

onlyatthemorebenignrateoflogW.Onthenegative

max

side,unliketheresultofAppenzelleretal.,ourresultisa

tradeoffresult—toobtainthislargedecreainbuffers,we

havetosacrificesomefixedfraction(sayaround25%)of

linkcapacity.Thismightbeagoodtradeoffforanall-optical

networkrouterswherebandwidthisplentifulandbuffersare

scarce.Butforelectronicrouters,thistrade-offmightnotmake

n.

Wegiveevidencethatourresultistightinthefollowing

n.

1)Underthescalingdescribedabove,buffersmustatleast

growinproportiontologWtoobtainaconstant

max

factorlinkutilization.InSectionIV-A,weprent

simulationevidencethatconstantsizedbuffersarenot

adequateasthemaximumwindowsizegrowstoinfinity.

Wealsoperformasimplecalculationwhichshowsthe

necessityofthelog-scalingassumingtheTCPequation

andM/M/1/Bqueueing.

2)WhenwerunsimulationswithoutusingPacedTCP,we

cannotobtainreasonablelinkutilizationswithlog-sized

buffers,evenintheover-provisionedca(SectionIII).

WhileTCPpacingisarguablyasmallpricetopayfor

drasticreductioninbuffersizes,itdoesrequireachangeto

end-hosts.Fortunately,wesuspectthisisnotnecessary,as

twoeffectsnaturallyprovidesomepacingincurrentnetworks.

First,theaccesslinksaretypicallymuchslowerthanthecore

links,andsotrafficenteringthecorefromaccesslinksis

automaticallypaced;wecallthisphenomenon“link-pacing”.

Weprentsimulationsshowingthatwithlink-pacingweonly

needverysmallbuffers,becaupacketsarespacedenough

bythenetwork.Second,theACK-clockingschemeofTCP

STANFORDHPNGTECHNICALREPORTTR05-HPNG-0606063

pacespackets[2].Thefullimpactofthetwophenomena

dervesfurtherstudy.

Otherinterestingdirectionsforfurtherstudyincludethe

impactofpacketsizes,theinteractionofswitchscheduling

algorithmsandsmallbuffers,theimpactofshortflows,and

thestabilitypropertiesofTCPwithourlog-scalingrule.

(Significantprogressinanalyzingstabilitywasmaderecently

byRainaandWischik[14].)

Ofcour,significantadditionalwork—includingexperi-

mentalverification,moredetailedanalysis,andlargersim-

ulationstudies—isrequiredbeforeweundertakeadrastic

reductioninbuffersizesinthecurrentInternet.

II.I:P

NTUITIONOISSONINJECTIONSANDAN

OVERPROVISIONEDNETWORK

-

Theintuitionbehindourapproachisquitesimple.Imagine

foramomentthateachflowisanindependentPoissonprocess.

Thisisclearlyanunrealistic(andincorrect)assumption,butit

rvestoillustratetheintuition.Assumetoothateachrouter

behaveslikeanM/M/1queue.Thedrop-ratewouldbeρ,

B

whereρisthelinkutilizationandBisthebuffersize.At

75%loadandwith20packetbuffers,thedropratewouldbe

0.3%,independentoftheRTT,numberofflows,andlink-

rate.Thisshouldbecomparedwithatypical10Gb/srouter

line-cardtodaythatmaintains1,000,000packetbuffers,and

itsbuffersizeisdictatedbytheRTT,numberofflowsand

link-rate.Inesnce,thecostofnothavingPoissonarrivalsis

aboutfiveordersofmagnitudemorebuffering!Aninteresting

questionis:How“Poisson-like”dotheflowsneedtobein

ordertoreapmostofthebenefitofverysmallbuffers?

Toanswerourquestion,assumeNlong-livedTCPflows

shareabottlenecklink.Flowihastime-varyingwindowsize

W(t)andfollowsTCP’sAIMDdynamics.Inotherwords

i

ifthesourcereceivesanACKattimet,itwillincreathe

windowsizeby1/W(t),andiftheflowdetectsapacketloss

i

itwilldecreathecongestionwindowbyafactoroftwo.

Inanytimeinterval(t,t]whenthecongestionwindowsize

󰀁

isfixed,thesourcewillndpacketsasaPoissonprocessat

rateW(t)/RTT.NotethatthisisdifferentfromregularTCP,

i

whichtypicallyndspacketsasaburstatthestartofthe

window.

WewillassumethatthewindowsizeisboundedbyW.

max

Implementationstodaytypicallyhaveaboundimpodbythe

operatingsystem(LinuxdefaultstoW=64kbytes),orthe

max

windowsizeislimitedbythespeedoftheaccesslink.We’ll

makethesimplifyingassumptionthatthetwo-waypropagation

delayofeachflowisRTT.Havingadifferentpropagation

delayforeachflowleadstothesameresults,buttheanalysis

ismorecomplicated.ThecapacityCofthesharedlinkis

assumedtobeatleast(1/ρ)·NW/RTTwhereρissome

max

constantlessthan1.Hence,thenetworkisover-provisioned

byafactorof1/ρ,i.e.thepeakthroughputisρC.Theeffective

utilization,θ,isdefinedastheachievedthroughputdividedby

ρC.

Inthisscenario,thefollowingtheoremholds:

Theorem1:Toachieveaneffectiveutilizationofθ,afactorslowerthanthatofthebottlenecklink,aPoisson-like

bufferofsize

󰀇

󰀁

B≥log(1)

W

1/ρ

max

2

2(1−θ)

suffices.

Proof:SeeAppendixI.

Asanexampleoftheconquencesofthissimplemodel,

ifW=64packets,ρ=0.5,andwewantaneffective

max

utilizationof90%,weneedabuffersizeof15packets

regardlessofthelinkcapacity.Inotherwords,theAIMD

dynamicsofTCPdon’tnecessarilyforceustoularger

buffers,ifthearrivalsarewell-behavedandnon-bursty.So

whathappensifwemakethemodelmorerealistic?Inthe

nextctionweconsiderwhathappensifinsteadofinjecting

packetsaccordingtoaPoissonprocess,eachsourceusPaced

TCPinwhichpacketsarespreaduniformlythroughoutthe

window.

III.PTCP,-

ACEDOVERPROVISIONEDNETWORK

Itshouldcomeasnosurprithatwecanuverysmall

bufferswhenarrivalsarePoisson:arrivalstotherouterare

benignandnon-bursty.Queuestendtobuildup—andhence

weneedlargerbuffers—whenlargeburstsarrive,suchas

whenaTCPsourcendsallofitsoutstandingpacketsat

thestartofthecongestionwindow.Butwecanpreventthis

fromhappeningifwemakethesourcespreadthepacketsover

thewholewindow.Intuitively,thismodificationshouldprevent

burstsandhenceremovetheneedforlargebuffers.Wenow

showthatthisisindeedtheca.Throughoutthisction,we

assumethatthebottlenecklinkisover-provisionedinthesame

nasinthepreviousction.Inthenextctionweremove

thisassumption.

First,suppoNflows,eachwithmaximumwindowsize

W,shareabottlenecklink.Thenthefollowingistrue,

max

undersomemildassumptions(laidoutinappendixII):

Theorem2:Thepacketlossprobabilityduringasin-

gleRTTisO(1/W),if(1)Thebuffersizeisatleast

2

cWlogpackets,wherec>0isasufficientlylarge

max

BmaxB

constant;and(2)Eachflowndspacketsatarateatmost

a1/clogWfractiontimesthatofthebottlenecklink,

Smax

wherecisasufficientlylargeconstant.

S

Proof:SeeAppendixII.

ThebuffersizerequirementforTheorem2(Assumption(1))

iscomparabletothatinTheorem1—afewdozenpackets

forprent-daywindowsizes,independentofthelinkca-

pacity,numberofflows,andRTT.Thisrequirementappears

tobenecessarytoachieveconstantthroughput,evenwith

PacedTCP(eSectionIV-A).Thepacketlossprobability

inTheorem2iscomparabletothatforPoissontrafficwith

thesamebuffersize.Tounderstandthecondassumptionof

Theorem2,notethatifflowscanndatthesamerateasthe

bottlenecklink,thenthereisnopacingoftrafficwhatsoever.

Inthisca,oursimulationsindicatethatconstantthroughput

isnotachievablewithlog-sizedbuffers.Thenaturalgoalis

thustoobtaingoodthroughputwithsmallbuffersprovided

flowsare“sufficientlynon-bursty”.Theorem2quantifiesthis:

aslongasallflowsndataratethatisroughlyalogW

max

STANFORDHPNGTECHNICALREPORTTR05-HPNG-0606064

throughput-buffersizetradeoffisachievable.Thisslowdown3.2Mb/sto3.4Gb/stokeepthepeakloadat80%.Thebuffer

factorisonlyafewdozenforprent-daywindowsizes,sizeisstilltto10packets.Thegraphshowsthatregardless

whileaccesslinksareoftenordersofmagnitudeslowerofthenumberofflows,throughputisimprovedbyPacedTCP.

thanbackbonelinks.ThishugedifferenceinaccesslinkandThethroughputofPacedTCPisaround70%(i.e.,theeffective

backbonelinkspeedsalsoemslikelytopersistinthenearutilizationismorethan85%)whilethethroughputoftheTCP

future(especiallywithanall-opticalbackbone).Renoisaround20%(withaneffectiveutilizationofaround

ToexplorethevalidityofTheorem2,weperformed

simulationsusingthepopularns2simulationtool[1].We

implementedPacedTCPandudvariousvaluesofRTT,

differentnumberofflows,andbuffersizes.

InFigure1wecomparethenumberofbuffersneededby

TCPRenowithPacedTCP.Weplotthethroughputofthe

systemasfunctionofthebuffersizeudintherouter,for

variousnumberofflows.Thecapacityofthebottlenecklinkis

100Mb/s,andtheaverageRTTis100ms.Inthisexperiment,

themaximumcongestionwindowsizeistto32packets,

andthesizeofpacketsis1,000bytes.Thesimulationisrun

for1,000conds,andwestartrecordingthedataafter200

conds.

Aswecane,with40unmodifiedTCP(Reno)flows,we

needtobufferabout100packetstoachieveathroughputabove

80%.However,inthesametting,PacedTCPachieves80%

throughputwithjust10packetbuffers.

Figure2comparesthecongestionwindow(CWND)of

TCPRenowithPacedTCP.Inthisexperiment,500flowsshare

abottlenecklinkwithacapacityof1.5Gb/s;thebuffersizeis

10packets;andeachflowislimitedtoamaximumwindow

sizeof32packets.NoticethatTCPRenorarelyreachesthe

3

maximumwindowsizeof32packets,whereasPacedTCPhas

alargercongestionwindowatalmostalltimes.PacedTCP

flowsexperiencefewerdrops,andsoCWND

growstolarger

values.

120

TCP−Reno

Paced TCP

100

80

_

D

N

W

60

C

40

20

0

0102030405060708090100

Time

Fig.2.Congestionwindowsize(TCPRenovs.PacedTCP)

InFigure1weincreadthesystemloadasweincread

thenumberofflows.It’salsointerestingtoewhathappens

ifwekeepthesystemloadconstant(at80%inthisca)while

increasingthenumberofflows.ThisisillustratedinFigure3,

forflowswithamaximumcongestionwindowof32packets.

Asweincreathenumberofflowsfromonetomorethana

thousand,wealsoincreathebottlenecklinkcapacityfrom

3

NotethatevenifCWNDismorethan32,thesourcedoesn’tallowmore

than32un-acknowledgedpackets.

25%)regardlessofthenumberofflowsinthesystem.

1

Paced TCP

0.9

TCP Reno

0.8

0.7

t

0.6

u

p

h

g

u

o

0.5

r

h

T

0.4

0.3

0.2

0.1

0

1002003004005006007008009001000

Number of flows

Fig.3.PacedTCPvs.TCPReno.

Itisimportanttonotethatthissignificantdiscrepancy

betweenpacedandregularTCPisobrvedonlywithsmall

buffers.Ifweuthebandwidth-delayruleforsizingbuffers,

thisdiscrepancyvanishes.

IV.U-,

NDERPROVISIONEDNETWORKLIMITEDACCESS

LINKCAPACITY

Sofarwehaveassumedthatthenetworkisover-provisioned

andwedonothavecongestiononthelinkunderstudy.Even

thoughthisistrueformostlinksinthecoreoftheInternet,

itisalsointerestingtorelaxthisassumption.Wenextstudy,

viasimulations,howcongestionaffectslinkutilization.

WerepeatanexperimentsimilartothatdepictedinFigure1.

However,weincreathenumberofflowstoupto100.The

averageRTTis100ms,andthemaximumwindowsizeis32

packets.Eachpacketis1000bytes,whichmeanseachflow

cancontributealoadof32∗1000∗8/0.1󰀇2.5Mb/s.The

capacityofthecorelinkis100Mb/s,whichmeanifwehave

morethan40flows,thecorelinkwillbecomecongested.

Figure4showsthethroughputofthebottlenecklinkasa

functionofthebuffersizeforvariousnumberofflows.Wecan

ethatasweincreathenumberofflowsfrom20to40(at

whichpointthelinkstartstobesaturated)thethroughputgoes

fromaround50%toabout80-90%.Aswekeepincreasingthe

numberofflows,to100,and200flows,forsomebuffersizes

weeadegradationinthroughput,butthethroughputnever

goesbelow80%evenwhenthebuffersizeis10packets.

WehaveshownthatPacedTCPcangainaveryhigh

throughputevenwithverysmallbuffers.Averyinteresting

obrvationisthis:ifthecapacityoftheaccesslinksis

muchsmallerthanthecorelink,packetsenteringthecore

willautomaticallyhavespacingbetweenthemevenwithout

modifyingTCP.Wedidsomeexperimentstoverifyifthis

STANFORDHPNGTECHNICALREPORTTR05-HPNG-0606065

1

0.9

0.8

0.7

1

1 flow

10 flows

20 flows

40 flows

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

012

101010

1 flow

10 flows

20 flows

40 flows

T

h

r

o

u

g

h

p

u

t

0.5

0.4

0.3

0.2

0.1

0

0102030405060708090100

Buffer size (packets)

T

h

r

o

u

g

h

p

u

t

0.6

Buffer size (packets)

(a)(b)

1

0.9

0.8

0.7

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

012

101010

1 flow

10 flows

20 flows

40 flows

1 flow

10 flows

20 flows

40 flows

T

h

r

o

u

g

h

p

u

t

0.5

0.4

0.3

0.2

0.1

0

0102030405060708090100

Buffer size (packets)

T

h

r

o

u

g

h

p

u

t

0.6

Buffer size (packets)

(c)(d)

Fig.1.Bottlenecklinkutilizationfordifferentbuffersizesandnumberofflows.(a)unmodifiedTCP(b)unmodifiedTCPwithlogarithmicx-axis(c)paced

TCP(d)pacedTCPwithlogarithmicx-axis.Themaximumpossibleofferedloadis0.026withoneflow,0.26with10flows,0.52with20flows,and1with

40flows.

spacingcanresultinthesamethroughputasPacedTCP.TheConsiderthescaling(describedintheintroduction)wherethe

corelinkbandwidthistto1Gb/s,andwevarythecapacityRTTisheldfixedatτ,butthemaximumwindowsizeW,

oftheaccesslinks.ThemaximumwindowsizeisverylargethenumberofflowsN,andthecapacityCallgoto∞.To

(tto10,000),andthebuffersizeistto10packets,andthecapturethefactthatthenetworkisunder-provisioned,wewill

averageRTTistto100ms.Figure5showsthatwestillgainassumethatC=i.e.thelinkcanonlysupporthalf

ahighutilizationeventhoughwearenotusingPacedTCP.

Here,thex-axisreprentsthecapacityoftheaccesslinks,

andthey-axisreprentsthethroughput.Wecanethatat

thebeginningthethroughputincreas(almost)linearlywith

accesslinkcapacity.Forexample,with100flows,thishappens

whentheaccesslinkcapacityisbelow8-9Mb/s.Notethatthe

normalizedthroughputiscloto100%inthiscasincethe

corelinkisnotthebottleneck.Asweincreatheaccesslink

capacity,thethroughputgraduallydecreas.Thisisbecau

welothenaturalspacingbetweenpacketsasthecapacity

ofaccesslinksisincread.

A.Thenecessityoflogarithmicscalingofbuffer-sizes

Wehavenotbeenabletoextendourproofoftheorem1to

thecawhenthenetworkisunder-provisioned.However,the1)AssumeC=.Foranyconstantα<1,thereex-

TCPequation[12]givesinterestinginsightsifweassumethatistsanotherconstantβsuchthatttingB=βlogW

therouterqueuecanbemodeledasanM/M/1/Bsystem[15].yieldsρ>α.Inotherwords,logarithmicbuffer-sizes

max

max

NW

2τ

max

thepeakrateofeachflow.Similarly,C=reprents

2NW

τ

theunder-provisionedca.

Letpbethedropprobability,andρthelinkutilization.

Clearly,ρ=RN/C,whereRistheaveragethroughputof

eachflow.Then,theTCPequationstates:

1313

R=+o(1/p)󰀇.(2)

τ2pτ2p

󰀆󰀆

√

TheM/M/1/Bassumptionyields[7]:

p=ρ󰀇ρ(3)

BB+1

1−ρρ

B

1−ρ1+ρ

Equations2,3immediatelyyieldthefollowing:

max

NW

2τ

max

STANFORDHPNGTECHNICALREPORTTR05-HPNG-0606066

1

0.9

0.8

0.7

t

u

p

h

0.6

g

u

o

r

h

T

0.5

0.4

0.3

20 Flows

0.2

40 Flows

100 Flows

200 Flows

0.1

10101010

0123

Buffer size (packets)

Fig.4.Bottlenecklinkutilizationvs.thebuffersize.Withonly40flowsthe

corelinkbecomessaturated,butevenifweincreathenumberupto200

flows,thethroughputdoesnotgobelow80%.

0.9

0.8

0.7

0.6

t

u

p

h

0.5

g

u

o

r

h

T

0.4

0.3

0.2

0.1

100 Flows

0

200 Flows

024681012141618

Access link bandwidth (Mb/s)

Fig.5.Throughputasafunctionofaccesslinkcapacity

sufficeforobtainingconstantlinkutilizationevenwhen

thenetworkisunder-provisioned.

2)AssumeC=.IfB=o(logW)thenρ=

2NW

max

max

o(1).Inotherwords,ifthebuffersizegrowsslowerthan

τ

logWthenthelinkutilizationdropsto0eveninthe

max

over-provisionedca.

Obtainingformalproofsoftheabovestatementsremains

aninterestingopenproblem.Simulationevidencesupports

theclaims,ascanbeeninFigure6whichdescribesthe

throughputforaconstantvs.alogarithmicsizedbuffer.For

thissimulationweareusingPacedTCP,Nisheldfixedat

10,Wvariesfrom10to1529,andCvariesasfollows:

max

Cischoninitiallysothatthepeakloadisconstantanda

littleover50%andthischoicedeterminestheinitialvaluefor

theratio;then,sincewefixNandRTT,Cvaries

C

NW

RTT

proportionallytoWkeepingtheaboveratioconstantas

max

max

inourtheoreticalmodeling.Thebuffersizeistto5packets

whenW=10.Thereafter,itincreasinproportionwith

max

logWforthelog-sized-bufferca,andremainsfixedat

max

5fortheconstantbufferca.Here,initiallythethroughput

isaround50%forbothbuffersizingschemes.However,theFirst,itemsthatTCPdynamicshaveverylittleeffecton

throughputfortheconstantsizedbufferdropssignificantlyasbuffer-sizing,andhencetheresultsshouldapplytoavery

C,Wincrea,whileforthelogarithmicsizedbufferthebroadclassoftraffic.Thisissurprising,andcountersthe

max

0.6

Constant buffer size

Logarithmic buffer size

0.55

0.5

n

0.45

o

i

t

a

z

i

l

i

t

U

0.4

0.35

0.3

0.25

05001000150020002500

Link bandwidth (Mb/s)

Fig.6.Constantvs.logarithmicbuffers

throughputremainsapproximatelythesame,justaspredicted

byourtheoreticalmodel.

V.C

ONCLUSIONS

Themainconclusion,ofcour,isthatourresultssuggest

packetbufferscanbemademuchsmaller;perhapsassmall

as10-20packets,ifwearepreparedtosacrificesomeofthe

linkcapacity.Itappearsfromsimulation-thoughwehavenot

beenabletoproveit-thatthebuffersizedictatesdirectlyhow

muchlinkcapacityislost,howevercongestedthenetworkis.

Forexample,a40Gb/slinkwith15packetbufferscouldbe

consideredtooperatelikea30Gb/slink.Thiscould,ofcour,

becompensatedbymakingtherouterrunfasterthanthelink-

rate,andsonotlothelinkcapacityatall.Inafuturenetwork

withabundantlinkcapacity,thiscouldbeaverygoodtradeoff:

Utinybufferssothatwecanprocesspacketsoptically.In

thepast,itwasreasonabletoassumethatpacketbufferswere

cheap,andlong-haullinkswereexpensiveandneededtobe

fullyutilized.Today,fast,largepacketbuffersarerelatively

painfultodesignanddeploy;whereaslinkcapacityisplentiful

anditiscommonforlinkstooperatewellbelowcapacity.This

isevenmoresoinanall-opticalnetworkwherepacketbuffers

areextremelycostlyandcapacityisabundant.

Thebuffer-sizewepropodependsonthemaximumwin-

dowsize.Today,defaultttingsinoperatingsystemslimit

windowsize,butthislimitationwillprobablygoawayover

time.However,evenifthemaximumwindowsizewereto

increaexponentiallywithtimeaccordingtosomeformof

”Moore’slaw”,thebuffersizewouldonlyneedtoincrea

linearlywithtime,whichisaverybenignscalinggivenrecent

technologytrends.

Ourresultsalsoassumethatpacketsaresufficientlyspaced

outtoavoidheavyburstsfromoneflow.Again,slowaccess

linkshelpmakethishappen.Butifthisisnottrue-for

example,whentwosupercomputerscommunicate-theTCP

nderscanbemodifiedtouPacedTCPinstead.

Ourresultsleadtosomeotherinterestingobrvations.

STANFORDHPNGTECHNICALREPORTTR05-HPNG-0606067

prevailingwisdom(andourownpriorassumption)thatbuffers

shouldbemadelargebecauofTCP’ssawtoothbehavior.

A

CKNOWLEDGEMENT

TheauthorswouldliketothankNedaBeheshti,Peter

Glynn,andDamonMosk-Aoyamaforhelpfuldiscussions.

ThisworkwassupportedunderDARPA/MTODOD-Naward

no.W911NF-04-0001/KK4118(LASORPROJECT)andthe

BufferSizingGrantno.W911NF-05-1-0224.Thethirdau-

thor’sworkwasalsosupportedbyanNSFcareergrantand

anAlfredP.Sloanfacultyfellowship,andthefifthauthor’s

workwasalsosupportedinpartbyONRgrantN00014-04-1-

0725.

R

EFERENCES

[1]Thenetworksimulator-ns-2./nsnam/ns/.

[2]A.Aggarwal,S.Savage,andT.Anderson.Understandingtheperfor-

manceofTCPpacing.InProceedingsoftheIEEEINFOCOM,pages

1157–1165,Tel-Aviv,Israel,March2000.

[3]G.Appenzeller,I.Keslassy,andN.McKeown.Sizingrouterbuffers.

InSIGCOMM’04,pages281–292,NewYork,NY,USA,2004.ACM

Press.

[4]J.Cao,W.Cleveland,D.Lin,andD.Sun.Internettraffictendsto

poissonandindependentastheloadincreas.Technicalreport,Bell

Labs,2001.

[5]V.Jacobson.[e2e]re:LatestTCPmeasurementsthoughts.Postingto

theend-to-endmailinglist,March7,1988.

[6]V.Jacobson.Congestionavoidanceandcontrol.ACMComputer

CommunicationsReview,pages314–329,Aug.1988.

[7]F.P.Kelly.Chapter3:QueueingNetworks,pages57–94.Wiley,

Chichester,1979.

[8]V.Lal,J.A.Summers,M.L.Masanovic,L.A.Coldren,andD.J.

Blumenthal.NovelcompactinPbadmonolithicwidely-tunablediffer-

entialMach-Zehnderinterferometerwavelengthconverterfor40Gbps

operation.InIndiumPhosphideandRelatedMaterials,Scotland,2005.

[9]M.L.Masanovic,V.Lal,J.S.Barton,E.J.Skogen,J.A.Sum-

mers,L.Rau,L.A.Coldren,andD.J.Blumenthal.Widely-tunable

monolithically-integratedall-opticalwavelengthconvertersinInP.Jour-

nalofLightwaveTehcnology,23(3),2005.

[10]Microsoft.TCP/IPandnbtconfigurationparametersforwindowsxp.

MicrosoftKnowledgeBaArticle-314053,November4,2003.

[11]R.MotwaniandP.Raghavan.RandomizedAlgorithms.Cambridge

UniversityPress,1995.

[12]J.Padhye,V.Firoiu,D.Towsley,andJ.Kuro.Modelingtcp

throughput:asimplemodelanditsempiricalvalidation.InSIGCOMM

’98,pages303–314,NewYork,NY,USA,1998.ACMPress.

[13]H.Park,E.F.Burmeister,S.Bjorlin,andJ.E.Bowers.40-gb/s

opticalbufferdesignandsimulations.InNumericalSimulationof

OptoelectronicDevices(NUSOD),2004.

[14]G.RainaandD.Wischik.Buffersizesforlarge

multiplexers:Tcpqueueingtheoryandinstabilityanalysis.

/staff/k

/Talks/.

[15]K.RamananandJ.Cao.Apoissonlimitforbufferoverflowprobabili-

ties.InINFOCOM,2002.

[16]C.VillamizarandC.Song.HighperformanceTCPinANSNET.ACM

ComputerCommunicationsReview,24(5):45–60,1994.

AI

PPENDIX

PMT

ROOFOFTHEAINHEOREM

Wewilluthetopologyoffigure7.Thecapacityofthesystemdropsthepacketbutthevirtualsystemdoesn’t,

sharedlink(v,w),whichisdenotedbyC,isassumedtobe

atleast(1/ρ)·NW/RTTwhereρissomeconstantless

max

than1.Hence,thenetworkisover-provisionedbyafactorof

1/ρ,i.e.thepeakthroughputisρC.Theeffectiveutilization,wecanconcludethatQ(t)>Q(t)(tisthetimeright

θ,isdefinedastheachievedthroughputdividedbyρC.Webeforethislastarrival),whichmeans[Q(t)−Q(t)]

sd

11

sd

22

vw

C

sd

NN

Fig.7.Topology

alsoassumethatnodevisanoutputqueuedswitch,andhas

abuffersizeofB.