Random early detection

Z Wikipedii

Random early detection (RED) - znany również jako random early drop, jest algorytmem kolejkowania. Jest on również algorytmem unikania zakleszczeń.

W tradycyjnym algorytmie "obcinania ogona", router lub inne urządzenia sieciowe buforuje tyle pakietów ile tylko może i po prostu odrzuca resztę, której nie może zbuforować. Jeżeli bufory są ciągle pełne, sieć zakleszcza się. "Odrzucanie ogona" rozdziela miejsce w buforze nierównomiernie. Może to prowadzić do globalnej synchronizacji TCP jak również, do wstrzymania połączeń TCP jednocześnie. Sieci stają się zalane pakietami synchronizacyjnymi.

RED rozwiązuje ten problem monitorując średnią wielkość kolejki i odrzuca (lub oznacza jeżeli jest połączony z ECN) bazując na prawdopodobieństwach statystycznych. Jeżeli bufor jest prawie pusty, wszystkie przychodzące pakiety są akceptowane. W miarę jak kolejka rośnie wzrasta prawdopodobieństwo odrzucenia przychodzącego pakietu. Kiedy bufor jest pełny prawdopodobieństwo osiąga 1 przez co wszystkie pakiety są odrzucane.

RED sprawia, że rozróżnienie Quality of Service (QoS) staje się niemożliwe. Weighted RED (WRED) i RED In/Out (RIO) zapewniają wczesne wykrywanie, jak również QoS.