Размещено на http://www.allbest.ru/

Аннотация

Объектом исследования являются открытые сети Джексона. Цель работы - анализ операционных характеристик сети Джексона. В работе вычисляются такие операционные характеристики сети, как максимальная пропускная способность, среднее время ожидания обслуживания, среднее число отказов в обслуживании.

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



Abstract

This paper presents the research of open Jackson networks. The main purpose is to analyze performance measures of Jackson networks. Performance measures such as the maximum throughput, the average time spent in the queue, the average number of losses are calculated.

Analytical and computational methods are considered to analyze the network. The python-based program is developed to simulate open Jackson network. The results of modelling are used to optimize the network configuration.



Введение

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

Например, облачные вычисления, как новый способ предоставления вычислительной среды, которая одновременно является гибкой и надёжной, становятся всё более интересными для исследователей, инженеров, разработчиков и обычных пользователей. Недавние исследования показывают, что облачные вычисления - многообещающая технология, которая изменит способ доступа к вычислениям и ресурсам сети [1; 2]. Необходимо понимать, как распределять имеющиеся ресурсы, какую конфигурацию выбрать, как проводить обслуживание и работу облачной системы, чтобы максимизировать её операционные характеристики. Однако, облачные системы обладают некоторыми особенностями: облачные центры обычно состоят большого числа серверов, число которых может исчисляться сотнями и тысячами, поэтому традиционная теория массового обслуживания редко используется для анализа. Вместо этого предлагается использовать открытые сети Джексона. Jin Y. и др. [3] моделируют облачную системы с помощью сети Джексона, чтобы исследовать работу компонентов в платформе «доставка контента как услуга» (content-delivery-as-a-service - CoDaaS). А Bruneo D. и др. [4] используют модель, построенную на основе теории массового обслуживания, чтобы исследовать качество обслуживания (quality of service - QoS) в облачной системе, в которой её архитектура моделируется, используя сеть Джексона. Исследуемая в [4] позволяет масштабировать облачную систему так, чтобы гарантировать минимальное качество обслуживания. Enver E. [5] исследует облачную систему с отказами с помощью сети Джексона, применяя как аналитические методы, так и компьютерное моделирование.

Сети массового обслуживания применяются и в других областях. Так например, Ghaderzadeh A. и др. [6] в своей работе оптимизируют работу P2P (peer-to-peer) системы для стриминга потокового видео, используя систему Джексона из нескольких узлов с бесконечным количеством приборов. Комбинируя вместе модель сетей Джексона и метод ReDePoly (который показывает, как новые пиры (peer) входят в системы), они смогли провести компьютерный эксперимент, который показал, что они действительно успешно снизили задержки в работе P2P стриминговой системы. А Guo Y. [7], в свою очередь, использует сеть Джексона, чтобы аппроксимировать поток жидкости.

Как уже упоминалось ранее, с увеличением типов приборов и с усложнением дисциплины обслуживания становится сложно применять теорию массового обслуживания для анализа комплексных систем. В качестве наглядного примера можно привести задачу, решённую мной в рамках Междисциплинарной курсовой работы [8]. В ней исследуется-канальная система массового обслуживания:

1) На вход поступает простейший поток заявок с заданным параметром .

2) Время обслуживания на каждом канале распределено по экспоненциальному закону со своим параметром .

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

4) После обслуживания заявки покидают систему.

Для произвольного количества приборов предельное распределение, если оно существует, выражается через формулы:

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

2) , если .

3) .

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

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



1. Открытая сеть Джексона

1.1 Определение сети Джексона. Ее характеристики

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

(1)

и вероятностная мера на нём

(2)

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

Обозначим внешний узел индексом 0.

Определение. [9] Сетью Джексона называется открытая сеть, для которой выполняются следующие условия:

1) Входной поток - пуассоновский с параметром , а мера на маршрутах задаётся равенством

(3)

где

(4)

2) - полустохастическая неразложимая матрица.

3) Существует такое, что

(5)

4) Случайный процесс

(6)

где - количество требований в -м узле в момент , является однородной цепью Маркова.

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

(7)

Одной из операционных характеристик сетей является её пропускная способность. Обозначим - решение предыдущей системы при различных параметрах :

(8)

Максимальная пропускная способность сети определяется соотношением

(9)

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

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

где - интенсивность обслуживания одного прибора, и имеет вид

(10)

