슬로우 스타트 알고리즘 (r1)

혼잡 윈도우(Congestion Window, cwnd)는 송신자가 수신자의 ACK 확인응답을 기다리지 않고 한 번에 전송할 수 있는 최대 데이터 양을 제어하는 변수이다. 슬로우 스타트 단계에서 이 윈도우는 매우 작은 값으로 초기화되며, 일반적으로 1, 2 또는 10개의 세그먼트(MSS) 크기로 시작한다[4].

혼잡 윈도우의 확장은 ACK 패킷 수신에 의해 주도된다. 기본 규칙은 매번 정상적인 ACK 하나를 받을 때마다 혼잡 윈도우 크기를 1 MSS만큼 증가시키는 것이다. 이는 실제로 지수적 성장을 유발한다. 왜냐하면 한 RTT(왕복 시간) 동안 모든 전송된 패킷에 대한 ACK가 도착하면, 그 RTT가 끝날 때 혼잡 윈드우 크기가 거의 두 배로 증가하기 때문이다. 예를 들어, 초기 cwnd가 1 MSS라면 첫 RTT 후 2 MSS, 다음 RTT 후 4 MSS, 그 다음에는 8 MSS로 증가한다.

이 지수적 증가는 네트워크의 사용 가능한 대역폭을 빠르게 탐색하고 활용하는 데 목적이 있다. 송신자는 네트워크에 과부하를 주지 않으면서 가능한 한 빨리 최적의 전송 속도에 도달하려고 한다. 아래 표는 초기 cwnd를 1 MSS로 가정한 지수적 확장의 예를 보여준다.

이 과정은 세 가지 조건 중 하나가 발생할 때까지 계속된다: 1) 슬로우 스타트 임계값(ssthresh)에 도달하여 혼잡 회피 단계로 전환될 때, 2) 패킷 손실이 감지되어 타임아웃이 발생하거나 3개의 중복 ACK가 수신될 때, 3) 수신자의 광고된 윈도우(Advertised Window)에 의해 흐름 제어가 선제적으로 제한될 때.

슬로우 스타트 임계값은 혼잡 윈도우의 성장 방식을 제어하는 핵심 매개변수이다. 이 값은 일반적으로 ssthresh로 표기되며, 혼잡 제어 알고리즘이 슬로우 스타트 단계에서 혼잡 회피 단계로 전환되는 시점을 결정한다. 초기 ssthresh 값은 임의로 큰 값(예: 65,535 바이트)으로 설정되거나, 이전 연결의 정보를 기반으로 동적으로 설정될 수 있다.

cwnd가 ssthresh 값보다 작을 때는 슼로우 스타트 단계가 활성화되어, 매 왕복 지연 시간마다 cwnd가 지수적으로 증가한다. cwnd가 ssthresh에 도달하거나 초과하면, 알고리즘은 혼잡 회피 단계로 전환된다. 이 단계에서는 cwnd의 성장 속도가 선형적으로 감소하여 네트워크의 혼잡을 더 신중하게 피하려고 시도한다.

패킷 손실이 발생하면, ssthresh 값은 현재 네트워크 상태를 반영하도록 갱신된다. 대부분의 구현에서는 ssthresh를 손실 발생 시점의 cwnd 값의 절반(일반적으로 cwnd/2)으로 설정한다. 이 조정은 네트워크가 수용할 수 있는 대역폭의 추정치를 낮추고, 이후의 공격적인 윈도우 확장을 억제하는 역할을 한다. 갱신된 후, cwnd는 작은 값(보통 1 또는 2 최대 세그먼트 크기)으로 재설정되고, 다시 슼로우 스타트 단계부터 ssthresh를 향해 성장하기 시작한다.

이 메커니즘을 통해 ssthresh는 네트워크의 과거 혼잡 이력을 기록하고, 이를 바탕으로 연결의 공격성을 동적으로 조절하는 지표 역할을 한다.

