Аналитическое моделирование на основе систем массового обслуживания

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

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

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

(3.1).

где - время распространения, время обслуживания и время ожидания соответственно. Одной из задач аналитического моделирования является определение среднего значения D. При больших загрузках основной вклад дает ожидание обслуживания IV. Для описания очередей в дальнейшем будет использована нотация Д. Дж. Кенделла:

где А — процесс прибытия; В — процесс обслуживания; С — число серверов (узлов); К — максимальный размер очереди (по умолчанию — ?);

in — число клиентов (по умолчанию — да); z — схема работы буфера (по умолчанию FIFO).

Буквы А и В представляют процессы прихода и обслуживания и обычно заменяются следующими буквами, характеризующими закон, соответствующий распределению событий:

• • D — постоянная вероятность;
• • ? - марковское экспоненциальное распределение;
• • G — обобщенный закон распределения;
• • - распределение Эрланга порядка k;
• •  — гиперэкспоненциальное распределение порядка k [4].

Наиболее распространенными схемами работы буферов являются.

FIFO (First-In-First-Out), LIFO (Last-In-First-Out) и FIRO (First-InRandom-Out). Например, запись M/M/2 означает очередь, для которой времена прихода и обслуживания имеют экспоненциальное распределение, имеется два сервера, длина очереди и число клиентов могут быть сколь угодно большими, а буфер работает по схеме FIFO [19].

Среднее значение длины очереди Q при заданной средней входной частоте сообщений? и среднем времени ожидания W определяется на основе теоремы Литла (1961) [18]:

(3.2).

Для варианта очереди M/G/1 входной процесс характеризуется распределением Пуассона со скоростью поступления сообщений ?. Вероятность поступления к сообщений на вход за время t равно:

(3.3).

Пусть N— число клиентов в системе, Q — число клиентов в очереди и пусть вероятность того, что входящий клиент обнаружит j других клиентов, равна:

(3.4).

Тогда среднее время ожидания:

(3.5).

где? — среднеквадратичное отклонение для распределения времени обслуживания.

Для варианта очереди (? - функция распределения времени обслуживания). Откуда следует [18].

(3.6).

Для варианта очереди M/D/1 время обслуживания постоянно, а среднее время ожидания составляет:

(3.7).

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

где

(3.8).

(3.9).

где , а равно вероятности того, что сообщение отправителя /' направлено получателю . Требование стабильности требует, чтобы . Для бо? льших n это приводит к

Работа сети Ethernet характеризуется рядом параметров, к числу которых относятся вероятность захвата канала и эффективность [18]. Первый параметр определяется по выражению.

(3.10).

где ? — вероятность того, что ровно одна станция попытается передать кадр в течение такта и захватить канал; Q — число станций, пытающихся захватить канал для передачи кадра данных.

Эффективность LAN Ethernet определяется следующим образом. Общее время работы сети Ethernet делится между интервалами передачи и интервалами конкуренции. Для передачи кадра данных требуется L/C секунд, где L — длина кадра в битах, С — скорость передачи данных в бит/сек. Среднее время ?, необходимое на захват канала, равно:

(З.11).

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

Среднее число тактов W рассчитывается следующим образом:

(3.12).

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

(3.13).

Для моделирования ЛВС наиболее часто используются следующие типы СМО:

• 1. Одноканальные СМО с ожиданием. Представляют собой один обслуживающий прибор с бесконечной очередью. Данная СМО является наиболее распространенной при моделировании. С той или иной долей приближения с ее помощью можно моделировать практически любой узел ЛВС.
• 2. Одноканальные СМО с потерями. Представляют собой один обслуживающий прибор с конечным числом мест в очереди. Если число заявок превышает число мест в очереди, то лишние заявки теряются. Этот тип СМО может быть использован при моделировании каналов передачи в ЛВС.
• 3. Многоканальные СМО с ожиданием. Представляют собой несколько параллельно работающих обслуживающих приборов с общей бесконечной очередью. Данный тип СМО часто используется при моделировании групп абонентских терминалов ЛВС, работающих в диалоговом режиме.
• 4. Многоканальные СМО с потерями. Представляют собой несколько параллельно работающих обслуживающих приборов с общей очередью, число мест в которой ограничено. Эти СМО, как и одноканальные с потерями, часто используются для моделирования каналов связи в ЛВС.
• 5. Одноканальные СМО с групповым поступлением заявок. Представляют собой один обслуживающий прибор с бесконечной очередью. Перед обслуживанием заявки группируются в пакеты по определенному правилу.
• 6. Одноканальные СМО с групповым обслуживанием заявок. Представляют собой один обслуживающий прибор с бесконечной очередью. Заявки обслуживаются пакетами, составляемыми по определенному правилу. Последние два типа СМО могут использоваться для моделирования таких узлов ЛВС, как центры (узлы) коммутации.

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

Открытой называется есть массового обслуживания, состоящая из ? узлов, причем хотя бы в один из узлов сети поступает извне входящий поток заявок и имеется сток заявок из сети. Для открытых сетей характерно то, что интенсивность поступления заявок в сеть не зависит от состояния сети, т. е. от числа заявок, уже поступивших в сеть. Открытые сети используются для моделирования ЛВС, работающих в неоперативном режиме. Каждая заявка поступает на вход соответствующего узла коммутации, где определяется место ее обработки. Затем заявка передается на «свой» сервер или по каналу связи — на «соседний», где обрабатывается, после чего возвращается к источнику и покидает сеть [18].

