[L4] TCP Congestion Control Algorithm

현대의 TCP 혼잡제어 알고리즘은 더 진보했지만, 10가지가 넘는 변종으로 뿔뿔이 각개 약진을 하기 때문에, 뿌리가 되는 4가지의 알고리즘만 파악해볼 것이다

0. Introduction

1980년대 중반, 라우터를 통과하는 TCP 연결의 Throughput은 0에 가깝게 떨어지는 현상이 나온다.

당시는 혼잡 제어 알고리즘이 없었고, TCP 송신자는 패킷이 유실되었다고 판단하면 재전송만 하게 되어 있었다.

혼잡 발생시 라우터의 RTT가 길어지고, 일부 호스트들이 아직 네트워크 경로 상에 있는 패킷에 대한 타임아웃을 경험하며, 패킷이 잃어버려졌다고 판단하고 재전송한다. 이 경우 네트워크 안에 재전송된 패킷들이 넘쳐나며 더 많은 타임아웃과 혼잡 증가, RTT가 증가한다.

 

이러한 경우를 혼잡 붕괴(congestion collapse)라고 부른다.

 

 

1. Van Jacobson Algorithm (Congestion Avoidance)

데이터 세그먼트 하나가 수신자에게 무사히 배달되면 ACK가 하나 돌아오고, 송신자는 빠져나간 데이터 세그먼트만큼 파이프를 채워넣는다. 이를 통해 평형(equilibrium)이 유지되고 네트워크가 감당할 수 있는 패킷 전송률을 유지할 수 있다

 

이러한 개념은 패킷 보존 원칙(packet conservation principle)을 기반으로 한다. 즉, 네트워크에서 나간 패킷이 있을 때만 새로운 패킷이 네트워크에 들어가며, 결과적으로 네트워크 내에 일정한 패킷 수를 유지한다.

 

 

Self-clocking

TCP self-clocking

TCP self-clocking $ P_b $는 병목에서의 데이터 세그먼트 간격 $ P_r $은 병목 아닌 구간에서의 세그먼트 간격($=P_b$) $ A_r $은 ACK 간격

 

ACK 패킷은 작기 때문에 병목을 지나가더라도 간격이 바뀌지 않아 ($ A_b $) TCP 송신자에 이르러서도 그대로 ($ A_s $) 유지된다.

평형 상태에서는 안정적으로 파이프의 병목이 소화할 수 있는 속도로 패킷이 자동 전송된다. 이때 병목 크기에 정의되는 파이프는 항상 차있다.

 

ACK 패킷은 작기 때문에 병목을 지나도 간격이 바뀌지 않으며, TCP 송신자에 이르러서도 그대로 유지된다. 이로 인해 병목에서 소화할 수 있는 속도로 자동으로 패킷이 전송된다.

송신자는 실제로 파이프의 크기를 알지 못한다. 병목 라우터에서 할당된 대역폭과 지연 시간은 계속 변하기 때문이다. 따라서 Jacobson 알고리즘은 현재 네트워크 경로가 허용할 수 있는 전송 속도를 추정하는 것을 목표로 한다.

 

TCP 송신자는 어떻게 파이프의 크기를 알아낼까?

Jacobson 알고리즘은 AIMD(Additive Increase Multiplicative Decrease) 방식을 따른다.

 

1. ACK가 오면 $ W \leftarrow W + 1 / W $

2. ACK가 오지 않고 재전송 타임아웃이 발생하면 $ W \leftarrow 1 $

 

1번의 결과로, 만일 한 RTT 동안 전송한 W 세그먼트가 모두 ACK에 돌아오면 W는 1 RTT가 지난 후 1세그먼트 만큼 커져있게 된다.

이렇게 RTT당 전송하는 데이터 량이 1 세그먼트씩 커지게 되는 것을 additive increase(AI)라고 한다.

 

TCP 송신자가 파이프의 최대용량을 알 수 없기에 1번이 반복되다보면 $ W $가 그 용량을 넘어서는 때가 온다. 그러면 패킷들이 병목 라우터에서 유실된다. 그 결과 2번이 수행되며 $ W $는 가장 최소값으로 리셋되게 된다.

1번이 반복되다 2번, 다시 1번으로 돌아가는 식의 동작이 반복된다.

 

TCP혼잡제어 알고리즘은 이렇게 불가피하게 반복적으로 혼잡을 야기하는 알고리즘이 된다.

 

 

 

2. Slow Start Algorithm

