Transcription

Transport Layer (TCP/UDP)

Where we are in the Course Moving on up to the Transport Layer!ApplicationTransportNetworkLinkPhysicalCSE 461 University of Washington2

Recall Transport layer provides end-to-end connectivityacross the ernetHostRouterCSE 461 University of WashingtonHost3

Recall (2) Segments carry application data across the network Segments are carried within packets within framesSegment802.11IPTCPApp, e.g., HTTPPacketFrameCSE 461 University of Washington4

Transport Layer Services Provide different kinds of data delivery across thenetwork to applicationsMessagesBytestreamUnreliableDatagrams (UDP)ReliableStreams (TCP)CSE 461 University of Washington5

Comparison of Internet Transports TCP is full-featured, UDP is a glorified packetTCP (Streams)ConnectionsBytes are delivered once,reliably, and in orderArbitrary length contentFlow control matchessender to receiverCongestion control matchessender to networkUDP (Datagrams)DatagramsMessages may be lost,reordered, duplicatedLimited message sizeCan send regardlessof receiver stateCan send regardlessof network stateCSE 461 University of Washington6

Socket API Simple abstraction to use the network The “network” API (really Transport service) used to writeall Internet apps Part of all major OSes and languages; originally Berkeley(Unix) 1983 Supports both Internet transport services (Streamsand Datagrams)CSE 461 University of Washington7

Socket API (2) Sockets let apps attach to the local network atdifferent portsSocket,Port #1Socket,Port #2CSE 461 University of Washington8

Socket API (3) Same API used for Streams and DatagramsOnly neededfor StreamsTo/From forDatagramsPrimitiveSOCKETBINDMeaningCreate a new communication endpointAssociate a local address (port) with a socketLISTENACCEPTCONNECTAnnounce willingness to accept connectionsPassively establish an incoming connectionActively attempt to establish a connectionSEND(TO)Send some data over the socketRECEIVE(FROM) Receive some data over the socketCLOSERelease the socketCSE 461 University of Washington9

Ports Application process is identified by the tuple IPaddress, transport protocol, and port Ports are 16-bit integers representing local “mailboxes”that a process leases Servers often bind to “well-known ports” 1024, require administrative privileges Clients often assigned “ephemeral” ports Chosen by OS, used temporarilyCSE 461 University of Washington10

Some Well-Known PortsPortProtocol20, 21 FTP22 SSH25 SMTPUseFile transferRemote login, replacement for TelnetEmail80 HTTP110 POP-3143 IMAPWorld Wide WebRemote email accessRemote email access443 HTTPS543 RTSP631 IPPSecure Web (HTTP over SSL/TLS)Media player controlPrinter sharingCSE 461 University of Washington11

Topics Service models Socket API and ports Datagrams, Streams User Datagram Protocol (UDP) Connections (TCP) Sliding Window (TCP) Flow control (TCP) Retransmission timers (TCP) Congestion control (TCP)CSE 461 University of Washington12

UDP

User Datagram Protocol (UDP) Used by apps that don’t want reliability orbytestreams Like what?CSE 461 University of Washington14

User Datagram Protocol (UDP) Used by apps that don’t want reliability orbytestreams Voice-over-IP DNS, RPC DHCP(If application wants reliability and messages then ithas work to do!)CSE 461 University of Washington15

Datagram SocketsClient (host 1) TimeServer (host 2)requestreplyCSE 461 University of Washington16

Datagram Sockets (2)Client (host 1)TimeServer (host 2)1: socket4: sendtorequest5: recvfrom*reply7: close1: socket2: bind3: recvfrom*6: sendto7: close* call blocksCSE 461 University of Washington17

UDP ssage queuesNetwork (IP)Port Mux/DemuxpacketCSE 461 University of Washington18

UDP Header Uses ports to identify sending and receivingapplication processes Datagram length up to 64K Checksum (16 bits) for reliabilityCSE 461 University of Washington19

