Методы организации и обработки очередей

11.1. Очереди FIFO

Очереди FIFO (First-In-First-Out) используются обычно в скоростных интерфейсах (быстродействие > 2048 Кбит/c). Здесь первый пришедший пакет первым покидает очередь. Порядок следования пакетов при этом алгоритме не изменяется. Приоритетное обслуживание в этом варианте также не может быть осуществлено. Когда очередь заполнена, все последующие пакеты будут отбрасываться до тех пор, пока из очереди не будет изъят хотя бы один пакет.

11.2. Приоритетное обслуживание очередей (PQ)

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

11.3. Обычное обслуживание очередей (СQ)

Чтобы избежать жесткой регламентации системы обслуживания очередей PQ, системный администратор может выбрать стратегию CQ (Custom Queuing — обычное обслуживание очередей). CQ позволяет сетевому администратору реализовать приоритетное обслуживание трафика без побочных эффектов, связанных с блокировкой низкоприоритетных потоков. С помощью CQ можно сформировать 16 очередей трафика. Каждая из очередей обслуживается в карусельном режиме (round-robin). По умолчанию CQ обслуживает 1500 байт за цикл. Однако CQ не может фрагментировать пакеты. Это означает, что если CQ обрабатывает пакет длиной 1000 байт, следующий 1500-байтный пакет будет обработан вне очереди. При этом может возникнуть ситуация, когда для коротких очередей возникает тайм-аут. CQ может конфигурироваться так же, как и PQ. Процесс классификации трафика приписывает пакеты одной из 16 конфигурируемых очередей, работающих в режиме "дырявого ведра". Существует очередь с номером 0 (системная очередь), которая зарезервирована для пакетов управления сетью и имеет наивысший приоритет. При больших потоках возможна потеря пакетов из-за переполнения очередей. Длина очереди может быть задана в пределах от 0 до 32767 (20 — значение по умолчанию).

11.4. Справедливые очереди (WFQ)

Стратегия справедливых (взвешенных) очередей WFQ (Weighted Fair Queuing) используется по умолчанию для интерфейсов низкого быстродействия (другим названием этого алгоритма является SFQ — Stochastic Fairness Queuing). WFQ делит трафик на несколько потоков, используя в качестве параметров (для IP-протокола): IP-адреса и порты получателя и отправителя, а также поле IP-заголовка ToS. Значение ToS служит для квалификации (части выделяемой полосы) потока. Для каждого из потоков формируется своя очередь. Максимально возможное число очередей равно 256. Очереди обслуживаются в соответствии с карусельным принципом (round-robin). Более высокий приоритет имеют потоки с меньшей полосой, например telnet. По умолчанию каждая из очередей имеет емкость 64 пакета (но допускается значение и <4096 пакетов).

В сетях существует 8 уровней приоритета. Следует иметь в виду, что WFQ не поддерживается в случае туннелирования или шифрования. Субпоток с низким весом получает более высокий уровень обслуживания, чем с высоким. Не реализуется WFQ и в сетях АТМ. Когда задействованы биты ToS, WFQ реализует приоритетное обслуживание пакетов согласно значению этого кода. Весовой фактор обратно пропорционален уровню приоритета.

11.5. Справедливые очереди, базирующиеся на классах (CBWFQ)

Дальнейшим развитием технологии WFQ является формирование классов потоков, задаваемых пользователем. Алгоритм построения очередей, базирующихся на классах, называется CBWFQ (Class-Based Weighted Fair Queuing). Алгоритм CBWFQ предоставляет механизм управления перегрузкой. Параметры, которые характеризуют класс, те же, что и в случае WFQ (только вместо ToS используется приоритет). В отличие от WFQ здесь можно в широких пределах перераспределять полосу пропускания между потоками. Для выделения класса могут привлекаться ACL (Access Control List) или даже номер входного интерфейса. Каждому классу ставится в соответствие очередь. В отличие от RSVP данный алгоритм гарантирует полосу лишь в условиях перегрузки. Всего может быть определено 64 класса. Нераспределенная полоса может использоваться потоками согласно их приоритетам. Если используется резервирование CBWFQ и RSVP, то возможны конфликты, так как IOS маршрутизатора не проверяет баланса зарезервированной полосы разными протоколами.

