计算机网络：Chapter 3 Transport Layer

《计算机网络：Chapter 3 Transport Layer》由会员分享，可在线阅读，更多相关《计算机网络：Chapter 3 Transport Layer（123页珍藏版）》请在金锄头文库上搜索。

1、2: Application Layer1Chapter 3 Transport LayerTransport Layer3-2Reading Assignment: Chapter 3Transport Layer3-3Chapter 3: Transport LayerOur goals: runderstand principles behind transport layer services:mmultiplexing/demultiplexingmreliable data transfermflow controlmcongestion controlrlearn about t

2、ransport layer protocols in the Internet:mUDP: connectionless transportmTCP: connection-oriented transportmTCP congestion controlLayering: The OSI ModelSessionNetworkLinkPhysicalPhysicalPhysicalApplicationPresentationTransportNetworkLinkLinkNetworkTransportSessionPresentationApplicationNetworkLinkPh

3、ysicalPeer-layer communicationlayer-to-layer communicationRouterRouter12345671234567Transport Layer3-4Layering: Our FTP ExampleNetworkLinkTransportApplicationPresentationSessionTransportNetworkLinkPhysicalThe 7-layer OSI ModelThe 4-layer Internet modelApplicationFTPASCII/BinaryIPTCPEthernet3-5Transp

4、ort LayerTransport Layer3-6Chapter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr

5、3.6 Principles of congestion controlr3.7 TCP congestion controlTransport Layer3-7Transport services and protocolsrprovide logical communication between app processes running on different hostsrtransport protocols run in end systems msend side: breaks app messages into segments, passes to network lay

6、ermrcv side: reassembles segments into messages, passes to app layerrmore than one transport protocol available to appsmInternet: TCP and UDPapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicallogical end-end transportTransport Layer3-8Transport vs. network layerr

7、network layer: logical communication between hostsrtransport layer: logical communication between processes mrelies on, enhances, network layer servicesHousehold analogy:12 kids sending letters to 12 kidsrprocesses = kidsrapp messages = letters in envelopesrhosts = housesrtransport protocol = Ann an

8、d Billrnetwork-layer protocol = postal serviceTransport Layer3-9Internet transport-layer protocolsrreliable, in-order delivery (TCP)mcongestion control mflow controlmconnection setuprunreliable, unordered delivery: UDPmno-frills extension of “best-effort” IPrservices not available: mdelay guarantees

9、mbandwidth guaranteesapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicallogical end-end transportTransport Layer3-10Cha

10、pter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr3.6 Principles of congestion c

11、ontrolr3.7 TCP congestion controlTransport Layer3-11Multiplexing/demultiplexingapplicationtransportnetworklinkphysicalP1applicationtransportnetworklinkphysicalapplicationtransportnetworklinkphysicalP2P3P4P1host 1host 2host 3= process= socketdelivering received segmentsto correct socketDemultiplexing

12、 at rcv host:gathering data from multiplesockets, enveloping data with header (later used for demultiplexing)Multiplexing at send host:Transport Layer3-12How demultiplexing worksrhost receives IP datagramsmeach datagram has source IP address, destination IP addressmeach datagram carries 1 transport-

13、layer segmentmeach segment has source, destination port number rhost uses IP addresses & port numbers to direct segment to appropriate socketsource port #dest port #32 bitsapplicationdata (message)other header fieldsTCP/UDP segment formatTransport Layer3-13Connectionless demultiplexingrCreate socket

14、s with port numbers:DatagramSocket mySocket1 = new DatagramSocket(12534);DatagramSocket mySocket2 = new DatagramSocket(12535);rUDP socket identified by two-tuple:(dest IP address, dest port number)However, we also consider source IP address, source port number in flow based appliance)rWhen host rece

15、ives UDP segment:mchecks destination port number in segmentmdirects UDP segment to socket with that port numberrIP datagrams with different source IP addresses and/or source port numbers directed to same socketTransport Layer3-14Connectionless demux (cont)DatagramSocket serverSocket = new DatagramSo

16、cket(6428);ClientIP:BP2client IP: AP1P1P3serverIP: CSP: 6428DP: 9157SP: 9157DP: 6428SP: 6428DP: 5775SP: 5775DP: 6428SP provides “return address”Transport Layer3-15Connection-oriented demuxrTCP socket identified by 4-tuple: msource IP addressmsource port numbermdest IP addressmdest port numberrrecv h

17、ost uses all four values to direct segment to appropriate socketrServer host may support many simultaneous TCP sockets:meach socket identified by its own 4-tuplerWeb servers have different sockets for each connecting clientmnon-persistent HTTP will have different socket for each requestTransport Lay

18、er3-16Connection-oriented demux (cont)ClientIP:BP1client IP: AP1P2P4serverIP: CSP: 9157DP: 80SP: 9157DP: 80P5P6P3D-IP:CS-IP: AD-IP:CS-IP: BSP: 5775DP: 80D-IP:CS-IP: BTransport Layer3-17Connection-oriented demux: Threaded Web ServerClientIP:BP1client IP: AP1P2serverIP: CSP: 9157DP: 80SP: 9157DP: 80P4

