TCP congestion control

TCP(Transmission Control Protocol) 은 연결 지향형 프로토콜로서 3-way handshaking 과정에 의해 연결을 설정한 후 데이터를 전송한다. TCP는 Transfer 과정에서 reliable하다는 것은, 전송 및 수신 상태를 보장해주기 때문이다. 하지만 이러한 TCP의 reliable하다는 것은 전송에 있어 신뢰성을 증가시켜줄 수 있지만 반대로 전송 과정에 문제가 생긴다면 처리 과정에 latency가 생기게 된다.

 

3-way handshaking

 예를 들면, 음식을 주문하고 대기표를 받고 기다리던 손님이 있었다. 손님 차례가 되어 주문한 음식이 나와 직원이 주문 대기표를 확인하는데 손님이 대기표를 잃어버린것이 아닌가? 이러한 상황에서 TCP라는 직원은 대기표를 명확하게 확인할 때 까지 그 손님에게 음식을 내어주지 않고 정해진 시간동안 찾지 못하면 다시 주문하라고 하는것이다... 물론 주문한 음식은 폐기될 것이다. (손님 입장에선 아주 황당할 듯하다) 이러한 과정을 볼 때 TCP는 신뢰성이라는 장점이 있지만 반대로 이로 인해 생기는 지연이 생길 수 있다.

 

 그렇다면 또 다른 예시를 들어보자. 점심을 먹기 위해 들어간 식당에 손님이 아주아주 많았지만 식당의 직원은 1명 뿐이였다. 직원은 이미 쌓인 주문을 처리하는데 급급했고 밀려오는 주문들은 까먹기 일쑤였다. 이로 인해 줄을 선 손님들은 정해진 시간 내에 점심을 먹기 위해 계속해서 주문을 하고 이를 감당하지 못하는 식당 직원은 점점 절망 상태(?)가 되어가고 있었다.

 

혼잡한 SHACK SHACK BURGER 

 

 만약 어떤 특정 네트워크로 많은 트래픽이 몰렸을 때 네트워크의 capacity가 traffic을 감당하지 못한다면 어떻게 될까? 말 그대로 담을 수 있는 공간 및 처리 능력이 되지 않으므로 추가적으로 전송된 패킷들은 수신자에게 도달하지 못하는 Loss가 발생한다. 이러한 Loss가 발생하면 TCP 의 reliable transfer특성으로 인해 재전송이 이루어진다.  재전송은 네트워크의 혼란을 가중시키기만 하고 어떠한 해결책을 제시하지는 않는다. 따라서 이러한 네트워크의 혼잡을 막기 위해 송신측에서 보내는 데이터 속도를 강제로 조절하는데, 이를 혼잡 제어(Congestion Control) 이라고 한다. 이러한 혼잡 제어는 흐름 제어와 달리 송신자와 수신자 사이 뿐만 아니라 네트워크 내, 호스트와 라우터를 포함한 보다 넓은 관점에서 이루어진다. 

 

그렇다면 이러한 혼잡 현상을 줄일 수 있는 제어 알고리즘에는 어떤 것들이 있는지 살펴보자.

 

1 ) AIMD (Additive Increase/Multiple Decrease, 합 증가/곱 감소)

 이 방식은 합 증가/ 곱 감소 방식이라고 알려져 있지만 AIMD로 더 많이 알려져있다. 

 동작 방식은 간단하다. 

 

 – 패킷 전송성공 : 윈도우 크기를 1씩 증가시킴 (Additive Increase)

 – 패킷 전송실패 : 윈도우 크기를 절반으로 줄임 (Multiplicative Decrease)

 

 AIMD 혼잡 제어 알고리즘을 사용하는 네트워크를 공유하는 여러 호스트가 있다면, 처음에 진입하는 호스트는 윈도우 크기가 작아 불리하지만 시간이 지날 수록 평형 상태로 수렴하게 되는 특징이 있다.

 

AIMD

하지만 여러 호스트가 네트워크 리소스를 공평한 상태에서 사용하는 Steady State가 될 때 까지 많은 시간이 소요된다는 것이 단점이다. 또한 혼잡한 상황이 발생했을 때 윈도우 사이즈를 절반으로 줄이는 방식이므로 혼잡한 상황을 예측하지는 못한다. 즉, 소 잃고 외양간 고치는 형식..

 

 

 2) Slow Start(느린 시작)

 

 AIMD 방식이 네트워크 수용량 주변에서는 효율적이지만 윈도우 크기를 1씩 증가시키므로 처음에 전송 속도를 올리기 까지 시간이 너무 길다는 단점이 있었다. Slow Start는 AIMD 방식과 마찬가지로 패킷을 하나씩 보내는 것으로 시작하는 것은 동일하지만 이 방식은 패킷이 문제 없이 도착하면 각각의 ACK 패킷마다 창 크기를 1씩 늘린다. 

