무작위 조기 검출
무작위 조기 버림 또는 무작위 조기 폐기으로 알려져 있는 무작위 조기 검출(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 큐 관리
각주
편집- ↑ 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일에 확인함.
- ↑ Gettys, Jim (2010년 12월 17일). “RED in a Different Light”. 《jg's Ramblings》. 2010년 12월 27일에 확인함.
- ↑ Jacobson, Van; Nichols, Kathy; Poduri, Kedar (1999년 9월 30일). “RED in a Different Light”.
- ↑ Clark, David D.; Wroclawski, John (July 1997). “An Approach to Service Allocation in the Internet”. IETF. 12쪽. 2011년 5월 27일에 확인함.
- ↑ 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.
- ↑ 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일에 확인함.
- ↑ Srikant, Rayadurgam (2004). 《The Mathematics of Internet Congestion Control》. Boston, MA, USA: Birkhäuser. ISBN 978-0-8176-3227-4.
- ↑ 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.
외부 링크
편집- RED(무작위 조기 검출) 큐 관리. 저자: Sally Floyd
- Guduz –간단한 임의의 초기 탐지기(RED)시뮬레이터
- RED 변형. 저자:Hei Xiao Jun
- 무작위 조기 검출(RED)을 다룬 최근 간행물 Archived 2016년 9월 17일 - 웨이백 머신