빠른 회복 알고리즘

혼잡 제어는 네트워크의 혼잡 붕괴를 방지하고 공정한 대역폭 분배를 달성하기 위한 핵심 메커니즘이다. 그 목표는 송신자가 네트워크 상태를 추정하여, 네트워크가 수용할 수 있는 최적의 데이터 전송률을 찾아내는 것이다. 이를 위해 혼잡 창이라는 변수를 사용하여 한 번에 전송할 수 있는 데이터 양을 동적으로 조절한다.

혼잡 제어의 기본 원리는 피드백 신호에 기반한다. 주요 피드백 신호는 패킷 손실이다. 패킷 손실은 일반적으로 라우터의 큐가 가득 차서 발생하는 것으로 간주되며, 이는 네트워크가 혼잡 상태임을 나타내는 지표로 사용된다. 또한, 지연 시간의 변화나 명시적 혼잡 통지 같은 추가 신호도 활용될 수 있다.

혼잡 제어 알고리즘은 일반적으로 두 가지 주요 단계로 구성된다. 첫 번째는 혼잡 회피 단계로, 네트워크가 혼잡 상태에 근접하지 않도록 서서히 전송률을 증가시키는 단계이다. 두 번째는 혼잡 발생 후의 대응 단계로, 패킷 손실과 같은 혼잡 신호를 감지하면 전송률을 급격히 줄여 네트워크의 혼잡을 완화한다. 이 증가와 감소의 정책이 전체적인 성능과 공정성을 결정한다.

AIMD는 혼잡 제어의 기본 원리로, 혼잡 윈도우 크기를 가법적으로 증가시키고 곱셈적으로 감소시키는 방식을 말한다. 네트워크에 패킷 손실이 발생하지 않으면 윈도우 크기를 1 MSS[1]씩 선형적으로 증가시킨다. 그러나 손실이 감지되면 윈도우 크기를 절반으로 줄인다. 이 방식은 공평성과 안정성을 보장하지만, 혼잡이 발생한 후 처리량이 급격히 떨어지는 문제가 있다.

반면, 빠른 회복 알고리즘은 AIMD의 곱셈적 감소 단계를 수정한 확장이다. 빠른 회복은 빠른 재전송 메커니즘에 의해 트리거되며, 단일 패킷 손실을 네트워크의 심각한 혼잡으로 간주하지 않는다. 대신, 윈도우 크기를 절반으로 줄인 후, 손실된 패킷이 재전송되고 승인될 때까지 윈도우 크기를 선형적으로 유지하거나 약간 증가시킨다. 이는 AIMD가 손실 직후 윈도우 크기를 절반으로 줄이고 느린 시작 단계부터 다시 시작하는 것과 대비된다.

두 접근법의 핵심 차이는 혼잡에 대한 반응과 이후의 회복 속도에 있다. 다음 표는 주요 차이점을 요약한다.

결론적으로, AIMD는 혼잡 제어의 보수적이고 안정적인 기본 골격을 제공하는 반면, 빠른 회복은 실제 네트워크에서 빈번히 발생하는 일시적 손실에 대한 과도한 반응을 완화하여 처리량과 응답성을 개선하는 실용적인 개선안이다.

혼잡 회피 단계는 TCP 연결이 혼잡 창 크기가 혼잡 임계값을 초과한 후 진입하는 상태이다. 이 단계의 주요 목표는 네트워크가 수용할 수 있는 최대 대역폭을 효율적으로 활용하면서도 패킷 손실을 유발하지 않는 선에서 전송 속도를 조절하는 것이다. 이는 네트워크의 공정성과 효율성을 동시에 달성하려는 시도이다.

이 단계에서는 AIMD 원칙에 따라 혼잡 창 크기가 선형적으로 증가한다. 구체적으로, 매 RTT마다 모든 ACK 확인응답을 수신했을 때 혼잡 창 크기를 1 MSS만큼 증가시킨다. 이는 지수적 증가가 아닌 점진적 증가를 의미하며, 네트워크가 포화 상태에 근접했을 때 과도한 트래픽을 주입하여 혼잡을 악화시키는 것을 방지한다. 이 방식을 '가법적 증가'라고 부른다.