Замкнутой называется сеть массового обслуживания с множеством узлов ? без источника и стока, в которой циркулирует постоянное число заявок. Замкнутые СМО используются для моделирования таких ЛВС, источниками информации для которых служат абонентские терминалы, работающие в диалоговом режиме. В этом случае каждая группа абонентских терминалов представляется в виде многоканальной системы массового обслуживания с ожиданием и включается в состав устройств сети [18].

Различают простой и сложный режимы работы диалоговых абонентов. В простом режиме абоненты не производят никаких действий, кроме посылки заданий в ЛВС и обдумывания полученного ответа [18].

Абоненты с терминалов посылают запросы, которые по каналам связи поступают на узлы коммутации, а оттуда — на обработку на «свой» или «соседний» сервер. Дальнейшая обработка осуществляется так же, как в открытой сети [14].

При сложном режиме диалога работа абонентов представляется в виде совокупности операций некоего процесса, называемого технологическим. Каждая операция технологического процесса моделируется соответствующей СМО. Часть операций предусматривает обращение к ЛВС, а часть операций может такого обращения не предусматривать [18]. Алгоритм работы самой ЛВС такой же, как для замкнутой сети.

Смешанной называется сеть массового обслуживания, в которой циркулирует несколько различных типов заявок (графика), причем относительно одних типов заявок сеть замкнута, а относительно других — открыта. С помощью смешанных СМО моделируются такие ЛВС, часть абонентов которых работает в диалоговом, а часть — в неоперативном режиме. Для диалоговых абонентов также различают простой и сложный режим работы. Часто смешанные СМО моделируют ЛВС, в которых сервер дополнительно загружается задачами, решаемыми на фоне работы самой сети [18].

Алгоритм работы сети для диалоговых абонентов аналогичен алгоритму работы замкнутой сети, а алгоритм работы сети для неоперативных абонентов — алгоритму работы открытой сети.

Различают экспоненциальные и неэкспоненциальные модели ЛВС. Экспоненциальные модели основаны на предположении о том, что потоки заявок, поступающие в ЛВС, являются пуассоновскими, а время обслуживания в узлах ЛВС имеет экспоненциальное распределение.

Для таких сетей получены точные методы для определения их характеристик; трудоемкость получения решения зависит в основном от размерности сети [18].

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

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

При этом не требуется точного знания функций распределения случайных величин, связанных с данной СМО (интервалов между поступлениями заявок временем обслуживания в приборах), а достаточно только знание первого (математического ожидания) и второго (дисперсии или квадрата коэффициента вариации — ???) моментов этих величин [18].

Применение диффузионной аппроксимации при анализе ЛВС основано на следующем:

• • по каждому типу заявок вычисляется интенсивность поступления заявок данного типа в узлы сети так, как если бы данный поток заявок циркулировал в сети только один;
• • по определенному правилу, зависящему от типа СМО и дисциплины обслуживания, складываются потоки заявок от всех источников;
• • по определенному правилу определяется среднее время обслуживания в каждом узле ЛВС;
• • полученные значения подставляются в соответствующую диффузионную формулу и определяются характеристики узлов ЛВС;
• • определяются характеристики ЛВС в целом.

Постановка задачи анализа ЛВС при этом примет следующий вид. Дано:

• • число узлов ЛВС;
• • тип каждого узла ЛВС (тип СМО, моделирующей данный узел);
• • дисциплина обслуживания в каждом узле ЛВС;
• • общее число типов источников заявок, работающих в диалоговом режиме;
• • общее число типов источников заявок, работающих в неоперативном режиме;
• • для диалоговых источников в случае сложного режима работы число технологических процессов каждого типа, число операций в каждом технологическом процессе, среднее и ??? времени выполнения каждой операции, матрица вероятностей передач между операциями, а также наличие или отсутствие на каждой операции обращения к ЛВС;
• • для диалоговых источников в случае простого режима работы число источников (терминалов) каждого типа, среднее и ??? времени реакции абонента на ответ сети;
• • для неоперативных абонентов — средняя интенсивность поступления заявок и ??? времени между поступлениями заявок; по каждому типу заявок (диалоговому и неоперативному) средняя интенсивность обслуживания в каждом узле ЛВС, ??? времени обслуживания в узлах ЛВС и матрица вероятностей передач между узлами. Требуется найти:
• • среднее значение и дисперсию (или стандартное отклонение) времени задержки заявки каждого типа в ЛВС в целом;
• • среднее значение и дисперсию (или стандартное отклонение) времени задержки в узлах ЛВС;
• • загрузку узлов ЛВС;
• • вероятность потери заявки в узле ЛВС (для узлов, моделируемых СМО с потерями).

Ограничения могут быть следующими:

• • загрузка узлов не должна превышать 1 ?
• • вероятность потери заявки не должна превышать 1;
• • все характеристики должны быть положительны.

Иногда представляет интерес определение такого показателя, как максимальное время задержки заявки каждого типа в ЛВС. Максимальное время — это такое время, превышение которого допустимо лишь для некоторого, наперед заданного процента заявок каждого типа. Для определения максимального времени используется методика, основанная на аппроксимации функции распределения времени задержки в сети эрланговским или гипсрэкспонснциальным распределением, при этом необходимо задавать долю (процент) заявок, для которых рассчитывается максимальное время.