Software & Systems

Неотъемлемой частью полноценного функционирования многих организаций и предприятий являются большие информационные системы (ИС) [1, 2]. Для успешного запуска системы, которая будет удовлетворять заданным потребностям, еще на этапе проектирования необходимо проводить предварительный анализ характеристик ее функционирования [3, 4]. Одной из наиболее важных характеристик ИС является время отклика на запрос пользователя. Часто для оценки временных характеристик ИС прибегают к анализу модели системы, в роли которой выступает сеть массового обслуживания (СеМО). Время отклика ИС в данном случае соответствует среднему времени пребывания заявки в СеМО [5].

Однако даже в случае использования модели ИС вычисление истинного значения средней задержки для большинства СеМО является сложной, а порой и неразрешимой задачей из-за масштабности исследуемых систем. В таких ситуациях для оценки среднего времени пре-  бывания заявок в сети прибегают к построению граничных значений [6, 7].

В данной работе рассмотрены методы построения верхнего и нижнего граничных значений для средней задержки заявки в СеМО.

Описание математической схемы   большой ИС

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

Рассмотрим сеть, состоящую из пронумерованного набора элементарных систем массового обслуживания. Каждая из систем представляет собой пару «обслуживающее устройство–буфер», в которой обслуживающее устройство является средством выполнения команд транзакций, а буфер – памятью для фиксации результатов выполнения команд транзакций и ожидания времени для поступления на обслуживание. Предлагаемая модель ИС подразумевает, что для нее заранее известен набор последовательностей обслуживающих устройств, в которых с заданной вероятностью будут обрабатываться транзакции. Таким образом, можно сказать, что каждая заявка пользователя ИС проходит определенный маршрут из обслуживающих устройств в СеМО. Также отметим, что при прохождении маршрута заявка не задерживается в промежуточных буферах, так как согласно правилу резервирования ресурсов для выполнения транзакций все обслуживающие устройства на маршруте заявки свободны [8]. Таким образом, набор маршрутов R представляется как список векторов с номерами обслуживающих устройств и полностью описывает структуру СеМО.

Каждый маршрут в СеМО характеризуется вероятностью появления заявок, обслуживаемых на маршруте, а каждое обслуживающее устройство – интенсивностью обслуживания и коэффициентом вариации времени обслуживания.

Методы определения верхней и нижней границ среднего времени отклика   ИС на запрос

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

Рассмотрим модель большой ИС, в которой наблюдаются частые пересечения некоторых маршрутов (рис. 1). Полное множество транзакций включает 16 маршрутов разной длины. Для обеспечения параллельной обработки запросов пользователей предлагается все множество маршрутов разбить на слабосвязанные группы маршрутов – кластеры.

Внутри каждого кластера одновременно может обслуживаться только одна заявка. Поступая на обслуживание, заявка блокирует все обслуживающие устройства своего маршрута. Необходимо понимать, что все смежные маршруты также окажутся заблокированными, поскольку имеют общие вычислительные ресурсы [9, 10]. Это означает, что за счет блокировки маршрутов, соединяющих соседние кластеры (то есть связующих узлов Т5, Т6, Т10, Т8 и Т14 для графа на рис. 1), среднее время пребывания заявок в подграфах, образующих кластеры, не может быть рассчитано независимо от времени обработки заявок на подобных маршрутах.

Таким образом, предлагаются методы оценки верхнего и нижнего граничных значений среднего времени отклика ИС на запрос.

Метод оценки верхней границы подразумевает дублирование связующих узлов и введение в граф зависимости маршрутов дополнительных фиктивных соединений, чтобы кластер вместе со всеми смежными связующими узлами образовал отдельный полносвязный подграф. Очевидно, что связующие узлы Т5, Т6, Т10, Т8 и Т14 на рисунке 1 должны быть продублированы в каждом связанном с ними подграфе и к ним добавлены связи от остальных узлов подграфа. За счет таких дополнений среднее время отклика ИС на запрос будет несколько увеличено, но зато позволит вычислить его для каждого кластера. Верхнее граничное значение среднего времени отклика ИС на запрос для всей СеМО вычисляется по следующей формуле:

где Pk – вероятность поступления заявки в k-й полносвязный подграф; Λk – интенсивность поступления заявок в k-й полносвязный подграф; φk(t) – плотность вероятности времени обслуживания в k-м полносвязном подграфе; Mk – интенсивность обслуживания заявок в k-м полносвязном подграфе.

Метод оценки нижней границы среднего времени отклика ИС на запрос заключается в поиске групп слабо связанных маршрутов, на которых не могут одновременно обрабатываться заявки. Такие группы представляют собой полносвязные подграфы, максимальные по включению вершин, – клики. Поиск клик производится на основе алгоритма Брона–Кербоша, после чего согласно алгоритму LBS (Load Based Strategy) из полученного набора клик выбираются отдельные клики, а связи между ними удаляются.

Согласно алгоритму LBS, разбиение на клики основано на величине загрузки множества маршрутов, входящих в состав клик. На каждом шаге для всех клик рассчитывается среднее время отклика ИС на запрос, после чего выбирается клика, для которой эта величина принимает наибольшее значение (рис. 2). В результате разделения графа маршрутов на отдельные полносвязные подграфы с удалением соединяющих связей будет получен набор групп маршрутов. Все группы могут принимать заявки на обслуживание независимо друга от друга, но в каждой группе может обслуживаться только одна заявка. Таким образом, зная общую интенсивность обслуживания в каждой выделенной клике и плотность вероятности времен обслуживания в узлах подграфа, можно оценить среднее время пребывания заявки в преобразованной СеМО, состоящей из отдельных групп маршрутов.

На рисунке 3 приведены результаты моделирования работы СеМО и определения верхних и нижних граничных значений, найденных по предлагаемым методам.

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

Поскольку оба метода опираются на топологию графа маршрутов транзакций, для оценки влияния структуры СеМО на точность полученных оценок был проведен ряд экспериментов, анализ которых позволил сделать следующие выводы:

-     точность верхней границы среднего времени пребывания заявки в СеМО напрямую зависит от размеров кластеров схожих транзакций;

-     при довольно больших размерах кластеров методы дают возможность получить практически точную оценку временной характеристики системы;

-     увеличение размеров кластеров приво-  дит к сужению коридора возможных значений среднего времени пребывания заявки в СеМО.

Заключение

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

Литература

1.   Проскуряков Н.Е., Ануфриева А.Ю. Анализ и перспективы современных систем хранения цифровых данных // Изв. ТулГУ: Технические науки. 2013. № 3. C. 368–377.

2.   Gnanasundaram S., Shrivastava A. Information Storage and Management. NJ, John Wiley & Sons Publ., 2016, 544 p.

3.   Фомин Д.С., Бальзамов А.В. Проблематика обработки транзакций при использовании микросервисной архитектуры. Изв. вузов. Поволжский регион. Технические науки. 2021. T. 58. № 2. C. 15–23. DOI: 10.21685/2072-3059-2021-2-2.

4.   Кутузов О.И., Татарникова Т.М. Инфокоммуникационные сети. Моделирование и оценка вероятностно-временных характеристик. СПб: Изд-во ГУАП, 2015. 382 с.

5.   Shelest M.N., Bakin E.A. Analysis of parallel queueing network with mutual expectations. WECONF, 2018, pp. 1–4. DOI: 10.1109/WECONF.2018.8604361.

6.   Kutuzov O.I., Tatarnikova T.M. On the acceleration of simulation modeling. Proc. XXII Int. Conf. SCM, 2019, pp. 45–47. DOI: 10.1109/SCM.2019.8903785.

7.   Шелест М.Н. Анализ средней задержки для одной модели сети массового обслуживания с резервированием ресурсов // Информационно-управляющие системы. 2022. № 2. C. 32–41. DOI: 10.31799/  1684-8853-2022-2-32-41.

8.   Challawala S., Mehta C., Patel K., Lakhatariya J. MySQL 8 for Big Data: Effective Data Processing with MySQL 8, Hadoop, NoSQL APIs, and Other Big Data Tools. Packt Publishing, Birmingham, 2017,   266 p.

9.   Богатырев В.А., Богатырев А.В., Богатырев С.В. Оценка надежности выполнения кластерами запросов реального времени // Изв. вузов. Приборостроение. 2014. Т. 57. № 4. С. 46–48.

10. Богатырев В.А., Кармановский Н.С., Попцова Н.А., Паршутина С.А., Воронина Д.А., Богаты-  рев С.В. Имитационная модель поддержки проектирования инфокоммуникационных резервированных систем // Науч.-технич. вестн. информ. технологий, механики и оптики. 2016. Т. 16. № 5. С. 831–838. DOI: 10.17586/2226-1494-2016-16-5-831-838.

References

1.      Proskuryakov N.E., Anufrieva A.Yu. Analysis and prospects of modern systems of storage of figures. Proceedings of the TSU, 2013, no. 3, pp. 368–377 (in Russ.).

2.      Gnanasundaram S., Shrivastava A. Information Storage and Management. NJ, John Wiley & Sons Publ., 2016, 544 p.

3.      Fomin D.S., Balzamov A.V. The problem of transaction processing using microservice architecture. University Proceedings. Volga Region. Technical Sciences, 2021, vol. 58, no. 2, pp. 15–23. DOI: 10.21685/2072-3059-2021-2-2 (in Russ.).

4.      Kutuzov O.I., Tatarnikova T.M. Infocomm Networks. Modeling and Evaluation of Probabilistic-temporal Characteristics. St. Petersburg, 2015, 382 p. (in Russ.).

5.      Shelest M.N., Bakin E.A. Analysis of parallel queueing network with mutual expectations. WECONF, 2018, pp. 1–4. DOI: 10.1109/WECONF.2018.8604361.

6.      Kutuzov O.I., Tatarnikova T.M. On the acceleration of simulation modeling. Proc. XXII Int. Conf. SCM, 2019, pp. 45–47. DOI: 10.1109/SCM.2019.8903785.

7.      Shelest М.N. Average delay estimation for one queueing network model with resource reservation. Information and Control Systems, 2022, no. 2, pp. 32–41. DOI: 10.31799/1684-8853-2022-2-32-41 (in Russ.).

8.      Challawala S., Mehta C., Patel K., Lakhatariya J. MySQL 8 for Big Data: Effective Data Processing with MySQL 8, Hadoop, NoSQL APIs, and Other Big Data Tools. Packt Publishing, Birmingham, 2017, 266 p.

9.      Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S.V. Estimation of reliability of execution of real-time queries. J. of Instrument Engineering, 2014, vol. 57, no. 4, pp. 46–48 (in Russ.).

10.    Bogatyrev V.A., Karmanovskiy N.S., Poptsova N.A., Parshutina S.A., Voronina D.A., Bogatyrev S.V. Simulation model for design support of infocomm redundant systems. Scientific and Technical J. of Information Technologies, Mechanics and Optics, 2016, vol. 16, no. 5, pp. 831–838. DOI: 10.17586/2226-1494-2016-16-5-831-838 (in Russ.).