Очереди и алгоритмы их обслуживания — основа QoS

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

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

Стратегия FlFO

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

Рисунок 3.5 – Очередь FIFO

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

Такая схема приемлема, если исходящий канал имеет достаточно большую свободную полосу пропускания.

При­о­ри­тет­ное об­слу­жи­ва­ние оче­ре­дей

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

Рисунок 3.6 – Очереди с приоритетами

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

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

Взвешенные настраиваемые очереди

Ал­го­ритм взве­шен­ных оче­ре­дей (Weighted Queuing) раз­ра­бо­тан для того, чтобы для всех клас­сов тра­фи­ка можно было предо­ста­вить опре­де­лен­ный ми­ни­мум про­пуск­ной спо­соб­но­сти или удо­вле­тво­рить тре­бо­ва­ния к за­держ­кам. Под весом ка­ко­го-ли­бо клас­са по­ни­ма­ет­ся доля вы­де­ля­е­мой дан­но­му виду тра­фи­ка про­пуск­ной спо­соб­но­сти вы­ход­но­го ин­тер­фей­са. Ал­го­ритм, в ко­то­ром вес клас­сов тра­фи­ка может на­зна­чать­ся ад­ми­ни­стра­то­ром, на­зы­ва­ет­ся «на­стра­и­ва­е­мой оче­ре­дью». Тра­фик де­лит­ся на несколь­ко клас­сов, и для каж­до­го вво­дит­ся от­дель­ная оче­редь па­ке­тов. С каж­дой оче­ре­дью свя­зы­ва­ет­ся доля про­пуск­ной спо­соб­но­сти вы­ход­но­го ин­тер­фей­са, га­ран­ти­ру­е­мая дан­но­му клас­су тра­фи­ка при пе­ре­груз­ках этого ин­тер­фей­са. В при­ме­ре, при­ве­ден­ном на ри­сун­ке 3.7, устрой­ство под­дер­жи­ва­ет пять оче­ре­дей для пяти клас­сов тра­фи­ка. Этим оче­ре­дям со­от­вет­ству­ет 10, 10, 30, 20 и 30% про­пуск­ной спо­соб­но­сти вы­ход­но­го ин­тер­фей­са при пе­ре­груз­ках.

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

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

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

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

Взве­шен­ное спра­вед­ли­вое об­слу­жи­ва­ние — это ком­би­ни­ро­ван­ный ме­ха­низм об­слу­жи­ва­ния оче­ре­дей, со­че­та­ю­щий при­о­ри­тет­ное об­слу­жи­ва­ние со взве­шен­ным (ри­су­нок 3.8). Этот механизм преду­смат­ри­ва­ет су­ще­ство­ва­ние одной осо­бой оче­ре­ди, ко­то­рая об­слу­жи­ва­ет­ся по при­о­ри­тет­ной схеме — все­гда в первую оче­редь и до тех пор, пока все за­яв­ки из неё не будут ис­пол­не­ны. Эта оче­редь пред­на­зна­че­на для си­стем­ных со­об­ще­ний, со­об­ще­ний управ­ле­ния сетью и, воз­мож­но, па­ке­тов наи­бо­лее кри­ти­че­ских и тре­бо­ва­тель­ных при­ло­же­ний. Во вся­ком слу­чае, пред­по­ла­га­ет­ся, что её тра­фик имеет невы­со­кую ин­тен­сив­ность, по­это­му зна­чи­тель­ная часть про­пуск­ной спо­соб­но­сти вы­ход­но­го ин­тер­фей­са оста­ет­ся дру­гим клас­сам тра­фи­ка.

Рисунок 3.8 – Взве­шен­ное спра­вед­ли­вое об­слу­жи­ва­ние

Технология MPLS

MPLS (MultiProtocol Label Switching) — это технология быстрой коммутации пакетов в многопротокольных сетях, основанная на использовании меток. MPLS широко используется для построения высокоскоростных IP-магистралей.

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

MPLS создает модель с установлением соединения, накладываемую на традиционную, не ориентированную на установление соединений, структуру маршрутизируемых IP-сетей.

Преимущества MPLS

1) Технология MPLS позволяет сети поддерживать как новые, так и существующие услуги. MPLS функционирует как поверх существующей (Е3, SDH), так и новой инфраструктуры (10/100/1000/10G Ethernet) и других сетей.

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

3) MPLS упрощает требования обработки, предъявляемые к маршрутизаторам, поскольку маршрутизаторы просто передают пакеты, основываясь на фиксированных метках.

4) MPLS обеспечивает соответствующий уровень безопасности, одновременно сокращая потребность на шифрование в IP-сетях общего пользования.

В соответствии с технологией MPLS пакетам присваиваются метки для их передачи по сети. Метки включаются в заголовок MPLS, вставляемый в пакет данных (Рисунок 4.1).

Метки-идентификаторы определяют принадлежность каждого пакета тому или иному классу FEC. FEC (Forwarding Equivalence Classes) класс эквивалентности при пересылке – это семейство пакетов, которые пересылаются одинаковым способом по одному и тому же маршруту и обрабатываются одинаковым образом, например, с целью обеспечить заданное QoS.

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