혼잡 회피 단계는 패킷 손실이 감지될 때까지 지속된다. 손실 감지는 주로 세 번의 중복 ACK 수신 또는 재전송 타임아웃을 통해 이루어진다. 중복 ACK에 의한 손실 감지는 '빠른 재전송' 메커니즘을 트리거하여 '빠른 회복' 단계로 진입하게 한다. 반면, 타임아웃은 더 심각한 혼잡으로 간주되어 '느린 시작' 단계로 회귀하게 만든다. 이 단계는 네트워크의 지속적인 모니터링과 미세 조정을 통해 안정적인 처리량을 유지하는 데 기여한다.

빠른 재전송은 TCP의 혼잡 제어 메커니즘에서, 세그먼트 손실을 더 빠르게 감지하고 복구하기 위해 설계된 절차이다. 이 메커니즘은 전통적인 재전송 타임아웃에만 의존하는 방식의 비효율성을 개선한다. 타임아웃은 일반적으로 왕복 시간의 여러 배에 달하는 긴 시간을 기다려야 하므로, 이 동안 혼잡 창이 1로 줄어들고 전송이 사실상 정지되는 문제가 있다. 빠른 재전송은 중복 ACK를 활용하여 타임아웃이 발생하기 전에 손실을 추정하고 재전송을 유발한다.

구체적인 작동 방식은 다음과 같다. 송신자는 전송한 데이터 세그먼트에 대한 확인응답을 기다린다. 수신자는 순서가 맞지 않는 세그먼트가 도착할 때마다, 마지막으로 제대로 받은 순차적 데이터의 시퀀스 번호를 가진 ACK를 중복으로 보낸다. 예를 들어, 세그먼트 1, 2, 3, 5가 도착하면, 수신자는 세그먼트 3에 대한 ACK를 세그먼트 5가 도착했을 때 다시 보낸다. 송신자가 동일한 시퀀스 번호를 가진 중복 ACK를 3개 연속으로 받으면[3], 해당 세그먼트(이 예에서는 세그먼트 4)가 손실되었다고 간주하고 즉시 재전송을 수행한다.

이 과정은 다음 표를 통해 요약할 수 있다.

빠른 재전송은 타임아웃을 기다리지 않으므로 전체 전송 지연을 줄이고 처리량을 향상시킨다. 이 메커니즘은 주로 순서가 바뀐 패킷 전달보다는 단일 패킷 손실에 더 효과적이다. 빠른 재전송이 성공적으로 트리거되면, TCP는 혼잡 회피 단계를 벗어나 빠른 회복 단계로 진입하여 보다 공격적으로 혼잡 창을 관리한다.

빠른 회복 단계는 빠른 재전송이 트리거된 후, 즉 중복 ACK 세 개를 받은 후에 시작된다. 이 단계의 핵심 목표는 혼잡 창 크기를 급격히 줄이지 않고 유지함으로써 네트워크 혼잡이 해소되는 동안에도 데이터 전송을 계속할 수 있게 하는 것이다. 이를 통해 AIMD 방식의 전통적인 혼잡 제어가 가진 처리량 급감 문제를 완화한다.

이 단계에서 송신자는 다음과 같은 절차를 따른다. 먼저, 혼잡 창 크기를 현재 값의 절반으로 줄이고, 혼잡 임계값을 이 새로운 창 크기로 설정한다. 그런 다음, 손실된 것으로 추정되는 세그먼트를 재전송한다. 이후에는 중복 ACK를 추가로 수신할 때마다 혼잡 창을 1 MSS씩 증가시킨다. 이는 네트워크 파이프라인에서 손실된 패킷 하나가 빠져나갔음을 의미하기 때문이다.

이 과정은 누락된 세그먼트에 대한 새로운 ACK가 도착할 때까지 지속된다. 새로운 ACK가 도착하면, 송신자는 빠른 회복 단계를 종료하고 혼잡 회피 단계로 돌아간다. 이때 혼잡 창 크기는 새로 설정된 혼잡 임계값으로 조정되어, 선형 증가 방식으로 다시 전송 속도를 높여 나간다. 이 메커니즘은 단일 패킷 손실에 대한 복구 시간을 크게 단축시킨다.