(11)

Теорема. (Джексона) Для существования стационарного распределения процесса необходимо и достаточно, чтобы сходился ряд (11), где - решение системы (8). Если это условие выполнено, то

1.2 Аналитическое исследование сети с тремя узлами

Рассмотрим следующую систему Джексона:

1) Количество узлов .

2) Петлей нет, т.е. для любого .

Внешний узел соединён только с одним внутренним. (12)

Решим систему уравнений (8) в случае рассматриваемой системы Джексона (12).

Подставим первое уравнение в третье

Подставим получившееся выражение во второе уравнение

Используя выражения для и , найдём

(13)



Обозначим - коэффициент перед в формулах для

Тогда формулу (9) можно представить в виде

(14)

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

python компьютерный моделирование

1.3 Компьютерное моделирование системы с тремя узлами с неограниченной очередью

Рассмотрим следующую систему Джексона:

1) Количество узлов .

2) Внешний узел соединён только с одним внутренним. Далее будем считать индекс этого узла равным 1.

Длина очереди на каждом узле - бесконечность. (15)

Смоделируем данную систему. В качестве операционной характеристики будем рассматривать суммарное время ожидание. Изучим её зависимость от числа приборов на 1-ом узле.

Обозначим за количество приборов, а за - интенсивность работы одного прибора в -ом узле.

Подробное описание программы, приведённой в приложении, останется за рамками данной работы. Опишем суть работы программы на каждом шаге моделирования.

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

1) Моделирование случайного равномерного распределения на отрезке
. В зависимости от того, какое значение принимает эта случайная величина, выбирается событие, которое произойдёт на данном шаге.

2) Моделирование экспоненциального распределения с соответствующим событию параметру.

3) Изменение состояния системы, а также расчёт оптимизационных параметров (например, суммарная длина очереди, времени ожидания и т.д.)

Рис.1 Алгоритм одного шага моделирования системы без ограничений на длину очереди.

Для моделирования системы необходимо задать характеристики системы:

Рассмотрим для сравнения аналогичную систему, но в которой .

После 1000 итераций моделирования системы в течение 100 ед. времени получим следующие графики:

Рис.2 Время ожидания при увеличении количества приборов на 1 узле, .



Рис.3 Время ожидания при увеличении количества приборов на 1 узле, .

Эти графики, приведённые на рис.2 и рис.3, в различном масштабе показывают зависимость времени ожидания на каждом из узлов и суммарное время ожидания от количества приборов на 1-ом узле.

Исходя из данных графиков, можно сделать вывод, что существует оптимальное количество приборов на 1-ом узле. Увеличение количества приборов не приведёт к улучшению операционной характеристики. А при увеличении интенсивности входящего потока ожидаемо увеличивается время ожидания и оптимальное количество приборов на 1-ом узле.

1.4 Компьютерное моделирование системы с тремя узлами c ограниченной очередью

Рассмотрим систему, аналогичную системе (15), но с ограниченными очередями. В данном случае можно рассматривать две операционные характеристики: суммарное время ожидания и количество потерянных заявок на каждом узле.

Обозначим за длину очереди на i-ом узле.

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

Рис.4. Алгоритм одного шага моделирования системы с ограничениями на длину очереди.



Пусть имеются следующие характеристики:

После 1000 итераций моделирования системы в течение 100 ед. времени получим следующие графики:

Рис.5 Изменение времени ожидания и количества потерь при увеличении количества приборов на 1 узле,

Первые три графика в различном масштабе показывают зависимость времени ожидания на каждом из узлов и суммарное время ожидания от количества приборов на 1-ом узле. А вторые три - зависимость количества потерь от количества приборов на 1-ом узле.

В случае системы с потерями для количества потерь можно сделать такой же вывод: имеется такое минимальное количество приборов на 1-ом узле, увеличение свыше которого не даст значимого улучшения рассматриваемой операционной характеристики. Но для суммарного времени ожидания существует минимум, который для данной системы достигается при .

Изменим в данной системе . Проведём такое же моделирование.

Рис.6 Изменение времени ожидания и количества потерь при увеличении количества приборов на 1 узле,



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

Рассмотрим теперь систему со следующими характеристиками:

Для неё так же проведём моделирование и получим графики, приведённые на рис.7.

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



Рис.7 Изменение времени ожидания и количества потерь при увеличении количества приборов на 1 узле.

