[Network] TCP Congestion control

📡 TCP AIMD

네트워크에서 데이터를 너무 빠르게 전송하면 라우터의 버퍼가 넘치면서 패킷 손실이 발생할 수 있다. 이러한 상황을 Congestion(혼잡)이라고 한다. TCP는 Congestion 상황에서도 효율적으로 데이터를 전송하기 위해 congestion control 알고리즘을 사용한다.

 

AIMD(Additive Increase Multiplicative Decrease)

TCP의 혼잡 제어 메커니즘은 AIMD 방식을 따른다. AIMD는 가산 증가 곱셈 감소라는 의미로, 네트워크가 원활하게 동작할 때는 전송 속도를 조금씩 늘리고 혼잡이 감지되면 전송 속도를 급격히 줄이는 방식이다.

 

• Additive Increase (가산적 증가): 네트워크가 양호하면 TCP는 매 RTT$_{Round \space Trip \space Time}$마다 혼잡 윈도우를 1MSS$_{Maximum \space Segment \space Size}$씩 증가시킨다.
• Multiplicative Decrease (곱셈적 감소): 반대로 패킷 손실이 발생하면 네트워크를 혼잡으로 판단하고, cwnd를 반으로 줄인다.

 

말은 되게 어렵게 작성된 것 같지만 증가할 때는 1씩 선형적으로 증가하고, 감소할 때는 절반으로 줄어든다고 이해하면 된다.

 

 

이 방식은 TCP의 전송 속도를 톱니$_{sawtooth}$ 모양으로 변화시킨다. 속도를 점진적으로 올렸다가 혼잡을 만나면 급격히 줄이고, 다시 서서히 증가하는 식이다. 이를 통해 TCP는 네트워크의 가용 대역폭을 조심스럽게 탐색$_{probing}$하게 된다.

송신
속도
│
│    /\    /\    /\
│   /  \  /  \  /  \
│  /    \/    \/    \
│ /
│/
└───────────────────── 시간

 

TCP는 패킷 손실을 ACK 패킷 반복 수신(3중복 ACK)이나 일정 시간 ACK 미수신(타임아웃)으로 감지해 그에 따라 혼잡 윈도우를 다르게 조절한다. 이 방식은 Reno나 Tahoe 같은 TCP 구현에 따라 다르게 적용된다.

 

cwnd

TCP에서 cwnd(congestion window, 혼잡 윈도우)는 송신자가 네트워크에 동시에 전송할 수 있는 데이터 양의 상한선을 의미하는 변수다. 혼잡 윈도우는 네트워크의 혼잡 상태를 반영해 전송 속도를 동적으로 조절한다.

 

TCP는 데이터를 보낼 때 다음 조건을 만족해야 한다.

 

$$
LastByteSent - LastByteAcked ≤ cwnd
$$

 

이 식은 아직 ACK를 받지 못한 상태로 네트워크에 남아 있는 데이터의 양이 혼잡 윈도우를 초과할 수 없음을 의미한다. cwnd가 작으면 적은 양의 데이터를 보내야 하고, cwnd가 크면 더 많은 데이터를 한 번에 전송할 수 있다.

 

실질적인 송신 속도는 다음과 같이 계산된다.

 

$$
송신 \space 속도 ≈ cwnd / RTT \space (단위: 바이트/초)
$$

 

즉, cwnd의 크기와 RTT가 TCP의 전송 속도를 결정하는 요소가 된다.

 

TCP는 AIMD 방식 등을 통해 cwnd의 크기를 점진적으로 조절하면서 혼잡을 회피하고 동시에 네트워크의 가용 대역폭을 최대한 활용하려고 한다.

 

이렇게 AIMD는 TCP의 전체 congestion control 방식에서의 기본 원리로 생각하면 된다. 하지만, TCP는 연결이 처음 시작될 때부터 congestion control까지 여러 단계로 혼잡 상황에 대응한다. 대표적으로 Slow Start, Congestion Avoidance, Fast Recovery 등이 있고 이들 각 단계는 AIMD 원칙을 기반으로 동작한다.

 

