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

Таблица 2.1 – Результаты работы алгоритма WFQ

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

Приоритеты  задают на основании проектов стандартов 802.1p и 802.1Q, упрощающих задание приоритетов  для одного типа трафика (такого, как  мультимедиа) по отношению к другому (например, электронной почте). Проект стандарта 802.1p представляет собой расширение стандарта для мостов 802.1D, где  описывается способ реализации приоритетов  в мостах уровня MAC. Проект стандарта 802.1Q содержит схемы задания приоритетов  для виртуальных локальных сетей. Стандарт 802.1p обеспечивает преимущественную очередность и доступ к ресурсам за счет увеличенного размера кадра.

Рисунок 2.1 – Взвешенные настраиваемые очереди

Рисунок 2.2 – Алгоритм работы модели справедливой взвешенной очереди

При использовании  WFQ существует опасность, что приоритетный трафик полностью займет полосу пропускания, т.к. он обладает безусловным приоритетом перед трафиком, проходящим через очереди с более низким весом.

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

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

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

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

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

В результате анализа было выяснено, что очереди, в которые устанавливаются пакеты, различаются между собой по приоритету, который характеризуется пропускной способностью, портами выхода и/или назначения и суммарной задержкой. Таким образом, в разрабатываемой модели будет использоваться метод сложных алгоритмов управления очередями.

Входными  следует считать следующие параметрами: потоки пакетов 3-х разных приоритетов, время обработки пакета.

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

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

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

В модели пакеты принимаются с i-го порта, затем разбиваются на приоритетные классы (высокий, средний, низкий) (рисунок 2.3) в соответствии с типом сетевого протокола на основании адресов назначения и источника, например номера порта или поля IP- пакета.

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

Это можно  считать недостатком и предусмотреть  в разрабатываемой модели более  эффективный метод управляя полосой пропускания. Для определения необходимой пропускной способности необходимо измерить очереди и рассчитать приоритет обслуживания очереди.

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

Пакет обрабатывается в течение определенного времени, задаваемого системными часами. Распознавание  приоритета и помещение в одну из 3 очередей и обработка в течение  заданного времени. При перегрузках в маршрутизаторе недостаток размера очереди приводит к необходимости отбрасывания пакетов (рисунок 2.4).

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

А- идентификатор порта, посылающего  пакет высокого приоритета.

В- идентификатор порта, посылающего  пакет среднего приоритета.

Рисунок 2.3 – Алгоритм назначения приоритета

 

Рисунок 2.4 - Алгоритм обработки пакетов с отбрасыванием пакета по заданному критерию

 

Параметры разрабатываемой модели:

LR – Объем  ОЗУ коммутатора.

LO – 1/3 LR.

VH,C,B –  объем очередей.

VR – скорость  обработки модели.

Z – задержка i-пакета.

Р – пропускная способность канала.

V1 – Объем  передаваемой информации.

Рассматриваемый алгоритм модели представлен на рисунке 2.5.

 

 

Рисунок 2.5 - Алгоритм работы предлагаемой модели обработки приоритетных очереди

 

2.3 Выбор  средства реализации программной  модели

Для построения данной модели больше всего подходит язык моделирования GPSS, поскольку это средство моделирования позволяет организовывать работу в реальном времени дискретно- стохастические схемы. Альтернативным вариантом могло бы служить написание программы модели на языке C++, но основной проблемой при данном подходе является задание реального времени.

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

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

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

Требование (транзакт) - это объект, поступающий в систему и нуждающийся в определенном обслуживании в данной системе. Требование является активным элементом в моделируемой системе. Под требованием можно понимать сообщение, машину, изделие, информацию, пользователя и т.д. Требование в системе GPSS - это объект с набором определенных признаков, который определяется уникальным номером. Объекты нумеруются последовательно, начиная с номера 1.

Канал обслуживания - устройство, в котором выполняется обслуживание требования. Основным параметром канала обслуживания является время обслуживания, которое, как правило, является случайной величиной.

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

На рисунке  2.6 представлена Q-схема обслуживания с одним процессором без QoS, где Г – источник заявок, ПР – обработка центральным процессором.

Рисунок 2.6 - Q-схема обслуживания с одним процессором без QoS

 

На рисунке  2.7 представлена Q-схема обслуживания без QoS, где Г – источник заявок, Qj – буфер j-го порта, ПРj – обработка процессором j-го порта, Qr – очередь центрального процессора, R – обработка пакета центральным процессором, Lj – размер буфера j-го порта, t – время обработки.

Рисунок 2.7 - Q-схема обслуживания без QoS

На рисунке  2.8 представлена Q-схема обслуживания проектируемой модели, для коммутатора с процессорами портов ввода\вывода и центральным процессором обработки коммутации, где Г – источник заявок, Qj – буфер j-го порта, ПРj – обработка процессором j-го порта, Пр сорт – обработка приоритетных очередей, Пр ц – обработка пакета центральным процессором, Vl, Vc, Vh – определение полосы пропускания для очередей с высоким приоритетом, средним и низким.

Рисунок 2.8 - Q-схема обслуживания проектируемой модели

2.4 Построение программной модели

Описание требований входных данных

В языке GPSS возможность  задания функций распределения  случайных величин ограничена заданием их в табличном виде путем аппроксимации  непрерывными функциями. Поэтому можно  задать только те функции, которые легко  преобразовать для новых значений параметров. К таким функциям, например, относится функция экспоненциального  распределения с параметром λ=1, а  также функция стандартного нормального  распределения с математическим ожиданием m 0 и стандартным отклонением σ=1.

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

где

λ - интенсивность  потока.

Интервалы времени  между соседними заявками пуассоновского потока распределены по экспоненциальному закону. Согласно методу обратной функции, можно получить ряд чисел, которые имеют экспоненциальное распределение, если ряд случайных чисел R, равномерно распределенных на интервале [0,1], преобразовать в соответствии с функцией, обратной к экспоненциальной функции распределения: