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

При аналитическом моделировании исследование процессов или объектов заменяется построением их математических моделей и исследованием этих моделей. В основу метода положены идентичность формы уравнений и однозначность соотношений между переменными в уравнениях, описывающих оригинал и модель. Поскольку события, происходящие в локальных вычислительных сетях, носят случайный характер, то для их изучения наиболее подходящими являются вероятностные математические модели теории массового обслуживания [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-In- Random-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;
  • • все характеристики должны быть положительны.

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

 
< Пред   СОДЕРЖАНИЕ     След >