TCP 연결 초기 단계에서 사용되는 Slow Start 먼저 살펴보자.

 

 

📡 Slow Start

Slow Start의 개념

TCP 연결이 처음 시작될 때, 송신자는 네트워크의 용량(대역폭과 지연 등)을 알 수 없다. 너무 많은 데이터를 한꺼번에 보내면 congestion을 유발하고, 너무 적게 보내면 자원을 비효율적으로 사용하는 문제가 생긴다.

 

이 문제를 해결하기 위해 TCP는 Slow Start라는 congestion control 알고리즘을 사용한다. 이름과 다르게 이 알고리즘은 실제로 cwnd를 지수적으로 빠르게 증가시키는 방식을 사용해 ‘빠른 시작’에 가깝긴 하다.

 

Slow Start의 동작 방식

Slow Start는 아래와 같이 동작한다.

• 연결이 시작되면 혼잡 윈도우$_{cwnd}$를 1MSS로 설정한다.
• 매 ACK를 받을 때마다 혼잡 윈도우를 1MSS씩 증가시킨다.
• 이렇게 하면 매 RTT$_{Round \space Trip \space Time}$마다 혼잡 윈도우가 2배로 증가한다.

 

이러한 지수적 증가는 다음과 같이 진행된다.

• 첫 RTT에서 1개의 세그먼트 전송
• 두 번째 RTT에서 2개의 세그먼트 전송
• 세 번째 RTT에서 4개의 세그먼트 전송
• 네 번째 RTT에서 8개의 세그먼트 전송

 

이런 식으로 cwnd가 1, 2, 4, 8, 16... 으로 증가하는 것을 볼 수 있다.

 

Slow Start 임계값(ssthresh)

TCP는 Slow Start를 계속 진행하면서 언제까지 지수적으로 증가시킬지 결정해야 한다. 이를 위해 ssthresh$_{slow \space start \space threshold}$라는 값을 사용한다.

 

초기에 ssthresh는 보통 큰 값으로 설정되어 있다(예: 65KB). cwnd가 ssthresh에 도달하면 TCP는 Slow Start 단계를 종료하고 'Congestion Avoidance' 단계로 전환한다. 이 단계에서는 cwnd가 선형적으로(매 RTT마다 1MSS씩) 증가한다.

 

패킷 손실이 발생하면 ssthresh는 손실 발생 직전의 cwnd 값의 절반으로 재설정된다. 이는 네트워크 용량에 근접했다는 신호로 해석되기 때문이다.

 

📡 Congestion Avoidance

Congestion Avoidance(혼잡 회피)는 TCP가 네트워크 congestion에 가까워졌다고 판단했을 때, 데이터를 조금 더 조심스럽게 보내기 시작하는 단계다. 전송 속도를 급격히 늘리는 대신 상황을 보며 천천히 증가시키는 방식을 취한다. 일반적으로 Slow Start 과정에서 cwnd가 ssthresh에 도달했을 때 시작된다.

 

Congestion Avoidance 단계에 진입할 때 cwnd는 대개 이전에 혼잡이 감지되었을 때의 값의 약 절반으로 네트워크가 다시 혼잡 상태에 빠질 위험이 있다는 것을 의미한다. 따라서 TCP는 Slow Start의 지수적 증가 방식보다 더 보수적인 접근법을 취하고, RTT마다 cwnd를 1 MSS만큼만 증가시킨다.

 

동작 원리

Congestion Avoidance 단계에서 cwnd는 다음과 같이 증가한다.

1. 새로운 ACK가 도착할 때마다 cwnd를 MSS × (MSS/cwnd) 바이트만큼 증가시킨다.
2. 이러한 방식으로 하나의 RTT 동안 모든 세그먼트의 ACK를 받으면 cwnd는 정확히 1 MSS만큼 증가하게 된다.

 