19、P3D-IP:CS-IP: AD-IP:CS-IP: BSP: 5775DP: 80D-IP:CS-IP: BTransport Layer3-18Chapter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable da

20、ta transfermflow controlmconnection managementr3.6 Principles of congestion controlr3.7 TCP congestion controlTransport Layer3-19UDP: User Datagram Protocol RFC 768r“no frills,” “bare bones” Internet transport protocolr“best effort” service, UDP segments may be:mlostmdelivered out of order to apprco

21、nnectionless:mno handshaking between UDP sender, receivermeach UDP segment handled independently of othersWhy is there a UDP?rno connection establishment (which can add delay)rsimple: no connection state at sender, receiverrsmall segment headerrno congestion control: UDP can blast away as fast as de

22、siredTransport Layer3-20UDP: moreroften used for streaming multimedia appsmloss tolerantmrate sensitiverother UDP usesmDNSmSNMPrreliable transfer over UDP: add reliability at application layermapplication-specific error recovery!source port #dest port #32 bitsApplicationdata (message)UDP segment for

23、matlengthchecksumLength, inbytes of UDPsegment,includingheaderTransport Layer3-21UDP checksumSender:rtreat segment contents as sequence of 16-bit integersrchecksum: addition (1s complement sum) of segment contentsrsender puts checksum value into UDP checksum fieldReceiver:rcompute checksum of receiv

24、ed segmentrcheck if computed checksum equals checksum field value:mNO - error detectedmYES - no error detected. But maybe errors nonetheless? More later .Goal: detect “errors” (e.g., flipped bits) in transmitted segmentTransport Layer3-22Internet Checksum ExamplerNotemWhen adding numbers, a carryout

25、 from the most significant bit needs to be added to the resultrExample: add two 16-bit integers1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 01 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 11 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 01 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1wraparoundsumchecksumTransport Layer3-23

26、Chapter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr3.6 Principles of congestio

27、n controlr3.7 TCP congestion controlTransport Layer3-24Principles of Reliable data transferrimportant in app., transport, link layersrtop-10 list of important networking topics!rcharacteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)Transport Layer3-2

28、5Principles of Reliable data transferrimportant in app., transport, link layersrtop-10 list of important networking topics!rcharacteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)Transport Layer3-26Principles of Reliable data transferrimportant in app

29、., transport, link layersrtop-10 list of important networking topics!rcharacteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)Transport Layer3-27Reliable data transfer: getting startedsendsidereceivesiderdt_send(): called from above, (e.g., by app.). P

30、assed data to deliver to receiver upper layerudt_send(): called by rdt,to transfer packet over unreliable channel to receiverrdt_rcv(): called when packet arrives on rcv-side of channeldeliver_data(): called by rdt to deliver data to upperTransport Layer3-28Reliable data transfer: getting startedWel

31、l:rincrementally develop sender, receiver sides of reliable data transfer protocol (rdt)rconsider only unidirectional data transfermbut control info will flow on both directions!ruse finite state machines (FSM) to specify sender, receiverstate1state2event causing state transitionactions taken on sta

32、te transitionstate: when in this “state” next state uniquely determined by next eventeventactionsTransport Layer3-29Rdt1.0: reliable transfer over a reliable channelrunderlying channel perfectly reliablemno bit errorsmno loss of packetsrseparate FSMs for sender, receiver:msender sends data into unde

33、rlying channelmreceiver read data from underlying channelWait for call from abovepacket = make_pkt(data)udt_send(packet)rdt_send(data)extract (packet,data)deliver_data(data)Wait for call from belowrdt_rcv(packet)senderreceiverTransport Layer3-30Rdt2.0: channel with bit errorsrunderlying channel may

34、flip bits in packetmchecksum to detect bit errorsrthe question: how to recover from errors:macknowledgements (ACKs): receiver explicitly tells sender that pkt received OKmnegative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errorsmsender retransmits pkt on receipt of NAKrn

35、ew mechanisms in rdt2.0 (beyond rdt1.0):merror detectionmreceiver feedback: control msgs (ACK,NAK) rcvr-senderTransport Layer3-31rdt2.0: FSM specificationWait for call from abovesnkpkt = make_pkt(data, checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt) & notc

36、orrupt(rcvpkt)rdt_rcv(rcvpkt) & isACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt) & isNAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt) & corrupt(rcvpkt)Wait for ACK or NAKWait for call from belowsenderreceiverrdt_send(data)LTransport Layer3-32rdt2.0: operation with no errorsWait for call from abovesnkpkt = make_p

37、kt(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)udt_send(NAK)rdt_rcv(rcvpkt) & corrupt(rcvpkt)Wait for ACK or NAKWait for call from belowrdt_send(dat

38、a)LTransport Layer3-33rdt2.0: error scenarioWait for call from abovesnkpkt = 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)udt_send(NAK)rdt_r