TCP Reno는 빠른 회복 알고리즘을 구현한 초기 TCP 혼잡 제어 프로토콜이다. 이는 TCP Tahoe의 후속으로, 빠른 재전송과 빠른 회복 단계를 도입하여 단일 패킷 손실에 대한 대응을 개선했다. Reno는 세 개의 중복 ACK를 받으면 혼잡 회피 단계에서 혼잡 창을 절반으로 줄이고, 이후 빠른 회복 단계에 진입한다. 빠른 회복 단계에서는 손실된 각 패킷에 대해 하나의 새로운 패킷을 전송하며, 새로운 ACK가 도착할 때마다 혼잡 창을 증가시킨다. 이로 인해 단일 패킷 손실 시 처리량 저하가 완화된다.

그러나 TCP Reno는 한 RTT 내에 여러 패킷이 손실되는 경우, 즉 다중 패킷 손실 시 비효율적인 문제를 보였다. 빠른 회복 단계에서 첫 번째 손실만 감지하고 복구한 후, 나머지 손실은 재전송 타임아웃을 기다려야 하는 경우가 발생했다. 이는 네트워크 처리량을 다시 저하시키는 원인이 되었다.

이 문제를 해결하기 위해 등장한 것이 TCP NewReno이다. NewReno는 Reno의 빠른 회복 단계를 확장하여 부분적인 ACK를 처리하는 방식을 개선했다. NewReno는 빠른 회복 단계에서 여러 패킷이 손실되더라도, 첫 번째 손실 복구 후에도 빠른 회복 상태를 유지한다. 이후 도착하는 부분적인 ACK(새로운 데이터를 확인응답하지만, 아직 손실된 구간이 남아 있는 ACK)를 받으면, 바로 다음 손실된 패킷을 재전송한다. 이 과정은 한 RTT 내의 모든 손실이 복구되고 원래의 전송 시퀀스 번호를 확인응답하는 ACK가 도착할 때까지 반복된다.

다음 표는 TCP Reno와 TCP NewReno의 핵심 차이점을 요약한다.

결과적으로, TCP NewReno는 Reno에 비해 다중 패킷 손실 상황에서 재전송 타임아웃 발생 빈도를 크게 줄이고 전반적인 네트워크 성능을 향상시켰다. 이 개선으로 인해 NewReno는 오랫동안 많은 시스템의 기본 TCP 구현에 채택되었다.

리눅스 커널에서 빠른 회복 알고리즘은 TCP 혼잡 제어 구현의 핵심 부분으로 통합되어 있다. 주로 net/ipv4/tcp_cong.c 및 관련 소스 파일에 구현되며, struct tcp_congestion_ops 구조체를 통해 다양한 혼잡 제어 알고리즘이 모듈화되어 관리된다. 리눅스의 표준 TCP 스택은 역사적으로 TCP Reno와 TCP NewReno의 동작을 기본으로 삼았으며, 이후 CUBIC이 기본 알고리즘으로 채택되었다. 빠른 회복 로직은 중복 ACK 수신 및 패킷 손실 감지 시 호출되는 콜백 함수들(예: tcp_fastretrans_alert()) 내에 구현되어 있다.

구체적인 동작은 tcp_reno_fast_recovery()와 같은 함수에서 확인할 수 있다. 이 함수는 세 번의 중복 ACK를 받아 빠른 재전송이 트리거되면 호출된다. 알고리즘은 혼잡 창(cwnd)을 반으로 줄이고, 손실로 추정된 패킷을 재전송한 후, 혼잡 회피 단계 대신 빠른 회복 단계로 진입한다. 이 단계에서는 매번 추가적인 중복 ACK를 수신할 때마다 혼잡 창을 일시적으로 증가시켜, 파이프라인에 새로운 패킷을 주입할 수 있도록 한다. 최종적으로 누락된 시퀀스 번호의 ACK(부분적 ACK가 아닌)를 수신하면 빠른 회복 단계를 종료하고 혼잡 회피 단계로 복귀한다.

리눅스 커널의 구현은 다음과 같은 튜닝 가능한 파라미터들을 통해 세부 동작을 조정할 수 있다.

