TCPOutlineTCP ServiceTCP Service (c’d)State DiagramState Diagram (c’d)Slide 7Flow ControlCongestion ControlCongestion Control (c’d)Slide 11Slide 12Slide 13RTT EstimationFast RetransmissionFast RecoveryUCBTCPJean WalrandU.C. Berkeleywww.eecs.berkeley.edu/~wlrUCBOutlineTCP ServiceState DiagramFlow ControlCongestion ControlRTT EstimationFast RecoveryFast RetransmitUCBTCP ServiceError-Free Byte StreamIPTCPUnreliable packet deliveryReliable byte streamActual data pathUCBIPTCPTCP Service (c’d)Multiplexing: PortsA B C[A | B | p1 | p2 | …]p1 p2 p1 p2 p3 p1 p2portsUCBState Diagram Key Steps:…(1) SYN: k(1) SYN = Synchronize: A tells B that its bytes start with sequence number k + 1(2) SYN: n ACK: k + 1(2) SYN = Synchronize: B tells A that its bytes start with sequence number n + 1 ACK = Acknowledgement: B tells A that it agrees that A’s bytes start with k+1(3) Data: k + 1 ACK: n + 1(3) Data: A starts sending bytes with sequence number k + 1 ACK = Acknowledgement: A tells B that it agrees that B’s bytes start with n+1(4) FIN(5) FIN.ack(4) FIN = Finish: A tells B that it closes the “half-connection” from A to B; (5) B acks(6) FIN(7) FIN.ack(6)-(7) Similar to (4)-(5)ACKABUCBState Diagram (c’d)States:ABSYNSYN + ACKData + ACKACK…FINFIN.ackFINFIN.ackListenSYN receivedEstablishedClose WaitLast AckClosedClosedSYN sentEstablishedFIN Wait-1FIN Wait-2Timed WaitClosed(1)(1): A waits in case B retransmits FIN and A must ack againUCBState Diagram (c’d)UCBFlow ControlObjective: Avoid saturating receiverMechanism: Receiver advertises window WrecWrecW Wrec – Outstandingwhere Oustanding = Last sent – last Acked[ACK | Wrec | …]UCBCongestion ControlObjective: Avoid saturating routersMechanism: Loss => Reduce W; No loss => Increase WDetails: See book.UCBCongestion Control (c’d)Slow Start: ACK => W = W + 1W = 1 W = 2 W = 4 W = 8UCBCongestion Control (c’d)Slow Start: ACK => W = W + 1WRTTUCBCongestion Control (c’d)Congestion Avoidance: ACK => W = W + 1/WW = 8W = 8 + 1/8W = 8.125 + 1/8.125 8 + 2/8W 8 + 8/8 = 9W 9 + 9/9 = 10UCBCongestion Control (c’d)Congestion Avoidance: ACK => W = W + 1/WWRTTUCBRTT EstimationTimeout if delay > average + 4 deviationsAverage delay and deviation: first order filters:A(n) = aA(n – 1) + (1 – a) Delay(n)D(n) = aD(n – 1) + (1 – a)|Delay(n) – A(n)|Average A(n) calculated when n-th ACK arrives:Deviation D(n) calculated when n-th ACK arrives:Note - Obvious corrections when retransmission: Do not include delays of retransmitted packets Double timeout after retransmissionUCBFast RetransmissionWhen 3 duplicated ACKs, retransmit and W = W/2Motivation: 3 dup to avoid retransmission after misorderingACK nACK nACK nUCBFast RecoveryObjective: Keep buffer full after setting W = W/2Illustration: Window goes from 2K to K L + 2K – 1, …, L + 4, L+3, L+2, L +1, L, L - 13 Dup AckL, L + 2K – 1, …, L + 4 Last ReceivedL + 2K, L, L + 2K – 1, …, L + 4 => W = 2K + 1L + 2K + 1, L + 2K, L, L + 2K – 1, …, L + 5 => W = 2K + 2L + 3K - 2,…, L + 2K + 1, L + 2K, L => W = 3K - 1. . . . . . . . .L + 3K - 1,…, L + 2K + 1, L + 2K => W =
View Full Document