39、cv(rcvpkt) & corrupt(rcvpkt)Wait for ACK or NAKWait for call from belowrdt_send(data)LTransport Layer3-34rdt2.0 has a fatal flaw!What happens if ACK/NAK corrupted?rsender doesnt know what happened at receiver!rcant just retransmit: possible duplicateHandling duplicates: rsender retransmits current p

40、kt if ACK/NAK garbledrsender adds sequence number to each pktrreceiver discards (doesnt deliver up) duplicate pktSender sends one packet, then waits for receiver responsestop and waitTransport Layer3-35rdt2.1: sender, handles garbled ACK/NAKsWait for call 0 from abovesndpkt = make_pkt(0, data, check

41、sum)udt_send(sndpkt)rdt_send(data)Wait for ACK or NAK 0udt_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

42、(rcvpkt) )rdt_rcv(rcvpkt) & notcorrupt(rcvpkt) & isACK(rcvpkt) Wait for call 1 from aboveWait for ACK or NAK 1LLTransport Layer3-36rdt2.1: receiver, handles garbled ACK/NAKsWait for 0 from belowsndpkt = make_pkt(NAK, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) & not corrupt(rcvpkt) & has_seq0(rcvpkt)rdt_

43、rcv(rcvpkt) & notcorrupt(rcvpkt) & has_seq1(rcvpkt) extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)Wait for 1 from belowrdt_rcv(rcvpkt) & notcorrupt(rcvpkt) & has_seq0(rcvpkt) extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)rdt

44、_rcv(rcvpkt) & (corrupt(rcvpkt)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) & not corrupt(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)Transport Layer3-37rdt2.1: discussionSend

45、er:rseq # added to pktrtwo seq. #s (0,1) will suffice. Why?rmust check if received ACK/NAK corrupted rtwice as many statesmstate must “remember” whether “current” pkt has 0 or 1 seq. #Receiver:rmust check if received packet is duplicatemstate indicates whether 0 or 1 is expected pkt seq #rnote: rece

46、iver can not know if its last ACK/NAK received OK at senderTransport Layer3-38rdt2.2: a NAK-free protocolrsame functionality as rdt2.1, using ACKs onlyrinstead of NAK, receiver sends ACK for last pkt received OKmreceiver must explicitly include seq # of pkt being ACKed rduplicate ACK at sender resul

47、ts in same action as NAK: retransmit current pktTransport Layer3-39rdt2.2: sender, receiver fragmentsWait for call 0 from abovesndpkt = 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)

48、 & isACK(rcvpkt,0) Wait for ACK0sender FSMfragmentWait for 0 from belowrdt_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)receiver FSMfragmen

49、tLTransport Layer3-40rdt3.0: channels with errors and lossNew assumption: underlying channel can also lose packets (data or ACKs)mchecksum, seq. #, ACKs, retransmissions will be of help, but not enoughApproach: sender waits “reasonable” amount of time for ACK rretransmits if no ACK received in this

50、timerif pkt (or ACK) just delayed (not lost):mretransmission will be duplicate, but use of seq. #s already handles thismreceiver must specify seq # of pkt being ACKedrrequires countdown timerTransport Layer3-41rdt3.0 sendersndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)

51、Wait for ACK0rdt_rcv(rcvpkt) & ( corrupt(rcvpkt) |isACK(rcvpkt,1) )Wait for call 1 from abovesndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)rdt_rcv(rcvpkt) & notcorrupt(rcvpkt) & isACK(rcvpkt,0) rdt_rcv(rcvpkt) & ( corrupt(rcvpkt) |isACK(rcvpkt,0) )rdt_rcv(rcvpkt) & not

52、corrupt(rcvpkt) & isACK(rcvpkt,1) stop_timerstop_timerudt_send(sndpkt)start_timertimeoutudt_send(sndpkt)start_timertimeoutrdt_rcv(rcvpkt)Wait for call 0from aboveWait for ACK1Lrdt_rcv(rcvpkt)LLLTransport Layer3-42rdt3.0 in actionTransport Layer3-43rdt3.0 in actionTransport Layer3-44Performance of rd

53、t3.0rrdt3.0 works, but performance stinksrex: 1 Gbps link, 15 ms prop. delay, 8000 bit packet:mU sender: utilization fraction of time sender busy sending m1KB pkt every 30 msec - 33kB/sec thruput over 1 Gbps linkmnetwork protocol limits use of physical resources!Transport Layer3-45rdt3.0: stop-and-w

54、ait operationfirst packet bit transmitted, t = 0senderreceiverRTT last packet bit transmitted, t = L / Rfirst packet bit arriveslast packet bit arrives, send ACKACK arrives, send next packet, t = RTT + L / RTransport Layer3-46Pipelined protocolsPipelining: sender allows multiple, “in-flight”, yet-to

55、-be-acknowledged pktsmrange of sequence numbers must be increasedmbuffering at sender and/or receiverrTwo generic forms of pipelined protocols: go-Back-N, selective repeatTransport Layer3-47Pipelining: increased utilizationfirst packet bit transmitted, t = 0senderreceiverRTT last bit transmitted, t