1.5 Задача о распределении ресурсов

Рассмотрим задачу для сети Джексона с узлами. Заданы матрица маршрутов , интенсивность входящего потока , интенсивности обслуживания для каждого узла . Расходы на эксплуатацию каждого прибора в единицу времени в -ом узле составляет , стоимость ожидания единицы времени одного прибора в -ом узле - , начальный капитал - f. Какое количество приборов нужно поставить в каждый -ый узел, чтобы минимизировать средние издержки по эксплуатации сети?

Для начала необходимо найти минимальную конфигурацию сети, при которой она является эргодичной. Для этого нужно решить систему (7). Тогда минимальное количество приборов определяется неравенством

Отсюда можно найти минимальный капитал

Суммарные затраты за эксплуатацию приборов имеет явный вид

(16)

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

(17)

(18)

Обозначим за - стационарную вероятность для -го узла при условии, что в нём содержится приборов. Тогда из определения математического ожидания средние издержки за ожидание единицы времени составляют



(19)

Таким образом, задача сводится к нахождению минимума функции

при ограничениях

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

Рассмотрим частный случай сети с узлами. Формулы (13), (16)-(19) позволяют смоделировать метод динамического программирования для случая, когда только один внутренний узел соединён с внешним. Найдём явные формулы для в общем случае. Для этого решим систему (7) в условиях данной сети:

Обозначим - издержки на эксплуатацию сети при конфигурации , т.е.

Пусть - минимальная конфигурация сети, при которой она является эргодичной.

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

Таблица 1

1-ый этап динамического программирования

Столько можно добавить на 1-ый узел	Столько добавляем на 1-ый узел	Суммарные издержки
0	0
1	0
	1
2	0
	1
	2
…	…	…

На 0-ом шаге никаких вариантов добавления нет. На 1-ом шаге есть 2 варианта: добавить на 1-ый узел 0 или 1 прибор. Из них выбирается наилучший. И так далее.

На 2-ом этапе рассматривается 1-ый и 2-ой узел. На 2-ой узел добавляются приборы, а используя результаты предыдущего этапа, на 1-ый узел добавляется оптимальное количество приборов на оставшиеся средства.

Таблица 2

2-ой этап динамического программирования

Столько можно добавить на 2-ой узел	Столько добавляем на 2-ой узел	Опт. кол-во добавленных на 1-ый узел	Суммарные издержки
0	0
1	0
	1
2	0
	1
	2
…	…	…	…

Здесь - наилучшая конфигурация для 1-го узла при условии, что на 2-ой узел было добавлено приборов.

Аналогично проводится 3-ий этап, после которого в столбце «Суммарные издержки» находится минимум, по которому определяется оптимальная конфигурация системы.

Рассмотрим систему со следующими характеристиками:

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

На рис.8-13 на верхних графиках представлена зависимость количества приборов на каждом из узлом от параметра, а на нижних - минимальных суммарных издержек. Если на графике количество приборов и суммарные издержки равны нулю, то это означает, что для данного значения параметра невозможно получить эргодичную систему из-за ограничения начального капитала.

Рис.8. Зависимость характеристик сети от интенсивности входящего потока.



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

Рис.9 показывает, что с увеличением интенсивности обслуживания прибора вполне ожидаемо уменьшается его оптимальное количество. Можно отметить, что в определённый момент оптимальное количество приборов на 2-ом и 3-их узлах увеличивается на единицу. Возможно это связано с тем, что при увеличении суммарной интенсивности работы 1 узла, интенсивность входящего потока в другие узлы возрастает, а значит может настать момент, когда выгоднее поставить дополнительный прибор в другой узел.

Рис.9. Зависимость характеристик сети от интенсивности обслуживания прибора на 1-ом узле.



Аналогичный тренд наблюдается при одновременном изменении интенсивностей обслуживания на нескольких или на всех узлах сразу (рис.10 и рис.11).

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

Рис.10. Зависимость характеристик сети от интенсивностей обслуживания приборов на 1-ом и 2-ом узлах.



Рис.11. Зависимость характеристик сети от интенсивностей обслуживания приборов накаждом узле



Рис.12. Зависимость характеристик сети от издержек за ожидание на 1-ом узле.

Рис.13. Зависимость характеристик сети от издержек за ожидание на каждом узле.

Заключение

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

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

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



Список использованных источников