UDP Header (2) Optional checksum covers UDP segment and IPpseudoheader Checks key IP fields (addresses) Value of zero means “no checksum”CSE 461 University of Washington20

TCP

TCP TCP Consists of 3 primary phases: Connection Establishment (Setup) Sliding Windows/Flow Control Connection Release (Teardown)

Connection Establishment Both sender and receiver must be ready before westart the transfer of data Need to agree on a set of parameters e.g., the Maximum Segment Size (MSS) This is signaling It sets up state at the endpoints Like “dialing” for a telephone callCSE 461 University of Washington23

Three-Way Handshake Used in TCP; opens connection fordata in both directions Each side probes the other with afresh Initial Sequence Number (ISN)Active party(client)Passive party(server) Sends on a SYNchronize segment Echo on an ACKnowledge segment Chosen to be robust even againstdelayed duplicatesCSE 461 University of Washington24

Three-Way Handshake (2) Three steps: Client sends SYN(x) Server replies with SYN(y)ACK(x 1) Client replies with ACK(y 1) SYNs are retransmitted if lostActive party(client)Passive party(server)123 Sequence and ack numbers carriedon further segmentsCSE 461 University of WashingtonTime25

Three-Way Handshake (3) Suppose delayed, duplicatecopies of the SYN and ACK arriveat the server!Active party(client)Passive party(server) Improbable, but anyhow CSE 461 University of Washington26

Three-Way Handshake (4) Suppose delayed, duplicatecopies of the SYN and ACK arriveat the server!Active party(client)Passive party(server) Improbable, but anyhow Connection will be cleanlyrejected on both sidesCSE 461 University of WashingtonXREJECTXREJECT27

TCP Connection State Machine Captures the states ([]) and transitions (- ) A/B means event A triggers the transition, with action BBoth partiesrun instancesof this statemachine

TCP Connections (2) Follow the path of the client:

TCP Connections (3) And the path of the server:

TCP Connections (4) Again, with states Active party (client)Passive party (server)CLOSEDCLOSED1LISTENSYN SENT2ESTABLISHEDSYN RCVD3TimeCSE 461 University of WashingtonESTABLISHED31

TCP Connections (5) Finite state machines are a useful tool to specifyand check the handling of all cases that may occur TCP allows for simultaneous open i.e., both sides open instead of the client-server pattern Try at home to confirm it worksCSE 461 University of Washington32

Connection Release Orderly release by both parties when done Delivers all pending data and “hangs up” Cleans up state in sender and receiver Key problem is to provide reliability while releasing TCP uses a “symmetric” close in which both sidesshutdown independentlyCSE 461 University of Washington33

TCP Connection Release Two steps: Active sends FIN(x), passive ACKs Passive sends FIN(y), active ACKs FINs are retransmitted if lostActivepartyPassiveparty Each FIN/ACK closes one directionof data transferCSE 461 University of Washington34

TCP Connection Release (2) Two steps: Active sends FIN(x), passive ACKs Passive sends FIN(y), active ACKs FINs are retransmitted if lost Each FIN/ACK closes one directionof data transferCSE 461 University of WashingtonActivepartyPassiveparty1235

TCP Connection State Machine Captures thestates ([]) andtransitions (- ) A/B meansevent A triggersthe transition,with action BBoth partiesrun instancesof this statemachineCSE 461 University of Washington36

TCP Release Follow the active partyCSE 461 University of Washington37

TCP Release (2) Follow the passive partyCSE 461 University of Washington38

TCP Release (3) Again, with states Active partyESTABLISHEDFIN WAIT 1Passive partyESTABLISHED1CLOSE WAITFIN WAIT 22TIME WAIT(timeout)CLOSEDCSE 461 University of WashingtonLAST ACKCLOSED39

TIME WAIT State Wait a long time after sending all segments andbefore completing the close Two times the maximum segment lifetime of 60 seconds Why?CSE 461 University of Washington40

TIME WAIT State Wait a long time after sending all segments andbefore completing the close Two times the maximum segment lifetime of 60 seconds Why? ACK might have been lost, in which case FIN will be resentfor an orderly close Could otherwise interfere with a subsequent connectionCSE 461 University of Washington41