56、= L / Rfirst packet bit arriveslast packet bit arrives, send ACKACK arrives, send next packet, t = RTT + L / Rlast bit of 2nd packet arrives, send ACKlast bit of 3rd packet arrives, send ACKIncrease utilizationby a factor of 3!Transport Layer3-48Pipelining ProtocolsGo-back-N: big picture:rSender can

57、 have up to N unacked packets in pipelinerRcvr only sends cumulative acksmDoesnt ack packet if theres a gaprSender has timer for oldest unacked packetmIf timer expires, retransmit all unacked packetsSelective Repeat: big picrSender can have up to N unacked packets in pipelinerRcvr acks individual pa

58、cketsrSender maintains timer for each unacked packetmWhen timer expires, retransmit only unack packetSliding WindowWindow SizeOutstandingUn-ackd dataData OK to sendData not OK to send yetData ACKd v Window is meaningful to the sender. vwindow size is “advertised” by receiver (usually 4k 8k Bytes whe

59、n connection set-up).v Retransmission policy: “Go Back N”, Selective RepeatTransport Layer3-49Transport Layer3-50Selective repeat: big picturerSender can have up to N unacked packets in pipelinerRcvr acks individual packetsrSender maintains timer for each unacked packetmWhen timer expires, retransmi

60、t only unack packetTransport Layer3-51Go-Back-NSender:rk-bit seq # in pkt headerr“window” of up to N, consecutive unacked pkts allowedrACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”mmay receive duplicate ACKs (see receiver)rtimer for each in-flight pktrtimeout(n): retransmit pkt n

61、 and all higher seq # pkts in windowTransport Layer3-52GBN: sender extended FSMWaitstart_timerudt_send(sndpktbase)udt_send(sndpktbase+1)udt_send(sndpktnextseqnum-1)timeoutrdt_send(data) if (nextseqnum no receiver buffering!mRe-ACK pkt with highest in-order seq #Waitudt_send(sndpkt)defaultrdt_rcv(rcv

62、pkt) & 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)LTransport Layer3-54GBN inactionTransport Layer3-55Selective Repea

63、trreceiver individually acknowledges all correctly received pktsmbuffers pkts, as needed, for eventual in-order delivery to upper layerrsender only resends pkts for which ACK not receivedmsender timer for each unACKed pktrsender windowmN consecutive seq #smagain limits seq #s of sent, unACKed pktsTr

64、ansport Layer3-56Selective repeat: sender, receiver windowsTransport Layer3-57Selective repeatdata from above :rif next available seq # in window, send pkttimeout(n):rresend pkt n, restart timerACK(n) in sendbase,sendbase+N:rmark pkt n as receivedrif n smallest unACKed pkt, advance window base to ne

65、xt unACKed seq # senderpkt n in rcvbase, rcvbase+N-1rsend ACK(n)rout-of-order: bufferrin-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pktpkt n in rcvbase-N,rcvbase-1rACK(n)otherwise: rignore receiverTransport Layer3-58Selective repeat in actionTransp

