무작위 조기 검출

3. 기존 RED 문제점

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

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

4. 변형

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

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

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

4. 1. WRED (Weighted RED)

4. 2. ARED (Adaptive RED)

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

4. 3. RRED (Robust RED)

참조

_[1] 논문 Random Early Detection (RED) gateways for Congestion Avoidance http://www.icir.org/[...] 2008-03-16
_[2] 뉴스 Sally Floyd, Who Helped Things Run Smoothly Online, Dies at 69 https://www.nytimes.[...] 2019-09-04
_[3] 웹사이트 RED in a Different Light http://gettys.wordpr[...] 2010-12-27
_[4] 논문 RED in a Different Light 1999-09-30
_[5] 뉴스 An Approach to Service Allocation in the Internet http://tools.ietf.or[...] IETF 2011-05-27
_[6] 서적 Quality of service control in high speed networks John Wiley & Sons Inc.
_[7] 논문 Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management http://citeseer.ist.[...] 2008-03-16
_[8] 서적 The Mathematics of Internet Congestion Control https://www.springer[...] Birkhäuser
_[9] 논문 RRED: robust RED algorithm to counter low-rate denial-of-service attacks 2010-05-01
_[10] 논문 Random Early Detection (RED) gateways for Congestion Avoidance http://www.icir.org/[...] 2008-03-16
_[11] 간행물 Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management http://citeseer.ist.[...] 2008-03-16
_[12] 서적 The Mathematics of Internet Congestion Control http://www.springer.[...] Birkhäuser 2004
_[13] 논문 Random Early Detection (RED) gateways for Congestion Avoidance http://www.icir.org/[...] 2008-03-16
_[14] 웹인용 RED in a Different Light http://gettys.wordpr[...] 2010-12-27
_[15] 웹인용 RED in a Different Light http://citeseerx.ist[...] 1999-09-30
_[16] 웹인용 An Approach to Service Allocation in the Internet http://tools.ietf.or[...] IETF 2011-05-27
_[17] 서적 Quality of service control in high speed networks John Wiley & Sons Inc.
_[18] 논문 Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management http://citeseer.ist.[...] 2008-03-16
_[19] 서적 The Mathematics of Internet Congestion Control http://www.springer.[...] Birkhäuser
_[20] 논문 RRED: robust RED algorithm to counter low-rate denial-of-service attacks 2010-05-01