패킷 손실은 네트워크 혼잡의 주요 지표로 간주되며, 슬로우 스타트 알고리즘이 혼잡 회피 단계로 전환되는 결정적 계기가 된다. TCP는 일반적으로 세 번의 중복 ACK 수신 또는 재전송 타임아웃 발생을 패킷 손실로 판단한다. 이는 네트워크가 현재의 데이터 전송 속도를 더 이상 수용하지 못하고 있음을 의미하며, 송신 측은 즉각적인 전송 속도 조절을 시작한다.

패킷 손실이 감지되면, 슬로우 스타트 임계값이 현재 혼잡 윈도우 크기의 절반으로 조정된다. 이는 네트워크가 안정적으로 수용할 수 있는 것으로 추정되는 새로운 상한선을 설정하는 과정이다. 동시에, 혼잡 윈도우 자체는 1 또는 2개의 MSS 크기로 줄어든다. 이후 알고리즘은 지수적 증가를 중단하고, 혼잡 회피 단계로 진입하여 혼잡 윈도우를 선형적으로 증가시킨다. 이 전환은 네트워크의 혼잡 상태를 벗어나 최대 처리량에 근접하면서도 안정적으로 운영하기 위한 핵심 메커니즘이다.

구체적인 전환 방식은 사용되는 TCP 혼잡 제어 알고리즘의 변종에 따라 차이가 있다. 예를 들어, TCP Tahoe는 패킷 손실 시 혼잡 윈도우를 1로 재설정하고 슬로우 스타트부터 다시 시작한다. 반면, TCP Reno는 빠른 회복 알고리즘을 도입하여, 중복 ACK에 의한 패킷 손실 시 혼잡 윈도우를 절반으로 줄인 후 즉시 혼잡 회피 단계로 진입함으로써 성능 저하를 완화한다. 재전송 타임아웃이 발생하는 경우 두 알고리즘 모두 혼잡 윈도우를 1로 재설정하고 슬로우 스타트를 재개한다.

TCP Tahoe와 TCP Reno는 슬로우 스타트 및 혼잡 회피 메커니즘을 구현한 초기 TCP 혼잡 제어 알고리즘이다. 두 알고리즘은 패킷 손실을 감지하고 대응하는 방식에서 근본적인 차이를 보이며, 이는 혼잡 윈도우를 관리하는 전략에 직접적인 영향을 미친다.

주요 차이는 타임아웃 또는 중복 ACK에 의한 패킷 손실 감지 후의 동작에 있다. TCP Tahoe는 손실이 발생하면, 그 원인과 관계없이 항상 혼잡 윈도우(cwnd)를 1 MSS(Maximum Segment Size)로 줄이고 슬로우 스타트 단계로 되돌아간다. 또한 슬로우 스타트 임계값(ssthresh)을 현재 혼잡 윈도우의 절반으로 설정한다. 이는 네트워크에 심각한 혼잡이 발생했다고 가정하고 매우 보수적으로 대응하는 방식이다. 반면, TCP Reno는 "Fast Recovery"라는 추가적인 상태를 도입하여 중복 ACK에 의한 손실(일반적으로 단일 패킷 손실로 간주)과 타임아웃에 의한 손실을 구분하여 처리한다.

구체적인 동작 차이는 다음 표와 같다.

결과적으로, TCP Reno는 단일 패킷 손실 시 혼잡 윈도우를 1로 초기화하지 않고 절반으로만 줄인 후 선형 증가하는 혼잡 회피 단계로 바로 진입할 수 있다. 이로 인해 중복 ACK로 인한 일시적인 손실에서 TCP Tahoe보다 빠르게 성능을 회복하는 장점이 있다. 그러나 여러 패킷이 한 번에 손실되는 경우에는 Fast Recovery 메커니즘이 제대로 동작하지 않아 타임아웃이 발생할 수 있으며, 결국 Tahoe와 유사한 성능 저하를 겪게 된다.

