Модель обработки приоритетных очередей в маршрутизаторах

Различают виды задержек: аппаратные и программные; фиксированные и переменные.

Составляющие  фиксированной задержки:

- задержка распространения рассчитывается в зависимости от расстояния между исходной точкой и точкой назначения. В расчетах обычно принимают задержку распространения равной 6 мкс на километр;

- интерфейсная задержка (задержка при передаче в канал) возникает в процессе помещения битов во внешний интерфейс. Интерфейсная задержка является существенной для каналов с пропускной способностью менее 768 кбит/с. В качестве иллюстративного примера, демонстрирующего разницу интерфейсной задержки можно привести следующие цифры. Помещение 1 байта на интерфейс 64 Кбит/с дает задержку в 125 μс. Тот же самый байт, помещенный на интерфейс 155 Мбит/с, дает задержку всего лишь в 0,05 μс;

- задержка обработки включает в себя алгоритмическую задержку и задержку пакетизации. Алгоритмическая задержка связана с обработкой голоса. Обычно она составляет от 1 до 30 μс для типовых кодеков. Задержка пакетизации возникает в процессе удержания голосовых образцов при помещении их в пакет IP до тех пор, пока их достаточное количество не заполнит этот пакет.

Таблица 1.1 –  Характеристики смешанного трафика

Вид трафика	Пропускная способность	Задержка	Время реакции (время ответа)	Взрывообразность
Данных	mах	min	-	10
Транзакций	max	min	От 1 до 3 сек	10
Реального времени	Не более 128Кб/с	<0,1сек <0,3 сек	-	0,2

 

Составляющие  переменной задержки:

- задержка в очереди вызвана ожиданием обслуживания предшествующих пакетов на интерфейсе. Время ожидания сильно зависит от размера тех пакетов, которые находятся во главе очереди. Для того чтобы минимизировать этот тип задержки, необходима соответствующая конфигурация маршрутизаторов;

- задержка в воспроизводящем буфере образуется на приемном конце при выравнивании возникающей вариации задержки голосовых пакетов.

Существуют  рекомендации ITU по допустимым уровням  суммарной задержки: 100 μс — высокое качество; 300 μс- среднее качество.

Для совместимости  с программным обеспечением и  сетевым оборудованием можно  использовать параметры соглашения SLA.

SLA используется  внутри организации для регулирования  взаимоотношений между подразделениями,  а также является основным  инструментом непрерывной оценки  и управления качеством предоставления  услуг аутсорсинга специализированной организацией — аутсорсером.

Как правило  термин SLA используется применительно к ИТ и телекоммуникационным услугам. В таком соглашении может содержаться детальное описание предоставляемого сервиса, в том числе перечень параметров качества, методов и средств их контроля, времени отклика поставщика на запрос от потребителя, а также штрафные санкции за нарушение этого соглашения. Для того, чтобы соблюсти SLA, поставщик услуг в свою очередь заключает операционное соглашение об уровне услуг (OLA) с другими внутренними подразделениями от которых зависит качество предоставления услуг.

SLA как  особый сервис позволяет сконфигурировать  аппаратное и программное обеспечение  для максимизации использования  пропускной способности.

1.2 Анализ  существующих алгоритмов обработки  приоритетных очередей в маршрутизаторах

Большинство современных маршрутизаторов имеют  встроенные функции организации  приоритетных очередей, которые позволяют  обслуживать в первую очередь  определенные виды трафика. Например, администратор может указать, что  трафик к определенной группе адресов  для некоторых приложений должен иметь более высокий приоритет, чтобы уменьшить задержку. Это  особенно важно в больших распределенных сетях.

Метод приоритетных очередей наиболее часто используется для предоставления временных гарантий чувствительным к задержкам приложениям. Его возможностей может быть достаточно для трафика некоторых протоколов. Данный метод может применяться для передачи аудио- и видеоинформации, когда не требуется высокое качество. Для доставки аудио- и видеоинформации с высоким качеством необходимо гарантировать низкую задержку и небольшой эффект дрожания. Этого трудно добиться в сетях без значительных накладных расходов при резервировании буферного пространства маршрутизаторов и без реализации сложных алгоритмов обработки очередей.

На данный метод не существует единого стандарта. Отдельные его части описаны  в разных стандартах. Каждый производитель  сетевого оборудования реализует в  своих изделиях собственные алгоритмы  обработки очередей. Например, компания Cisco Systems использует алгоритм взвешенной справедливой очереди с ранним обнаружением ошибок, а компания Bay Networks — очередь, основанную на классах.

Если  маршрутизатор получает пакеты быстрее, чем он может отправить их через  данный порт, он помещает пакеты в очередь. Затем, в простейшем случае, они отправляются в порядке поступления, то есть реализуется  принцип «первым пришел, первым ушел»  — FIFO_(First In, First Out). Такой алгоритм довольно эффективен, но опыт управления сетями показывает, что он далеко не оптимален (рисунок 1.1).

