Approaches towards congestion control

네트워크는 수많은 개체들이 서로 통신하는 공공 (Public)의 영역이다. 네트워크상에서 통신하는 수많은 개체들은 모두 많은 양의 데이터를 빠르게 전송하기를 원한다. 하지만 모든 개체가 무분별하게 데이터를 많이 전송하면 네트워크는 혼잡해진다.

기본적으로 TCP는 송신한 패킷이 제대로 전송되지 않으면 그 데이터를 재전송한다. 만약 네트워크가 혼잡해서 데이터가 제대로 전송되지 않으면 TCP는 똑같은 데이터를 계속 재전송할 것이며, 이는 결과적으로 네트워크를 더더욱 혼잡하게 만들 것이다.

따라서 TCP는 같은 네트워크 상의 다른 개체들을 위해, 또 전체적인 네트워크의 혼잡도를 낮추기 위해서 송신하는 데이터의 양을 조절한다.

네트워크의 혼잡이 예상되면 데이터의 양을 줄이고, 네트워크가 널널하다고 판단되면 데이터의 양을 늘리는게 바로 혼잡 제어 (Congestion control)이다.

TCP에서 전송자는 항상 네트워크의 혼잡도와 수신자의 수용량을 체크하면서, 둘 중에서 더 성능이 좋지 않은 쪽에 맞춰서 패킷을 전송해야 한다.

만약 수신자는 10바이트의 데이터를 받을 수 있지만 네트워크가 혼잡하여 5바이트밖에 보낼 수 없다면, 전송자는 네트워크 혼잡도에 맞춰서 5바이트의 데이터를 보내야한다.

반대로 네트워크는 현재 10바이트의 데이터를 보낼 수 있지만 수신자가 5바이트의 데이터만 받을 수 있다면, 전송자는 수신자의 수용량에 맞춰서 5바이트의 데이터를 보내야한다.

이때 수신자의 수용량은 흐름 제어 방식에 따라서 수신자의 피드백으로 확인할 수 있다.
그런데 네트워크의 혼잡도는 어떻게 파악할 수 있을까?

End-end congestion control

End system들은 서로 주고 받는 TCP ACK 피드백을 토대로 네트워크의 혼잡도를 유추한다. 만약 ACK가 오지 않거나 늦게 온다면 네트워크가 혼잡하다고 판단하여 데이터의 양을 줄인다.

항상 정확하지는 않지만 어쩔 수 없는 측면이 있다.

Network-assisted congestion control

네트워크의 라우터들이 지속적으로 어느 정도의 데이터를 전송하고있는지를 End system들에게 알려주는 방식이다. 하지만 이는 추상적인 개념이며 현재 구현되어있지 않다.

The TCP Intuition

TCP의 혼잡 제어가 이루어지는 방식을 그림으로 빗대어 표현한 개념이다.

파이프를 통해 물을 보내야하는 상황에서, 처음부터 많은 양의 물을 쏟아붇지 않고, 한 방울 두 방울 조금씩 보내보면서 얼마나 빠르게 가는지를 본다.

물이 충분히 빠르게 전송된다고 판단되면 더 많은 양의 물을 붇기 시작한다.
만약 물이 흐르는 속도가 느려지만 그만큼 파이프에 물이 많이 들어있다고 판단해서 물의 양을 줄인다.

TCP의 혼잡 제어는 이와 같이 이루어진다.

TCP Congestion Control

TCP에서 혼잡 제어는 다음과 같이 이루어진다.

1. Slow Start
   병목 현상이 샐길 수 있으므로 먼저 적은 양의 데이터를 보내면서 시작한다.

2. Additive Increase
   Threshold를 만나면 (점차 수용량의 한계에 가까워지고 있으니) 점차 증가 속도를 늦춘다. (Linear)

3. Multiplicative Decrease
   패킷 유실이 발견되면 데이터의 양을 절반으로 확 줄인다.

Multiplicative Decrease에서 절반으로 확 줄이는 이유는, 네트워크의 혼잡도를 해결하기 위해서는 양을 조금만 줄여서는 힘들다. 모든 엔드 시스템들이 한번에 확 줄여야 해결할 수 있다.

Additive increase, Multiplicative decrease

