무작위 조기 검출

위키백과, 우리 모두의 백과사전.
Random Early Detection algorithm en.svg

무작위 조기 버림 또는 무작위 조기 폐기으로 알려져 있는 무작위 조기 검출(Random early detect, RED)혼잡 제어에 적합한 네트워크 스케줄러대기열 규율이다.[1]

기존의 테일 드롭 알고리즘에서는 라우터 또는 다른 네트워크 구성 요소가 가능한한 많은 패킷을 버퍼링하고, 버퍼링할 수 없는 패킷은 삭제한다. 버퍼가 계속해서 가득 차면 네트워크는 정체된다. 테일 드롭은 트래픽 흐름 간에 불필요하게 버퍼 공간을 분산시키고, 또한 모든 TCP 연결이 동시에 "보류"되기 때문에 TCP 글로벌 동기화를 야기시킬 수 있고 그 다음에야 동시에 다음 단계로 나아갈 수 있다. 그렇게 되면 네트워크 활용도는 낮아지고 동작들로 홍수를 이룬다. RED는 이러한 문제를 해결한다.

동작[편집]

RED는 통계적 확률을 기반으로 평균 대기열 크기 및 폐기 (또는 ECN과 함께 사용되는 경우 표시) 패킷을 모니터링한다. 버퍼가 거의 비어 있으면 들어오는 모든 패킷이 허용된다. 대기열이 커짐에 따라 들어오는 패킷을 삭제할 확률도 증가한다. 버퍼가 꽉 찼을 때 확률은 1에 도달하고 들어오는 모든 패킷이 삭제된다.

RED는 대역폭의 작은 부분만을 사용하는 버스트 트래픽에 대해 특별한 처리를 하지 않기 때문에 테일 드롭보다 공평하다. 호스트가 전송할수록 호스트 패킷이 삭제 될 확률은 대기열에 있는 데이터의 양에 비례하므로 패킷이 삭제되는 확률이 높다. 조기 발견은 TCP 글로벌 동기화를 회피하는 데 도움이 된다.

이전 RED 문제점[편집]

밴 제이콥슨(Van Jacobson)에 따르면 "이전의 RED에는 하나가 아니라 두 가지 버그가 있다."[2] 알고리즘의 개선 사항이 개발되었고, 논문 초안[3]이 준비되었지만, 그 논문은 결코 출판되지 않았고, 그 개선은 널리 전파되거나 실행되지 못했다. 연구를 끝내고 버그를 수정하는 데 몇 가지 작업이 있었다.

순수한 RED는 서비스 품질 (QoS) 차별화를 수용하지 않는다.  가중치가 있는 RED (WRED)와 입출력을 가진 RED(RIO)[4] 는 QoS 고려 사항에 대한 조기 감지를 제공한다.

변형[편집]

WRED[편집]

가중치가 적용된 RED에서는 우선 순위(IP 우선 순위, DSCP) 및 / 또는 대기열마다 차별화된 우선 순위에 대해 다른 확률을 가질 수 있다.[5]

ARED[편집]

적응형 RED 또는 액티브 RED (ARED) 알고리즘[6]은 평균 대기열 길이를 관찰하여 RED를 다소 공격적으로 만들 것인지 여부를 유추한다. 평균 대기열 길이가 최소 임계 값 주변에서 진동하는 경우 조기 감지는 너무 공격적이다. 반면 평균 대기열 길이가 최대 임계 값 주변에서 진동하는 경우 조기 감지는 너무 보수적이다. 이 알고리즘은 트래픽을 무시하고 얼마나 적극적으로 감지했는지에 따라 확률을 변경한다.

이러한 기법과 분석에 대한 자세한 설명은 Srikant[7]를 참조.

RRED[편집]

DoS(Denial of Service) 공격, 특히 저속 서비스 거부 (Low-rate DoS, LDoS) 공격에 대한 TCP 처리량을 향상시키기 위해 강력한 임의 조기 탐지 (RRED) 알고리즘이 제안되었다. 실험 결과, 공격으로 인한 TCP 대기열 크기의 변동으로 인해 저속 서비스 거부 (Low-rate Denial-of-Service) 공격에서 기존의 RED와 유사한 알고리즘이 취약하다는 사실이 확인되었다.[8] RRED 알고리즘은 저속 서비스 거부 공격 하에서 TCP의 성능을 크게 향상시킬 수 있다.

같이 보기[편집]

  • 블루(큐 관리 알고리즘)
  • Active 큐 관리

각주[편집]

  1. Floyd, Sally; Jacobson, Van (August 1993). “Random Early Detection (RED) gateways for Congestion Avoidance”. 《IEEE/ACM Transactions on Networking》 1 (4): 397–413. doi:10.1109/90.251892. 2008년 3월 16일에 확인함. 
  2. Gettys, Jim (2010년 12월 17일). “RED in a Different Light”. 《jg's Ramblings》. 2010년 12월 27일에 확인함. 
  3. Jacobson, Van; Nichols, Kathy; Poduri, Kedar (1999년 9월 30일). “RED in a Different Light”. 
  4. Clark, David D.; Wroclawski, John (July 1997). “An Approach to Service Allocation in the Internet”. IETF. 12쪽. 2011년 5월 27일에 확인함. 
  5. Chao, H. Jonathan (2002). 《Quality of service control in high speed networks》. 605 Third Avenue, New York, NY: John Wiley & Sons Inc. doi:10.1002/0471224391.fmatter_indsub. ISBN 0-471-00397-2. 
  6. Floyd, Sally; Gummadi, Ramakrishna; Shenker, Scott (2001년 8월 1일). “Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management”. 2008년 3월 16일에 확인함. 
  7. Srikant, Rayadurgam (2004). 《The Mathematics of Internet Congestion Control》. Boston, MA, USA: Birkhäuser. ISBN 978-0-8176-3227-4. 
  8. Zhang, Changwang; Yin, Jianping; Cai, Zhiping; Chen, Weifeng (2010년 5월 1일). “RRED: robust RED algorithm to counter low-rate denial-of-service attacks”. 《IEEE Communications Letters》 14 (5): 489–491. doi:10.1109/LCOMM.2010.05.091407. 

외부 링크[편집]