Модели нестационарной параллельно-последовательной сети обслуживания на примере распределенной системы мониторинга тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Шардаков Кирилл Сергеевич

• Шардаков Кирилл Сергеевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Шардаков Кирилл Сергеевич

Введение

1 Объект, цель и задачи исследования

1.1 Основные компоненты системы мониторинга

1.2 Анализ существующих решений

1.3 Выводы по существующим решениям

1.4 Особенности архитектуры распределенной системы мониторинга

1.5 Постановка задачи исследования

1.6 Выводы по разделу

2 Параллельно-последовательная модель нсо и методы ее расчета

2.1 Распределенная система мониторинга как параллельно-последовательная НСО

2.2 Принципы построения и расчета модели НСО

2.3 Алгоритмы генерации матрицы коэффициентов

2.3.1 Последовательный алгоритм

2.3.1.1 Суть последовательного алгоритма

2.3.1.2 Сравнительный анализ рекурсивного и последовательного алгоритмов

2.3.1.3 Последовательный алгоритм генерации списка состояний в параллельно-последовательной модели

2.3.2 Рекурсивный с группировкой алгоритм

2.3.2.1 Причины разработки

2.3.2.2 Суть рекурсивного с группировкой алгоритма

2.3.2.3 Сравнительный анализ рекурсивного и рекурсивного с группировкой алгоритмов

2.3.2.4 Особенности программной реализации рекурсивного с группировкой алгоритма

2.4 Формирование правил переходов и матрицы коэффициентов

2.5 Особенности программной реализации решения системы ОДУ

2.6 Выводы по разделу

3 Программный комплекс моделей

3.1 Аналитическая модель

3.1.1 Суть и характеристики

3.1.2 Детали программной реализации

3.1.3 Моделирование работы в нестационарном режиме

3.2 Имитационная модель

3.2.1 Суть и характеристики

3.2.2 Детали программной реализации

3.2.3 Моделирование работы в нестационарном режиме

3.3 Выводы по разделу

4 Методика выбора необходимой аппаратно-программной конфигурации распределенной системы мониторинга сети передачи данных

4.1 Требования к модели и средства моделирования

4.2 Алгоритм выбора необходимой аппаратно-программной конфигурации с использованием программного комплекса для параллельно-последовательной модели

4.3 Пример использования методики

4.3.1 Моделирование текущей нагрузки

4.3.2 Моделирование требуемой нагрузки

4.3.3 Моделирование с использованием вертикального масштабирования

4.3.4 Моделирование с использованием горизонтального и вертикального масштабирования

4.3.5 Выводы по результатам моделирования

4.4 Выводы по разделу

Заключение

Список литературы

Приложение 1 Программа численно-аналитического расчёта вероятностей состояний нестационарной ациклической сети обслуживания с конечным числом заявок

Приложение 2 Программа для имитационного моделирования процесса обслуживания заявок в нестационарной ациклической сети обслуживания с

конечным числом заявок

Приложение 3 Акты о внедрении

Приложение 4 Свидетельства о регистрации программ для ЭВМ

Введение диссертации (часть автореферата) на тему «Модели нестационарной параллельно-последовательной сети обслуживания на примере распределенной системы мониторинга»

Введение

Автоматизированные системы мониторинга играют важную роль в жизни современного общества. Мониторинг - непрерывный процесс сбора, агрегирования и анализа метрик для улучшения понимания характеристик и поведения компонентов системы. В этот пункт входит также визуализация собранных данных по метрикам в различные графики, диаграммы, гистограммы. В ряде отраслей данные мониторинга собираются и накапливаются очень интенсивно. Сложившиеся в настоящее время тенденции роста сетей передачи данных увеличивают требования к системам мониторинга этих сетей. При увеличении размеров сети увеличивается и количество составляющих её объектов, нуждающихся в мониторинге, что, в свою очередь, увеличивает нагрузку на систему мониторинга. Подобная ситуация влечет за собой замедленную реакцию на аварийные события, возникающие в сети, и ведет к деградации сетевых сервисов и служб [1]. Для предотвращения этих ситуаций необходим правильный подход к выбору системы мониторинга, ее архитектуре и дальнейшему обслуживанию и масштабированию.

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

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

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

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

Существуют модели СМО, которые учитывают поведение аппаратно-программного комплекса, функционирующего в условиях перегрузок на заданном

(директивном) временном интервале, они и представляют наибольший теоретический и практический интерес. Такие системы приобрели название нестационарных систем обслуживания (НСО). Начало «нестационарной» ТМО прослеживается в работах таких авторов, как Такач К., Прохоров Ю.В., Хинчин А.Я., Коваленко И.Н., Ежов И.Ч., Гнеденко Б.В. [3-8]. В работах Абольникова Л.М., Арсенишвили Г.Л. проведены исследования некоторых моделей ТМО, параметры которых зависят от состояния системы [9-10]. В работах Конолли Б. и Хидиди Н. рассмотрены отдельные характеристики однолинейных систем массового обслуживания с ординарным входящим потоком, интенсивность которого обратно пропорциональна величине очереди [11-12]. В дальнейшем появились работы авторов: Скляревича Ф.А., Greenberg H., Neuts M.F., Сиголова Г.Г., Люперсольского А.М., Leese E., Leguesdron P., Read R.R., Зефмана А.И., Syshi R., Головко Н.И. [13-19]. Эти работы рассчитывали и анализировали нестационарные вероятностные характеристики моделей ТМО с постоянными интенсивностями входящего потока и обслуживания с бесконечными или конечными накопителями. Под НСО понимается система обслуживания с переменными во времени вероятностями состояний. Каждое состояние такой системы описывается минимум двумя параметрами: числом заявок, которые находятся в системе, и числом заявок, которые уже обслужены системой. Число заявок, поступающих на обслуживание, должно быть конечно. Некоторые сложности, связанные с составлением и решением НСО были описаны в [20]. Нестационарным моделям систем массового обслуживания по сравнению со стационарными моделями массового обслуживания посвящено значительно меньше опубликованных работ [21-30].

Впервые базовая модель одноканальной НСО представлена в публикации [31]. В дальнейшем появились [32-33]. В дальнейшем модели НСО использовались для построения моделей надежности программных средств и планированию их испытаний.

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

модели были рассмотрены в работах Мусы, Литлвуда и Джелинского - Моранды. Описание этих и других моделей надежности программ приводится в [34-39]. Другие нетрадиционные методы оценки надежности информационных систем, использующие надежностный и вероятностный подход рассмотрены в [38].

Изначально модели НСО строились с использованием следующего подхода:

- определение параметров, описывающих состояния модели НСО;

- построение диаграммы переходов и состояний;

- запись уравнения Чепмена - Колмогорова для каждого состояния системы;

- вывод общего уравнения системы однородных дифференциальных уравнений Чепмена - Колмогорова;

- задание начальных условий для решения соответствующей им задачи Коши;