빠른 재전송은 TCP가 세그먼트 손실을 감지하는 전통적인 방법인 재전송 타임아웃을 기다리지 않고, 더 신속하게 대응할 수 있게 해주는 메커니즘이다. 이 메커니즘은 수신 측에서 순서가 잘못된 세그먼트를 받을 때마다 중복 ACK를 보내는 동작에 기반한다. 송신 측이 동일한 시퀀스 번호에 대한 중복 ACK를 연속적으로 세 번 받으면, 해당 세그먼트가 손실되었다고 판단하고 타임아웃이 만료되기 전에 즉시 재전송을 시작한다.

슬로우 스타트 알고리즘은 빠른 재전송이 발생했을 때 그 동작 방식이 달라진다. 대표적인 TCP 혼잡 제어 구현체인 TCP Reno에서는 빠른 재전송이 트리거되면, 알고리즘이 즉시 혼잡 회피 단계로 진입한다. 이때의 핵심 동작은 다음과 같다.

1. 현재 혼잡 윈도우 크기의 절반을 새로운 슬로우 스타트 임계값으로 설정한다.

2. 슬로우 스타트 임계값으로 설정된 이 새로운 값으로 혼잡 윈도우 크기를 조정한다.

3. 이후부터는 혼잡 회피 알고리즘(일반적으로 가산 증가)을 사용하여 윈도우를 확장한다.

이 상호작용의 결과, 네트워크는 슬로우 스타트의 지수적 증가 단계에서 벗어나 선형적으로 더 조심스럽게 대역폭을 활용하게 된다. 이는 빠른 재전송이 단순한 패킷 손실 복구를 넘어, 네트워크 혼잡의 초기 징후로 해석되어 혼잡 제어 정책을 더 보수적으로 전환하는 계기가 된다는 점을 의미한다. 반면, TCP Tahoe 구현에서는 빠른 재전송 후에도 혼잡 윈도우를 1로 줄이고 슬로우 스타트를 다시 시작하여 Reno에 비해 더 공격적인 성능 저하를 보인다.

슬로우 스타트 알고리즘의 핵심 목표는 혼잡 제어를 시작하는 시점에 네트워크의 사용 가능한 대역폭을 가능한 한 빠르게 탐색하는 것이다. 연결이 맺어진 직후, 송신자는 네트워크의 현재 상태에 대한 정보를 거의 가지고 있지 않다. 이때 보수적으로 작은 혼잡 윈도우 크기(예: 1 또는 2개의 MSS)로 데이터 전송을 시작하면, 네트워크 자원을 효율적으로 활용하지 못하고 성능이 저하된다. 슬로우 스타트는 이러한 초기 탐색 단계에서 혼잡 윈도우를 지수 함수적으로 증가시켜, 짧은 시간 내에 링크의 용량에 근접한 전송 속도를 달성하도록 설계되었다.

구체적인 동작 방식은 다음과 같다. 송신자는 매 RTT마다 혼잡 윈도우 크기를 두 배로 증가시킨다. 이는 각 전송된 패킷에 대한 ACK 확인응답을 수신할 때마다 윈도우를 1씩 증가시키는 방식으로 구현된다. 예를 들어, 초기 혼잡 윈도우가 2개 패킷이라면, 첫 번째 RTT 동안 2개 패킷을 보내고 이들의 ACK를 받으면 윈도우는 4가 된다. 다음 RTT에는 4개 패킷을 보낼 수 있으며, 그 ACK를 모두 받으면 윈도우는 8이 된다. 이 지수적 성장은 네트워크에 남아 있는 여유 대역폭이 충분하다고 가정할 때, 매우 빠르게 대역폭을 포화 상태로 만든다.

이러한 빠른 탐색 메커니즘은 특히 짧은 연결이나 파일 전송에서 유리하다. 대역폭이 충분한 네트워크에서는 몇 번의 RTT 안에 최적의 전송 속도에 도달하여 전체 전송 시간을 크게 단축시킨다. 또한, 네트워크가 비어 있는 상태에서 새로운 연결이 시작될 경우, 유휴 상태의 네트워크 자원을 신속하게 활용할 수 있게 한다. 이는 TCP의 공정성과 효율성을 동시에 추구하는 혼잡 제어 정책의 중요한 첫 단계를 구성한다.