Flow Control

Recall ARQ with one message at a time is Stop-and-Wait(normal case below)SenderTimeoutReceiverFrame 0ACK 0TimeFrame 1ACK 1CSE 461 University of Washington43

Limitation of Stop-and-Wait It allows only a single message to be outstandingfrom the sender: Fine for LAN (only one frame fits in network anyhow) Not efficient for network paths with BD 1 packetCSE 461 University of Washington44

Limitation of Stop-and-Wait (2) Example: R 1 Mbps, D 50 ms, 10kb packets RTT (Round Trip Time) 2D 100 ms How many packets/sec? What if R 10 Mbps?CSE 461 University of Washington45

Sliding Window Generalization of stop-and-wait Allows W packets to be outstanding Can send W packets per RTT ( 2D) Pipelining improves performance Need W 2BD to fill network pathCSE 461 University of Washington46

Sliding Window (2) What W will use the network capacity? Assume 10kb packets Ex: R 1 Mbps, D 50 ms Ex: What if R 10 Mbps?CSE 461 University of Washington47

Sliding Window (3) Ex: R 1 Mbps, D 50 ms 2BD 106 b/sec x 100. 10-3 sec 100 kbit W 2BD 10 packets of 1250 bytes Ex: What if R 10 Mbps? 2BD 1000 kbit W 2BD 100 packets of 1250 bytesCSE 461 University of Washington48

Sliding Window Protocol Many variations, depending on how buffers,acknowledgements, and retransmissions are handled Go-Back-N Simplest version, can be inefficient Selective Repeat More complex, better performanceCSE 461 University of Washington49

Sliding Window – Sender Sender buffers up to W segments until they areacknowledged LFS LAST FRAME SENT, LAR LAST ACK REC’D Sends while LFS – LAR WSlidingWindowW 5Available5Acked6 7 . Unacked2 3 4 5 Unavailable2 3 . 3.LARLFSCSE 461 University of Washingtonseq. number50

Sliding Window – Sender (2) Transport accepts another segment of data fromthe Application . Transport sends it (as LFS–LAR 5)SlidingWindowW 5Sent5Acked6 7 . Unacked2 3 4 5 Unavailable2 3 . 3.LARLFSCSE 461 University of Washingtonseq. number51

Sliding Window – Sender (3) Next higher ACK arrives from peer Window advances, buffer is freed LFS–LAR 5 (can send one more)SlidingWindow5Acked6 7 .LARW 5Available2 3 4 5 2 Unavailable3 . 3Unacked.LFSCSE 461 University of Washingtonseq. number52

Sliding Window – Go-Back-N Receiver keeps only a single packet buffer for thenext segment State variable, LAS LAST ACK SENT On receive: If seq. number is LAS 1, accept and pass it to app, updateLAS, send ACK Otherwise discard (as out of order)CSE 461 University of Washington53

Sliding Window – Selective Repeat Receiver passes data to app in order, and buffers out-oforder segments to reduce retransmissions ACK conveys highest in-order segment, plus hints about outof-order segments TCP uses a selective repeat design; we’ll see the details laterCSE 461 University of Washington54

Sliding Window – Selective Repeat (2) Buffers W segments, keeps state variable LAS LASTACK SENT On receive: Buffer segments [LAS 1, LAS W] Send app in-order segments from LAS 1, and update LAS Send ACK for LAS regardlessCSE 461 University of Washington55

Sliding Window – Selective Retransmission (3) Keep normal sliding window If receive something out of order Send last unacked packet again!W 5SlidingWindowAck Arrives Out of Order!5Acked6 7 .2 .4 5 5 Unavailable3 . 3Unacked.LFS seq. numberLAR 1CSE 461 University of Washingtonagain56

Sliding Window – Selective Retransmission (4) Keep normal sliding window If correct packet arrives, move window and LAR,send more messagesSlidingWindow5Acked6 7 .W 5Correct ack arrives Now Available. . Unacked4 5 5 3 . 3. .LARLFSseq.CSE 461 University of Washingtonnumber57