- использование методов численного решения типа Рунге - Кутта с заданным шагом интегрирования для решения системы однородных дифференциальных уравнений.

На основе результатов работ [39-48] был разработан комплекс программ [49] расчёта надежности и планирования испытаний программных средств, в котором системы однородных дифференциальных уравнений (ОДУ) для различных моделей нестационарных систем обслуживания решаются с помощью численных методов. Численные методы, однако, тоже имеют свои недостатки, вплоть до отрицательных значений рассчитанных вероятностей, что привело к разработке численно-аналитического метода расчета вероятностей состояний моделей НСО, предлагаемого в работах [50-51]. Однако и этот метод имеет свои минусы, например, долгое время заполнения и приведения к треугольному виду матрицы коэффициентов системы обыкновенных дифференциальных уравнений Чепмена-Колмогорова, связанное с необходимостью сортировать строки и столбцы внутри матрицы [52-53].

В рассмотренной выше литературе нет представления распределенной системы мониторинга в виде модели НСО. В рамках диссертационного исследования было принято решение:

1. разработать вероятностную нестационарную модель, описывающую распределенную систему мониторинга;

2. модифицировать численно-аналитический метод расчета вероятностей состояний моделей НСО для увеличения скорости его работы без потери в точности расчетов;

3. разработать программный комплекс для аналитико-имитационного моделирования разработанной модели НСО с учетом модификации численно-аналитического метода расчета;

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

Объектом диссертационного исследования является система мониторинга, позволяющая использовать распределенную архитектуру.

Предметом исследования в диссертационной работе являются вероятностные нестационарные модели систем обслуживания и методы их расчёта.

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

Для достижения поставленной цели были сформулированы и решены следующие задачи:

1) Разработка модели НСО, описывающей распределенную систему мониторинга.

2) Модификация численно-аналитического метода расчёта вероятностно-временных характеристик аналитических моделей нестационарных систем обслуживания с целью оптимизации времени выполнения расчетов.

3) Разработка рекурсивного с группировкой метода генерации матрицы коэффициентов для системы дифференциальных уравнений Чепмена-Колмогорова (модели нестационарных систем обслуживания (НСО)).

4) Разработка имитационной и аналитической моделей исследуемой системы мониторинга.

5) Программная реализация рассматриваемых моделей.

6) Разработка методики выбора оптимальной аппаратно-программной конфигурации распределенной системы мониторинга сети передачи данных с использованием разработанного программного комплекса моделей.

Научная новизна диссертационной работы заключается в следующем:

1) предложена параллельно-последовательная модель НСО с конечным числом заявок в источнике;

2) модифицирован и программно реализован численно-аналитический метод для расчёта вероятностно-временных характеристик НСО, увеличивающий скорость работы метода по сравнению с другими существующими методами при прежнем уровне точности;

3) разработан и реализован рекурсивный с группировкой метод генерации списка возможных состояний рассматриваемой НСО и матрицы коэффициентов для системы дифференциальных уравнений Чепмена-Колмогорова (модели НСО), позволяющий генерировать матрицу коэффициентов без вывода общего уравнения системы уравнений Чепмена-Колмогорова в готовом для дальнейших расчетов нижнетреугольном виде и не требующий ее сортировки;

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

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

Теоретическая значимость исследования выражается в дальнейшем развитии методов построения и расчёта моделей НСО.

Практическая значимость диссертационного исследования состоит в следующем:

1) использование модификации численно-аналитического метода с применением рекурсивного с группировкой алгоритма генерации списка состояний НСО и матрицы коэффициентов вместо рекурсивного метода для расчёта систем уравнений Чепмена-Колмогорова (модели НСО) повышает скорость расчёта вероятностно-временных характеристик НСО по сравнению с существующими методами без потери точности;

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

3) предложенные модели и методы реализованы в виде программного комплекса, состоящего из аналитической и имитационной моделей для расчёта вероятностно-временных характеристик НСО, учитывающей особенности распределенной архитектуры исследуемой системы мониторинга;

4) применение методики выбора оптимальной аппаратно-программной конфигурации распределенной системы мониторинга позволяет на разных этапах жизненного цикла системы решать различные задачи, на этапе проектирования -выбор аппаратно-программных характеристик для серверов в системе, на этапе эксплуатации - принятие решения о горизонтальном или вертикальном

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

Методы исследования. Работа выполнена на основе методов теории вероятностей, методов теории массового обслуживания (построение аналитических и имитационных моделей НСО), методов построения аналитических и имитационных моделей сложных систем. В качестве языка программирования использовался Python3, графическая среда разработки PyCharm.

Положения, выносимые на защиту:

1) аналитическая и имитационная параллельно-последовательные модели НСО;

2) модификация численно-аналитического метода для расчёта вероятностно временных характеристик НСО с использованием рекурсивного с группировкой алгоритма генерации списка возможных состояний НСО и формирования матрицы коэффициентов для системы уравнений Чепмена-Колмогорова (модели НСО);

3) программный комплекс аналитических и имитационных моделей для расчёта вероятностно-временных характеристик НСО, описывающих исследуемую систему мониторинга;

4) методика выбора необходимой аппаратно-программной конфигурации распределенной системы мониторинга сети передачи данных.

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

Внедрение результатов работы. Полученные научные результаты были внедрены и применены:

1. В СПИИРАН в ходе выполнения НИР «Шифр 0073-2019-0004» на тему «Методология и технологии интеграции существующих и перспективных государственных и коммерческих информационно-управляющих и телекоммуникационных систем и сетей на различных этапах их жизненного цикла», а именно:

а) комплекс аналитико-имитационных моделей сетей обслуживания, позволяющий моделировать «пиковые» перегрузочные ситуации на заданном директивном временном интервале для параллельно-последовательной модели системы мониторинга информационно-управляющих и телекоммуникационных систем и сетей включен в научно-методические материалы по описанию модельно-алгоритмического обеспечения совместного и раздельного проактивного мониторинга и управления созданием информационно-управляющих комплексов и телекоммуникационных систем и сетей в интересах эффективного развития системы распределенных ситуационных центров Российской Федерации;

б) Методика определения достаточности аппаратно-программных средств распределенной системы мониторинга Zabbix использовалась при обосновании технических решений по организации возможных сценариев интеграции государственных и коммерческих информационно-управляющих комплексов и телекоммуникационных систем и сетей в интересах эффективного развития системы распределенных ситуационных центров Российской Федерации.

Использование полученных результатов позволило:

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

б) оптимизировать время обработки метрик системой мониторинга на 30% посредством применения разработанного комплекса моделей, методик и рекомендаций.

2. В учебный процесс кафедры «Информационные и вычислительные системы» ПГУПС при проведении лекционных занятий и практических работ по дисциплинам «Моделирование информационных процессов на транспорте» и «Информатика и вычислительная техника», а именно:

1. нестационарная параллельно-последовательная модель высоконагруженной распределенной системы мониторинга сети передачи данных;

2. рекурсивный с группировкой алгоритм генерации списка состояний системы обслуживания и заполнения матрицы коэффициентов системы однородных дифференциальных уравнений Чепмена-Колмогорова;

3. программная реализация аналитической (Свидетельство о регистрации программы для ЭВМ 2020662856, 20.10.2020. Заявка № 2020662236 от 12.10.2020.) и имитационной (Свидетельство о регистрации программы для ЭВМ 2020663070, 22.10.2020. Заявка № 2020662212 от 12.10.2020) моделей высоконагруженной распределенной системы мониторинга сети передачи данных.

Исходный код программной реализации моделей представлен в Приложении 1 и Приложении 2. Акты об использовании и внедрении результатов работы представлены в Приложении 3. Свидетельства о регистрации программ для ЭВМ представлены в Приложении 4.

Апробация результатов. Материалы диссертации докладывались и обсуждались на заседаниях кафедры «Информационные и вычислительные системы» Петербургского государственного университета путей сообщения Императора Александра I (ПГУПС) в 2017-2021 гг., на конференциях: «Неделя науки» в ПГУПС в 2017 г.; 5 международная научно-методическая конференция «Проблемы математической и естественнонаучной подготовки в инженерном

образовании» на базе ПГУПС в 2018 году; международная конференция «Модели и методы исследования информационных систем» на базе ПГУПС в 2019 году; международная конференция «Модели и методы исследования информационных систем на транспорте» на базе ПГУПС в 2020 году; международная конференция «Технологии построения когнитивных транспортных систем» секция «Интеллектуальные транспортные системы. Транспортная безопасность» в 2021 году.

Публикации. Результаты по теме диссертации изложены в 13 публикациях, 4 из которых изданы в журналах, рекомендованных ВАК, 4 публикации индексированы базой SCOPUS, 2 свидетельства о регистрации программ для ЭВМ в ФИПС.

Личный вклад автора. Решение задач диссертации, разработка параллельно-последовательной модели НСО, оптимизация методов расчета -аналитической модели рассматриваемой системы, разработка рекурсивного с группировкой алгоритма генерации списка состояний и заполнения матрицы коэффициентов системы ОДУ Чепмена-Колмогорова, а также разработка программного комплекса для аналитического и имитационного моделирования систем, описываемых параллельно-последовательной моделью НСО.

1 ОБЪЕКТ, ЦЕЛЬ И ЗАДАЧИ ИССЛЕДОВАНИЯ 1.1 Основные компоненты системы мониторинга

Любая система мониторинга, в том числе система мониторинга сетевых устройств — это сложная информационная система, включающая в себя:

- метрики сетевых устройств (CPU, температура, доступность устройств, потери пакетов, ошибки на интерфейсах, доступная полоса пропускания и прочие) - критически важные параметры, за значениями которых необходимо вести постоянное наблюдение;

- мониторинг - процесс сбора, агрегирования и анализа метрик для улучшения понимания характеристик и поведения компонентов системы путем сравнения текущих значений с заданными критериями [54]. В этот пункт входит также визуализация собранных данных по метрикам в различные графики, диаграммы, гистограммы;

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

В контексте информационных систем, которыми и являются любые сети передачи данных, можно выделить два основных направления мониторинга:

1. Мониторинг инфраструктуры.

2. Мониторинг сервисов.

Можно выделить 2 основных типа мониторинга:

2. Агентный - клиентская часть системы мониторинга, так называемый «агент», устанавливается непосредственно на сервер, являющийся объектом мониторинга. Такой агент может самостоятельно собирать метрики и передавать их дальше в систему.

2. Безагентный - опросом метрик занимается сама система мониторинга, в основном используется для таких объектов мониторинга, на которые нельзя установить «агент», например, сетевые устройства, которые для мониторинга используют протокол Simple Network Management Protocol (SNMP).

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

1. Сбор метрик.

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

2. Хранение и анализ метрик.

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

3. Визуализация данных.

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

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

4. Автоматические действия и оповещения.

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

1) Высокий приоритет - критичные метрики, требующие незамедлительной реакции на оповещение.

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Шардаков Кирилл Сергеевич, 2021 год

СПИСОК ЛИТЕРАТУРЫ

1. Шардаков К. С. Сравнительный анализ популярных систем мониторинга сетевого оборудования, распространяемых по лицензии GPL / К. С. Шардаков // Интеллектуальные технологии на транспорте. - 2018. -№ 1. - С. 44-48.

2. Бубнов В. П. Обзор существующих моделей нестационарных систем обслуживания и методов их расчета / В. П. Бубнов, В. И. Сафонов, К. С. Шардаков // Системы управления, связи и безопасности. - 2020. - №3. -С.65-121. DOI: 10.24411/2410-9916-2020-10303.

3. Хинчин А. Я. Работы по математической теории массового обслуживания / А. Я. Хинчин. - М.: ФИЗМАТЛИТ, 1963. - 236 с.

4. Takacs К. Investigation of Waiting Time Problems by Reduction to Orkov processes / К. Takacs // Acta Mathematica Academiae Scientarium Hungaicae. - 1955. - Vol. 6. - P. 101-129.

5. Гнеденко Б. В. Введение в теорию массового обслуживания / Б. В. Гнеденко, И. Н. Коваленко. - М.: Наука, 1966. - 432 с.

6. Коваленко И. Н. О системе массового обслуживания со скоростью обслуживания, зависящей от числа требований в системе, и периодическим отключением каналов / И. Н. Коваленко // Проблемы передачи информации. - 1971. - № 2. - С. 108-114.

7. Коваленко И. Н. О восстановлении характеристик системы по наблюдениям над выходящим потоком / И. Н. Коваленко // Доклады Академии Наук СССР. - 1965. - № 5. - С. 979-981.

8. Ежов И. И. Распределение количества каналов системы ремонта, когда интенсивность потока изменяется специальным образом / И. И. Ежов, М. Т. Корнейчук, И. Д. Олийнык // Кибернетика. - 1976. - № 3. - С. 92-97.

9. Абольников Л. М. Нестационарная задача массового обслуживания для систем с бесконечным числом каналов при групповом поступлении

требований / Л. М. Абольников // Проблемы передачи информации. - 1968.

- № 3. - С. 99-102.

10. Арсенишвили Г. Л. Однолинейная система массового обслуживания с зависящей от величины очереди интенсивностью входящего потока / Г. Л. Арсенишвили // Сообщения Академии наук Грузинской ССР. - 1974.

- № 2. - С. 285-288.

11. Conolly В. W. Generalized State Dependent Eriangian Queues (speculation about calculating easure of effectiveness) / В. W. Conolly // Applied Probability.

- 1975. - № 2. - P. 358-363.

12. Hadidi N. A. A queueing model with variable arrival rates / N. A. Hadidi // Periodica Mathematica Hungarica. - 1975. - № 1. - P. 39-47.

