Анализ очередей

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

Определить основные характеристики QoS и сформулировать требования к ним — это значит наполовину решить задачу. Пользователь формулирует свои требования к качеству обслуживания в виде некоторых предельных значений характеристик QoS, которые не должны быть превышены, например, он может указать, что предельное значение вариации задержки пакетов не должно превышать 50 мс с вероятностью 0,99.

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

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

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

Знакомство с моделью М/М/1

Существует ветвь прикладной математики, предметом которой являются процессы образования очередей. Эта дисциплина так и называется — теория очередей. Мы не будем углубляться в математические основы этой теории, приведем только некоторые ее выводы, существенные для рассматриваемой нами проблемы QoS.

На рис. 7.3 показана наиболее простая модель теории очередей, известная под названием М/М/1 (здесь 1 означает, что моделируется одно обслуживающее устройство, первая буква М обозначает тип распределения интервалов поступления заявок (марковское распределение), вторая — тип распределения значений времени обслуживания (тоже марковское)).

Рис. 7.3. Модель М/М/1

Основными элементами модели являются:

• входной поток абстрактных заявок на обслуживание;

• буфер;

• обслуживающее устройство;

• выходной поток обслуженных заявок.

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

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

Если прибывшая заявка застает буфер не пустым, то она становится в очередь и ожидает обслуживания. Заявки выбираются из очереди в порядке поступления, то есть соблюдается дисциплина обслуживания первым пришел — первым обслужен (First-In, First-Out, FIFO).

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

Будем считать, что нам известно, что среднее время между поступлениями заявок равно Т. Это значит, что интенсивность поступления заявок, которая традиционно обозначается в теории очередей символом λ, равна

λ = 1/Т заявок в секунду.

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

Рис. 7.4. Плотность распределения входного потока

Будем также считать, что среднее время обслуживания заявки равно b. Это означает, что обслуживающий прибор способен продвигать заявки на выход с интенсивностью 1/b = μ. Опять же для получения аналитического результата считают, что время обслуживания — это случайная величина с пуассоновской плотностью распределения.

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

Здесь через ρ обозначено отношение λ/μ.

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

Зависимость среднего времени ожидания заявки w от ρ иллюстрирует рис. 7.5. Как видно из поведения кривой, параметр ρ играет ключевую роль в образовании очереди. Если значение ρ близко к нулю, то и среднее время ожидания очень близко к нулю. А это означает, что заявки почти никогда не ожидают обслуживания в буфере (в момент их прихода он оказывается пустым), а сразу попадают в обслуживающее устройство. И наоборот, если ρ приближается к 1, то время ожидания растет очень быстро и нелинейно (и в пределе равно бесконечности). Такое поведение очереди интуитивно понятно, ведь ρ — это отношение средней интенсивности входного потока к средней интенсивности его обслуживания. Чем ближе средние значения интервалов между пакетами к среднему времени обслуживания, тем сложнее обслуживающему устройству справляться с нагрузкой.

Рис. 7.5. Зависимость среднего времени ожидания заявки

от коэффициента использования ресурса

М/М/1 как модель обработки пакетов

С помощью модели М/М/1 можно моделировать сеть с коммутацией пакетов (рис. 7.6).

Рис. 7.6. Соответствие модели М/М/1 элементам сети

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

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

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

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

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

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

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

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

На рис. 7.7 показано семейство зависимостей w от ρ, полученных для разных значений коэффициента вариации CV входного потока. Имитационная модель учитывает фиксированную задержку в сети. Одна из кривых, у которой CV = 1, соответствует пуассоновскому входному потоку. Из рисунка видно, что чем меньше пульсирует входной поток (CV приближается к нулю), тем меньше проявляется эффект лавинообразного образования очереди при приближении коэффициента загрузки ресурса к 1. И наоборот, чем больше CV, тем раньше (при меньших значениях ρ) начинает этот эффект проявляться. Из поведения графиков на рисунке можно сделать два вывода.

Рис. 7.7. Влияние степени пульсации потока на задержки

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

Для снижения уровня задержек нужно снижать значение ρ и сглаживать трафик.