혼잡 제어에서 전송하는 데이터 양의 단위는 MSS (Maximum Segment Size)이다.

additive increase : 매 RTT마다 1 MSS^2씩 Window Size를 증가한다.
multiplicative decrease : 패킷 유실이 발견되면 Window Size를 절반으로 줄인다.

이러한 과정에서 생기는 다이어그램이 마치 톱날같다고 하여 Saw Tooth Behavior 이라고도 한다.

Details

데이터의 전송 속도는 네트워크의 혼잡도에 따라 달라진다.
혼잡도가 높으면 속도가 늦어지고, 혼잡도가 낮으면 속도가 높아진다.

네트워크의 혼잡도는 결국 그 안의 개체들에 의해 결정된다. 따라서 전송 속도는 네트워크 안에 있는 개체들에 의해 결정된다고 볼 수 있다.

따라서 전송 속도는 rate = (Congestion Window Size / RTT) Bytes/sec 로 구할 수 있다.

Slow Start

처음에 연결이 시작되면 전송 속도는 낮은 속도에서 시작하다가 처음으로 패킷 유실이 발생하기 전까지 기하급수적으로 증가 (exponentially increase)한다.

TCP Tahoe vs Reno

TCP 혼잡 제어는 크게 2개의 버전이 있다.

버전 1은 Tahoe, 버전 2는 Reno 라는 이름을 갖고 있다.

TCP 혼잡 제어 과정에서는
먼저 패킷 유실이 발생하면 Window size를 절반으로 줄여서 다시 Slow Start 부터 시작한다. 이때 TCP에서는 패킷 유실을 크게 2가지 방식으로 파악한다. (Time-out vs 3-duplicate-ACK)

Time-out이 발생했다는 것은 유실된 패킷 이후의 모든 패킷이 정상적으로 전송되지 않았다는 의미이고, 3-duplicate-ACK은 특정 패킷 하나가 유실된 상황이다.

즉, Time-out으로 인한 패킷 유실이 훨씬 더 심각한 상황이다.

TCP Tahoe

그림에서 파랑색 선이 TCP Tahoe의 동작 방식이다.

Slow Start로 시작해서 Threshold (임계점)를 넘어서면 선형적으로 (Linear) 증가한다.
이후 패킷 유실이 발생하면 Congestion Window Size가 무조건 1 MSS로 감소한다.
따라서 초기 상태로 되돌아와 다시 Slow Start 부터 시작한다.
이때 Threshold는 유실이 발생했을 시점의 절반이 된다.

그림에서는 12 MSS에서 유실이 발생했으므로, 새로운 Threshold는 12 / 2 = 6이 된다.

문제는 이 Tahoe는 무조건 1 MSS로 보내버린다는 것이다. 따라서 다시 처음부터 원래 상태까지 돌아오는데 시간이 많이 걸린다.

이를 개선해서 등장한 다음 버전이 TCP Reno 이다.

TCP Reno

앞서 얘기했듯 TCP에서 패킷 유실은 Time-out과 3-duplicate-ACK, 2가지 케이스로 발생한다.

Reno는 Time-out이 발생하면 Tahoe와 동일하게 Congestion window size를 1 MSS로 줄인다.

하지만 3-duplicate-ACK가 발생하면, Congestion window size를 바로 직전에 유실된 패킷을 기준으로 절반으로 줄인다.

TCP Fairness

만약 K 개의 TCP 연결 디바이스들이 R bps의 대역폭을 가지는 병목 링크 (Bottleneck Link)를 공유한다면, 각 연결의 평균 전송률을 R / K에 가깝게 맞출 경우 혼잡 제어 매커니즘은 공평 (Fairness)하다고 할 수 있다.

예를 등러서, 해당 링크를 먼저 사용하고있던 디바이스가 더 높은 속도를 가질 수는 있다. 하지만 다른 디바이스가 들어오면서 패킷 유실이 발생하기 시작하면, Multiplicative Decrease를 실시하면서 모든 디바이스가 속도를 절반으로 줄인다.

다시 점진적으로 속도를 증가시키다가 패킷 유실이 발생하면 또 속도를 절반으로 줄인다.

이렇게 속도를 늘리다가 줄이다가 하다보면 결과적으로 공평한 Throughput을 찾아갈 수 있다.