Чтобы понять суть MPLS-маршрутизации приведу пример: Студенты отправляются в путешествие по реке Амур. Каждый студент одет в синюю футболку с надписью ХИИК. При посадке на теплоход не имеет смысла у каждого студента проверять билет, так как все студенты отправляются по единому маршруту (как все пакеты одного и того же сообщения). Таким образом, уменьшается время на отправку каждого студента и значительно упрощается весь процесс транспортировки студентов по всему маршруту следования.

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

Сети MPLS организуют помеченные коммутируемые маршруты LSP (Label Switched Path)для прохождения данных по сети. LSP определяются последовательностью меток, назначаемых узлам на пути следования пакета от источника к получателю.

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

Рисунок 4.1 – Сеть MPLS

Собственные маршрутизаторы потребителей на краю сети потребителя (CE) взаимодействуют с маршрутизаторами на краю сети провайдера, также называемые краевыми маршрутизаторами меток (Label Edge Routers) - LER, являющихся собственностью провайдера услуг. В точке входа сети MPLS (входящий поток) маршрутизаторы LER добавляют метки пакетам. В точке выхода сети MPLS маршрутизаторы LER удаляют метки. В пределах облака MPLS маршрутизаторы провайдера, называемые коммутирующими маршрутизаторами меток (Label Switching Routers) - LSR последовательно коммутируют трафик, основываясь на метках MPLS.

Прежде чем направить трафик в сеть MPLS, маршрутизаторы LER сначала организуют LSP через сеть MPLS до удаленных LER.

Входной LER анализирует заголовок пришедшего извне пакета, устанавливает, какому FEC он принадлежит, чтобы связать его с определённым уровнем качества, снабжает этот пакет меткой, которая присвоена данному FEC, и пересылает пакет к соответствующему LSR. Пакет продолжает движение по LSP, при этом каждый промежуточный маршрутизатор LSR заменяет метки, как определено информацией в его базе меток LIB, чтобы направить пакет на следующий транзитный участок. В LER точки выхода последняя метка MPLS удаляется, и пакет передается с использованием традиционных механизмов маршрутизации. Затем пакет направляется в сеть потребителя.

Итак, метка, помещаемая в некоторый пакет, представляет FEC, к которому этот пакет относится. Как правило, отнесение пакета к определенному классу производится на основе сетевого адреса получателя.

Метки для каждого FEC всегда назначаются «снизу», то есть либо выходным LER, либо тем LSR, который является для этого FEC «нижним» (расположенным ближе к адресату), и распределяются им по тем маршрутизаторам, которые расположены «выше» (ближе к отправителю).

Для распределения меток может использоваться специальный протокол LDP (Label Distribution Protocol)— протокол распределения информации о привязке меток к FEC.

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

Поскольку принадлежность пакетов тому или иному FEC определяется не только IP-адресом, но и другими параметрами, нетрудно организовать разные LSP для потоков пакетов, предъявляющих разные требования к QoS. Каждый FEC обрабатывается отдельно от остальных - не только в том смысле, что для него образуется свой LSP, но и в смысле доступа к общим ресурсам (полосе пропускания канала, буферному пространству). Поэтому технология MPLS позволяет очень эффективно поддерживать требуемое QoS, соблюдая предоставленные пользователю гарантии.

Построение коммутируемого маршрута

Сеть MPLS автоматически создает путь LSP с помощью протокола LDP. Сначала посредством многоадресной рассылки сообщений UDP коммутирующие маршрутизаторы LSR определяют свое «соседство» в рамках протокола LDP. Это необходимо для реализации туннельной передачи. После того как соседство установлено, LDP открывает транспортное соединение между участниками сеанса с помощью протокола ТСР. По этому соединению передаются запросы на установку привязки и сама информация о привязке. Кроме того, участники сеанса периодически проверяют работоспособность друг друга, отправляя тестовые сообщения. Рассмотрим на примере, как происходит заполнение таблиц меток по протоколу LDP (рис. 4.2).

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

На стадии B маршрутизаторы сети MPLS применяют процедуру нахождения соседних устройств и устанавливают с ними сеансы LDP.

Рисунок 4.2 – Построение коммутируемого маршрута

На стадии С LER 2 на основе анализа собственных таблиц маршрутизации обнаруживает, что он является выходным LER для пути, ведущего к IP-сети 193.233.48.0. Тогда LER 2 ассоциирует класс FEC с пакетами, адрес получателя которых соответствует префиксу данной сети, и присваивает этому классу случайное значение метки — в нашем случае 18. Получив привязку, протокол LDP уведомляет верхний маршрутизатор LSR (LSR 1) о том, что потоку, адресованному сети с префиксом 193.233.48, присвоена метка 18. LSR 1 помещает это значение в поле выходной метки своей таблицы.

На стадии D устройство LSR 1, которому известно значение метки для потока, адресованного на префикс 193.233.48, присваивает собственное значение метки 33 данному FEC и уведомляет верхнего соседа (LER 0) об этой привязке. Теперь LER 0 записывает полученную информацию в свою таблицу. После завершения данного процесса все готово для передачи пакетов из сети «клиента» в сеть с адресом 193.233.48.0, т.е. по выбранному пути LSP.