RED (random early detection) – 무작위 조기 탐지

RED는 큐를 관리하는 알고리즘이다. 전통적인 종단 탈락 (tail drop) 알고리즘은 버퍼에 가능한 한 많은 패킷들을 저장하고 있다가 더 이상 여유 공간이 없을 때, 나중에 도착하는 패킷을 무조건 탈락시킨다. 이 방식은 버퍼가 가득차는 경우가 빈번히 발생하게 되면, 그에 따라 네트웍 혼잡도가 증가하게 된다. 종단 탈락 알고리즘은 또한 트래픽 흐름 속에서 버퍼 공간을 불공평하게 배분한다. 종단 탈락 알고리즘은 모든 TCP 접속이 동시에 느려지면 글로벌 동기화의 원인이 될 수 있으며, 그로 인해 망 이용효율이 떨어지게 된다. RED는 이러한 문제점에 착안하여, 큐의 평균 크기를 감시하면서 통계적 확률에 의거 패킷을 탈락시킨다. 버퍼가 거의 비어있는 경우에는, 모든 패킷을 받아들이지만, 큐가 점점 차게 되면 들어오는 패킷이 탈락할 확률도 함께 증가한다. 확률이 1에 도달하면, 즉 버퍼가 가득 차면 모든 패킷들이 탈락된다. RED는 종단 탈락 알고리즘에 비해 좀더 공평하다고 간주되는데, 이는 많은 패킷을 전송한 호스트의 패킷 탈락 가능성이 더 커지기 때문이다. 게다가 RED의 조기 탐지 기능은 글로벌 동기화를 방지하는데 도움이 된다. RED는 기본적으로 QoS에 따른 차등 처리가 불가능하므로, 만약 그런 서비스가 필요하다면 조기 탐지를 할 때 어느 정도 QoS에 관해 고려해 주는 WRED (weighted RED)나 RIO (RED in/out)과 같은 알고리즘을 생각해볼 필요가 있다.