11.6. Очереди с малой задержкой (LLQ)

В некоторых случаях, например в случае VoIP, более важно обеспечить малую задержку, а не полосу пропускания. Для таких задач разработан алгоритм LLQ (Low Latency Queuing), который является модификацией CBWFQ. В этом алгоритме пакеты всех приоритетов, кроме наивысшего, вынуждены ждать, пока очередь более высокого приоритета будет опустошена (см. PQ ). Разброс задержки в высокоприоритетном потоке может быть связан только с ожиданием завершения передачи пакета низкого приоритета, начавшейся до прихода приоритетного кадра. Такой разброс определяется диапазоном длин кадров (MTU).

11.7. Методы работы в условиях перегрузки

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

Идеальная (с точки зрения потребителя) нагрузочная характеристика сети сначала описывается прямой линией, то есть числа посланных и доставленных пакетов равны или почти равны. При достижении максимума пропускной способности сети число пакетов, доставляемых в единицу времени, становится постоянным, в то время как число посланных пакетов продолжает расти. К сожалению, такого в реальной жизни не происходит. Желательной нагрузочной характеристикой является такая, которая при малых и максимальных загрузках ведет себя как идеальная, а при переходных скоростях имеет плавный характер и доставляет несколько меньший процент пакетов, чем в идеале. Реальная нагрузочная характеристика (например, для Ethernet) много хуже даже желательного варианта. Сначала по мере роста загрузки начинает расти процент потери пакетов. Далее при входных потоках, превышающих некоторый порог, число доставляемых пакетов начинает падать при росте числа посланных пакетов, а при дальнейшем нарастании загрузки число доставляемых пакетов может стать равным нулю ("коллапс"). В версиях Ethernet, где столкновения исключены (в сети используются только переключатели и маршрутизаторы), ситуация более благоприятна.

Отчасти это может быть связано с недостатком памяти для входных буферов, по этой причине некоторое увеличение памяти может помочь. Но следует помнить, что всякое лекарство хорошо в меру. Еще в 1987 году Нагле (Nagle) обнаружил, что если маршрутизатор имеет даже беспредельную память, эффект перегрузки может оказаться еще более тяжелым. Это сопряжено со временем, в течение которого пакеты ожидают обработки. Если время ожидания в очереди превышает длительность тайм-аута, появятся дубликаты пакетов, что понижает эффективность системы. Причиной перегрузки может быть медленный процессор или недостаточная пропускная способность какого-то участка сети. Простая замена процессора или интерфейса на более быстродействующий не всегда решает проблему — чаще переносит "узкое место" в другую часть системы. Перегрузка, как правило, включает механизмы, усиливающие ее негативное воздействие. Так, переполнение буфера приводит к потере пакетов, которые позднее должны будут быть переданы повторно (возможно, даже несколько раз). Процессор передающей стороны получает дополнительную паразитную загрузку. Все это указывает на то, что контроль перегрузки является крайне важным процессом.

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

Следует делать различие между управлением потоком и контролем перегрузки. Под контролем потока подразумевается балансировка потока отправителя и возможностей приема и обработки получателя. Этот вид контроля предполагает наличие обратной связи между получателем и отправителем. В таком процессе участвуют, как правило, только два партнера. Перегрузка же — более общее явление, относящееся к сети в целом или к какой-то ее части. Например, 10 ЭВМ хотят передать одновременно какие-то файлы другим 10 ЭВМ. Конфликта потоков здесь нет, каждая из ЭВМ способна переработать поступающие данные, но сеть не может пропустить поток, генерируемый 10 сетевыми интерфейсами одновременно. Часто эти явления не так просто разделить. Отправитель может получить сообщение ICMP (quench – в случае стека протоколов TCP/IP) при перегрузке получателя или при перегрузке какого-то сетевого устройства.

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

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

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

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

Преодоление перегрузки может быть осуществлено понижением нагрузки или добавлением ресурсов приемнику.

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

