Комбинированные алгоритмы обслуживания очередей

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

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

Механизмы кондиционирования трафика

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

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

Классификация трафика

Классификация трафика представляет собой элемент QoS, позволяющий определить, какие пакеты нужно отправить в ту или иную очередь. Классификация обычно выполня­ется средствами фильтрации трафика, имеющимися в коммутаторах и маршрутизаторах пакетных сетей; для этих средств используется также такое название, как списки контроля доступа (Access Control List, ACL)[28]. Для классификации используются различные при­знаки пакетов, например адреса назначения и источника, тип протокола транспортного или прикладного уровня. Мы уже упоминали классификацию трафика при описании приоритетных и взвешенных очередей, так как без этого механизма кондиционирования трафика невозможно задействовать различные очереди к одному и тому же выходному интерфейсу.

Профилирование

Профилирование представляет собой меру принудительного воздействия на трафик, ко­торая служит для ограничения скорости потока пакетов. Профилирование обеспечивает соответствие потока пакетов заданному скоростному профилю; в качестве параметров профиля обычно выбирается средняя скорость потока пакета, измеренная на определен­ном интервале времени[29]. Пакеты, которые не укладываются в заданный профиль, либо отбрасываются, либо деквалифицируются, то есть помещаются в класс обслуживания с более низкими привилегиями, например переводятся из приоритетного класса в стан­дартный класс, обслуживаемый «по возможности». Англоязычное название операции профилирования — policing[30] — кажется более жестким и, возможно, дает более адекватное представление о характере действий.

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

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

Рис. 7.12. Эффект профилирования — отбрасывание избыточного трафика

 

Формирование трафика

Формирование трафика — это процесс намеренной задержки некоторых пакетов из обще­го потока в целях удержания средней скорости трафика в некоторых заданных пределах. Формирование трафика напоминает профилирование, так как имеет схожую цель - ограничение скорости трафика, но достигается эта цель другим способом. Вместо того чтобы отбрасывать избыточные пакеты (то есть те, передача которых могла бы привести к превышению лимита скорости), механизм формирования трафика задерживает пакеты-нарушители так, что результирующая скорость оказывается в заданных пределах. Эффект формирования трафика^[31] иллюстрирует рис. 7.13. Из рисунка видно, что скорость трафика сглаживается, так как избыточные пакеты не отбрасываются, а передаются с задержкой в другие интервалы времени. Тем самым скорость исходного потока снижается в течение периодов времени с избыточным трафиком и растет в тех последующих интервалах, в которых она оказывается меньше установленного предела.

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

Рис. 7.13. Эффект формирования трафика — сглаживание

 

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

Обратная связь

Назначение

Алгоритмы управления очередями и кондиционирования трафика не предотвращают пере­грузок, а лишь некоторым «справедливым» образом в условиях дефицита перераспределя­ют ресурсы между различными потоками или классами трафика. Алгоритмы управления очередями относятся к механизмам управления перегрузкой (congestion management), которые начинают работать, когда сеть уже перегружена.

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

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

Участники обратной связи

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

На рис. 7.14 показаны различные варианты организации обратной связи.

Рис. 7.14. Участники обратной связи

 

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

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

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

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

Ъобратной связи 4, как и в обратной связи 1, сообщение о перегрузке порождается узлом- получателем и передается узлу-источнику. Однако имеется и важное отличие: в данном случае каждый промежуточный коммутатор реагирует на это сообщение. Во-первых, он снижает скорость передачи данных в направлении узла назначения, во-вторых, он мо­жет изменить содержание сообщения. Например, если узел назначения просит снизить скорость до 30 Мбит/с, то промежуточный коммутатор может снизить эту величину до 20 Мбит/с, оценив состояние своего буфера. Кроме того, породить сообщение обратной связи может любой коммутатор сети, а не только узел назначения.

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

Информация обратной связи

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

§ признак перегрузки;

§ максимальная скорость передачи;

§ максимальный объем данных (кредит);

§ косвенные признаки.

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

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

Сообщение о максимальном объеме данных используется в широко применяемом в па­кетных сетях алгоритме скользящего окна (подробнее о нем рассказывается в главе 17). Этот алгоритм позволяет не только обеспечивать надежную передачу данных, но и реали­зовать обратную связь для контроля потока между конечными узлами. Параметром, не­сущим информацию обратной связи, является «окно» — число, тесно связанное с текущим размером свободного пространства в буфере принимающего узла. Окно также называют кредитом, который принимающий дает передающему узлу. Передающий узел может с любой скоростью передать объем информации (или определенное количество пакетов, если окно измеряется в пакетах), соответствующий кредиту. Но если кредит исчерпан, то передающий узел не имеет права передавать информацию, пока не получит следующий кредит. При перегрузках принимающий узел уменьшает размер окна, тем самым снижая нагрузку. Если эффект перегрузки исчезает, то принимающий узел увеличивает размер окна. Недостатком этого алгоритма является то, что он работает только в протоколах с установлением соединения.

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

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

Резервирование ресурсов