13. Сиголов Г. Г. Метод расчета переходных процессов в сетевых моделях массового обслуживания / Г. Г. Сиголов, А. М. Люперсольский // Сборник тезисов всесоюзной школы-семинара по распределенным автоматизированным системам массового обслуживания (Рига, 15-20 октября 1988 г.). - 1988. - С. 353-354.

14. Сиголов Г. Г. Метод приближенного расчета переходных процессов в сетевых моделях массового обслуживания / Г. Г. Сиголов, А. М. Люперсольский // Автоматика и вычислительная техника. - 1990. -№ 3. - С. 40-43.

15. Скляревич Ф. А. Характеристика пребывания фрагмента вычислительной сети в фиксированном подмножестве состояний / Ф. А. Скляревич // Автоматика и вычислительная техника. - 1985. - № 2. - С. 14-20.

16. Головко Н. И. СМО с бесконечным накопителем и скачкообразной интенсивностью входного потока / Н. И. Головко, В. О. Каретник, А. В. Пелешок // Автоматика и телемеханика. - 2009. - № 10. - С. 75-96.

17. Зейфман А. И. О нестационарной модели Эрланга / А. И. Зейфман // Автоматика и телемеханика. - 2009. - № 12. - С.71-80.

18. Gelenbe E. Analysis and Synthesis of computer systems / E. Gelenbe, I. Mitrani.

- Academic Press, 1980. - 239 p.

19. Zeifman A. On stability for Mt/Mt/N/N queue / A. Zeifman, A. Korotysheva, Y. Satin // Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2010 International Congress (Moscow, 18-20 October 2010). - 2010. - P. 1102-1105. DOI: 10.1109/ICUMT.2010.5676515.

20. Шлепкин А. А. О нестационарных системах массового обслуживания / А. А. Шлепкин // Наука, техника и образование. - 2016. - №9. - С. 29-31.

21. Поршнев С. В. Математическое моделирование информационных контрольно-пропускных систем, обоснование выбора аппроксимации интенсивности поступления заявок / С. В. Поршнев, И. А. Корелин // Автоматизация. Современные технологии. - 2018. - № 7. - С.324-329.

22. Поршнев С. В. Исследование особенностей нестационарной одноканальной системы массового обслуживания в разрезе числа обслуженных заявок / С. В. Поршнев, И. А. Корелин // Cloud of Science. -2017. - № 3. - С.366-375.

23. Поршнев С. В. Исследование особенностей функционирования информационных контрольно-пропускных систем объектов проведения массовых мероприятий / С. В. Поршнев, Д. А. Якоб - Екатеринбург : Институт экономики УрО РАН, 2014. - 216 с.

24.Zeifman A. I. Ergodicity bounds for the markovian queue with time-varying transition intensities, batch arrivals and one queue skipping policy/ A. I. Zeifman, R. V. Razumchik, Y. A. Satin, I. A. Kovalev // Applied Mathematics and Computation. - 2021. - V.7. DOI:10.1016/j.amc.2020.125846.

25.Korolev V. Bounds for convergence rate in laws of large numbers for mixed poisson random sums / V. Korolev, A. Zeifman // Statistics & Probability Letters. - 2021. - V. 168. DOI: 10.1016/j.spl.2020.108918.

26. Zeifman A. Bounds on the rate of convergence for markovian queuing models with catastrophes / A. Zeifman // Statistics & Probability Letters. - 2021. - V. 176.

27. Ammar S. I. Transient behavior of a two-processor heterogeneous system with catastrophes, server failures and repairs / S. I. Ammar // Applied Mathematical Modelling. - 2014. - V. 38. - DOI: 10.1016/j.apm.2013.10.033.

28. Li J. MXMc Queue with catastrophes and state-dependent control at idle time / J. Li, L. Zhang // Frontiers of Mathematics in China. - 2017. - V. 12. - DOI: 10.1007/s 11464-017-0674-8.

29. Marin A. A Queueing Model that Works Only on the Biggest Jobs / A. Marin, S. Rossi - Lecture Notes in Computer Science book series. - 2020. - P. 118132. - DOI: 10.1007/978-3-030-44411-2_8.

30. Chakravarthy S. R. A catastrophic queueing model with delayed action / S. R. Chakravarthy // Applied Mathematical Modelling. - 2017. - V. 46. - P. 631-649. - DOI: 10.1016/j.apm.2017.01.089.

31. Бубнов В. П. О загрузке вычислительной системы с изменяющейся интенсивностью поступления заданий / В. П. Бубнов, В. И. Сафонов, В. А. Смагин // Автоматика и вычислительная техника. - 1987. - № 6. - С. 19-22.

32. Бубнов В. П. Алгоритм исследования модели нестационарных систем обслуживания / В. П. Бубнов, В. И. Сафонов // Сборник типовых алгоритмов и программ. - 1987. - № 8. - С. 172-178.

33. Бубнов В. П. Разработка динамических моделей нестационарных систем обслуживания / В. П. Бубнов, В. И. Сафонов. - СПб.: Издательство "Лань", 1999. - 64 c.

34. Darcy D. P. Object-Oriented Metrics in Practice / D. P. Darcy, C. F. Kemerer // Software. - 2005. - № 6. - P. 17-19.

35. Dick S. Software-Reliability Modeling: The Case for Deterministic Behavior / S. Dick, C. L. Bethel, A. Kandel // IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans. - 2007. - Vol. 37. - № 1. - P. 106119.

36. El-Emam K. Object-Oriented Metrics: A Review of Theory and Practice / K. El-Emam // Advances in software engineering. - 2002. - № 1. - P. 23-50.

37. El-Emam K. The prediction of faulty classes using object-oriented design metrics / K. El-Emam, W. Melo, J. C. Machado // Journal of Systems and Software. - 2001. - № 1. - P. 63-75.

38. Musa J. D. The Measurement and Management of Software Reliability / J. D. Musa // Proceedings of the IEEE. - 1980. - № 9. - P. 1131-1143.

39. Тырва А. В. Метод планирования тестирования сложных программных комплексов на этапах проектирования и разработки / А. В. Тырва, А. Д. Хомоненко // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - 2009. - № 4. - С. 125131.

40. Тырва А. В. Методика задания исходных данных для моделей надежности программных средств железнодорожного транспорта / А. В. Тырва // Известия Петербургского университета путей сообщения. - 2010. - № 2. -С. 250-261.

41. Тырва А. В. Методика сертификационных испытаний программного обеспечения системы «Горочная автоматическая централизация микропроцессорная с ведением накопления вагонов в сортировочном парке (ГАЦ МН) 86246294.50 5200 020-01 / А. В. Тырва. - СПб.: Петербургский государственный университет путей сообщения императора Александра I, 2009. - 18 c.

