Краткая теория. Федерального государственного автономного образовательного учреждения высшего профессионального образования

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ОБНИНСКИЙ ИНСТИТУТ АТОМНОЙ ЭНЕРГЕТИКИ – филиал

Федерального государственного автономного образовательного учреждения высшего профессионального образования

«Национальный исследовательский ядерный университет «МИФИ»

(ИАТЭ НИЯУ МИФИ)

Факультет Кибернетики

Кафедра Компьютерных Систем, Сетей и Технологий

Лабораторная работа № 3.

«Моделирование открытой марковской сети массового обслуживания методом Монте-Карло»

Выполнил:
студент группы ВТ3-С08
Азаров А.И.

Проверил:
профессор
Перегуда А.И.

ОБНИНСК 2012

Цель работы:

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

Краткая теория

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

Узел сети i представляет собой систему массового обслуживания из c_i Î {1, 2, …} идентичных приборов и накопителя заявок емкости r_i Î {1, 2, …} заявок. Примем, что 1 £ c_i < ∞, r_i - ∞, i – 1,M. Поскольку все заявки одного типа, то быстродействие прибора в узле i полностью описывает B_i(x), x ³ 0, - функция распределения длительности обслуживания заявки в этом узле, а для экспоненциального узла i

Где 1/m_i, 0 < 1/m_i — средняя длительность обслуживания в узле i, i 1,M.

Нужно также задать дисциплину обслуживания, т.е. порядок обработки заявки в узле от момента ее поступ­ления в узел до момента ухода из узла. Для определенности примем, что дисциплина обслуживания во всех узлах — «пришедший первым обслуживается первым» (FCFS).

Сделаем также следующие три естественных предположения:

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

Ø Заявки не покидают узел недообслуженными;

Ø Длительность обслуживания заявки в узле не зависит ни от ее длительности ожидания в этом узле, ни от характера и продолжительности ее предшествующего маршрута.

Эти три предположения часто называют законом сохранения работы.

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

Поскольку все заявки одного типа, то для обслуживания в любом узле им предоставляется только один прибор (канал), т.е. любой узел является односервисной СМО.

Сеть состоит из множества M = {1, 2, …, M} узлов, в которых размещены обслуживающие приборы и на­копители заявок. Пусть узел 0 описывает «внешнюю среду», с которой взаимодействует сеть, а M₀ = MÈ{0} - расширенное множество узлов. С физической точки зрения узел 0 можно разделить на два: узел a, объединя­ющий все источники заявок, и узел b, объединяющий все стоки, так что M_ab - MÈ{a}È{b} - также расширенное множество узлов. Иногда через 0 обозначают узел a, а через M +1 —узел-сток b.

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

Примем, что на открытую сеть из внешней среды поступает пуассоновский поток с постоянной интенсивно­стью λ₀. Пусть θ_ij — вероятность того, что после завершения обслуживания в узле и независимо от ее предшествующей траектории заявка мгновенно переходит в узел j, j Î M₀. i, i Î M.

Рассмотрим открытую сеть со стохастической маршрутной матрицей

b^T = (b₁, …, b_M)

Пусть — вероятность направления вновь поступившей заявки в узел их

физических соображений. Тогда a^T = (a_1, …, a_M), . j, j – 1,M, a θ₀₀ - 0

соответствующий стохастический вектор.

Пусть далее θ_i0 – 1 - - вероятность ухода некоторой заявки из сети сразу после завершения ее обслуживания в узле i, i = 1,M, а вектор соответствующий неотрицательный вектор.

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

Итак, для открытой сети возможны два варианта записи стохастической маршрутной матрицы

Здесь все векторы — M-мерные столбцы, а переходами между внутренними узлами сети управляет подматрица

являющаяся сужением матриц на множество внутренних узлов.

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

Блуждание заявки по открытой сети начинается в момент ее поступления из источника в некоторый узел i₀, для которого a_i0 > 0, может проходить, причем неоднократно, через любые узлы из множества M_i, а затем заканчивается на шаге n в момент ухода из узла i_n, для которого b_in > 0, в сток b. Все маршруты имеют вид i₀, i₁, …, i_n, где i₀, i₁, …, i_n Î M.

Результаты:

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

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

На графиках отображается среднее время ожидания заявки в очереди и среднее, минимальное и максимальное число заявок состоящих в очереди.

Рис. 1. Главное окно моего программного обеспечения

Рис. 2. Результаты моделирования

Вывод:

Был изучен метод моделирования открытой марковской системы массового обслуживания. Были получены её характеристики и необходимые оценки.

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