슬로우 스타트 알고리즘은 혼잡 윈도우를 지수적으로 증가시켜 사용 가능한 네트워크 대역폭을 빠르게 탐색하도록 설계되었다. 그러나 이 방식은 대역폭-지연 곱이 큰 네트워크 환경에서는 비효율적이고 긴 연결 설정 시간을 초래하는 한계를 보인다.

BDP가 큰 네트워크는 사용 가능한 대역폭이 넓고 왕복 지연 시간이 길다는 특징을 가진다. 슬로우 스타트는 혼잡 윈도우를 패킷 손실이 발생할 때까지 매 RTT마다 두 배로 증가시킨다. 따라서 링크를 완전히 포화시켜 최대 처리량에 도달하기 위해서는 필요한 윈도우 크기까지 여러 번의 RTT가 소요된다. 예를 들어, 초기 혼잡 윈도우가 10개 패킷이고 목표 윈도우 크기가 1000개 패킷이라면, 이를 채우기 위해서는 약 7번의 RTT(2^7=128)가 필요하다. RTT가 100ms인 경우, 이는 700ms의 지연을 의미하며, 이 시간 동안 링크는 낮은 활용률을 보인다.

이러한 한계는 특히 장거리 해저 광케이블이나 위성 링크와 같은 고지연 환경에서 두드러진다. 짧은 파일 전송이나 HTTP 트랜잭션과 같은 단시간 연결에서는 슬로우 스타트 단계가 끝나기도 전에 데이터 전송이 완료될 수 있어, 네트워크의 실제 용량을 전혀 활용하지 못하는 결과를 낳는다. 또한, 슬로우 스타트는 혼잡을 탐지하는 유일한 신호로 패킷 손실에 의존한다. 고대역폭 환경에서 손실이 발생하면 이미 많은 양의 데이터가 큐에 쌓여 있을 가능성이 높아, 이후의 혼잡 회피 단계에서도 성능이 급격히 저하되는 현상을 초래할 수 있다.

이러한 문제점을 해결하기 위해 초기 혼잡 윈도우 값을 증가시키거나, TCP CUBIC이나 BBR과 같이 대역폭과 지연을 보다 적극적으로 측정하여 슬로우 스타트 단계를 보완하거나 대체하는 새로운 혼잡 제어 알고리즘이 제안되고 채택되었다.

TCP BIC는 2004년에 제안된 알고리즘으로, 고대역폭-고지연 네트워크에서 슬로우 스타트 및 혼잡 회피의 선형적 증가 방식이 링크 용량을 효율적으로 활용하지 못하는 문제를 해결하기 위해 개발되었다. 핵심 아이디어는 패킷 손실을 혼잡의 이진 신호로 간주하고, 손실이 발생한 윈도우 크기와 손실 직전의 윈도우 크기의 중간값을 새로운 목표로 삼는 것이다. 이는 손실이 발생한 시점의 네트워크 상태를 근거로 윈도우 크기를 조정하는 방식으로, 기하급수적 증가와 선형 증가 사이를 효율적으로 탐색한다. BIC는 특히 장거리 고속 네트워크에서 기존 TCP Reno보다 우수한 확장성을 보였다.

그러나 BIC는 윈도우 크기 조정 시 공격적으로 증가하는 구간이 존재하여 RTT가 서로 다른 여러 TCP 연결 간의 공정성 문제를 야기할 수 있었다. 이 문제를 해결하기 위해 등장한 것이 TCP CUBIC이다. CUBIC는 2008년에 제안되었으며, BIC의 핵심 논리를 유지하되, 윈도우 증가 함수를 3차 함수(큐빅 함수)로 단순화했다. 증가 함수는 시간의 3차 함수로 표현되며, 마지막으로 패킷 손실이 발생한 시점을 함수의 중심으로 설정한다. 이 방식은 RTT에 독립적으로 동작하므로, 다양한 지연 시간을 가진 흐름 간의 공정성을 크게 향상시킨다.

