Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

ДИСКРЕТНО-СОБЫТИЙНОЕ МОДЕЛИРОВАНИЕ СЕТЕВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ В УСЛОВИЯХ ВЫСОКИХ НАГРУЗОК

Чубейко С.В. 1
1 ФГБОУ ВПО «Ростовский государственный университет путей сообщения»
Статья посвящена аспектам дискретно-событийного моделирования сетевых компьютерных систем. Отличительной особенностью предлагаемого подхода является принятие во внимание условий высоких нагрузок функционирования сетевых компьютерных систем. В статье выделяются наиболее существенные характеристики сетевых компьютерных систем, которыми являются синхронизация событий и конкуренция за вычислительные ресурсы. Определены отличия предлагаемого подхода от двух известных подходов математического моделирования: методов теории автоматического управления и методов теории сетей и систем массового обслуживания. Рассмотрено идемпотентное (max,+) полукольцо, которое является основной алгебраической структурой, применяемой в рассматриваемом подходе к дискретно-событийному моделированию. Указаны основные алгебраические свойства (max,+) полукольца, именуемого также диоидом. Рассмотрен пример дискретно-событийного моделирования функционирования автоматизированных рабочих мест автоматизированной системы управления контейнерными перевозками на железнодорожном транспорте, функционирующей в условиях высоких нагрузок. Приведены числовые результаты дискретно-событийного моделирования рассматриваемой сетевой компьютерной системы.
дискретно-событийное моделирование
идемпотентное (max
+) полукольцо
диоид
1. Бражник А.Н. Имитационное моделирование: возможности GPSS WORLD. – СПб..: Реноме, 2006. – 439 с.
2. Бутакова М.А. Имитационное моделирование процессов возникновения ошибок для оценки надежности программного обеспечения / М.А. Бутакова, С.В. Чубейко // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки. – 2012. – № 5 (168). – C. 29–34.
3. Глухов М.М., Елизаров В.П., Нечаева А.А. Алгебра. Т. 2. – М.: Гелиос АРВ. – 2003. – 416 с.
4. Гуда А.Н. Прогнозирование надежности программного обеспечения на основе модели неоднородного пуассоновского процесса и бутстреп-методов / А.Н. Гуда, С.В. Чубейко // Программные продукты и системы. – 2012. – № 3. – С. 131–135.
5. Котов В.Е. Сети Петри. – М.: Наука, 1984. – 160 с.
6. Маслов В.П. Идемпотентный анализ и его применение в оптимальном управлении / В.П. Маслов, В.Н. Колокольцов. – М.: ФИЗМАТЛИТ. – 1994. – 144 с.
7. Таха Х.А. Введение в исследование операций: пер. с англ. – 7-е изд. – М.: Издательский дом «Вильямс», 2005. – 912 с.
8. Чубейко С.В. Алгоритмы и программное обеспечение для имитационного моделирования сетевых систем на основе (min,+) фильтраций // Современные проблемы науки и образования. – 2013. – № 6; URL: http://www.science-education.ru/113-11545 (дата обращения: 13.01.2014).
9. Baccelli F. Synchronization and linearity: An algebra for discrete event systems / F. Baccelli, Cohen G., G.J. Olsder, J.-P. Quadrat. – Chichester: Wiley, 1992. – 514 p.
10. Cassandras C.G., Lafortune S. Introduction to Discrete Event Systems. Second Edition. – Springer, 2008. – 782 p.
11. Gondran M. Graphs, Dioids and Semirings. New Models and Algorithms / Gondran M., Minoux M. – Springer Science+Business Media, LLC. – 2008. – 384 p.
12. Heidergott B. Max Plus at Work. Modeling and Analysis of Synchronized Systems: A course on Max-Plus Algebra and Its Applications / B. Heidergott, G. Jan Olsder, J. van der Woude. – Princeton University Press, Princeton. – 2006. – 232 p.
13. Wainer G.A. Discrete Event Modeling and Simulation: A Practitioner’s Approach // CRC Press, 2009. – 486 p.

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

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

Заметим следующее: и в общей теории систем, и в теории систем и сетей массового обслуживания неявно предполагается использование процессного времени. Это означает, что в первом случае принимается, что процессы в системах протекают по возможности мгновенно (хотя в некоторых случаях допустима их инерционность), а во втором случае принимается, что процессы подчинены некоторому вероятностному закону. Однако во втором случае иногда рассматривают потоки general (общего) типа, в которых основным соотношением является рекуррентное уравнение Линдли [7], что по сути близко к рассматриваемому нами далее подходу с идейной стороны, но не со стороны реализации методов моделирования. В целом процессное время означает, что изменение состояний системы, а также её модели можно отметить на некоторой временной шкале, если шкала является непрерывной, то естественным будет непрерывное моделирование состояний системы, иначе – дискретное моделирование состояний системы, а также соответствующий им математический аппарат.

