Announcement• Homework 2 in tonight– Will be graded and sent back before Th. class• Midterm next Tu. in class– Review session next time– Closed book– One 8.5” by 11” sheet of paper permitted• Recitation tomorrow on midterm review and project 2Some slides are in courtesy of J. Kurose and K. RossReview of Previous Lecture• Reliable transfer protocols– Pipelined protocols• Selective repeat• Connection-oriented transport: TCP– Overview and segment structure– Reliable data transferTCP: 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= 120SendBase= 120Sendbase= 100Outline• Flow control• Connection management• Congestion controlTCP Flow Control• receive side of TCP connection has a receive buffer:• speed-matching service: matching the send rate to the receiving app’s drain rate• app process may be slow at reading from buffersender won’t overflowreceiver’s buffer bytransmitting too much,too fastflow controlTCP Flow control: how it works(Suppose TCP receiver discards out-of-order segments)• spare room in buffer= RcvWindow= RcvBuffer-[LastByteRcvd -LastByteRead]• Rcvr advertises spare room by including value of RcvWindow in segments• Sender limits unACKeddata to RcvWindow– guarantees receive buffer doesn’t overflowTCP Connection ManagementRecall: TCP sender, receiver establish “connection”before exchanging data segments• initialize TCP variables:–seq. #s– buffers, flow control info (e.g. RcvWindow)•client:connection initiator•server:contacted by clientThree way handshake:Step 1: client host sends TCP SYN segment to server– specifies initial seq #–no dataStep 2:server host receives SYN, replies with SYNACK segment– server allocates buffers– specifies server initial seq. #Step 3:client receives SYNACK, replies with ACK segment, which may contain dataTCP Connection Management: ClosingStep 1: client end system sends TCP FIN control segment to serverStep 2: server receives FIN, replies with ACK. Closes connection, sends FIN.Step 3: client receives FIN, replies with ACK. – Enters “timed wait” - will respond with ACK to received FINsStep 4: server, receives ACK. Connection closed. Note: with small modification, can handle simultaneous FINsclientFINserverACKACKFINclosingclosingclosedtimed waitclosedTCP Connection Management (cont)TCP clientlifecycleTCP serverlifecycleOutline• Flow control• Connection management• Congestion controlPrinciples of Congestion ControlCongestion:• informally: “too many sources sending too much data too fast for networkto handle”• different from flow control!•manifestations:– lost packets (buffer overflow at routers)– long delays (queueing in router buffers)•Reasons– Limited bandwidth, queues– Unneeded retransmission for data and ACKsTCP Congestion Control• end-end control (no network assistance)• sender limits transmission:LastByteSent-LastByteAcked≤ CongWin•Roughly,• CongWin is dynamic, function of perceived network congestionHow does sender perceive congestion?• loss event = timeout or3 duplicate acks•TCP sender reduces rate (CongWin) after loss eventthree mechanisms:–AIMD–slow start– conservative after timeout eventsrate =CongWinRTTBytes/secTCP AIMD8 Kbytes16 Kbytes24 Kbytestimecongestionwindowmultiplicative decrease:cut CongWin in half after loss eventadditive increase:increase CongWin by 1 MSS every RTT in the absence of loss events: probingLong-lived TCP connectionTCP Slow Start• When connection begins, CongWin = 1 MSS– Example: MSS = 500 bytes & RTT = 200 msec– initial rate = 20 kbps• available bandwidth may be >> MSS/RTT– desirable to quickly ramp up to respectable rate• When connection begins, increase rate exponentially fast until first loss eventTCP Slow Start (more)• When connection begins, increase rate exponentially until first loss event:–double CongWin every RTT– done by incrementing CongWin for every ACK received• Summary: initial rate is slow but ramps up exponentially fastHost Aone segmentRTTHost Btimetwo segmentsfour segmentsRefinement• After 3 dup ACKs:– CongWin is cut in half–window then grows linearly•Butafter timeout event:–Enter “slow start”– CongWin instead set to 1 MSS; –window then grows exponentially– to a threshold, then grows linearly• 3 dup ACKs indicates network capable of delivering some segments• timeout before 3 dup ACKs is “more alarming”Philosophy:Refinement (more)Q: When should the exponential increase switch to linear? A: When CongWingets to 1/2 of its value before timeout.Implementation:•Variable Threshold • At loss event, Threshold is set to 1/2 of CongWin just before loss event02468101214123456789101112131415Transmission roundcongestion window size (segments)thresholdSummary: TCP Congestion Control•When CongWin is below Threshold, sender in slow-start phase, window grows exponentially.•When CongWin is above Threshold, sender is in congestion-avoidance phase, window grows linearly.•When a triple duplicate ACK occurs, Thresholdset to CongWin/2 and CongWin set to Threshold.•When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS.Fairness 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 FairnessWhy is TCP fair?Two competing sessions:• Additive increase gives slope of 1, as throughout increases• multiplicative 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 factor of 2Fairness (more)Fairness and UDP• Multimedia apps often do not use TCP– do not want rate throttled by congestion control•Instead use UDP:– pump audio/video at constant rate, tolerate packet loss• Research area: TCP friendlyFairness and parallel TCP connections• nothing prevents app from opening parallel connections between 2 hosts.•Web browsers do this • Example: link of rate R supporting 9 connections; – new app asks for 1 TCP, gets rate R/10– new app asks for 11 TCPs, gets R/2