[1] Bruneo D., A Stochastic Model to Investigate Data Center Performance and QoS in IaaS Cloud Computing Systems // IEEE Transactions on Parallel and Distributed Systems, 2014, V. 25, I. 3, P. 560-569.

[2] Duan Q., Yan Y., Vasilakos A., A survey on service-oriented network virtualization toward convergence of networking and cloud computing // IEEE Transactions on Network and Service Management, 2012, V. 9, I. 4, 373-392.

[3] Jin Y., Wen Y., Zhang W., Content routing and lookup schemes using global bloom filter for content-delivery-as-a-service // IEEE Systems Journal, 2014, V. 8, I. 1, P. 268-278.

[4] Bruneo D., Distefano S., Longo F., Puliafito A., Scarpa M., Workload-based software rejuvenation in cloud systems // IEEE Transactions on Computers, 2013, V. 62, I. 6, P. 1072-1085.

[5] Enver E., Performability analysis of cloud computing centers with large numbers of servers // The Journal of Supercomputing, 2016, V. 73, N. 5, P. 2130-2156.

[6] Ghaderzadeh A., Kargahi M., Reshadi M., ReDePoly: reducing delays in multi-channel P2P live streaming systems using distributed intelligence // Telecommunication Systems. 2018. V. 67. N. 2. P. 231-246.

[7] Guo Y., Fluid approximation for generalized Jackson network with vacations // Frontiers of Mathematics in China. 2012. V. 3. N. 3. P. 459-485.

[8] Плеханов А.Ю., Оптимизация параметров в марковской системе массового обслуживания, Междисциплинарная курсовая работа, МИЭМ НИУ ВШЭ, 2017.

[9] Афанасьева Л.Г., Очерки исследования операций // МГУ, Механико-Математический факультет, 2007, С. 1-176.



Приложение

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

Вызов необходимых библиотек:

import numpy as np

import matplotlib.pyplot as plt

from matplotlib.backends.backend_pdf import PdfPages

%matplotlib inline

from sympy import sympify

import mpmath

from mpmath import nsum, inf, exp

from math import factorial

mpmath.mp.dps = 10

Моделирование системы без потерь:

P = np.array([[0,1,0,0], [1/3,0,3/6,1/6], [0,3/4,0,1/4], [0,3/4,1/4,0]])

l = 30

n1 = 4; mu1 = 15; N1_cur = 0; waiting_time1 = 0;

n2 = 3; mu2 = 15; N2_cur = 0; waiting_time2 = 0;

n3 = 1; mu3 = 25; N3_cur = 0; waiting_time3 = 0;

mu = np.array([mu1, mu2, mu3])

system = np.array([[n1, mu1, N1_cur, mu1*min(n1, N1_cur), waiting_time1],

[n2, mu2, N2_cur, mu2*min(n2, N2_cur), waiting_time2],

[n3, mu3, N3_cur, mu3*min(n3, N3_cur), waiting_time3]])

time_cur = 0; time_max = 100; total_cust = 0; iteration_max = 1000; num_nodes = system.shape[0]

Y3 = np.zeros(19)+1

X = np.zeros(19)+1

Y1 = np.zeros(19)+1

Y2 = np.zeros(19)+1

for it in range(1, iteration_max+1):

print("iteration number", it)

for n in range(1, 20):

system[0][0] = n

system[0][2] = 0

system[1][2] = 0

system[2][2] = 0

time_cur = 0

total_cust = 0

system[0][3] = 0

system[1][3] = 0

system[2][3] = 0

system[0][4] = 0

system[1][4] = 0

system[2][4] = 0

while (time_cur < time_max):

rate_total = l + np.sum(system[:,3])

x = np.random.uniform(0, 1)

x_rate = l

if (x < x_rate/rate_total):

total_cust += 1

t = np.random.exponential(1/l)

time_cur += t

x = np.random.uniform(0, 1)

x_route = 0

for i in range(num_nodes):

x_route += P[0][i+1]

if (x < x_route):

system[0][4] += max((system[0][2]-system[0][0]),0)*t

system[1][4] += max((system[1][2]-system[1][0]),0)*t

system[2][4] += max((system[2][2]-system[2][0]),0)*t

system[i][2] += 1

system[i][3] = system[i][1]*min(system[i][0], system[i][2])

break

else:

for i in range(num_nodes):

x_rate += system[i][3]