Случайное раннее обнаружение (Random Early Detection, RED) представляет собой альтернативу очередям FIFO. Этот метод позволяет смягчить эффект от потери пакетов даже при очень больших нагрузках. Такая очередь по-прежнему использует принцип FIFO, но пакеты отбрасываются случайным образом (вместо того, чтобы отбрасывать сообщения из конца очереди), когда средняя длина очереди за данный промежуток времени превосходит установленное значение. Этим достигается оптимизация заполнения очереди. Данный алгоритм был изначально придуман для протокола TCP, но он может быть применим к трафику любого протокола, когда сеть не гарантирует доставки.

Рисунок 1.1- Алгоритм обработки пакетов по принципу «Первым пришел- первым обслужился»

Другой  подход к борьбе с перегрузкой  в объединенных сетях представляет собой упреждающее отбрасывание пакетов, т.е. маршрутизатор отбрасывает  один или несколько входящих пакетов  прежде, чем переполнится выходной буфер. Упреждающее отбрасывание пакетов  может быть реализовано в одной  или нескольких очередях.

Наиболее  важный вариант схемы упреждающего отбрасывания пакетов называется случайное  раннее обнаружение. Сначала обсудим  причины для применения схемы RED и цели ее разработки, после чего перейдем к деталям.

Когда в  сети возникает перегрузка, буферы маршрутизаторов переполняются  и маршрутизаторы начинают терять пакеты. Для TCP-трафика это является сигналом о необходимости перехода в т.н. «фазу затяжного пуска» для снижения нагрузки на сеть и устранения перегрузки. Это достаточно простая процедура, когда в начале передачи данных окно соединения устанавливается равным 1, а при получении каждого последующего подтверждения окно увеличивается  на 1, пока не достигнет максимума. 

У данного  сценария есть два недостатка. Во-первых, потерянные пакеты необходимо передавать повторно, что увеличивает нагрузку на сеть и является причиной значительных задержек в TCP-потоках. Более серьезный  феномен называется глобальной синхронизацией, при которой имеет место следующая  ситуация. В случае резкого увеличения объемов трафика очереди переполняются, и множество пакетов теряется. Как правило, это затрагивает  многие TCP-соединения, в результате они переходят в фазу затяжного  пуска, суммарный объем сетевого трафика резко падает и в течение  определенного периода сеть используется не в полной мере. Поскольку многие TCP-соединения переходят в фазу затяжного  пуска примерно в одно и то же время, они и выходят из этого  режима также приблизительно одновременно, что вызывает очередное резкое увеличение объемов трафика в сети и новый  цикл «изобилия и голодания».

Одно  из решений заключается в использовании  на каждом маршрутизаторе буферов большего размера для снижения вероятности  потери пакетов. У такого подхода  есть два недостатка. Во-первых, когда  эти большие буферы заполняются, задержки во всех соединениях возрастают во много раз. Еще хуже ситуация в  случае самоподобного трафика (инвариантный относительно изменения масштаба) –  повторяющийся во всех масштабах  времени. Тогда построить достаточно большие буферы невозможно в принципе. Большие всплески активности отправителей могут возникать друг за другом, поддерживая состояние перегрузки, и потребности в буферах при  этом будут расти до бесконечности. 

Лучшее  решение состоит в том, чтобы  предвидеть наступление перегрузки и предлагать то одному, то другому TCP-сообщению снизить скорость передачи данных. Затем определяется эффект этого замедления, после чего, в  случае необходимости, замедляется  другое соединение. Подобным образом, когда начинается перегрузка, торможение трафика осуществляется постепенно, с минимальным воздействием на TCP-соединения и без глобальной синхронизации. Именно такое решение реализовано в методе RED.

Предупреждение  перегрузки.

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

Предотвращение  глобальной синхронизации.

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

Предотвращение  дискриминации источников неравномерного трафика.

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

Ограничение средней длины очередей.

Метод случайного раннего обнаружения (рисунок 1.2) должен уметь контролировать среднюю длину очередей и, следовательно, среднюю задержку.

Каждый  раз, когда новый пакет поступает  в выходную очередь с дисциплиной FIFO, этот алгоритм выполняет две  функции.

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

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

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

 

Рисунок 1.2 – Алгоритм протокола случайное раннее обнаружение

Рисунок 1.3 – Работа алгоритма RED

Очередь с приоритетами — это алгоритм, при котором несколько очередей FIFO или RED образуют одну очередь. Трафик распределяется между этими очередями в соответствии с заданными критериями. При этом трафик отправляется в порядке строгой очередности: первым — трафик с высоким приоритетом, вторым — со средним и т. д.

Очереди на основе классов (Class-Based Queuing, CBQ) — это алгоритм, при котором трафик делится на несколько классов. Каждый класс имеет собственную очередь и ему выделяется некоторая часть пропускной способности канала.

Взвешенная  справедливая очередь (Weighted Fair Queuing, WFQ) — частный случай CBQ, когда классам соответствуют независимые потоки. Каждому классу соответствует одна очередь FIFO и ей отводится некоторая часть пропускной способности канала. При этом происходит перераспределение "пропускной способности между потоками. Выделение дополнительной пропускной способности для больших потоков позволяет уменьшить задержку при их обработке.

Интерфейсом к очередям передачи пакетов служит протокол резервирования ресурсов (Resource Reservation Protocol — RSVP). Этот протокол позволяет системам запрашивать сервисы у сети, например, гарантированную пропускную способность, максимальный уровень потерь пакетов или предсказуемую задержку (RFC 2205).