Одной из причин перегрузки часто являются импульсные загрузки сегмента сети или сетевого устройства. По этой причине любые меры (например, pipelining — конвейер), которые могут выравнивать поток пакетов, безусловно, улучшат ситуацию (например, traffic shaping в сетях ATM). В TCP же с его окнами импульсные загрузки предопределены.

11.8. Алгоритм leaky bucket ("дырявое ведро")

Для систем без обратной связи решение проблемы выравнивания скорости передачи данных может быть решено с помощью алгоритма leaky bucket ( "дырявое ведро" ). Суть этого алгоритма заключается в том, что на пути потока устанавливается буфер, выходной поток которого постоянен и согласован с возможностью приемника. Если буфер переполняется, пакеты теряются.

Потеря пакетов — вещь малоприятная, но это блокирует процессы, которые могут привести к коллапсу сегмента или всей сети.

Там, где потеря пакетов нежелательна, можно применить более гибкий алгоритм.

11.9. Алгоритм "маркерное ведро"

Алгоритм token bucket (маркерное ведро) предполагает наличие в буферном устройстве (или программе) некоторого количества маркеров. При поступлении на вход буфера пакетов маркеры используются для их транспортировки на выход. Дальнейшая передача данных на выход зависит от генерации новых маркеров. Поступающие извне пакеты тем временем накапливаются в буфере. Таким образом, полной гарантии отсутствия потерь мы не имеем и здесь. Но алгоритм token bucket позволяет передавать на выход "плотные" группы пакетов ограниченной численности (по числу маркеров), снижая в некоторых случаях вероятность потери. Если буферное устройство "смонтировано" внутри ЭВМ отправителя, потерь можно избежать вовсе, блокируя передачу при заполнении буфера. Как в одном, так и в другом алгоритме мерой передаваемой информации может быть не пакет, а n -байт (где n — некоторое оговоренное заранее число).

11.10. Алгоритмы RED и WRED

Одним из возможных подходов при решении проблемы перегрузки является алгоритм RED (Random Early Detection). RED позволяет маршрутизатору отбрасывать пакеты, даже когда в очереди еще имеется место.

Алгоритм WRED использует взвешенное значение длины очереди в качестве фактора, определяющего вероятность отбрасывания пакета. По мере роста средней длины очереди растет вероятность отбрасывания пакетов. Если средняя длина очереди меньше определенного порога, вероятность отбрасывания пакета равна нулю. Небольшие кластеры пакетов могут успешно пройти через фильтр RED. Более крупные кластеры могут понести потери. Это приводит к тому, что ТСР-сессии с большими открытыми окнами имеют большую вероятность отбрасывания пакетов.

Главной целью алгоритма RED является исключение ситуации, когда несколько ТСР-потоков перегружаются почти одновременно и затем синхронно начинают процедуру восстановления.

Интересное предложение относительно выборочного (приоритетного) отбрасывания пакетов содержится в работе [11.1] в отношении мультимедиа-потоков.

Алгоритм RED позволяет организовать очереди таким образом, что их размер отслеживает осцилляции величины RTT.

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

Существует модификация алгоритма обработки очередей WRED (Weighted Random Early Detection), широко используемая в маршрутизаторах. Этот алгоритм применяется и при реализации DiffServ и гарантированной переадресации ( AF ), когда решение об обработке пакета принимается в каждом транзитном узле независимо ( PHB — Per Hop Behavior). При этом может учитываться код DSCP (Differential Service Code Point) IP-заголовка.

Алгоритм WRED удобен для адаптивного трафика, который формируется протоколом ТСР, так как здесь потеря пакетов приводит к снижению темпа их посылки отправителем. Алгоритм WRED присваивает пакетам не IP-типа нулевой приоритет, повышая вероятность их потери. Имеется возможность конфигурации WRED и WFQ для одного и того же интерфейса.

