Advanced Computer Networks TCP Congestion ControlWhat is congestion?IssuesTCP Congestion ControlSlide 5Slide 6Slow StartSlow Start ExampleCongestion Avoidance via AIMDExample of Slow Start/Congestion AvoidanceResponses to CongestionSummary of TCP congestion controlFast RetransmitFlavors of TCP Congestion ControlTCP RenoFast RecoveryTCP Tahoe and TCP Reno (for single segment losses)TCP CCTCP New RenoSACKCongestion AvoidanceCongestion Avoidance in TCP (TCP Vegas)AlgorithmAdvanced Computer NetworksTCP Congestion ControlWhat is congestion?Increase in network load results in decrease of useful work doneDifferent sources compete for resources inside networkWhy is it a problem?Sources are unaware of current state of resourceSources are unaware of each otherIn many situations, this will result in decrease in throughput (congestion collapse)Destination1.5-Mbps T1 linkRouterSource2Source1100-Mbps FDDI10-Mbps EthernetIssuesHow to deal with congestion?pre-allocate resources so as to avoid congestion (avoidance)control congestion if (and when) it occurs (control) Two points of implementationhosts at the edges of the network (transport protocol)routers inside the network (queuing discipline)Underlying service modelbest-effort data deliveryTCP Congestion ControlIdeaassumes best-effort network (FIFO or FQ routers) each source determines network capacity for itselfuses implicit feedbackACKs pace transmission (self-clocking)Challengedetermining the available capacity in the first placeadjusting to changes in the available capacityTCP Congestion ControlTCP sender is in one of two states: slow start OR congestion avoidanceThree components of implementationOriginal TCP (TCP Tahoe)1. Slow Start 2. Additive Increase Multiplicative Decrease (AIMD) 3. Fast RetransmitTCP Reno 3. Fast RecoveryTCP VegasIntroduces Congestion AvoidanceTCP Congestion ControlObjective: adjust to changes in the available capacityNew state variables per connection: CongestionWindow and (slow start)thresholdlimits how much data source has in transitMaxWin = MIN(CongestionWindow, AdvertisedWindow)EffWin = MaxWin - (LastByteSent - LastByteAcked)Slow StartInitial value: Set cwnd = 1 Note: Unit is a segment size. TCP actually is based on bytes and increments by 1 MSS (maximum segment size)The receiver sends an acknowledgement (ACK) for each packet Note: Generally, a TCP receiver sends an ACK for every other segment. Each time an ACK is received by the sender, the congestion window is increased by 1 segment:cwnd = cwnd + 1 If an ACK acknowledges two segments, cwnd is still increased by only 1 segment.Even if ACK acknowledges a segment that is smaller than MSS bytes long, cwnd is increased by 1.Does Slow Start increment slowly? Not really. In fact, the increase of cwnd is exponential (why?)Slow Start ExampleThe congestion window size grows very rapidlyFor every ACK, we increase cwnd by 1 irrespective of the number of segments ACK’edTCP slows down the increase of cwnd when cwnd > ssthresh segment 1ACK for segment 1cwnd = 1cwnd = 2segment 2segment 3ACK for segments 2cwnd = 4segment 4segment 5segment 6ACK for segments 4cwnd = 8ACK for segments 3ACK for segments 5ACK for segments 6segment 7ACK for segments 7Congestion Avoidance via AIMDCongestion avoidance phase is started if cwnd has reached the slow-start threshold valueIf cwnd >= ssthresh then each time an ACK is received, increment cwnd as follows:cwnd = cwnd + 1/ cwndSo cwnd is increased by one only if all cwnd segments have been acknowledged.Example of Slow Start/Congestion AvoidanceAssume that ssthresh = 8Roundtrip timesCwnd (in segments)ssthreshcwnd = 1cwnd = 2cwnd = 4cwnd = 8cwnd = 9cwnd = 10Responses to CongestionSo, TCP assumes there is congestion if it detects a packet lossA TCP sender can detect lost packets via:Expiration of a retransmission timerReceipt of a duplicate ACK (why?)TCP interprets a Timeout as a binary congestion signal. When a timeout occurs, the sender performs: cwnd is reset to one:cwnd = 1ssthresh is set to half the current size of the congestion window:ssthresh = cwnd / 2 and slow-start is enteredSummary of TCP congestion controlInitially:cwnd = 1;ssthresh = advertised window size;New Ack received:if (cwnd < ssthresh) /* Slow Start*/ cwnd = cwnd + 1;else /* Cong. Avoidance */ cwnd = cwnd + 1/cwnd;Timeout:/* Multiplicative decrease */ssthresh = cwnd/2;cwnd = 1;Fast RetransmitIf three or more duplicate ACKs are received in a row, the TCP sender believes that a segment has been lost. Then TCP performs a retransmission of what seems to be the missing segment, without waiting for a timeout to happen.Enter slow start:ssthresh = cwnd/2cwnd = 11KSeqNo=0AckNo=1024AckNo=10241KSeqNo=1024SeqNo=20481KAckNo=1024SeqNo=30721KSeqNo=10241KSeqNo=40961KAckNo=4096Flavors of TCP Congestion Control TCP Tahoe (1988, FreeBSD 4.3 Tahoe)Slow StartCongestion AvoidanceFast RetransmitTCP Reno (1990, FreeBSD 4.3 Reno)Fast RecoveryNew Reno (1996)SACK (1996)RED (Floyd and Jacobson 1993)TCP RenoDuplicate ACKs:Fast retransmitFast recovery Fast Recovery avoids slow startTimeout:Retransmit Slow StartTCP Reno improves upon TCP Tahoe when a single packet is dropped in a round-trip time.Fast RecoveryFast recovery avoids slow start after a fast retransmitIntuition: Duplicate ACKs indicate that data is getting throughAfter three duplicate ACKs set:Retransmit “lost packet”On packet loss detected by 3 dup ACKs:ssthresh = cwnd/2cwnd=ssthreshenter congestion avoidance1KSeqNo=0AckNo=1024AckNo=10241KSeqNo=1024SeqNo=20481KAckNo=1024SeqNo=30721KSeqNo=10241KSeqNo=40961KAckNo=4096TCP Tahoe and TCP Reno(for single segment losses)RenotimecwndtimecwndTahoeTCP CCTCP New RenoWhen multiple packets are dropped, Reno has problemsPartial ACK: Occurs when multiple packets are lostA partial ACK acknowledges some, but not all packets that are outstanding at the start of a fast recovery, takes sender out of fast recoverySender has to wait until timeout occurs New Reno: Can deal with multiple lost segments without going to slow startAfter the recovery of initial loss packet, one ACK is enough to trigger re-transmission of next lost packet within the same group of lost segmentsSender keeps track of which packets have been
View Full Document
Unlocking...