if(x < x_rate/rate_total):

t = np.random.exponential(1/system[i][3])

time_cur += t

system[0][4] += max((system[0][2]-system[0][0]),0)*t

system[1][4] += max((system[1][2]-system[1][0]),0)*t

system[2][4] += max((system[2][2]-system[2][0]),0)*t

system[i][2] -= 1

system[i][3] = system[i][1]*min(system[i][0], system[i][2])

x = np.random.uniform(0, 1)

x_route = P[i+1][0]

if (x < x_route):

x = 1

else:

for j in range(num_nodes):

x_route += P[i+1][j+1]

if (x < x_route):

system[j][2] += 1

system[j][3] = system[j][1]*min(system[j][0], system[j][2])

break

break

Y1[n-1] += system[0][4]

Y2[n-1] += system[1][4]

Y3[n-1] += system[2][4]

X[n-1] += n-1

Y1 = Y1 / (iteration_max+1)

Y2 = Y2 / iteration_max

Y3 = Y3 / iteration_max

X = (X-1)/iteration_max+1

mask = (Y1 >= 0)

print("minimal waiting time is when 1st node has", 1+np.argmin((Y1+Y2+Y3)[mask]), "servers")

f, (ax1, ax2, ax3) = plt.subplots(3, 1, sharex=True, figsize=(10,10))

ax1.plot(X, Y1, '-o', label='1st node')

ax1.plot(X, Y2, '-o', label='2nd node')

ax1.plot(X, Y3, '-o', label='3rd node')

ax1.plot(X, Y1+Y2+Y3, '-o', label='all together')

ax1.set_xlabel("num of servers 1");

ax1.set_ylabel("waiting time");

ax1.grid()

ax2.set_ylim(0, Y1[0]/4)

ax2.plot(X, Y1, '-o', label='1st node')

ax2.plot(X, Y2, '-o', label='2nd node')

ax2.plot(X, Y3, '-o', label='3rd node')

ax2.plot(X, Y1+Y2+Y3, '-o', label='all together')

ax2.set_xlabel("num of servers 1");

ax2.set_ylabel("waiting time");

ax2.grid()

ax3.set_ylim(0, Y1[0]/16)

ax3.plot(X, Y1, '-o', label='1st node')

ax3.plot(X, Y2, '-o', label='2nd node')

ax3.plot(X, Y3, '-o', label='3rd node')

ax3.plot(X, Y1+Y2+Y3, '-o', label='all together')

ax3.set_xlabel("num of servers 1");

ax3.set_ylabel("waiting time");

ax3.grid()

plt.legend()

pp = PdfPages('vkr_graphs_nolosses.pdf')

plt.savefig(pp, format='pdf')

pp.close()

plt.show()

Моделирование системы с потерями:

P = np.array([[0,1,0,0], [1/3,0,3/6,1/6], [0,3/4,0,1/4], [0,3/4,1/4,0]])

l = 15

n1 = 4; mu1 = 5; N1_cur = 0; waiting_time1 = 0; q_length1 = 100;

n2 = 3; mu2 = 5; N2_cur = 0; waiting_time2 = 0; q_length2 = 1;

n3 = 1; mu3 = 10; N3_cur = 0; waiting_time3 = 0; q_length3 = 1;

mu = np.array([mu1, mu2, mu3])

#system - количество приборов, интенсивность работы одного прибога, количество заявок в данный момент,

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

system = np.array([[n1, mu1, N1_cur, mu1*min(n1, N1_cur), float(waiting_time1), q_length1, 0],

[n2, mu2, N2_cur, mu2*min(n2, N2_cur), float(waiting_time2), q_length2, 0],

[n3, mu3, N3_cur, mu3*min(n3, N3_cur), float(waiting_time3), q_length3, 0]])

time_cur = 0; time_max = 100; total_cust = 0; iteration_max = 1000; num_nodes = system.shape[0]

X = np.zeros(19)+1

WT1 = np.zeros(19)+1

WT2 = np.zeros(19)+1

WT3 = np.zeros(19)+1

LOSS1 = np.zeros(19)+1

LOSS2 = np.zeros(19)+1

LOSS3 = np.zeros(19)+1

for it in range(1, iteration_max+1):

print("iteration number", it)

for n in range(1, 20):

system[0][0] = n

system[:, 2:5] = 0

system[:, 6] = 0

time_cur = 0

