Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 4415-441 Computer NetworkingLecture 17 – TCP & Congestion Control2Lecture 17: TCP & Congestion ControlGood Ideas So Far…•Flow control•Stop & wait•Parallel stop & wait•Sliding window•Loss recovery•Timeouts•Acknowledgement-driven recovery (selective repeat or cumulative acknowledgement)3Lecture 17: TCP & Congestion ControlOutline•TCP flow control•Congestion sources and collapse•Congestion control basics4Lecture 17: TCP & Congestion ControlSequence 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 window5Lecture 17: TCP & Congestion ControlSequence 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/s =~ 2.3Gbit/s (hmm!)0Maxaba < b0Maxbab < a6Lecture 17: TCP & Congestion ControlTCP 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•But receiver buffer space != available net. capacity!•Congestion control now limits this•window = min(receiver window, congestion window)7Lecture 17: TCP & Congestion ControlWindow Flow Control: Send SideSent but not acked Not yet sentwindowNext to be sentSent and acked8Lecture 17: TCP & Congestion Controlacknowledged sent to be sent outside windowSource Port Dest. PortSequence NumberAcknowledgmentHL/Flags WindowD. Checksum Urgent PointerOptions…Source Port Dest. PortSequence NumberAcknowledgmentHL/Flags WindowD. Checksum Urgent PointerOptions...Packet SentPacket ReceivedApp writeWindow Flow Control: Send Side9Lecture 17: TCP & Congestion ControlAcked but notdelivered to userNot yetackedReceive bufferwindowWindow Flow Control: Receive SideNewWhat should receiver do?10Lecture 17: TCP & Congestion ControlTCP 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 packet11Lecture 17: TCP & Congestion ControlPerformance Considerations•The window size can be controlled by receiving application•Can change the socket buffer size from a default (e.g. 8-64Kbytes) to some maximum value•Modern TCPs (linux, bsd, os x) may auto-tune•Historical source of performance problems on fast nets•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 limit12Lecture 17: TCP & Congestion ControlOutline•TCP flow control•Congestion sources and collapse•Congestion control basics13Lecture 17: TCP & Congestion ControlInternet Pipes?•How should you control the faucet?14Lecture 17: TCP & Congestion ControlInternet Pipes?•How should you control the faucet?•Too fast – sink overflows!15Lecture 17: TCP & Congestion ControlInternet Pipes?•How should you control the faucet?•Too fast – sink overflows!•Too slow – what happens?16Lecture 17: TCP & Congestion ControlInternet 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 sink17Lecture 17: TCP & Congestion ControlPlumbers Gone Wild!•How do we prevent water loss?•Know the size of the pipes?18Lecture 17: TCP & Congestion ControlPlumbers Gone Wild 2!•Now what?•Feedback from the bucket or the funnels?19Lecture 17: TCP & Congestion ControlCongestion•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 Mbps20Lecture 17: TCP & Congestion ControlCauses & Costs of Congestion•Four senders – multihop paths•Timeout/retransmitQ: What happens as rate increases?21Lecture 17: TCP & Congestion ControlCauses & Costs of Congestion•When packet dropped, any “upstream transmission capacity used for that packet was wasted!22Lecture 17: TCP & Congestion ControlCongestion 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? RTT increases!•Solution: better timers and TCP congestion control•Undelivered packets•Packets consume resources and are dropped elsewhere in network•Solution: congestion control for ALL traffic23Lecture 17: TCP & Congestion ControlCongestion Control and Avoidance•A mechanism that:•Uses network resources efficiently•Preserves fair network resource allocation•Prevents or avoids collapse•Congestion collapse is not just a theory•Has been frequently observed in many networks24Lecture 17: TCP & Congestion ControlApproaches Towards Congestion Control•End-end congestion control:•No explicit feedback from network•Congestion inferred from end-system observed loss, delay•Approach taken by TCP•Network-assisted congestion control:•Routers provide feedback to end systems•Single bit indicating congestion (SNA, DECbit, TCP/IP
View Full Document