`ACKNOWLEDGEMENTINTERVAL
`Athesispresentedto
`TheFacultyof
`TheCollegeofArtsandSciencesofOhioUniversity
`InPartialFul(cid:12)llment
`oftheRequirementsfortheDegree
`MasterofScience
`StacyR.Johnson
`June
`
`INTEL EX. 1100.001
`
`
`
`INCREASINGTCPTHROUGHPUTBYUSINGANEXTENDED
`ACKNOWLEDGEMENTINTERVAL
`BY
`STACYR.JOHNSON
`Thisthesishasbeenapproved
`fortheDepartmentofMathematics
`andtheCollegeofArtsandSciencesby
`ShawnD.Ostermann
`AssistantProfessorofComputerScience
`HaroldMolineu
`Dean,CollegeofArtsandSciences
`
`INTEL EX. 1100.002
`
`
`
`Tomyfamily
`
`To my family
`
`INTEL EX. 1100.003
`
`INTEL EX. 1100.003
`
`
`
`ABSTRACT
`Johnson,StacyR..M.S.,OhioUniversity,June .IncreasingTCPThroughput
`byUsinganExtendedAcknowledgementInterval.MajorProfessor:Dr.ShawnD.
`Ostermann.
`TheTransmissionControlProtocol(TCP)isawidelyusednetworkprotocolthat
`isusuallylayeredovertheInternetProtocol(IP).IPisnotreliable;itdoesnotinsure
`datadelivery.However,TCPisreliable,andinsuresdatadeliverythroughtheuseof
`acknowledgementsandretransmissions.
`ThereceivingsideofaTCPconnectioncurrentlyacknowledgesatleasteveryother
`datablock(segment)thatitreceives.Someoftheseacknowledgementsmaybesu-
`per(cid:13)uous.AlargeportionofaTCPconnection'scostistheoverheadofprocessinga
`newpacketasitarrives.Consequently,itispossiblethatextendingtheacknowledge-
`mentintervalmayincreasethroughputbyrequiringlessacknowledgementoverhead
`perconnection.
`WeimplementedextendedacknowledgementintervalsinUNIX.BSDcompat-
`iblenetworkcode.WecompiledthecodeonaSunIPCworkstationrunningSunOS.
`Totestourhypothesis,weconductedthroughputtestsusingmachinesonthe
`samelocalnetwork,anearnetwork,andadistantnetwork.Analysisofthedata
`revealedthatextendingtheacknowledgementintervaldoesincreasethroughputbya
`statisticallysigni(cid:12)cantamountinthelocalandnearnetworkcases.Inparticular,in
`thelocalcasethethroughputwasincreasedbyasmuchaspercentinsomecases.
`ItisprobablethatcongestionontheInternetandtheresultingpacketlossprevented
`theoverallincreaseinthroughputonthenon-localconnections.
`
`INTEL EX. 1100.004
`
`
`
`ACKNOWLEDGMENTS
`Thankstomyfamilyandmyfriends;yoursupportoverthepastyearisgreatly
`appreciated.SpecialthankstomyfellowmembersofOhioUniversity'sInternetwork-
`ingResearchGroupforthelivelydiscussions.Also,thankstoDr.Ostermannfor
`yourideas,patience,andforintroducingmetothewideworldofnetworking.
`
`INTEL EX. 1100.005
`
`
`
`DISCARDTHISPAGE
`
`DISCARD THIS PAGE
`
`INTEL EX. 1100.006
`
`INTEL EX. 1100.006
`
`
`
`TABLEOFCONTENTS
`ABSTRACT::::::::::::::::::::::::::::::::::::
`LISTOFTABLES:::::::::::::::::::::::::::::::::
`LISTOFFIGURES::::::::::::::::::::::::::::::::
`INTRODUCTION:::::::::::::::::::::::::::::::
` .
` . TCP/IPOverview::::::::::::::::::::::::::::
` .AcknowledgementsinTCP::::::::::::::::::::::::
` .. TCPProcessingOverhead::::::::::::::::::::
` ..CurrentTCPAcknowledgementImplementation::::::::
` .. TimingTCPSegments::::::::::::::::::::::
` ..DelayedAcknowledgementsandtheRoundTripTime
`::::
` . WindowSizeandThroughputinTCP:::::::::::::::::
` .ExtendedAcknowledgementIntervals::::::::::::::::::
`IMPLEMENTATION:::::::::::::::::::::::::::::
`.
`. Environment::::::::::::::::::::::::::::::::
`.
`ImplementationDetails::::::::::::::::::::::::::
`..
`tcpvar.h:TrackingFields::::::::::::::::::::
`..
`tcpinput.c:::::::::::::::::::::::::::::
`..
`tcpoutput.c::::::::::::::::::::::::::::
`..
`tcpsubr.c:::::::::::::::::::::::::::::
`..
`tcptimer.c:::::::::::::::::::::::::::::
`
`
`Page
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INTEL EX. 1100.007
`
`
`
` .EXPERIMENTALRESULTS:::::::::::::::::::::::::
` . .
`StatisticalAnalysis::::::::::::::::::::::::
` . LocalNetwork:::::::::::::::::::::::::::::::
` . . Gatheringdata::::::::::::::::::::::::::
` . .ExperimentswithakWindowSize
`::::::::::::::
` . . Experimentswitha kWindowSize::::::::::::::
` . .Experimentswitha kWindowSize::::::::::::::
` .NearNetwork:::::::::::::::::::::::::::::::
` .. ExplanationofResults::::::::::::::::::::::
` . DistantNetwork:::::::::::::::::::::::::::::
` . . ExplanationofResults::::::::::::::::::::::
`.CONCLUSIONS::::::::::::::::::::::::::::::::
`. Overview::::::::::::::::::::::::::::::::::
`.Conclusions::::::::::::::::::::::::::::::::
`. RecommendationsforFurtherResearch:::::::::::::::::
`BIBLIOGRAPHY:::::::::::::::::::::::::::::::::
`APPENDIX
`A.HOWTOREADATCPTIMESEQUENCEGRAPH:::::::::::
`
`Page
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INTEL EX. 1100.008
`
`
`
`
`Page
`
`
`
`
`LISTOFTABLES
`Table
`:::::::::::::
` . TheE(cid:11)ectofTCPWindowSizeonThroughput
`tcpinput.cTrackingVariables
`:::::::::::::::::::::::
`.
`tcpoutput.cTrackingVariables:::::::::::::::::::::::
`.
`APPENDIX
`Table
`
`INTEL EX. 1100.009
`
`
`
`LISTOFFIGURES
`Figure
` . ProtocolLayeringontheInternet::::::::::::::::::::::
` .TCPHeaderFormat:::::::::::::::::::::::::::::
`. TCPResearchVariableStructure::::::::::::::::::::::
`.ExtendingtheAcknowledgementInterval
`:::::::::::::::::
` . RawThroughputCurve:::::::::::::::::::::::::::
` .AdjustedThroughputCurve
`::::::::::::::::::::::::
` . LocalNetworkThroughput-kBu(cid:11)erSize::::::::::::::::
` .AverageNumberofAcknowledgementsperConnection::::::::::
`kWindowSizeLeadstoAck-Every-OtherConditions::::::::::
` .
` .LocalNetworkThroughput- kBu(cid:11)erSize
`:::::::::::::::
` .E(cid:11)ectofBu(cid:11)erSizeonLocalNetworkThrougput:::::::::::::
` .LocalNetworkThroughput- kBu(cid:11)erSize
`:::::::::::::::
` . ExtendedAcknowledgementIntervalof- kWindowSize:::::::
` . AcknowledgementIntervalof(Default)- kWindowSize:::::::
` . NearNetworkThroughput
`:::::::::::::::::::::::::
` . DistantNetworkThroughput::::::::::::::::::::::::
`A. ExampleTCPTimeSequenceGraph::::::::::::::::::::
`
`
`Page
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INTEL EX. 1100.010
`
`
`
`
` .INTRODUCTION
` . TCP/IPOverview
`Anetworkprotocolisasetofrulesthatcomputersusewhenexchangingdata
`overacomputernetwork.TCPandIParethetwoprotocolsthatformthebasis
`ofsharinginformationovertheInternet.Aprotocolisreliableifitguaranteesdata
`delivery.Anunreliableprotocoldoesnotguaranteedatadelivery.Aprotocolis
`connectionlessifeachpacketsentovertheprotocolistreatedindependently[Com].
`Withaconnectionlessprotocol,eachpacketmaytakeadi(cid:11)erentpathtoreachits
`destination,andthepacketsmayarriveinanyorder.
`Dataissplitintopiecesbeforeitissentoveranetwork.Beforetransmittingthe
`data,theprotocoladdsaheaderthatincludesthesourceanddestinationofthedata.
`OnanEthernet,theresultingunitiscalledaphysicalframe[Com].Atahigher
`protocollevel,eachunitmaybecalledadatagramorasegment.
`Networkprotocolsareoftenlayered.Acompletepacketincludingtheheaderand
`datafromoneprotocolmaybecontained,orencapsulated,withinthedatasection
`ofanotherprotocol.Ahigh-levelprotocolmaybeencapsulatedwithinalow-level
`protocol,whichmayitselfbeencapsulatedwithinanotherprotocol.Eachprotocol
`layeraddsusefulfeaturestotheonebelowit.
`
`INTEL EX. 1100.011
`
`
`
`
`TheInternetProtocol(IP)isanunreliable,connectionlessprotocolthatdeliv-
`ersdatabetweencomputersovertheInternet.EachunitsentusingIPiscalleda
`datagram.
`TheTransmissionControlProtocol(TCP)isareliable,connection-oriented[Com]
`protocolthatdeliversdatabetweenapplications.TCPcanbeusedtodeliverdatabe-
`tweenapplicationsonthesamecomputer,ortodi(cid:11)erentcomputersoveraninternet.
`AlthoughTCPisageneralpurposeprotocolwhichcanbeusedwithseveraldelivery
`systems,ontheInternetitsdataunits,calledsegments,areencapsulatedwithinIP
`datagrams[Com]asshownin(cid:12)gure . .EventhoughTCPisencapsulatedwithin
`theconnectionlessIPprotocol,itisconnection-oriented[Com]becausehostsmust
`negotiatetoopenandcloseaTCPconnection.
`Figure . ProtocolLayeringontheInternet
`WhenusingTCPontheInternet,dataisencapsulatedwithinaTCPsegment,anIP
`datagram,aphysicalframe,andthentransmitted.
`
`Physical network frame
`
`TCP segment
`
`IP datagram
`
`(e.g. Ethernet frame)
`
`INTEL EX. 1100.012
`
`
`
`
` .AcknowledgementsinTCP
`Asmentionedpreviously,IPisanunreliableprotocol.IPhasa\best-e(cid:11)ort"de-
`liveryscheme,butdoesnotguaranteethedeliveryofanydata.Tocompensatefor
`this,TCPisreliable;itguaranteesthedeliveryofdatathroughtheuseofacknowl-
`edgementsandretransmissions..
`EachbyteofdatathatissentthroughaTCPconnectionisacknowledgedusing
`apositiveacknowledgement,whichmeansthatthereceivingTCPacknowledgesdata
`thatitreceives .IfthereceivingTCPdoesnotacknowledgedatawithinacertain
`timelimit(seesection .. )thesendingTCPwillretransmitthedata.TCPac-
`knowledgementsarealsocumulative;ahostacknowledgingreceiptofthenthbyteis
`alsoimplicitlyacknowledgingthereceiptofallbytespreviouston.
`EachsideofaTCPconnectionchoosesaninitialsequencenumberforthe(cid:12)rst
`byteofdatathatTCPsendsoverthenetwork.Subsequentdatabytesarenumbered
`sequentiallystartingatthisnumber.ThereceivingTCPmustacknowledgereceiptof
`everydatabytesentthroughaTCPconnection,atleastcumulatively.Thereceiving
`TCPacknowledgesthedatabysendinganacknowledgement(ACK)whichcontains
`thesequencenumberofthenextbyteitexpectstoreceive.Forexample,ifasegment
`arrivescontainingbyteswiththesequencenumbers - ,thereceivingTCP
`canacknowledgeallofthebytesinthesegmentbysendinganacknowledgement
`containingthesequencenumber .
`TCPconnectionsarefull-duplex,whichmeansthatdatacan(cid:13)owinbothdirections
`simultaneously[Com].The(cid:12)eldsthatareusedforacknowledgementsarecontained
`intheheaderoftheTCPsegment(see(cid:12)gure .),whichallowsTCPtosendan
`acknowledgementanddatainthesamesegment.Thisisknownaspiggybackingan
`acknowledgementonadatasegment.
` Incontrast,someprotocolsuseanegativeacknowledgement;thereceiverwillsendamessageif
`itdoesnotreceiveexpecteddata.
`
`INTEL EX. 1100.013
`
`
`
`16
`
`24
`Destination Port
`
`31
`
`0
`
`4
`Source Port
`
`10
`
`Data Offset
`
`Reserved
`Checksum
`
`Sequence Number
`Acknowledgement Number
`Flags
`
`
`Figure .TCPHeaderFormat[Pos ]
`ThereisspacereservedforanacknowledgementineachTCPsegment.Ahostmay
`senddataandanacknowledgementinthesamepacketbysettingtheacknowledge-
`ment(cid:13)agand(cid:12)llingtheacknowledgement(cid:12)eldwiththe bitsequencenumberof
`thenextbyteitexpectstoreceive.
` .. TCPProcessingOverhead
`AsimpleversionofTCPacknowledgeseverysegmentsent.Thus,foreverydata
`segmentsentoverthenetwork,thereisalsoanacknowledgementsegment.Most
`ofthecostofmaintainingaTCPconnection,intermsofcomputerresources,is
`duetotheoverheadofdealingwithincomingpackets[Cla].RecallthatTCP
`acknowledgementsarecumulative;thosesentneareachothermayberedundant.
`Eliminatingsomeoftheredundantacknowledgementswillhelptoalleviateconnection
`overhead.
`
`Window
`Urgent Pointer
`Padding
`
`Options
`Data (variable length)
`
`INTEL EX. 1100.014
`
`
`
`
` ..CurrentTCPAcknowledgementImplementation
`Thecurrentspeci(cid:12)cationofTCP[Bra ]recommendsdelayedacknowledgements.
`Speci(cid:12)cally,afterreceivingasegment,thereceivingTCPmaydelaysendingthe
`acknowledgementforupto ms.BSD-basedimplementationsofTCPwilldelay
`sendingtheacknowledgementforupto ms[WS ].Ifthehosthasoutgoingdata
`forthesameconnection,TCPcanpiggybacktheacknowledgementonthenextdata
`segment.Thisisusefulforcuttingdownonthenumberofsegmentsininteractive
`connectionssuchasatelnetconnection,whereeachcharactertypedisimmediately
`echoedbacktothesender.Furthermore,accordingtothestandard,thereceiving
`TCPmustsendanacknowledgementforatleasteverysecondsegment[Bra ].
` .. TimingTCPSegments
`Asmentionedpreviously,thereceivingTCPusespositiveacknowledgementsto
`signalreceiptofdatasegments.Ifadatasegmentislostordamaged,thereceiving
`TCPwillnotacknowledgeit.Inthiscase,thesendingTCPneedsamechanismto
`recognizewhentoresendasegment.ThesendingTCPmaintainsaretransmission
`timeoutvalue(RTO),whichistheamountoftimethatTCPwillwaitbeforere-
`sendingasegment[Ste ].
`Theroundtriptime(RTT)ofasegmentistheelapsedtimebetweensendinga
`segmentandreceivinganacknowledgementthatcoversthesegment.TheRTOvalue
`isbasedontheroundtriptimesofTCPsegments(cid:13)owingoverthegivenconnection.
`TheRTTofsegments(cid:13)owingoveraconnectioncanvarywidely[Jac],sotheRTTof
`individualsegmentsarecombinedthroughasmoothingalgorithm[Jac]toprovide
`abetterestimateoftheRTTforsubsequentsegments.
`TCPhastwotimersrunningatalltimes:a msfasttimeranda msslow
`timer.TCPmeasurestheRTTofasegmentinslowtimerticks,agranularityof
`
`INTEL EX. 1100.015
`
`
`
`
`ms[WS ].TheTCPVegasresearchproject[BOP ]claimstohavegottenhigher
`throughputbyusingUNIXtimestampswithamillisecondgranularity,asopposed
`totheslowtimertick.
`TCPtimesonlyonesegmentatatime[Ste ].Consequently,TCPonlytimes
` segmentpereverynsegments,wherenisthenumberofsegmentsintransitata
`giventime.ThesamplingoftheRTTisdependentonthenumberofsegmentsin
`transitsimultaneously[JBB ].Severalsuggestionshavebeenmadeforimproving
`theaccuracyoftheRTTmeasurements.Forexample,ifTCPtimedeverysegment,
`itcouldapplytheRTTtothelastsegmentcoveredbytheacknowledgement.This
`wouldincreasetheRTTsamplingrate,andwouldresultinamoreaccurateRTT.
`SuchaschemeisproposedinTCPVegas[BOP ].TCP'stimestampoption[JBB ]
`o(cid:11)ersanotherwaytogetamoreaccurateRTT.Whenusingthisoption,TCPin-
`cludesatimestampineachsegmentthatissent.Thereceiverechoesthistimestamp
`intheacknowledgementsegment.ThesenderisabletocalculateaRTTforeach
`acknowledgementitreceives[JBB ].Currently,TCPcanonlycalculateaRTTfor
`anacknowledgementofatimedsegment(onesegmentperwindow)[Ste ].
` ..DelayedAcknowledgementsandtheRoundTripTime
`Delayedacknowledgementsa(cid:11)ecttheRTTbecauseofthewaythatTCPcurrently
`timesthesegments(seesection .. ).AssumethatthesendingTCPsendsthe
`segmentitistiming,segmentn,followedbysegmentn+ .IfthereceivingTCP
`delaysacknowledgementofsegmentn,thenthesendingTCPwillcalculatealonger
`RTTforthesegmentnwhenitreceivestheacknowledgementofsegmentn+ [Ste ].
`TCP'stimestampoptionmaybeusedinconjunctionwithdelayedacknowledge-
`ments.Ifdelayedacknowledgementsarebeingused,thereceivingTCPechoesthe
`AUNIXtimestampisanintegerwhichrepresentsthepresenttimeasthenumberofseconds
`sinceJanuary , .
`
`INTEL EX. 1100.016
`
`
`
`
`earliesttimestampitreceivedthatithasnotyetacknowledged.ThesendingTCP
`thenautomaticallytakesintoaccountthetimeforthedelayedacknowledgements
`[JBB ].Whenusingdelayedacknowledgementsasweareinthisresearch,alonger(in-
`correct)RTTmeasurementisvital.IftheRTTisaccurate,TCPmayconstruethe
`longerRTTcausedbythedelayedacknowledgementstomeanlostsegments,and
`startretransmittingsegmentsunnecessarily[Bra ].
` . WindowSizeandThroughputinTCP
`EachsideofaTCPconnectionhasabu(cid:11)erforincomingdata.Theamountof
`bu(cid:11)erspaceavailableiscalledthewindowsize.Datasentthroughtheconnectionis
`heldinthereceivingTCP'sbu(cid:11)ersuntilitcanbedeliveredtotheapplicationreading
`fromtheconnection.Theavailablewindowsizewillvarythroughouttheduration
`oftheconnection,dependingonhowmuchdatahasarrivedatthehostandisstill
`waitingtobeprocessed.
`Ifyouvisualizetheconnectionbetweentwohostsasapipeline,thenthesizeof
`thebu(cid:11)ersonbothsidesoftheconnectionlimithowmuchinformationcanbeinthe
`pipelineatonetime.Theamountofinformationinthepipelinemustneverexceed
`thereceivingTCP'sbu(cid:11)erspace.TCPwillattemptto(cid:12)lltheconnectionbetween
`thehostswithasmuchdataaspossible.Ingeneral,asthebu(cid:11)ersizegrows,sodoes
`theamountofdatathatcanbeintransitatagiventime.
`Throughputisameasureoftheamountofdata(cid:13)owingthroughaconnectionper
`unittime.Ingeneral,onedesirestomaximizethethroughputofagivenconnection.
`TheTCPwindowsizea(cid:11)ectsthroughputbylimitingtheamountofdatathatcanbe
`intransitatagiventime.Forexample,ifthewindowsizeofthereceivinghostis
`
`INTEL EX. 1100.017
`
`
`
`
`small,thenthesendinghostwillhavetopauseperiodicallythroughouttheduration
`oftheconnectiontoallowthewindowtoopenagain[Ste ].
`IfthesendingTCPmanagesto(cid:12)llthereceivingTCP'sbu(cid:11)ers,thereceiving
`TCPwillsendazerowindowadvertisementwhichcausesthesendingTCPtostop
`transmittingdataovertheconnection[Ste ].ThesendingTCPwillsetapersist
`timer;ifithasnotreceivedawindowupdatewhenthetimerexpires,itwillsenda
`messagetothereceivingTCPtoseeifawindowupdatehasbeenlost[Ste ].During
`thetimethatthesendingTCPwaitsforthereceivingTCPtoemptyinformationfrom
`itsbu(cid:11)ers,thepipelinebetweenthehostsmayemptyout.Oncebu(cid:11)erspacebecomes
`available,itwilltaketimetore(cid:12)llthepipewithdataandhavetheconnectionrunning
`at\fullcapacity"again.Table . showsthetheoreticalmaximumthroughputfor
`variouswindowsizes,ascalculatedbythebandwidth-delayproductequation[Ste ].
`RoundTripTime(ms)
`local
`cross-campusKentStateUofKentuckySunsiteCA
`Bu(cid:11)erSize
`(.ms)
`(.ms)
`( ms)
`( ms)
`( ms)
`k
` .
` .
` .
` .
` .
` k
`.
` .
` .
` .
` .
` k
` .
`.
` .
` .
` .
`k
`.
` .
` .
` .
` .
`Table . TheE(cid:11)ectofTCPWindowSizeonThroughput
`Foreachhost/RTTandbu(cid:11)ersizelisted,throughputisshowninMB/s.Themaxi-
`mumpossiblethroughputincreasesastheTCPwindowsize(bu(cid:11)ersize)increases.
`
`INTEL EX. 1100.018
`
`
`
`
` .ExtendedAcknowledgementIntervals
`BasedonourobservationsofTCP,wehypothesizethatextendedacknowledge-
`mentintervalsmayallowforgreaterthroughputonaTCPconnection.TCPcur-
`rentlyrequiresahosttoacknowledgeatleasteveryothersegment[Bra ].Thisisan
`acknowledgementintervaloftwo;twosegmentsmaybereceivedbeforeanacknowl-
`edgementmustbesent.Itispossiblethatextendingtheacknowledgementinterval
`mayincreasethroughputbyrequiringlessacknowledgementoverheadperconnection.
`Theresearchpresentedintherestofthispaperteststhee(cid:11)ectsofextended
`acknowledgementintervalsonthethroughputoflocalandnon-localTCPconnections.
`Chapterfocusesonthenecessaryoperatingsystemchangestoimplementextended
`acknowledgementintervals.Chapter describestheexperimentsperformedwith
`themodi(cid:12)edTCP.Chapterexaminestheresultsoftheexperimentsandgives
`suggestionsforfurtherresearch.
`
`INTEL EX. 1100.019
`
`
`
`
`.IMPLEMENTATION
`. Environment
`Wecompiledanexperimentaloperatingsystem(kernel)onaSunIPCworkstation
`(netipc)runningSunOS. .,fromSunMicrosystems.Wemadechangesto.BSD
`compatiblepublicdomainnetworkingcode,andcompiledthenetworkingcodeinto
`theSunOS. .operatingsystem.TheworkstationisattachedtoalocalEthernet
`network.
`.
`ImplementationDetails
`Fewchangesareneededtoimplementextendedacknowledgementintervalsin
`TCP.Mostofthechangesthatwemadetrackthee(cid:11)ectsoftheextendedacknowl-
`tcpinput.c,tcpoutput.c,tcpsubr.c,
`edgementintervals.Thea(cid:11)ected(cid:12)lesare:
`tcptimer.c,andtcpvar.h.Thefollowingsectionsdescribethechangesmadetoeach
`ofthe(cid:12)les.
`..
`tcpvar.h:TrackingFields
`EachTCPconnectionisassociatedwithaTCPcontrolblockthatholdsinforma-
`tionabouttheconnection.TCPkeepstrackofseveralstatistics.Forexample,TCP
`
`INTEL EX. 1100.020
`
`
`
`
`tracksthenumberofbytessent,thenumberofbytesreceived,andthenumberof
`duplicatepacketsreceived.However,TCPdoesnottracktheseonaper-connection
`basis.Weaddedanewstructurethatcontainsper-connectiontrackingdata((cid:12)g-
`ure. ).TheTCPcontrolblockhasapointertothisstructure.Weplacedcode
`toupdatethesetrackingvariablesnexttowheretheSunOStrackingvariableswere
`maintainedinthebasicTCPcode.
`ThenewversionofTCPalsokeepstrackofthenumberoftimestheextended
`intervalcodeiscalledduringthelifetimeofeachTCPconnection(variablestinc,
`tackdone,andttimeackin(cid:12)gure. ).
`#ifdefTCPEXP
`#defineMT_TCPE
`
`/*mbuftypeforourexperimentalvariables*/
`/*thisshouldbeinmbuf.h
`*/
`/*Thisstructureholdsthetcpexperimentalfields/statistics.*/
`/*ApointertothisstructureislocatedintheTCPcontrolblock.*/
`structtcpe{
`u_long
`t_acknowcnt;
`/*countdowntosettingacknowflag*/
`u_long
`t_inc;
`/*numtimesacknowcntincreased*/
`u_long
`t_ackdone;
`/*numtimesacknowreachedlimit*/
`u_long
`t_timeack;
`/*numtimestimedoutandacked*/
`u_long
`t_sndbyte;
`/*databytessent*/
`u_long
`t_sndrexmitpack;
`/*retransmittedpackets*/
`u_long
`t_sndrexmitbyte;
`/*databytesretransmitted*/
`u_long
`t_sndacks;
`/*ack-onlypacketssent*/
`u_long
`t_rcvbyte;
`/*bytesreceivedinsequence*/
`u_long
`t_rcvdupbyte;
`/*duplicate-onlybytesreceived*/
`u_long
`t_rcvpartdupbyte;
`/*dup.bytesinpart-dup.packets*/
`u_long
`t_rcvackpack;
`/*acksreceived*/
`u_long
`t_rcvackbyte;
`/*bytesackedbyrcvdacks*/
`u_long
`t_rcvdupack;
`/*duplicateackpacketsreceived*/
`};#endif
`Figure. TCPResearchVariableStructure
`Theexperimentalvariablesstructurehousesthevariablesusedinthisresearch.The
`TCPcontrolblockstructurehasapointerleadingtothisstructure.
`
`INTEL EX. 1100.021
`
`
`
`
`tcpinput.c
`..
`Themostextensivelyaltered(cid:12)leintheimplementationistcpinput.c.Thechanges
`totcpinputcomprisethebulkoftheextendedacknowledgementintervalimplemen-
`tation.Theheartofthecodeisshownin(cid:12)gure..
`if(tcp_nodelack== ){
`(tp->t_exp->t_acknowcnt)++;
`(tp->t_exp->t_inc)++;
`if(tp->t_exp->t_acknowcnt==TCPE_ACKNOWCNT){
`tp->t_flags|=TF_ACKNOW;
`tp->t_exp->t_acknowcnt= ;
`(tp->t_exp->t_ackdone)++;
`}elsetp->t_flags|=TF_DELACK;
`}elsetp->t_flags|=TF_ACKNOW;
`Figure.ExtendingtheAcknowldegementInterval
`Thispieceofcodeintcpinput.cchecksthenumberof\outstanding"segmentsto
`seeiftheextendedacknowledgementintervallimithasbeenreached.Ifthelimithas
`beenreached,itsetsa(cid:13)agtoacknowledgethesegment.
`Thispieceofcodeisplacedinthedodatasectionoftcpinput,whichprocessesan
`incomingsegmentandarrangesforanacknowledgmentofthesegment,ifnecessary.
`Ifdelayedacknowledgementsarenotenabled(theyareenabledbydefault),a(cid:13)ag
`issettoacknowledgethepacket.Ifdelayedacknowledgementsareenabled,thenthree
`thingsoccur.First,the(cid:12)eldthatcountsthenumberofoutstandingacknowledgements
`(tacknowcnt)isincremented.Second,thetincisincrementedtoshowthatthe
`outstandingacknowledgements(cid:12)eldwasincremented..Third,TCPdecideswhether
`thecurrentsegmentneedstobeacknowledgedimmediatelybycomparingthenumber
`ofoutstandingacknowledgementstothepresetlimit.
`Ifthenumberofoutstandingacknowledgementsreachesthepresetlimit
`(TCPEACKNOWCNT),thenthe(cid:13)agissettoacknowledgethesegmentimmediately.The
`outstandingacknowledgements(cid:12)eld(tacknowcnt)isreset,andthetrackingvariable
`
`INTEL EX. 1100.022
`
`
`
`
`tackdoneisincrementedtoshowthattheacknowledgementwassentbecausethe
`numberofoutstandingacknowledgementsmetthepresetlimit.
`Thecodethatsetstheinitialthresholdvalueforoutstandingacknowledgements
`(TCPEACKNOWCNT)isalsocontainedintcpinput.c.Settingtheintervaltoevokes
`the\ack-every-other"behaviorofthestandard.BSDTCPcode.
`Thetrackingvariablesalteredbyroutinesintcpinput.carelistedinTable.
`TrackingVariables-Receiving
`Name
`Description
`trcvackbyte
`bytesackedbytheacknowledgementpacketsreceived
`trcvackpack
`acknowledgementpacketsreceived
`trcvbyte
`bytesreceived
`trcvdupack
`duplicateacknowledgementpacketsreceived
`trcvdupbyte
`duplicatebytesreceived
`trcvpartdupbyteduplicatebytesinpartiallyduplicatepackets
`Table. tcpinput.cTrackingVariables
`Thetrackingvariablesthatareincrementedbyroutinesinthetcpinput.c(cid:12)le.
`..
`tcpoutput.c
`Allchangestotcpoutput.cinvolvetrackingthee(cid:11)ectsoftheextendedacknowl-
`edgementintervalsonTCP'ssendingside.Thetrackingvariablesthataremodi(cid:12)ed
`intcpoutput.carelistedin..
`
`INTEL EX. 1100.023
`
`
`
`
`TrackingVariables-Sending
`Name
`Description
`tsndacks
`ack-only(non-piggybacked)acknowledgementssent
`tsndbyte
`databytessent
`tsndrexmitbyte
`retransmittedbytes
`tsndrexmitpackretransmittedpackets
`Table.tcpoutput.cTrackingVariables
`Thetrackingvariablesthatareincrementedbyroutinesinthetcpoutput.c(cid:12)le.
`tcpsubr.c
`..
`WhenanewsocketiscreatedforaTCPconnection,thetcpnewtcpcbsubroutine
`iscalledtoallocateandinitializeanewTCPcontrolblock[WS ].Thecodethatwe
`addedtotcpnewtcpcballocatesandinitializesastructuretoholdtheextravariables
`neededforthisimplementation.TCPaccessesthesevariablesthroughapointerinside
`theTCPcontrolblockstructure.Thecontrolblockcannotholdtheinformationitself
`duetothesizerestrictionsoftheBSDmbufstructure[LMKQ ].
`AclosingTCPconnectioncallsthetcpclosefunction[WS ].Thecodeaddedto
`thisfunctionprintstheconnection'stracking(cid:12)eldvariablestothesystemlog.The
`tcpclosefunctionalsodeallocatesthememoryusedforthetracking(cid:12)eldsstructure.
`..
`tcptimer.c
`TherearetwotimerfunctionsforTCP.Thefasttimeriscalledevery ms,and
`theslowtimeriscalledevery ms.Thefasttimerfunctiondealswiththedelayed
`acknowledgementtimer[WS ].
`Thefasttimercheckstoseeifadelayedacknowledgementiswaitingtobesent.
`Itchecksevery ms,sothedelayedacknowledgementissentbetween and
`
`INTEL EX. 1100.024
`
`
`
`
`msfromthetimeitisprepared.Inadditiontosendingtheacknowledgement,the
`newimplementationresetstheoutstandingacknowledgementscount(tacknowcnt)
`tozero.Italsoincrementsthetrackingvariablethatcountsthenumberofdelayed
`acknowledgementstriggeredbythetimer(asopposedtothepresetoutstandingac-
`knowledgementlimit).
`
`INTEL EX. 1100.025
`
`
`
`
` .EXPERIMENTALRESULTS
`Weranthreegroupsofexperimentstotestthee(cid:11)ectofanextendedacknowledge-
`mentintervalonconnectionthroughput.The(cid:12)rstgroupoftestsranonthelocal
`network.Thesecondgroupoftestsranonanearnetwork,whichisseparatedfrom
`thelocalnetworkbyonebridge.Thethirdgroupoftestsranonadistantnetwork
`overtheInternet.Foreachtestrun,wetransferredalargeamountofdatafroma
`remotemachinetothemachinewiththealteredoperatingsystemandcapturedcon-
`nectionstatisticssuchasthroughputandnumberofretransmissionsforsubsequent
`analysis.
` . .StatisticalAnalysis
`Inordertomakeameaningfulcomparisonbetweenanytwotestbracketsusing
`con(cid:12)denceintervals,weneedanormaldistributionofdatapointsineachbracket
`[Fre ].However,wecannotassumethatasetoftestsmeasuringthroughputbetween
`twogivenmachineswillyieldanormaldistribution.Forexample,(cid:12)gure . contains
`agraphoftherawdataforanextendedacknowledgementintervalof .
`Thecentrallimittheoremstatesthat,givensetsofrandomsamplesfromanin(cid:12)-
`nitepopulation,themeansofthesetsarenormallydistributedregardlessoftheinitial
`distribution[Fre ].Tocomparethedatafromtwoextendedacknowledgementin-
`tervalsettings,wemust(cid:12)rstdividetestsfromeachacknowledgementintervalsetting
`intosets,andthentakethemeansofthesets.Themeanswillformanormaldistri-
`bution,whichcanbeusedtocomparethetwosettings.Figure .showstheadjusted
`throughputgraphfortheextendedacknowledgementinterval .Theadjustedcurve
`
`INTEL EX. 1100.026
`
`
`
`
`
`90
`
`80
`
`70
`
`Raw Local Net Throughput Distribution
`
`3.2
`
`4
`3.8
`3.6
`3.4
`Connection Throughput (MBit/s)
`
`4.2
`
`4.4
`
`4.6
`
`Figure . RawThroughputCurve
`Thisistherawthroughputdistributionfortheextendedacknowledgementinterval
`of ,withabu(cid:11)ersizeofk.
`isapproximatelynormal,whichwillallowcomparisonswiththeadjustedthroughput
`distributionfromanotheracknowledgementintervalsetting.
`Giventheresultsofthetests,wecansaywithacertaincon(cid:12)dencethatthetrue
`meanofthebracketpopulationlieswithinaspeci(cid:12)crange[Fre ].Forexample,
`giventheresultsofthelocaltests,wecansaywitha %con(cid:12)dencelevelthat
`themeanofthroughputsusinganextendedacknowledgementintervalofanda
`bu(cid:11)ersizeofkfallswithintherangeof. Mbit/secto. Mbit/sec.Ifthe
`con(cid:12)denceintervalsfortwoextendedacknowledgementintervalsoverlap,thenthere
`
`60
`
`50
`
`40
`
`30
`
`20
`
`10
`
`0
`2.8
`
`3
`
`Number of Connections
`
`INTEL EX. 1100.027
`
`
`
`
`
`Translated Local Net Throughput Distribution
`
`4.1
`
`4.16
`4.15
`4.14
`4.13
`4.12
`4.11
`Mean Connection Set Throughput
`
`4.17
`
`4.18
`
`0123456
`
`4.09
`
`Number of Connection Sets
`
`Figure .AdjustedThroughputCurve
`Thisistheadjustedthroughputdistributionfortheextendedacknowledgementin-
`tervalof ,withabu(cid:11)ersizeofk.
`isnostatisticaldi(cid:11)erencebetweenthem,i.e.wecannotclaimthatoneextended
`acknowledgementintervalgetsbetterresultsthantheother.
` . LocalNetwork
`Forthepurposesofthisresearch,twomachinesareconsideredtobeonthesame
`localnetworkiftheyareconnectedtothesamephysicalnetworkwithnobridgesor
`routersbetweenthem.Thelocalnetworktestsinvolvedthreemachines,whichareall
`
`INTEL EX. 1100.028
`
`
`
`
`connectedtothesamesectionofEthernet.ThereceivingTCPwasalwayslocatedon
`netipc,aSUNIPCworkstationrunningSunOS. .fromSunMicrosystems,with
`themodi(cid:12)cationslistedinchapter.ThesendingTCPwassometimesrunningon
`netipc ,amachineidenticaltonetipcbutrunninganunmodi(cid:12)edoperatingsystem.
`Theothersendingmachinewasjarok,aSUNSparcrunningSunOS. fromSun
`Microsystems.Experimentsranduringtheearlymorninghours,whenlocalnetwork
`tra(cid:14)cispresumedlow.
` . . Gatheringdata
`TomeasureTCPperformancebetweentwohosts,weusedaprogramcalledttcp.
`ItwascreatedattheU.S.ArmyBallisticsResearchLab(BRL)[Ste ].Thepro-
`gramproducesnetworktra(cid:14)candthenpresentsvariousperformancemeasurements,
`includingthroughput.
`Tomeasurethee(cid:11)ectofchangingtheextendedacknowledgementintervalonthe
`receivingmachine,weranseveraltestsatdi(cid:11)erentextendedacknowledgementinterval
`settings.Wecomparedtheresultsofthetestsusingthestatisticalmethodsoutlined
`insection . ..
` . .ExperimentswithakWindowSize
`Asmentionedinsection . ,thebu(cid:11)ersizeatbothendsofaTCPconnection
`cane(cid:11)ectthroughputconsiderably.Thesizeofthesmallestbu(cid:11)eristhemaximum
`amountofdatathatmaybeintransitatagiventime.Weranthe(cid:12)rstsetof
`experimentsatTCP'sdefaultbu(cid:11)ersizesettingofk( )bytes.
`Overthousandconnectionsranbetweennetipc andnetipc.Thetestswere
`gatheredintosetsof foranalysis.Thegraphin(cid:12)gure . showsthe %con(cid:12)dence
`
`INTEL EX. 1100.029
`
`
`
`
`intervalscalculatedoverthenormallydistributedmeanofeachextendedacknowledge-
`mentinterval.Non-overlappingcon(cid:12)denceintervalsindicateastatisticallysigni(cid:12)cant
`di(cid:11)erenceinthroughput.Thegraphindicatesthatacknowledgingeverythirdseg-
`mentdoesimprovethroughput.However,thethroughputgainsdonotcontinueto
`riseforextendedacknowledgementintervalsoffourandabove.Thereisastatisti-
`callysigni(cid:12)cantdipinthethroughputatextendedacknowledgementinterval .This
`suggestssomeadverseinteractionwithinTCPatthisacknowledgementinterval.
`
`4.2
`
`4.15
`
`Local Net Throughput - 4k Buffer Size (95% conf)
`
`Mbps (avg and confidence interval)
`
`4.1
`
`4.05
`
`4
`
`3.95
`
`3.9
`
`2
`
`4
`
`6
`
`14
`12
`10
`8
`Acknowledgement Interval
`
`16
`
`18
`
`20
`
`Figure . LocalNetworkThroughput-kBu(cid:11)erSize
`Eachdatapointrepresentsthemeanofoneextendedacknowledgementinterval
`bracket.Non-overlappingcon(cid:12)denceintervalsindicateastatisticallysigni(cid:12)cantdif-
`ferenceinthroughput.
`
`INTEL EX. 1100.030
`
`
`
`
` . .. ExplanationofResults
`Inthelocalnetworkcase,extendedacknowledgementintervalsincreasedthrough-
`put.EachdatapointonFigure . representsoneextendedacknowledgementinterval
`setting.Thediamondrepresentsthethroughputmeanatthatinterval,andthever-
`ticalbarthroughthemeanextendsoverthecon(cid:12)denceintervalrange.Wecanstate
`with %con(cid:12)dencethatanextendedacknowledgmentintervalofthreeincreases
`throughput(fromthedefaultof)onalocalnetworkbasis.
`Inthelocalnetworkcase,theRTTdrawbacksofusinganextendedacknowledge-
`mentintervaldonotmakeasigni(cid:12)cantimpact.Oneoftheprincipaldrawbacksof
`usinganextendedacknowledgementintervalisthattheRTTfortheconnectionwill
`bein(cid:13)ated.Thisin(cid:13)atedRTTwillnotmatterunlessasegmentislostorcorrupted.
`Then,theconnectionwilltakelongerto(cid:12)ndoutaboutthesegmentloss.Onthe
`localnet,lostsegments(andthereforeretransmissions)arerare.Retransmittedseg-
`mentsmaybedetectedasbytesarrivingoutoforderintheconnection;throughout
`overtwenty-sixthousandlocalconnections,. percentofthedatabytesappeared
`outoforder.Thus,thein(cid:13)atedRTTseemstohaveaminimale(cid:11)ectonlocalnet
`connections.
`Havingfewerpacketsforagivenconnectionmayallowhigherthroughput[Cla].
`Aspreviouslystated,oneofthemajorsourcesofTCPoverheadisintheinterrupttime
`takentodealwitheachincomingpacket.Theextendedacknowledgementinterval
`allowsforfeweracknowledgementpacketsperconnection,whichcutsdownonthe
`overheadofprocessingpackets[Cla].Inaddition,moreoftheavailablenetwork
`resourcescanbeusedfordatasegments.Figure .showstheaveragenumberof
`acknowledgementsegmentssentfromthereceivingsideofthetestconnectionsat
`
`INTEL EX. 1100.031
`
`
`
`
`eachacknowledgementintervaltested.Theamountofdatatobetransferredandthe
`windowsizewereconstantthroughouttheexperimentalruns.
`
`7000
`
`6000
`
`Avg Number of Acks per Connection - Local Net
`
`Average number of acks sent per connection
`
`5000
`
`4000
`
`3000
`
`2000
`
`1000
`
`0
`
`0
`
`2
`
`4
`
`14
`12
`10
`8
`6
`Acknowledgement Interval
`
`16
`
`18
`
`20
`
`Figure .AverageNumberofAcknowledgementsperConnection
`Theaveragenumberofacknowledgementsperconnectiondropsastheextendedac-
`knowledgementintervalincreases.Feweracknowledgementsegmentsperconnection
`meanslessinterruptoverheadforprocessingtheincomingpacketsofaconnection.
`Throughputlevelso(cid:11)afteranextendedacknowledgementintervalofthree.Recall
`thatthewindowsize(sending/receivingbu(cid:11)ersize)ofthetestconnectionsiskbytes.
`AfterthesendingTCPsendsenoughsegmentsto(cid:12)llthewindow,itwillpauseand
`
`INTEL EX. 1100.032
`
`
`
`
`waitforanacknowledgementbeforesendingadditionaldata[Ste ].Figure .shows
`aTCPtimesequencegraph(seeA)describingtheresultsofusingasmall(k)bu(cid:11)er
`onaTCPconnection.Itisreasonabletoassumethatincreasingthewindowsizewill
`allowgreaterthroughputgainsusingextendedacknowledgementintervals.
`
`jarok.cs.ohiou.edu:48283_==>_netipc2.cs.ohiou.edu:discard
`
`332885000
`
`332880000
`
`332875000
`
`332870000
`
`Figure .kWindowSizeLeadstoAck-Every-OtherConditions
`After(cid:12)llingthewind