66、ort Layer3-59Selective repeat: dilemma Example (limited seq # to 3): rseq #s: 0, 1, 2, 3rwindow size=3rreceiver sees no difference in two scenarios!rincorrectly passes duplicate data as new in (a)Q: what relationship between seq # size and window size?Transport Layer3-60Chapter 3 outliner3.1 Transpo

67、rt-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr3.6 Principles of congestion controlr3.7 TCP congestion

68、controlTransport Layer3-61TCP: Overview RFCs: 793, 1122, 1323, 2018, 2581rreliable, in-order byte steam:mAcknowledgements indicate delivery of data.mChecksums are used to detect corrupted data.mSequence numbers detect missing, or mis-sequenced data.mCorrupted data is retransmitted after a timeout.mM

69、is-sequenced data is re-sequenced.mno “message boundaries”r(Window-based) Flow control prevents over-run of receiver. Transport Layer3-62TCP: Overview RFCs: 793, 1122, 1323, 2018, 2581rfull duplex data:mbi-directional data flow in same connectionmMSS: maximum segment sizerconnection-oriented: mhands

70、haking (exchange of control msgs) inits sender, receiver state before data exchangerflow controlled:msender will not overwhelm receiverrpoint-to-point:mone sender, one receiver rpipelined:mTCP congestion and flow control set window sizersend & receive buffersTCP is connection-orientedConnection Setu

71、p3-way handshake(Active)Client(Passive)ServerSynSyn + AckAckConnection Close/Teardown2 x 2-way handshake(Active)Client(Passive)ServerFin(Data +) AckFinAckTransport Layer3-63TCP supports a “stream of bytes” serviceByte 0Byte 1Byte 2Byte 3Byte 0Byte 1Byte 2Byte 3Host AHost BByte 80Byte 80Transport Lay

72、er3-64which is emulated using TCP “segments”Byte 0Byte 1Byte 2Byte 3Byte 0Byte 1Byte 2Byte 3Host AHost BByte 80TCP DataTCP DataByte 80Segment sent when:1.Segment full (MSS bytes),2.Not full, but times out, or3.“Pushed” by application.Transport Layer3-65The TCP Segment FormatIP HdrIP DataTCP HdrTCP D

73、ataSrc portDst portSequence #Ack Sequence #HLEN4RSVD6URGACKPSHRSTSYNFINFlagsWindow SizeChecksumUrg Pointer(TCP Options)01531TCP DataTCP Header and Data + IP AddressesSrc/dst port numbersand IP addresses uniquely identify socketTransport Layer3-66Sequence NumbersHost AHost BTCP DataTCP DataTCP HDRTCP

74、 HDRISN (initial sequence number)Sequence number = 1st byteAck sequence number = next expected byteTransport Layer3-67Initial Sequence NumbersConnection Setup3-way handshake(Active)Client(Passive)ServerSyn +ISNASyn + Ack +ISNBAckTransport Layer3-68TCP Sliding WindowrHow much data can a TCP sender ha

75、ve outstanding in the network?rHow much data should TCP retransmit when an error occurs? Just selectively repeat the missing data?rHow does the TCP sender avoid over-running the receivers buffers?Transport Layer3-69TCP Sliding WindowWindow SizeOutstandingUn-ackd dataData OK to sendData not OK to sen

76、d yetData ACKd v Window is meaningful to the sender. v Current window size is “advertised” by receiver (usually 4k 8k Bytes when connection set-up).v TCPs Retransmission policy is “Go Back N”.Transport Layer3-70TCP Sliding WindowHost AHost BACKWindow SizeRound-trip time(1) RTT Window sizeACKWindow S

77、izeRound-trip time(2) RTT = Window sizeACKWindow Size?Transport Layer3-71Transport Layer3-72TCP segment structuresource port #dest port #32 bitsapplicationdata (variable length)sequence numberacknowledgement numberReceive windowUrg data pnterchecksumFSRPAUheadlennotusedOptions (variable length)URG:

78、urgent data (generally not used)ACK: ACK #validPSH: push data now(generally not used)RST, SYN, FIN:connection estab(setup, teardowncommands)# bytes rcvr willingto acceptcountingby bytes of data(not segments!)Internetchecksum(as in UDP)Transport Layer3-73TCP seq. #s and ACKsSeq. #s:mbyte stream “numb

79、er” of first byte in segments dataACKs:mseq # of next byte expected from other sidemcumulative ACKQ: how receiver handles out-of-order segmentsmA: TCP spec doesnt say, - up to implementorHost AHost BSeq=42, ACK=79, data = CSeq=79, ACK=43, data = CSeq=43, ACK=80UsertypesChost ACKsreceipt of echoedCho

80、st ACKsreceipt ofC, echoesback Ctimesimple telnet scenarioTransport Layer3-74TCP Round Trip Time and TimeoutQ: how to set TCP timeout value?rlonger than RTTmbut RTT variesrtoo short: premature timeoutmunnecessary retransmissionsrtoo long: slow reaction to segment lossQ: how to estimate RTT?rSampleRT

81、T: measured time from segment transmission until ACK receiptmignore retransmissionsrSampleRTT will vary, want estimated RTT “smoother”maverage several recent measurements, not just current SampleRTT3-75TCP: Retransmission and TimeoutsHost AHost BACKRound-trip time (RTT)ACKRetransmission TimeOut (RTO

82、)Estimated RTTData1Data2Guard BandTCP uses an adaptive retransmission timeout value: CongestionChanges in RoutingRTT changes frequentlyTransport LayerTransport Layer3-76TCP Round Trip Time and TimeoutEstimatedRTT = (1- )*EstimatedRTT + *SampleRTTrExponential weighted moving averagerinfluence of past

83、 sample decreases exponentially fastrtypical value: = 0.125Transport Layer3-77Example RTT estimation:3-78TCP: Retransmission and Timeouts Picking the RTO is important: vPick a values thats too big and it will wait too long to retransmit a packet, vPick a value too small, and it will unnecessarily re

84、transmit packets.The original algorithm for picking RTO:1. EstimatedRTTk= EstimatedRTTk-1 + (1 - ) SampleRTT2. RTO = 2 * EstimatedRTTCharacteristics of the original algorithm:vVariance is assumed to be fixed.vBut in practice, variance increases as congestion increases.Determined empiricallyTransport

85、 LayerTransport Layer3-79TCP Round Trip Time and TimeoutSetting the timeoutrEstimtedRTT plus “safety margin”mlarge variation in EstimatedRTT - larger safety marginrfirst estimate of how much SampleRTT deviates from EstimatedRTT: TimeoutInterval = EstimatedRTT + 4*DevRTTDevRTT = (1- )*DevRTT + *|Samp

86、leRTT-EstimatedRTT|(typically, = 0.25) Then set timeout interval:3-80TCP: Retransmission and Timeoutsv There will be some (unknown) distribution of RTTs.v We are trying to estimate an RTO to minimize the probability of a false timeout.RTTProbabilitymeanvarianceLoad(Amount of trafficarriving to route

87、r)Average Queueing DelayVariance grows rapidly with loadv Router queues grow when there is more traffic, until they become unstable.v As load grows, variance of delay grows rapidly.Transport LayerTransport Layer3-81Chapter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.

88、3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr3.6 Principles of congestion controlr3.7 TCP congestion controlTransport Layer3-82TCP reliable data transferrTCP

89、 creates rdt service on top of IPs unreliable servicerPipelined segmentsrCumulative acksrTCP uses single retransmission timerrRetransmissions are triggered by:mtimeout eventsmduplicate acksrInitially consider simplified TCP sender:m ignore duplicate acksmignore flow control, congestion controlTransp

90、ort Layer3-83TCP sender events:data rcvd from app:rCreate segment with seq #rseq # is byte-stream number of first data byte in segmentrstart timer if not already running (think of timer as for oldest unacked segment)rexpiration interval: TimeOutInterval timeout:rretransmit segment that caused timeou

91、trrestart timer Ack rcvd:rIf acknowledges previously unacked segmentsmupdate what is known to be ackedmstart timer if there are outstanding segmentsTransport Layer3-84TCP sender(simplified) NextSeqNum = InitialSeqNum SendBase = InitialSeqNum loop (forever) switch(event) event: data received from app

92、lication above create TCP segment with sequence number NextSeqNum if (timer currently not running) start timer pass segment to IP NextSeqNum = NextSeqNum + length(data) event: timer timeout retransmit not-yet-acknowledged segment with smallest sequence number start timer event: ACK received, with AC

93、K field value of y if (y SendBase) SendBase = y if (there are currently not-yet-acknowledged segments) start timer /* end of loop forever */ Comment: SendBase-1: last cumulatively acked byteExample: SendBase-1 = 71;y= 73, so the rcvrwants 73+ ;y SendBase, sothat new data is ackedTransport Layer3-85T

94、CP: retransmission scenariosHost ASeq=100, 20 bytes dataACK=100timepremature timeoutHost BSeq=92, 8 bytes dataACK=120Seq=92, 8 bytes dataSeq=92 timeoutACK=120Host ASeq=92, 8 bytes dataACK=100losstimeoutlost ACK scenarioHost BXSeq=92, 8 bytes dataACK=100timeSeq=92 timeoutSendBase= 100SendBase= 120Sen

95、dBase= 120Sendbase= 100Transport Layer3-86TCP retransmission scenarios (more)Host ASeq=92, 8 bytes dataACK=100losstimeoutCumulative ACK scenarioHost BXSeq=100, 20 bytes dataACK=120timeSendBase= 120Transport Layer3-87TCP ACK generation RFC 1122, RFC 2581Event at ReceiverArrival of in-order segment wi

96、thexpected seq #. All data up toexpected seq # already ACKedArrival of in-order segment withexpected seq #. One other segment has ACK pendingArrival of out-of-order segmenthigher-than-expect seq. # .Gap detectedArrival of segment that partially or completely fills gapTCP Receiver actionDelayed ACK.

97、Wait up to 500msfor next segment. If no next segment,send ACKImmediately send single cumulative ACK, ACKing both in-order segments Immediately send duplicate ACK, indicating seq. # of next expected byteImmediate send ACK, provided thatsegment starts at lower end of gapTransport Layer3-88Fast Retrans

98、mitrTime-out period often relatively long:mlong delay before resending lost packetrDetect lost segments via duplicate ACKs.mSender often sends many segments back-to-backmIf segment is lost, there will likely be many duplicate ACKs.rIf sender receives 3 ACKs for the same data, it supposes that segmen

99、t after ACKed data was lost:mfast retransmit: resend segment before timer expiresTransport Layer3-89Host AtimeoutHost BtimeXresend 2nd segmentFigure 3.37 Resending a segment after triple duplicate ACKTransport Layer3-90 event: ACK received, with ACK field value of y if (y SendBase) SendBase = y if (

100、there are currently not-yet-acknowledged segments) start timer else increment count of dup ACKs received for y if (count of dup ACKs received for y = 3) resend segment with sequence number y Fast retransmit algorithm:a duplicate ACK for already ACKed segmentfast retransmitTransport Layer3-91Chapter

101、3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr3.6 Principles of congestion contro

102、lr3.7 TCP congestion controlTransport Layer3-92TCP Flow Controlrreceive side of TCP connection has a receive buffer:rspeed-matching service: matching the send rate to the receiving apps drain raterapp process may be slow at reading from buffersender wont overflowreceivers buffer bytransmitting too m

103、uch, too fastflow controlTransport Layer3-93TCP Flow control: how it works(Suppose TCP receiver discards out-of-order segments)rspare room in buffer= RcvWindow= RcvBuffer-LastByteRcvd - LastByteReadrRcvr advertises spare room by including value of RcvWindow in segmentsrSender limits unACKed data to

104、RcvWindowmguarantees receive buffer doesnt overflowTransport Layer3-94Chapter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data t

105、ransfermflow controlmconnection managementr3.6 Principles of congestion controlr3.7 TCP congestion controlTransport Layer3-95TCP Connection ManagementRecall: TCP sender, receiver establish “connection” before exchanging data segmentsrinitialize TCP variables:mseq. #smbuffers, flow control info (e.g.

106、 RcvWindow)rclient: connection initiator Socket clientSocket = new Socket(hostname,port number); rserver: contacted by client Socket connectionSocket = welcomeSocket.accept();Three way handshake:Step 1: client host sends TCP SYN segment to servermspecifies initial seq #mno dataStep 2: server host re