이러한 구현은 TCP NewReno의 동작을 모델로 하여, 부분적 ACK를 처리하는 동안에도 한 번의 RTT 내에 여러 패킷 손실을 복구할 수 있도록 개선되었다. 또한, 선택적 확인응답(SACK) 옵션이 협상된 연결의 경우, 더 정교한 tcp_sacktag_write_queue() 함수를 통해 손실된 패킷을 식별하고 복구 효율을 높인다.

빠른 회복 알고리즘의 주요 목표는 혼잡 제어 과정에서 발생하는 불필요한 처리량 저하를 최소화하는 것이다. 기존의 TCP Tahoe와 같은 알고리즘은 패킷 손실을 감지하면 혼잡 창 크기를 1로 줄이고 슬로 스타트 단계부터 다시 시작한다. 이 방식은 네트워크가 실제로 혼잡한 상태가 아니더라도 급격한 처리량 감소를 초래한다. 반면, 빠른 회복은 손실이 단일 패킷에 의한 일시적 현상일 가능성을 고려하여, 창 크기를 반으로만 줄이고 선형 증가 단계로 바로 진입하게 한다. 이를 통해 혼잡 상태에서 회복하는 시간을 크게 단축시켜 평균 처리량을 향상시킨다.

구체적인 효과는 시뮬레이션과 실제 네트워크 측정을 통해 확인된다. 손실률이 낮은 환경에서 빠른 회복을 적용한 TCP Reno는 TCP Tahoe 대비 상당히 높은 처리량을 유지한다. 다음 표는 단순화된 조건에서 두 알고리즘의 처리량 변화를 비교한 예시이다.

이러한 향상은 특히 왕복 지연 시간이 길거나, 무선 네트워크에서 간헐적인 손실이 발생하는 환경에서 두드러진다. 알고리즘이 빠른 재전송 메커니즘과 결합되어 중복 ACK를 통해 손실을 빠르게 감지하고, 빠른 회복 단계에서 창 크기를 절반으로 유지한 상태로 데이터 전송을 계속하기 때문이다. 결과적으로 연결이 가용 대역폭을 더 효율적으로 그리고 지속적으로 활용할 수 있게 된다.

그러나 처리량 향상 효과는 모든 상황에서 균일하지는 않다. 연속적인 패킷 손실이나 시간 초과가 발생하는 극심한 혼잡 상황에서는 빠른 회복의 이점이 제한될 수 있다. 또한, TCP NewReno와 같은 후속 알고리즘은 부분적 ACK를 처리하는 방식을 개선하여 여러 패킷이 한 번에 손실되는 경우의 처리량을 더욱 높였다.

빠른 회복 알고리즘은 패킷 손실을 혼잡의 유일한 신호로 가정한다는 근본적인 한계를 가진다. 무선 네트워크 환경에서는 전파 간섭이나 핸드오버로 인해 패킷이 손실될 수 있으며, 이는 혼잡과 무관한 손실이다. 그러나 알고리즘은 이러한 손실도 혼잡으로 오인하여 불필요하게 혼잡 창 크기를 줄이게 되어 처리량을 저하시킨다. 또한, 네트워크에 버퍼블로트가 발생한 상황에서도 패킷 손실이 일어나기 전까지는 혼잡을 감지하지 못해 과도한 지연을 유발할 수 있다.

이러한 한계를 극복하기 위해 여러 개선 방향이 연구되고 적용되었다. 대표적인 방향은 혼잡 신호의 다각화이다. ECN은 라우터가 혼잡을 미리 감지하여 패킷 헤더에 표시하고, 수신측이 이 신호를 송신측에 알려 패킷 손실 없이도 혼잡 창을 조절할 수 있게 한다. 또한, RTT의 변화율을 지속적으로 모니터링하여 지연 증가를 혼잡의 선행 지표로 활용하는 BBR과 같은 새로운 알고리즘들이 개발되었다. 이들은 패킷 손실에만 의존하지 않고 네트워크 경로의 정체를 보다 정확히 판단한다.

다음 표는 주요 한계와 그에 대응하는 개선 기술을 정리한 것이다.

