Computer Networking A Top Down Approach ,Chapter3_5th

TransportLayer 3 1 Chapter3TransportLayer ComputerNetworking ATopDownApproach5thedition JimKurose KeithRossAddison Wesley April2009 Anoteontheuseofthesepptslides We remakingtheseslidesfreelyavailabletoall faculty students readers They reinPowerPointformsoyoucanadd modify anddeleteslides includingthisone andslidecontenttosuityourneeds Theyobviouslyrepresentalotofworkonourpart Inreturnforuse weonlyaskthefollowing Ifyouusetheseslides e g inaclass insubstantiallyunalteredform thatyoumentiontheirsource afterall we dlikepeopletouseourbook Ifyoupostanyslidesinsubstantiallyunalteredformonawwwsite thatyounotethattheyareadaptedfrom orperhapsidenticalto ourslides andnoteourcopyrightofthismaterial Thanksandenjoy JFK KWRAllmaterialcopyright1996 2009J FKuroseandK W Ross AllRightsReserved TransportLayer 3 2 Chapter3 TransportLayer Ourgoals understandprinciplesbehindtransportlayerservices multiplexing demultiplexingreliabledatatransferflowcontrolcongestioncontrol learnabouttransportlayerprotocolsintheInternet UDP connectionlesstransportTCP connection orientedtransportTCPcongestioncontrol TransportLayer 3 3 Chapter3outline 3 1Transport layerservices3 2Multiplexinganddemultiplexing3 3Connectionlesstransport UDP3 4Principlesofreliabledatatransfer 3 5Connection orientedtransport TCPsegmentstructurereliabledatatransferflowcontrolconnectionmanagement3 6Principlesofcongestioncontrol3 7TCPcongestioncontrol TransportLayer 3 4 Transportservicesandprotocols providelogicalcommunicationbetweenappprocessesrunningondifferenthoststransportprotocolsruninendsystemssendside breaksappmessagesintosegments passestonetworklayerrcvside reassemblessegmentsintomessages passestoapplayermorethanonetransportprotocolavailabletoappsInternet TCPandUDP TransportLayer 3 5 Tworklayer networklayer logicalcommunicationbetweenhoststransportlayer logicalcommunicationbetweenprocessesrelieson enhances networklayerservices Householdanalogy 12kidssendinglettersto12kidsprocesses kidsappmessages lettersinenvelopeshosts housestransportprotocol AnnandBillnetwork layerprotocol postalservice TransportLayer 3 6 Internettransport layerprotocols reliable in orderdelivery TCP congestioncontrolflowcontrolconnectionsetupunreliable unordereddelivery UDPno frillsextensionof best effort IPservicesnotavailable delayguaranteesbandwidthguarantees TransportLayer 3 7 Chapter3outline 3 1Transport layerservices3 2Multiplexinganddemultiplexing3 3Connectionlesstransport UDP3 4Principlesofreliabledatatransfer 3 5Connection orientedtransport TCPsegmentstructurereliabledatatransferflowcontrolconnectionmanagement3 6Principlesofcongestioncontrol3 7TCPcongestioncontrol TransportLayer 3 8 Multiplexing demultiplexing application transport network link physical P1 application transport network link physical application transport network link physical P2 P3 P4 P1 host1 host2 host3 process socket deliveringreceivedsegmentstocorrectsocket gatheringdatafrommultiplesockets envelopingdatawithheader laterusedfordemultiplexing TransportLayer 3 9 Howdemultiplexingworks hostreceivesIPdatagramseachdatagramhassourceIPaddress destinationIPaddresseachdatagramcarries1transport layersegmenteachsegmenthassource destinationportnumberhostusesIPaddresses portnumberstodirectsegmenttoappropriatesocket sourceport destport 32bits applicationdata message otherheaderfields TCP UDPsegmentformat TransportLayer 3 10 Connectionlessdemultiplexing Createsocketswithportnumbers DatagramSocketmySocket1 newDatagramSocket 12534 DatagramSocketmySocket2 newDatagramSocket 12535 UDPsocketidentifiedbytwo tuple destIPaddress destportnumber WhenhostreceivesUDPsegment checksdestinationportnumberinsegmentdirectsUDPsegmenttosocketwiththatportnumberIPdatagramswithdifferentsourceIPaddressesand orsourceportnumbersdirectedtosamesocket TransportLayer 3 11 Connectionlessdemux cont DatagramSocketserverSocket newDatagramSocket 6428 SPprovides returnaddress TransportLayer 3 12 Connection orienteddemux TCPsocketidentifiedby4 tuple sourceIPaddresssourceportnumberdestIPaddressdestportnumberrecvhostusesallfourvaluestodirectsegmenttoappropriatesocket ServerhostmaysupportmanysimultaneousTCPsockets eachsocketidentifiedbyitsown4 tupleWebservershavedifferentsocketsforeachconnectingclientnon persistentHTTPwillhavedifferentsocketforeachrequest TransportLayer 3 13 Connection orienteddemux cont ClientIP B serverIP C SP 9157 DP 80 D IP C S IP A D IP C S IP B D IP C S IP B TransportLayer 3 14 Connection orienteddemux ThreadedWebServer ClientIP B serverIP C SP 9157 DP 80 P4 D IP C S IP A D IP C S IP B D IP C S IP B TransportLayer 3 15 Chapter3outline 3 1Transport layerservices3 2Multiplexinganddemultiplexing3 3Connectionlesstransport UDP3 4Principlesofreliabledatatransfer 3 5Connection orientedtransport TCPsegmentstructurereliabledatatransferflowcontrolconnectionmanagement3 6Principlesofcongestioncontrol3 7TCPcongestioncontrol TransportLayer 3 16 UDP UserDatagramProtocol RFC768 nofrills barebones Internettransportprotocol besteffort service UDPsegmentsmaybe lostdeliveredoutofordertoappconnectionless nohandshakingbetweenUDPsender receivereachUDPsegmenthandledindependentlyofothers WhyisthereaUDP noconnectionestablishment whichcanadddelay simple noconnectionstateatsender receiversmallsegmentheadernocongestioncontrol UDPcanblastawayasfastasdesired TransportLayer 3 17 UDP more oftenusedforstreamingmultimediaappslosstolerantratesensitiveotherUDPusesDNSSNMPreliabletransferoverUDP addreliabilityatapplicationlayerapplication specificerrorrecovery sourceport destport 32bits Applicationdata message UDPsegmentformat length checksum Length inbytesofUDPsegment includingheader TransportLayer 3 18 UDPchecksum Sender treatsegmentcontentsassequenceof16 bitintegerschecksum addition 1 scomplementsum ofsegmentcontentssenderputschecksumvalueintoUDPchecksumfield Receiver computechecksumofreceivedsegmentcheckifcomputedchecksumequalschecksumfieldvalue NO errordetectedYES noerrordetected Butmaybeerrorsnonetheless Morelater Goal detect errors e g flippedbits intransmittedsegment TransportLayer 3 19 InternetChecksumExample NoteWhenaddingnumbers acarryoutfromthemostsignificantbitneedstobeaddedtotheresultExample addtwo16 bitintegers 1111001100110011011101010101010101110111011101110111101110111011110010100010001000011 wraparound sum checksum TransportLayer 3 20 Chapter3outline 3 1Transport layerservices3 2Multiplexinganddemultiplexing3 3Connectionlesstransport UDP3 4Principlesofreliabledatatransfer 3 5Connection orientedtransport TCPsegmentstructurereliabledatatransferflowcontrolconnectionmanagement3 6Principlesofcongestioncontrol3 7TCPcongestioncontrol TransportLayer 3 21 PrinciplesofReliabledatatransfer importantinapp transport linklayerstop 10listofimportantnetworkingtopics characteristicsofunreliablechannelwilldeterminecomplexityofreliabledatatransferprotocol rdt TransportLayer 3 22 PrinciplesofReliabledatatransfer importantinapp transport linklayerstop 10listofimportantnetworkingtopics characteristicsofunreliablechannelwilldeterminecomplexityofreliabledatatransferprotocol rdt TransportLayer 3 23 PrinciplesofReliabledatatransfer importantinapp transport linklayerstop 10listofimportantnetworkingtopics characteristicsofunreliablechannelwilldeterminecomplexityofreliabledatatransferprotocol rdt TransportLayer 3 24 Reliabledatatransfer gettingstarted sendside receiveside TransportLayer 3 25 Reliabledatatransfer gettingstarted We ll incrementallydevelopsender receiversidesofreliabledatatransferprotocol rdt consideronlyunidirectionaldatatransferbutcontrolinfowillflowonbothdirections usefinitestatemachines FSM tospecifysender receiver eventcausingstatetransition actionstakenonstatetransition state wheninthis state nextstateuniquelydeterminedbynextevent TransportLayer 3 26 Rdt1 0 reliabletransferoverareliablechannel underlyingchannelperfectlyreliablenobiterrorsnolossofpacketsseparateFSMsforsender receiver sendersendsdataintounderlyingchannelreceiverreaddatafromunderlyingchannel Waitforcallfromabove packet make pkt data udt send packet rdt send data extract packet data deliver data data Waitforcallfrombelow rdt rcv packet sender receiver TransportLayer 3 27 Rdt2 0 channelwithbiterrors underlyingchannelmayflipbitsinpacketchecksumtodetectbiterrorsthequestion howtorecoverfromerrors acknowledgements ACKs receiverexplicitlytellssenderthatpktreceivedOKnegativeacknowledgements NAKs receiverexplicitlytellssenderthatpkthaderrorssenderretransmitspktonreceiptofNAKnewmechanismsinrdt2 0 beyondrdt1 0 errordetectionreceiverfeedback controlmsgs ACK NAK rcvr sender TransportLayer 3 28 rdt2 0 FSMspecification Waitforcallfromabove snkpkt make pkt data checksum udt send sndpkt extract rcvpkt data deliver data data udt send ACK rdt rcv rcvpkt notcorrupt rcvpkt rdt rcv rcvpkt isACK rcvpkt udt send sndpkt rdt rcv rcvpkt isNAK rcvpkt sender receiver rdt send data L TransportLayer 3 29 rdt2 0 operationwithnoerrors Waitforcallfromabove snkpkt make pkt data checksum udt send sndpkt extract rcvpkt data deliver data data udt send ACK rdt rcv rcvpkt notcorrupt rcvpkt rdt rcv rcvpkt isACK rcvpkt udt send sndpkt rdt rcv rcvpkt isNAK rcvpkt Waitforcallfrombelow rdt send data L TransportLayer 3 30 rdt2 0 errorscenario Waitforcallfromabove snkpkt make pkt data checksum udt send sndpkt extract rcvpkt data deliver data data udt send ACK rdt rcv rcvpkt notcorrupt rcvpkt rdt rcv rcvpkt isACK rcvpkt udt send sndpkt rdt rcv rcvpkt isNAK rcvpkt Waitforcallfrombelow rdt send data L TransportLayer 3 31 rdt2 0hasafatalflaw WhathappensifACK NAKcorrupted senderdoesn tknowwhathappenedatreceiver can tjustretransmit possibleduplicate Handlingduplicates senderretransmitscurrentpktifACK NAKgarbledsenderaddssequencenumbertoeachpktreceiverdiscards doesn tdeliverup duplicatepkt Sendersendsonepacket thenwaitsforreceiverresponse TransportLayer 3 32 rdt2 1 sender handlesgarbledACK NAKs Waitforcall0fromabove sndpkt make pkt 0 data checksum udt send sndpkt rdt send data udt send sndpkt rdt rcv rcvpkt corrupt rcvpkt isNAK rcvpkt sndpkt make pkt 1 data checksum udt send sndpkt rdt send data rdt rcv rcvpkt notcorrupt rcvpkt isACK rcvpkt udt send sndpkt rdt rcv rcvpkt corrupt rcvpkt isNAK rcvpkt rdt rcv rcvpkt notcorrupt rcvpkt isACK rcvpkt L L TransportLayer 3 33 rdt2 1 receiver handlesgarbledACK NAKs sndpkt make pkt NAK chksum udt send sndpkt rdt rcv rcvpkt notcorrupt rcvpkt has seq0 rcvpkt rdt rcv rcvpkt notcorrupt rcvpkt has seq1 rcvpkt extract rcvpkt data deliver data data sndpkt make pkt ACK chksum udt send sndpkt rdt rcv rcvpkt notcorrupt rcvpkt has seq0 rcvpkt extract rcvpkt data deliver data data sndpkt make pkt ACK chksum udt send sndpkt rdt rcv rcvpkt corrupt rcvpkt sndpkt make pkt ACK chksum udt send sndpkt rdt rcv rcvpkt notcorrupt rcvpkt has seq1 rcvpkt rdt rcv rcvpkt corrupt rcvpkt sndpkt make pkt ACK chksum udt send sndpkt sndpkt make pkt NAK chksum udt send sndpkt TransportLayer 3 34 rdt2 1 discussion Sender seq addedtopkttwoseq s 0 1 willsuffice Why mustcheckifreceivedACK NAKcorruptedtwiceasmanystatesstatemust remember whether current pkthas0or1seq Receiver mustcheckifreceivedpacketisduplicatestateindicateswhether0or1isexpectedpktseq note receivercannotknowifitslastACK NAKreceivedOKatsender TransportLayer 3 35 rdt2 2 aNAK freeprotocol samefunctionalityasrdt2 1 usingACKsonlyinsteadofNAK receiversendsACKforlastpktreceivedOKreceivermustexplicitlyincludeseq ofpktbeingACKedduplicateACKatsenderresultsinsameactionasNAK retransmitcurrentpkt TransportLayer 3 36 rdt2 2 sender receiverfragments sndpkt make pkt 0 data checksum udt send sndpkt rdt send data udt send sndpkt rdt rcv rcvpkt corrupt rcvpkt isACK rcvpkt 1 rdt rcv rcvpkt notcorrupt rcvpkt isACK rcvpkt 0 senderFSMfragment rdt rcv rcvpkt notcorrupt rcvpkt has seq1 rcvpkt extract rcvpkt data deliver data data sndpkt make pkt ACK1 chksum udt send sndpkt rdt rcv rcvpkt corrupt rcvpkt has seq1 rcvpkt udt send sndpkt receiverFSMfragment L TransportLayer 3 37 rdt3 0 channelswitherrorsandloss Newassumption underlyingchannelcanalsolosepackets dataorACKs checksum seq ACKs retransmissionswillbeofhelp butnotenough Approach senderwaits reasonable amountoftimeforACKretransmitsifnoACKreceivedinthistimeifpkt orACK justdelayed notlost retransmissionwillbeduplicate butuseofseq salreadyhandlesthisreceivermustspecifyseq ofpktbeingACKedrequirescountdowntimer TransportLayer 3 38 rdt3 0sender sndpkt make pkt 0 data checksum udt send sndpkt start timer rdt send data rdt rcv rcvpkt corrupt rcvpkt isACK rcvpkt 1 sndpkt make pkt 1 data checksum udt send sndpkt start timer rdt send data rdt rcv rcvpkt notcorrupt rcvpkt isACK rcvpkt 0 rdt rcv rcvpkt corrupt rcvpkt isACK rcvpkt 0 rdt rcv rcvpkt notcorrupt rcvpkt isACK rcvpkt 1 stop timer stop timer udt send sndpkt start timer timeout udt send sndpkt start timer timeout rdt rcv rcvpkt L rdt rcv rcvpkt L L L TransportLayer 3 39 rdt3 0inaction TransportLayer 3 40 rdt3 0inaction TransportLayer 3 41 Performanceofrdt3 0 rdt3 0works butperformancestinksex 1Gbpslink 15msprop delay 8000bitpacket Usender utilization fractionoftimesenderbusysending 1KBpktevery30msec 33kB secthruputover1Gbpslinknetworkprotocollimitsuseofphysicalresources TransportLayer 3 42 rdt3 0 stop and waitoperation firstpacketbittransmitted t 0 sender receiver RTT lastpacketbittransmitted t L R firstpacketbitarrives lastpacketbitarrives sendACK ACKarrives sendnextpacket t RTT L R TransportLayer 3 43 Pipelinedprotocols Pipelining senderallowsmultiple in flight yet to be acknowledgedpktsrangeofsequencenumbersmustbeincreasedbufferingatsenderand orreceiver Twogenericformsofpipelinedprotocols go Back N selectiverepeat TransportLayer 3 44 Pipelining increasedutilization firstpacketbittransmitted t 0 sender receiver RTT lastbittransmitted t L R firstpacketbitarrives lastpacketbitarrives sendACK ACKarrives sendnextpacket t RTT L R lastbitof2ndpacketarrives sendACK lastbitof3rdpacketarrives sendACK Increaseutilizationbyafactorof3 TransportLayer 3 45 PipeliningProtocols Go back N bigpicture SendercanhaveuptoNunackedpacketsinpipelineRcvronlysendscumulativeacksDoesn tackpacketifthere sagapSenderhastimerforoldestunackedpacketIftimerexpires retransmitallunackedpackets SelectiveRepeat bigpicSendercanhaveuptoNunackedpacketsinpipelineRcvracksindividualpacketsSendermaintainstimerforeachunackedpacketWhentimerexpires retransmitonlyunackpacket TransportLayer 3 46 Selectiverepeat bigpicture SendercanhaveuptoNunackedpacketsinpipelineRcvracksindividualpacketsSendermaintainstimerforeachunackedpacketWhentimerexpires retransmitonlyunackpacket TransportLayer 3 47 Go Back N Sender k bitseq inpktheader window ofuptoN consecutiveunack edpktsallowed ACK n ACKsallpktsupto includingseq n cumulativeACK mayreceiveduplicateACKs seereceiver timerforoldestunackedpackettimeout n retransmitpktnandallhigherseq pktsinwindow TransportLayer 3 48 GBN senderextendedFSM start timerudt send sndpkt base udt send sndpkt base 1 udt send sndpkt nextseqnum 1 timeout rdt send data if nextseqnum base N sndpkt nextseqnum make pkt nextseqnum data chksum udt send sndpkt nextseqnum if base nextseqnum start timernextseqnum elserefuse data data base getacknum rcvpkt 1If base nextseqnum stop timerelsestart timer rdt rcv rcvpkt notcorrupt rcvpkt base 1nextseqnum 1 rdt rcv rcvpkt corrupt rcvpkt L TransportLayer 3 49 GBN receiverextendedFSM ACK only alwayssendACKforcorrectly receivedpktwithhighestin orderseq maygenerateduplicateACKsneedonlyrememberexpectedseqnumout of orderpkt discard don tbuffer noreceiverbuffering Re ACKpktwithhighestin orderseq Wait udt send sndpkt default rdt rcv rcvpkt notcurrupt rcvpkt hasseqnum rcvpkt expectedseqnum extract rcvpkt data deliver data data sndpkt make pkt expectedseqnum ACK chksum udt send sndpkt expectedseqnum expectedseqnum 1sndpkt make pkt expectedseqnum ACK chksum L TransportLayer 3 50 GBNinaction TransportLayer 3 51 SelectiveRepeat receiverindividuallyacknowledgesallcorrectlyreceivedpktsbufferspkts asneeded foreventualin orderdeliverytoupperlayersenderonlyresendspktsforwhichACKnotreceivedsendertimerforeachunACKedpktsenderwindowNconsecutiveseq sagainlimitsseq sofsent unACKedpkts TransportLayer 3 52 Selectiverepeat sender receiverwindows TransportLayer 3 53 Selectiverepeat datafromabove ifnextavailableseq inwindow sendpkttimeout n resendpktn restarttimerACK n in sendbase sendbase N markpktnasreceivedifnsmallestunACKedpkt advancewindowbasetonextunACKedseq pktnin rcvbase rcvbase N 1 sendACK n out of order bufferin order deliver alsodeliverbuffered in orderpkts advancewindowtonextnot yet receivedpktpktnin rcvbase N rcvbase 1 ACK n otherwise ignore TransportLayer 3 54 Selectiverepeatinaction TransportLayer 3 55 Selectiverepeat dilemma Example seq s 0 1 2 3windowsize 3receiverseesnodifferenceintwoscenarios incorrectlypassesduplicatedataasnewin a Q whatrelationshipbetweenseq sizeandwindowsize TransportLayer 3 56 Chapter3outline 3 1Transport layerservices3 2Multiplexinganddemultiplexing3 3Connectionlesstransport UDP3 4Principlesofreliabledatatransfer 3 5Connection orientedtransport TCPsegmentstructurereliabledatatransferflowcontrolconnectionmanagement3 6Principlesofcongestioncontrol3 7TCPcongestioncontrol TransportLayer 3 57 TCP OverviewRFCs 793 1122 1323 2018 2581 fullduplexdata bi directionaldataflowinsameconnectionMSS maximumsegmentsizeconnection oriented handshaking exchangeofcontrolmsgs init ssender receiverstatebeforedataexchangeflowcontrolled senderwillnotoverwhelmreceiver point to point onesender onereceiverreliable in orderbytesteam no messageboundaries pipelined TCPcongestionandflowcontrolsetwindowsizesend receivebuffers TransportLayer 3 58 TCPsegmentstructure URG urgentdata generallynotused ACK ACK valid PSH pushdatanow generallynotused RST SYN FIN connectionestab setup teardowncommands bytesrcvrwillingtoaccept countingbybytesofdata notsegments Internetchecksum asinUDP TransportLayer 3 59 TCPseq sandACKs Seq s bytestream number offirstbyteinsegment sdataACKs seq ofnextbyteexpectedfromothersidecumulativeACKQ howreceiverhandlesout of ordersegmentsA TCPspecdoesn tsay uptoimplementor HostA H