Congestion control

일반적으로 라우터는 다음과 같이 동작한다. 각각의 인터페이스마다 Incoming buffer, Outgoing buffer가 있고, Queue처럼 이 버퍼를 동작시켜 FIFO하게 패킷을 전송하게 된다.

좀 더 자세하게 살펴보자면, 패킷이 라우터에 동작하면 해당 인터페이스의 incoming queue 끝에 추가된다. 이 queue에 들어가 라우터의 CPU가 해당 패킷을 처리시킬 때까지 대기하게 된다. CPU는 버퍼에서 차례로 패킷들을 꺼내 이에 대한 라우팅 처리를 진행한다. 이 과정에서 패킷의 헤더를 열람하여 자신의 Routing Table과 비교하게 되고 해당 패킷을 어디로 보내야 할 지를 결정하게 된다. 경로가 결정되었다면, 결정된 경로의 outgoing interface에 위치해있는 버퍼에 추가되고, 여기서 순서를 기다리다가 네트워크로 전송된다.

문제는 버퍼에서 발생한다. 패킷이 Incoming buffer에 들어가는 속도보다 라우터에서 Incoming buffer의 패킷을 처리하는 속도가 더 느리다면 Incoming buffer가 수용할 수 있는 패킷의 수보다 많아지게 되고, 이는 오버플로우가 발생하여 이후 들어오는 패킷들은 Loss된다.
또는, Outgoing buffer에서 소비하는, 즉 전송되는 패킷의 속도보다 라우터가 패킷을 처리해서 Outgoing buffer에 넣는 속도가 더 빠르다면 Outgoing buffer 역시 오버플로우가 발생할 수 있다.

이렇게 오버플로우가 발생하는 것을 Congestion이라고 한다. Congestion이 발생하면 패킷이 사라질 수 있고 이 때문에 Timeout이 발생할 수 있다. 결국 이 현상은 Network의 용량과 리시버가 허용할 수 있는 용량보다 더 많은 패킷이 발생되기 때문에 발생한다. Sender는 이 두 요소를 고려하여 패킷을 전송해야 한다.

이를 방지하기 위해 TCP는 Sender에게 Receiver가 보내는 rwnd와 congestion window값인 cwnd를 제공한다. rwnd는 Receiver가 받아들일 수 있는 용량을 Sender에게 전달하는 것이고 cwnd는 Network가 받아들일 수 있는 용량을 Sender에게 전달하는 것이다. 이 두 Window size를 받은 Sender는 두 요소 중에서 더 작은 값을 선택하여 실제 Window size로 사용한다.

Actual Window size = min ( receiver-advertised window size , congestion window size )

Slow start & Additive increase

근데 이러면 cwnd는 누가 보내줄까? rwnd는 당연히 Receiver가 명확하니, Receiver에서 Sender로 rwnd값을 알려준다. 그렇지만, cwnd는 "네트워크"가 허용할 수 있는 양이기 때문에 특정 host에서 보내주는 것이 아니라 Sender가 스스로 판단해야 한다.

이때, 사용하는 것이 Slow start라는 방법이다. Slow start를 사용하면 Sender는 cwnd값을 예상할 수 있다.
우선 처음 TCP 연결이 시작되면 Sender는 cwnd를 천천히 증가시켜 나간다. 초기 값은 Segment size의 최대 크기를 Window size로 설정한다. 즉, Maximum Segment Size(MSS)를 초기 cwnd로 사용한다는건데, 왜 이럴까?

MSS는 TCP와 IP 헤더 크기를 제외한 순수 Payload의 크기를 말한다. 즉 초기 cwnd를 MSS로 설정한다는 것은 첫번째 Segment는 무조건 꽉 채워서 보낸다는 것이다. 이렇게 MSS 크기로 초기화해서 전송하게 되면, 이에 대한 Ack가 도착한다. 이때, 아직 Threshold 값에 도달하지 않았다면, 보낸 MSS 크기의 2배만큼, 즉 2MSS만큼 cwnd가 늘어나게 된다. 이렇게 되면 Segment 2개를 꽉 채워서 보내게 되고, 이에 대한 Ack가 또 도착하면 이번에는 4MSS만큼 cwnd가 늘어난다. 즉, 2의 지수배만큼 cwnd는 늘어나게 된다. 이렇게 지수배만큼 늘어나는 것을 바로 Slow start라고 한다.