궁극적인 개선 방향은 네트워크 상태에 대한 보다 풍부한 정보를 수집하고, 이를 기반으로 한 지능적인 의사 결정으로 나아가는 것이다. 머신러닝을 활용해 네트워크 상태를 예측하고 혼잡 제어 매개변수를 실시간으로 조정하는 연구나, QUIC 프로토콜처럼 전송 계층 프로토콜 자체를 재설계하여 더 유연한 혼잡 제어를 가능하게 하는 접근법이 활발히 진행 중이다.

TCP Tahoe는 TCP의 초기 혼잡 제어 알고리즘으로, 패킷 손실을 혼잡의 유일한 신호로 간주했다. Tahoe는 세 번의 중복 ACK 수신 또는 재전송 타임아웃이 발생하면 혼잡 창 크기를 1 MSS로 줄이는(슬로 스타트 임계값을 절반으로 설정한 후) 급격한 감소를 수행한다. 그 후 슬로 스타트 단계부터 다시 시작하여 창 크기를 천천히 증가시켰다. 이 방식은 혼잡이 해결된 후에도 네트워크 대역폭을 빠르게 재활용하지 못해 처리량이 급격히 떨어지는 문제가 있었다.

반면, 빠른 회복 알고리즘을 도입한 TCP Reno는 '빠른 재전송'과 '빠른 회복' 단계를 추가하여 이 문제를 완화했다. Reno는 세 개의 중복 ACK를 받으면 Tahoe와 마찬가지로 손실된 세그먼트를 즉시 재전송하지만, 혼잡 창을 반으로만 줄이고 '빠른 회복' 단계로 진입한다. 이 단계에서는 손실로 추정되는 각 중복 ACK에 대해 혼잡 창을 점진적으로 증가시켜, 데이터 흐름이 완전히 멈추지 않도록 유지한다. 새로운 ACK가 도착하면 혼잡 회피 단계로 복귀하여 안정적으로 운영된다.

두 알고리즘의 핵심 차이는 혼잡 신호(주로 중복 ACK)에 대한 반응 방식에 있다. 다음 표는 주요 차이점을 요약한다.

결과적으로, TCP Reno의 빠른 회복은 단일 패킷 손실이 발생한 상황에서 TCP Tahoe보다 더 나은 처리량과 더 짧은 전송 지연을 보여준다. 그러나 여러 패킷이 한 라운드 트립 시간 내에 손실되는 경우, Reno 역시 성능이 저하될 수 있으며, 이는 후속 알고리즘인 TCP NewReno나 TCP SACK에서 추가로 개선되었다.

TCP Reno와 TCP NewReno는 AIMD 기반의 기본적인 빠른 회복 알고리즘을 구현했지만, 고대역폭·고지연 네트워크 환경에서는 혼잡 창의 선형 증가가 너무 느려 링크를 효율적으로 활용하지 못하는 문제가 있었다. 이 한계를 극복하기 위해 개발된 대표적인 현대 혼잡 제어 알고리즘으로 CUBIC TCP와 BBR이 있다.

CUBIC은 2008년에 제안된 알고리즘으로, 혼잡 창 증가를 시간의 3차 함수(큐빅 함수)에 기반하도록 설계했다. 혼잡 손실이 발생한 시점의 창 크기를 기준으로, 이후 창 크기를 시간의 함수로 빠르게 증가시킨 다음 점차 완만하게 증가시켜 그 기준점에 접근한다. 이 방식은 RTT에 덜 민감하게 반응하여 고대역폭·고지연 네트워크에서 공정성을 유지하면서도 높은 처리량을 달성하는 데 효과적이다. CUBIC은 리눅스 커널의 기본 TCP 혼잡 제어 알고리즘으로 널리 채택되었다.

반면, 구글이 2016년에 발표한 BBR은 패킷 손실을 혼잡의 지표로 사용하는 기존 방식에서 근본적으로 벗어난 접근법을 취한다. BBR은 네트워크 경로의 최대 대역폭과 최소 RTT를 실시간으로 측정하여 이 두 가지의 곱인 BDP를 산출하고, 이를 기반으로 최적의 송신 속도와 혼잡 창 크기를 결정한다. 목표는 버퍼블로트를 유발하지 않으면서도 링크 대역폭을 꽉 채우는 것이다. BBR은 손실 기반 알고리즘이 버퍼 오버플로우를 필연적으로 유발한다고 보고, 대역폭과 지연을 직접 측정하는 모델 기반 방식으로 전환했다는 점에서 혁신적이다.

