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는 데이터를 보낼 때 다음 조건을 만족해야 한다.

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

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

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

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

이렇게 AIMD는 TCP의 전체 congestion control 방식에서의 기본 원리로 생각하면 된다. 하지만, TCP는 연결이 처음 시작될 때부터 congestion control까지 여러 단계로 혼잡 상황에 대응한다. 대표적으로 Slow Start, Congestion Avoidance, Fast Retransmit, 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 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 알고리즘을 정리하면 아래와 같다.

📡 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로 리셋

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

📡 지연 기반 TCP 혼잡 제어

전통적인 TCP 혼잡 제어는 패킷 손실을 혼잡의 신호로 사용했다. 하지만 이 방식은 혼잡이 이미 심각한 수준에 도달했을 때만 반응한다는 한계가 있다. 이를 보완하기 위해 '지연 기반 혼잡 제어' 방식이 등장했다.

지연 기반 접근법은 RTT의 변화를 통해 네트워크 상태를 추론한다. 먼저 네트워크가 혼잡하지 않은 상태에서의 최소 RTT$_{RTTmin}$를 측정한다. 그리고 현재 측정된 RTT가 RTTmin보다 현저히 증가하면 패킷이 라우터 큐에서 대기하고 있다는 신호이므로 혼잡이 시작되고 있다고 판단한다. 이를 바탕으로 패킷 손실이 발생하기 전에 미리 혼잡 윈도우를 조정해 혼잡을 완화하고 큐잉 지연을 최소화한다.

지연 기반 TCP 혼잡 제어는 패킷 손실을 일으키지 않고도 네트워크 혼잡을 관리하는 방식이다. 이 접근법의 아이디어는 패킷 손실이 발생하기 전에 네트워크 혼잡 상태를 감지하고 대응하는 것이다.

전통적인 TCP 혼잡 제어는 패킷 손실이 발생해야만 네트워크가 혼잡하다고 판단한다. 그러나 이미 패킷 손실이 발생했다는 것은 네트워크가 이미 심각하게 혼잡해졌다는 의미다. 반면, 지연 기반 접근법은 RTT$_{Round \space Trip \space Time}$의 증가를 감지해 혼잡 상태를 예측한다.

이 방식의 목표는 네트워크 파이프를 "꽉 차게 유지하되, 넘치지 않게" 하는 것이다. 즉, 네트워크 처리량을 최대화하면서도 지연 시간을 낮게 유지하는 균형점을 찾는 것이다. 이상적으로는 병목 링크가 항상 데이터를 전송 중이지만, 큰 대기열이 형성되지 않는 상태를 유지한다.

현재 여러 TCP 구현체들이 이러한 지연 기반 접근법을 채택하고 있다. 그 중에서도 특히 주목할 만한 것은 Google이 자사의 내부 백본 네트워크에 배포한 BBR$_{Bottleneck \space Bandwidth \space and \space Round-trip \space propagation \space time}$다.

BBR은 네트워크의 병목 대역폭과 최소 RTT를 추정해 최적의 전송 속도를 결정한다. BBR은 패킷 손실을 혼잡의 신호로 사용하지 않고, 대신 측정된 전송 속도와 지연 시간의 변화를 관찰한다. 이 접근법은 손실이 많은 무선 네트워크나 버퍼가 큰 네트워크(bufferbloat 현상이 있는 네트워크)에서 좋은 성능을 보인다.

TCP 통신에서는 네트워크 지원 혼잡 제어를 구현하는데, 이것이 명시적 혼잡 알림(ECN)이다. ECN은 네트워크가 혼잡해지면 명시적으로 알려주는 메커니즘이다.

작동 방식은 아래와 같다.

• IP 헤더의 ToS$_{Type \space of \space Service}$ 필드에 있는 2개의 비트가 네트워크 라우터에 의해 표시된다. 라우터는 자신의 버퍼가 차고 있거나 혼잡이 예상될 때 이 비트를 설정한다. 어떤 기준으로 혼잡을 판단하고 표시할지는 네트워크 운영자가 결정한다.
• 이렇게 표시된 혼잡 정보는 IP 데이터그램을 통해 목적지까지 전달된다. 처음에는 ECN=10으로 표시되었다가, 혼잡이 감지되면 라우터가 ECN=11로 변경한다.
• 목적지에 도착하면, 수신 측 TCP는 이 혼잡 표시를 확인하고 다시 송신자에게 알려야 한다. 이를 위해 TCP ACK 세그먼트의 ECE(ECN-Echo) 비트를 1로 설정한다.
• 송신자는 이 ECE=1이 설정된 ACK를 받으면 네트워크에 혼잡이 발생했음을 인식하고, 혼잡 제어 알고리즘을 실행해 전송 속도를 줄인다.
• 이 메커니즘의 장점은 패킷 손실이 발생하기 전에 혼잡을 감지하고 대응할 수 있다는 점이다. 전통적인 TCP는 패킷 손실이 발생해야만 혼잡을 감지했지만, ECN을 사용하면 패킷 손실 없이도 혼잡 제어가 가능하다.
• ECN은 IP와 TCP 프로토콜 모두의 협력이 필요하다. IP 헤더의 비트를 통해 혼잡을 표시하고, TCP 헤더의 비트를 통해 이 정보를 다시 송신자에게 전달한다.

📡 진화하는 전송 계층 기능

TCP와 UDP는 지난 40년간 인터넷의 주요 전송 프로토콜로 사용되어 왔다. 하지만 네트워크 환경과 요구사항이 다양해짐에 따라 전송 계층도 계속 진화해왔다.

