Transcription
TCP Flow ControlThe receiver side of a TCP connection maintains areceiver buffer:Computer NetworksLecture 30:Flow Control, Reliable Deliveryapplication process may be slow at reading fromthe bufferFlow control ensures that sender won’t overflowreceiver’s buffer by transmitting too much, too fastSliding WindowTCP Receiver WindowTCP uses sliding window flow control: allows a largeramount of data “in flight” than has been acknowledgedReceiver window size (rwnd) allows sender to get ahead of the receiver but not too far aheadSending processTCPLast byte writtenNext byte ACKed(snd una)Next byte sent(snd next)Receiver continually advertises buffer space availableto sender by including the current value of rwnd inTCP headerReceiving processTCP amount that can be sent without acknowledgment receiver can buffer this amount of dataSender limits unACKed data to rwndLast byte readguarantees receiver buffer wouldn’t overflowWindow SizeNext byte expectedLast byte receivedData ACK’d[Rexford]OutstandingUn-ack’d dataData OKto sendData not OKto send yet[Rexford]
TCP Flow Control ProblemsTCP Header with rwndTwo flow-control problems:1. receiver too slow (silly-window syndrome)S’s portFlags: SYNFINRSTPSHURGACK2. sender’s data comes in small amount (Nagle’s algorithm)D’s portSequence NumberSilly-window syndrome:Acknowledgment Seq#020window sizeUA PR S FChecksumreceiver window opens only bya small amount, hence sendercan send only a small amountof data at a timeUrgent pointerOptions (variable)Why is this not good?0 (size 1000)1000 (1000)2000 (500)application readsout 1 byte2500 (1)application readsout 1 byte1. packet header overhead2. small packets cause more[Rexford]Solution to Silly-window SyndromeDon’t advertise window until it opens “significantly”( ½*MSS or ½*rwnd)DestinationSenderHostSHost DDSw 2500Implementation alternatives:w 12501 (1)interrupts at busy receiverCharacteristics ofInteractive ApplicationsUser sends only a small amount of data, e.g., instantmessaging, sends one character at a time0 (1000)Problem: 40-byte header for every byte sent!1000 (1000)sender probes afterpersistence timer goes off delayed ACK, but delayed not more than 500 ms or ACK every other segment(Why?)w 2500w 1Data ACK with rwnd 0:DestinationHostDDSenderSHostS2000 (500)application readsout 1 bytew 0persisttimerprobe 2499 (1)Solution: “clumping,” sender clumps data together,i.e., sender waits for a “reasonable” amount of timebefore sendingw 2000How long is “reasonable”?
Nagle Algorithm send first segment immediatelyNagle AlgorithmNagle sends data as fast as network can deliver: accumulate data until ACK returns, or up to ½ sender window or ½ MSSwithout Nagleround-triptime (rtt)123.Advantages: bulk transfer is not held up data sent as fast as network can deliver(see next slide)wwith NagleSender SHostReceiverSenderHostSSHostR DSround-triptime (rtt)ReceiverHostDR1pkts.ACKs1123.2 to w 1waccumulateddata sent in 1 pkt2 to w 1Can be disabled by setsockopt(TCP NODELAY)TCP Error RecoverySender: maintains only one active timer, for snd una, restarting thew 1bytesin 2rttsw 1bytesin 2rttsTCP Go-back-N with BufferingReceiver: buffers out-of-order packets cumulative ACKs all packets received in-ordertimer after retransmissionReceiver: cumulative ACKs all packets received in-order out-of-order packets repeat the last ACK buffers out-of-order packets error recovery on TCP is actually more complicated becauseit’s tied up with congestion control, but it still relies onretransmission timeout for correctnessFor illustration only!Actual error recoverytied up withcongestion control
Retransmission TimeoutImplications of Bad RTOARQ depends on retransmission to achieve reliability:sender sets a timeout waiting for an ACKRTO too small:unnecessaryretransmissions:Retransmission timeout (RTO)computed from round-trip time (RTT) expects ACK to arrive after an RTT but on the Internet, RTT of a pathvaries over time, due to:2. optimal sender’s window sizelower 2342A2rto2retransmissiontimeout (rto)Estimating RTTRTO must adapt to actual and current RTTEstimate the RTT by watching returning ACKs compute a smoothed estimate by keeping a running average ofthe RTTs (a.k.a. Exponentially Weighted Moving Average (EWMA)) estimated RTT’ α * estimated RTT (1 –α ) * sample RTTwhere sample RTT: time between when a segment is transmitted andwhen its ACK is received α is the weight: α 1: each sample changes the estimate only a little bit α 0: each sample influences the estimate heavily α is typically (1 – ½3, which allows for fast implementation (3 right shifts))Xrttrttrto2!A122PktsRouterRSenderS1Varying RTT complicates thecomputation of:1. retransmission timeout (RTO)RouterRSenderSSenderSround-triptime (rtt) route changes congestionRTO too big:Example RTT EstimationDestinationD
ACK AmbiguityHow to Compute RTO?Which retransmitted packet to associate with an ACK?Two problems:1. an ACK acknowledges receiptof data, is not an ACK fortransmission: which packetto associate with an ACK inthe case of retransmission?DestinationDSenderSpkt irtt0Xrtorto0pkt i0rtt1Xrtortoack i112. RTTs spreadrto2rtorto 2 rttACK Ambiguity: Karn’s AlgorithmKarn’s algorithm: adjust RTT estimate only from non-retransmitted samples2XThere is a feedback loopbetween RTO computationand RTT estimatepkts with thesertt must berexmittedrttmean1rttrttpdftoo wideDestinationDSenderS0rtortt?RTO shrinksRTO can grow unboundedDestinationDSenderS2. retransmitted packet:1. original packet:First try: RTO β RTT, with β typically set to 2 or 3rttsamplesRTT Spread Too WideRTT estimate computed using EWMA only considersthe mean, doesn’t take variance into accountpdf however, ignoring retransmissions could lead topkts with thesertt must berexmittedinsensitivity to long delays so, back off RTO upon retransmission:RTOnew γ RTOold, γ typically 2Jacobson’s algorithm:rttmeanrto 2 rttrttsamples estimate deviation (D) of sample RTT Dnew α Dold (1 α) sample RTT – estimated RTT compute new estimated RTT as usual take the deviation in sample RTT (D) into account whencomputing RTO RTO estimated RTT 4D
Timers Used in TCP1.TIME WAIT: 2*MSL2. persistence timer3. RTO4. keep-alive timer: probe the other side ifconnection has been idle for “too long” may be turned on/off idle period may be set using setsockopt()
persistence timer goes off delayed ACK, but i.e., sender waits for a "reasonable" amount of time delayed not more than 500 ms or ACK every other segment (Why?) Sender S Destination D w 2500 0 (1000) 1000 (1000) 2000 (500) probe 2499 (1) application reads out 1 byte w 0 w 2000 persist timer Host S Host D Characteristics of
