Проекты

Вероятностный анализ регенеративных и гауссовских коммуникационных систем с использованием методов высокопроизводительных вычислений

2011-2013 г.г.
рук. Морозов Е.В.
тема НИР, N 60

В 2011 г. продолжен анализ устойчивости системы с повторными вызовами, с конечным буфером и постоянной скоростью возвращения блокированных заявок с орбиты в систему. (Достаточные условия устойчивости такой системы были найдены в 2010.) В систему поступает входной поток восстановления, времена обслуживания на приборах имеют общее распределение, а интенсивность возвращения заявок в систему не зависит от числа блокированных заявок на орбите. Такая система хорошо моделирует работу телефонных линий, протоколов множественного доступа ALOHA, протокола TCP с короткими сообщениями. В частности, было показано, что условия стационарности такой системы включают первые моменты заданных случайных величин, а также стационарную вероятность потери в некоторой (более простой для анализа) системе с потерями. Имитационные исследования, проведенные в 2011 г., подтвердили, что найденные условия на самом деле являются критерием устойчивости для ряда систем с повторными вызовами, в частности, для системы без буфера с распределением Парето времени обслуживания. На основе обобщенной формулы Литтла выведены предельные соотношения для вероятности блокировки, как в стационарном, так и в нестационарном режиме (когда орбита неограниченно растет). Доказано, что в области стационарности вероятность блокировки может быть надежно оценена на основе классической регенерации, а в области нестационарности – на основе так называемой квази-регенерации. Исследованы свойства различных статистических оценок вероятности блокировки, включая эффект уменьшения дисперсии.

В 2011 г. предложена модель вычислительного кластера на основе модифицированной рекурсии Кифера-Вольфовица для многосерверной системы G/G/s, в которую поступают заявки, каждая из которых требует случайное число обслуживающих устройств с идентичным временем обслуживания на всех этих устройствах. Такая модель гораздо труднее для анализа, чем классические модели ввиду идентичности времен обслуживания. Исследованы моментные свойства компонент (векторного) процесса загрузки в том числе, в случае, когда время обслуживания имеет тяжелый хвост. Имитационный эксперимент, проведенный на модели, показал хорошее согласие с данными о реальной работой кластера в течение года.

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

В 2011 г. предложен метод параллельного оценивания вероятностей редких событий в системах обслуживания с адаптацией к числу свободных ресурсов (кластера). Предложенный метод является модификацией разработанного ранее метода ускоренного регенеративного имитационного моделирования (УРИМ) вероятностей перегрузок в системах обслуживания. Моделирование траектории наблюдаемого случайного процесса по циклам регенерации с расщеплением на заданных уровнях дает возможность «распараллелить» вычисления оценки искомой вероятности. Регенеративный подход (так же как для метода УРИМ) позволяет обосновать состоятельность и асимптотическую нормальность получаемых оценок. После расщепления каждая траектория вычисляется в своем потоке (либо на отдельном процессоре). Число расщеплений на каждом уровне не превышает число возможных потоков (свободных процессоров) — системные ограничения. В зависимости от выбора реализации метода, должны быть учтены ограничения, введенные администратором вычислительной системы (кластера).
Последние изменения: 16 февраля 2012