В основу дискретно-событийного моделирования, развиваемого появления известной системы GPSS [1] и сетей Петри [5] положена другая концепция: состояния системы изменяются под воздействием некоторых событий, в общем случае безотносительно их точной привязки к временной шкале. Существенными являются лишь факты наличия возникновения этих событий и взаимодействие их между собой, то есть синхронизация (некоторое событие предшествует другому, некоторое событие вызывает возникновение другого, либо других событий и так далее). Для сетевых компьютерных систем как многопользовательских многозадачных, многомашинных, многопроцессорных систем характерным является еще один аспект событийности – конкуренция за сетевые распределенные вычислительные ресурсы, с целью увеличения производительности, минимизации простоев и тому подобное. Оба этих аспекта – синхронизация и конкуренция – делают сетевые компьютерные системы существенно нелинейными, что усложняет их аналитическое и имитационное моделирование, а рассматриваемый далее в работе подход можно рассматривать как возможную линеаризацию таких систем.

В итоге введения к статье следует заметить, что научные исследования в области дискретно-событийного моделирования сейчас достаточно широко развиты в различных направлениях [13, 10], а также служат как существенное дополнение методов имитационного моделирования систем. Существуют также программные реализации дискретно-событийных систем моделирования, например AnyLogic, SimPy, SimEvents и другие. Однако в рамках данной статьи нас интересует вполне самостоятельное направление дискретно-событийного моделирования с применением алгебраических структур (max,+) подхода [9], который, на наш взгляд, адекватно отражает поставленную в названии статьи проблему – моделирование высоконагруженных сетевых компьютерных систем.

Применение метода (max,+) алгебры в дискретно-событийном моделировании

Основной структурой в рассматриваемом подходе является (max,+) полукольцо [9], являющееся числовым множеством (с элементами из множества ¡, включая –∞ и не включая +∞ ), снабженным операциями «максимума», играющего роль «сложения» и «сложения», играющего роль «умножения». Указанные операции (max,+) в специализированной литературе [9, 6] обозначаются соответственно ⊕ и ⊗ (то есть имеют другое значение в отличие от общепринятых – прямой суммы и прямого произведения матриц), то есть x⊕y = max{x, y}, x⊗y = x + y. Данное (mах,+) полукольцо является идемпотентным [6], то есть сложение a⊕a = a является идемпотентным, нулем считается ε = –∞, единицей, считается e = 0, которая нейтральна по операции ⊗, а для каждого ненулевого элемента по этой операции имеется обратный элемент. Для обеих операций выполняется коммутативность и ассоциативность, а операция ⊗ дистрибутивна относительно ⊕. Такая алгебраическая структура часто называется диоидом [11]. Аналогичный подход с использованием (min,+) алгебраических структур рассмотрен в работе автора [8].

Данные свойства указанной алгебраической структуры оказываются существенно полезными для дискретно-событийного моделирования сетевых компьютерных систем с точки зрения оценки и достижения их максимальной производительности. Рассмотрим простой пример дискретно-событийного моделирования автоматизированной системы управления контейнерными перевозками (АСУ КП) на железнодорожном транспорте. В моделируемой системе имеются автоматизированные рабочие места (АРМ) работников АСУ КП на двух железнодорожных станциях:

1) узловой станции Ростов-Товарная;

2) припортовой станции Новороссийск.

Посредством единой сети передачи данных ОАО «РЖД» АРМы АСУ КП работают в сетевом режиме и между ними передается информация, сопутствующая технологическому процессу обработки документов. Будем рассматривать 4 события (конечно, в существенно упрощенной форме), соответствующие работе оператора АРМ АСУ КП:

1) подготовка пакета исходной документации с телеграмм-натурным листом поезда;

2) ввод и передача информации в сетевом режиме АРМ АСУ КП на первой станции;

3) прием и распечатка входящей документации с телеграмм-натурным листом поезда;

4) подтверждение и корректировка принятых данных в АРМ АСУ КП на второй станции.

Естественным образом устанавливается порядок синхронизации событий, так, например, подтверждение и корректировка данных могут произойти не ранее, чем данные вообще будут получены, а подготовка документации может происходить не ранее прибытия поезда с контейнерами. Для того, чтобы не ограничиваться одним направлением и подчиняться общим принципам моделирования систем на рисунке показаны технологические процессы с АРМ АСУ КП на станциях и названы в целом «подготовкой данных». Различное время технологических операций на станциях, а также приема и передачи в разных направлениях может быть обусловлено различной производительностью АРМов, различным опытом операторов и другими аналогичными причинами. Приемы моделирования различных событий, связанных с интенсивной нагрузкой информационных систем и программного обеспечения, рассматривались ранее в работах автора [2, 4].