Sliding Window – Retransmissions Go-Back-N uses a single timer to detect losses On timeout, resends buffered packets starting at LAR 1 Selective Repeat uses a timer per unacked segmentto detect losses On timeout for segment, resend it Hope to resend fewer segmentsCSE 461 University of Washington58

Sequence Numbers Need more than 0/1 for Stop-and-Wait But how many? For Selective Repeat, need W numbers for packets, plusW for acks of earlier packets 2W seq. numbers Fewer for Go-Back-N (W 1) Typically implement seq. number with an N-bitcounter that wraps around at 2N—1 E.g., N 8: , 253, 254, 255, 0, 1, 2, 3, CSE 461 University of Washington59

Seq. NumberSequence Time PlotTransmissions(at Sender)Acks(at Receiver)Delay ( RTT/2)TimeCSE 461 University of Washington60

Sequence Time Plot (2)Seq. NumberGo-Back-N scenarioTimeCSE 461 University of Washington61

Sequence Time Plot (3)Seq. NumberRetransmissionsLossTimeoutTimeCSE 461 University of Washington62

ACK Clocking

Sliding Window ACK Clock Each in-order ACK advances the sliding window andlets a new segment enter the network ACKs “clock” data segments20 19 18 17 16 15 14 13 12 11 DataAck 1 2 3 4 5 6 7 8 9 10CSE 461 University of Washington64

Benefit of ACK Clocking Consider what happens when sender injects a burstof segments into the networkQueueFast linkSlow (bottleneck) linkCSE 461 University of WashingtonFast link65

Benefit of ACK Clocking (2) Segments are buffered and spread out on slow linkSegments“spread out”Fast linkSlow (bottleneck) linkCSE 461 University of WashingtonFast link66

Benefit of ACK Clocking (3) ACKs maintain the spread back to the original senderSlow linkAcks maintain spreadCSE 461 University of Washington67

Benefit of ACK Clocking (4) Sender clocks new segments with the spread Now sending at the bottleneck link without queuing!Segments spreadQueue no longer buildsSlow linkCSE 461 University of Washington68

Benefit of ACK Clocking (4) Helps run with low levels of loss and delay! The network smooths out the burst of data segments ACK clock transfers this smooth timing back to sender Subsequent data segments are not sent in bursts sodo not queue up in the networkCSE 461 University of Washington69

TCP Uses ACK Clocking TCP uses a sliding window because of the value ofACK clocking Sliding window controls how many segments areinside the network TCP only sends small bursts of segments to let thenetwork keep the traffic smoothCSE 461 University of Washington70

Problem Sliding window has pipelining to keep network busy What if the receiver is overloaded?Arg BigIronStreamingvideoCSE 461 University of WashingtonWeeMobile71

Sliding Window – Receiver Consider receiver with W buffers LAS LAST ACK SENT, app pulls in-order data from buffer withrecv() callSlidingWindowW 5. 35Finished6 7 5 Acceptable5 5 5 5 2Too3 high.LASseq. numberCSE 461 University of Washington72

Sliding Window – Receiver (2) Suppose the next two segments arrive but app doesnot call recv()W 5. 35Finished6 7 5 Acceptable5 5 5 5 2Too3 high.LASCSE 461 University of Washingtonseq.number73

Sliding Window – Receiver (3) Suppose the next two segments arrive but app doesnot call recv() LAS rises, but we can’t slide window!W 5. 35Finished6 7 Acked5 5 5 5 5 2Too3 high.LASCSE 461 University of Washingtonseq. number74

Sliding Window – Receiver (4) Further segments arrive (in order) we fill buffer Must drop segments until app recvs!NothingAcceptable!W 5. 35Finished6 7 Acked5 5 5 5 5 2Too3 high.LASCSE 461 University of Washingtonseq. number75

