Алгоритмы управления очередями

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

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

Оценка возможной длины очередей в сетевых устройствах позволила бы определить параметры качества обслуживания при известных характеристиках трафика. Однако изменение очередей представляет собой вероятностный процесс, на который влияет множество факторов, особенно при сложных алгоритмах обработки очередей в соответствии с заданными приоритетами или путем взвешенного обслуживания разных потоков. Анализом очередей занимается специальная область прикладной математики — теория массового обслуживания (queuing theory), однако получить с ее помощью количественные оценки можно только для очень простых ситуаций, не соответствующих реальным условиям работы сетевых устройств. Поэтому служба QoS использует для поддержания гарантированного уровня качества обслуживания достаточно сложную модель, решающую задачу комплексно. Это делается с помощью следующих методов:

• предварительное резервирование пропускной способности для трафика с известными параметрами (например, для средних значений интенсивности и величины блока пакетов);
• принудительное профилирование входного трафика для удержания коэффициента нагрузки устройства на нужном уровне;
• использование сложных алгоритмов управления очередями.

АЛГОРИТМЫ ОБРАБОТКИ ОЧЕРЕДЕЙ

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

· традиционный алгоритм FIFO;

· приоритетное обслуживание (Priority Queuing), которое также называют «подавляющим»;

· настраиваемые очереди (Custom Queuing);

· взвешенное справедливое обслуживание (Weighted Fair Queuing, WFQ).

Каждый алгоритм разрабатывался для решения определённых задач и поэтому специфическим образом воздействует на качество обслуживания различных типов трафика в сети. Возможно комбинированное применение этих алгоритмов.

Принцип алгоритма FIFO состоит в следующем. В случае перегрузки пакеты помещаются в очередь, а если перегрузка устраняется или уменьшается, пакеты передаются на выход в том порядке, в котором поступили («первым пришел — первым ушел», First In — First Out). Этот алгоритм обработки очередей по умолчанию применяется во всех устройствах с коммутацией пакетов. Он отличается простотой реализации и отсутствием потребности в конфигурировании, однако имеет принципиальный недостаток — дифференцированная обработка пакетов различных потоков невозможна. Очереди FIFO необходимы для нормальной работы сетевых устройств, но они не справляются с поддержкой дифференцированного качества обслуживания.

ПРИОРИТЕТНОЕ ОБСЛУЖИВАНИЕ

Механизм приоритетной обработки трафика предусматривает разделение всего сетевого трафика на небольшое количество классов с назначением каждому классу некоторого числового признака — приоритета. Разделение на классы (классификация) может производиться разными способами.

Классификация трафика представляет собой отдельную задачу. Пакеты могут разбиваться на классы по приоритетам в соответствии с типом сетевого протокола, например, IP, IPX или DECnet (заметим, что такой способ подходит только для устройств, работающих на втором уровне), на основании адресов получателя и отправителя, номера порта TCP/UDP и любых других комбинаций признаков, содержащихся в пакетах. Правила классификации пакетов на приоритетные классы являются составной частью политики управления сетью.

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

Этот вариант классификации требует наличия в пакете специального поля, куда может заноситься заданное значение приоритета, чтобы им могли воспользоваться все последующие сетевые устройства для обработки трафика на пути его следования. Такое поле имеется в заголовке многих протоколов. Так, в пакете IP для этой цели предусмотрено трехразрядное подполе IP Precedence в поле Type Of Service (TOS). Когда специального поля приоритета не предусмотрено, новый заголовок с таким полем вводится при помощи специально разработанного дополнительного протокола. В частности, для протокола Ethernet (и других протоколов семейства 802) были приняты спецификации IEEE 802.1Q/p, которые определяют дополнительное трехразрядное поле приоритета.

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

