무작위 조기 검출

1. 개요

무작위 조기 감지(RED)는 통계적 확률을 기반으로 평균 대기열 크기를 모니터링하여 네트워크 혼잡을 관리하는 기술이다. 버퍼가 비어있을 때는 모든 패킷을 허용하고, 대기열이 커짐에 따라 패킷 삭제 확률을 증가시키며, 버퍼가 가득 차면 모든 패킷을 삭제한다. RED는 테일 드롭보다 공평하며 TCP 글로벌 동기화를 방지하는 데 도움이 된다. 초기 RED는 몇 가지 문제점을 가지고 있었으며, 서비스 품질(QoS) 차별화를 위해 가중 RED(WRED) 및 입출력을 가진 RED(RIO)와 같은 변형이 개발되었다. 가중 RED는 패킷 속성 및 큐에 따라 확률을 변화시키며, 적응/동적 RED(ARED)는 평균 큐 길이를 관찰하여 공격적인 RED 적용 여부를 결정한다. 또한, 강력한 무작위 조기 감지(RRED)는 저속 서비스 거부(LDoS) 공격과 같은 서비스 거부 공격에 대한 TCP 처리량을 향상시키기 위해 제안되었다.

2. 동작

RED는 통계적 확률에 기반하여 평균 대기열 크기를 모니터링하고, 패킷을 폐기하거나 ECN과 함께 사용될 경우 표시한다. 버퍼가 거의 비어 있을 때는 모든 들어오는 패킷을 수용한다. 하지만 대기열의 크기가 커짐에 따라, 들어오는 패킷을 폐기할 확률도 점진적으로 증가한다. 버퍼가 완전히 가득 차면 폐기 확률은 1(100%)이 되어 모든 들어오는 패킷이 폐기된다.

RED는 테일 드롭 방식보다 공정하다는 장점이 있다. 특정 호스트가 대역폭의 작은 부분만을 사용하는 짧은 버스트 트래픽을 보낸다고 해서 특별히 불리하게 처리하지 않기 때문이다. 호스트가 더 많은 데이터를 전송하여 대기열에 데이터가 많이 쌓일수록, 해당 호스트의 패킷이 폐기될 확률은 높아진다. 이러한 조기 감지 방식은 TCP 글로벌 동기화 문제를 피하는 데 도움을 준다.

가중치 RED (Weighted RED) 방식에서는 IP 패킷의 ToS 필드 값이나 DSCP 값 등 다양한 속성이나 특정 큐에 따라 패킷 폐기 확률을 다르게 적용할 수 있다.

적응/동적 RED (Adaptive/Dynamic RED, ARED) 알고리즘은 평균 대기열 길이를 관찰하여 RED의 폐기 정책이 너무 공격적인지 혹은 너무 보수적인지를 동적으로 판단한다. 평균 대기열 길이가 낮은 임계값 근처에 머무르면, RED가 지나치게 공격적으로 패킷을 폐기한다고 판단한다. 반대로 평균 대기열 길이가 높은 임계값 근처에 있다면, RED가 너무 보수적이라고 판단한다. ARED는 이러한 판단을 바탕으로 트래픽 폐기 확률을 조절한다.

더 자세한 기술적 해설과 분석은 Srikant의 연구에서 찾아볼 수 있다.

3. 기존 RED 문제점

밴 제이콥슨(Van Jacobson)에 따르면 "이전의 RED에는 하나가 아니라 두 가지 버그가 있다." 이러한 버그를 수정하고 알고리즘을 개선하려는 시도가 있었으며, 논문 초안까지 준비되기도 했다. 그러나 해당 논문은 정식으로 출판되지 못했고, 개선 사항 역시 널리 알려지거나 실제 시스템에 구현되지 못하는 한계가 있었다. 연구를 마무리하고 버그를 수정하기 위한 일부 작업이 진행되었다.

