TCP Congestion control

UDP 와 달리 TCP는 congestion control 을 지원해준다고 했다. 

TCP 의 congestion control은 sender 가 receiver 에게 보낼 데이터 양을 제한함으로써 이루어진다.

만약에 TCP sender가 경로에 congestion이 없다고 판단하면 send rate 를 높이는 식이다. 

반대로 경로상에 congestion 이 있다고 판단하면 send rate를 낮추어서 congestion을 줄이기 위해 노력한다.

TCP connection 은 receive buffer와 send buffer와 여러 변수들로 이루어져있다고 했었다.

sender 측에서 작동하는 TCP congestion control 메커니즘은 추가적인 변수인 congestion window 를 유지한다.

이 congestion window 는 줄여서 cwnd 라고 불린다. 이 cwnd는 TCP sender가 어느만큼의 rate로 receiver에게 

데이터를 보낼 수 있을지를 제한하는 역할을 한다. 

 

그렇다면, TCP sender 는 congestion 을 어떻게 감지할까? Loss event 란 것을 timeout 이나 receiver로 부터의 three duplicate ACK  로 생각하자.

만약에, sender 와 receiver 의 경로상에 congestion이 있다면, sender 가 보낸 packet은 유실되고 말 것이다. 따라서 

결과적으로 sender에게 loss event가 되는 것이다.

1. segment 유실은 congestion을 의미한다. 따라서, TCP sender의 rate 는 segment 가 유실되었을 때 낮아져야한다.

2. Acknowledged segment 는 network 가 sender 의 segment 를 receiver에게 보냄을 의미한다. 따라서 

   sender rate 는 ACK 가 도착할 때마다 증가할 수 있다.  그러니깐, sender 가 보낸 segment를 receiver가 무사히

   받았기 때문에 sender는 다시 ACK 를 받았을 것 이기 때문에 이 경우에는 transmission rate를 더 늘려도 되겠죠?

3. ACK는 sender 와 receiver 사이의 path가 congestion free 하다는 것을 의미한다. TCP는 이러한 점을 이용해서

  ACK가 유실될 때 까지 transmission rate 를 늘립니다. 텍스트에 이 방식에 대한 재밌는 analogy 가 있네요.

 어린아이가 부모님이 사탕을 주면 계속 더 달라고 조르는 것 과 비슷합니다. 언제까지? 부모님이 안 돼! 라고 말 할 때 까지요.

 

○ Slow start 

TCP connetion 이 시작되면, cwnd 는 일반적으로 작은 값인 1MSS 로 설정됩니다(여기서 MSS는 Maximum Segment Size) 

일단 조금만 보내봐서 간을 보는거죠, 이때부터 slow-start 상태가 시작됩니다. cwnd 는 1MSS 로 시작해서 

acknowlegement를 받으면 1MSS를 늘려서 2MSS 를 보냅니다. 그리고 그 segment 들에 대해 모두 acknowledgement를 받는다면

4MSS 를 보냅니다 이렇게 계속 doubling 을 해가면서 exponetial 하게 늘려가는 것이 slow start phase 입니다. 

그러면, 언제까지 이렇게 계속 2배씩 늘려가면서 보낼 수 있을까요? 

만약에 timeout에 의한 loss event가 발생한다면 TCPsender 는 cwnd 를 1로 재설정하고 다시 slow start 과정을 시작하면서, ssthresh(slow start threshold)를 cwnd/2 로 설정합니다.  

그러니깐, ssthresh 에는 congestion 이 발생한 그 순간의 cwnd 값의 절반이 있는 것이죠. 

그렇기 때문에, cwnd 가 ssthresh 와 같아지거나 초과할 때까지 cwnd 를 늘리는 것은 무모한 짓일겁니다. 

따라서, cwnd 가 ssthresh와 다시 같아진다면, slow start 가 끝나고 congestion avoidance mode로 들어가게 됩니다.

 

○ Congestion Avoidance

congestion avoidance state에서는 congestion이 마지막으로 감지되었을 때의 cwnd 의 거의 반인 상태입니다.

즉, congestion 이 around the corner인 셈입니다. 따라서 cwnd 를 2배씩 늘리기 보다는, 매 RTT 마다 

cwnd를 1 MSS씩 늘리는 방법을 취합니다. 그렇다면 이 linear increase는 언제 멈추는가?

이것도 slow start 때와 마찬가지로, timeout 이 발생하면 멈추게 됩니다. cwnd 의 값이 1MSS 로 재설정 되고

ssthresh 는 cwnd 의 반으로 재설정 됩니다. 이러고 다시 Fast recovery 상태에 들어갑니다. 

 

○ Fast Recovery 

이 phase에서는 fast recovery 상태로 들어가게 만들었던 원인인 missing segment 의 duplicate ACK를 받을 때 마다 cwnd를 1MSS 씩 증가시킵니다.