이후, Threshold에 도달하게 되면 2배씩이 아니라 1개 분량의 MSS만큼 증가한다. 예를 들어 8MSS로 보냈는데, Threshold가 8이라면 다음번 전송은 16MSS가 아니라 9MSS로 해서 보낸다. 이렇게 지수배가 아니라 하나씩 늘어나는 것을 Additive increase라고 한다.

이런 식으로 조금씩 cwnd를 높여가며 데이터를 보낸다면 언젠가는 Network에서 허용할 수 있는 범위를 넘어가는 cwnd값이 도출될 것이다. 이런 상황이 되면 Network에서 Congestion이 발생해서 Loss가 일어날 수 있기 때문에 Sender는 보내는 Segment의 양을 줄여야 한다.

즉, Window size를 줄여야 하는데, Sender 입장에서 Congestion이 일어났다는 것을 알 수 있는 방법은 Ack가 자신에게 돌아오지 않는 상황이 발생하면 Congestion이 일어났기 때문에 Ack가 오지 않는다고 생각할 수밖에 없다. 특히 어떤 특정한 Segment 1개에 대한 Ack만 못 받은게 아니라 다른 여러 개의 Segment에 대한 Ack도 여럿 들어오지 않는다면, 에러가 났다기보다는 Network Flow 상에서 생긴 Congestion으로 인한 것이라고 생각할 수 있을 것이다.

즉, 3-Acks receiving 상황보다는 RTO가 timeout 되었을 때가 더 Congesetion으로 인해 발생한 상황이라고 간주된다. 3-Acks receiving 상황은 특정 Segment 하나가 사라진 상황일 가능성이 더 높기 때문이다. 이런 상황에서 Sender가 Window size를 줄이기 위해 사용하는 것이 바로 Threshold이다.

Threshold를 이용한 Congestion control

이 Threshold값은 Ack가 돌아오지 않아 Sender가 Timeout 되어 문제를 알아차린 그 시점에서의 cwnd의 절반으로 설정한다. 이후 다시 처음부터 slow start를 시작하여 다시 Sender는 Segment를 다시 보낸다. 다시 말하지만 이 상황은 RTO가 timeout되었을 때의 threshold를 설정하는 방법이다.

그러나, 3-Acks를 받아 다시 재전송해야 할 때는 앞선 상황보다는 Congestion이 일어났을 경우가 적다고 생각하여 cwnd는 똑같이 깎되, 이제는 그 cwnd부터 Additive increase하게 동작한다는 점이 RTO timeout 상황과 다른 점이다.

이렇게 보면 첫 번째는 20에서 RTO timeout이 발생한 것이다. 그러면 threshold를 절반인 10으로 내리고, 다시 1MSS부터 Slow start를 시작한다. 이후 3-Ack를 수신하면 threshold를 5로 내리고 여기서부터 다시 Additive increase를 시작한다.

왜 근데 Threshold를 반으로 줄이는걸까? 이렇게 한번에 확 줄이지 않으면 계속 다시 Congestion이 발생할 수도 있고, 반으로 줄여야 2진수 계산에서 비트 하나를 지우면 되니까 더 편해지기 때문일 수 있을 것 같다.

또한, 호스트가 ICMP Source Quench 메시지를 받았다면 어떻게 해야할까? 이 메시지 역시 Congestion이 발생함에 따라 해당 Congestion이 발생한 라우터에서 Sender에게 보내는 양을 줄여달라고 요청하는 것이다. 이건 그러면 RTO가 timeout되었을 때와 동일하게 처리하면 된다.

