TCP - 4. congestion control

평소처럼 웹사이트에 접속하려는데 오늘따라 유독 접속이 느렸던 경험이 있을 것이다.

수강신청처럼 사람이 갑자기 몰리는 상황에 특히 그렇다.

서버 자체가 많은 사용자의 요청을 처리하는데 시간이 많이 걸리는 것일 수 있고

네트워크가 혼잡해서 drop이 발생하거나 queueing delay가 큰 것 일수도 있다. 이런 상황을 congestion collapse라고 한다.

 

정리하면 congestion은 너무 많은 사용자가 너무 많은 데이터를 네트워크가 감당하기 힘들정도로 보내는 것을 말한다.

이 문제를 해결하려면 sender가 패킷을 보내는 속도를 제한해야 한다.

 

* 참고로 congestion control은 신뢰성 있는 전송을 위해서도 필요하다. 네트워크가 혼잡할수록 reliable data transfer가 어렵기 때문이다. (ex. queue overflow)

1. Principle of congestion

incomming rate가 커질수록 outgoing rate는 커지다가 네트워크 throughput의 절반, 최대 R/2에 수렴한다.

queue의 크기를 무한으로 가정했기 때문에 패킷이 무한정 쌓일 수 있어 queueing delay는 시간이 갈수록 무한대를 향해 지수배로 커진다.

이번에는 버퍼의 크기가 유한한 상황을 가정해보자. 이전 상황과 달리 패킷 loss가 발생할 수 있다.

Host A가 application layer에서 lamda(in)으로 transport layer에게 패킷을 내려보내면 receiver인 Host C에서 transport layer에서 application layer로 패킷이 전달되는 속도 lamda(out)은 lamda(in)과 동일하다.