42.Bubnov V. P. Model of reliability of the software with Coxian distribution of length of intervals between the moments of detection of errors / V. P. Bubnov, A. V. Tyrva, A. D. Khomonenko // Proceedings of the 2010 IEEE 34th Annual Computer Software and Applications Conference (COMPSAC 2010). - Seoul, 2010. - P. 238-243. DOI: 10.1109/C0MPSAC.2010.78.

43.Bubnov V. P. Software Reliability Model with Coxian Distribution of Length of Intervals Between Errors Detection and Fixing Moments / V. P. Bubnov, A. V. Tyrva, A. D. Khomonenko // 2011 IEEE 35th Annual Computer Software and Applications Conference Workshops (COMPSACW 2011). - Munich, 2011. - 2011. - P. 310-314. DOI: 10.1109/C0MPSACW.2011.58.

44. Тырва А. В. Модели надежности программного обеспечения: учебное пособие / А. В. Тырва, А. Д. Хомоненко, В. П. Бубнов. - СПб.: ПГУПС, 2010. - 39 с.

45. Бубнов В. П. Нестационарная модель надежности программных средств с распределением Кокса длин интервалов времени исправления ошибок / В. П. Бубнов, А. В. Тырва, К. И. Бурцева // Вестник Всероссийского научно-исследовательского и проектно-конструкторского института электровозостроения. - 2010. - № 1. - С. 143-152.

46. Бубнов В. П. Комплекс моделей надежности программных средств с распределениями фазового типа / В. П. Бубнов // Вестник Всероссийского научно-исследовательского и проектно-конструкторского института электровозостроения. - 2011. - № 1. - С. 185-193.

47. Бубнов В. П. Комплекс моделей нестационарных систем обслуживания с распределениями фазового типа / В. П. Бубнов, А. В. Тырва, А. С. Еремин // Труды СПИИРАН. - 2014. - № 6. - С. 61-71.

48. Бубнов В. П. Обоснование стратегии отладки программ на основе нестационарной модели надежности / В. П. Бубнов, А. В. Тырва, А. Д. Хомоненко // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. - 2010. - № 2. - С. 85-92.

49. Свидетельство о государственной регистрации программ для ЭВМ № 2010615617 Российская Федерация. Комплекс программ расчета надежности и планирования испытаний программных средств / А. В. Тырва, А. Д. Хомоненко, В. П. Бубнов ; А. В. Тырва, А. Д. Хомоненко, В. П. Бубнов. - № 2010613695 ; дата государственной регистрации в реестре программ для ЭВМ 18.06.2010. - 1 с.

50. Бубнов В. П. Алгоритм аналитического расчета вероятностей состояний нестационарных систем обслуживания / В. П. Бубнов // Известия Петербургского университета путей сообщения. - 2011. - № 4. - С. 90-97.

51. Бубнов В. П. Особенности программной реализации численно-аналитического метода расчёта моделей нестационарных систем

обслуживания / В. П. Бубнов, А. С. Еремин, С. А. Сергеев // Труды СПИИРАН. - 2015. - № 1. - С. 218-232.

52. Шардаков К. С. Последовательный алгоритм генерации матрицы коэффициентов для системы однородных дифференциальных уравнений в модели нестационарной системы обслуживания / К. С. Шардаков // Интеллектуальные технологии на транспорте. - 2018. - № 4. - С. 20-25.

53. Shardakov K.S. Generating of the Coefficient Matrix of the System of Homogeneous Differential Equations / K. S. Shardakov, V. P. Bubnov, A. N. Pavlov // Workshop Computer Science and Engineering in the framework of the 5th International Scientific-Methodical Conference «Problems of Mathematical and Natural-Scientific Training in Engineering Education». -2018. - P. 42-47. - DOI: 10.24412/1613-0073-2341-42-47

54. Носкова А. И. Обзор автоматизированных систем мониторинга / А. И. Носкова, М. В. Токранова // Интеллектуальные технологии на транспорте. - 2017. - № 1. - С. 42-47

55. A Simple Network Management Protocol (SNMP), RFC - Текст : электронный // - 2021. - URL: https://datatracker.ietf.org/doc/html/rfc1157 (дата обращения: 11.02.2018).

56. Сетевая и серверная статистика с использованием Cacti - Текст : электронный // - 2021. - URL: https://nsrc.org/workshops/2014/caren-nsrc-dante/raw-attachment/wiki/Agenda/cacti-from-packages-vRU.pdf (дата обращения: 11.02.2018).

57. Документация Cacti - Текст : электронный // - 2021. - URL: https://www.cacti.net/documentation.php (дата обращения: 12.02.2018).

58. Анализ систем централизованного мониторинга с открытым исходным кодом мониторинга - Текст : электронный // - 2021. - URL: https://sites.google.com/site/teachingandresearchwork/sravnenie-sredstv-monitoringa (дата обращения: 12.02.2018).

59. Документация Nagios - Текст : электронный // - 2021. - URL: https://www.nagios.org/documentation/ (дата обращения: 12.02.2018).

60. Graphite - как построить миллион - Текст : электронный // - 2021. - URL: https: //events .yandex.ru/lib/talks/1122/

61. Документация Zabbix - Текст : электронный // - 2021. - URL: https://www.zabbix.com/documentation/3.4/manual (дата обращения: 12.02.2018).

62. Владышев А. Zabbix и миллионы метрик: наилучший опыт масштабного мониторинга - Текст : электронный // - 2021. - URL: http://www.highload.ru/2015/abstracts/1965.html (дата обращения: 13.02.2018).

63. Шардаков К. С. Бубнов В.П. Нестационарная параллельно-последовательная модель высоконагруженной системы мониторинга / К. С. Шардаков, В. П. Бубнов // Информация и космос. - 2020. - №3. -С.56-67

64. Shardakov K. S. Stochastic Model Of A High-Loaded Monitoring System Of Data Transmission Network / K. S. Shardakov, V. P. Bubnov // Proceedings of Models and Methods of Information Systems Research Workshop 2019. - 2020. - P. 29-34. DOI: 10.24412/1613-0073-2556-29-34

65. Свидетельство о государственной регистрации программы для ЭВМ № 2014662753 Российская Федерация. Программа для расчёта вероятностей состояний нестационарных систем обслуживания / С. А. Сергеев, В. В. Бубнов, А. С. Ерёмин ; С. А. Сергеев, В. В. Бубнов, А. С. Ерёмин. -№ 2014660760 ; дата поступления 21.10.2014 ; дата государственной регистрации в реестре программ для ЭВМ 08.12.2014. - 1 с.

66. Сергеев С. А. Нестационарные модели компонентов системы автоматизированного мониторинга технического состояния искусственных сооружений: дис. ... к.т.н.: 05.13.18. / С. А. Сергеев. - СПб, 2016. - 385 с.

67. Свидетельство о государственной регистрации программы для ЭВМ № 2015617625 Российская Федерация. Программный комплекс аналитико-имитационных моделей для расчёта вероятностно-временных характеристик нестационарных систем обслуживания / С. А. Сергеев,