107、ceives SYN, replies with SYNACK segmentmserver allocates buffersmspecifies server initial seq. #Step 3: client receives SYNACK, replies with ACK segment, which may contain dataTransport Layer3-96TCP Connection Management (cont.)Closing a connection:client closes socket: clientSocket.close(); Step 1:

108、 client end system sends TCP FIN control segment to server Step 2: server receives FIN, replies with ACK. Closes connection, sends FIN. clientFINserverACKACKFINclosecloseclosedtimed waitTransport Layer3-97TCP Connection Management (cont.)Step 3: client receives FIN, replies with ACK. mEnters “timed

109、wait” - will respond with ACK to received FINs Step 4: server, receives ACK. Connection closed. Note: with small modification, can handle simultaneous FINs.clientFINserverACKACKFINclosingclosingclosedtimed waitclosedTransport Layer3-98TCP Connection Management (cont)TCP clientlifecycleTCP serverlife

110、cycleTransport Layer3-99Chapter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr3.6

111、 Principles of congestion controlr3.7 TCP congestion controlTransport Layer 3-100Principles of Congestion ControlCongestion:rinformally: “too many sources sending too much data too fast for network to handle”rdifferent from flow control!rmanifestations:mlost packets (buffer overflow at routers)mlong

112、 delays (queueing in router buffers)ra top-10 problem!Transport Layer 3-101Causes/costs of congestion: scenario 1 rtwo senders, two receiversrone router, infinite buffers rno retransmissionrlarge delays when congestedrmaximum achievable throughputunlimited shared output link buffersHost Alin : origi