Для дальнейшей определенности и конкретных расчетов положим, что время подготовки документации на железнодорожные платформы с контейнерами в АРМ АСУ КП занимает у оператора xA = 3 минуты; ввод данных на каждый вагон формируемого поезда из 60 вагонов на станции Ростов-Товарная составляет yBA = 12 минут при отправке телеграмм-натурного листа на станцию Новороссийск. Время, затрачиваемое на формирование принятого на припортовой станции Новороссийск телеграмм-натурного листа контейнерного поезда, составляет xB = 2 минуты, а время, затрачиваемое на согласование корректировок со станцией Ростов-на-Дону и внесение их в АРМ АСУ КП на станции Новороссийск, составляет yBA = 10 минут.

pic_31.wmf

Графическая иллюстрация упрощенного технологического процесса контейнерной перевозки между станциями StA и StB

Поставим цели моделирования, состоящие в нахождении максимальных нагрузок на сетевые компьютерные АРМы АСУ КП при выполнении следующих ограничений:

1) нормативы времени на технологические операции, выполняемые операторами АРМ АСУ КП на станциях, являются максимально допустимыми;

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

3) интенсивность обработки документаций в АРМах должна учитывать максимальную производительность контейнерных перевозок, а следовательно, и максимально возможное количество поездов, курсирующих на участке между StA и StB.

Смоделируем времена tA отправления пакетов с телеграмм-натурными листами поездной документации со станции StA. Пусть для начального условия tA(0) = 0, а, учитывая заданные ранее значения времени подготовки, ввода, обработки и корректировки данных, следует, что очередной пакет поездных документов отправится не ранее, чем будет сформирован, то есть

chubey01.wmf (1)

а очередной прибывший пакет поездных документов будет обработан не ранее, чем будут переданы предыдущие корректировки на станцию StA со станции StB:

chubey02.wmf (2)

где tB(0) – начальный момент времени отправления корректировок со станции StB, который можно принять tB(0) = 0, Δ – некоторая временная задержка в технологических процессах на транспорте. Выражения (1) и (2) можно записать в более общем виде:

chubey03.wmf (3)

chubey04.wmf (4)

Приняв Δ = 0 и подставив значения из примера из (3) и (4), получим, что максимальная задержка отправления составит

chubey05.wmf (5)

а для станции StB аналогично (1)–(4)

chubey06.wmf (6)

Так же как и в работе [12], для k = 0, 1, 2, ... по (5) и (6) рассчитаем последовательность tA = {0, 10, 22, 32, ...} и tB = {0, 12, 22, 34, ...}.

Заметим, что выражения (3)–(4) и соответствующие им выражения (5)–(6) с подставленными в них максимальными значениями временных интервалов xA, xB, yAB, yBA можно переписать в общем виде следующим образом.

Пусть имеется n станций ti, t = 1, ..., n, а времена, необходимые на технологические операции по перемещению контейнерной документации между i-й и j-й станциями, обозначим zij, тогда (5) и (6) имеет вид

chubey07.wmf (7)

Выражение (7) можно сравнить с выражением для линейной рекуррентной последовательности [3] следующим образом:

chubey08.wmf (8)

chubey09.wmf (9)

В (9) применим метод (max, +)-алгебры, а для того, чтобы подчеркнуть дальнейшую возможность использования методов линейной алгебры в (max, +)-алгебре, выражение (9) запишем как

chubey10.wmf (10)

Также, по аналогии с линейной алгеброй, выражение (10) можно записать в матричном виде:

chubey11.wmf (11)

где e – (max, +) – операции; Z – матрица, содержащая коэффициенты преобразований.

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

chubey12.wmf chubey13.wmf

таким образом,

chubey14.wmf

Далее, принимая во внимание, что

chubey15.wmf

и так далее.

Заключение

Дискретно-событийное моделирование с использованием (max,+) подхода является достаточно эффективной технологией моделирования систем с синхронизацией событий, Эта технология является пригодной для моделирования сетевых компьютерных систем, в частности АРМов и АСУ, применяемых на железнодорожном транспорте для определения режимов их функционирования в условиях максимальных нагрузок.

Работа выполнена при финансовой поддержке РФФИ, проекты 13-01-00325-а, 13-01-00637-а.

Рецензенты:

Павлов И.В., д.ф.-м.н., профессор, заведующий кафедрой высшей математики Ростовского государственного строительного университета, г. Ростов-на-Дону;

Чернов А.В., д.т.н., профессор, заведующий кафедрой прикладной математики и вычислительной техники Ростовского государственного строительного университета, г. Ростов-на-Дону.

Работа поступила в редакцию 21.05.2014.


Библиографическая ссылка

Чубейко С.В. ДИСКРЕТНО-СОБЫТИЙНОЕ МОДЕЛИРОВАНИЕ СЕТЕВЫХ КОМПЬЮТЕРНЫХ СИСТЕМ В УСЛОВИЯХ ВЫСОКИХ НАГРУЗОК // Фундаментальные исследования. – 2014. – № 8-2. – С. 340-344;
URL: https://fundamental-research.ru/ru/article/view?id=34556 (дата обращения: 28.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674