CUBIC의 동작은 다음과 같은 특징을 가진다.

• 3차 함수 기반 증가: 윈도우 크기 W(t) = C*(t-K)³ + W_max 공식을 사용한다. 여기서 C는 스케일링 상수, t는 마지막 손실로부터의 경과 시간, K는 윈도우 크기가 W_max에 도달하는 데 걸리는 시간의 추정치, W_max는 마지막 손실 발생 시의 윈도우 크기이다.

• 충분히 빠른 탐색: 네트워크 용량이 갑자기 증가한 경우, 함수의 볼록한 부분을 통해 빠르게 대역폭을 탐색한다.

• 점근적 성장: 윈도우가 W_max에 가까워지면 함수의 오목한 부분으로 인해 증가 속도가 느려져 네트워크를 안정적으로 유지한다.

CUBIC는 그 우수한 확장성과 공정성으로 인해 리눅스 운영체제의 기본 TCP 혼잡 제어 알고리즘으로 채택되었으며, 현재까지도 인터넷에서 가장 널리 사용되는 알고리즘 중 하나이다. 이는 기존의 TCP Reno가 가진 고대역폭-고지연 네트워크에서의 성능 한계를 극복하는 데 기여했다.

BBR(Bottleneck Bandwidth and Round-trip propagation time)은 구글이 2016년에 발표한 새로운 TCP 혼잡 제어 알고리즘이다. 기존의 슬로우 스타트 알고리즘 및 혼잡 회피를 포함한 대부분의 TCP 알고리즘이 패킷 손실을 혼잡의 주요 신호로 삼는 데 반해, BBR은 패킷 손실을 명시적인 혼잡 신호로 사용하지 않는다. 대신, 네트워크 경로의 실제 용량인 병목 대역폭(Bottleneck Bandwidth)과 왕복 지연 시간(RTT)을 지속적으로 측정하여 이 두 가지 파라미터의 곱인 BDP(Bandwidth-Delay Product)를 모델링한다. 이 모델을 바탕으로 데이터 전송 속도를 조절하여 대역폭을 최대한 활용하면서도 큐잉 지연을 최소화하는 것을 목표로 한다.

BBR의 핵심 동작은 네트워크 상태를 탐색하는 '상태 머신'에 기반한다. 주요 상태는 다음과 같다.

Startup 단계는 전통적인 슬로우 스타트와 유사하게 대역폭을 빠르게 찾지만, 목표는 손실 발생이 아닌 전송 속도 증가에 따른 RTT 증가율 변화를 감지하는 것이다. 일단 대역폭 증가가 정체되면 Drain 단계로 전환되어 네트워크 버퍼에 쌓인 패킷을 제거한다. 이후 대부분의 시간을 보내는 ProbeBW 단계에서는 대역폭 변동에 민첩하게 대응하기 위해 주기적으로 전송 속도를 높였다 낮추는 방식을 사용한다.

BBR은 고대역폭-고지연(LFN) 환경이나 패킷 손실이 빈번한 무선 네트워크에서 기존 손실 기반 혼잡 제어 알고리즘보다 더 높은 처리량과 더 낮은 지연을 보이는 경우가 많다. 또한, 네트워크 버퍼블로트 현상을 유발하지 않도록 설계되었다는 점이 큰 장점이다. 그러나 상대적으로 짧은 RTT를 가진 흐름과의 공정성 문제나, 갑작스러운 대역폭 감소에 대한 추종 속도 등이 개선 과제로 지적된다. BBR은 현재 구글의 내부 네트워크 및 유튜브, 구글 클라우드 등 여러 서비스에 적용되어 성능 향상을 이루었다.

