무작위 조기 검출

무작위 조기 검출 (Random Early Detection, RED)은 네트워크 혼잡 제어를 위해 사용되는 능동적 대기열 관리(Active Queue Management, AQM) 알고리즘이다. 라우터나 스위치에서 발생하는 네트워크 혼잡을 완화하기 위해, 패킷을 무작위로 폐기하여 송신 호스트가 전송률을 조절하도록 유도한다.

개요

RED는 큐의 평균 크기를 모니터링하고, 이 평균 크기가 미리 설정된 최소 임계값(min_th)과 최대 임계값(max_th) 사이의 범위에 있을 때 패킷을 무작위로 폐기하거나 ECN(Explicit Congestion Notification) 마크를 설정한다. 큐의 평균 크기가 최소 임계값보다 작으면 모든 패킷이 큐에 들어가고, 최대 임계값보다 크면 모든 패킷이 폐기된다. 평균 큐 크기가 임계값 사이에 있을 경우, 폐기 확률은 평균 큐 크기가 증가함에 따라 선형적으로 증가한다.

작동 방식

RED 알고리즘의 핵심은 다음과 같다.

1. 평균 큐 크기 계산: 지수 가중 이동 평균(Exponential Weighted Moving Average, EWMA)을 사용하여 큐의 평균 크기를 계산한다. 이는 과거 큐 크기의 영향력을 점차 줄여 현재 큐 상황에 더 민감하게 반응하도록 한다.

2. 폐기 확률 결정: 계산된 평균 큐 크기에 따라 패킷 폐기 확률을 결정한다. 평균 큐 크기가 최소 임계값보다 작으면 폐기 확률은 0이고, 최대 임계값보다 크면 폐기 확률은 1이다. 두 임계값 사이에서는 평균 큐 크기에 비례하여 폐기 확률이 선형적으로 증가한다.

3. 패킷 폐기 또는 ECN 마크 설정: 결정된 폐기 확률에 따라 패킷을 무작위로 폐기하거나 ECN 마크를 설정한다. ECN 마크는 송신 호스트에게 혼잡이 발생하고 있음을 알리는 역할을 한다.

장점 및 단점

장점:

• 글로벌 동기화 현상 방지: 모든 연결이 동시에 혼잡에 대응하는 것을 방지하여 네트워크 성능을 향상시킨다.
• TCP의 혼잡 제어 메커니즘 활성화: 패킷 손실 또는 ECN 마크 설정을 통해 TCP의 혼잡 제어 메커니즘을 활성화하여 네트워크 혼잡을 완화한다.

단점:

• 매개변수 설정의 어려움: 최적의 성능을 위해 최소 임계값, 최대 임계값, 가중치 등의 매개변수를 신중하게 설정해야 한다.
• TCP 흐름에 대한 공정성 문제: 특정 TCP 흐름에 불리하게 작용할 수 있다는 문제점이 있다.

관련 기술

• AQM (Active Queue Management)
• ECN (Explicit Congestion Notification)
• CoDel (Controlled Delay)
• PIE (Proportional Integral controller Enhanced)