total_cust = 0

while (time_cur < time_max):

rate_total = l + np.sum(system[:,3])

x = np.random.uniform(0, 1)

x_rate = l

if (x < x_rate/rate_total):

total_cust += 1

t = np.random.exponential(1/l)

time_cur += t

x = np.random.uniform(0, 1)

x_route = 0

for i in range(num_nodes):

x_route += P[0][i+1]

if (x < x_route):

system[0][4] += max(system[0][2]-system[0][0],0)*t

system[1][4] += max(system[1][2]-system[1][0],0)*t

system[2][4] += max(system[2][2]-system[2][0],0)*t

if (system[i][2] < system[i][0] + system[i][5]):

system[i][2] += 1

system[i][3] = system[i][1]*min(system[i][0], system[i][2])

else:

system[i][6] += 1

break

else:

for i in range(num_nodes):

x_rate += system[i][3]

if(x < x_rate/rate_total):

t = np.random.exponential(1/system[i][3])

time_cur += t

system[0][4] += max(system[0][2]-system[0][0],0)*t

system[1][4] += max(system[1][2]-system[1][0],0)*t

system[2][4] += max(system[2][2]-system[2][0],0)*t

system[i][2] -= 1

system[i][3] = system[i][1]*min(system[i][0], system[i][2])

x = np.random.uniform(0, 1)

x_route = P[i+1][0]

if (x < x_route):

x = 1

else:

for j in range(num_nodes):

x_route += P[i+1][j+1]

if (x < x_route):

if (system[j][2] < system[j][0] + system[j][5]):

system[j][2] += 1

system[j][3] = system[j][1]*min(system[j][0], system[j][2])

else:

system[j][6] += 1

break

break

WT1[n-1] += system[0][4]

WT2[n-1] += system[1][4]

WT3[n-1] += system[2][4]

LOSS1[n-1] += system[0][6]

LOSS2[n-1] += system[1][6]

LOSS3[n-1] += system[2][6]

X[n-1] += n-1

WT1 = WT1 / iteration_max

WT2 = WT2 / iteration_max

WT3 = WT3 / iteration_max

LOSS1 = LOSS1 / iteration_max

LOSS2 = LOSS2 / iteration_max

LOSS3 = LOSS3 / iteration_max

X = (X-1)/iteration_max+1

f, (ax1, ax2, ax3, ax4, ax5, ax6) = plt.subplots(6, 1, sharex=True, figsize=(10,10))

ax1.plot(X, WT1, '-o', label='1st node')

ax1.plot(X, WT2, '-o', label='2nd node')

ax1.plot(X, WT3, '-o', label='3rd node')

ax1.plot(X, WT1+WT2+WT3, '-o', label='all together')

ax1.set_ylabel("waiting time");

ax1.grid()

ax2.set_ylim(0, WT1[0]/4)

ax2.plot(X, WT1, '-o', label='1st node')

ax2.plot(X, WT2, '-o', label='2nd node')

ax2.plot(X, WT3, '-o', label='3rd node')

ax2.plot(X, WT1+WT2+WT3, '-o', label='all together')

ax2.set_ylabel("waiting time");

ax2.grid()

ax3.set_ylim(0, WT1[0]/100)

ax3.plot(X, WT1, '-o', label='1st node')

ax3.plot(X, WT2, '-o', label='2nd node')

ax3.plot(X, WT3, '-o', label='3rd node')

ax3.plot(X, WT1+WT2+WT3, '-o', label='all together')

ax3.set_ylabel("waiting time");

ax3.grid()

ax4.plot(X, LOSS1, '-o', label='1st node')

ax4.plot(X, LOSS2, '-o', label='2nd node')

ax4.plot(X, LOSS3, '-o', label='3rd node')

ax4.plot(X, LOSS1+LOSS2+LOSS3, '-o', label='all together')

ax4.set_ylabel("losses");

ax4.grid()

ax5.set_ylim(0, LOSS1[0]/2)

ax5.plot(X, LOSS1, '-o', label='1st node')

ax5.plot(X, LOSS2, '-o', label='2nd node')

ax5.plot(X, LOSS3, '-o', label='3rd node')

ax5.plot(X, LOSS1+LOSS2+LOSS3, '-o', label='all together')

ax5.set_ylabel("losses");

ax5.grid()

ax6.set_ylim(0, LOSS1[0]/10)

