Определение параметров системы с очередями

Для проведения расчета параметров систем с очередями необходимо определить, что, собственно, входит в состав этой системы и то, какие параметры подлежат

оценке. Простейшая система с организацией очередей к серверу показана на рис. П4.2.

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

На рис. П4.2 также показаны некоторые важные параметры, которые исполь­зуются при расчетах. Элементы данных поступают в эту систему с некоторой средней скоростью поступления λ (она измеряется в элементах в секунду). На определенный момент времени некоторое количество элементов данных будет находиться в очереди. Давайте обозначим среднее число элементов данных, находящихся в очереди, буквой ω, а среднее время, которое элементы данных должны ожидать в очереди — символом Тω. Этот параметр определен и имеет смысл для всех входящих элементов данных, включая и те, которые не ожидали вовсе. Сервер обрабатывает входящие элементы данных, затрачивая на это сред­нее время обработки Тs. Этот временной интервал отсчитывается от момента поступления элемента данных на сервер вплоть до обработки его сервером (то есть отправки). Утилизация (степень загрузки) сервера р — это доля общего времени, в течение которой сервер был занят.

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

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

Однако размер очереди резко возрастает при вхождении системы в режим насыщения, стремясь к бесконечности при р=1. Поэтому на практике обычно ограничивают скорость поступления данных на сервер до 70-90 % от теорети­ческого максимума.

Можно показать процессы, происходящие в очереди, в их динамике. На рис. П4.3 показан график, иллюстрирующий работу системы с очередью. По оси ординат откладывается общее число элементов данных в системе. Затененные области по оси абсцисс определяют периоды времени, в течение которых сервер занят. Вдоль этой же оси располагаются отрезки, означающие события двух типов: поступление элемента данных; (элемент поступает во время Аj) и завер­шение обработки этого же элемента; (обработка завершается в момент времени Di), когда элемент покидает систему. Очевидно, время, которое элемент данных j находился в системе, определяется по следующей формуле: Т. - D.-Aj. Мини­мальное время обслуживания для элемента; обозначается символом Sy

В нашем примере время обработки первого элемента данных Т₁ равно мини­мальному времени обслуживания для этого элемента S₁, так как когда элемент 1 поступает в систему, она находится в режиме простоя, и элемент сразу же поступает на обслуживание. Время обслуживания второго элемента данных Т₂ определяется суммированием двух времен: времени, которое элемент 2 ожи­дает обслуживания в очереди и которое определяется выражением (D₁-A₂), и времени, затраченного на его обслуживание S₂. Аналогично, T₃ ⁼ (D₃-A₃) = (d₃-d₂) + (D₂-А₃) - S ₃ + (D₂-A₃).

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

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

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

q Определенный порядок обслуживания элементов данных. Когда сервер становится свободным, и в очереди находится несколько элементов данных, необходимо определить правила, в соответствии с которыми определяется элемент данных, выбираемый сервером для обработки. Простейшим пра­вилом является обслуживание очереди по принципу FIFO (First In, First Out — первым пришел, первым и ушел), также известного под названием FCFS (First Come, First Served — первым поступил, первым и обслужен). Другим возможным правилом обслуживания очереди может быть LIFO (Last In, First Out — первым пришел, последним ушел). Кроме того, на практике приходится иметь дело с порядком обслуживания, базирующим­ся на времени обслуживания. К сожалению, обслуживание очереди, осно­ванное на временных параметрах, достаточно сложно для моделирования. Более общим случаем является обслуживание очереди на основе приори­тетов, которое и будет рассматриваться дальше. При этом рассматривается поступление пакетов с одинаковым приоритетом.

В табл. П4.1 перечислены все параметры, определенные на рис. П4.2, а также добавлены новые параметры, которые будут использованы далее при проведе­нии расчетов, в том числе и для систем со множеством серверов.

Таблица П4.1. Используемые параметры

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

За исключением параметра утилизации серверов, все остальные параметры, приведенные в табл. П4.1, соответствуют ситуации, показанной на рис. П4.2. Если в системе N идентичных серверов, а р обозначает утилизацию каждого сервера, то можно рассматривать Np как утилизацию всей системы. Этот пока­затель часто рассматривают как интенсивность трафика (в табл. П4.1 обозначена символом и) или интенсивность работы системы. Следовательно, теоретическая максимальная утилизация такой системы будет равна Nx100%. Максимальная скорость поступления элементов данных в такую систему будет определяться по формуле:

В случае множества идентичных серверов выбор определенного сервера для обслуживания определенного элемента данных не влияет на время обслужива­ния. На рис. П4.4, б показана структура с организацией нескольких очередей для множества серверов. Такое изменение структурной схемы в значительной степени влияет на производительность всей системы в целом.

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

Таблица П4.2. Формулы для расчета параметров систем с очередями

Эти формулы могут быть полезны для вычисления некоторых параметров при «интуитивном» выборе структуры системы. Для получения формулы р = λTs достаточно заметить, что для скорости поступления элементов данных λ, сред­нее время между поступлениями элементов будет определяться выражением Т = 1/λ. Если интервал времени T меньше интервала времени Тs, то можно будет записать Тs/Т = λТ_S Аналогичные рассуждения подходят и в случае со множес­твом серверов: р = (λTs)/N.

