임의조기검출

Random early detection
Random Early Detection algorithm en.svg

RED(Random Early Detection, 무작위 조기 폐기 또는 무작위 조기 강하라고도 함)는 혼잡 방지를 위해 적합한 네트워크 스케줄러에 대한 대기열이다.[1]

기존의 tail drop 알고리즘에서는 라우터나 다른 네트워크 구성요소가 가능한 한 많은 패킷을 버퍼링하고, 버퍼링할 수 없는 패킷을 간단하게 삭제한다. 버퍼가 계속 꽉 차면 네트워크가 정체된다. 테일드롭은 교통 흐름 사이에 버퍼 공간을 불공평하게 분배한다. Tail drop은 또한 모든 TCP 연결이 동시에 "holdback"되고 나서 동시에 앞으로 나아가면서 TCP 전역 동기화를 유도할 수 있다. 네트워크는 활용도가 떨어지고 물결이 일면서 홍수가 난다.

RED는 버퍼가 완전히 차기 전에 패킷을 미리 삭제하여 이러한 문제를 해결한다. 어떤 패킷을 떨어뜨릴지 결정하기 위해 예측 모델을 사용한다. 1990년대 초 샐리 플로이드와 반 제이콥슨에 의해 발명되었다.[2]

작전

RED는 통계적 확률을 기반으로 평균 대기열 크기 및 드롭(또는 ECN과 함께 사용할 경우 표시) 패킷을 모니터링한다. 버퍼가 거의 비어 있으면 들어오는 모든 패킷이 허용된다. 대기열이 커질수록 들어오는 패킷을 떨어뜨릴 확률도 커진다. 버퍼가 가득 차면 확률은 1에 도달하고 들어오는 패킷은 모두 삭제된다.

RED는 대역폭의 작은 부분만을 사용하는 버스트 트래픽에 대한 편견을 갖지 않는다는 점에서 테일 드롭보다 더 공정하다. 호스트가 더 많이 전송할수록 호스트의 패킷이 삭제될 확률은 큐에 있는 데이터 양에 비례하여 패킷이 삭제될 가능성이 더 높아진다. 조기 발견은 TCP 전역 동기화를 방지하는 데 도움이 된다.

고전적 RED의 문제

Van Jacobson에 따르면, "클래식 RED에는 한 개의 버그가 아니라 두 개의 버그가 있다."[3] 알고리즘에 대한 개선이 개발되었고, 초안 논문이[4] 준비되었지만, 논문은 발표되지 않았고, 개선 사항이 널리 보급되거나 실행되지 않았다. 연구를 끝내고 벌레를 고치려는 노력이 좀 있었다.[3]

순수 RED는 QoS(서비스 품질) 차별화를 수용하지 않는다. 가중 적색(WRED)과 적색(RIDO 포함)[5]은 QoS 고려사항과 함께 조기 발견을 제공한다.

기타 변형

WRED

주요 기사: 가중 무작위 조기 검출

가중 RED에서는 우선순위(IP 우선 순위, DSCP) 및/또는 대기열에 따라 다른 확률을 가질 수 있다.[6]

아레드

적응형 RED 또는 활성 RED(ARD) 알고리즘은[7] 평균 대기열 길이의 관찰을 기반으로 RED를 더 공격적으로 만들 것인지 여부를 입력한다. 평균 대기열 길이가 최소 임계값에서 진동할 경우 조기 감지가 너무 공격적이다. 반면에, 평균 대기열 길이가 최대 임계값에서 진동한다면 조기 감지는 너무 보수적이다. 알고리즘은 트래픽을 얼마나 공격적으로 감지해 왔는지에 따라 확률을 바꾼다.

이러한 기술과 분석에 대한 자세한 설명은 스리칸트를[8] 참조하십시오.

RRED

주요 기사: 강력한 무작위 조기 탐지

서비스 거부(DoS) 공격, 특히 저율 서비스 거부(LDoS) 공격에 대한 TCP 처리량을 개선하기 위해 강력한 RRED(Random Random Early Detection) 알고리즘이 제안되었다. 실험 결과, 기존 RED와 유사한 알고리즘이 공격에 의해 발생하는 진동 TCP 대기열 크기 때문에 저율 서비스 거부(LDoS) 공격 시 특히 취약하다는 것이 확인되었다.[9] RRED 알고리즘은 저율 서비스 거부 공격 시 TCP의 성능을 크게 향상시킬 수 있다.[9]

참고 항목

참조

  1. ^ Floyd, Sally; Jacobson, Van (August 1993). "Random Early Detection (RED) gateways for Congestion Avoidance". IEEE/ACM Transactions on Networking. 1 (4): 397–413. CiteSeerX 10.1.1.147.3833. doi:10.1109/90.251892. Retrieved 2008-03-16.
  2. ^ Hafner, Katie (September 4, 2019). "Sally Floyd, Who Helped Things Run Smoothly Online, Dies at 69" – via NYTimes.com.
  3. ^ Jump up to: a b Gettys, Jim (2010-12-17). "RED in a Different Light". jg's Ramblings. Retrieved 2010-12-27.
  4. ^ Jacobson, Van; Nichols, Kathy; Poduri, Kedar (1999-09-30). "RED in a Different Light". CiteSeerX 10.1.1.22.9406. Cite 저널은 필요로 한다. journal= (도움말)
  5. ^ Clark, David D.; Wroclawski, John (July 1997). "An Approach to Service Allocation in the Internet". IETF. p. 12. Retrieved 2011-05-27.
  6. ^ Chao, H. Jonathan (2002). "Frontmatter and Index". Quality of service control in high speed networks. 605 Third Avenue, New York, NY: John Wiley & Sons Inc. pp. i–xvi. doi:10.1002/0471224391.fmatter_indsub. ISBN 978-0-471-00397-7.CS1 maint: 위치(링크)
  7. ^ Floyd, Sally; Gummadi, Ramakrishna; Shenker, Scott (2001-08-01). "Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management". Retrieved 2008-03-16. Cite 저널은 필요로 한다. journal= (도움말)
  8. ^ Srikant, Rayadurgam (2004). The Mathematics of Internet Congestion Control. Boston, MA, USA: Birkhäuser. ISBN 978-0-8176-3227-4.
  9. ^ Jump up to: a b Zhang, Changwang; Yin, Jianping; Cai, Zhiping; Chen, Weifeng (1 May 2010). "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.

외부 링크