В. П. Бубнов, В. В. Бубнов ; Общество с ограниченной ответственностью «Научно-технический центр инновационных космических технологий СПИИРАН» - № 2015614100 ; дата поступления 19.05.2015 ; дата государственной регистрации в реестре программ для ЭВМ 16.07.2015. - 1 с.

68. Свидетельство о государственной регистрации программы ЭВМ № 201561735 Российская Федерация. Программа для имитационного моделирования нестационарных систем обслуживания / С. А. Сергеев, В. П. Бубнов, В. В. Бубнов ; Общество с ограниченной ответственностью «Научно-технический центр инновационных космических технологий СПИИРАН» - № 2015614097 ; дата поступления 19.05.2015 ; дата государственной регистрации в реестре программ для ЭВМ 16.07.2015. - 1 с.

69. Бубнов В. П. Нестационарная сетевая модель управляющего аппаратно-программного комплекса / В. П. Бубнов, В. А. Ходаковский, С. А. Сергеев,

B. Г. Соловьева // Автоматика на транспорте. - 2018. - Том 4. - № 2. - С. 208-222.

70. Бубнов В. П. Рекурсивный метод генерации матрицы коэффициентов системы однородных дифференциальных уравнений, описывающих нестационарную систему обслуживания / В. П. Бубнов, А. Д. Хомоненко,

C. А. Сергеев // XVIII Международная конференция по мягким вычислениям и измерениям ^СМ-2015) (Санкт-Петербург, 19-21 мая 2015 г.). - СПб.:СПбГЭТУ «ЛЭТИ», - 2015. - С. 164-166.

71. Сергеев С. А. Метод составления систем однородных дифференциальных уравнений для расчёта вероятностно-временных характеристик нестационарных систем обслуживания / С. А. Сергеев // Интеллектуальные технологии на транспорте. - 2015. - № 2. - С. 32-42.

72. Бубнов В. П. Нестационарные модели локального сервера автоматизированной системы мониторинга искусственных сооружений /

В. П. Бубнов, С. А. Сергеев // Труды СПИИРАН. - 2016. - № 2. - С. 102115.

73. Decimal — Decimal fixed point and floating point arithmetic, Python3 Documentation - Текст : электронный // - 2021. - URL: https://docs.python.org/3/library/decimal.html (дата обращения: 01.03.2020).

74. Class BigDecimal, Java Documentation - Текст : электронный // - 2021. -URL: http: //docs.oracle. com/j avase/7/docs/api/j ava/math/BigDecimal .html (дата обращения: 01.03.2020).

75. Thread State and the Global Interpreter Lock, Python3 Documentation - Текст : электронный // - 2021. - URL: https://docs.python.org/3/c-api/init.html#thread-state-and-the-global-interpreter-lock (дата обращения: 15.04.2019).

76. Шардаков К. С. Особенности программной реализации численно-аналитической модели параллельно-последовательной нестационарной системы обслуживания / К. С. Шардаков // Интеллектуальные технологии на транспорте. - 2021. - № 2. - С. 33-44. - DOI: 10.24412/2413-2527-2021226-33-44.

77. Свидетельство о государственной регистрации программы для ЭВМ № 2020662856 Российская Федерация. Программа численно-аналитического расчёта вероятностей состояний нестационарной ациклической сети обслуживания с конечным числом заявок / К. С. Шардаков, В. П. Бубнов ; Федеральное государственное бюджетное образовательное учреждение высшего образования «Петербургский государственный университет путей сообщения Императора Александра I» (ФГБОУ ВО ПГУПС) - № 2020662236 ; дата поступления 12.10.2020 ; дата государственной регистрации в реестре программ для ЭВМ 20.10.2020. - 1 с.

78. Свидетельство о государственной регистрации программы для ЭВМ № 2020663070 Российская Федерация. Программа для имитационного моделирования процесса обслуживания заявок в нестационарной ациклической сети обслуживания с конечным числом заявок /

К. С. Шардаков, В. П. Бубнов ; Федеральное государственное бюджетное образовательное учреждение высшего образования «Петербургский государственный университет путей сообщения Императора Александра I» (ФГБОУ ВО ПГУПС) - № 2020662212 ; дата поступления 12.10.2020; дата государственной регистрации в реестре программ для ЭВМ 22.10.2020. - 1 с.

79. Shardakov K. S. Stochastic Modeling the operation of a distributed high-load monitoring system for a data transmission network in a non-stationary mode / K. S. Shardakov, V. P. Bubnov, S. V. Kornienko // Proceedings of Models and Methods of Information Systems Research Workshop 2020. - 2020. - P. 107116. DOI: 10.24412/1613-0073-2803-107-116

80. Shardakov K. S. Analysis of algorithms for generating the matrix of coefficients of non-stationary queuing system models / K. S. Shardakov, V. P. Bubnov// Proceedings of the Workshop "Intelligent Transport Systems and Transport Security 2021" on the basis of the Solomenko Institute of Transport Problems of the Russian Academy of Sciences and Emperor Alexander I St. Petersburg State Transport University. - 2021. - P. 42-49. DOI: 10.24412/1613-0073-2924-4249

81. Бубнов В. П. Сравнительный анализ рекурсивного и рекурсивного с группировкой алгоритмов генерации матрицы коэффициентов системы обыкновенных дифференциальных уравнений Чепмена-Колмогорова моделей нестационарных систем / В. П. Бубнов, К. С. Шардаков // Информация и космос. - 2021. - №3. - С. 47-55

82. Тырва А. В. Методика подготовки исходных данных для нестационарных моделей надежности и планирования испытаний программных средств / А. В. Тырва, В. П. Бубнов, К. С. Шардаков, Д. В. Бараусов // Системы управления, связи и безопасности. - 2021. - № 1. - С. 77-103. - DOI: 10.24411/2410-9916-2021-10104.

Приложение 1 Программа численно-аналитического расчёта вероятностей состояний нестационарной ациклической сети обслуживания с конечным

числом заявок

import random

import time

import numpy as np

from decimal import *

import matplotlib.pyplot as plt

num_of_proxies = 2 # amount of proxies for modeling getcontext().prec = 1000 # precision getcontext().rounding = ROUND_HALF_UP time_moment = Decimal(str(5)) # time moment

num_tasks = 3 # amount of task for modeling

time_spent = 0

lambda_lst = []

mu_lst = []

mu_main_lst = []

for i in range(num_tasks):

lambda_lst.append(Decimal(random.random())) mu_lst.append(Decimal(random.uniform(1, 2))) mu_main_lst.append(Decimal(random.uniform(1, 2)))

class State:

def _init_(self, number=0, in_progress=(0, 0, 0), served=(0,

0)): _ _

self.number = number

self.in_progress = list(in_progress) self.served = list(served)

def numbering(states): number = 0 for group in states:

for subgroup in group:

for under_subgroup in subgroup:

for key, state in under_subgroup.items(): state.number = number number += 1

return number

def structure_preparation():

# preparing subgroup structure for states keeps

# general list with states states = []

for group in range(num_tasks + 1): states.append([])

for subgroup in range(num_tasks + 1): states[group].append([]) for k in range(num_tasks + 1):

states[group][subgroup].append({})

return states

def recursive_generate_states(): start = time.time() states = structure_preparation() print("\nRECURSIVE GENERATING...")

# initial state when all parameters are equals to 0 initial_in_system = [0 for _ in range(num_of_proxies + 1)] zero_patient = State(in_progress=initial_in_system, served=[0,

0])

states[0][0][0],setdefault(tuple(initial_in_system), zero_patient)

def recursive(current_state): global time_spent

out_proxy, out_main = current_state.served """ Skip if all tasks already served """ if out_main == num_tasks: return

""" New task arriving in system (literally to one of proxies) """

if out_main + sum(current_state.in_progress) < num_tasks: for proxy in range(num_of_proxies): """ Copy from current state """

new_in_progress = list(current_state.in_progress) """ Add task to proxy """ new_in_progress[proxy] += 1

""" Skip new state if this state is already exists

in structure """

search_start_time = time.time() if

states[out_main][out_proxy][sum(new_in_progress)].get(tuple(new_in_p rogress)):

time_spent += time.time() - search_start_time continue

""" Add new state if not exists yet """ state = State(in_progress=new_in_progress, served=[out_proxy, out_main])

states[out_main][out_proxy][sum(new_in_progress)].setdefault(tuple(n ew_in_progress), state)

recursive(state)

""" Task served on proxy """ if sum(current_state.in_progress[:-1]) > 0: for proxy in range(num_of_proxies):

""" We can't serve task on proxy if proxy is empty currently, skipping... """

if current_state.in_progress[proxy] == 0:

continue """ Copy from current state """

new_in_progress = list(current_state.in_progress) new_served = list(current_state.served) """ Task leaves from proxy """ new_in_progress[proxy] -= 1 """ Task comes to main server """ new_in_progress[-1] += 1

""" Increase served on proxy counter """ new_served[0] += 1

""" Skip new state if this state is already exists

in structure """

search_start_time = time.time() if

states[new_served[1]][new_served[0]][sum(new_in_progress)].get(tuple (new_in_progress)):

time_spent += time.time() - search_start_time continue

""" Add new state if not exists yet """ state = State(in_progress=new_in_progress, served=list(new_served))

states[new_served[1]][new_served[0]][sum(new_in_progress)].setdefaul t(tuple(new_in_progress), state)

recursive(state)

""" Task served on main server """ if current_state.in_progress[-1] > 0: """ Copy from current state """

new_in_progress = list(current_state.in_progress) new_served = list(current_state.served) """ Task served on main server """ new_in_progress[-1] -= 1

""" Increase served on main server counter """ new_served[1] += 1

""" Skip new state if this state is already exists in structure """

search_start_time = time.time() if

states[new_served[1]][new_served[0]][sum(new_in_progress)].get(tuple (new_in_progress)):

time_spent += time.time() - search_start_time return

""" Add new state if not exists yet """ state = State(in_progress=new_in_progress, served=list(new_served))

states[new_served[1]][new_served[0]][sum(new_in_progress)].setdefaul t(tuple(new_in_progress), state) recursive(state)

""" Start recursive generation """ recursive(zero_patient)

print("recursive time: ", time.time() - start) num_states = numbering(states) print("recursive states: ", num_states) return states, num states

def print_states(states): for group in states:

print("Group: ", states.index(group), "length: ",

group._len_())

for subgroup in group:

print("\tSubgroup: ", group.index(subgroup), "length: ",

subgroup._len_())

for under_subgroup in subgroup: print("\t\tUnder subgroup: ", subgroup.index(under_subgroup), "length: ",

under_subgroup._len_())

for key, state in under_subgroup.items():

print("\t\t\t", state.number, state.in_progress,

state.served)

print("Amount of states: ", num_states)

def new_fill_matrix_a(states, num_states): global time_spent

""" Code block below is modifying matrix A with correct values.

This code is parsing states list one by one state and

modifying matrix A on the run for each state ii ii ii

matrix_A = np.zeros((num_states, num_states), Decimal) # matrix A filled by ZEROs

for group in states:

group_index = states.index(group) for subgroup in group:

subgroup_index = group.index(subgroup) for under_subgroup in subgroup: under_subgroup_index = subgroup.index(under_subgroup)

for key, state in under subgroup.items():

Task arrived, transition FROM the state

ii II II

if under subgroup index < num tasks -

group index:

Always there are few possible transitions FROM the state due to we have few channels,

task can arrive to any of proxies ii ii ii

for i in range(num_of_proxies):

matrix_A[state.number][state.number] lambda lst[under subgroup index]

Task arrived, transition TO the state

OR

Task served on the proxies, transition FROM the

state

if subgroup_index < num_tasks:

if under subgroup. len () > 1:

previous under subgroup

next subgroup

We can transit TO current state from

OR

We can transit FROM current state to the

IF

There is non empty proxies currently.

For arriving tasks. Transition TO the

state

one by one per loop """

for i in range(num_of_proxies):

temp_key = list(state.in_progress) """ Decrease value for each proxy

temp_key[i] -= 1

""" Skip if no tasks in proxy """ if temp_key[i] < 0: continue

""" Modify matrix A if there is the

state in previous under_subgroup current state

from which we can transit to

search_start_time = time.time() if subgroup[under_subgroup_index -

1].get(tuple(temp_key)):

from_state_number = subgroup[under_subgroup_index - 1].get(tuple(temp_key)).number

time_spent += time.time() -

search start time

matrix_A[state.number][from_state_number] += lambda lst[under subgroup index - 1]

h H H

FROM the state

For served on proxies tasks. Transition

for i in range(num_of_proxies):

temp_key = list(state.in_progress) """ Decrease value for each proxy

one by one per loop """

temp_key[i] -= 1 if temp_key[i] < 0: continue

""" Increase value in main server since task is served and moved to main server """

temp_key[-1] += 1

""" Modify matrix A if there is the

state in the next subgroup

to which we can transit from

current state

!! !! !!

search_start_time = time.time() if group[subgroup_index + 1][under_subgroup_index].get(tuple(temp_key)):

time_spent += time.time() -

search_start_time

matrix A[state.number][state.number] -= mu lst[subgroup index]

state

the state

Task served on the proxies, transition TO the OR

Task served on the main server, transition FROM

if subgroup_index > group_index: !! !! !!

For served on proxies tasks. Transition TO

the state

for i in range(num_of_proxies):

temp_key = list(state.in_progress)

""" Increase value for each proxy one by

one per loop """

temp_key[i] += 1

""" Decrease value in main server since task was served and moved to main server """

temp_key[-1] -= 1

""" Modify matrix A if there is the

