Открытые сети Джексона - Курсовая работа

В работе вычисляются такие операционные характеристики сети, как максимальная пропускная способность, среднее время ожидания обслуживания, среднее число отказов в обслуживании. Разработана на языке python имитационная модель открытой сети Джексона. Результаты моделирования используются для оптимизации параметров сети. This paper presents the research of open Jackson networks.А в ситуации, когда необходимо будет рассматривать систему с более сложной дисциплиной обслуживания (например, когда заявка не сразу покидает систему) или с различным числом приборов какого-то типа, сложность задачи возрастает еще больше. В рамках теории сетей рассматривают сеть массового обслуживания, состоящую из N узлов, каждый из которых является системой массового обслуживания со своими характеристиками (число приборов, длина очереди, дисциплина обслуживания и т.д.). Эти графики, приведенные на рис.2 и рис.3, в различном масштабе показывают зависимость времени ожидания на каждом из узлов и суммарное время ожидания от количества приборов на 1-ом узле. Пусть имеются следующие характеристики: После 1000 итераций моделирования системы в течение 100 ед. времени получим следующие графики: Рис.5 Изменение времени ожидания и количества потерь при увеличении количества приборов на 1 узле, Первые три графика в различном масштабе показывают зависимость времени ожидания на каждом из узлов и суммарное время ожидания от количества приборов на 1-ом узле. Рис.6 Изменение времени ожидания и количества потерь при увеличении количества приборов на 1 узле, При увеличении интенсивности входящего потока оптимальное с точки зрения количества потерь количество приборов на 1-ом узле также увеличивается, но для суммарного времени ожидания минимум достигается при таком же количестве приборов .Для системы, в которой внешний узел соединен только с одним внешним, были получены аналитические формулы для вычисления операционных характеристик. Используя полученные формулы и разработанную имитационную модель, построены графики зависимостей операционных характеристик от количества приборов на узле, соединенном с внешним узлом.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] 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 #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] 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.

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

Например, облачные вычисления, как новый способ предоставления вычислительной среды, которая одновременно является гибкой и надежной, становятся все более интересными для исследователей, инженеров, разработчиков и обычных пользователей. Недавние исследования показывают, что облачные вычисления - многообещающая технология, которая изменит способ доступа к вычислениям и ресурсам сети [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.