Sliding Window – Receiver (5) App recv() takes two segments Window slides (phew)W 5 Acceptable5Finished6 7 5 5 Acked5 5 5 2 3 .LASCSE 461 University of Washington3seq. number76

Flow Control Avoid loss at receiver by telling sender the availablebuffer space WIN #Acceptable, not W (from LAS)W 5 Acceptable5Finished6 7 5 5 Acked5 5 5 2 3 .LASCSE 461 University of Washington3seq. number77

Flow Control (2) Sender uses lower of the sliding window and flowcontrol window (WIN) as the effective window sizeW 3Acceptable. 35Finished6 7 Acked5 5 5 5 5 2Too3 high.LASCSE 461 University of Washingtonseq. number78

Flow Control (3) TCP-style example SEQ/ACK sliding window Flow control with WIN SEQ length ACK WIN 4KB buffer at receiver Circular buffer of bytesCSE 461 University of Washington79

Topic How to set the timeout for sending a retransmission Adapting to the network pathLost?NetworkCSE 461 University of Washington80

Retransmissions With sliding window, detecting loss with timeout Set timer when a segment is sent Cancel timer when ack is received If timer fires, retransmit data as lostRetransmit!CSE 461 University of Washington81

Timeout Problem Timeout should be “just right” Too long wastes network capacity Too short leads to spurious resends But what is “just right”? Easy to set on a LAN (Link) Short, fixed, predictable RTT Hard on the Internet (Transport) Wide range, variable RTTCSE 461 University of Washington82

Example of RTTsBCN SEA BCN1000Round Trip Time (ms)9008007006005004003002001000020406080100120CSE 461 University of Washington140160180200Seconds83

Example of RTTs (2)BCN SEA BCN1000900Variation due to queuing at routers,changes in network paths, etc.800Round Trip Time(ms)700600500400300200Propagation ( transmission) delay 2D1000020406080100120CSE 461 University of Washington140160180200Second84

Example of RTTs (3)1000Timer too high!Round Trip Time (ms)900800Need to adapt to thenetwork conditions700600500Timer too low!4003002001000020406080100120CSE 461 University of Washington140160180200Seconds85

Adaptive Timeout Smoothed estimates of the RTT (1) and variance in RTT (2) Update estimates with a moving average1. SRTTN 1 0.9*SRTTN 0.1*RTTN 12. SvarN 1 0.9*SvarN 0.1* RTTN 1– SRTTN 1 Set timeout to a multiple of estimates To estimate the upper RTT in practice TCP TimeoutN SRTTN 4*SvarNCSE 461 University of Washington86

Example of Adaptive Timeout1000900800RTT SE 461 University of Washington140160180200Seconds87

Example of Adaptive Timeout (2)1000Earlytimeout900800Timeout (SRTT 4*Svar)RTT (ms)7006005004003002001000020406080100120CSE 461 University of Washington140160180200Seconds88

Adaptive Timeout (2) Simple to compute, does a good job of trackingactual RTT Little “headroom” to lower Yet very few early timeouts Turns out to be important for good performanceand robustnessCSE 461 University of Washington89

Congestion

TCP to date: We can set up a connection (connectionestablishment) Tear down a connection (connection release) Keep the sending and receiving buffers fromoverflowing (flow control)What’s missing?

Network Congestion A “traffic jam” in the network Later we will learn how to control itWhat’s the hold up?NetworkCSE 461 University of Washington92

Congestion Collapse in the 1980s Early TCP used fixed size window (e.g., 8 packets) Initially fine for reliability But something happened as the ARPANET grew Links stayed busy but transfer rates fell by orders ofmagnitude!CSE 461 University of Washington93

Nature of Congestion Routers/switches have internal buffering.InputBufferFabricCSE 461 University of Washington.InputOutputOutputBuffer94

Nature of Congestion (2) Simplified view of per port output queues Typically FIFO (First In First Out), discard when fullRouterRouter (FIFO)QueueCSE 461 University of WashingtonQueuedPackets95

Nature of Congestion (3) Queues help by absorbing bursts when input output rate But if input output