Рассмотрим момент времени прихода очередного элемента данных. При по­ступлении этого элемента в систему в очереди находится в среднем со элементов данных, которые ожидают обслуживания. В момент, когда этот элемент покида­ет очередь для обслуживания, он оставляет после себя такое же среднее коли­чество элементов в очереди (на то оно и среднее количество, что не меняется). Среднее время, которое элемент ждет своей очереди до обслуживания, равно Тs. А так как элементы поступают в очередь со скоростью λ, то можно утверждать, что за промежуток времени Tω должно поступить λTω элементов данных. Следо­вательно, ω = λTω. Рассуждая аналогично, можно заключить, что q =λТq.

Из табл. П4.2 видно, что время, которое элемент данных находится в системе, равно сумме времени ожидания обслуживания и времени самого обслуживания. На любой момент времени количество элементов во всей системе равно сумме количества элементов, ожидающих обслуживания, и количества элементов, ко­торые уже обслуживаются. Для одного сервера среднее число элементов, кото­рые обслуживаются в данный момент времени, равно ρр. Следовательно, q = ω + ρ для одного сервера. Аналогично, q =ω+Nρ, если рассматривать случай с N серверами.

Основная задача при проведении анализа очередей заключается в получении информации о:

q скорости поступления элементов данных в очередь;

q времени обслуживания этих элементов на сервере на входе в систему;

q общем количестве ожидающих элементов;

q времени ожидания элементов в системе.

При этом важно знать средние значения этих параметров и диапазон их из­менений. Следовательно, большое значение при анализе очередей имеет знание стандартных (среднеквадратичных) отклонений каждого из перечисленных па­раметров; эти отклонения обозначаются σ_q, σ_Tq, σ_ω и σ_Tω.

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

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

q Поступление одного элемента данных не зависит от поступления другого элемента, то есть события происходят независимо;

q Никогда не поступают сразу два или более элементов данных;

q Среднее количество поступлений не изменяется со временем (то есть рас­пределение статично).

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

где е — основание натуральных логарифмов; λ — скорость поступления элемен­тов данных; п — количество элементов, поступивших за время t.

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

Продолжительность обслуживания элементов на сервере обычно описывает­ся несколько другими законами. Чаще всего в этом случае используется закон интервалов или экспоненциальный закон. Для этого закона используются боль­шое количество продолжительностей времен обслуживания. Рассмотрим при­мер с использованием 1000 продолжительностей времен обслуживания (каждый промежуток из этой 1000 отличается по времени). Такое количество продолжи­тельностей позволяет повысить точность вычислений. Для упрощения расчетов интервалы времени обслуживания группируются. Например: первая группа с временами обслуживания, лежащими в промежутке времени от 0 до 15 с, следу­ющая группа с временами обслуживания, лежащими в промежутке времени от 15 до 30 с, следующая — от 30 до 45 с и т. д. Приведем таблицу, поясняющую смысл сказанного (табл. П4.3).

Таблица П4.3. Пример распределения интервалов обслуживания

В промежутке времени 0-15 с (второй столбец) имеет место 1000 вариантов продолжительностей обслуживания. В промежутке 15-30 с (третий столбец) имеет место 798 вариантов продолжительностей обслуживания. А в промежутке времени 300-315 секунд (последний столбец) имеет место всего 11 вариантов продолжительностей обслуживания.

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

Для проведения оценки системы можно определить параметр, характеризую­щий интенсивность работы системы. Так как рассматриваются средние величи­ны, важно, чтобы норма поступления элементов данных не превосходила общего уровня обслуживания, то есть λ < pN, или >λ/pN< 1. Эта величина и определяет интенсивность работы системы.

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

Для обобщения всех возможных (или точнее, всех вероятных) случаев орга­низации системы с очередями, к которым применимы рассмотренные выше до­пущения, был разработан удобный подход. Все такие системы можно разделить, исходя из применяемых законов распределения времен обслуживания и поступ­ления в систему. Система (в том аспекте, который мы рассматриваем) может быть определена тройкой X/Y/N, где Х — это закон распределения времени поступления элементов данных в систему; Y — закон распределения времени обслуживания элементов данных сервером и N — число серверов. Для рассмат­риваемых здесь систем характерны следующие возможные законы распределе­ния (ниже также указаны буквы, которыми обозначаются эти законы):

q G — нормальное распределение времени поступления или времени обслу­живания элементов данных;

q М — пуассоновское распределение времени поступления; пуассоновское или экспоненциальное распределение времени обслуживания элементов данных;

q D — детерминированное время поступления или время обслуживания элементов данных.

Следовательно, модель М/М/1 определяет систему с одним сервером, пуассоновским распределением времени поступления элементов данных в систему и экспоненциальным временем обслуживания элементов на сервере.

Система с одним сервером

В первом столбце табл. П4.4 показаны формулы для определения некоторых параметров системы с одним сервером, которая подчиняется модели M/G/1. В соответствии с этой моделью скорость поступления элементов данных подчи­няется пуассоновскому закону, а время обслуживания — нормальному распреде­лению. Использование масштабирующего коэффициента А в значительной мере упрощает формулы для вычисления основных выходных параметров. Следует учесть, что коэффициент масштабирования зависит только от отношения стан­дартного (среднеквадратичного) отклонения времени обслуживания к среднему времени обслуживания (см. формулу). При этом не требуется никакой другой информации о времени обслуживания.

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

Таблица П4.4. Формулы для определения параметров системы с одним сервером

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

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