113、nal dataHost BloutTransport Layer 3-102Causes/costs of congestion: scenario 2 rone router, finite buffers rsender retransmission of lost packetfinite shared output link buffersHost Alin : original dataHost Bloutlin : original data, plus retransmitted dataTransport Layer 3-103Causes/costs of congesti

114、on: scenario 2 ralways: (goodput)r“perfect” retransmission only when loss:rretransmission of delayed (not lost) packet makes larger (than perfect case) for samelinlout=linloutlinlout“costs” of congestion: rmore work (retrans) for given “goodput”runneeded retransmissions: link carries multiple copies

115、 of pktR/2R/2linloutb.R/2R/2linlouta.R/2R/2linloutc.R/4R/3Transport Layer 3-104Causes/costs of congestion: scenario 3 rfour sendersrmultihop pathsrtimeout/retransmitlinQ: what happens as and increase ?linfinite shared output link buffersHost Alin : original dataHost Bloutlin : original data, plus re

116、transmitted dataTransport Layer 3-105Causes/costs of congestion: scenario 3 Another “cost” of congestion: rwhen packet dropped, any “upstream transmission capacity used for that packet was wasted!Host AHost BloutTransport Layer 3-106Approaches towards congestion controlEnd-end congestion control:rno

117、 explicit feedback from networkrcongestion inferred from end-system observed loss, delayrapproach taken by TCPNetwork-assisted congestion control:rrouters provide feedback to end systemsmsingle bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM)mexplicit rate sender should send atTwo broad appr

118、oaches towards congestion control:Transport Layer 3-107Case study: ATM ABR congestion controlABR: available bit rate:r“elastic service” rif senders path “underloaded”: msender should use available bandwidthrif senders path congested: msender throttled to minimum guaranteed rateRM (resource managemen

119、t) cells:rsent by sender, interspersed with data cellsrbits in RM cell set by switches (“network-assisted”) mNI bit: no increase in rate (mild congestion)mCI bit: congestion indicationrRM cells returned to sender by receiver, with bits intact Transport Layer 3-108Case study: ATM ABR congestion contr

120、olrtwo-byte ER (explicit rate) field in RM cellmcongested switch may lower ER value in cellmsender send rate thus maximum supportable rate on pathrEFCI bit in data cells: set to 1 in congested switchmif data cell preceding RM cell has EFCI set, sender sets CI bit in returned RM cellTransport Layer 3

121、-109Chapter 3 outliner3.1 Transport-layer servicesr3.2 Multiplexing and demultiplexingr3.3 Connectionless transport: UDPr3.4 Principles of reliable data transferr3.5 Connection-oriented transport: TCPmsegment structuremreliable data transfermflow controlmconnection managementr3.6 Principles of conge

122、stion controlr3.7 TCP congestion controlTransport Layer 3-110TCP congestion control: additive increase, multiplicative decreaserApproach: increase transmission rate (window size), probing for usable bandwidth, until loss occursmadditive increase: increase CongWin by 1 MSS every RTT until loss detect

123、edmmultiplicative decrease: cut CongWin in half after loss timecongestion window sizeSaw toothbehavior: probingfor bandwidthTransport Layer 3-111TCP Congestion Control: detailsrsender limits transmission: LastByteSent-LastByteAcked CongWinrRoughly,rCongWin is dynamic, function of perceived network c

