[Computer Network] Congestion Control

 

 

 

Congestion은 너무 많은 소스가 너무 많은 데이터를 너무 빨리 보내서 네트워크가 감당하지 못하는 상태를 의미한다.

패킷 손실이 발생하거나.. 큐잉 지연이 발생하거나.. 당연한 소리긴 함.

 

Flow Control은 한 명의 송신자가 너무 빨라서, 한 명의 수신자가 처리하지 못하는 문제고, 

Congestion Control은 여러 송신자가 네트워크 자체를 혼잡하게 만드는 문제이다.

 

네트워크 안의 라우터가 아니라 송신자 컴퓨터가 TCP 프로토콜을 사용해 스스로 처리한다. (Sender)

 

라우터는 이게 혼잡한지 원활한지 알 수 없음.. TCP의 패킷 손실같은 신호로 혼잡을 감지해야 한다.

혼잡을 감지하는 알고리즘으로는 Slow Start, AIMD를 사용함.

 

 

 

 

 

 

 

1988년에 혼잡 붕괴에 대한 대응으로 혼잡 제어 기능이 처음 도입됐고, 이후 혼잡 제어 알고리즘이 점점 다양화되고 있다. 

혼잡제어 기능이 없으면 패킷이 손실되면 안갔다고 인식하고 정보를 반복해서 보낸다. 그리고 트래픽은 2배가 됨.. 

 

1990년대 까지는 Reno와 NewReno가 표준이었는데. 2000년대 이후 네트워크 환경이 다양해지며 TCP 알고리즘도 여러 갈래로 나뉨.

 

Loss-Based

Teno, NewReno가 이 방식을 사용함. 패킷 손실을 혼잡 신호로 본다.
BIC와 CUBIC은 Linux의 기본 알고리즘으로 채택되고 고속 네트워크에서 대역폭을 빠르게 확보하도록 설계됨.

 

패킷 손실이 발생하기 전에 RTT 증가를 감지해 미리 속도를 줄이는 방식이다.

 

AIMD

 

 

 

 

 

혼잡 제어의 핵심 알고리즘은 AIMD를 사용한다.

여러 컴퓨터가 자율적으로 동작하는 분산 비동기 알고리즘으로, 네트워크 전체의 흐름을 최적화하고 안정성을 유지한다.

 

송신자는 패킷 손실이 발생할 때 까지 전송 속도를 계속 높이고, 손실이 감지되면 속도를 줄인다. Probing for Bandwidth)

 

어떻게 속도를 줄이는지에 대해서는 두 가지 방법이 있음.

 

3개의 중복된 ACK 등장 (TCP Reno) - cwnd를 1/2로 줄인다. (아직 완전히 죽지는 않았구나)

타임아웃 (TCP Tahoe) - cwnd를 1MSS로 초기화한다. (네트워크가 힘들어하는구나)

 

여기서 cwnd는 송신자가 아직 ACK를 받지 않은 상태에서 네트워크에 보낼 수 있는 데이터를 최대량을 의미한다.

그러니 송신자는 아직 ACK를 받지 못한 데이터의 양을 cwnd값보다 작거나 같도록 전송을 제한해야 한다. (혼잡제어는 송신자가 관리)

 

 

TCP Slow Start

TCP 연결 초기에 전송속도를 빠르게 올리기 위해 Slow Start 알고리즘을 사용한다.

시작만 느리고 지수적으로 빠르게 속도를 올려버림.

 

 

 

 

 

일단 cwnd를 1 MSS부터 시작한다. 왜? 처음에는 얼마나 감당할 수 있는지 모르니까.. (cwnd == 보낼 수 있는 데이터 양. 송신측이 관리)

송신자는 보냈지만 ACK를 받지 못한 데이터의 양이 cwnd를 넘지 않도록 제한한다.

 

이후 ACK를 하나 받을 때 마다 cwnd를 1 MSS씩 증가시키는데, 이렇게 되면 한 번의 RTT가 지날 때 마다 전송한 세그먼트의 수 만큼 ACK를 받게 되니 cwnd가 RTT마다 2배씩 증가하게 된다.

 

제대로 받으면 더 보내도 되는구나 싶어서 두배씩 늘리는거임.. 

그런데 패킷 손실이 발생하면 한계에 도달했다는거니까. 그 때 조정 알고리즘을 사용하는 것.

 