WRED полезен для любого выходного интерфейса, где ожидается перегрузка. Когда приходит пакет, вычисляется среднее значение длины очереди. Если вычисленное значение меньше минимального порога очереди (Т1), приходящий пакет ставится в очередь. Если вычисленное значение лежит между минимальным порогом очереди для данного типа трафика и максимальным порогом для интерфейса (Т2), пакет ставится в очередь или отбрасывается в зависимости от вероятности отброса, установленной для данного типа трафика. И, наконец, если усредненный размер очереди больше максимального порога, пакет безальтернативно отбрасывается (см. рис 11.2).

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

Ни АТМ-интерфейсы маршрутизаторов, ни АТМ-коммутаторы не предоставляют гарантий QoS для UBR виртуальных каналов. Маршрутизатор CISCO может специфицировать только пиковую скорость передачи ( PCR ) для UBR-канала.

Маршрутизатор автоматически задает параметры, которые нужно использовать в вычислениях WRED. Среднее значение длины очереди определяется на основе предыдущего значения и текущего размера очереди, согласно

Среднее = (old_evarage * (1-2-n)) + (current_queue_size * 2-n),

где n — экспоненциальный весовой фактор, конфигурируемый пользователем.

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

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

Когда n становится слишком большим, WRED не будет реагировать на перегрузку. Пакеты будут посылаться или отбрасываться так, как если бы WRED не работал.

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

Вероятность отбрасывания пакета зависит от минимального порога ( Т1 ), максимального порога ( Т2 ) и маркерного деноминатора вероятности PC. Когда средняя длина очереди выше T1, RED начинает отбрасывать пакеты. Частота отбрасываний увеличивается линейно по мере роста длины очереди до тех пор, пока усредненный размер очереди не достигнет максимального порога ( Т2 ).

Маркерный деноминатор вероятности ). Когда усредненная длина очереди превышает T2, отбрасываются все пакеты. Минимальный порог T1 следует выбрать достаточно высоким, чтобы максимизировать использование канала. Значение PC можно задать и больше 1, но в этом случае длина очереди никогда не достигнет T2.

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

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

Еще более универсальным решением, пригодным для работы с установлением соединения и без, является посылка пакетов блокировки (choke Packets). Маршрутизатор обычно контролирует загруженность всех своих внешних каналов L, которая может принимать значения от 0 до 1. Когда L достигает некоторого порогового значения, отправителю посылается пакет блокировки. При вычислении L следует использовать какую-либо методику усреднения, чтобы избежать слишком частых блокировок.

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

ЭВМ может понижать трафик, корректируя свои параметры, например ширину окна или темп передачи, на выходе устройства типа "дырявое ведро". Обычно первый блокирующий пакет уменьшает поток вдвое, следующий на — 0,25 и т.д. Увеличение потока также производится аналогичными шагами. Существует большое число вариантов алгоритма управления потоком с использованием пакетов блокировки. Параметром, который контролируется и определяет условие отправки пакета блокировки, может служить длина очереди или степень заполнения буфера.

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

Ситуация перегрузки не всегда управляется однозначно. Например, при поступлении на вход пакетов от трех источников возможна ситуация, когда приемник посылает блокирующие пакеты всем отправителям, а откликнется сокращением потока только один. В результате этот узел, который "играет по правилам" (как это часто бывает и в жизни), оказывается в проигрыше. В 1987 году Нагле был предложен алгоритм fair queuing (справедливая очередь, см. соответствующий раздел WFQ выше). В этом алгоритме маршрутизатор организует независимые очереди для пакетов, поступающих от разных источников. Когда выходной канал маршрутизатора оказывается свободным, он просматривает очереди циклически и отправляет очередной пакет. В результате при n очередях по завершении такого цикла просмотров-посылок будет послано по одному пакету из каждой очереди. Этот алгоритм используется в некоторых ATM-переключателях. Следует заметить, что этот алгоритм дает преимущества тем узлам, которые посылают более длинные пакеты. Демерс (Demers) и др. в 1990 году предложили усовершенствование алгоритма. В данном варианте организуется циклический просмотр очередей не попакетно, а побайтно. Система последовательно сканирует очереди и определяет положение концов пакетов. Первыми отправляются более короткие пакеты. Для иллюстрации предлагается рассмотреть рис 11.5.

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

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

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

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

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

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