124、ongestionHow does sender perceive congestion?rloss event = timeout or 3 duplicate acksrTCP sender reduces rate (CongWin) after loss eventthree mechanisms:mAIMDmslow startmconservative after timeout eventsrate = CongWin RTT Bytes/secTransport Layer 3-112TCP Slow StartrWhen connection begins, CongWin

125、= 1 MSSmExample: MSS = 500 bytes & RTT = 200 msecminitial rate = 20 kbpsravailable bandwidth may be MSS/RTTmdesirable to quickly ramp up to respectable raterWhen connection begins, increase rate exponentially fast until first loss eventTransport Layer 3-113TCP Slow Start (more)rWhen connection begin

126、s, increase rate exponentially until first loss event:mdouble CongWin every RTTmdone by incrementing CongWin for every ACK receivedrSummary: initial rate is slow but ramps up exponentially fastHost Aone segmentRTTHost Btimetwo segmentsfour segmentsTransport Layer 3-114Refinement: inferring lossrAfte

127、r 3 dup ACKs:mCongWin is cut in halfmwindow then grows linearlyrBut after timeout event:mCongWin instead set to 1 MSS; mwindow then grows exponentiallymto a threshold, then grows linearlyq 3 dup ACKs indicates network capable of delivering some segmentsq timeout indicates a “more alarming” congestio

128、n scenarioPhilosophy:Transport Layer 3-115RefinementQ: When should the exponential increase switch to linear? A: When CongWin gets to 1/2 of its value before timeout. Implementation:rVariable Threshold rAt loss event, Threshold is set to 1/2 of CongWin just before loss eventTransport Layer 3-116Summ

129、ary: TCP Congestion ControlrWhen CongWin is below Threshold, sender in slow-start phase, window grows exponentially.rWhen CongWin is above Threshold, sender is in congestion-avoidance phase, window grows linearly.rWhen a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to Thre

130、shold.rWhen timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS. Transport Layer 3-117TCP sender congestion controlStateEvent TCP Sender Action CommentarySlow Start (SS)ACK receipt for previously unacked data CongWin = CongWin + MSS, If (CongWin Threshold) set state to “Congestion

131、 Avoidance”Resulting in a doubling of CongWin every RTTCongestionAvoidance (CA) ACK receipt for previously unacked dataCongWin = CongWin+MSS * (MSS/CongWin) Additive increase, resulting in increase of CongWin by 1 MSS every RTTSS or CALoss event detected by triple duplicate ACKThreshold = CongWin/2,

132、 CongWin = Threshold,Set state to “Congestion Avoidance”Fast recovery, implementing multiplicative decrease. CongWin will not drop below 1 MSS.SS or CATimeoutThreshold = CongWin/2, CongWin = 1 MSS,Set state to “Slow Start”Enter slow startSS or CADuplicate ACKIncrement duplicate ACK count for segment

133、 being ackedCongWin and Threshold not changedTransport Layer 3-118TCP throughputrWhats the average throughout of TCP as a function of window size and RTT?mIgnore slow startrLet W be the window size when loss occurs.rWhen window is W, throughput is W/RTTrJust after loss, window drops to W/2, throughp

134、ut to W/2RTT. rAverage throughout: .75 W/RTTTransport Layer 3-119TCP Futures: TCP over “long, fat pipes”rExample: 1500 byte segments, 100ms RTT, want 10 Gbps throughputrRequires window size W = 83,333 in-flight segmentsrThroughput in terms of loss rate:rL = 210-10 WowrNew versions of TCP for high-sp

135、eedTransport Layer 3-120Fairness goal: if K TCP sessions share same bottleneck link of bandwidth R, each should have average rate of R/KTCP connection 1bottleneckroutercapacity RTCP connection 2TCP FairnessTransport Layer 3-121Why is TCP fair?Two competing sessions:rAdditive increase gives slope of

136、1, as throughout increasesrmultiplicative decrease decreases throughput proportionally RRequal bandwidth shareConnection 1 throughputConnection 2 throughputcongestion avoidance: additive increaseloss: decrease window by factor of 2congestion avoidance: additive increaseloss: decrease window by facto

137、r of 2Transport Layer 3-122Fairness (more)Fairness and UDPrMultimedia apps often do not use TCPmdo not want rate throttled by congestion controlrInstead use UDP:mpump audio/video at constant rate, tolerate packet lossrResearch area: TCP friendlyFairness and parallel TCP connectionsrnothing prevents

138、app from opening parallel connections between 2 hosts.rWeb browsers do this rExample: link of rate R supporting 9 connections; mnew app asks for 1 TCP, gets rate R/10mnew app asks for 11 TCPs, gets R/2 !Transport Layer 3-123Chapter 3: Summaryrprinciples behind transport layer services:mmultiplexing, demultiplexingmreliable data transfermflow controlmcongestion controlrinstantiation and implementation in the InternetmUDPmTCPNext:rleaving the network “edge” (application, transport layers)rinto the network “core”