성장하던 혼잡 윈도우가 패킷 유실로 인해 1 세그먼트로 리셋되면, 파이프의 최대 용량까지 회복하는 데 오랜 시간이 걸린다.

 

previous-window-size를 $ W(k-1) $, current-window-size를 $ W(k) $ 라고 가정할 때, $k$는 인접한 패킷 유실 이벤트들 사이의 한 기간을 뜻한다. 1부터 $ W(k) $까지는 빠르게 윈도우를 증가시키는 것이 Throughput을 향상시키는 방법이다.

 

이 때, $ W(k-1)/2 $까지는 ACK가 올 때마다 윈도우 크기를 2배로 증가시키는 exponent increase 방식을 사용한다. 즉, ACK가 도착할 때마다 윈도우 크기를 $W \leftarrow W + 1$로 증가시키는 방식이다.

 

고속 증가 알고리즘은 ACK가 올 때마다 윈도우 크기를 2배로 키운다. -> exponent increase $ W \leftarrow W+ 1 $
ACK가 올 때마다이지, RTT마다가 아니기에 해당 식은 exponent increase가 맞다.

 

패킷 유실 직후 $ W=1 $일 때 세그먼트 1개가 전송된다. 통상적으로 $W(k) > 1 $일 것이므로 파이프 용량을 초과하지 못 하고 ACK가 된다. 그러면 $ W \leftarrow 1 + 1 = 2$가 된다. 따라서 두 세그먼트가 전송되는데, 이 두 세그먼트도 ACK가 되어 돌아오면, 두 번 $W$가 증가하여 $W=4$가 된다.

 

이 방식은 RTT마다 윈도우가 두 배씩 증가하기 때문에 "Slow Start"라 불린다. 여기서 "Slow"는 초기 윈도우 크기(1 세그먼트)가 작다는 의미이지, 증가 속도가 느리다는 뜻은 아니다. 전송 속도를 아주 낮은 Slow Speed에서 시작한다는 의미라는걸 생각해보자.

 

그림과 같이 Slow Start는 윈도우 크기가 $W(k-1)/2$인 Slow Start Threshold(ssthresh)에 도달하면 중단되고, 그 후 additive increase 방식을 사용하여 윈도우를 점진적으로 증가시킨다.

 

 

1. Exponent increase에 의해 $W(k)$에 도달하는 경우

 

$$  \sum_{i=0}^{log_2 W(k)-1} + 2^i + W(k) $$

 

2. Exponent increase에 이어 linear increase로 $W(k)$에 도달하는 경우

$$  \sum_{i=0}^{log_2 W(k)-1} + 2^i + \sum_{i=1}^{W(k)/2} W(k) / 2+i $$

 

 

1번 방식의 경우 $1+2+4+8+11 = 26$ 패킷이 네트워크를 통과한다. 

2번 방식의 경우 $1+2+4+8+9+10+11 = 37$ 패킷이 네트워크를 통과한다.

 

매 RTT마다 몇 패킷이 전송되었는가가 Throughput이므로 각각 5.2, 5.28이다.

하지만 이 방식은 패킷 유실의 강도를 전혀 무시함으로써 1번 방식에 최대한 유리하게 계산된 결과.

 

2번 방식의 경우 5개의 패킷이 아니라 1개의 패킷이 유실된다. -> 재전송과 윈도우 크기 복구가 훨씬 빠르게 된다.

패킷 유실 시간 간격이 짧아짐으로써 실제로는 훨씬 Throughput이 커질 수 있다.

 

1, 2의 차이인 $ \sum_{i=1}^{W(k)/2-1} W(k)/2+i $ 가 커진다. 이 차이값의 함수는 $O(W^2)$이다.

위 Toy Example이 차이가 얼마 안 되지만, 현실에서는 차이가 매우 크며, TCP에서 2번 방식이 채택된 이유 중에 하나다.

 

 

 

 

3. Fast Retransmit Algorithm

한 윈도우 만큼 세그먼트를 RTT동안 내보낼 때, 그중 몇 패킷이 유실되는가 하는 건 네트워크 혼잡 상태를 추정하는데 주요한 정보가 된다. 일단 패킷이 유실되면 TCP송신자는 그 사실을 알아내는데 시간을 쓰게 되는데, TCP 재전송 타이머는 최신 RTT보다 크게 설정되어야 하므로, RTO가 수백 ms에 이를 수 있다. Throughput의 손실 문제를 해결하기 위한 알고리즘이다.

 