또한, 순수한 형태의 RED 알고리즘은 트래픽의 종류나 중요도에 따른 서비스 품질(QoS) 차별화를 지원하지 않는다는 문제점을 가지고 있다. 이러한 단점을 보완하기 위해 가중 RED(WRED)나 입출력(In and Out, RIO)을 사용하는 RED와 같은 방식들이 개발되었다. 이 방식들은 QoS 요구 사항을 고려하여 조기 감지 기능을 제공한다.

4. 변형

기존의 RED(Random Early Detection) 알고리즘은 초기 제안 이후 몇 가지 문제점이 지적되었으며, 이를 개선하려는 시도가 있었으나 널리 적용되지는 못했다. 이러한 한계를 극복하고 특정 요구사항을 만족시키기 위해 여러 변형 알고리즘이 개발되었다.

특히 서비스 품질(QoS) 차별화를 지원하기 위한 변형들이 등장했다. 가중 RED(WRED)는 IP 패킷의 ToS 필드 값이나 DSCP와 같은 우선순위 또는 특정 큐에 따라 패킷 폐기 확률을 다르게 적용한다. 또한 In and Out(RIO) 방식 역시 QoS를 고려한 조기 감지 기능을 제공한다.

네트워크 상황 변화에 더 능동적으로 대처하기 위해 적응형 RED(ARED) 알고리즘도 제안되었다. ARED는 평균 큐 길이를 지속적으로 관찰하여, 그 변화 추세에 따라 패킷 폐기 확률을 동적으로 조절하는 방식이다. Srikant의 연구에서 RED 기법에 대한 자세한 해설과 분석을 찾아볼 수 있다.

4.1. WRED (Weighted RED)

가중 임의 조기 감지(WRED)는 패킷의 우선 순위(IP 우선 순위, DSCP 등)나 특정 네트워크 큐에 따라 패킷 폐기 확률을 다르게 적용하는 방식이다. 예를 들어, IP 패킷의 ToS 필드 값이나 DSCP 값과 같은 속성을 기준으로 확률을 차등화할 수 있다.

4.2. ARED (Adaptive RED)

적응형 RED(Adaptive RED) 또는 능동적 RED(Active RED, ARED) 알고리즘은 평균 큐(대기열) 길이를 관찰하여 RED의 패킷 폐기 확률을 동적으로 조절하는 방식이다.

ARED는 평균 큐 길이가 특정 임계값 주변에서 어떻게 변하는지를 보고 RED의 공격성 수준을 판단한다.
* 만약 평균 큐 길이가 최소 임계값(min) 부근에서 진동한다면, 이는 현재 패킷 폐기가 너무 공격적이라고 판단한다. 즉, 필요 이상으로 패킷을 일찍 버리고 있다는 의미이다.
* 반대로 평균 큐 길이가 최대 임계값(max) 부근에서 진동한다면, 이는 현재 패킷 폐기가 너무 보수적(소극적)이라고 판단한다. 즉, 큐가 거의 가득 찰 때까지 패킷을 충분히 버리지 않고 있다는 의미이다.

이러한 판단에 따라 ARED 알고리즘은 목표 평균 큐 길이에 맞춰 패킷 폐기 확률을 자동으로 조정하여, 네트워크 트래픽 변화에 더 효과적으로 대응하려고 시도한다.

ARED 기법과 분석에 대한 더 자세한 내용은 Srikant의 연구에서 찾아볼 수 있다.

4.3. RRED (Robust RED)

DoS(Denial of Service) 공격, 특히 저속 서비스 거부(Low-rate DoS, LDoS) 공격에 대한 TCP 처리량을 향상시키기 위해 RRED(Robust Random Early Detection) 알고리즘이 제안되었다. 실험 결과, 기존의 RED와 유사한 알고리즘들은 LDoS 공격 발생 시 TCP 대기열 크기가 불안정하게 변동하여 공격에 취약하다는 점이 확인되었다. RRED 알고리즘은 이러한 LDoS 공격 상황에서 TCP의 성능을 크게 향상시킬 수 있다.