[컴퓨터네트워크] TCP Congestion Control

Congestion 

인터넷 상에서 congestion이 일어나는 원인은 다음과 같다: 

 

1. Connectionless packet-switched(Udp, IP같은) 네트워크에서 무조건으로 패킷을 보낼때, 이때 packet switched 네트워크에서는 속도에 상관없이 packet을 보내기 때문에 이걸 받는 쪽에서 감당 못할때 congestion 발생.

2. Router에 있는 큐가 꽉차서 더 이상 패킷을 저장할 수 없을때 congestion 발생한다.

 

이러한 congestion은 결국 packet을 잃거나 delay가 늘어나는 현상이 발생한다.

 

이러한 현상을 해결하기 위해 Congestion Control을 한다.

 

Congestion Control

Congestion Control의 목적은 delay를 없애기 위해서 sending rate을 높이고 lower delay를 원하지만 이러한 경우 buffer overflow가 일어 날 수 있다.

그럼으로 TCP sender의 bandwidth, delay, product값을 잘 optimize 시켜야 한다. 

이 생각은 1986년에 Van Jacobson과 Karels에 의해서 제안되었고 1988년에 TCP에 추가 되었다. 

 

그럼 Source 즉 Sender입장에서 Congestion이 일어나는지 어떻게 알 수 있나?

그것은 RTO(Retransmission time out)를 확인해서 congestion 발생을 확인 할 수 있다. 다만 초창기때 congestion이 발생할 것임을 예측하지 못해서 이러한 데이터는 flow control의 window관리 그리고 error control에서 retransmission 타이머의 개념을 가져와서 사용한다. 

Flow Control과 Error Control은 초창기 설계된 기능들이다..

 

TCP는 sender에 congestion control이 implement되어 있습니다. (flow control은 receiver에)

Sender는 두개의 인자가 있는데 하나는 Congestion window size(cwnd)이고 다른 하나는 slow start threshold value(ssthresh)이다.

cwnd의 값은 MSS(maximum segment size), 하나의 packet을 보낼 수 있는 크기로 설정되있고, ssthresh 값은 65536(최대값) 바이트로 설정이 되어 있다. 

 

Packet을 보내는 pipe에 Congestion이 일어나지 않기 위해서는 cwnd를 한번 보내고 congestion이 일어나지 않으면 2배를 보내고 괜찮으면 4배를 보낸다. 

예를 들어서 처음에 하나의 cwnd를 채우고 congestion이 일어나지 않아서 2배인 2개의 cwnd를 채우고 congestion이 또 일어나지 않아 2배인 4개의 cwnd를 채우고 2배인 8개의 cwnd를 채우자 congestion이 일어났다. 이때 ssthresh는 4가 된다. 이후에는 천천히 pipe를 채우게 된다.cwnd의 MSS값은 초기에는 ssthresh값을 알 수 없으니 1이 된다.

 

number of outstanding segment란 것은 아직 ack가 오지 않은 것을 number of outstanding segment라고 한다.이 값은 rwnd와 cwnd둘중 값의 최소 값이 된다. 

cwnd값은 최초의 1을 가지고 있습니다. 그리고 ack가 한번 잘 돌아왔을 때는 increase, congestion이 발생시 decrease 시켜준다. 

 

AIMD algorithm

cwnd가 congestion이 나면 threshold를 반으로 줄인다. 

대충 위와 같은 톱니 바퀴 모양의 그래프가 나온다.

그렇게 해서 threshold를 반으로 줄이면 이후에 cwnd값을 얼만큼씩 pipe에 넣을 것이냐?

두가지 방법 존재, 1) slow start 2) congestion avoidance

 

Slow Start

slow start는 최대한 빨리 threshold의 값까지 크기가 커진다. exponentially하게 왜? pipe를 최대한 빨리 채우기 위해서!

slow start는 ack를 받을 때마다 혹은 RTT마다 이전에 보낸 segment양 보다 2배개씩 보낸다. (이론적으로...실제론 딱2배씩은 아니라고 한다.)

언제까지 증가? cwnd가 ssresh보다 작거나 같을때까지 증가시킨다. 그러다 RTO가 나면 ssthread = cwnd/2가 된다.(예에서 말했던 것 처럼). cwnd는 1로 초기화된다. 그후로는 congestion avoidance로 넘어간다. 

 

Congestion Avoidance

Slow Start에서 threshold까지 급격하게 증가했다면 그 이후에 congestion avoidance에서는 천천히 증가한다. 

RTT당 1MSS씩 증가시킨다. 

cwnd = cwnd + MSS * MSS / cwnd + MSS / 8 

 

packet drop이 났을 때 RTO를 기다린다. RTO는 1~2초 사이다. 그 다음에 pipe를 empty시키고 다시하면 packet drop이란 시간 손해가 굉장하다. RTO시간 RTT시간 보다 너무 긴 시간을 대기해야 한다. pipe를 empty시켜서 throughput이 갑자기 떨어지는 것도 문제...

 

그래서 다양한 TCP 버전들이 생기기 시작됐다...

 

TAHOE

RTO를 기다리지 말고 three duplicate ack이 발생했을 때 congestion일어났다고 생각. 이 알고리즘은 fast retransmit이라고도 불린다. 

 

RENO

TAHOE의 컨셉을 기본적으로 가져가고 throughput을 조금 유지하자.

cwnd = ssthreash + 3; 여기서 3이 three duplicate으로 온 3이다. 

추가적으로 ack가 들어왔을 때는 cwnd = cwnd + segsize가 된다.