Host A의 transport layer는 재전송의 경우도 있기 때문에 lamda(in)보다 더 많은 패킷을 전송한다. (lamda'(in)) 

 

가정 1. sender가 버퍼가 얼만큼 비어있는지 알고 있다면?

sender는 버퍼에 공간이 있을때만 패킷을 전송한다.

즉 각 호스트는 R/2이상의 속도로 패킷을 보낼 일이 없기 때문에 throughput 그래프를 보면 lamda(in)은 R/2이후로 없다. 

당연히 outgoing rate는 R/2를 넘지 않는다.

 

가정 2. 버퍼가 얼마나 비어있는지는 모르지만 sender가 packet loss를 알아채고 대응할 수 있다면?

패킷 loss가 발생했을때 재전송한다. 재전송을 고려하면 각 host는 R/2보다 더 많이 보내게 된다. 

당연히 outgoing rate는 R/2를 넘지 않는다.

 

좀더 현실적인 가정 3. 버퍼 크기도 모르고 packet loss를 알아챌 수 없다.

sender가 버퍼 크기를 모르니 버퍼가 꽉차서 패킷 loss가 발생할 수 있다.

또한 queueing delay때문에 timeout내에 ack가 도달하지 않으면 packet loss가 발생하지 않았어도 재전송하므로 버퍼에는 중복 패킷이 존재할 수 있다.

버퍼 안에 중복패킷들이 link 자원을 쓸데없이 소모하기 때문에 때문에 throughput은 R/2에 닿지 못하고 근접만 할 수 있다.

 

완전 현실적인 가정 4. 가정3에 더불어 multihop, 더 많은 sender환경 일 때

만약 red traffic이 증가하면 blue traffic이 drop될 것이다. blue traffic이 drop 되면 더 많은 패킷을 재전송하게 되고 결국은 pink packet이 drop될 수도 있다. 즉 서로의 throughput은 관련이 있다.

어떤 패킷이 세번째 hop에서 drop되면 그 패킷을 전송하기 위한 이전의 첫번째, 두번째 hop에서의 upstream transmission 노력들은 다 자원 낭비가 된다.

따라서 모두가 계속해서 많이 보내려한다면 각자의 throughput은 증가하다가 갑자기 점점 0에 가까워진다. 이게 congestion collapse이다.

참고로 TCP Tahoe가 이런 문제가 있어서 TCP Reno가 등장했다.

N명이 네트워크를 통해 서버에 요청을  한다고 해보자.

throughput graph를 한번 더 그려보면 다음과 같다.

연두색은 "패킷 loss, duplicate과 관련된 재전송이 소모하는 자원"을 나타낸다. 이것들이 bandwidth를 소모한다.

2. Congestion control

네트워크 혼잡을 해결하는 방법은 결국 sender가 패킷을 천천히 보내도록 하는 것이다.

throughput이 이상적인 수치에 도달하려고 하면 sender가 천천히 보내도록 하고 반대로 좀 여유가 있으면 빨리 보내도록하는 것이다.

그럼 그 throughput의 이상적인 수치는 어떻게 구할까? 이전 예시처럼 간단하게 R/N으로 구할 수 없기 때문에 일단 점점 빨리 보내다가 throughput이 갑자기 많이 줄어든다(congestion발생) 싶으면 sender를 늦추는 방식을 사용한다. 

2-1 Rate는 어떻게 조절할 수 있을까?

congestion window, cwnd를 통해 sender의 transmission rate를 조절한다.

outstanding, in-flight unacked 패킷이 cwnd보다 작거나 같도록 한다. (노랑 영역이 cwnd보다 작거나 같도록 한다)

TCP는 window 크기를 congestion 상황에 맞추어 동적으로 조절한다.

네트워크가 혼잡하지 않으면 cwnd를 늘리고 반대로 너무 혼잡하면 cwnd를 좁혀서 sender가 보내는 패킷의 양을 조절한다.

RTT를 대략 구해보면 위와 같다. cwnd만큼 패킷을 연달아 보내고 ack가 하나 오는게 RTT니까 대략 이렇게 추정한다.

2-2 TCP Slow Start 

connection이 만들어지면 첫 loss가 발생할 때까지 rate를 exponential하게 증가시킨다.

맨 처음에는 cwnd를 1 MSS로 설정한다.

*MSS(maximum segment size)

ack가 한개씩 도달할 때마다 계속 cwnd를 1씩 키운다. 그럼 대략 1 RTT마다 두배씩 rate가 증가하는 꼴이 된다.

이렇게 rate를 지수배로 증가시킬 수 있다. 

 

이렇게 rate가 계속 증가하다가 timeout이 발생하면 다시 slow start로 돌아온다.

이렇게 rate가 계속 증가하다가 3-duplicated ACK가 발생하면 congestion avoidance도 돌아간다.

2-3 sender는 congestion을 어떻게 탐지할까?

TCP는 packet loss가 발견되면 네트워크가 혼잡한 상황이라고 인지한다.

하지만 sender는 packet loss를 정확하게 알 수 없다. 단지 그럴 가능성이 높다고 다음처럼 추측할 뿐이다.

timeout 혹은 3-duplicated ACK가 발생하면 packet loss가능성이 매우 크다고 생각하고 조치를 취한다.

대부분의 delay는 queueing delay로부터 발생하기 때문에 이 추측은 매우 타당하다. 하지만 무선 통신의 상황이라면 loss를 일으키는 변수가 너무 많기 때문에 타당하지 않을 수도 있다.

2-4 rate를 언제 얼마나 늘리고 줄여야하나?

1. sender가 timeout을 경험한 경우

-> 네트워크가 "매우" 안좋다

-> slow start로 돌아간다 (cwnd를 1MSS로 설정)

-> 무한정 cwnd를 증가시키지 않고 threshold까지만 키운다. (ssthresh)

-> threashold 부터는 congestion을 피하기 위해 rate를 linear하게 증가시킨다. (congestion avoidance 상태)

 

2. sender가 3-duplicated ACK를 경험한 경우

-> 네트워크가 "조금" 안좋다

-> cwnd 크기를 절반으로 줄인다. (fast recovery)

-> congestion을 피하기 위해 rate를 linear하게 증가시킨다. (congestion avoidance 상태)

 

*slow start 이후 timeout 혹은 3 dup ack를 경험(이때 윈도우 크기 h)하고나면 ssthresh를 h/2로 설정한다.

*참고로 지금까지 우리가 배우고 있는 내용들은 다 TCP Reno를 기준으로 한다.

2-5 congestion avoidance

최종적으로 sender는 congestion을 피하기 위해 congestion avoidance 상태로 들어간다.

congestion avoidance는 천천히 linear하게 cwnd를 증가시키는 단계를 말한다.

loss가 발생할 때까지 bandwidth 한계까지 천천히 도달하는 것이다.

 

AIMD(additive increase, multiplicative decrease) 알고리즘을 활용한다.

additive increase : loss가 발생할 때까지 every RTT마다 cwnd를 1MSS만큼 증가한다.

multiplicative decrease : loss가 발생하면 cwnd를 반으로 줄인다.

cwnd가 sending rate를 대변한다. 모양이 톱날 같다고 해서 saw tooth behavior이라고 한다.

2-6 정리

처음에는 ssthresh(8)까지만 cwnd가 지수배로 증가한다. 그 이후부터는 linear하게 증가한다. (congestion avoidance)

라운드8에서 3 dup ack를 경험하면 ssthresh를 6으로 설정하고 거기서 부터 congestion avoidance로 들어간다. (검정 그래프)

반면 라운드8에서 timeout을 경험했다면 ssthresh를 6으로 설정하고 slow start로 돌아간다. (파랑 그래프)

 

* 참고로 한가지 아이디어를 더 소개하려 한다.

3 dup ack는 timeout에 비해 좀 덜 심각하게 인지하기 때문에 slow start로 안가고 fast recovery를 위해 cwnd/2 부터 congestion control을 시작한다고 했다. (ssthresh = cwnd/2)

하지만 지금 소개할 방법은 fast recovery 상태에서 cwnd를 ssthresh + 3으로 만든다.

fast recovery 상태에서 중복 ack가 발생하면 그냥 윈도우 크기를 +1 MSS 만큼 늘린다.

새로운 ack가 도달하면 +3, +1 했던 내용들을 다 버리고 ssthresh 값을 시작으로 congestion avoidance를 시작한다.

fast recovery 상태에서 timeout이 발생하면 slow start로 이동한다. 

이 아이디어는 tahoe말고 reno부터 적용되었다.