15-441 Computer NetworkingGood Ideas So Far…OutlineSequence Numbers (reminder)Sequence NumbersTCP Flow ControlWindow Flow Control: Send SideSlide 8Window Flow Control: Receive SideTCP PersistPerformance ConsiderationsSlide 12Internet Pipes?Slide 14Slide 15Slide 16Plumbers Gone Wild!Plumbers Gone Wild 2!CongestionCauses & Costs of CongestionSlide 21Congestion CollapseCongestion Control and AvoidanceApproaches Towards Congestion ControlExample: TCP Congestion ControlSlide 26ObjectivesBasic Control ModelLinear ControlPhase PlotsSlide 31Additive Increase/DecreaseMuliplicative Increase/DecreaseConvergence to EfficiencyDistributed Convergence to EfficiencyConvergence to FairnessConvergence to Efficiency & FairnessWhat is the Right Choice?Important LessonsSlide 40Slide 41Pipes…Tubes…Let’s call the whole thing off15-441 Computer NetworkingLecture 17 – TCP & Congestion Control10-26-2006 Lecture 17: TCP & Congestion Control 2Good Ideas So Far…•Flow control•Stop & wait•Parallel stop & wait•Sliding window•Loss recovery•Timeouts•Acknowledgement-driven recovery (selective repeat or cumulative acknowledgement)10-26-2006 Lecture 17: TCP & Congestion Control 3Outline•TCP flow control•Congestion sources and collapse•Congestion control basics10-26-2006 Lecture 17: TCP & Congestion Control 4Sequence Numbers (reminder)•How large do sequence numbers need to be?•Must be able to detect wrap-around•Depends on sender/receiver window size•E.g.•Max seq = 7, send win=recv win=7•If pkts 0..6 are sent succesfully and all acks lost•Receiver expects 7,0..5, sender retransmits old 0..6!!!•Max sequence must be send window + recv window10-26-2006 Lecture 17: TCP & Congestion Control 5Sequence Numbers•32 Bits, Unsigned for bytes not packets!•Circular Comparison•Why So Big?•For sliding window, must have |Sequence Space| > |Sending Window| + |Receiving Window|•No problem•Also, want to guard against stray packets•With IP, packets have maximum lifetime of 120s•Sequence number would wrap around in this time at 286MB/s0Maxaba < b0Maxbab < a10-26-2006 Lecture 17: TCP & Congestion Control 6TCP Flow Control•TCP is a sliding window protocol•For window size n, can send up to n bytes without receiving an acknowledgement •When the data is acknowledged then the window slides forward•Each packet advertises a window size•Indicates number of bytes the receiver has space for•Original TCP always sent entire window•Congestion control now limits this10-26-2006 Lecture 17: TCP & Congestion Control 7Window Flow Control: Send SideSent but not acked Not yet sentwindowNext to be sentSent and acked10-26-2006 Lecture 17: TCP & Congestion Control 8acknowledged sent to be sent outside windowSource PortSource PortDest. PortDest. PortSequence NumberSequence NumberAcknowledgmentAcknowledgmentHL/FlagsHL/FlagsWindowWindowD. ChecksumD. ChecksumUrgent PointerUrgent PointerOptions…Options…Source PortSource PortDest. PortDest. PortSequence NumberSequence NumberAcknowledgmentAcknowledgmentHL/FlagsHL/FlagsWindowWindowD. ChecksumD. ChecksumUrgent PointerUrgent PointerOptions...Options...Packet SentPacket ReceivedApp writeWindow Flow Control: Send Side10-26-2006 Lecture 17: TCP & Congestion Control 9Acked but notdelivered to userNot yetackedReceive bufferwindowWindow Flow Control: Receive SideNewWhat should receiver do?10-26-2006 Lecture 17: TCP & Congestion Control 10TCP Persist•What happens if window is 0?•Receiver updates window when application reads data•What if this update is lost?•TCP Persist state•Sender periodically sends 1 byte packets•Receiver responds with ACK even if it can’t store the packet10-26-2006 Lecture 17: TCP & Congestion Control 11Performance Considerations•The window size can be controlled by receiving application•Can change the socket buffer size from a default (e.g. 8Kbytes) to a maximum value (e.g. 64 Kbytes)•The window size field in the TCP header limits the window that the receiver can advertise•16 bits 64 KBytes•10 msec RTT 51 Mbit/second•100 msec RTT 5 Mbit/second•TCP options to get around 64KB limit increases above limit10-26-2006 Lecture 17: TCP & Congestion Control 12Outline•TCP flow control•Congestion sources and collapse•Congestion control basics10-26-2006 Lecture 17: TCP & Congestion Control 13Internet Pipes?•How should you control the faucet?10-26-2006 Lecture 17: TCP & Congestion Control 14Internet Pipes?•How should you control the faucet?•Too fast – sink overflows!10-26-2006 Lecture 17: TCP & Congestion Control 15Internet Pipes?•How should you control the faucet?•Too fast – sink overflows!•Too slow – what happens?10-26-2006 Lecture 17: TCP & Congestion Control 16Internet Pipes?•How should you control the faucet?•Too fast – sink overflows•Too slow – what happens?•Goals•Fill the bucket as quickly as possible•Avoid overflowing the sink•Solution – watch the sink10-26-2006 Lecture 17: TCP & Congestion Control 17Plumbers Gone Wild!•How do we prevent water loss?•Know the size of the pipes?10-26-2006 Lecture 17: TCP & Congestion Control 18Plumbers Gone Wild 2!•Now what?•Feedback from the bucket or the funnels?10-26-2006 Lecture 17: TCP & Congestion Control 19Congestion•Different sources compete for resources inside network•Why is it a problem?•Sources are unaware of current state of resource•Sources are unaware of each other•Manifestations:•Lost packets (buffer overflow at routers)•Long delays (queuing in router buffers)•Can result in throughput less than bottleneck link (1.5Mbps for the above topology) a.k.a. congestion collapse10 Mbps100 Mbps1.5 Mbps10-26-2006 Lecture 17: TCP & Congestion Control 20Causes & Costs of Congestion•Four senders – multihop paths•Timeout/retransmitQ: What happens as rate increases?10-26-2006 Lecture 17: TCP & Congestion Control 21Causes & Costs of Congestion•When packet dropped, any “upstream transmission capacity used for that packet was wasted!10-26-2006 Lecture 17: TCP & Congestion Control 22Congestion Collapse•Definition: Increase in network load results in decrease of useful work done•Many possible causes•Spurious retransmissions of packets still in flight•Classical congestion collapse•How can this happen with packet conservation•Solution: better timers and TCP congestion control•Undelivered packets•Packets consume resources and are dropped elsewhere in
View Full Document
Unlocking...