state in previous subgroup

from which we can transit to current

state

!! !! !!

search_start_time = time.time if group[subgroup index -

1][under_subgroup_index].get(tuple(temp_key)):

from_state_number = group[subgroup_index - 1][under_subgroup_index]\

.get(tuple(temp_key)).number time_spent += time.time() -

search_start_time

matrix_A[state.number][from_state_number] += mu_lst[subgroup_index -1]

For served on the main server tasks.

Transition FROM the state

ii ii ii

temp_key = list(state.in_progress) """ Decrease value in main server since task is served and moved to main server """

temp_key[-1] -= 1

""" Modify matrix A if there is the state in

the next group

to which we can transit from current

state

ii II II

search_start_time = time.time() if states[group_index + 1][subgroup_index][under_subgroup_index - 1].get(tuple(temp_key)):

time_spent += time.time() -

search_start_time

matrix_A[state.number][state.number] -=

mu main lst[group index]

Task served on the main server, transition TO

the state

ii II II

if group_index > 0:

if subgroup_index >= group_index:

""" For served on main server tasks.

Transition TO the state """

temp_key = list(state.in_progress) """ Increase value in main server since task is served and moved to main server """

temp_key[-1] += 1

""" Modify matrix A if there is the

state in previous group

from which we can transit to current

state

ii II II

search_start_time = time.time() if states[group_index -1][subgroup_index][under_subgroup_index + 1].get(tuple(temp_key)):

from_state_number = states[group index - 1][subgroup index][under subgroup index + 1]\

.get(tuple(temp_key)).number time_spent += time.time() -

search_start_time

matrix_A[state.number][from_state_number] += mu_main_lst[group_index - 1]

return matrix A

def fill_multiplicities():

This function is implementing filling multiplicities vector. Every multiplicity is vector that contains 4 entries.

1) Eigenvalue;

2) Multiplicity of this eigenvalue for all previous equations;

3) Index of previous multiplicity if current multiplicity > 1, else it is == -1;

4) Index of next multiplicity for current if it exist,else it is """

multiplicities = [[matrix_A[0][0], 1, -1, -1]] # list of multiplicities

for i in range(1, num_states):

for j in reversed(range(len(multiplicities))): if multiplicities[j][0] == matrix_A[i][i]: multiplicities.append([matrix_A[i][i], multiplicities[j][1] + 1, j, -1])

multiplicities[j][3] = i break

if i == len(multiplicities):

multiplicities.append([matrix_A[i][i], 1, -1, -1]) return multiplicities

def calc_coefficients():

# Block for calculation vector b for i in range(1, num_states): equation = 0 while equation < i:

b[equation] = Decimal("0")

for column in range(equation, i):

if matrix_A[i][column] != 0 and coefficients[column][equation] != 0:

b[equation] += matrix_A[i][column] * coefficients[column][equation]

''' It takes more time then simple loop b[equation] = sum(matrix_A[i][equation:i] *

coefficients[equation:i][:, equation])

'''

equation += 1

# Now we have to calculate coefficients matrix equation = 0

while equation <= i:

# In case those own numbers is equal, it means they are multiple or it is the same number on diagonal

if matrix_A[i][i] == matrix_A[equation][equation]:

# In case equation own number has few multiplicities in PREVIOUS equations

if multiplicities[equation][1] > 1:

# Set value "column" as the index of previous

multiple number

column = multiplicities[equation][2] coefficients[i][equation] = b[column] / multiplicities[column][1]

# It needs in case it first or single

multiplicity

else:

need_to_finish = equation

# In case those own numbers is NOT equal, it means tey are NOT multiple

else:

# In case this equation own number has no multiplicities in NEXT equations

if multiplicities[equation][3] == -1 and b[equation]

!= 0:

coefficients[i][equation] = b[equation] / (matrix_A[equation][equation] - matrix_A[i][i]) equation += 1

# And last step, now we have to finish calculation if we have flag "need_to_finish"

if need_to_finish != -1:

for column in reversed(range(i)):

# In case those own numbers is is not equal but "column" has multiplicities in next equations

if matrix_A[i][i] != matrix_A[column][column] and multiplicities[column][3] != -1:

coefficients[i][column] = (b[column] -

(coefficients[i][multiplicities[column][3]] *

multiplicities[column][1])) / \

(matrix_A[column][column] - matrix_A[i][i])

coefficients[i][need_to_finish] = P0[i] for column in range(i):

if multiplicities[column][1] == 1 and need_to_finish

!= column:

coefficients[i][need_to_finish] -= coefficients[i][column]

need to finish = -1

def calc_probabilities(time_moment):

This function is implementing probabilities calculations """

probabilities = [] current_state = 0

while current_state < num_states:

if multiplicities[current_state][1] == 1:

# b[] here to keep middle already calculated values b[current_state] =

matrix_A[current_state][current_state] * time_moment b[current_state] = b[current_state].exp() j = multiplicities[current_state][3]

# only if we have multiplies in next equations while j != -1:

b[j] = b[multiplicities[j][2]] * time_moment j = multiplicities[j][3] current_state += 1

for i in range(num_states): probability = 0

for j in range(len(coefficients)): if coefficients[i][j] != 0:

probability += coefficients[i][j] * b[j]

probabilities.append(probability) return probabilities

def is_lower_triangular(matrix_a): for i in range(len(matrix_a)):

for j in range(i + 1, len(matrix_a)): if matrix_a[i][j] != 0: return False

return True

if __name__ == "__main__":

start_time = time.time()

states, num_states = recursive_generate_states() matrix_A = new_fill_matrix_a(states, num_states)

print("\n--- Matrix A generation time %s seconds ---" %

(time.time() - start_time))

print("Matrix A is lower triangular: ", is_lower_triangular(matrix_A))

multiplicities = fill_multiplicities()

b = np.zeros(num_states, Decimal) # vector with some type of coefficients

coefficients = np.zeros((num_states, num_states), Decimal) P0 = np.zeros((num_states), Decimal) # vector of start probability

P0[0] = Decimal("1") # First state is 1 as point of start calc,other states are ZEROS

coefficients[0][0] = P0[0] calc_coefficients()

probabilities = calc_probabilities(time_moment)

print("\nProbabilities per state:") count = 0

for each in probabilities:

print("#%s: " % count, each) count += 1

print_states(states)

for i in range(len(probabilities)):

if probabilities[i] < Decimal("0"):

print("CRITICAL! Probability ", i, " < 0 : ", probabilities[i])

if probabilities[i] > Decimal("1"):

print("CRITICAL! Probability ", i, " > 1 : ", probabilities[i])

print("\n--- Whole time of execution %s seconds ---" %

(time.time() - start_time))

print("\nSum of probabilities = ", sum(probabilities)) print("\nDecimal rounding type == ", getcontext().rounding)

""" Plot of probabilities """