예를 들어, MSS가 1,460바이트이고 cwnd가 14,600바이트라면 이 시점에 송신자는 한 번에 10개의 세그먼트를 보낼 수 있다. 이때 각 ACK가 올 때마다 cwnd는 1/10 MSS씩 늘어나고, 결국 한 RTT가 끝나면 1 MSS만큼 증가하게 된다.

 

각 ACK가 도착할 때마다 cwnd는 1/10 MSS만큼 증가하고, 10개의 세그먼트에 대한 모든 ACK가 도착하면 cwnd는 총 1 MSS만큼 증가한 상태가 된다.

 

종료 조건

Congestion Avoidance의 선형적 증가는 언제 끝나야 할까? TCP는 패킷 손실이 감지될 때까지 이 과정을 계속한다. 패킷 손실은 두 가지 방식으로 감지될 수 있다.

 

• 타임아웃 발생 시
  • Slow Start에서와 마찬가지로 cwnd를 1 MSS로 설정하고, ssthresh를 손실 발생 시점의 cwnd의 절반으로 업데이트한다. 그리고 Slow Start 단계로 돌아간다.
• 3중복 ACK 발생 시
  • 이 경우 네트워크는 여전히 일부 세그먼트를 전달하고 있는 상태이므로, 타임아웃보다 덜 급격한 대응이 필요하다. cwnd를 절반으로 줄이고 (3 MSS를 더해 3중복 ACK를 고려), ssthresh를 3중복 ACK 발생 시점의 cwnd의 절반으로 설정한다. 그런 다음 Fast Recovery 단계로 진입한다.

 

📡 Fast Recovery

Fast Recovery는 TCP가 네트워크 congestion을 효율적으로 제어하기 위해 도입한 기법이다. 기존의 TCP Tahoe는 패킷 손실을 발견하면 항상 cwnd를 1 MSS로 리셋하고 Slow Start부터 다시 시작했기 때문에, 네트워크 상태가 나쁘지 않아도 성능을 크게 낮추는 단점이 있었다.

 

이를 보완하기 위해 TCP Reno는 3중복 ACK을 통해 발생한 손실에 대해 더 정교하게 대응하는 Fast Recovery 알고리즘을 도입했다.

 

동작 원리

Fast Recovery는 3중복 ACK로 패킷 손실이 감지되었을 때 아래와 같이 동작한다.

• 손실이 감지되면 ssthresh를 cwnd / 2로 설정한다.
• 손실된 세그먼트를 재전송한다.
• cwnd를 ssthresh + 3 MSS로 설정한다.
  • 3개의 중복 ACK가 도착한 만큼은 이미 수신자에 도달했으므로 그만큼 보내는 건 허용한다.
• 이후 중복 ACK마다 cwnd를 1 MSS씩 증가시킨다.
  • 약간씩 전송량을 늘리며 네트워크 상황을 탐색한다.
• 손실된 세그먼트에 대한 새로운 ACK를 받으면,
  • cwnd를 ssthresh 값으로 설정하고 Congestion Avoidance 단계로 전환한다.

 

TCP Tahoe vs. TCP Reno

TCP Tahoe와 Reno는 패킷 손실에 어떻게 반응하는가에서 가장 큰 차이를 보인다.

 

구분	TCP Tahoe	TCP Reno
손실 감지 방식	타임아웃, 3중복 ACK 동일 처리	감지 방식에 따라 다르게 대응
대응 방식	항상 cwnd = 1 MSS, Slow Start로 리셋	3중복 ACK 시 Fast Recovery, 타임아웃 시만 Slow Start
회복 속도	느림 (지수 증가)	빠름 (선형 증가 유지)
성능 특성	매우 보수적	실용적, 대부분의 시스템에서 채택됨

 

TCP CUBIC의 배경과 필요성

TCP Reno의 Fast Recovery는 일정 수준의 손실에는 잘 대응했지만, 초고속 네트워크나 장거리 대역폭 환경에서는 여전히 너무 보수적이었다. 예를 들어, 손실이 한 번 발생했다고 해서 갑자기 전송 속도를 반토막 내는 건 자원 낭비일 수 있다.

 

