A Survey on Queuing Systems with Parallel Servingof Customers. Part II

Cover Page

Abstract


This paper is a continuation of the survey of the “fork-join” queuing systems (in the westernclassification) or the systems with splitting of queries. Interest in such systems is explainedby a wide range of problems that can be solved with their help, since in fact it is a matter ofparallel processing of data and their applications. For example, this may concern the analysis ofdisk arrays, cloud computing, high-performance services and even the process of picking ordersin a warehouse. In the first part of the survey, the main features of the described model (andrelated systems) and its construction were introduced. Also the detailed description of theapproach to obtaining an accurate expression of the average response time in the case of twodevices was presented as well as several methods of approximate analysis of this characteristic(the case when the number of devices is more than two). This part of the survey is devotedto the description of other existing methods for approximating the average response time. Inparticular, the approaches of the approximate analysis of the response time are as follows: thematrix-geometric method, the analysis with the help of order statistics for various types ofdistribution of the service time of subqueries.


1. Введение Наряду с такими методами аппроксимации среднего времени отклика системы с расщеплением запросов, как эмпирический подход и интерполяция с помощью предельных значений загрузки системы [1], отдельного внимания заслуживают матрично-геометрический метод и анализ с помощью порядковых статистик, которому посвящена большая часть статьи, поскольку известные результаты теории порядковых статистик позволяют расширить ряд изучаемых распределений для входящего потока и времени обслуживания, а также оценить не менее важные характеристики для рассматриваемой системы: математическое ожидание и дисперсию времени синхронизации. Под временем синхронизации здесь фактически подразумевается её задержка, т.е. время между окончанием обслуживания первого и последнего подзапросов одного запроса [2]. Статья организована следующим образом: в разделе 2 описываются особенности и результаты применения матрично-геометрического метода к анализу системы с расщеплением запросов, в разделе 3 представлен подход к анализу среднего времени отклика, основанный на теории порядковых статистик, в заключении кратко подведены итоги работы. 2. Анализ с помощью матрично-геометрического метода Идея использования матрично-геометрического подхода при анализе fork-join систем в большинстве работ сводится к рассмотрению моделей, аппроксимирующих исходную, непосредственный анализ которых позволяет сделать вывод, что изучаемый процесс, описывающий поведение системы, является квазипроцессом «размножения и гибели» со всеми вытекающими из этого следствиями [3 - 5]. То же касается и fork-join системы с конечными очередями к серверам в условиях пуассоновского входящего потока и экспоненциальных времён обслуживания. Так, в [6, 7] был предложен алгоритм, позволяющий свести матрицу вероятностей переходов для марковского процесса, описывающего поведение системы, к блочно-диагональному виду, что даёт возможность компактно записать систему уравнений равновесия (СУР) и решить её одним из известных численных методов и, как следствие, вычислить среднее время отклика. Матрично-геометрический подход для оценки времени отклика fork-join системы используется в серии статей [8 - 10]. В первой работе [8] были предложены две модели, аппроксимирующие исходную fork-join систему с ветвями || 1 и различными интенсивностями обслуживания на разных серверах (приборах): 1) поступающий запрос принимается в систему тогда и только тогда, когда число подзапросов -го типа, находящихся в системе, меньше некоторого фиксированного положительного целого числа , в противном случае он теряется; 2) отказ в обслуживании на -м сервере происходит тогда и только тогда, когда нарушается условие: для некоторого и для фиксированных положительных целых чисел причём сервер блокируется до тех пор, пока подзапрос не закончит обслуживаться на сервере . Здесь вектор отражает состояние системы, - число подзапросов -го типа в системе, В результате анализа обеих систем с помощью матрично-геометрического метода удаётся определить стационарное распределение числа подзапросов в системах ( ⃗ ). Далее полученное распределение используется при алгоритмическом решении задачи нахождения функции распределения времени оклика: > 0. Таким образом, задача сводится к поиску условного распределения времени отклика при условии, что система находится в состоянии ⃗ . Для первой модифицированной модели искомое условное распределение может быть выражено с помощью распределения Эрланга, а во втором случае условное распределение получается при анализе процесса поглощения для подзапросов. Кроме того, авторы доказали, что решения, полученные при анализе этих двух систем, являются верхней и нижней границами для функции распределения времени отклика соответственно. В следующей статье авторов [9] изучается fork-join система с пуассоновским входящим потоком, но при этом время обслуживания на однородных серверах имеет распределение Кокса. Отметим, что для стационарных вероятностей состояний в СМО | | 1 известно точное решение [11]. Как и в предыдущей работе рассматриваются две аналогичные, аппроксимирующие исходную систему модели: 1) модель, в которой все очереди кроме очереди к первому серверу имеют конечную ёмкость; 2) модель, в которой вводится ограничение на то, что разница между каждой парой длин очередей к серверам не должна превышать заданный порог. Матрично-геометрический анализ указанных систем, предложенный в [12], благодаря тому, что матрицы вероятностей перехода сводятся к блочно-треугольному виду, позволяет получить стационарные вероятности, которые используются для вывода распределения времени отклика, а, соответственно, и моментов этого распределения. Полученные выражения являются верхними и нижними границами для моментов времени отклика. Следующая работа [10] продолжает начатые исследования. Авторы предлагают алгоритмический метод для вычисления верхних и нижних оценок производительности системы, который, по их мнению, может быть расширен для анализа систем с отличными от пуассоновского входящим потоком и отличным от экспоненциального временем обслуживания на разнородных серверах. Отметим, что матрично-геометрический метод (МГМ) использовался и при анализе систем, родственных fork-join. Так, МГМ был применён для анализа модели независимых серверов (ISM), в [13] с помощью МГМ анализируется split-merge система [I] с двумя ветвями с наложением ограничения на ёмкость накопителя одной из очередей. Были получены выражения для математического ожидания, дисперсии и функции распределения времени отклика. Также был разработан метод аппроксимации для систем с более чем с двумя ветвями. В работах [14, 15] также исследуется fork-join система, но уже с распределением фазового типа для входящего потока и с потерями. В статье [16] рассматривается ещё одна вариация классической fork-join системы, для анализа которой используется МГМ: обслуживание каждого подзапроса происходит в несколько этапов, включая фазу ожидания и фазу объединения родственных подзапросов; существует динамическая политика планирования нагрузки системы для поддержания эффективного использования сервера. 3. Анализ с помощью порядковых статистик Поскольку время отклика fork-join системы классически определяется как максимум, а в некоторых случаях и как минимум из случайных величин времён пребывания подзапросов в системе [17], то естественно, что одним из альтернативных способов оценки среднего времени отклика является использование теории порядковых статистик [18 - 20]. По определению [18 - 20], если - конечная выборка, определённая на некотором вероятностном пространстве , и далее, если перенумеровать последовательность в порядке неубывания таким образом, что, то такая последовательность будет называться вариационным рядом, а его члены - порядковыми статистиками. Случайная величина же () : называется -й порядковой статистикой исходной выборки. Из определения ясно, что . (1) Таким образом, время отклика в терминах теории порядковых статистик, где - положительные случайные величины времён пребывания подзапросов в системе до попадания в буфер синхронизации. Следовательно, математическое ожидание времени отклика можно вычислить, зная распределения экстремальных значений , причём функция распределения второй случайной величины фактически является совместной функцией распределения случайных величин . Обозначим через - функцию распределения, а через ( ) - плотность распределения случайной величины . Если сделать допущение о том, что - независимые, что в нашем случае, как уже говорилось выше, является упрощающим предположением, то: а -й момент случайной величины времени отклика можно определить, вычислив интеграл: Далее, если предположить, что серверы являются однородными, т.е. случайные величины не только независимы, но и одинаково распределены, а, следовательно, их функции и плотности распределения равны между собой: , то Также заметим, что математическое ожидание максимума н.о.р.с.в. можно представить в виде [21]: Для того чтобы проанализировать время отклика, необходимо вычислить указанные интегралы. В зависимости от типа распределения для оценки интегралов могут быть применены численные методы, однако для таких распределений, как экспоненциальное, гиперэкспоненциальное и распределение Эрланга 2-го порядка, распределение Кокса, результат может быть получен в символьном виде [21 - 23]. Вычислительные затраты увеличиваются с ростом ветвей ( ) и увеличением порядка для распределений Эрланга или Кокса. Для уменьшения вычислительных затрат при вычислении максимума может быть использован характеристический максимум [24]. 3.1. Экспоненциальное распределение Допустим, что времена пребывания подзапросов в подсистемах являются независимыми экспоненциально распределёнными случайными величинами с плотностями распределения Для того, чтобы определить моменты высшего порядка максимума независимых экспоненциальных случайных величин, эффективнее с вычислительной точки зрения может быть дифференцирование соответствующее число раз преобразования Лапласа- Стилтьеса (ПЛС) совместной функции распределения максимума по и в последующем приравнивание к нулю. В частности, для случая = 2 функция распределения, плотность распределения и ПЛС [25, 26] равны: Тогда математическое ожидаемое максимума равно [21, 23, 25, 26]: Общее выражение для ПЛС максимума экспоненциально распределённых случайных величин может быть записано в следующем виде [27] где обозначает сложение по модулю . Кроме того, ПЛС максимума независимых экспоненциально распределённых случайных величин с параметрами и плотностью распределения можно представить с помощью рекуррентной формулы [28]: где « / » означает исключение Тогда момент -го порядка максимума независимых экспоненциально распределённых случайных величин равен: Рассмотрим ещё одну важную характеристику производительности системы облачных вычислений - время синхронизации. Время синхронизации определяется как время между поступлением первого и последнего подзапросов одного запроса в буфер синхронизации, иными словами, это разность между максимумом и минимумом из времён пребывания подзапросов в системе: В теории порядковых статистик данная величина называется размахом [18 - 20]. Одни из первых результатов анализа этого показателя были приведены в работе [2], а именно численное решение оптимизационной задачи по минимизации среднего времени синхронизации. В статье [25] были представлены оценки математического ожидания в случае неоднородных приборов, а в случае однородных приборов получена оценка и для дисперсии времени синхронизации: Вычислить дисперсию исследуемой величины, для определения которой недостаточно знать значения дисперсий случайных величин ,max и ,min , можно и в неэкспоненциальном случае, действуя аналогичным образом, а именно пользуясь известными в теории порядковых статистик формулой для функции распределения размаха положительных н.о.р.с.в.: либо непосредственно формулой для вычисления дисперсии размаха выборки объёма н.о.р.с.в. с функцией распределения[18]: 3.2. Распределение Эрланга Формула для аппроксимации среднего времени отклика fork-join системы с распределением Эрланга -го порядка ( ), которое представляет собой сумму независимых случайных величин, распределённых по одному и тому же экспоненциальному закону с параметром для времени пребывания в -й ветви системы, с функцией и плотностью распределения: 3.3. Распределение экстремальных значений Ещё один метод вычисления максимума н.о.р.с.в. - это его аппроксимация распределением экстремальных значений [30]. Распределение экстремальных значений представляет собой предельное распределение наибольшего () (наименьшего (1) ) из значений н.о.р. непрерывных с.в. при бесконечном увеличении их числа → ∞ , т.е., говоря иными словами, это предельное распределение наибольшего (наименьшего) выборочного значения при бесконечном увеличении объёма выборки из непрерывного распределения [30], хотя, конечно, нельзя сказать, что распределение экстремального значения - это распределение () при → ∞ , поскольку фактически оно будет вырожденным, поэтому, чтобы получить невырожденное предельное распределение, рассматривают линейное преобразование () с коэффициентами, зависящими от объёма выборки, что в действительности аналогично нормировке, но по большому счету не исчерпывается только последовательностями линейных преобразований [30]. Существует три типа семейств экстремальных распределений [30]: 1) тип I - распределение типа Гумбеля, которое ещё иногда называют дважды экспоненциальным 2) тип II - распределение типа Фреше: 3) тип III - распределение типа Вейбулла где 0 - параметры. Распределения типа II и III приводятся к распределению типа I с помощью преобразований , соответственно, поэтому в основном акцент делается на распределении типа Гумбеля, плотность распределения которого имеет вид: а математическое ожидание и дисперсия равны: где , 577721 - это постоянная Эйлера-Маскерони. При получается стандартная форма распределения типа I - распределение Гумбеля: В [30] упоминается об установленной связи между свойствами генерального распределения ( ) и типом предельного распределения. Полученные условия, которым, вообще говоря, удовлетворяют далеко не все распределения (например, распределения с «тяжёлыми хвостами»), являются необходимыми и достаточными для сходимости к одному из трёх типов семейств экстремальных значений и касаются поведения ( ) при больших (малых) значениях , если речь идёт о наибольших (наименьших) значениях случайных величин. Причём при одном и том же исходном распределении наибольшее и наименьшее значения могут иметь предельные распределения, относящиеся к разным типам. К распределениям, которые удовлетворяют условию сходимости к типу I можно отнести нормальное, экспоненциальное и логистическое, к типу II - распределение Коши, а к типу III - распределения, сосредоточенные на ограниченной сверху части числовой оси [30]. Так, в [20] было показано, что распределение максимального значения () в выборке из случайных величин с экспоненциальным распределением с параметром = 1 приближается к распределению Гумбеля в его стандартной форме с ростом объёма выборки, т.е. где - это случайная величина с распределением Гумбеля с функцией распределения из (8), математическим ожиданием и дисперсией Отметим, что для случая, когда каждая порядковая статистика имеет стандартное распределение экстремальных значений типа I из (8), математическое ожидание максимума вычисляется по формуле [30]: . 3.4. Произвольное распределение Рассмотрим обобщение вывода в [28] для аппроксимации моментов максимума случайных величин с произвольным распределением [4]. Рассмотрим случайную величину , - неотрицательные и независимые с функциями распределения - это ПЛС этих функций распределения, Тогда математическое ожидание можно выразить следующим образом: Пусть- первые два момента случайной величины - случайной величины 2 . Тогда, если 1 - экспоненциальная, то Далее окончательно получаем следующую аппроксимацию: которая фактически является точным результатом для случая, когда обе случайные величины 1 и 2 имеют экспоненциальное распределение. Таким образом, в общем случае, когда речь идёт о случайных величинах, необходимо аппроксимировать ПЛС функции распределения максимума ( - 1) случайных величин. Поэтому допустим, что уравнение (4) применимо не только к экспоненциальным случайным величинам. Обозначим среднее значение максимума случайных величин с математическими ожиданиями и вторыми моментами. Тогда можно выразить рекуррентно Результаты моделирования для оценки точности приближения приведены в [28], а также в [31] с использованием уравнения из (2). Рассматриваются следующие распределения: распределение Эрланга 2-го, 3-го и 4-го порядков и распределение Парето с функцией распределения вида Условие > 2 необходимо для того, чтобы первые два момента были конечными, так что . Погрешность аппроксимации выражений (9) и (2) мала и для 2 , но быстро увеличивается начиная с . Интересно, что оба уравнения дают точные результаты для распределения Парето, а последнее уравнение даёт более точные результаты в обоих случаях. 3.5. Аппроксимация на основе границ моментов порядковых статистик Если математическое ожидание и дисперсию генерального распределения обозначить и 2 соответственно, то справедливо [18, 19]: Поэтому в [18,19] для максимума н.о.р.с.в. () была предложена аппроксимация следующего вида: Заметим, для экспоненциального распределения справедливо, что а для равномерного распределения выполняется: [27]. Если же математическое ожидание равно нулю, а стандартное квадратическое отклонение равно единице, то, очевидно, Знак равенства в выражении (11) имеет место для н.о.р.с.в. с функцией и плотностью распределения Для аппроксимации ожидаемого значения максимума н.о.р.с.в. с нормальным распределением в работе [32] используется в формуле (10), т.е.: Более точная аппроксимация дана в [30]: Стоит отметить, что в уравнении (12) существует некоторый сдвиг (смещение), который корректируется путём вычитания 0 , из выражения в скобках в (12) [33]. Таким образом, имеем: На основе формулы (10) в [34] для случайной величины времени отклика было представлено приближение где max обозначают математическое ожидание и среднее квадратическое отклонение времени отклика СМО || 1 с коэффициентом загрузки системы . Напомним, что если времена обслуживания подзапросов распределены по произвольному закону [4], то математическое ожидание максимума н.о.р.с.в. с функцией распределения ( ). Легко показать, что для экспоненциального распределения , а для распределения экстремальных значений [30]. Сравнительный анализ полученного приближения и результатов имитационного моделирования при заданном распределении времени отклика может быть использован для получения выражения [34]: Так, например, для fork-join системы с двумя ветвями || 1 из выражения (6) следует, что Заключение В статье рассмотрены подходы к приближенному анализу времени отклика: матрично-геометрический метод, анализ с помощью порядковых статистик для различных типов распределения времени пребывания подзапросов в системе. Также приводятся результаты для математического ожидания и дисперсии времени синхронизации. Стоит отметить, что существуют исследования, посвящённые анализу работы сетей массового обслуживания, в качестве узла или узлов которой выступает система с расщеплением, но обзор подобных работ выходит за рамки поставленной перед авторами задачи.

