상세 컨텐츠

본문 제목

네트워크 프로그래밍 - TCP congestion policy(Congestion avoidance additive increase, Slow start, exponential increase)

Computer Science/Network

by 2021. 10. 19. 03:59

본문

반응형

window size는 rwnd(Receiver window)와 cwnd(Congestion Window)의 minimum으로 결정된다. 

rwnd는 receiver가 buffer의 빈 공간에 대한 정보를 sender에게 알려주는 용도이고, cwnd는 sender가 빈 공간에 대한 정보를 전송하는 용도이다. 

window size는 일반적으로 byte 단위이지만 여기서는 패킷 단위로 설명함을 주의한다.
또한 rwnd는 고려하지 않는다.

cwnd는 최초에는 1로 설정하고, 0으로는 설정되지 않는다. 

 

Congestion avoidance, additive increase

위 그림을 보자

cwnd의 값이 4이므로 패킷 4개를 보낸다. receiver에서는 패킷 하나당 ACK을 전송하므로 4개의 ACK을 전송한다. 

receiver로부터 4개의 ACK이 다 왔다면, 이는 패킷 4개를 전송하는 것이 congestion을 일으키지 않는다는 의미로 받아들인다.

 

그러한 경우 4개에서 하나를 추가하여 5개(i+1)를 보낸다. 마찬가지로 5개의 ACK이 정상적으로 돌아오면 congestion을 일으키지 않고 더 패킷을 보낼 수 있다는 의미로 인지한다.

 

6개일 경우, 7개일 경우도 마찬가지이다. 

 

이렇게 패킷의 개수를 늘리는 이유는, 특정 네트워크 구간에 대해 현재 보내는 패킷의 양이 너무 적은지 적당한지를 알 수 없기 때문에 늘려가면서 확인하는 것이다. 한 번에 많이 늘릴 경우 부담이 있을 수 있으므로 (위 그림처럼 반드시 1패킷 단위는 아니지만) 조금씩 늘리는 방법이다.

늘리다가 congestion이 발생하면, 보내는 양을 절반으로 줄인다.

절반으로 줄인 후 다시 조금씩 늘리며 보내다가, congestion이 발생하면 다시 절반으로 줄이고 하는 작업을 반복한다.

 

위 그림과 같이 congestion으로 인한 병목현상이 일어났을때 연결된 connection 모두가 절반으로 보내는 양을 줄이는 것이다. 

 

이와 같은 방법을 additive increase라고 한다.

 

additive increase 방법의 경우 처음 cwnd가 1이고 결과적으로 받을 수 있는 cwnd의 크기가 50이라고 가정한다면, 1에서 50까지 상당히 오래걸린다. 이를 보완하기 위한 방법이 exponential increase이다.

Slow start, exponential increase

exponential increase는 모든 ACK이 정상적으로 돌아왔을 때, cwnd를 2배씩 늘린다.

이름이 Slow start인 이유는 congestion이 없다고 가정했을 때, 처음부터 cwnd를 가능한 만큼 보내는 flow control과 비교했을 때, 1부터 2배씩 증가하는 방식이 상대적으로 느리기 때문이다. 

 

일반적으로 처음에 exponential increase로 2배씩 증가하다가 congestion이 가깝다고 판단 될 경우 additive increase로 1씩 증가하도록 바꾼다.

 

slow start exponential increase방식은 미리 정해놓은 threshold 값에 도달하면, 2배씩 증가하는 것을 멈추고,
congestion avoidance additive increase방식은 congestion이 발견될 때까지 1씩 증가한다.

 

 

TCP congestion policy summary

TCP에서 혼잡이 일어나고 cwnd를 통해 window size를 조절하는 과정이다.

 

처음에는 slow start를 통해 window size를 2배씩 증가시키다가 cwnd가 threshold를 만나게 되면 slow start가 stop한다.

slow start를 벗어난 후 congestion avoidance 즉 additive increase를 한다. 

 

congestion avoidance를 하다 혼잡이 발생하면, cwnd 즉 window size를 절반으로 줄인 후 additive increase를 재개한다.  

 

3 duplicate ACKs 즉 중복된 ACK을 3번 받으면 해당 패킷을 빠르게 재전송하는 것을 이전에 fast retransmission이라고 공부했다. 이는 packet loss로 간주된다. 

 

그림에서 3 duplicate ACKs가 congestion으로 이어지는데 그 이유는 packet loss의 대부분의 경우는 congestion이 원인이기 때문이다. 

Congestion example

위 그림은 시간에 따른 congestion 과정을 그래프로 나타낸 것이고, RTT는 sender가 패킷을 전달하고 receiver가 ACK을 반환하는 한 싸이클을 의미하며, 그림에서 RTT는 1초로 가정한다. 

 

cwnd의 minimum은 1이고 0이 될 수 없다. 그림에서도 y축인 cwnd의 최소값은 1에서 출발한다. 

 

맨 처음 SS(Slow Start)구간을 보자. RTT마다 2배씩 cwnd가 증가한다. 1에서 2배씩 16까지 올라가는데, 

위 그림에서 default로 정해놓은 threshold는 16이다. 따라서 cwnd가 threshold인 16에 다다르면 AI(Additive Increase)로 cwnd는 RTT마다 1씩 증가한다. 

 

RTT 8의 MD(Multiplicative Decrease)는 나중에 보고, 그 다음 SS, AI를 보면 RTT 14에서 3ACKs 즉 packet loss가 일어난다. Additive Increase에서 congestion이 일어나면 window size를 절반으로 줄이므로 cwnd는 12에서 절반인 6이 되고 다시 Additive Increase가 진행된다.

 

AI에서 서서히 증가시키다가 congestion을 만나면 갑자기 확 줄이는 것을 AIMD(Additive Increase Multiplicative Decrease)라고 한다. 

 

RTT 8에서 MD가 일어난 구간을 보자

이 경우 Time out에 의해서 congestion이 발견된 경우이다. 'TCP congestion policy summary' 그림을 다시 보면

time out에 의해서 congestion이 발견되는 경우 3 duplicate ACKs와 같이 절반으로 줄이는 방법으로는 부족해서 window size를 아예 1로 만들어 버린 후 cwnd threshold 값을 현재 window size cwnd 값의 절반으로 설정한다. 

 따라서 congestion example 그래프에서도 time out이 발생하였을 때, threshold의 값은 cwnd 값 20의 절반인 10으로 설정되고, cwnd는 1에서부터 다시 시작한다.

마찬가지로 SS과정을 진행하다 threshold에 다다르면 AI로 진행된다. 

 

그렇다면 어떤 경우에 3 duplicate ACKs로, 어떤 경우에 Time out으로 congestion이 발견되는가?

packet loss가 일어난 후 3개의 패킷이 제대로 전송되고 해당 패킷들에 대한 3개의 ACK이 들어오면 3 duplicate ACKs 방식으로 congestion을 발견하지만, 

 만약 packet loss 이후에 전송하는 패킷이 손실되는 경우에는 중복되는 ACK들이 오지 않으니 congestion을 3 duplicate ACKs로 알려주기 어렵다. 따라서 3개의 ACK이 오기까지 기다리기 전에 Time out로 congestion을 체크하는 것이다. 

Slow start에서의 congestion

여태까지 Congestion avoidance에서 congestion을 발견하는 케이스를 보았다.

'TCP congestion policy summary' 그림을 보면, slow start에서도 3 duplicate ACKs, Time-out을 통해서 congestion이 발생할 수 있는데 slow start에서도 congestion이 발견되면 congestion avoidance와 window size를 처리하는 방식은 같다.

 

반응형

관련글 더보기