В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 126
Текст из файла (страница 126)
Наиболее важный вариант схемы упреждающего отбрасывания пакетов впервые упоминается в [88 [ как случайное раннее обнаружение (Каш1шв Еаг1у 1)егесйоп, КЕР). Схема случайного раннего обнаружения была реализована многими производителями. В данном разделе мы сначала обсудим побудительныс причины для применения схемы КЕР и цели ее разработки, после чего перейдем к деталям. Мотивация Когда в сети возникает перегрузка, буферы маршрутизаторов переполняются и маршрутизаторы начинают терять пакеты.
Для ТСР-графика это является сигналом о необходимости перехода в фазу затяжного пуска для снижения нагрузки на сетг и устранения перегрузки. У данного сценария есть два недостатка. Во-первых, потерянные пакеты необходимо передавать повторно, что увеличивает нагрузку на сеть и является причиной значительных задержек в ТС1хпотоках. Более серьезный феномен называется глобалыгой синхроназа|1ией (я!оЬа1 зулсЬгошха|юп), при которой имеет место следующая ситуация.
В случае резкого увеличения объемов графика очереди переполняются, и множество пакетов теряется. Как правило, это затрагивает многие ТСР-соединения, в результате опи переходят в фазу затяжного пуска, суммарный объем сетевого графика резко падает и в течение определенного периода сеть используется не в полной мере. Поскольку многие ТСР-соединения переходят в фазу затяжного пуска примерно в одно и то же вреьи, они и выходят из этого режима также приблизительно одновременно, что вызывает очередное резкое увеличение объемов графика в сети и новый цикл «ггзобилия и голодания». Одно из решений заключается в использовании на каждом маршрутизаторе буферов большего размера для снижения вероятности потери пакетов.
У такого подхода есть два недостатка. Во-первых, когда эти большие буферы заполняются, задержки во всех соединениях возрастают во много раз. Еще хуже ситуация в случае самоподобного графика (что весьма вероятно). Тогда построить достаточно большие буферы невозможно в принципе. Больцше всплески активности отправителей могут воз>гикать ггруг за другом, поддерживая состояние перегрузки, и потребности в буферах при атом будут расти до бесконечности. Лучшее решение состоит в том, чтобы предвидеть наступление перегрузки и предлагать то одному, то другому ТСР-сообшению снизить скоросп передачи данных. Затем определяется эффект этого замедления, после чего, в случае необходимости, замедляется другое соединение. Подобным образом, когда начинается перегрузка, торможение графика осуществляется постепенно, с минимальным воздействием на ТСР-соединения и без глобальной синхронизации, Именно такое решение реализовано в методе КЕР.
548 Глава 17. Интегрированные и дифференцированные службы 17.3. Случайное раннее обнаружение 549 Цели разработки метода случайного раннего обнаружения Цели, которые преследовались при разработке метода случайного раннего об о на ружения, перечислень) далее [831: + Предуттреждеиие пераг)нузки. Метал случайного раннего обнаружен„„, назначен не для реагирования на возникновение перегрузки, а для ее „ дотвращения. + Предотпращнние глобальной синхронизации.
Когда маршрутизатор б живает перегрузку, он должен решит)в которому соединению (или соедн ненинм) пРелложить снизить скоРостт пеРеДачи Данных. В пРименаемо)и сегодня варианте этого метода данное уведомление является неявным и про является в потере пакетов. Обнаруживая перегрузку заранее т( уведоьитяя о ней только те соединения, которые требуется, этот метод позволяет избежать глобальной синхронизации. + Предотвращениедискрилтинации источникоанераенамерного трафика.
С бот,— шой вероятностью перегрузка в сети начинается с поступления большого объев(а данных от одного ильи нескольких источников. Этот всплеск активности добавляется к текущей нагрузке на маршрутизатор. Если для отбрасывания выбираются только прибываюшие пакеты, тогда велика вероятность того„что алгоритм отбрасывания пакетов будет направлен в основном против источников с непостоянной скоростью передачи данных. + Ограничение средней длины очередей'. Метод случайного раннего обнаружения должен уметь контролировать среднюю длину очередей и, следовательно, среднюю задержку.
Алгоритм йЕ0 В обших чертах алгоритм случайного раннего обнаружения для каждого прибыв- шего пакета выглядит следующим образом: вычислить среднюю длину очереди акд если акд < ТН... усгановить панет в очередь иначе если ТН„. < аид < ТН,.„ вычислить вероятность Р, с вероятностью Р, отбросить пакет иначе с вероятностью 1 — Р, установить пакет в очередь иначе если атд < ТН, отбросить пакет Каждый раз, котла новый пакет поступает в выходную очередь с дисциплиной Е)ГО, этот алгоритм выполняет две функции. Первый шаг заключается в вычис ленин средней длины очереди ттд. Средняя длина очереди сравнивается с двумя уровнями (рис.
17.7). Если средняя длина очереди аоя меньше нижнего предел~ ТГ) ... то перегрузка считается минимальной или отсутстнуюшей и пакет помеШа- ~ ется в очередь. Если значение аюд больше или равно верхнему пределу ТЕ( „, то перегрузка считается серьезной и пакет отбрасывается. Если значение атп находится между двул(я предельными значениями, тогда мы попадаем в область перегрузки. В атой области вычисляется вероятность выбрасывания пакета Р„, зависяшая от точного значения средней длины очереди асЯ и увеличивающаяся при приближении значения ась к верхнему пределу. Когда средняя длина очереди находится в атой области, пакет отбрасывается с вероятностью Р, и ставится в очередь с вероятностью 1 — Р .
77 Еык ) Ниик Пакеты не отбрасываются Пакеты отбрасываются с растущей вероятностью Р'и Пакеты отбрасываются Рис. 17.7. Буфер маршрутизатора при использовании алгоритма РЕ0 Нниииализация акд ь — О соипЕ ь — -1 Е)ля кандого прибываююего пакета Вьнислить среднюю длину очереди если очередь не пуста (то есть О О) а д ь — (1 — кь) акд ь, о иначе ку < — 7(гтлю - О Етлю] акд ь- (1 - ьЬ) акд + к; О Определить несбходиность отбрасывания пакета если аид < % . пакет ставится в очередь ссилг ( — -1 иначе если 7Н„, < акд < ТН увеличить соил( Р, ь — Р, (акд - 7Н...)7(ГН, — 7Н...) Р, т — Рту(1 соипЕ х Рд с вероятностью Р. отбросить пакег ссипЕ ь — О иначе с вероятностью 1 - Р, установить пакет в очередь иначе если акд > ТН'...
отбросить пакет соил( ь- О Ко~да очередь опустеет О Етке ь — Ение По сути, первая часть алгоритма (вычисление средней длины очереди) определяет допустимый уровень неравномерности графика, а вторая часть алгоритма— частоту отбрасывания пакетов прти данном уровне перегрузки. Теперь можем подробнее изучить алгоритм случайного раннего обнаружения.
550 Глава 17. У1нгегрированные и дифференцированные службы 17зй Случайное раннее обнаружение 551 Далее перечисленга обозначения, использованные в этом алгоритме: + Сохраняемые переменные: асд — средний размер очереди; +»7 г(те — время освобождения очереди; соипг — счетчик пакетов, начиная с последнего отброшенного пакета, + Константы: 軄— вес очереди; П(ььь минимальное для очереди пороговое значение; + ТН„,„„— максимальное для очереди пороговое значение; + Р„,„„— максимальное значение Рь.
+ Другие обозначения: + Р. — текущая вероятность отбрасывания пакета; Рь — временная расчетная вероятность; + д — текущий размер очереди; Вше — текущее время; + 7(Г) — линейная функция времени й Вычисление среднего размера очереди Средний размер очереди вычисляется методом экспоненциально взвешенного среднего значения предыдуп1их размеров очередей. В инструкции если учитываются периоды, в течение которых очередь пуста, путем оценки количества небольших пакетов и, которые мог бы передать маршрутизатор за время простоя.
Может возникнуть вопрос, почему используется среднее значение размера очереди, тогда как проще было бы использовать ее текущий размер. Цель использования среднего значения заключается в том, чтобы отфильтровать кратковременные периоды перегрузки маршрутизатора. Вес ю, определяет скорость изменения среднего размера очереди аь8 в ответ на изменения фактического размера очереди. В [83( рекомендуется совсем неболыпая величина 0,002.
В результате значение ага значительно отстает от изменений фактического размера очереди. Использование небольшого весового коэффициента не позволяет алгоритму реагировать на кратковременную перегрузку. Принятие решения об отбрасывании пакета Если средний размер очереди ас8 меньше нижнего предела ТН„„„, то поступивший пакет помещается в очередь, а если значение агя больше или равно верхнему пределу 7Н„„то поступивший пакет автоматически отбрасывается. Критическая область для значения ас5 находится меькду этими двумя предельными значениями.
В этой области алгоритм случайного раннего обнаружения назначает каждому поступившему пакету вероятность отбрасывания в зависимости от двух факторов: + Чем ближе значение аьк к верхнему пределу ТН,„» тем выше вероятность отбрасывания пакета. + Пока значение аиа находится в критической области, в счетчике соипг учитывается, сколько последовательных пакетов избежали отбрасывания.
Чем выше значение счетчика соилг, тем выше вероятность отбрасывания пакета. Кратко поясним работу описанного алгоритма КЕП, Сначала вычисляется временная нероятность Р», линейно увеличивающаяся от 0 при аг»д = ТН.„„до некого максимального значения Р, .„при аиК = ТН „„. Для большей ясности введем величину Р, представляющую собой относительную долю критической области от ее нижней границы до значения аг»а: 5-Тн,„ь Р= Т̈́— ТН,„„ При этом мы получаем: Рь = Р.
Р ., 0 < Р < 1. Вероятностные явления характеризуются тем, что создают кластеры, Например, если мы будем много раз подбрасывать монету, то мы не можем ожидать равномерного чередования орлов и решек. Вместо этого будут возникать кластеры из следующих подряд орлов, кластеры из почти одних решек и т. д., но при усреднении за большой период доля выпадающих орлов и решек будет одинаковой.
В алгоритме ВЕП желательно отбрасывать пакеты относительно равномерно, чтобы неравномерный источник пакетов не был наказан строже равномерного. Поатому вместо использования вероятности Рь напрямую она учитывается в вычислении второй вероятности Р„, которая и применяется для принятия решения об отбрасывании пакета. Подставляя значение Р в формулу Р„имеюпьуюся в гап.оритме, получим следующее выражение: РР„»„ 1 — соипГ - РР,„ 1 1 — сои»»Г . Р— гоипг —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
