Question? Leave a message!




TCP Connection Management

TCP Connection Management 15
Computer Communication Networks (CCN) 1TCP: Overview • Pointtopoint: – one sender, one receiver • Reliable, inorder byte steam: – no “message boundaries” – But TCP chops it up into segments for transmission internally • Pipelined (window) flow control: – Window size decided by receiver and network • Send receive buffers Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 2TCP: Overview application application writes data reads data socket socket door door TCP TCP send buffer receive buffer segment Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 3TCP: Overview • Full duplex data: – bidirectional data flow in same connection – MSS: maximum segment size • Connectionoriented: – handshaking (exchange of control msgs) init’s sender, receiver state before data exchange • Flow Congestion Control: – sender will not overwhelm receiver or the network Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 4TCP segment structure 32 bits URG: urgent data counting source port dest port (generally not used) by bytes sequence number of data ACK: ACK (not segments) acknowledgement number valid head not UAPRS F rcvr window size PSH: push data now len used bytes (generally not used) checksum ptr urgent data rcvr willing to accept RST, SYN, FIN: Options (variable length) connection estab (setup, teardown commands) application data Internet (variable length) checksum (as in UDP) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 5TCP seq. ’s and ACKs (I) Sequence Numbers: – byte stream “number” of first byte in segment’s data ACKs: – seq of next byte expected from other side – cumulative ACK Q: how receiver handles outoforder segments – A: TCP spec doesn’t say, up to implementor Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 6TCP Seq. ’s and ACKs (II) Host B Host A User types ‘C’ host ACKs receipt of ‘C’, echoes back ‘C’ host ACKs receipt of echoed ‘C’ simple telnet scenario Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 7Temporal Redundancy Model Packets • Sequence Numbers • CRC or Checksum Timeout • ACKs Status Reports • NAKs, • SACKs • Bitmaps Retransmissions • Packets • FEC information Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 8Status Report Design • Cumulative acks: – Robust to losses on the reverse channel – Can work with gobackN retransmission – Cannot pinpoint blocks of data which are lost • The first lost packet can be pinpointed because the receiver would generate duplicate acks Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 9TCP: reliable data transfer (I) event: data received from application above create, send segment • one way data transfer • no flow, congestion event: timer timeout for wait wait segment with seq y for for control retransmit segment event event event: ACK received, with ACK y ACK processing Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 1000 sendbase = initialsequence number 01 nextseqnum = initialsequence number 02 03 loop (forever) 04 switch(event) 05 event: data received from application above 06 create TCP segment with sequence number nextseqnum 07 start timer for segment nextseqnum TCP: 08 pass segment to IP 09 nextseqnum = nextseqnum + length(data) 10 event: timer timeout for segment with sequence number y reliable 11 retransmit segment with sequence number y 12 compute new timeout interval for segment y 13 restart timer for sequence number y data 14 event: ACK received, with ACK field value of y 15 if (y sendbase) / cumulative ACK of all data up to y / 16 cancel all timers for segments with sequence numbers y 17 sendbase = y transfer (II) 18 19 else / a duplicate ACK for already ACKed segment / 20 increment number of duplicate ACKs received for y 21 if (number of duplicate ACKS received for y == 3) Simplified 22 / TCP fast retransmit / 23 resend segment with sequence number y 24 restart timer for segment y TCP 25 26 / end of loop forever / sender Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 11TCP ACK generation TCP Receiver action Event inorder segment arrival, delayed ACK. Wait up to 500ms for next segment. If no next segment, no gaps, send ACK everything else already ACKed immediately send single inorder segment arrival, cumulative ACK no gaps, one delayed ACK pending outoforder segment arrival send duplicate ACK, indicating seq. of next expected byte higherthanexpect seq. gap detected immediate ACK if segment starts arrival of segment that partially or completely fills gap at lower end of gap Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 12TCP: retransmission scenarios Host A Host B Host A Host B X loss time time premature timeout, lost ACK scenario cumulative ACKs Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 13 timeout Seq=100 timeout Seq=92 timeoutTCP Flow Control flow control receiver: explicitly sender won’t overrun informs sender of receiver’s buffers by free buffer space transmitting too much, – RcvWindow too fast field in TCP segment RcvBuffer = size or TCP Receive Buffer sender: keeps the RcvWindow = amount of spare room in Buffer amount of transmitted, unACKed data less than most recently received RcvWindow receiver buffering Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 14Timeout and RTT Estimation • Timeout: for robust detection of packet loss • Problem: How long should timeout be – Too long = underutilization – Too short = wasteful retransmissions – Solution: adaptive timeout: based on estimate of max RTT Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 15How to estimate max RTT • RTT = prop + queuing delay – Queuing delay highly variable – So, different samples of RTTs will give different random values of queuing delay • Chebyshev’s Theorem: – MaxRTT = Avg RTT + kDeviation – Error probability is less than 1/(k2) – Result true for ANY distribution of samples Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 16Round Trip Time and Timeout (II) Q: how to estimate RTT • SampleRTT: measured time from segment transmission until ACK receipt – ignore retransmissions, cumulatively ACKed segments • SampleRTT will vary wildly = want estimated RTT “smoother” – use several recent measurements, not just current SampleRTT to calculate “AverageRTT” Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 17TCP Round Trip Time and Timeout (III) AverageRTT = (1x)AverageRTT + xSampleRTT • Exponential weighted moving average (EWMA) • influence of given sample decreases exponentially fast; x = 0.1 Setting the timeout • AverageRTT plus “safety margin” proportional to variation Timeout = AverageRTT + 4Deviation Deviation = (1x)Deviation + xSampleRTT AverageRTT Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 18TCP Connection Management 1 Recall: TCP sender, receiver establish connection before exchanging data segments • initialize TCP variables: – seq. s – buffers, flow control info (e.g. RcvWindow) • client: connection initiator Socket clientSocket = new Socket("hostname","port number"); • server: contacted by client Socket connectionSocket = welcomeSocket.accept(); Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 19TCP Connection Management 2 Three way handshake: Step 1: client end system sends TCP SYN control segment to server – specifies initial seq Step 2: server end system receives SYN, replies with SYNACK control segment – ACKs received SYN – allocates buffers – specifies server receiver initial seq. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 20TCP Connection Management 3 Closing a connection: client closes socket: clientSocket.close(); Step 1: client end system sends TCP FIN control segment to server Step 2: server receives FIN, replies with ACK. Closes connection, sends FIN. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 21TCP Connection Management 4 Fddfdf client server close close closed d Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 22 timed waitTCP Connection Management 5 Step 3: client receives FIN, replies with ACK. – Enters “timed wait” will respond with ACK to received FINs Step 4: server, receives ACK. Connection closed. Note: with small modification, can handle simultaneous FINs. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 23TCP Connection Management 6 TCP client lifecycle Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 24TCP Connection Management 7 TCP server lifecycle Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 25Recap: Stability of a Multiplexed System Average Input Rate Average Output Rate = system is unstable How to ensure stability 1. Reserve enough capacity so that demand is less than reserved capacity 2. Dynamically detect overload and adapt either the demand or capacity to resolve overload Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 26Congestion Problem in Packet Switching 10 Mbs statistical multiplexing C Ethernet A 1.5 Mbs B queue of packets 45 Mbs waiting for output link D E  Cost: selfdescriptive header perpacket, buffering and delays for applications.  Need to either reserve resources or dynamically detect/adapt to overload for stability Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 27The Congestion Problem  i  i  •Problem: demand outstrips available capacity  1 Demand Capacity  n • If information about  , and  is i known in a central location where control of  or  can be effected i with zero time delays, – the congestion problem is solved Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 28The Congestion Problem (Continued) • Problems: – Incomplete information (eg: loss indications) – Distributed solution required – Congestion and control/measurement locations different – Timevarying, heterogeneous time delay Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 29The Congestion Problem • Static fixes may not solve congestion – a) Memory becomes cheap (infinite memory) No buffer Too late  b) Links become cheap (high speed links) Replace with 1 Mb/s All links 19.2 kb/s S S S S S S S S File Transfer Time = 7 hours File Transfer time = 5 minsThe Congestion Problem (Continued) • c) Processors become cheap (fast routers switches) A C S B D Scenario: All links 1 Gb/s. A B send to C = “highspeed” congestion (lose more packets faster)Principles of Congestion Control Congestion: • informally: “too many sources sending too much data too fast for network to handle” • different from flow control (receiver overload) • manifestations: – lost packets (buffer overflow at routers) – long delays (queuing in router buffers) • a top10 problem Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 32Causes/costs of congestion: scenario 1 • two senders, two receivers • one router, infinite buffers • no retransmission • large delays when congested • maximum achievable throughput Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 33Causes/costs of congestion: scenario 2 • one router, finite buffers • sender retransmission of lost packet Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 34Causes/costs of congestion: scenario 2 (continued) “Costs” of congestion: • More work (retrans) for given “goodput” • Unneeded retransmissions: link carries multiple copies of pkt due to spurious timeouts Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 35Causes/costs of congestion: scenario 3 Another “cost” of congestion: • when packet dropped, any “upstream transmission capacity used for that packet was wasted Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 36Approaches towards congestion control 1 • Two broad approaches towards congestion control: Endend congestion control: • no explicit feedback from network • congestion inferred from endsystem observed loss, delay • approach taken by TCP Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 37Approaches towards congestion control 2 Networkassisted congestion control: • routers provide feedback to end systems – single bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM) – explicit rate sender should send at Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 38TCP congestion control 1 • endend control (no network assistance) • transmission rate limited by congestion window size, Congwin, over segments: Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 39TCP congestion control 2 • w segments, each with MSS bytes sent in one RTT: w MSS throughput = Bytes/sec RTT Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 40TCP congestion control 3 • “Probing” for usable bandwidth: – Window flow control: avoid receiver overrun – Dynamic window congestion control: avoid/control network overrun • Policy: – Increase Congwin until loss (congestion) – Loss = decrease Congwin, then begin probing (increasing) again Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 41Additive Increase/Multiplicative Decrease (AIMD) Policy • For stability: – rateofdecrease rateofincrease – Decrease performed “enough” times as long as congestion exists • AIMD policy satisfies this condition, provided packet loss is congestion indicator window time Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 42Fairness Fairness goal: if N TCP sessions share same bottleneck link, each should get 1/N of link capacity TCP connection 1 bottleneck TCP router connection 2 capacity R Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 43Fairness Analysis Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 44AIMD Converges to Fairness Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 45TCP congestion control 4 • TCP uses AIMD policy in “steady state” • Two “phases” – Transient phase: aka “Slow start” – Steady State: aka “Congestion avoidance” • Important variables: – Congwin – threshold: defines threshold between two slow start phase, congestion avoidance phase Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 46TCP Slowstart 1 Slowstart algorithm initialize: Congwin = 1 for (each segment ACKed) Congwin++ until (loss event OR CongWin threshold) • Exponential increase (per RTT) in window size (not so slow) • Loss event: timeout (Tahoe TCP) and/or three duplicate ACKs (Reno TCP) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 47TCP Slowstart 2 Host A Host B • asdf time Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 48 RTTTCP Dynamics 2nd RTT 3rd RTT 4th RTT 1st RTT • Rate of acks determines rate of packets : “Selfclocking” property. 100 Mbps 10 Mbps Router Q Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 49TCP Congestion Avoidance 1 Congestion avoidance / slowstart is over / / Congwin threshold / Until (loss event) every w segments ACKed: Congwin++ threshold = Congwin/2 Congwin = 1 1 perform slowstart 1: TCP Reno skips slowstart (aka fast recovery) after three duplicate ACKs and performs close to AIMD Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 50TCP Congestion Avoidance 2 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 51TCP window dynamics (more) Receiver Window Timeout Congestion Idle Window ssthresh Interval (cwnd) 1 Time (units of RTTs) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 52TCP latency modeling 1 Q: How long does it take to receive an object from a Web server after sending a request • TCP connection establishment • data transfer delay Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 53TCP latency modeling 2 Notation, assumptions: • Assume one link between client and server of rate R • Assume: fixed congestion window, W segments • S: MSS (bits) • O: object size (bits) • no retransmissions (no loss, no corruption) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 54TCP latency modeling 3 Two cases to consider: • WS/R RTT + S/R: ACK for first segment in window returns before window’s worth of data sent • WS/R RTT + S/R: wait for ACK after sending window’s worth of data sent Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 55TCP latency modeling 4 Case 1: latency = 2RTT + O/R Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 56TCP latency modeling 5 K = O/WS Case 2: latency = 2RTT + O/R + (K1)S/R + RTT WS/R Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 57TCP latency modeling: slow start 1 • Now suppose window grows according to slow start. • Will show that the latency of one object of size O is: O S S  P Latency 2RTTP RTT (21)  R R R  where P is the number of times TCP stalls at server: Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 58TCP latency modeling: slow start 2 P minQ,K1 where Q is the number of times the server would stall if the object were of infinite size. and K is the number of windows that cover the object. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 59TCP latency modeling: slow start 3 initiate TCP connection Example: request object first window = S/R O/S = 15 segments RTT second window = 2S/R K = 4 windows third window = 4S/R Q = 2 fourth window = 8S/R P = minK1,Q = 2 complete object transmission delivered Server stalls P=2 times. time at time at server client Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 60TCP latency modeling: slow start 4 S  RTT time from when server starts to send segment R until server receives acknowledgement S k1 2 time to transmit the kth window R  S S  k1 RTT 2 stall time after the kth window  R R  Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 61TCP latency modeling: slow start 5 P O latency 2RTT stallTime  p R p1 P O S S k1  2RTT RTT 2  R R R k1 O S S P  2RTTPRTT  (21) R R R Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 62Sample Results Latency with slow Minimum Latency: R O/R P O/R + 2 RTT start 28 Kbps 28.6 sec 1 28.8 sec 28.9 sec 100 Kbps 8 sec 2 8.2 sec 8.4 sec 1 Mbps 800 5 1 sec 1.5 sec msec 10 Mbps 80 msec 7 0.28 sec 0.98 sec Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 63Summary: Chapter 3 • Principles behind transport layer services: • multiplexing/demultiplexing • reliable data transfer • flow control • congestion control • Instantiation and implementation in the Internet • UDP, TCP Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 64
Website URL
Comment