다시 말해, 윈도우 사이즈가 4였다면 ACK 패킷을 4개를 받게 되므로 4개가 추가로 늘어나 한 주기가 끝나면 윈도우 크기가 8이 된다. 따라서 전송 속도는 AIMD가 Linear한 형태였다면 Slow Start는 exponential 하게 증가한다.

Window size

1 -> 2 -> 4 -> 8 -> 16 .....

 

 

Slow Start

대신에, 혼잡 현상이 발생하게 된다면 윈도우 크기를 1로 줄인다. 처음에는 네트워크의 수용량을 알 수 없어 혼잡 현상이 발생하기를 기다려야 하지만, 한 번 혼잡 현상이 발생하게 되면 네트워크 수용량을 파악할 수 있어 혼잡제어가 발생한 cwnd 까지는 exponential 하게, 그리고 그 이후부터는 다시 AIMD와 같이 Linear하게 증가하도록 조절할 수 있다. 

이 방식은 AIMD보다 효율적이지만 마찬가지로 혼잡한 상황이 된 경우에는 Timeout 이 될 때 까지 기다려야 하는 latency가 있다.

 

Q) Linear 한 AIMD보다 exponential한 Slow Start가 더 전송 속도를 올리는게 빠른데, 왜 Slow 인가?

이는 AIMD와 비교해서는 안되고, 전통적인 TCP 전송 방식에 대해 비교해야한다. Slow Start가 생길 당시 TCP의 전송 방식은 보낼 수 있는 만큼 최대한 많이 전송하여 혼잡 현상이 발생하면 윈도우 크기를 줄여나갔다.  따라서, 이전 방식과 비교해본다면 최대한 큰 윈도우 사이즈로 전송을 했던 것과 다르게 Slow Start는 1부터 exponential 하게 증가시키므로 느린 시작이라고 할 수 있겠다.

 

 

3) Fast Retransmit(빠른 재전송)

 

빠른 재전송은 TCP의 혼잡 제어 조절에 추가된 정책이다. 패킷을 받는 수신자 입장에서는 세그먼트로 분할된 내용들이 순서대로 도착하지 않는 경우가 생길 수 있다. 예를 들면, 1,2,3,4,5 번의 데이터가 순서대로 와야하는데 1,2 다음 4번이 온 것이다.  원래 기존의 방식은 3번이 Loss가 발생한 것이므로 5번을 추가로 전송하지 않고 1,2,3,4,5 데이터를 다시 재전송하도록 요구한다. 

하지만 빠른 재전송 방식에서는 다음 패킷이 도착한 경우에도 ACK패킷을 보낸다. 단 순서대로 잘 도착한 마지막 패킷의 다음 패킷의 순번을 ACK패킷에 실어서 보낸다. 

 

Fast Retransmit

다음 그림을 본다면 2~6까지를 Send했는데 Receiver입장에서 3을 받지 못했다고 한다. Fast Retransmit에서는 정상적으로 잘 받은 2번까지 ACK를 보낸다. 따라서 중간에 패킷 하나가 손실되게 되면 보내는 측에서 순번이 중복된 ACK를 여러게 받게 되는데 이것을 감지하는 순간 Sender는 문제가 생긴 데이터를 재전송 해줄 수 있다. 빠른 재전송에서는 3번의 중복된 패킷을 받으면 재전송이 이루어지는데, 그림에서는 ACK 2 패킷이 세 번 보내져 3번이 Re-send되는 것을 볼 수가 있다. 따라서 전체 데이터를 재전송하지 않고 문제가 발생한 패킷에만 재전송이 이루어져 보다 빠른 전송률을 유지할 수 있게 된다. 또한 이러한 현상이 생기는 것은 네트워크가 혼잡한 상황이 발생했다는 것이므로 혼잡을 감지하고 윈도우 사이즈를 줄이게 된다.

 

 4) Fast Recovery(빠른 회복)

 

빠른 회복 정책은 혼잡한 상태가 되면 윈도우 사이즈를 1로 줄이지 않고 반으로 줄여 Linear 형태로 증가시키는 방법이다. 빠른 회복정책 까지 적용하면 혼잡 상황을 한 번 겪고나서부터 순수한 AIMD 방식으로 동작한다.

 

 

 

TCP Reno

대표적으로 이러한 제어 정책들을 사용하여 혼잡 제어를 하는 모델로, TCP Reno 가 있다. Reno는 MS-WINDOW에서도 이 방식을 사용한다.