새로운 TCP 연결이 생성되거나 재전송 타임아웃으로 패킷 손실이 감지되면 Slow Start가 시작된다.

초기 시작 값을 1로 설정하면 너무 느리니까.. 최근에는 IW 를 10 MSS로 설정해 연결 초기에도 빠르게 데이터를 전송할 수 있도록 설정함.

 

 

 

 

TCP 는 ssthresh 를 임계값으로 다룬다. 

즉, Slow Start 도중 cwnd가 ssthresh보다 커지면 TCP는 전송 속도 증가를 2배씩 증가시키지 않고 1씩 증가시키는 Congestion Avoidance 상태로 돌입한다.

 

1988에 도입된 TCP Tahoe는 Slow Start, Congestion Avoidance, Fast Retransmit 기능을 가진다.

어떤 방식으로든 패킷 손실이 감지되면 cwnd를 1 MSS로 리셋하고 무조건 Slow Start를 다시 수행하게 돼서 비효율적인데..

 

1990에 도입된 TCP Reno는 여기에 Fast Recovery라는 새로운 단계를 도입해서 문제를 해겷한다.

3개의 중복 ACK -> 1 MSS 로 초기화 대신 1/2 로 줄이기.

이후 Fast Recovery 상태로 진입해 손실된 패킷을 재전송하면서 추가로 수신되는 중복 ACK마다 cwnd를 1MSS씩 증가시킨다.

 

1996에는 TCP NewReno가 등장해 기존 Reno를 개선한다. 

Reno는 Fast Recovery 중에 한 윈도우 내에서 여러 개의 패킷이 동시에 손실되면 첫 번째 손실 패킷만 복구할 수 있다.

나머지 패킷은 타임아웃이 발생할 때 까지 기다려야 함.. 

 

Fast Recovery 도중 부분 ACK를 처리로 이 부분을 개선한다.

부분 ACK는 윈도우 내에 아직 받지 못한 다른 손실 패킷이 있음을 의미하고, NewReno는 부분 ACK를 받으면 타임아웃을 기다리지 않고 바로 다음 손실 패킷을 파악하고 재전송한다.

 

2000년대에는 TCP BIC와 TCP CUBIC 알고리즘이 등장했다.

네트워크 환경이 1Gbps이상의 고속망으로 발전했고, 이 환경에서는 Bandwidth-Delay Product 값이 매우 크다.

기존 TCP Reno는 cwnd를 1 MSS씩 선형적으로 증가시키기에.. 이런 BDP를 가진 네트워크의 대역폭을 활용하기 힘들다.

 

 

 

 

 

 

CUBIC은 마지막으로 혼잡이 발생했던 지점을 기억하고, 손실이 발생한 후 cwnd를 급격하게 증가시킨다.

Wmax에 근접할수록 다시 혼잡이 발생할 수 있으니 증가 속도를 늦춘다.

 

형태를 보면 CUBIC은 이름 그대로 cwnd를 시간에 대한 3차함수 형태로 증가시킴을 확인할 수 있다. 

 

Reno는 원래 속도로 돌아가는 기울기가 완만해 한참 걸리지만, CUBIC은 손실 후 빠르게 이전 대역폭을 회복한다.

 

 

구글은 TCP Bottleneck Bandwidth and RTT라는 알고리즘을 도입했다.

기존의 Reno나 CUBIC 기반 알고리즘은 패킷 손실을 혼잡의 신호로 사용하는데, 고속망에서는 패킷 손실이 무조건 혼잡때문에 발생하는건 아니다. 

그러니 패킷 손실 (Loss) 대신 두 가지 지표를 실시간으로 측정한다.

 

Bottlneck Bandwidth - 경로상에서 가장 느린 구간의 최대 대역폭

Round-Trip Propagation Time - 네트워크의 최소 지연 시간 

 

cwnd = BtlBw * Rtprop

 

두 값을 곱해서 최적의 윈도우 크기를 계산해 버퍼를 불필요하게 채우지 않으면서도 대역폭을 최대로 유지한다.

 

 

 

 

연결 사이의 RTT가 동일하고,

세션의 수가 고정되어있고,

모든 세션이 Congestion Avoidance에 있다

 

이 가정 하에서는 AIMD 기반 Congestion Control 알고리즘이 공평하다고 할 수 있다.

 

UDP는 혼잡제어를 안하니 TCP 대역폭을 뺏어갈 수 있으니 RTT가 짧은 연결이 불리할 수 있음.