다양한 시나리오에 맞춰 여러 ‘종류’의 TCP가 개발되었다.

• 대용량 데이터 전송을 위한 long, fat pipe
  • 많은 패킷이 동시에 전송 중일 때 하나의 패킷 손실이 발생하면 전체 파이프라인이 중단되는 문제가 있다.
  • 이를 위해 큰 윈도우 크기와 효율적인 복구 메커니즘을 갖춘 TCP 변형이 개발되었다.
• 무선 네트워크
  • 무선 링크의 노이즈나 모바일 기기의 이동으로 인한 패킷 손실이 발생한다.
  • TCP는 이러한 손실을 혼잡으로 오인해 불필요하게 전송 속도를 줄이는 문제가 있다.
  • 무선 환경에 최적화된 TCP 변형은 이런 환경에서의 손실을 구분해 처리한다.
• long-delay links
  • 위성 통신과 같이 RTT가 매우 긴 경우, 기존 TCP의 느린 시작과 혼잡 제어 알고리즘이 성능을 크게 저하시킨다.
  • 이런 환경을 위한 TCP 변형은 긴 RTT에 더 효과적으로 대응한다.
• 데이터센터 네트워크
  • 지연에 매우 민감한 환경으로, 밀리초 단위의 지연도 중요하다.
  • 데이터 센터에 최적화된 TCP는 빠른 응답 시간과 높은 처리량을 모두 제공하도록 설계되었다.
• 백그라운드 트래픽 flows
  • 사용자 경험에 직접적인 영향을 주지 않는 낮은 우선순위의 트래픽을 위한 TCP 변형이다.
  • 이런 TCP는 다른 중요한 트래픽에 영향을 최소화하면서 남은 대역폭을 활용한다.

최근에는 전송 계층의 기능을 애플리케이션 계층으로 이동시키는 경향도 있다. 특히 UDP 위에서 구현된 HTTP/3의 QUIC(Quick UDP Internet Connections) 프로토콜이 대표적이다. QUIC은 UDP를 기반으로 하면서도 TCP와 유사한 신뢰성과 혼잡 제어를 제공한다. 동시에 연결 설정 시간을 줄이고 헤드 오브 라인 차단 문제를 해결하는 등의 장점을 제공한다.

QUIC

QUIC은 UDP를 기반으로 하는 애플리케이션 계층 프로토콜로, HTTP의 성능을 향상시키기 위해 설계되었다. Google에서 개발한 이 프로토콜은 현재 많은 Google 서버와 애플리케이션(Chrome 브라우저, 모바일 YouTube 앱 등)에서 널리 사용되며 HTTP/3의 기반 기술이 되었다.

QUIC은 앞서 학습한 연결 설정, 오류 제어, 혼잡 제어 등의 접근 방식을 도입했다.

• 오류 및 혼잡 제어
  • QUIC 명세에 따르면, ‘TCP의 손실 감지 및 혼잡 제어에 익숙한 독자들은 여기서 잘 알려진 TCP 알고리즘과 유사한 알고리즘을 발견할 것입니다.’라 되어 있다.
• 연결 설정
  • 신뢰성, 혼잡 제어, 인증, 암호화 등의 상태를 단 하나의 RTT$_{Round \space Trip \space Time}$로 설정한다.
• 다중 스트림
  • 단일 QUIC 연결을 통해 여러 애플리케이션 수준의 "스트림"을 다중화한다.
  • 개별 스트림은 독립적인 신뢰성 있는 데이터 전송과 보안을 제공한다.
  • 모든 스트림이 공통의 혼잡 제어를 사용한다.

QUIC의 연결 설정 비교

기존 TCP+TLS 방식

• TCP 핸드셰이크 (전송 계층)
• TLS 핸드셰이크 (보안)
  • 두 개의 직렬 핸드셰이크가 필요하다.
  • TCP(신뢰성, 혼잡 제어 상태) + TLS(인증, 암호화 상태) 설정에 총 2-3 RTT가 소요된다.

QUIC 방식

• QUIC 핸드셰이크
  • 단 하나의 핸드셰이크로 충분하다.
  • 신뢰성, 혼잡 제어, 인증, 암호화 상태를 모두 1 RTT 내에 설정한다.
  • 이전에 연결했던 서버에 재연결할 경우 0-RTT로 즉시 데이터 전송이 가능하다.

QUIC 스트림: 병렬성 및 HOL 차단 방지

TCP는 모든 데이터를 단일 바이트 스트림으로 처리하기 때문에, 하나의 패킷이 손실되면 그 뒤의 모든 데이터 전송이 일시 중단된다. 이것을 Head-of-Line(HOL) 차단이라고 한다.

QUIC은 여러 스트림을 독립적으로 처리한다.

• 각 HTTP 요청은 별도의 QUIC 스트림으로 처리된다.
• 하나의 스트림에서 오류가 발생해도 다른 스트림은 계속 데이터를 주고받을 수 있다.
• 단일 연결 내에서 여러 스트림의 병렬 처리가 가능하다.
• 모든 스트림이 공통된 혼잡 제어를 사용하면서도 각각 독립적인 오류 복구를 수행한다.

이러한 특성 덕분에 QUIC은 패킷 손실이 발생하더라도 전체 연결의 처리량을 최대한 유지할 수 있고 웹 페이지 로딩 시간을 크게 단축시킬 수 있다.

references

• Computer Networking: A Top-Down Approach, 8th edition
• COMP0414 수업 내용