第2章传输层协议设计v4分析解析

清华大学研究生课程,1,Internet传输层协议设计,徐恪清华大学计算机系,清华大学研究生课程,2,提纲,传输层协议概述UDP协议简介TCP协议简介与可靠性设计TCP窗口流控TCP拥塞控制机制分析Tahoe,Reno,NewReno,Sack,Vegas等源算法RED等主动队列管理算法,清华大学研究生课程,3,提纲,传输层协议概述UDP协议简介TCP协议简介与可靠性设计TCP窗口流控TCP拥塞控制机制分析Tahoe,Reno,NewReno,Sack,Vegas等源算法RED等主动队列管理算法,清华大学研究生课程,4,TCP/IP协议栈,清华大学研究生课程,5,传输层协议,实现端到端的数据传输ProtocolimplementedentirelyattheendsFate-sharingCompleteness/correctnessoffunctionimplementations,清华大学研究生课程,6,传输层协议,UDPprovidesjustintegrityanddemuxTCPaddsConnection-orientedReliableOrderedPoint-to-pointByte-streamFullduplexFlowandcongestioncontrolled,清华大学研究生课程,7,提纲,传输层协议概述UDP协议简介TCP协议简介与可靠性设计TCP窗口流控TCP拥塞控制机制分析Tahoe,Reno,NewReno,Sack,Vegas等源算法RED等主动队列管理算法,清华大学研究生课程,8,UDP:UserDatagramProtocolRFC768,MinimalTransportService:“Besteffort”service,UDPsegmentsmaybe:LostDeliveredoutofordertoappConnectionless:NohandshakingbetweenUDPsender,receiverEachUDPsegmenthandledindependentlyofothers,Noconnectionestablishment(whichcanadddelay)Simple:noconnectionstateatsender,receiverSmallheaderNocongestioncontrol:UDPcanblastawayasfastasdesired:dubious!,清华大学研究生课程,9,Multiplexing/demultiplexing,multiplexing/demultiplexing:basedonsender,receiverportnumbers,IPaddressessource,destport#sineachsegmentwell-knownportnumbersforspecificapplications,e.g.DNSonport53,gatheringdatafrommultipleappprocesses,envelopingdatawithheader(laterusedfordemultiplexing),sourceport#,destport#,32bits,applicationdata(message),otherheaderfields,TCP/UDPsegmentformat,清华大学研究生课程,10,Multiplexing/demultiplexing,P2,segment-unitofdataexchangedbetweentransportlayerentitiesakaTPDU:transportprotocoldataunit,receiver,H,t,Demultiplexing:deliveringreceivedsegmentstocorrectapplayerprocesses,segment,segment,M,P1,P3,P4,segmentheader,application-layerdata,清华大学研究生课程,11,UDP,cont.,OftenusedforstreamingmultimediaappsLosstolerantRatesensitiveOtherUDPuses(why?):DNSSNMPReliabletransferoverUDP:addreliabilityatapplicationlayerApplication-specificerrorrecover!,Sourceport#,Destport#,32bits,Applicationdata(message),UDPsegmentformat,Length,Checksum,Length,inbytesofUDPsegment,includingheader,清华大学研究生课程,12,UDPChecksum,SenderTreatsegmentcontentsassequenceof16-bitintegersChecksum:addition(1scomplementsum)ofsegmentcontentsSenderputschecksumvalueintoUDPchecksumfield,ReceiverComputechecksumofreceivedsegmentCheckifcomputedchecksumequalschecksumfieldvalue:NO-errordetectedYES-noerrordetected.Butmaybeerrorsnonetheless?,Goal:detect“errors”(e.g.,flippedbits)intransmittedsegmentNote:IPonlyhasaheaderchecksum,清华大学研究生课程,13,提纲,传输层协议概述UDP协议简介TCP协议简介与可靠性设计TCP窗口流控TCP拥塞控制机制分析Tahoe,Reno,NewReno,Sack,Vegas等源算法RED等主动队列管理算法,清华大学研究生课程,14,IntroductiontoTCP,Communicationabstraction:ReliableOrderedPoint-to-pointByte-streamFullduplexFlowandcongestioncontrolledProtocolimplementedentirelyattheendsFatesharing,清华大学研究生课程,15,EvolutionofTCP,1975,1980,1985,1990,1982TCPpredictscongestioncollapse,1987Karnsalgorithmtobetterestimateround-triptime,1986Congestioncollapseobserved,1988VanJacobsonsalgorithmscongestionavoidanceandcongestioncontrol(mostimplementedin4.3BSDTahoe),19904.3BSDRenofastretransmitdelayedACKs,1975Three-wayhandshakeRaymondTomlinsonInSIGCOMM75,清华大学研究生课程,16,TCPThroughthe1990s,1993,1994,1996,1994ECN(Floyd)ExplicitCongestionNotification,1993TCPVegas(Brakmoetal)realcongestionavoidance,1994T/TCP(Braden)TransactionTCP,1996SACKTCP(Floydetal)SelectiveAcknowledgement,1996HoeImprovingTCPstartup,1996FACKTCP(Mathisetal)extensiontoSACK,清华大学研究生课程,17,TCPHeader,Sourceport,Destinationport,Sequencenumber,Acknowledgement,Advertisedwindow,HdrLen,Flags,0,Checksum,Urgentpointer,Options(variable),Data,Flags:,SYNFINRESETPUSHURGACK,清华大学研究生课程,18,PrinciplesofReliableDataTransfer,Characteristicsofunreliablechannelwilldeterminecomplexityofreliabledatatransferprotocol(rdt),清华大学研究生课程,19,ReliabilityModels,Reliability=requiresredundancytorecoverfromuncertainlossorotherfailuremodesTwotypesofredundancy:SpatialredundancyindependentbackupcopiesForwarderrorcorrection(FEC)codesProblem:requireshugeoverhead,sincetheFECisalsopartofthepacket(s)itcannotrecoverfromerasureofallpacketsTemporalredundancyretransmitifpacketslost/errorLazy:tradesoffresponsetimeforreliabilityDesignofstatusreportsandretransmissionoptimizationimportant,清华大学研究生课程,20,Forwarderrorcontrol,addredundancytorecoverfromlosses,originalfile(nblocks),infinitenumberofblocks,encoding,lossychannel,receive(1+e)blocks,recoverfile,decoding,清华大学研究生课程,21,TemporalRedundancyModel,Packets,SequenceNumbersCRCorChecksum,StatusReports,ACKsNAKsSACKsBitmaps,Retransmissions,Timeout,清华大学研究生课程,22,Typesoferrorsandeffects,Forwardchannelbit-errors(garbledpackets)Forwardchannelpacket-errors(lostpackets)Reversechannelbit-errors(garbledstatusreports)Reversechannelpacket-errors(loststatusreports)Protocol-inducedeffects:DuplicatepacketsDuplicatestatusreportsOut-of-orderpacketsOut-of-orderstatusreportsOut-of-rangepackets/statusreports(inwindow-basedtransmissions),清华大学研究生课程,23,Mechanisms,Mechanisms:Checksuminpkts:detectspktcorruptionACK:“packetcorrectlyreceived”NAK:“packetincorrectlyreceived”Providesreliabletransmissionover:Aforwardchannelwhichhasbit-errors;reverse:okCannothandlereverse-channelbit-errors;orpacket-lossesineitherdirection,清华大学研究生课程,24,MoreMechanisms,Mechanisms:Checksum:detectscorruptioninpktstransmitnewpacket(s)Onnon-dupACK(1RTTlater),setcwndssthresh(windowdeflation)EnterCA,清华大学研究生课程,91,Example:FR/FR,FastretransmitRetransmiton3dupACKsFastrecoveryInflatewindowwhilerepairinglosstofillpipe,time,S,time,R,8,cwnd,8,ssthresh,清华大学研究生课程,92,Summary:Reno,BasicideasFastrecoveryavoidsslowstartdupACKs:fastretransmit+fastrecoveryTimeout:fastretransmit+slowstart,slowstart,retransmit,congestionavoidance,FR/FR,dupACKs,timeout,清华大学研究生课程,93,NewReno:Motivation,On3dupACKs,receiverhaspackets2,4,6,cwnd=8,retransmitspkt1,enterFR/FRNextdupACKincrementcwndto9AfteraRTT,ACKarrivesforpkts1&2,exitFR/FR,cwnd=5,8unackedpktsNomoreACK,sendermustwaitfortimeout,1,2,time,S,time,R,3,4,5,6,8,7,1,FR/FR,10,9,0,0,0,0,0,8unackdpkts,2,清华大学研究生课程,94,NewRenoFall&Floyd96,(RFC2583),Motivation:multiplelosseswithinawindowPartialACKacknowledgessomebutnotallpacketsoutstandingatstartofFRPartialACKtakesRenooutofFR,deflateswindowSendermayhavetowaitfortimeoutbeforeproceedingIdea:partialACKindicateslostpacketsStaysinFR/FRandretransmitsimmediatelyRetransmits1lostpacketperRTTuntilalllostpacketsfromthatwindowareretransmittedEliminatestimeout,清华大学研究生课程,95,SACKMathis,Mahdavi,Floyd,Romanow96(RFC2018,RFC2883),Motivation:Reno&NewRenoretransmitatmost1lostpacketperRTTPipecanbeemptiedduringFR/FRwithmultiplelossesIdea:SACKprovidesbetterestimateofpacketsinpipeSACKTCPoptiondescribesreceivedpacketsOn3dupACKs:retransmits,halveswindow,entersFRUpdatespipe=packetsinpipeIncrementwhenlostornewpacketssentDecrementwhendupACKreceivedTransmitsa(lostornew)packetwhenpipecwndExitFRwhenallpacketsoutstandingwhenFRwasenteredareacknowledged,清华大学研究生课程,96,TCPReno(Jacobson1990),SS,time,window,CA,SS:SlowStartCA:CongestionAvoidance,清华大学研究生课程,97,TCPVegas(Brakmo&Peterson1994),SS,time,window,CA,Converges,noretransmissionprovidedbufferislargeenough,清华大学研究生课程,98,foreveryRTTifW/RTTminW/RTTbthenW-foreverylossW:=W/2,VegasCAalgorithm,清华大学研究生课程,99,Implications,Congestionmeasure=end-to-endqueueingdelayAtequilibriumZerolossStablewindowatfullutilizationApproximatelyweightedproportionalfairnessNonzeroqueue,largerformoresourcesConvergencetoequilibriumConvergesifsufficientnetworkbufferOscillateslikeRenootherwise,清华大学研究生课程,100,提纲,传输层协议概述UDP协议简介TCP协议简介与可靠性设计TCP窗口流控TCP拥塞控制机制分析Tahoe,Reno,NewReno,Sack,Vegas等源算法RED等主动队列管理算法,清华大学研究生课程,101,RED(Floyd&Jacobson1993),Idea:warnsourcesofincipientcongestionbyprobabilisticallymarking/droppingpacketsLinkalgorithmtoworkwithsourcealgorithm(Reno)Bonus:desynchronizationPreventburstylosswithbufferoverflows,清华大学研究生课程,102,RED(Floyd&Jacobson1993),time,window,host,清华大学研究生课程,103,RED,ImplementationProbabilisticallydroppacketsProbabilisticallymarkpacketsMarkingrequiresECNbit(RFC2481)PerformanceDesynchronizationworkswellExtremelysensitivetoparametersettingFailtopreventbufferoverflowas#sourcesincreases,清华大学研究生课程,104,SALLYFLOYD,2007SIGCOMMAward2005IEEEInternetAwardForcontributionstotheInternetarchitecture,particularlyintheareasofcongestioncontrol,trafficmodeling,andactivequeuemanagement.,清华大学研究生课程,105,Variant:ARED,Motivation:REDextremelysensitiveto#sourcesIdea:adaptmaxptoloadIfavg.queuemaxth,increasemaxpNoper-flowinformationneeded,清华大学研究生课程,106,Variant:FRED,Motivation:markingpacketsinproportiontoflowratedoesnotleadtofairbandwidthsharing(e.g.,adaptivevsunadaptiveflows)IdeaAflowcanbufferuptominqpacketswithoutbeingmarkedAflowthatfrequentlybuffersmorethanmaxqpacketsgetspenalizedAllflowswithbacklogsinbetweenaremarkedaccordingtoREDNoflowcanbuffermorethanavgcqpacketspersistentlyNeedper-active-flowaccounting,清华大学研究生课程,107,Variant:BLUE,Motivation:wildoscillationofREDleadstocyclicoverflow&underutilizationAlgorithmOnbufferoverflow,incrementmarkingprobOnlinkidle,decrementmarkingprob,清华大学研究生课程,108,Optimization-basedapproachtowardscongestioncontrol,Resourceallocationasoptimizationproblem:howtoallocateresources(e.g.,bandwidth)tooptimizesomeobjectivefunctionmaybenotpossiblethatoptimalityexactlyobtainedbutoptimizationframeworkasmeanstoexplicitlysteernetworktowardsdesirableoperatingpointpracticalcongestioncontrolasdistributedasynchronousimplementationsofoptimizationalgorithmsystematicapproachtowardsprotocoldesign,清华大学研究生课程,109,c1,c2,Model,Network:LinksleachofcapacityclSourcess:(L(s),Us(xs)L(s)-linksusedbysourcesUs(xs)-utilityifsourcerate=xs,x1,x2,x3,Us(xs),xs,exampleutilityfunctionforelasticapplication,清华大学研究生课程,110,OptimizationProblem,maximizesystemutility(note:allsourcesequal)constraint:bandwidthusedlessthancapacitycentralizedsolutiontooptimizationimpracticalmustknowallutilityfunctionsimpracticalforlargenumberofsourcescongestioncontrolasdistributedasynchronousalgorithmstosolvethisproblem,“system”problem,清华大学研究生课程,111,REM,MainideasDecouplecongestion&performancemeasurePriceadjustedtomatchrateandclearbufferMarkingprobabilityexponentialinprice,REM,RED,Avgqueue,1,清华大学研究生课程,112,CongestionControl,HeavytailMice-elephants,清华大学研究生课程,113,TCP&AQM,Examplecongestionmeasurepl(t)Loss(DropTail)Queuelength(RED)Queueingdelay(Vegas)Price(REM),清华大学研究生课程,114,TCP&AQM,DualitytheoryequilibriumSourceratesxi(t)areprimalvariablesCongestionmeasurespl(t)aredualvariablesCongestioncontrolisoptimizationprocessoverInternet,清华大学研究生课程,115,TCP&AQM,Controltheorystability&robustnessInternetisagiganticfeedbacksystemDistributed&delayed,清华大学研究生课程,116,提纲,传输层协议概述UDP协议简介TCP协议简介与可靠性设计TCP窗口流控TCP拥塞控制机制分析Tahoe,Reno,NewReno,Sack,Vegas等源算法RED等主动队列管理算法,清华大学研究生课程,117,总结,拥塞控制是Internet最重要的问题之一初期研究来自直观和实验TCP源算法RED等链路算法控制理论和优化理论提供了重要的分析工具,清华大学研究生课程,118,其他研究课题,高带宽延迟乘积网络无线网络组播拥塞控制TCP友好的拥塞控制,清华大学研究生课程,119,参考文献,1VanJacobson.CongestionAvoidanceandControl.InProceedingsofACMSIGCOMM,Sept.1988.2W.Stevens.TCPSlowStart,CongestionAvoidance,FastRetransmit,andFastRecoveryAlgorithms.RFC2001,Jan.1997.3L.Brakmo,S.OMalley,andL.Peterson.TCPVegas:Newtechniquesforcongestiondetectionandavoidance.InProceedingsofACMSIGCOMM,1994.4SallyFloydandVanJacobson.R