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

Скорость фильтрации (filtering) определяет скорость, с которой коммутатор выполняет следующие этапы обработки кадров:

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

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

Скорость продвижения (forwarding) определяет скорость, с которой коммутатор выполняет следующие этапы обработки кадров.

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

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

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

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

Величина вносимой коммутатором задержки зависит от режима его работы. Если коммутация осуществляется «на  лету», то задержки обычно невелики и составляют от 5 до 40 мкс, а при полной буферизации кадров - от 50 до 200 мкс (для кадров минимальной длины).

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

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

Значение максимального  числа МАС - адресов, которое может  запомнить процессор порта, зависит  от области применения коммутатора. Коммутаторы рабочих групп обычно поддерживают всего несколько адресов  на порт, так как они предназначены  для образования микросегментов. Коммутаторы отделов должны поддерживать несколько сотен адресов, а коммутаторы  магистралей сетей - до нескольких тысяч, обычно 4000-8000 адресов.

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

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

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

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

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

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

Вывод

В главе  рассмотрены варианты технической  реализации коммутаторов. Выявлены характеристики архитектур коммутаторов влияющих на работу алгоритмов обработки приоритетных очередей в маршрутизаторах: объем  буфера порта ввода вывода; производительность процессоров коммутатора; объем  буфера ОЗУ.

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

2.1 Описание  работы модели справедливой взвешенной  очереди

Процесс обработки кадра  в коммутаторе второго уровня состоит из следующих этапов:

- прием кадра с любого  порта;

- маркировка трафика по  некоторому признаку;

- размещение пакета в  приоритетные очереди на выходном  порту.

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

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

Например, в маршрутизаторах компании Cisco предусмотрено  несколько разновидностей WFQ:

• основанный на потоках (Flow-based) режим WFQ (FWFQ);
• основанный на классах (Class-based) режим WFQ (CWFQ).

Для варианта FWFQ на базе потоков в маршрутизаторе создается столько очередей, сколько  потоков существует в трафике. Под  потоком в данном случае понимаются пакеты с определенными значениями IP-адресов отправителя и получателя и/или портов TCP/UDP отправителя и  получателя (типа протоколов транспортного  уровня), а также одинаковыми значениями поля ToS. Иначе говоря, поток — это последовательность пакетов от одного приложения с определенными параметрами качества обслуживания, заданными в поле ToS.

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

Вариант CWFQ на базе классов в маршрутизаторах Cisco имеет два подварианта:

• классы трафика определяются на основании так называемых групп QoS, соответствующих набору признаков из списка управления доступом (ACL), например, номеру входного интерфейса или номеру хоста или подсети;
• классы трафика определяются значениями полей ToS.

Для варианта групп QoS администратор задает веса пропускной способности, выделяемой каждой группе QoS, а также (опционально) максимальную длину очереди. Пакеты, не отнесенные ни к одной из групп, включаются в  группу 0. При назначении весов WFQ нужно  принимать во внимание следующее:

• группе QoS с номером 0 автоматически назначается 1% имеющейся пропускной способности;
• общий вес всех остальных групп не может быть более 99%;
• оставшаяся после назначения весов пропускная способность выделяется группе 0.

В варианте классификации на основании значении ToS предусматриваются веса классов  по умолчанию. Они вступают в силу, если администратор явно не задал  их с помощью команды weight. Для  классификации используется два  младших бита трехразрядного подполя IP Precedence из поля ToS, так что в этом варианте имеется всего четыре класса трафика. По умолчанию, классу 0 выделяется 10% выходной пропускной способности, классу 1 — 20%, классу 2 — 30% и классу 3 — 40%. Чем  выше класс, тем важнее трафик, поэтому  выделение большей доли пропускной способности создает для него более привилегированные условия  продвижения.

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

WFQ как обобщение алгоритма честных планировщиков (Fair Queuing - FQ). Оба планировщика имеют отдельные FIFO-очереди для каждого потока данных. Так, если канал со скоростью R используется для N потоков, то скорость обработки каждого из них будет R/N при использовании честного планировщика. Честный планировщик с приоритетными коэффициентами позволяет регулировать долю каждого потока. Если имеется N активных потоков, с приоритетами w1,w2,…wn, то i-ый поток будет иметь скорость .

Каждому пришедшему пакету присваивается виртуальное время начала и конца обработки , где k — это номер пакета, а i — номер потока. Время начала и конца вычисляются по следующим формулам:

,                          (2.1)

где

 — время прихода и длина пакета соответственно;

• — виртуальная функция времени, которая определяется как ;

j — все активные сессии.

Пусть есть три очереди: первые две с приоритетом 1 и третья имеет  приоритет 2. С самого начала мы имеем 1 пакет в первой, два во второй и 5 в третьей. Пусть все пакеты одинакового размера. Результат работы алгоритма приведены в таблице 2.1.

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