A V Gorbunova

Peoples’ Friendship University of Russia (RUDN University)

Author for correspondence.
Email: gorbunova_av@rudn.university
6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Gorbunova A. V. - Candidate of Physical and Mathematical Sciences, assistant of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University)

I S Zaryadov

Peoples’ Friendship University of Russia (RUDN University); Institute of Informatics Problems Federal Research Center “Computer Science and Control” Russian Academy of Sciences

Email: zaryadov_is@rudn.university
6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation; 44-2 Vavilova St., Moscow, 119333, Russian Federation

Zaryadov I. S. - Candidate of Physical and Mathematical Sciences, assistant professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Senior Researcher of Institute of Informatics Problems of Federal Research Center “Computer Science and Control” Russian Academy of Sciences

K E Samouylov

Peoples’ Friendship University of Russia (RUDN University)

Email: samuylov_ke@rudn.university
6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Samouylov K. E. - professor, Doctor of Engineering Science, head of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University)

  • A. V. Gorbunova, I. S. Zaryadov, K. E. Samouylov, E. S. Sopin, A Survey on Queuing Systems with Parallel Serving of Customers, RUDN Journal of Mathematics, Information Sciences and Physics 25 (4) (2017) 350–362, in Russian.
  • I. Tsimashenka, W. J. Knottenbelt, Reduction of Subtask Dispersion in Fork-Join Systems, in: Computer Performance Engineering, Springer Berlin Heidelberg, 2013, pp. 325–336.
  • G. P. Basharin, Lectures on the Mathematical Theory of Teletraffic, PFUR, Moscow, 2009, in Russian.
  • P. P. Bocharov, A. V. Pechinkin, Queueing Theory, PFUR, Moscow, 1995, in Russian.
  • P. Bocharov, C. D’Apice, A. Pechinkin, S. Salerno, Queueing theory, Brill Academic Publishers, 2004.
  • E. V. Mokrov, K. E. Samouylov, Modeling of Cloud Computing as a Queuing System with Batch Arrivals, T-Comm — Telecommunications and transport 11 (7) (2013) 139–141, in Russian.
  • E. V. Mokrov, A. V. Chukarin, Performance Analysis of Cloud Computing System with Live Migration, T-Comm — Telecommunications and transport 8 (8) (2014) 64–67, in Russian.
  • S. Balsamo, I. Mura, Approximate Response Time Distribution in Fork and Join Systems, SIGMETRICS Performance Evaluation Review 23 (1) (1995) 305–306.
  • S. Balsamo, I. Mura, On Queue Length Moments in Fork and Join Queuing Networks with General Service Times, Computer Performance Evaluation Modelling Techniques and Tools. LNCS 1245 (1997) 218–231.
  • S. Balsamo, L. Donatiello, N. M. Van Dijk, Bound Performance Models of Heterogeneous Parallel Processing Systems, IEEE Transactions on Parallel and Distributed Systems 9 (10) (1998) 1041—-1056.
  • H. G. Perros, On the
  • M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, Courier Corporation, 1981.
  • B. M. Rao, M. J. M. Posner, Algorithmic and Approximation Analyses of the Split and Match Queue, Stochastic Models 1 (3) (1985) 433–456.
  • M. Takahashi, H. ¯ Osawa, T. Fujisawa, On a Synchronization Queue with Two Finite Buffers, Queueing Systems 36 (2000) 107–123.
  • M. Takahashi, Y. Takahashi, Synchronization Queue with Two MAP Inputs and Finite Buffers, in: Proc. of the Third International Conference on Matrix Analytical Methods in Stochastic Models, 2000, pp. 375–390.
  • M. S. Squillante, Y. Zhang, A. Sivasubramaniam, N. Gautam, Generalized Parallel- Server Fork-Join Queues with Dynamic Task Scheduling, Annals of Operations Research 160 (1) (2008) 227–255.
  • G. Joshi, E. Soljanin, G. Wornell, Efficient Redundancy Techniques for Latency Reduction in Cloud Systems, arXiv preprint arXiv:1508.03599.
  • H. A. David, Order Statistics, Wiley, New York, 1981.
  • H. A. David, H. N. Nagaraja, Order Statistics, John Wiley & Sons, 2003.
  • E. J. Gumbel, Statistics of Extremes, Columbia University Press, New York, 1958.
  • A. O. Allen, Probability, Statistics, and Queueing Theory: With Computer Science Applications, Gulf Professional Publishing, 1990.
  • L. Kleinrock, Queueing Systems, Volume I: Theory, Wiley Interscience, 1975.
  • K. S. Trivedi, Probability and Statistics with Reliability, Queueing, and Computer Science Applications (2nd ed.), John Wiley & Sons, 2002.
  • A. Gravey, A Simple Construction of an Upper Bound for the Mean of the Maximum of
  • A. V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin, The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests, Distributed Computer and Communication Networks. DCCN 2016. Communications in Computer and Information Science 678 (2016) 418–429.
  • K. E. Samouylov, I. S. Zaryadov, A. V. Gorbunova, The Response Time Analysis of Cloud Computing System, T-Comm — Telecommunications and transport 9 (11) (2015) 57–61, in Russian.
  • A. Thomasian, Analysis of Fork/Join and Related Queueing Systems, ACM Computing Surveys (CSUR) 47 (2) (2014) 17:1–17:71.
  • P. Harrison, Z. S., Queueing Models with Maxima of Service Times, in: Computer Performance Evaluation. Modelling Techniques and Tools, Springer Berlin Heidelberg, 2003, pp. 152–168.
  • A. Thomasian, J. Menon, RAID5 Performance with Distributed Sparing, IEEE Transactions on Parallel and Distributed Systems 8 (6) (1997) 640–657.
  • N. L. Johnson, S. Kotz, N. Balakrishnan, Continuous Univariate Distributions, Vol. 1, Wiley Series in Probability and Statistics, 1995
  • A. S. Lebrecht, W. J. Knottenbelt, Response Time Approximations in Fork-Join Queues, in: In Proceedings of the 23rd Annual UK Performance Engineering Workshop (UKPEW’07), 2007.
  • B. C. Arnold, Distribution-Free Bounds on the Mean of the Maximum of a Dependent Sample, SIAM Journal on Applied Mathematics 38 (1) (1985) 163–167.
  • M. Petzold, A Note on the First Moment of Extreme Order Statistics from the Normal Distribution, in: rapport nr.: Seminar Papers, 2000.
  • A. Thomasian, A. N. Tantawi, Approximate Solutions for

Views

Abstract - 145

PDF (Russian) - 29


Copyright (c) 2018 Gorbunova A.V., Zaryadov I.S., Samouylov K.E.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.