API tools faq
paste
Advertisement
Infiniti_Inter

Untitled

Infiniti_Inter
May 20th, 2020
431
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 45.36 KB | None | 0 0
raw download clone embed print report
  1. \documentclass[bachelor, och, coursework, times]{SCWorks}
  2.  
  3. % параметр - тип обучения - одно из значений:
  4. % spec - специальность
  5. % bachelor - бакалавриат (по умолчанию)
  6. % master - магистратура
  7. % параметр - форма обучения - одно из значений:
  8. % och - очное (по умолчанию)
  9. % zaoch - заочное
  10. % параметр - тип работы - одно из значений:
  11. % referat - реферат
  12. % coursework - курсовая работа (по умолчанию)
  13. % diploma - дипломная работа
  14. % pract - отчет по практике
  15. % pract - отчет о научно-исследовательской работе
  16. % autoref - автореферат выпускной работы
  17. % assignment - задание на выпускную квалификационную работу
  18. % review - отзыв руководителя
  19. % critique - рецензия на выпускную работу
  20. % параметр - включение шрифта
  21. % times - включение шрифта Times New Roman (если установлен)
  22. % по умолчанию выключен
  23. \usepackage[T2A]{fontenc}
  24. \usepackage[utf8]{inputenc}
  25. \usepackage{graphicx}
  26.  
  27. \usepackage{subcaption}
  28.  
  29.  
  30. \usepackage{algorithm}
  31. \usepackage{algpseudocode}
  32.  
  33. \usepackage[sort,compress]{cite}
  34. \usepackage{amsmath}
  35. \usepackage{amssymb}
  36. \usepackage{amsthm}
  37. \usepackage{fancyvrb}
  38. \usepackage{longtable}
  39. \usepackage{array}
  40. \usepackage{cellspace}
  41. \usepackage{booktabs}
  42. \usepackage{multirow}
  43.  
  44.  
  45. \usepackage{color}
  46. \usepackage[english,russian]{babel}
  47.  
  48. \usepackage[pdfborder={0 0 0}]{hyperref}
  49.  
  50. \newcommand{\eqdef}{\stackrel {\rm def}{=}}
  51.  
  52. \newtheorem{lem}{Лемма}
  53. \newcommand{\tab}{\ \ \ \ \ \ \ \ \ }
  54. \renewcommand{\listalgorithmname}{Список алгоритмов}
  55. \floatname{algorithm}{Алгоритм}
  56.  
  57. \newcommand{\hl}[1]{\textcolor{green}{#1}}
  58.  
  59.  
  60. \begin{document}
  61.  
  62. % Кафедра (в родительном падеже)
  63. \chair{системного анализа и автоматического управления}
  64.  
  65. % Тема работы
  66. \title{Моделирование служб очередей сообщений}
  67. %ВАРИАНТ ВАРИАНТ ВАРИАНТ ВАРИАНТ ВАРИАНТ
  68. % Курс
  69. \course{2}
  70.  
  71. % Группа
  72. \group{281}
  73.  
  74. % Факультет (в родительном падеже) (по умолчанию "факультета КНиИТ")
  75. %\department{факультета Компьютерный наук и информационных технологий}
  76.  
  77. % Специальность/направление код - наименование
  78. \begin{center}
  79. \napravlenie{27.03.03 "-— Системный анализ и управление}
  80. \end{center}
  81. %\napravlenie{02.03.02 "-— Фундаментальная информатика и информационные технологии}
  82. %\napravlenie{02.03.01 "-— Математическое обеспечение и администрирование информационных систем}
  83. %\napravlenie{09.03.01 "-— Информатика и вычислительная техника}
  84. %\napravlenie{09.03.04 "-— Программная инженерия}
  85. %\napravlenie{10.05.01 "-— Компьютерная безопасность}
  86.  
  87. %Для студентки. Для работы студента следующая команда не нужна.
  88. \studenttitle{cтудента}
  89.  
  90. % Фамилия, имя, отчество в родительном падеже
  91. \author{Попова Данила Валерьевича}
  92. %ФИО ФИО ФИО ФИО ФИО
  93. % Заведующий кафедрой
  94. \chtitle{к.\,ф.-м.\,н.,\,доцент} % степень, звание
  95. \chname{И.\,Е.\,Тананко}
  96.  
  97.  
  98.  
  99. %Научный руководитель (для реферата преподаватель проверяющий работу)
  100. \dolzh{доцент} %должность
  101. \satitle{доцент, к.\,ф.-м.\,н.\,} %степень, звание
  102. \saname{О.\,А.\,Осипов}
  103.  
  104. % Руководитель практики от организации (только для практики,
  105. % для остальных типов работ не используется)
  106. %\patitle{к.\,ф.-м.\,н., доцент}
  107. %\paname{И.\,Е.\,Тананко}
  108.  
  109. % Семестр (только для практики, для остальных
  110. % типов работ не используется)
  111. %\term{3}
  112.  
  113. % Наименование практики (только для практики, для остальных
  114. % типов работ не используется)
  115. %\practtype{Учебная практика}
  116.  
  117. % Год выполнения отчета
  118. \date{2020}
  119.  
  120. \maketitle
  121. \tableofcontents
  122. \intro
  123.  
  124.  
  125. Очередь сообщений как сервис (Message Queuing as service~--- MaaS) стала популярной облачной\ службой и сегодня предлагается ведущими "облачными"\ поставщиками услуг. Microsoft Windows Azure Queue Service, StormMQ, IronMQ, RabbitMQ, Apache Kafka and ActiveMQ, HiveMQ, \newline CloudAMQP и другие \cite{1, 2, 4, 5, 6, 7, 8, 9}. MaaS можно использовать во многих облачных приложениях, таких как CRM, служба снабжения, веб-сервисы, колл-центры, биржевая торговля, логистические решения, системы инвентаризации, решения по управлению автопарком, и даже для агрегации, очереди и обработки данных Internet of Things (IoT), как в CloudMQTT\cite{10}. Обычно, эти "облачные"\ приложения имеют несколько частей или машин, участвующих в обработке требований, которые помещаются в централизованную очередь. Обслуживание поставленного в очередь требования обычно выполняется последовательно в несколько этапов, прежде чем оно выйдет из очереди.
  126.  
  127. Учитывая ожидаемую интенсивность входящего потока, размер очереди и интенсивность обслуживания на каждом этапе работы приложения, модель может оценить производительность приложения с точки зрения общих параметров SLA, таких как пропускная способность, время отклика и вероятность потери запроса. Таким образом, инженеры могут настроить и скорректировать базовую конфигурацию приложения и размер очереди MaaS, чтобы немедленно удовлетворить данное SLA. Регулируемые параметры могут включать в себя размер очереди и интенсивность обслуживания запросов приложением. Согласование размера очереди может проводиться вручную или автоматически. Интенсивность обслуживания запросов может быть увеличена путем предоставления большего количества облачных вычислительных ресурсов.
  128.  
  129.  
  130. \newpage
  131. %==========================================================================================================
  132.  
  133.  
  134. \section{Обзор MaaS}
  135. ~\
  136.  
  137. Abstract-MaaS это облачный сервис, который позволяет отделам разработки сосредоточиться на доставке бизнес-приложений и вычислительных приложений, не заботясь о базовой инфраструктуре очереди сообщений, согласованности, безопасности и надежности.
  138.  
  139. Оценка задержки обслуживания (до предоставления облачных ресурсов) такого типа облачных приложений является важной инженерной проблемой и проблемой управления ресурсами. Такая оценка поможет вычислить общую задержку сети и сервиса, с которой сталкиваются пользователи. В каком-то смысле провайдеры облачных услуг выделяли бы соответствующие мощности для необходимых облачных ресурсов в соответствии с параметрами Соглашения об уровне сервиса (SLA). В данной работе рассматривается аналитическая модель с использованием цепи Маркова для изучения производительности облачных приложений, использующих MaaS. Учитывая ожидаемую интенсивность потока, размер очереди и ожидаемая интенсивность обслуживания на каждом этапе обработки облачного приложения, рассматриваемая аналитическая модель может оценить производительность приложения с точки зрения ключевые параметры SLA, которые включают время отклика, пропускную способность и потеря требований.
  140.  
  141.  
  142. \newpage
  143. %==========================================================================================================
  144.  
  145.  
  146. %==========================================================================================================
  147.  
  148. \section{Модели теории массового обслуживания}
  149.  
  150. Рассмотрим основные понятия теории массового обслуживания.
  151.  
  152. Входящий поток --- это поток требований поступающих в систему и требующих обслуживания. Они возникают случайно и требуют определенного, обычно заранее точно предсказуемого времени для их выполнения.
  153. В простейшем случае входящий поток является пуассоновским: вероятность появления требования в любой сколь угодно малый промежуток времени пропорциональна длине этого промежутка и не зависит от того, возникали или нет требования в предшествующие промежутки времени. Пуассоновский поток обладает тремя свойствами: ординарностью, отсутствием последействия и стационарностью.
  154.  
  155.  
  156. \textit\textbf{Ординарность} --- вероятность появления за элементарный промежуток времени более одного требования сравним с нулем.
  157.  
  158. \textit\textbf{Отсутствие последействия} --- вероятность появления $k$ событий на любом промежутке времени не зависит от того, появлялись или не появлялись события в моменты времени, предшествующие началу рассматриваемого промежутка.
  159.  
  160. \textit\textbf{Стационарность} --- вероятность появления $k$ событий на любом промежутке времени зависит только от числа $k$ и от длительности $t$ промежутка и не зависит от начала его отсчёта
  161.  
  162. Экспоненциальное распределение позволяет моделировать интервалы времени между наступлением событий. Говорят, что величина $\xi$ имеет экспоненциальное (показательное) распределение, если
  163.  
  164. \begin{equation}
  165. P(\xi < x) =
  166. \begin{cases}
  167. 0,&\text{если $x<0$;}\\
  168. 1 - e^{-\lambda x},&\text{если $x \geq 0$;}\\
  169. \end{cases}
  170. \end{equation}
  171.  
  172. Пусть $\xi$ – время ожидания события, тогда из формулы (1) следует, что вероятность того, что это событие наступит раньше $x$ равна $1 - e^{-\lambda x}$. Этот удобный формализм позволяет описывать моменты возникновения случайных событий.
  173.  
  174. Нотация Кендала \textbf{A/B/m/n/k}.
  175.  
  176. Системы, в которых в случайные моменты времени поступают требования, которые необходимо обслужить и имеются устройства для обслуживания этих требований, называются \textbf{системами массового обслуживания} (СМО). Для краткой характеристики СМО Д.Кендалл ввел символику \textbf{A/B/m/n/k}.
  177.  
  178.  
  179. \textbf{n} --- количество мест в очереди (емкость накопителя),
  180.  
  181. \textbf{m} --- количество обслуживающих приборов,
  182.  
  183. \textbf{k} --- количество источников.
  184.  
  185. \textbf{A} и \textbf{B} характеризуют соответственно поток требований и процесс обслуживания, задавая функцию распределения интервалов между требованиями во входном потоке и функцию распределения времен обслуживания.
  186.  
  187. \textbf{A} и \textbf{B} могут принимать значения:
  188.  
  189. $D$ – детерминированное распределение,
  190.  
  191. $M$ – показательное распределение,
  192.  
  193. $\text{E}_r$ – распределение Эрланга порядка $r$,
  194.  
  195. $\text{H}_r$ - гиперпоказательное распределение с $r$ этапами,
  196.  
  197. $G$ – произвольный характер распределения.
  198.  
  199. Цепи Маркова.
  200. Множество случайных величин ${X_n}$ образуют цепь Маркова, если вероятность того, что следующее значение (состояние) равно ${X_{n+1}}$, зависит только от текущего значения ${X_n}$ и не зависит от предыдущих значений процесса. Таким образом, имеется случайная последовательность, в которой воздействие всей предыстории процесса на его будущее полностью сосредоточенно в текущем значении процесса.
  201.  
  202. Изменения состояний в цепи Маркова с дискретным временем могут происходить только в моменты, предопределяемые натуральным рядом чисел, а для
  203. цепи Маркова с непрерывным временем изменение состояния может произойти в любой момент времени, а значит появляется необходимость ввести
  204. в рассмотрение случайную величину, указывающую, как долго процесс остается в текущем(дискретном) состоянии перед тем, как перейдет в
  205. другое состояние. Однако, поскольку, согласно марковскому свойству, вся предыстория процесса полностью заключена в определении текущего состояния, нельзя требовать, чтобы описание этого текущего состояния содержало так де информацию о том, как долго процесс находится в этом состоянии.
  206. Это накладывает существенные ограничения на распределение времени пребывания процесса в данном состоянии. Время пребывания в этом состоянии
  207. должно быть распределено по показательному закону. Таким образом, показательное распределение является непрерывным распределением без последействия. Аналогично в случае цепи Маркова с дискретным временем время пребывания процесса в данном состоянии описывается геометрическим
  208. распределением, которое является единственным дискретным распределением без последействия. Требование отсутствия последействия накладывается на все цепи Маркова и является существенным ограничением общности тех процессов, которое будут рассмотрены\cite{Kleinrok}.
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216. \section{Аналитическая модель}
  217.  
  218.  
  219. На рисунке~\ref{fig2} показана упрощенная модель облачных приложений, использующих MaaS, в виде системы массового обслуживания(СМО). Как показано нарисунке~\ref{fig2}, требование сначала поступает в очередь вместимостью $K-1$, а затем обслуживается \textit{последовательно} на $N$ этапах. Длительность обслуживания требования на этапе $i$ имеет экспоненциальное распределение с параметром $\mu_i$, $i = 1,\dots , N$.
  220.  
  221. Новое требование поступает на $1$\textit{-й этап} только после того, как предыдущее требование покинуло систему, т.е. покинул последний, $N$\textit{-й этап}. Выполнение всех этапов является взаимоисключающим. Это означает, что в любой момент времени обслуживается одно требование. Предполагается, что в систему поступает пуассоновский поток требований с интенсивностью~$\lambda$. Порядок обслуживания поступающих требований - Первый Пришел Первый Обслужен (FCFS - First Come First Served).
  222.  
  223. \begin{figure}[!ht]
  224. \centering
  225. \includegraphics[width=0.9\linewidth]{fig2.pdf}
  226. \caption{\label{fig2}%
  227. Многофазная система массового обслуживания.
  228. }
  229. \end{figure}
  230. % процесс - поток
  231. \textbf{Обоснования адекватности модели}. В \cite{12} было показано, что под большой нагрузкой, что интенсивность прибытия HTTP-запросов следовать пуассоновскому процессу. Другие исследования показали, что процесс поступления других сетевых запросов (например, HTTP или XML)может не всегда является пуассоновским потоком, например имеет место групповое поступление\cite{13}. Кроме того, в реальности время обслуживания не всегда может быть распределено экспоненциально. Для тех предположений, которые связаны с быстрым трафиком и не Пуассоновским поступлением, аналитическое решение становится трудноразрешимым и трудно поддается моделированию. Тем не менее, в литературе широко использовалось моделирование очередей с предположениями о поступлении Пуассоновского потока требований и экспоненциальном времени обслуживания, которые обеспечили адекватное приближение реальных систем \cite{12, 13}.Результаты, полученные в результате анализа, хорошо согласуются с экспериментальными измерениями, полученными в результате генерации реалистичного HTTP-трафика. Наконец, рассматриваемая модель предполагает, что этапы приложения обрабатываются последовательно\cite{11}. Для этого случая рассматриваемая модель все еще полезна, рассматривая распараллеленные вычисления как один этап вычислений с некоторой приблизительной общей интенсивностью обслуживания~$\mu$. Однако, точность такого приближения при использовании параллельных вычислений является предметом дальнейших исследований.
  232.  
  233. Поведение системы может быть описано цепью Маркова с непрерывным временем и бесконечным числом состояний $S$,
  234. \[
  235. S = \{ (k, n),\ 0 \leq k \leq K,\ 0 \leq n \leq N \},
  236. \]
  237.  
  238. где $k$ обозначает число прибвающих в системе требований, а $n$ - активный этап обслуживания. Очередь системы имеет вместимость $K-1$. Другими словами, состояние $(0,0)$ представляет собой особый случай, когда система пуста или простаивает, т.е. состояние бездействия системы. Состояния $(k,n)$ представляют собой состояния, в которых требование обслуживается на этапе $n$ с $k$ требований в системе. На~\ref{fig3} приведена соответствующая диаграмма интенсинвостей перехода между состояниями.
  239.  
  240.  
  241.  
  242. \begin{figure}[!ht]
  243. \centering
  244. \includegraphics[width=0.8\linewidth]{fig3.png}
  245. \caption{\label{fig3}%
  246. Диаграмма интенсивности перехода состояний с многоступенчатой службой}
  247. \end{figure}
  248.  
  249. \newpage
  250. Пусть $p_{k,n}$ есть стационарная вероятность состояния~$(k, n)$. Система уравнений глобольного баланса может быть записана следующим образом:\newline
  251. состояние $(0, 0)$:
  252. \[
  253. 0 = -\lambda p_{0,0} + \mu_N p_{1,N} ,
  254. \]
  255. cостояние~($1, N$):
  256. \[
  257. 0 = - (\lambda + \mu _N)p_{1,N} + \mu _{N-1} p_{1,N-1},
  258. \]
  259. состояние~($1, n$):
  260. \[
  261. 0 = - (\lambda + \mu _n)p_{1,n} + \mu _{n-1} p_{1,n-1}, \quad 2 \leq n \leq N - 1,
  262. \]
  263. состояние~$(1, 1)$:
  264. \[
  265. 0 = - (\lambda + \mu _1)p_{1,1} + \lambda p_{0,0} + \mu _N p_{2,N},
  266. \]
  267. состояние~$(k, N)$:
  268. \[
  269. 0 = - (\lambda + \mu _N)p_{k,N} + \lambda p_{k-1,N} + \mu _{N-1} p_{k,N-1}, \quad 2 \leq k \leq K - 1,
  270. \]
  271. состояние~$(k, n)$:
  272. \[
  273. 0 = - (\lambda + \mu _n)p_{k,n} + \lambda p_{k-1,n} + \mu _{n-1} p_{k,n-1},
  274. \]
  275. \[
  276. 2 \leq k \leq K - 1 ; 2 \leq n \leq N - 1,
  277. \]
  278. состояние~$(k, 1)$:
  279. \[
  280. 0 = - (\lambda + \mu _1)p_{k,1} + \lambda p_{k-1,1} + \mu _{N} p_{k+1,N}, \quad 2 \leq k \leq K - 1,
  281. \]
  282. состояние~$(k, N)$:
  283. \[
  284. 0 = -\mu _N p_{K,N} + \lambda p_{K-1,N} + \mu _{N-1} p_{K,N-1},
  285. \]
  286. состояние~$(k, n)$:
  287. \[
  288. 0 = -\mu _n p_{K,n} + \lambda p_{K-1,n} + \mu _{n-1} p_{k,n-1}, \quad 2 \leq n \leq N - 1,
  289. \]
  290. состояние~$(K, 1)$:
  291. \[
  292. 0 = -\mu _1 p_{K,1} + \lambda p_{K-1,1}.
  293. \]
  294.  
  295. Следовательно, стационарные вероятности состояния $p_{k,n}$ могут быть рекурсивно записаны в терминах $p_{0,0}$. А при использовании нормализации, $p_{0,0}$ может быть выражено как:
  296. \[
  297. p_0 = p_{0,0} = \frac{1}{1 + \sum\limits_{k=1}^K \sum\limits_{n=1}^N \frac{p_{k,n}}{p_{0,0}}}
  298. \]
  299. Тогда все остальные вероятности состояний $\left\{p_{k,n} \colon 1 \leq k \leq K, 1\leq n \leq N\right\}$ могут быть выражены в терминах $p_{0,0}$
  300. Алгоритм 1 показывает, как вычислить все вероятности состояний.
  301.  
  302. \begin{algorithm}
  303. Входные данные: $\lambda, K, N, Vector\ \mu [1 \dots N]$
  304.  
  305. Выходные данные: $p_0, Matrix\ P[1 \dots K, 1 \dots N]$
  306. \caption{Алгоритм 1}\label{alg}
  307. \begin{algorithmic}[1]
  308.  
  309.  
  310. \State $p_0 = 1;$
  311. \State $P[i,j] = 0;$
  312.  
  313. \For {i = 1 to K}
  314. \For {for j = 1 to N}
  315. \State P[i, j] = 0;
  316. \EndFor
  317. \EndFor
  318.  
  319. \State $P[1,N] = \lambda/\mu[N];$
  320.  
  321. \State $P[1, N-1] = ((\lambda + \mu[N])/\mu[N-1])\times P[1,N];$
  322.  
  323. \For {i = N - 1 \textbf{downto} 2}
  324. \State $P[1, i-1] = ((\lambda + \mu[i])/\mu[i-1])\times P[1,i];$
  325.  
  326. \EndFor
  327.  
  328. \State $P[2, N] = ((\lambda + \mu[1])/\mu[N])\times P[1,1] - \lambda/\mu[N];$
  329.  
  330. \For {i = 2 to K-1}
  331. \State $P[i, N-1] = ((\lambda + \mu[N])/\mu[N-1]) \times P[i, N]$
  332.  
  333. $\tab\tab -(\lambda/\mu[N-1])\times P[i-1, N];$
  334.  
  335. \For{j = N - 1 \textbf{downto} 2}
  336. \State $P[i, j -1] = ((\lambda + \mu[j])/\mu[j-1])\times P[i,j] $
  337.  
  338. $\tab\tab -(\lambda/\mu[j-1])\times P[i-1, j];$
  339.  
  340. \EndFor
  341.  
  342. \State $P[i+1, N] = ((\lambda + \mu[1])/\mu[N])\times P[i,1]$
  343.  
  344. $\tab\tab -(\lambda/\mu[N])\times P[i-1, 1]$
  345.  
  346. \EndFor
  347. \State $P[K, N-1] = (\mu[N]/\mu[N-1])\times P[K,N]$
  348.  
  349. \tab\tab$-(\lambda/\mu[N-1]) \times P[K-1, N])$
  350. % \algstore{bkbreak}
  351. \end{algorithmic}
  352. \end{algorithm}
  353.  
  354. \newpage
  355. % \algrestore{bkbreak}
  356. \begin{algorithm}
  357.  
  358. \begin{algorithmic}[1]
  359.  
  360. \For {i = N-1 \textbf{downto} 2}
  361. \State $P[K, i-1] = (\mu[i]/\mu[i-1])\times P[K, i] - (\lambda/\mu[i-1])\times P[K-1,i];$
  362. \EndFor
  363. \State $p_0 = 1/(p_0+sum(P));$
  364. \State $P = p_0 \times P; // p_0 \times \forall p \in P$
  365. \State $return\ p_0, P;$
  366. \end{algorithmic}
  367. \end{algorithm}
  368.  
  369.  
  370. Следовательно, можно определить показатели производительности системы. Во-первых, пропускная способность $\gamma$ может быть выражена как эффективная интенсивность поступления $\lambda'$ которая составляет $\lambda(1 - P_{loss})$. Тогда,
  371. \[
  372. \gamma = \lambda(1 - P_{loss}),
  373. \]
  374. где $P_{loss}$ --- вероятность потери.
  375. $P_{loss}$ может быть выражено как
  376. \[
  377. P_{loss} = p_k = 1 - \frac{1-p_0}{\rho} = \frac{p_0 + \rho - 1}{\rho},
  378. \]
  379. где $\rho = \lambda \bar{X}$ есть коэффициент использования. Также, $P_{loss}$ может быть записано как вероятность пребывания в состояниях $(K,\{1\dots N\})$
  380. \[
  381. P_{loss} = \sum\limits_{n=1}^N p_{K,n}.
  382. \]
  383. Также $\gamma$ может быть выражена как
  384. \[
  385. \gamma = \frac{1-p_0}{\bar{X}},
  386. \]
  387. где $\bar{X}$ --- математическое ожидание длительности обслуживания, которое может быть записано как
  388. \[
  389. \bar{X} = \sum\limits_{n=1}^N \frac{1}{\mu _n}.
  390. \]
  391.  
  392.  
  393. Математическое ожидание $E[K]$ числа требований в системе и математическое ожидание $E[K_q]$ числа требований в очереди имеет вид
  394. \[
  395. E[K] = \sum\limits_{k=1}^K\sum\limits_{n=1}^N kp_{k,n}.
  396. \]
  397.  
  398. \[
  399. E[K_q] = \sum\limits_{k=1}^K \sum\limits_{n=1}^N (k-1)p_{k,n} = E[K] - (1-p_0).
  400. \]
  401. Где $1 - p_0$ определяет математическое ожидание числа требований находящихся на приборах. Используя закон Литтла, математическое ожидание длительности пребывания требований в системе, может быть записано как
  402. \[
  403. W = \frac{E[K]}{\gamma} = \frac{1}{\gamma}\sum\limits_{k=1}^K\sum\limits_{n=1}^N kp_{k,n}.
  404. \]
  405. Тогда для математического ожидания длительности пребывания в очереди справедливо
  406. \[
  407. W_q = \frac{E[K_q]}{\gamma} = W - \bar{X} = \frac{1}{\gamma}\sum\limits_{k=1}^K\sum\limits_{n=1}^N kp_{k,n} - \sum\limits_{n=1}^N \frac{1}{\mu _n}.
  408. \]
  409. Коэффициент использования системы можно записать следующим образом
  410. \[
  411. U = \gamma\bar{X}.
  412. \]
  413. %==========================================================================================================
  414.  
  415. \section{Численный эксперимент}
  416.  
  417. Для вычисления стационарных характеристик и наблюдения за поведением системы при различных начальных условиях была написана программа на ЯП C++. Листинг программы представлен в приложении \ref{code}. Графики приведены ниже.
  418.  
  419. \begin{figure}[!ht]
  420. \centering
  421. \subcaptionbox{График зависимости $U$ от $\rho$}
  422. {\includegraphics{rhoU.pdf}}
  423. \subcaptionbox{График зависимости $\gamma$ от $\rho$}
  424. {\includegraphics{rhogamma.pdf}}
  425.  
  426. \subcaptionbox{График зависимости $E[K]$ от $\rho$}
  427. {\includegraphics{rhoEk.pdf}}
  428. \subcaptionbox{График зависимости $E[K_q]$ от $\rho$}{
  429. \includegraphics{rhoEkq.pdf}}
  430.  
  431.  
  432.  
  433. \end{figure}
  434.  
  435.  
  436. \begin{figure}[!ht]
  437. \centering
  438. \subcaptionbox{График зависимости $p_0$ от $\rho$}
  439. {\includegraphics{rhop0.pdf}}
  440. \subcaptionbox{График зависимости $p_K$ от $\rho$}
  441. {\includegraphics{rhopk.pdf}}
  442.  
  443. \subcaptionbox{График зависимости $W$ от $\rho$}
  444. {\includegraphics{rhoW.pdf}}
  445. \subcaptionbox{График зависимости $W_q$ от $\rho$}
  446. {\includegraphics{rhoWq.pdf}}
  447.  
  448. \subcaptionbox{График зависимости $U$ от $\lambda$}
  449. {\includegraphics{lambdaU.pdf}}
  450. \subcaptionbox{График зависимости $\gamma$ от $\lambda$}
  451. {\includegraphics{lambdagamma.pdf}}
  452.  
  453.  
  454.  
  455. \end{figure}
  456.  
  457. \begin{figure}[!ht]
  458. \centering
  459. \subcaptionbox{График зависимости $E[K]$ от $\lambda$}
  460. {\includegraphics{lambdaEk.pdf}}
  461. \subcaptionbox{График зависимости $E[K_q]$ от $\lambda$}{
  462. \includegraphics{lambdaEkq.pdf}}
  463.  
  464. \subcaptionbox{График зависимости $p_0$ от $\lambda$}
  465. {\includegraphics{lambdap0.pdf}}
  466. \subcaptionbox{График зависимости $p_K$ от $\lambda$}
  467. {\includegraphics{lambdapk.pdf}}
  468.  
  469. \subcaptionbox{График зависимости $W$ от $\lambda$}
  470. {\includegraphics{lambdaW.pdf}}
  471. \subcaptionbox{График зависимости $W_q$ от $\lambda$}
  472. {\includegraphics{lambdaWq.pdf}}
  473. \end{figure}
  474.  
  475. \newpage
  476.  
  477.  
  478. \newpage
  479. %==========================================================================================================
  480.  
  481.  
  482.  
  483. \newpage
  484. %==========================================================================================================
  485.  
  486.  
  487.  
  488.  
  489. \newpage
  490. %==========================================================================================================
  491.  
  492. \conclusion
  493.  
  494.  
  495.  
  496. MaaS используют большое количество компаний, которым необходимо следить за своим оборудованием и программным обеспечением постоянно или достаточно часто.
  497.  
  498. MaaS легко можно модифицировать. Отчетность становится проще: MaaS дает отчет по работе всей инфраструктуры в целом, а не по отдельным ее разделам. Работа любого приложения или устройства может быть включена в отчет.
  499.  
  500. В данной работе была рассмотрена аналитическая модель с использованием цепи Маркова для вычисления стационарных характеристик. Результаты совпали с численными результатами эксперимента, проделанным Халедом Салахом и Тарекой Рахилом Шелтамом в статье\cite{stat}.
  501.  
  502. Таким образом, диспетчер очереди --— это архитектурный паттерн, приложение, которое принимает и отдает сообщения между отдельными модулями/приложениями внутри некоторой сложной системы, где модули/приложения должны общаться между собой --— то есть пересылать данные друг другу.
  503.  
  504.  
  505.  
  506.  
  507. \begin{thebibliography}{99}
  508. \bibitem{1} G.\,Mantri,\,Comparing Windows Azure Queue Service and Amazon Simple Queue Service [Электронный ресурс] : [сайт]. --- URL :
  509. http://gauravmantri.com/2012/03/27/comparing-windows-azure-queue-service-and-amazon-simple-queue-service/
  510.  
  511. \bibitem{2}Amazon Inc., “Amazon Simple Queue Service,” [Электронный ресурс] : [сайт]. --- URL : http://aws.amazon.com/sqs/
  512. http://stormmq.com/cloud-based-mq-services
  513.  
  514. \bibitem{4}Iron.io., IronMQ: Elastic and Scalable Message and Event Handling [Электронный ресурс] : [сайт]. --- URL : http://www.iron.io/products/mq
  515.  
  516. \bibitem{5}RabbitMQ [Электронный ресурс] : [сайт]. --- URL : http://www.rabbitmq.com/
  517.  
  518. \bibitem{6} Kuan-Ching,\,Li. Big Data Management and Processing / Li.\, Kuan-Ching, A.\,Y.\,Zomaya, H.\, Jiang. --- T.~: Chapman and Hall/CRC, 2017. --- 487 с.
  519.  
  520.  
  521. \bibitem{7}ActiveMQ [Электронный ресурс] : [сайт]. --- URL : http://activemq.apache.org/
  522.  
  523. \bibitem{8}HiveMQ [Электронный ресурс] : [сайт]. --- URL : http://www.hivemq.com/
  524.  
  525. \bibitem{9}CloudAMQP [Электронный ресурс] : [сайт]. --- URL : https://www.cloudamqp.com/
  526. \bibitem{10}CloudMQTT [Электронный ресурс] : [сайт]. --- URL : http://www.cloudmqtt.com/docs.html
  527.  
  528. \bibitem{11} J.\,Dean,\,MapReduce: Simplified Data Processing on Large Clusters / J.\,Dean\, S.\,Ghemawat // Communications of ACM 2008. --- 113 c.
  529.  
  530.  
  531. \bibitem{12} M.\,Andersson,\,Web Server Traffic in Crisis Conditions / M.\,Andersson,\,A.\,Bengtsson,\,M.\,Host,\,C.\,Nyberg, // Proceedings of the 3rd Swedish National Computer Networking Workshop --- 2005.
  532.  
  533. \bibitem{13} W.\,Leland,\,On the Self-Similar Nature of Ethernet Traffic / W.\,Leland,\,M.\,Taqqu,\,W.\,Willinger,\,D.\,Wilson, // IEEE/ACM Transaction on Networking --- 1994. --- 213c.
  534.  
  535. \bibitem{Kleinrok} Клейнрок,\,Л. Теория массового обслуживания : Учебник / Л.\,Клейнрок. --- М. : Машиностроение, 1979. --- 432 с.
  536.  
  537. \bibitem{stat} Khaled,\,S. Modeling of Message Queueing as a Service // Computer Engineering Department / S.\, Khaled, \,Tarek\,R.\,S. --- 2018. --- URL: researchgate.net/publication/329698311\_Modeling\_of\_Message\_Queueing
  538. \_as\_a\_Service\_MaaS
  539.  
  540.  
  541.  
  542.  
  543. \end{thebibliography}
  544. \appendix
  545. \section{Вычисление стационарных характеристик}
  546. \label{code}
  547.  
  548.  
  549. \begin{verbatim}
  550. #define _CRT_SECURE_NO_WARNINGS
  551. #include <iostream>
  552. #include <iomanip>
  553. #include <vector>
  554. #include <random>
  555. #include <string>
  556.  
  557. using namespace std;
  558.  
  559. void connectFilesToStandardInputOutputStreams()
  560. {
  561. freopen("input.txt", "r", stdin);
  562. freopen("output.txt", "w", stdout);
  563. ios_base::sync_with_stdio(false);
  564. cin.tie(0);
  565. cout.tie(0);
  566. }
  567. random_device rnd;
  568. mt19937 mersenne(rnd());
  569. int randomSign()
  570. {
  571. return (mersenne() % 2 == 0 ? 1 : -1);
  572. }
  573. double generateSmallNumber(int N = 100)
  574. //функция возвращает случайное значение от [-9;9]/N
  575. //можно использовать для изменения начальных условий
  576. //и наблюдением за системой
  577. {
  578. double res = (mersenne() % 10) / (N);
  579. return res * randomSign();
  580. }
  581. struct systemDescription
  582. {
  583. int K;
  584. int N;
  585. systemDescription(int k, int n)
  586. {
  587. K = max(k, 3);
  588. N = max(n, 3);
  589. }
  590. };
  591. vector< vector< long double > > calcPij
  592. (double lambda, systemDescription par, vector<double> mu)
  593. {
  594. int N = par.N;
  595. int K = par.K;
  596. double p0 = 1;
  597. vector< vector< long double > > P
  598. (K + 1, vector<long double>(N + 1));
  599. for (int i = 1; i <= K; ++i)
  600. for (int j = 1; j <= N; ++j)
  601. P[i][j] = 0;
  602. P[1][N] = lambda / mu[N];
  603. P[1][N - 1] = ((lambda + mu[N]) / mu[N - 1])*P[1][N];
  604. for (int i = N - 1; i > 1; --i)
  605. P[1][i - 1] = (lambda + mu[i]) / mu[i - 1] * P[1][i];
  606. P[2][N] = (lambda + mu[1]) / mu[N] * P[1][1] - lambda / mu[N];
  607. for (int i = 2; i <= K - 1; ++i)
  608. {
  609. P[i][N - 1] = (lambda + mu[N]) / mu[N - 1] * P[i][N]
  610. - (lambda / mu[N - 1]) * P[i - 1][N];
  611. for (int j = N - 1; j >= 2; --j)
  612. P[i][j - 1] = (lambda + mu[j]) / mu[j - 1] * P[i][j]
  613. - (lambda / mu[j - 1]) * P[i - 1][j];
  614. P[i + 1][N] = (lambda + mu[1]) / mu[N] * P[i][1]
  615. - (lambda / mu[N]) * P[i - 1][1];
  616. }
  617. P[K][N - 1] = mu[N] / mu[N - 1] * P[K][N]
  618. - (lambda / mu[N - 1]) * P[K - 1][N];
  619. for (int i = N - 1; i >= 2; --i)
  620. {
  621. P[K][i - 1] = mu[i] / mu[i - 1] * P[K][i]
  622. - (lambda / mu[i - 1]) * P[K - 1][i];
  623. }
  624. long double sumP = 0;
  625. for (int i = 1; i <= K; ++i)
  626. for (int j = 1; j <= N; ++j)
  627. sumP += P[i][j];
  628. p0 = 1 / (p0 + sumP);
  629. for (int i = 1; i <= K; ++i)
  630. for (int j = 1; j <= N; ++j)
  631. P[i][j] *= p0;
  632. P[0][0] = p0;
  633. return P;
  634. }
  635.  
  636. struct performanceMeasures
  637. {
  638. int cntLambda;
  639. double lambda;
  640. vector<double> mu;
  641. double p0;
  642. double X;
  643. double gamma;
  644. double p;
  645. double Ploss;
  646. double Ek;
  647. double Ekq;
  648. double W;
  649. double Wq;
  650. double U;
  651. performanceMeasures() {}
  652. performanceMeasures(int cntLambda, double lambda,
  653. vector<double> mu, double p0, double X,
  654. double gamma, double p, double Ploss, double Ek, double Ekq,
  655. double W, double Wq, double U) : cntLambda(cntLambda),
  656. lambda(lambda), mu(mu), p0(p0), X(X), gamma(gamma), p(p),
  657. Ploss(Ploss), Ek(Ek), Ekq(Ekq), W(W),
  658. Wq(Wq), U(U){}
  659. void Show()
  660. {
  661. string line = string(30, '-');
  662. line += "\n";
  663. cout << line;
  664. cout << "Test #" << cntLambda << endl;
  665. cout << line;
  666. cout << "lambda = " << lambda <<endl;
  667. cout << "mu [] = ";
  668. for (auto v : mu)
  669. cout << v << "\t";
  670. cout << line;
  671. cout << "U = " << U << endl;
  672. cout << "gamma = " << gamma << endl;
  673. cout << "p0 = " << p0 << endl;
  674. cout << "p = " << p << endl;
  675. cout << "E[K] = " << Ek << endl;
  676. cout << "E[Kq] = " << Ekq << endl;
  677. cout << "W = " << W << endl;
  678. cout << "Wq = " << Wq << endl;
  679. cout << "X = " << X << endl;
  680.  
  681. cout << "\n====================================\n";
  682. }
  683.  
  684. static void ShowInfoAboutSystem()
  685. {
  686. cout << "K - размер системы,\n";
  687. cout << "N - количество этапов в системе,\n";
  688. cout << "cntLambda - количество различных лямбда"
  689. << "(корень квадратный из количества экспериментов) ,\n";
  690. cout << "lambda[i] - интенсивность потока
  691. на iм эксперементе,\n";
  692. cout << "mu[i] - вектор интенсивности обслуживания на iм
  693. эксперементе,\n";
  694. cout << "lambdaMin - минимальное значение lambda,\n";
  695. cout << "deltaLambda - разница lambda между двумя
  696. последующими экспериментами,\n";
  697. cout << "coefficientMu - коэффициент роста
  698. интенсивности Mu,\n";
  699. cout << "gamma - пропускная способность,\n";
  700. cout << "Ploss - вероятность потери,\n";
  701. cout << "p - коэффициент использования,\n";
  702. cout << "X - м.о. длительности обслуживания,\n";
  703. cout << "Ek - м.о. числа требований в системе,\n";
  704. cout << "Ekq - м.о. числа требований в очереди,\n";
  705. cout << "W - м.о. длительности пребывания
  706. требований в системе,\n";
  707. cout << "Wq - м.о. длительности пребывания
  708. требований в очереди,\n";
  709. cout << "U - rоэффициент использования системы.";
  710. }
  711. };
  712.  
  713. int main() {
  714. connectFilesToStandardInputOutputStreams();
  715. systemDescription par(8, 5);
  716. int cntLambda = 15;
  717. vector<double> lambda(cntLambda);
  718. vector<vector<double> > mu(cntLambda, vector<double>(par.N + 1));
  719. double lambdaMin = 0.0002;
  720. double deltaLambda = 0.019990;
  721. double coefficientMu = 1.1;
  722. for (int i = 0; i < cntLambda; ++i)
  723. {
  724. lambda[i] = (i == 0 ? lambdaMin : lambda[i - 1] + deltaLambda);
  725.  
  726. for (int j = 0; j < par.N; ++j)
  727. mu[i][j + 1] = coefficientMu*(i + 1);
  728. }
  729. cout << setprecision(3);
  730. vector<performanceMeasures> result(cntLambda * cntLambda);
  731. int cnt = 0;
  732. for (int f = 0; f < cntLambda; f++)
  733. {
  734. for (int i = 0; i < cntLambda; ++i)
  735. {
  736. vector<double> Mu = mu[f];
  737. vector<vector<long double> > P
  738. = calcPij(lambda[i], par, mu[f]);
  739. double p0 = P[0][0];
  740. double SumPkN = 0;
  741. for (int k = 1; k <= par.K; ++k)
  742. SumPkN += P[k][par.N];
  743. double X = 0;
  744. for (int n = 1; n <= par.N; ++n)
  745. X += 1 / Mu[n];
  746. double gamma = (1. - p0) / X;
  747. double p = lambda[i] * X;
  748. double Ploss = (p0 + p - 1) / p;
  749. double SumPKn = 0;
  750. double Ek = 0;
  751. for (int k = 1; k <= par.K; ++k)
  752. for (int n = 1; n <= par.N; ++n)
  753. Ek += P[k][n] * k;
  754. double Ekq = Ek - (1 - p0);
  755. double W = Ek / gamma;
  756. double Wq = Ekq / gamma;
  757. double U = gamma * X;
  758. result[cnt++] = performanceMeasures(cnt, lambda[i], Mu,
  759. p0, X, gamma, p, Ploss, Ek, Ekq, W, Wq, U);
  760. }
  761. for (auto v : result)
  762. v.Show();
  763. performanceMeasures::ShowInfoAboutSystem();
  764. }
  765. return 0;
  766. }
  767. \end{verbatim}
  768.  
  769.  
  770. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!