마침내, missing segment에 대한 ACK가 모두 도착하면 TCP 는 congestion avoidance state에 진입합니다. 

만약에 timeout event가 발생하면 fast recovery 는 slow start 상태로 다시 들어가게 됩니다. 이 때 slow start 와 congestion avoidance 에서 했던 것 처럼 

ssthresh 를 cwnd 의 반으로 재 설정하는 것 입니다.

Fast recovery는 권장되긴 하지만 필수적인 상태는 아닙니다. 초기 버전의 TCP인 TCP Tahoe는

timeout 이나 triple duplicate ACK를 받을 때 마다 무조건적으로  cwnd 의 사이즈를 1MSS 로 줄여버렸습니다.

좀 더 새로운 버전인 TCP Reno 는 fast recovery 상태를 포함했습니다. 

수업을 들으면서 교수님께서, 이 두 가지 TCP version 의 이름의 기원을 말해주셨는데

Tahoe

Reno

Tahoe 와 Reno 는 모두 미국의 도시 이름입니다. 두 도시의 특징은 우리가 잘 아는 Las vegas 처럼 카지노가 성행하는

도시라는 의미입니다. 왜 하필 이런 도시가 뽑혔는가? 바로 TCP 의 congestion control 방식이 Casino 에서 도박하는 것 처럼 

동작하기 때문이다(잃을 때 까지 2배씩 판돈을 높이는..?). 그리고 재밌게도 조금 더 발전된 TCP의 버전이름은 TCP Vegas 이다.

교수님께서 TCP Vegas 를 만드셨으니, 이름의 기원에 대해 매우 믿음이 간다..

 

Tahoe 와  Reno 모두 초기에 threshold 가  8MSS 인 경우의 graph 이다. Tahoe, Reno 모두 ssthresh 에 도달한 후 

1MSS 씩 늘려가는 것을 볼 수 있다. cwnd 가 12일 때, loss event 가 발생했고,

ssthresh 는 따라서 cwnd의 반인 6으로 바뀐다. 앞에서 설명했듯이, Tahoe 는 congestion 을 감지하자마자 1로

cwnd 를 확 줄여버린다. Reno는 대신에 ssthresh로 줄인다음 선형적으로 증가시키는 것을 볼 수 있다. 

 

TCP REno 의 variatin으로 아까 언급한 TCP Vegas alogirthm이 있다. Vegas algorithm의 특징을 몇 가지 살펴보면

1) packet loss 가 일어나기 전에 source 와 destination의 라우터가 congestion을 감지한다

2. pack loss 가 감지되었을 때 rate를 linear 하게 감소시킨다.

 

* 추가 

왜 하필 Triple duplicate Acknowledgement 를 loss event 로 생각했을까?

RFC 2001 에 의하면 

TCP 는 duplicate ACK 가 lost segment에 의해 발생했는지 segment 의 reordering에 의해 발생됐는지 모른다
TCP는 단지 적은 수의 duplicate ACK가 오기를 기다린다. 그리고 만약에 segment의 reordering이 발생했다면 
reordered segment 가 처리되기 전에 오직 하나 혹은 두 개의 ACK 가 있었을 것 이다. 만약에 3개나 그 이상의 
duplicate ACK가 연속적으로 들어온다면, 이것은 segment 가 유실되었다는 강력한 증거일 수 있다. 따라서 
TCP는 retransmission timeout 까지 기다리지 않고 retransmission 을 진행한다

충분히 납득이 가는 이유지만, 아무리 생각해도 이런 crucial 한 알고리즘을 뭔가 heuristic 하게 정했을리가 없다는 생각이 들었지만

secretofsh.tistory.com/attachment/cfile29.uf@180913054BC6C99737A205.pdf

위의 자료를 참고해보면 3 페이지에서 

Fast Retransmit을 동작시키기 위해서 필요한 중복 승인 패킷의 수를 세 개로 정한 것에는 특별한 이론적인 배경은 없다. 
다만, IP 패킷들은 서로 다른 경로로 전달되는 경우가 흔히 발생하기 때문에 TCP 패킷들 역시 순서가 바뀐 채로 

정말 특별한 이유없이 정한 것이었습니다. 앞에서 ssthresh 의 값을 반으로 줄이는 것도 또한 

윈도우 크기가 W(loss)일 때 발생한 손실된 패킷을 Fast Retransmit에 의해 재전송한 이후 ssthresh의 값은
W(loss)/2로 설정된다. 이 값을 반으로 줄이는 것에는 특별한 이론적인 근거는 없다.

 

참조

https://stackoverflow.com/questions/4233851/why-does-tcp-wait-for-three-duplicate-ack-before-fast-retransmit