ECN(Explicit congesetion notification)

이건 TCP의 2bit짜리 Control bit와 IP에서의 2bit짜리 ECN에 대한 설명이다. 이 컨트롤 비트들은 Receiver나 Router에서 Congestion이 일어날 것 같다는 것을 Sender가 미리 안다면 Congestion이 일어나기 전에 미리 Window size를 줄여 선제적으로 대응할 수 있게 해준다. 이렇게 동작한다면 Congestoin으로 Segment들이 Loss되기 전에 미리 대처할 수 있으므로 Segment Loss 현상을 줄일 수 있을 것이다. 즉, 네트워크에서 Congestion이 일어날 것 같다라고 알려주면 Sender에서는 자신의 cwnd값을 줄여서 Window size를 줄이고자 하는 것이다. 이를 Explicit congestion notification, ECN이라고 한다

동작 과정

일단 네트워크에서 특정 라우터가 자신에게 Congestion이 일어날 것 같다고 알려줘야 하기 때문에 먼저, Router가 IP 패킷 헤더에 있는 ECN bit를 조정한다. IP에 있는 ECN bit는 2bit로 구성된다. 앞에 있는 비트는 이 라우터가 ECN동작이 가능하다는 것을 의미하고, 뒤에 있는 비트는 Congestion이 일어날 것 같으면 1로 설정해서 보내는 bit이다. Congestion이 일어날 것 같다는 기준은 주로 Buffer에 패킷이 차는 속도가 급격히 증가하거나 Buffer에 남은 공간이 얼마 없을 때 ECN bit를 설정하게 된다.

이 라우터 내부에서 언제를 기준으로 ECN bit를 1로 설정할 것인가는 명확한 표준이 없지만, ECN이 비교적 최신에 나온 프로토콜이기 때문에 라우터 내부에서 Congestion을 예측하는 알고리즘들이 개발되어 논문으로 나오는 중이다.

그림에서는 빨간색 라우터에서 Congestion이 일어날 것 같아서 ECN bit를 11로 해서 Receiver에게 전달한다. 그러면 Receiver는 이 IP 패킷을 받으면 Sender에게 Ack를 보낼 때 Segment Header의 ECE bit를 1로 설정하여 Ack를 보낸다. ECE가 1이라는 의미는 Sender와 Receiver 사이 어딘가에서 Congestion이 일어날 것 같으니 Sender의 cwnd를 줄이자는 의미이다. Sender는 이 Ack를 받으면 자신이 가진 cwnd값을 줄이고 Receiver에게 CWR bit를 1로 설정해서 다시 echo한다(Receiver에게 알린다).

Maximum segment size (MSS) option

이 옵션은 Segment에서의 data 부분 크기, 즉 Payload에 들어가는 바이트 크기를 조정하는 옵션이다. 이 옵션을 이용해서 Receiver는 Sender에게 자신이 받을 수 있는 MSS를 알려줄 수 있다. Receiver가 자신이 받을 수 있는 MSS를 알려주는 것이기 때문에 Sender가 결정하는 것이 아니라 Receiver가 이 값을 결정하게 된다.

MSS를 결정하는 과정은 역시 TCP Connection을 형성하는 Connection establishment 과정에서 이루어진다. Sender가 상대방에게 자신이 받을 수 있는 MSS를 SYN로 알려주면 상대방은 자신의 MSS를 포함해서 SYN+ACK를 보내게 되고, 이 두 값 중에 작은 값이 두 Connection의 MSS로 결정된다. 즉 MSS option은 Connection establishment 과정에서 사용하는 옵션이고, 이걸 정의하지 않는다면 default값은 536 bytes로 정해진다.

최근에는 이 값이 거의 필수로 들어간다. 성능에 직결되기 때문이다. 이때 설정하는 값은 보통 1460으로 설정한다.

1460 = 1500(이더넷 프레임) - IP 헤더(20) - TCP 헤더(20)