ax6.plot(X, LOSS1, '-o', label='1st node')

ax6.plot(X, LOSS2, '-o', label='2nd node')

ax6.plot(X, LOSS3, '-o', label='3rd node')

ax6.plot(X, LOSS1+LOSS2+LOSS3, '-o', label='all together')

ax6.set_xlabel("num of servers 1");

ax6.set_ylabel("losses");

ax6.grid()

plt.legend()

pp = PdfPages('vkr_graphs.pdf')

plt.savefig(pp, format='pdf')

pp.close()

plt.show()

Моделирование метода динамического программирования

def opt_node3(P, P0, l, MU, C, D, funds):

l3 = ( l*P[0][3]+l*P[0][1]*P[1][3]/(1-P[1][1])+l*P[0][2]*(P[2][3]+P[2][1]*P[1][3]/(1-P[1][1]))/(1-P[2][2]-P[2][1]*P[1][2]/(1-P[1][1]))+l*P[0][1]*P[1][2]/(1-P[1][1])*(P[2][3]+P[2][1]*P[1][3]/(1-P[1][1]))/(1-P[2][2]-P[2][1]*P[1][2]/(1-P[1][1])) ) / ( 1-P[3][1]*P[1][3]/(1-P[1][1])-P[3][3]-P[3][1]*P[1][2]/(1-P[1][1])*(P[2][3]+P[2][1]*P[1][3]/(1-P[1][1]))/(1-P[2][2]-P[2][1]*P[1][2]/(1-P[1][1]))-P[3][2]*(P[2][3]+P[2][1]*P[1][3]/(1-P[1][1]))/(1-P[2][2]-P[2][1]*P[1][2]/(1-P[1][1])) )

l2 = ( l*P[0][2]+l*P[0][1]*P[1][2]/(1-P[1][1])+l3*P[3][1]*P[1][2]/(1-P[1][1])+l3*P[3][2] ) / ( 1-P[2][2]-P[2][1]*P[1][2]/(1-P[1][1]) )

l1 = ( l*P[0][1]+l2*P[2][1]+l3*P[3][1] ) / ( 1-P[1][1] )

L = np.array([l1,l2,l3])

