Алгоритм RED

Цели разработки метода случайного раннего обнаружения

§ Предупреждение перегрузки. Метод случайного раннего обнаружения пред­назначен не для реагирования на возникновение перегрузки, а для ее пре­дотвращения.

§ Предотвращение глобальной синхронизации. Когда маршрутизатор обнару­живает перегрузку, он должен решить, которому соединению (или соеди­нениям) предложить снизить скорость передачи данных. В применяемом сегодня варианте этого метода данное уведомление является неявным и про­является в потере пакетов. Обнаруживая перегрузку заранее и уведомляя о ней только те соединения, которые требуется, этот метод позволяет избе­жать глобальной синхронизации.

§ Предотвращение дискриминации источников неравномерного трафика. С боль­шой вероятностью перегрузка в сети начинается с поступления большого объема данных от одного или нескольких источников. Этот всплеск актив­ности добавляется к текущей нагрузке на маршрутизатор. Если для отбра­сывания выбираются только прибывающие пакеты, тогда велика вероят­ность того, что алгоритм отбрасывания пакетов будет направлен в основном против источников с непостоянной скоростью передачи данных.

§ Ограничение средней длины очередей. Метод случайного раннего обнаруже­ния должен уметь контролировать среднюю длину очередей и, следователь­но, среднюю задержку.

вычислить среднюю длину очереди avg

если avg < ТН_min

установить пакет в очередь

иначе если ТН_min < avg < ТН_max

вычислить вероятность Рa

с вероятностью Ра

отбросить пакет

иначес вероятностью 1 - Рa

установить пакет в очередь

иначе если avg > ТН_max

отбросить пакет

Каждый раз, когда новый пакет поступает в выходную очередь с дисциплиной FIFO, этот алгоритм выполняет две функции. Первый шаг заключается в вычис­лении средней длины очереди avg. Средняя длина очереди сравнивается с двумя уровнями. Если средняя длина очереди avg меньше нижнего предела ТНmin, то перегрузка считается минимальной или отсутствующей и пакет помеща-

ется в очередь. Если значение avg больше верхнего предела ТНmax, то перегрузка считается серьезной и пакет отбрасывается. Если значение avg нахо­дится между двумя предельными значениями, тогда мы попадаем в область пе­регрузки. В этой области вычисляется вероятность выбрасывания пакета Р_α, зави­сящая от точного значения средней длины очереди avg и увеличивающаяся при приближении значения avg к верхнему пределу. Когда средняя длина очереди находится в этой области, пакет отбрасывается с вероятностью Р„ и ставится в оче­редь с вероятностью 1 - Ра.

По сути, первая часть алгоритма (вычисление средней длины очереди) опреде­ляет допустимый уровень неравномерности трафика, а вторая часть алгоритма — частоту отбрасывания пакетов при данном уровне перегрузки.

На рисунке показан результат эмуляции, в которой алгоритм RED сравнива­ется с политикой обрубания хвостов (drop-tail policy), когда прибывающий пакет просто отбрасывается, если в очереди нет свободного места. При высоких уровнях перегрузки алгоритм RED заметно превосходит политику обрубания хвостов, обеспечивая более высокую пропускную способность.