이런 문제를 해결하기 위해 등장한 것이 TCP CUBIC이다. 이름처럼 cwnd 크기를 세제곱 함수(cubic) 형태로 증가시키는 알고리즘이다.

 

CUBIC 동작 원리

TCP CUBIC은 TCP Reno와 크게 다르지 않다. ACK 수신 시에만 혼잡 윈도우를 증가시키며, Slow Start와 Fast Recovery 단계는 동일하게 유지된다.

 

CUBIC은 오직 Congestion Avoidance 단계만 다음과 같이 변경한다.

 

• 마지막으로 손실이 발생한 시점의 cwnd를 $W_{max}$라고 한다.
• 시간 $t$이 흐를수록 cwnd를 점점 키워간다.
  • 단, $W_{max}$에 가까워질수록 증가 속도를 줄이고,
  • $W_{max}$보다 훨씬 멀어진 시점에는 다시 과감히 증가

쉽게 말하면 예전에 손실이 있었던 곳 근처에서는 조심히 올리고, 그 외에는 과감하게 속도를 올려본다.

 

전체적으로 Fast Recovery 알고리즘을 정리하면 아래와 같다.

 

알고리즘	손실 대응	속도 회복	특징
Tahoe	무조건 cwnd = 1 MSS, Slow Start로 리셋	느림	매우 보수적, 단순
Reno	3중복 ACK → Fast Recovery	적절히 빠름	대부분의 OS에서 기본
CUBIC	세제곱 함수 기반 증가	매우 빠름	대역폭 큰 환경에 최적

 

📡 TCP Congestion control의 상태 머신(FSM)

TCP congestion control는 전체 동작을 세 가지 주요 상태(Slow Start, Congestion Avoidance, Fast Recovery)로 나누어 설명할 수 있다. 이들은 서로 연결된 유한 상태 머신(Finite State Machine, FSM)처럼 작동해 각 상태가 네트워크의 반응에 따라 전환된다.

1. 초기 상태
   • cwnd는 1 MSS로 시작하고, TCP는 Slow Start 단계로 진입한다.
2. Slow Start
   • 매 RTT마다 cwnd가 2배씩 증가
   • 혼잡 신호 감지 전까지 지수적 증가
   • cwnd ≥ ssthresh → Congestion Avoidance로 전환
3. Congestion Avoidance
   • cwnd는 선형적으로 증가 (1 MSS씩)
   • 3중복 ACK 발생 → Fast Recovery
   • 타임아웃 발생 → Slow Start
4. Fast Recovery
   • 손실 세그먼트 재전송 후 cwnd 증가 유지
   • 새로운 ACK 수신 시 → Congestion Avoidance로 복귀
   • 타임아웃 시 → Slow Start로 리셋

아래처럼 표로 요약해볼 수 있다.

 

상태	이벤트	동작	전이
Slow Start	ACK 수신	cwnd += 1 MSS	유지
	cwnd ≥ ssthresh		→ Congestion Avoidance
	3중복 ACK	ssthresh = cwnd/2, cwnd = ssthresh + 3×MSS	→ Fast Recovery
	타임아웃	ssthresh = cwnd/2, cwnd = 1 MSS	유지
Congestion Avoidance	ACK 수신	cwnd += MSS×(MSS/cwnd)	유지
	3중복 ACK	ssthresh = cwnd/2, cwnd = ssthresh + 3×MSS	→ Fast Recovery
	타임아웃	ssthresh = cwnd/2, cwnd = 1 MSS	→ Slow Start
Fast Recovery	중복 ACK	cwnd += 1 MSS	유지
	새로운 ACK	cwnd = ssthresh	→ Congestion Avoidance
	타임아웃	ssthresh = cwnd/2, cwnd = 1 MSS	→ Slow Start

 

references

Computer Networking: A Top-Down Approach, 8th edition

COMP0414 수업 내용