슬로우 스타트 알고리즘은 HTTP를 통한 웹 페이지 로딩 성능에 직접적인 영향을 미친다. 웹 브라우저는 일반적으로 하나의 호스트에 대해 여러 개의 TCP 연결을 동시에 열어 여러 리소스를 병렬로 다운로드한다. 각 연결은 독립적인 슬로우 스타트 단계를 거치기 때문에, 작은 크기의 웹 객체(예: HTML, CSS, 작은 이미지 파일)를 전송하는 동안에는 연결이 최대 대역폭을 활용하지 못하고 종료될 수 있다. 이는 특히 지연 시간이 긴 네트워크에서 웹 페이지의 전체 로드 시간을 증가시키는 요인으로 작용한다[5].

이러한 문제를 완화하기 위해 TCP 초기 혼잡 윈도우 크기는 역사적으로 증가해 왔으며, 현대의 웹 브라우저와 서버는 TLS 핸드셰이크 과정에서 데이터 전송을 시작하는 TCP Fast Open 같은 최적화 기법을 지원하기도 한다. 또한, HTTP/2나 HTTP/3 프로토콜은 멀티플렉싱을 통해 단일 연결로 여러 스트림을 처리함으로써 슬로우 스타트의 빈번한 발생을 줄이는 효과를 낸다.

스트리밍 서비스, 특히 적응형 비트레이트 스트리밍을 사용하는 경우에도 슬로우 스타트는 중요한 고려 사항이다. 비디오 재생이 시작되기 전의 초기 버퍼링 시간은 클라이언트가 서버로부터 첫 번째 데이터 세그먼트를 다운로드하는 속도에 좌우된다. 슬로우 스타트 단계에서의 전송 속도는 느리게 증가하므로, 높은 비트레이트의 비디오 품질로 빠르게 전환하는 데 걸리는 시간이 길어질 수 있다. 많은 스트리밍 제공업체는 전 세계에 분산된 콘텐츠 전송 네트워크 서버를 활용하여 왕복 시간을 줄이고, 슬로우 스타트 기간의 성능 저하를 최소화한다.

데이터센터 네트워크는 짧은 왕복 시간과 높은 대역폭, 그리고 낮은 패킷 손실률을 특징으로 합니다. 이러한 환경에서 전통적인 슬로우 스타트 알고리즘은 링크 용량을 빠르게 탐색하는 장점이 있지만, 매우 짧은 흐름의 경우 연결이 종료될 때까지 혼잡 윈도우가 충분히 성장하지 못해 성능을 제한할 수 있습니다. 또한, 많은 수의 짧은 연결이 동시에 슬로우 스타트 단계에 진입하면 순간적인 버퍼 오버플로우와 미세한 혼잡을 유발할 수 있습니다.

이러한 문제를 해결하기 위해 데이터센터 특화 TCP 변형들이 개발되었습니다. TCP DCTCP는 ECN을 적극적으로 활용하여 네트워크 혼잡을 초기에 감지하고, 혼잡 윈도우를 더 세밀하게 조절합니다. TCP RAPID는 초기 혼잡 윈도우를 크게 설정하거나, 대역폭 지연 곱을 사전에 예측하는 방식으로 슬로우 스타트 단계를 사실상 우회하거나 단축합니다. 한편, Google의 BBR 알고리즘은 패킷 손실 대신 대역폭과 지연 시간을 직접 측정하여 혼잡을 제어하는 다른 접근법을 제시합니다.

다음은 데이터센터 환경에서의 주요 TCP 혼잡 제어 알고리즘 특징을 비교한 표입니다.

결론적으로, 데이터센터 내부 통신에서는 전통적인 패킷 손실 기반의 혼잡 신호가 비효율적일 수 있어, 슬로우 스타트의 동작을 수정하거나 대체하는 알고리즘이 표준 TCP Reno나 CUBIC보다 더 나은 성능을 보입니다. 이러한 최적화는 분산 파일 시스템, 키-값 저장소, 그리고 마이크로서비스 간의 RPC 호출과 같은 짧은 대기 시간이 요구되는 작업에 필수적입니다.