Стохастическое моделирование, анализ и оценивание характеристик информационно-вычислительных и телекоммуникационных систем

Целью работы является развитие и применение прикладных вероятностных методов к исследованию широкого класса стохастических моделей современных информационно-вычислительных и телекоммуникационных систем. Такие системы обладают особыми свойствами: большим числом (неоднородных) обслуживающих устройств, особыми (неконсервативными) дисциплинами обслуживания, значительным масштабом и высокой скоростью, а также случайным характером и сложной структурой зависимости описывающих такие системы процессов. Указанные особенности в значительной степени мотивированы приложениями в области исследования производительности и качества обслуживания в современных вычислительных (параллельных, распределенных, квантовых) и телекоммуникационных (беспроводных, оптических, мобильных) системах. Вероятностная динамика таких систем очень сложна и требует развития как марковских, так и немарковских моделей и специальных методов анализа их стационарности, а также получения ключевых характеристик в стационарном и переходном режимах. В рамках данной темы основными методами такого анализа являются регенеративный и матрично-аналитический методы, метод стохастического сравнения и метод каплинга. В отсутствии аналитического решения предполагается развитие и применение вероятностно-статистических методов, в частности, методов дискретно-событийного моделирования и регенеративного оценивания, понижения дисперсии оценки, а также асимптотических методов анализа, включая гауссовскую аппроксимацию и оценивание вероятности большого уклонения процесса очереди. Кроме того, в рамках исследования предполагается построение и исследование моделей и алгоритмов работы ключевых компонент современных вычислительных систем. Таким образом, исследование направлено на развитие взаимосвязанных разделов прикладной математики в областях стохастического моделирования, прикладного вероятностного анализа, теории массового обслуживания и дискретной математики, теоретической информатики, математического и программного обеспечения вычислительных систем, комплексов и компьютерных сетей. В рамках предлагаемой тематики планируется выполнить построение и анализ стохастических моделей широкого класса современных информационно-вычислительных и телекоммуникационных систем. Ключевыми особенностями таких систем является значительный масштаб и высокая степень параллелизма (большое число вычислительных узлов, процессоров, узлов сети передачи данных в параллельных вычислительных системах), высокая степень неоднородности (существенно различная скорость и надежность узлов/серверов в системах распределенных вычислений), высокие требования к качеству обслуживания при одновременных ограничениях на среднюю потребляемую мощность, используемую память, ограниченную емкость хранения (в системах малого масштаба, таких как узлы сети интернета вещей), использование новых принципов (беспроводная передача данных, оптические среды и оптическая буферизация, квантовые вычисления). Математически указанные системы, как правило, исследуются с помощью особых классов вероятностных моделей, таких как системы параллельной обработки, системы с повторными вызовами, системы обслуживания/запасания; системы с несколькими очередями; для таких классов в наиболее общем случае даже установление условий стационарности является сложной математической проблемой. Модели систем параллельной обработки используются для анализа современных суперкомпьютеров (вычислительных кластеров), систем распределенных вычислений (типа Desktop Grid), систем облачных вычислений. Системы с повторными вызовами используются для описания широкого класса систем мобильной связи, современных оптических систем передачи данных, отдельных компонент распределенных вычислительных систем. Системы со многими очередями применяются для исследования систем со многими классами клиентов; при этом отдельное направление исследования представляют модели, в которых распределение времени обслуживания представлено смесью распределений. Исследование таких моделей, как правило, ведется методами прикладной теории вероятностей и имитационного моделирования, однако значительную сложность в анализе указанных моделей представляет неконсервативность (отсутствие свойства сохранения работы) классических дисциплин обслуживания. Это приводит к необходимости использования сложной математической техники, либо требует применения имитационного моделирования. Кроме того, большой масштаб указанных систем затрудняет анализ с помощью марковских моделей, в том числе в связи с вычислительными сложностями. В рамках исследования указанных систем, как правило, первой важной задачей является нахождение условий стационарности (существования стационарного распределения вероятностей состояний) рассматриваемой модели. Однако данная задача является отдельной сложной проблемой для предлагаемых к исследованию моделей, в связи с особыми свойствами (неконсервативность, наличие нескольких очередей) и сложной структурой зависимостей исследуемых процессов. Решение данной проблемы предполагается осуществлять с помощью развития регенеративного и матрично-аналитического методов, а также методов статистического анализа. Для анализа ключевых характеристик производительности (в стационарном/переходном режимах), как правило, применяют аналитические методы (методы анализа цепей Маркова), а также оценивание с помощью имитационного моделирования. В первом случае трудности заключаются в большом масштабе исследуемых систем, а во втором - в необходимости построения надежных оценок. Для преодоления этих трудностей в рамках темы предполагается развитие матрично-аналитического и альтернативных подходов к анализу структурированных цепей Маркова, а в случае имитационного моделирования - активное использование регенеративного оценивания с применением методов повышения точности оценки. Для систем большого масштаба предполагается применять методы оценивания вероятностей редких событий и асимптотические методы. Таким образом, решение указанных актуальных задач требует разработки и развития современных методов, моделей, алгоритмов и программных систем для анализа как отдельных аспектов, так и больших комплексов современных информационно-вычислительных и телекоммуникационных систем. Для достижения указанной цели предполагается решение ряда взаимосвязанных задач. Применение регенеративного подхода, а также исследование возможностей применения неклассической регенерации (искусственная регенерация, регенеративные огибающие) к анализу стационарности и получению базовых стационарных характеристик многоклассовых систем, систем со многими неограниченными очередями/орбитами; значительное внимание в этой связи планируется уделять системам с повторными вызовами. В условиях, когда получение аналитических результатов затруднено, предполагается применять и развивать методы статистического исследования стационарности с использованием имитационного моделирования. Применение и развитие матрично-аналитического метода и альтернативных методов анализа структурированных цепей Маркова, а также специальных методов теории очередей для аналитического и численного исследования ключевых характеристик производительности и энергоэффективности многоресурсных систем обслуживания (в том числе систем с многосерверными клиентами), а также систем с изменяемой скоростью обслуживания. Особое внимание предполагается уделить анализу моделей, в которых управляющие последовательности обладают так называемым тяжелым хвостом (что является характерным признаком нагрузки современных вычислительных систем и систем хранения). Для анализа таких моделей предполагается развивать асимптотические методы, а также метод регенеративного имитационного моделирования, позволяющий гарантировать заданную точность оценивания. Кроме того, в ряде случаев планируется применять метод точного моделирования (perfect simulation) для получения оценок требуемого, но неизвестного распределения, описывающего стационарный режим работы модели. Развитие подходов, основанных на технике каплинга и стохастических сравнениях, в том числе с использованием конечных смесей распределений (в системах со сложными входными потоками данных, идущих от разнородных пользователей), использование так называемой искусственной регенерации (основанной на расщеплении переходных вероятностей описывающей модель марковской цепи), для исследования стохастической упорядоченности в классе систем параллельной обработки и получения оценок для ключевых показателей производительности, в том числе с использованием результатов для классических систем. Развитие методов исследования систем в переходном режиме, в том числе исследование скорости сходимости к стационарному режиму, что является особенно важным для анализа энергоэффективности автономных вычислительных систем с ограниченным запасом энергии. В контексте исследования вычислительных и телекоммуникационных систем большого масштаба, предполагается развитие асимптотических методов анализа, а также исследования важных эффектов (таких, как долговременная зависимость), влияющих на эффективность оценивания характеристик качества обслуживания, в допредельных режимах. Кроме того, предполагается обобщить ряд важных результатов известных для классических систем обслуживания с ожиданием на широкий класс систем с повторными вызовами, включая гауссовскую аппроксимацию в случае классической дисциплины повторов и построение границ для (логарифма) вероятности большой величины орбиты. Разработка и исследование математических и имитационных моделей и алгоритмов работы ключевых компонент параллельных, распределенных вычислительных систем. Исследование взаимовлияния указанных технологий, в том числе гибридных (квантово-классических) алгоритмов с точки зрения сходимости, вероятности получения требуемого решения, использования методов повышения надежности и скорости получения результатов, эффективности универсальных квантовых вычислителей.