Независимо от выбранного способа классификации трафика, в сетевом устройстве имеется несколько очередей, в соответствии с количеством классов. Поступивший в период перегрузки пакет помещается в очередь согласно его приоритету. На Рисунке 1 приведен пример использования четырех приоритетных очередей: с высоким, средним, нормальным и низким приоритетом. Приоритеты очередей имеют абсолютный характер предпочтения при обработке: пока из более приоритетной очереди не будут выбраны все пакеты, устройство не переходит к обработке следующей, менее приоритетной. Поэтому пакеты со средним приоритетом всегда обрабатываются только тогда, когда очередь пакетов с высоким приоритетом пуста, а пакеты с низким приоритетом — только когда пусты все вышестоящие очереди.

Конечный размер буферной памяти сетевого устройства предполагает некоторую предельную длину каждой очереди. Обычно по умолчанию всем приоритетным очередям отводятся буферы одинакового размера, но многие устройства разрешают администратору выделять каждой очереди индивидуальный буфер. Его максимальная длина определяет предельное количество пакетов, которые могут храниться в очереди данного приоритета. Пакет, поступивший в то время, когда буфер заполнен, просто отбрасывается.

Приоритетное обслуживание очередей обеспечивает высокое качество сервиса для пакетов из самой приоритетной очереди. Если средняя интенсивность их поступления в устройство не превосходит пропускной способности выходного интерфейса (и производительности внутренних блоков самого устройства, участвующих в продвижении пакетов), то пакеты с наивысшим приоритетом всегда получают ту пропускную способность, которая им необходима. Что же касается остальных классов приоритетов, то качество их обслуживания ниже, чем у пакетов с наивысшим приоритетом, причем предсказать уровень снижения затруднительно. Оно может быть довольно существенным, если высокоприоритетные данные передаются с большой интенсивностью.

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

ВЗВЕШЕННЫЕ НАСТРАИВАЕМЫЕ ОЧЕРЕДИ

Алгоритм взвешенных очередей (Weighted Queuing) разработан для того, чтобы для всех классов трафика можно было предоставить определенный минимум пропускной способности или удовлетворить требования к задержкам. Под весом какого-либо класса понимается доля выделяемой данному виду трафика пропускной способности выходного интерфейса. Алгоритм, в котором вес классов трафика может назначаться администратором, называется «настраиваемой очередью» (Custom Queuing). Именно его мы и будем рассматривать. В случае, когда веса назначаются автоматически, на основании некоторой адаптивной стратегии, реализуется так называемый алгоритм «взвешенного справедливого обслуживания» (Weighted Fair Queuing, WFQ), ему будет посвящен следующий раздел.

Как при взвешенном, так и при приоритетном обслуживании, трафик делится на несколько классов, и для каждого вводится отдельная очередь пакетов. С каждой очередью связывается доля пропускной способности выходного интерфейса, гарантируемая данному классу трафика при перегрузках этого интерфейса. В примере, приведенном на Рисунке 2, устройство поддерживает пять очередей для пяти классов трафика. Этим очередям соответствует 10, 10, 30, 20 и 30% пропускной способности выходного интерфейса при перегрузках.

Поставленная цель достигается благодаря тому, что очереди обслуживаются последовательно и циклически, и в каждом цикле из каждой очереди забирается такое число байт, которое соответствует весу очереди. Например, если цикл просмотра очередей в рассматриваемом примере равен 1 сек, а скорость выходного интерфейса составляет 100 Мбит/с, то при перегрузках в каждом цикле из первой очереди забирается 10 Мбит данных, из второй тоже 10 Мбит, из третьей — 30 Мбит, из четвертой — 20 Мбит, из пятой — 30 Мбит. В результате каждому классу трафика достается гарантированный минимум пропускной способности, что во многих случаях является более желательным результатом, чем подавление низкоприоритетных классов высокоприоритетным.

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

Лекция 3: Механизмы профилирования и формирования трафика

1. Случайное ранее обнаружение.

