Рассмотрим общий принцип функционирования базового алгоритма RED. Алгоритм состоит из двух частей: оценка среднего размера очереди и принятие решения о сбросе вновь поступившего пакета. При поступлении каждого нового пакета, используя фильтр высоких частот совместно с «экспоненциально взвешенной скользящей средней» EWMA (low-pass filter with an exponentially weighed moving average), RED определяет средний размер очереди avg. Далее значение avg сравнивается со значениями ранее определенных границ: верхней max_th и нижней min_th, которые определяют степень нагрузки в очереди.

В случае если значение avg принадлежит интервалу [0; min thj, то поступающий пакет помещается в очередь, если же значение avg принадлежит интервалу [min_ch; rr.ax_thj, то вычисляется вероятность сброса пакета Р_а, и либо с вероятностью Р₀осуществляется сброс поступающего пакета, либо с вероятностью (1 - Р₀) поступающий пакет помещается в очередь. Если же значение среднего размера очереди avg превышает значение max_th, то поступающий пакет обязательно сбрасывается. Заметим, что вероятность сброса пакета является функцией от переменной avg, т.е. с повышением нагрузки повышается вероятность сброса поступающего пакета. Метакод алгоритма представлен на рис. 2.50, а на рис. 2.51 - графическая интерпретация RED.

Следует отметить, что RED также имеет возможность осуществлять не сброс пакетов, а маркировку. Маркировка может быть произведена посредством изменения какого-либо бита в каком-либо опциональном поле в заголовке пакета с целью извещения протокола транспортного уровня, например, TCP, о надвигающейся или наступившей перегрузке. Тогда в этом случае, если в приемнике реализован протокол, «понимающий» маркирование пакета, то протокол приемника должен понизить размер окна rwnd и, тем самым, сообщить источнику о необходимости понижения нагрузки. В результате этого источник должен уменьшить размер окна cwnd и, тем самым, понизить количество пакетов, передаваемых в сеть за некоторый промежуток времени. Реализация маркировки пакета в RED более эффективна, чем реализация сброса в Случае функционирования на транспортном уровне протокола, подобного TCP, а в случае если осуществляется управление потоками UDP, то RED должен реализовывать функцию сброса.

Рис. 2.50. Метакод базового алгоритма RED

Рис. 2.51. RED: вероятность потери пакета увеличивается с увеличением среднего размера очереди Таким образом, RED состоит из двух различных алгоритмов: с помощью алгоритма вычисления среднего размера очереди фактически вычисляется степень пачечности нагрузки, которая может быть принята буфером; алгоритм подсчета вероятности маркировки или сброса пакета на основе известного значения нагрузки (т.е. значения средней длины очереди) определяет как часто маршрутизатор маркирует или сбрасывает пакеты. Целью функционирования RED в маршрутизаторе является такая реализация маркировки/сброса пакетов, при которой будет соблюдаться принцип «справедливого распределения ресурсов» и избегание «глобальной синхронизации».

⇐Алгоритм red | Управление трафиком и качество обслужевания в сети | Принцип функционирования расширенного алгоритма red⇒