TCP 송신자가 세그먼트 유실을 발견하는 방법은 Duplicated ACK를 사용하는 것인데, ACK되고 있는 시퀀스 번호를 가진 세그먼트가 유실되었다고 판단한다. 즉, out-of-order delivery가 늦는 것이 아니라고 판단한다.

이러한 세그먼트 유실을 찾는 방법을 Fast Retransmit라고 한다.

 

Fast Retransmit의 조건

1. 윈도우 크기가 꽤 커서 여러 세그먼트가 한꺼번에 전송될 정도

2. 혼잡이 발생하여 세그먼트의 유실이 일어난 라우터의 혼잡 도가 극심해서는 안된다. 즉, 유실 직후 도착하는 다음 세그먼트들은 라우터 큐에 대기해야함.

 

Fast Retransmit은 재전송 타이머 기반 재전송을 완전히 대체할 수 없으나, 조건이 충족될 경우 빠른 재전송을 가능하게 한다. 이는 RTT + 3d(패킷 전송 간격)로 빠르며, 타이머 기반 재전송의 $avg(RTT) + 4 \times dev(RTT)$보다 효율적이다.

RTT와$avg(RTT)$가 비슷하다고 가정하면 $3d$는 $4 \times dev(RTT)$보다 작다.

 

 

 

4. Fast Recovery Algorithm

Fast Retransmit으로 패킷 유실을 발견했다면 병목 혼잡이 심각하지 않다는 의미다.

(=한 개의 패킷이 유실된 직후에도 그 다음 패킷들이 병목 라우터에 받아들여졌다는 뜻)

 

이 알고리즘은 패킷 유실이 발생하였으므로 전송 속도를 줄이되, Slow Start를 시행할 만큼 크게 줄이지 않고 윈도우 값을 $W \leftarrow ssthresh + 3$으로 설정한다. 윈도우가 ssthresh를 초과하면 Slow Start 대신 Congestion Avoidance Algorithm을 수행한다.

 

Fast Recovery는 Fast Retransmit에 의해 시작된다. Fast Retransmit의 조건인 3개의 duplicated ACK 각각은 수신자로부터 패킷이 빠져나갔다는 것을 의미하며, TCP 송신자는 이 세 패킷이 나갔음을 감안하여 윈도우 크기를 증가시키며 재전송을 수행해 파이프 내 평형 상태를 유지한다.

 

Fast Recovery는 윈도우를 기존의 약 1/2배로 만들기 때문에 Multiplicatvie Decrease(MD)라고 불린다.

$\rightarrow$ 안정적인 제어가 되려면 AI, 줄일 땐 과감한 MD를 사용해야 한다는데 기반한 알고리즘이다. (=AIMD)

 

Fast Retransmit과 Fast Recovery가 불가능한 경우에는 항상 Time-out과 Slow Start가 대안으로 준비되어 있다.

 

 

 

 

5. Modern Congestion Control Algorithms

TCP가 처음 개발될 당시에는 컴퓨터들이 Interrupt 처리에 부하가 많이 걸려 TCP 코드에도 시간을 정확히 재기 위해 Timer Interrupt를 촘촘한 간격으로 쓰지 못 했다.

하지만 컴퓨팅 성능이 개선되며, 최근 TCP 혼잡 제어는 RTT의 미세한 변화를 지속적으로 측정하여 혼잡 상태를 미리 감지하고 전송률을 조정한다. 대표적인 현대적 알고리즘에는 BBR(Bottleneck Bandwidth and RTT), CUBIC, Reno, Vegas 등이 있다.

 

이제는 큐잉 지연 시간의 증가에 의해 야기되는 미세한 RTT 변화마저도 부담없이 측정할 수 있어, 결과적으로 TCP 송신자는 자신의 전송 경로상 혼잡 수준을 미리 추정할 수 있고 미리 전송률을 낮출 수 있다.

 

• BBR: RTT와 네트워크의 병목 대역폭을 직접 측정하여 혼잡을 예측하고 Throughput을 최적화한다.
• CUBIC: 비선형적으로 윈도우를 증가시키고 빠르게 복구하는 방식을 채택하여 높은 대역폭 환경에서 뛰어난 성능을 발휘한다.
• Reno와 NewReno: 전통적인 AIMD 방식을 개선하여 중복 ACK 처리 능력을 높였다.
• Vegas: RTT 변화를 세밀히 관찰하여 혼잡을 예방적으로 대응한다.