Технология RED представляет собой механизм профилирования трафика для предотвращения перегрузок. RED работает с ТСР и исполняет алгоритм реакции ТСР на потерю пакетов. В алгоритме используется 2 конфигурационных уровня. Когда уровень перегрузки ниже первого порога, то пакеты не отбрасываются. Когда уровень перегрузки находится между 2-мя порогами, то пакеты отбрасываются с линейно-возрастающей вероятностью от 0 до величины отбрасывания. Когда перегрузка превышает верхний порог, то пакеты отбрасываются со 100% вероятностью. В качестве показателей перегрузки берется средняя длина очереди пакетов, относящаяся к определенному сеансу.

2. Алгоритм «дырявого ведра».

Разработан для профилирования пульсирующего трафика, позволяет проверить соблюдения трафика, определить значение средней скорости и значение пульсации. Используются следующие параметры: Т – период усреднения скорости, С/R среднюю скорость, которую трафик не должен превышать. Вс – объем пульсации, объем соответствующие средней скорости трафика, Ве – превышение объема пульсации.

Вс/Т = С/R.

В алгоритме предполагается, что скорость контролируется каждые Т-секунд. Контролируется на основе подсчета объема, поступившего за период времени. Если этот объем меньше или равен значению Вс, то фактическая скорость будет меньше или равна С/R. При превышении объема пульсации величины Вс+Ве – кадры отбрасываются. Алгоритм использует счетчик С поступивший от пользователя. Каждые Т-секунд – этот счетчик отбрасывается. Все кадры, данные которых не увеличили значение счетчика выше порога Вс и передаются в сеть. Работает в рамках сети GCRA и других вычислительных сетях.

3. «Ведро токенов».

Алгоритм применяется для формирования трафика с целью уменьшения неравномерности продвижения пакетов. Под токеном понимается некий абстрактный объект – носитель информации. Генератор токенов периодически отправляет токен в ведро с ограниченным объемом b байт. Все токены имеют одинаковый объем m, и ведро заполняется со скоростью r байт в секунду. Скорость r является средней желаемой скоростью для данного потока. Пакеты поступают в систему и заполняются в в буфере объемом К байт. Из очереди пакет будет продвигаться только в том случае, если ведро токенов будет заполнено до уровня М байт, где М – объем пакета. Если это условие выполняется, то пакет продвигается на выход и из ведра удаляются токены общим объемом в М байт с точностью m байт. Если ведро заполнено недостаточно, то пакет ожидает поступления нужного числа токенов.

ОБЩАЯ ХАРАКТЕРИСТИКА ПРОТОКОЛОВ QOS IP

Протоколы и механизмы поддержки качества обслуживания в сетях IP делятся на две категории в зависимости от уровня гарантий предоставляемого сервиса:

· протоколы поддержки «твердого» качества сервиса гарантируют обслуживание потоков данных путем резервирования ресурсов;

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

Протоколы первой категории разрабатываются рабочей группой IETF по интегрированным сервисам (Integrated Services Working Group, IntServ). Базовая модель такого сервиса предполагает интегрированное взаимодействие всех устройств сети по обеспечению требуемого качества обслуживания вдоль всего пути потока.

IETF занимается разработкой IntServ достаточно давно — в рамках этого направления проблема обеспечения QoS в сетях TCP/IP впервые стала решаться систематически. Однако ввиду значительной сложности поддержки интегрированных сервисов в масштабах такой сети, как Internet, свое развитие получило и другое направление, которое в данный момент ведет рабочая группа по дифференцированным сервисам (Differentiated Services Working Group, DiffServ). Она специализируется на протоколах второй категории, которые не обеспечивают «настоящего» гарантированного качества обслуживания, но зато гораздо проще в реализации.

Сервисы DiffServ опираются на ту же обобщенную модель QoS, что и сервисы IntServ, однако для них резервирование ресурсов сетевых устройств не предусматривается. Вместо этого они сигнализируют о потребностях потока в обслуживании путем включения необходимой информации в каждый отдельный пакет — поле IP Precedence несет код, который интерпретируется каждым маршрутизатором сети для приоритетного или взвешенного обслуживания данного потока по отношению к другим.

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

Дата добавления: 2014-01-20