MIN_SETUP = np.array([int(L[0]//MU[0]+1), int(L[1]//MU[1]+1), int(L[2]//MU[2]+1)])

min_pay = MIN_SETUP[0]*C[0] + MIN_SETUP[1]*C[1] + MIN_SETUP[2]*C[2]

rem_funds = funds - min_pay

if (rem_funds < 0):

return(int(0))

delta = 10**(-20)

c_prev = 0

flag = 0

p = np.zeros([3,funds//C.min()+1]) # в i-ой строчке j-го столбца -- стац вер-ть 0 заявок в i-ом приборе при j серверов на нём

for i in range(3):

for j in range(MIN_SETUP[i], funds//C[i]+1):

if (flag == 0):

a = nsum(lambda k: (L[i]/MU[i])**k/factorial(k), [0,j-1])

b = nsum(lambda k: (L[i]/MU[i])**k/factorial(j)/j**(k-j), [j, inf])

c = 1/(a+b)

p[i][j] = c

if (abs(c - c_prev) < delta):

flag = 1

c_prev = c

else:

p[i][j] = c_prev

delta = 10**(-40)

b_prev = 0

flag = 0

decisions_1 = np.zeros([rem_funds//C[0]+1,2])

temp = np.zeros(rem_funds//C[0] + 1)

for i in range(rem_funds//C[0]+1):

cur_serv = MIN_SETUP[0]+i # количество приборов на узле

a = C[0]*cur_serv

if (flag == 0):

b = D[0]*p[0][cur_serv]*nsum(lambda x: (x-cur_serv)*(L[0]/MU[0]/cur_serv)**x, [cur_serv, inf])

temp[i] = a + b

if (abs(b - b_prev) < delta):

flag = 1

else:

temp[i] = a + b_prev

x = np.argmin(temp[:i+1])

decisions_1[i][0] = temp[x]

decisions_1[i][1] = x

delta = 10**(-40)

b_prev = 0

flag = 0

decisions_2 = np.zeros([rem_funds//C[1]+1, 3])

temp = np.zeros(rem_funds//C[1]+1)

for i in range(rem_funds//C[1]+1):

cur_serv = MIN_SETUP[1] + i # количество приборов на узле

a = C[1]*cur_serv

if (flag == 0):

b = D[1]*p[1][cur_serv]*nsum(lambda x: (x-cur_serv)*(L[1]/MU[1]/cur_serv)**x, [cur_serv, inf])

temp[i] = a + b

if (abs(b - b_prev) < delta):

flag = 1

else:

temp[i] = a + b_prev

x = np.argmin(temp[:i+1])

rest = (rem_funds - x*C[1])//C[0] # столько можем поставить на 1 узел

decisions_2[i][0] = temp[x] + decisions_1[rest][0]

decisions_2[i][1] = decisions_1[rest][1]

decisions_2[i][2] = x

delta = 10**(-40)

b_prev = 0

flag = 0

decisions_3 = np.zeros([rem_funds//C[2]+1, 4])

temp = np.zeros(rem_funds//C[2]+1)

for i in range(rem_funds//C[2]+1):

cur_serv = MIN_SETUP[2] + i # количество приборов на узле

a = C[2]*cur_serv

if (flag == 0):

b = D[2]*p[2][cur_serv]*nsum(lambda x: (x-cur_serv)*(L[2]/MU[2]/cur_serv)**x, [cur_serv, inf])

temp[i] = a + b

if (abs(b - b_prev) < delta):

flag = 1

else:

temp[i] = a + b_prev

x = np.argmin(temp[:i+1])

rest = (rem_funds - x*C[2])//C[1] # столько можем поставить на 2 узел

decisions_3[i][0] = temp[x] + decisions_2[rest][0]

decisions_3[i][1] = decisions_2[rest][1]

decisions_3[i][2] = decisions_2[rest][2]

decisions_3[i][3] = x

decisions_3[:,1:] += MIN_SETUP

best_setup = np.argmin(decisions_3[:,0])

return decisions_3[best_setup]

D = np.array([1000,1000,1000])

C = np.array([10,10,10])

P = np.array([[0,1,0,0],[1/6,0,1/3,1/2], [0,3/4,0,1/4], [0,3/4,1/4,0]])

P0 = np.array([0,1,0,0])

l = 30

MU = np.array([100, 40, 50])

funds = 180

MIN = 10

k = 0

X = np.zeros(MIN)

Y = np.zeros(MIN)

Y1 = np.zeros(MIN)

Y2 = np.zeros(MIN)

Y3 = np.zeros(MIN)

for i in range(1, 300, 10):

D[0] = i

#D[1] = i

#D[2] = i

x = opt_node3(P,P0,l,MU,C,D,funds)

#print(x)

if (k < MIN):

X[k] = i

if (type(x) is int):

Y[k] = 0

Y1[k] = 0

Y2[k] = 0

Y3[k] = 0

else:

Y[k] = x[0]

Y1[k] = x[1]

Y2[k] = x[2]

Y3[k] = x[3]

k += 1

else:

X = np.append(X, i)

if (type(x) is int):

Y = np.append(Y, 0)

Y1 = np.append(Y1, 0)

Y2 = np.append(Y2, 0)

Y3 = np.append(Y3, 0)

else:

Y = np.append(Y, x[0])

Y1 = np.append(Y1, x[1])

Y2 = np.append(Y2, x[2])

Y3 = np.append(Y3, x[3])

k += 1

if (np.min(X) == 0):

a = np.argmin(X)

X = np.delete(X, np.s_[a::])

Y = np.delete(Y, np.s_[a::])

Y1 = np.delete(Y1, np.s_[a::])

Y2 = np.delete(Y2, np.s_[a::])

Y3 = np.delete(Y3, np.s_[a::])

f, (ax1, ax2) = plt.subplots(2, 1, sharex=True, figsize=(10,10))

ax1.plot(X, Y1, '-s', label='1st node')

ax1.plot(X, Y2, '-x', ms = 10, label='2st node')

ax1.plot(X, Y3, '-o', ms = 5, label='3st node')

ax1.set_ylabel("number of servers");

ax1.grid()

ax1.legend()

ax2.plot(X, Y, '-o', label='total minimal cost')

ax2.set_ylabel("cost");

ax2.grid()

ax2.legend()

ax2.set_xlabel('$d_1$')

pp = PdfPages('vkr_test_new.pdf')

plt.savefig(pp, format='pdf')

pp.close()

plt.show()

Размещено на Allbest.ru

...