아래 표는 두 알고리즘의 핵심 특징을 비교한 것이다.

이 외에도 TCP Vegas, Compound TCP, BBR v2 등 다양한 개선 알고리즘이 존재하며, 각각 다른 네트워크 조건과 요구사항에 맞춰 발전하고 있다.

빠른 회복 알고리즘은 고속 이더넷이나 데이터 센터 네트워크와 같이 대역폭이 크고 지연 시간이 짧은 환경에서 TCP 처리량을 최적화하는 데 중요한 역할을 한다. 이러한 네트워크는 높은 대역폭-지연 곱을 가지므로, 패킷 손실이 발생했을 때 혼잡 창을 너무 급격하게 줄이면 링크 활용도가 크게 떨어지게 된다. 빠른 회복은 혼잡 창을 절반으로만 줄이고 중복 확인 응답을 통해 빠르게 창 크기를 회복시킴으로써, 고속 링크의 대역폭을 효율적으로 유지하도록 설계되었다.

데이터센터 내부 통신에서, 특히 RDMA over Converged Ethernet와 같은 저지연 애플리케이션은 작은 버퍼와 미세한 혼잡 신호를 사용한다. 전통적인 AIMD 방식은 이러한 환경에서 과도하게 공격적인 창 감소를 유발하여 성능을 저하시킨다. 빠른 회복 알고리즘을 적용하면, 단일 패킷 손실에 대한 반응이 완화되어 전체 처리량 변동성을 줄이고 예측 가능한 성능을 제공하는 데 도움이 된다.

다음 표는 고속 네트워크 환경에서 빠른 회복의 이점을 요약한 것이다.

그러나 데이터센터의 극단적으로 낮은 지연 시간과 특정 혼잡 제어 요구사항을 완전히 충족하기 위해, 빠른 회복은 TCP CUBIC이나 데이터센터 TCP와 같은 더 진화된 알고리즘의 기본 구성 요소로 통합되는 경우가 많다. 이러한 현대적 프로토콜은 빠른 회복의 원리를 확장하여, 명시적 혼잡 통지 신호를 활용하거나 대역폭-지연 곱을 직접 추정하는 방식으로 고속 네트워크의 성능을 한층 더 최적화한다.

빠른 회복 알고리즘은 본래 유선 네트워크의 혼잡 제어를 위해 설계되었다. 그러나 무선 네트워크는 패킷 손실의 원인이 전파 간섭, 핸드오버, 신호 감쇠 등 혼잡과 무관한 요인에서 비롯되는 경우가 많다. 이러한 무선 특유의 손실을 혼잡 신호로 오인하면, 알고리즘이 불필요하게 전송 속도를 낮추어 처리량이 저하되는 문제가 발생한다.

이 문제를 완화하기 위해 TCP Veno나 TCP Westwood와 같은 변형 알고리즘이 제안되었다. 이들은 왕복 지연 시간(RTT) 변화나 대역폭 추정을 통해 손실 원인을 추론하려 시도한다. 또한, 이중 큐를 사용하는 무선 액세스 포인트나 셀룰러 네트워크의 기지국은 링크 계층에서의 재전송(링크 계층 재전송)으로 상위 전송 계층에 패킷 손실을 숨기는 방식을 사용하기도 한다. 하지만 이 방법은 버퍼블로트를 유발하거나 종단 간 전송 지연을 증가시킬 수 있다.

손실이 빈번한 네트워크 환경, 예를 들어 위성 통신이나 심해 해저 통신에서도 유사한 도전 과제가 존재한다. 이러한 환경에서는 긴 지연과 높은 비트 오류율(BER)로 인해 전통적인 재전송 기반 혼잡 제어의 효율이 떨어진다. 이를 위해 전송 제어 프로토콜(TCP) 대신 사용자 데이터그램 프로토콜(UDP)을 기반으로 한 프로토콜(예: QUIC)이 연구되거나, 순방향 오류 수정(FEC) 기술이 결합되어 사용된다[9].