networking - TCP congestion control - Fast Recovery in graph -

i've been reading book "computer networking: top down approach" , encountered question don't seem understand.

read, tcp congestion control has 3 states: slow start, congestion avoidance , fast recovery. understand slow start , congestion avoidance well, fast recovery pretty vague. book claims tcp behaves way:(cwnd= congestion window) enter image description here
let's @ following graph: transmission round-congestion window size graph

as can see, @ round 16 sender sends 42 segments, , because congestion window size had been halved (+3), can infer there have been 3 duplicate-acks. answer question claims rounds between 16 , 22 in congestion avoidance state. why not fast recovery? mean, after 3 duplicate acks tcp enters fast recovery , every other duplicate ack since should increase congestion window. why graph has no representation of that? reasonable explanation think of in graph, there three-duplicate acks, , acks had been received since not duplications.

even if that's case, how graph have looked if there had been more 3 duplicated acks? **

is there representation of fast recovery in graph above? why not/yes?

** i've been struggling answer question long time. i'll glad reply, thank you!

update here's image. think round defined when segments in window being acked. in photo, round shown circle. enter image description here why cwnd grow exponentially when in fast recovery state? (in image accidentally wrote expediently instead of exponentially)

update: original answer agreed solution, after careful thought, think solution wrong. answer rewritten scratch; please read carefully. show why fast recovery entered @ time t=16 , why protocol remains there until t=22. data in graph backs theory, i'm pretty positive solution plain wrong.

let's start setting straight: slow start grows exponentially; congestion avoidance grows linearly, , fast recovery grows linearly though uses same formula slow start update value of cwnd.

allow me clarify.

why slow start grows cwnd exponentially?

note cwnd increased mss bytes for each ack received.

let's see example. suppose cwnd initialized 1 mss (the value of mss typically 1460 bytes, in practice means cwnd initialized 1460). @ point, because congestion window size can hold 1 packet, tcp not send new data until packet acknowledged. assuming acks aren't being lost, implies approximately 1 new packet transferred every rtt seconds (recall rtt round-trip time), since need (1/2)*rtt send packet, , (1/2)*rtt ack arrive.

so, results in send rate of mss/rtt bps. now, remember each ack, cwnd incremented mss. thus, once first ack arrives, cwnd becomes 2*mss, can send 2 packets. when these 2 packets acknowledged, increment cwnd twice, cwnd 4*mss. great! can send 4 packets. these 4 packets acknowledged, increment cwnd 4 times! have cwnd = 8*mss. , cwnd = 16*mss. doubling cwnd every rtt seconds (this explains why cwnd = cwnd+mss*(mss/cwnd) in congestion avoidance leads linear growing)

yes, it's tricky, formula cwnd = cwnd+mss leads believe it's linear - common misconception, because people forget applied each acknowledged packet.

note in real world, transmitting 4 packets doesn't generate 4 acks. may generate 1 ack only, since tcp uses cumulative acks, single ack still acknowledging 4 packets.

why fast recovery linear?

the cwnd = cwnd+mss formula applied in both slow start , congestion avoidance. 1 think causes both states induce exponential growth. however, fast recovery applies formula in different context: when duplicate ack received. herein lies difference: in slow start, 1 rtt acknowledged whole bunch of segments, , each acknowledged segment contributed +1mss new value of cwnd, whereas in fast recovery, duplicate ack wasting rtt acknowledge loss of single segment, instead of updating cwnd n times each rtt seconds (where n number of segments transmitted), updating cwnd once segment lost. "wasted" 1 round trip 1 segment, increment cwnd 1.

about congestion avoidance - 1 i'll explain below when analysing graph.

analysing graph

ok, let's see happens in graph, round round. picture correct degree. let me clear things first:

when slow start , fast recovery grow exponentially, means grows exponentially round round, show in picture. so, correct. correctly identified rounds blue circles: notice how values of cwnd grow exponentially 1 circle next - 1, 2, 4, 8, 16, ...
your picture seems after slow start, protocol enters fast recovery. not happens. if went fast recovery slow start, see cwnd being halved. that's not graph shows: value of cwnd not decrease half t=6 t=7.

ok, let's see happens on each round. note time unit in graph round. so, if @ time t=x transmit n segments, assumed @ time t=x+1 these n segments have been acked (assuming weren't lost, of course).

also note how can tell value of ssthresh looking @ graph. @ t=6, cwnd stops growing exponentially , starts growing linearly, , value not decrease. possible transition slow start state doesn't involve decreasing cwnd transition congestion avoidance, happens when congestion window size equal ssthresh. can see in graph happens when cwnd 32. so, know ssthresh initialized 32 mss. book shows similar graph on page 276 (figure 3.53), authors draw similar conclusion:

enter image description here

under normal conditions, happens - when tcp switches first time exponential growth linear growth without decreasing size of window, it's because hit threshold , switched congestion avoidance.

finally, assume mss @ least 1460 bytes (it commonly 1460 bytes because ethernet has mtu = 1500 bytes , need account size of tcp + ip headers, need 40 bytes). important see when cwnd exceeds ssthresh, since cwnd's unit mss , ssthresh expressed in bytes.

so here go:

t = 1:

cwnd = 1 mss; ssthresh = 32 kb

transmit 1 segment

t = 2

1 segment acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 2

transmit 2 segments

t = 3

2 segments acknowledged

cwnd += 2; ssthresh = 32 kb

new value of cwnd: 4

transmit 4 segments

t = 4

4 segments acknowledged

cwnd += 4; ssthresh = 32 kb

new value of cwnd: 8

transmit 8 segments

t = 5

8 segments acknowledged

cwnd += 8; ssthresh = 32 kb

new value of cwnd: 16

transmit 16 segments

t = 6

16 segments acknowledged

cwnd += 16; ssthresh = 32 kb

new value of cwnd: 32

transmit 32 segments

ok, let's see happens now. cwnd reached ssthresh (32*1460 = 46720 bytes, greater 32000). it's time switch congestion avoidance. note how values of cwnd grow exponentially across rounds, because each acknowledged packet contributes 1 mss new value of cwnd, , every packet sent acknowledged in next round.

the switch congestion avoidance

now, cwnd not increase exponentially, because each ack won't contribute 1 mss anymore. instead, each ack contributes mss*(mss/cwnd). so, example, if mss 1460 bytes , cwnd 14600 bytes (so @ beginning of each round sending 10 segments), each ack (assuming 1 ack per segment) increase cwnd 1/10 mss (146 bytes). since send 10 segments, , @ end of round assume every segment acknowledged, @ end of round have increased cwnd 10 * 1/10 = 1. in other words, each segment contributes small fraction cwnd such increment cwnd 1 mss each round. each round increments cwnd 1 rather number of segments transferred / acknowledged.

we remain in congestion avoidance until loss detected (either 3 duplicate acks or timeout).

now, let clocks resume...

t = 7

32 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 33

transmit 33 segments

note how cwnd went 32 33 though 32 segments acknowledged (each ack therefore contributes 1/32). if in slow start, in t=6, have cwnd += 32. new value of cwnd consistent see in graph @ time t = 7.

t = 8

33 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 34

transmit 34 segments

t = 9

34 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 35

transmit 35 segments

notice consistent graph: @ t=9, have cwnd = 35. keeps happening t = 16...

t = 10

35 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 36

transmit 36 segments

t = 11

36 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 37

transmit 37 segments

t = 12

37 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 38

transmit 38 segments

t = 13

38 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 39

transmit 39 segments

t = 14

39 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 40

transmit 40 segments

t = 15

40 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 41

transmit 41 segments

t = 16

41 segments acknowledged

cwnd += 1; ssthresh = 32 kb

new value of cwnd: 42

transmit 42 segments

pause

what happens now? graph shows congestion window size decreases approximately half of size, , grows linearly across rounds again. possibility there 3 duplicate acks , protocol switches fast recovery. graph shows not switch slow start because bring cwnd down 1. possible transition fast recovery.

by entering fast recovery, ssthresh = cwnd/2. remember cwnd's units mss , ssthresh in bytes, have careful that. thus, new value ssthresh = cwnd*mss/2 = 42*1460/2 = 30660.

again, lines graph; notice ssthresh hit in near future when cwnd less 30 (recall mss = 1460, ratio not 1:1, that's why hit threshold though congestion window size below 30).

the switch congestion avoidance causes new value of cwnd ssthresh+3mss = 21+3 = 24 (remember careful units, here converted ssthresh mss again because our values of cwnd counted in mss).

as of now, in congestion avoidance, t=17, ssthresh = 30660 bytes , cwnd = 24.

upon entering t=18, 2 things can happen: either receive duplicate ack, or don't. if don't (so it's new ack), transition congestion avoidance. bring cwnd down value of ssthresh, 21. wouldn't match graph - graph shows cwnd keeps increasing linearly. also, doesn't switch slow start because bring cwnd down 1. implies fast recovery isn't left , getting duplicate acks. happens time t=22:

t = 18

duplicate ack arrived