ОБ ИССЛЕДОВАНИЯХ В 2004-2005 ПО ГРАНТУ 04-07-90115
Руководитель:
Морозов Е.В. - д.ф-м.н., профессор,Институт прикладных математических
исследований Карельского научного центра РАН, г. Петрозаводск;
Рыков В.В. - д.ф-м.н., профессор, Российский Государственный
университет нефти и газа им. И.М. Губкина, г.Москва;
Пешкова И.В. - к.ф-м.н., преподаватель, Петрозаводский государственный
университет, г. Петрозаводск;
Белый А.В. - преподаватель, Петрозаводский государственный
университет, г. Петрозаводск;
Боденов Д.В. - аспирант, Петрозаводский государственный университет,
г. Петрозаводск;
Бородина А.В. - младший научный сотрудник, Институт прикладных
математических исследований Карельского научного центра РАН, г. Петрозаводск;
Жуков А.В. - преподаватель, Петрозаводский государственный
университет, г. Петрозаводск;
За 2004 г. метод слабой регенерации распространен на процессы,
описывающие многоканальные системы обслуживания, а также ациклическую коммуникационную
сеть (сеть типа Джексона) с марковской маршрутизацией заявок между узлами, произвольным
распределением интервалов входного потока, а также произвольными распределениями
времен обслуживания заявок в узлах. В отличие от известных работ рассматриваются
многоканальные узлы с неидентичными каналами, а входной поток является (положительно
возвратным) регенерирующим процессом. Кроме того, условие сильной регенерации
(полного освобождения сети от заявок) заменяется на условие слабой регенерации,
при котором, вообще говоря, возможно лишь пересечение сети заявкой без ожидания
в очередях. Для описанного класса сетей найдены условия положительной возвратности
многомерного процесса незавершенной нагрузки в сети. Доказательства данных условий
опираются на характеризацию асимптотического поведения незавершенного времени
между моментами регенерации и теорию однозависимых процессов.
Проведены имитационные экперименты по проверке эффективности метода слабой
регенерации, квази-регенерации и так называемого метода А-циклов при доверительном
оценивании времени прохождения завкой 2-х узловой тандемной сети и 3-х узловой
древовидной сети. Метод слабой регенерации является обобщением классического
случая, допускающим некоторую зависимость между соседними циклами регенерации.
Ранее (в исследованиях поддержанных грантом РФФИ 01-07-90259) было доказано,
что метод слабой регенерации имеет значительные преимущества по сравнению с
классическим регенеративным подходом при оценивании на основе имитационного
моделирования характеристик загруженных сетей (или сетей со значительным числом
узлов). Однако недостатком этого подхода в реальном моделировании является необходимость
учета неслучайных барьеров в конструкции обновляющих событий, лежащих в основе
процедуры идентификации моментов слабой регенерации. С точки зрения алгоритмической
реализации эти барьеры должны разделять заявки, проходящие сеть без столкновения
с другими заявками (такие события и порождают моменты слабой регенерации). Наличие
барьеров значительно усложняет упомянутые алгоритмы идентификации при усложнении
топологии сети. Для преодоления этого недостатка в работах авторов проекта был
предложен метод квази-регенерации, позволяющий учесть все заявки, пересекающие
сеть без конфликтов, в рамках одного типа (квази)регенерации. Однако такое обобщение
приводит к появлению зависимости между произвольным числом циклов регенерации
и ставит вопрос о правомерности применения центральной предельной теоремы (при
доверительном оценивании). В результате исследований установлена принципиальная
возможность обоснования метода квази-регенерации (связанная с наличием вложенного
процесса слабой регенерации).
Метод А-циклов в его оригинальной трактовке не связан с регенеративным подходом
и является аппроксимационным. Суть метода состоит в том, что наблюдаемые данные
разбиваются на циклы по моментам попадания значений процесса в некоторое ограниченное
(компактное) множество А. Частота таких моментов зависит от выбора множества
А. При статистическом оценивании полученные циклы принимаются независимыми и
к их обработке применяются методы классической статистики. Такое сильное допущение
(независимость) оставляет открытым вопрос о корректности метода и достоверности
получаемых статистических выводов. В то же время, попытки его обоснования оправдываются
простотой реализации и возможностью получения высокой частоты А-циклов. Как
показывает проведенный авторами проекта теоретический анализ, данный метод может
получить полноценное обоснование в рамках регенеративного метода, что позволит
обоснованно его использовать при доверительном оценивании характеристик сетевых
процессов. На данном этапе исследований было проведено сравнение скорости доверительного
оценивания (при заданной надежности и точности) для всех трех упомянутых методов
(слабой, квази-регенерации и А-циклов), а также их сравнение с результатами,
полученными на основе классической регенерации. Как и следовало из теоретических
соображений, метод А-циклов во многих случаях обладает заметным преимуществом
(в упомянутом выше смысле) в сравнении с другими методами, однако является чувствительным
к выбору множества А. Перспективным представляется использование данного метода
при наличии так называемых распределений с тяжелым хвостом (например, распределение
Парето), характерных для трафиков современных коммуникационных сетей.
В 2004 г. были начаты исследования по применению регенеративного имитационного
моделирования для оценки среднего времени прохождения тандемной сети в условиях,
когда случайный процесс времени ожидания заявки в узлах является процессом с
долговременной зависимостью. Имитационное моделирование во-первых, подтвердило
свойство долговременной зависимости процесса времени ожидания на первом узле
при некоторых моментных условиях на время обслуживания и входной поток (что
было теоретически предсказано профессором D.Daley) и во-вторых, показало, что
это свойство сохраняется и для процесса ожидания в последющих узлах тандемной
сети (рассматривалась 3 -х узловая сеть). Получена высокая эффективность доверительного
оценивания на основе классической регенерации такого процесса для некоторого
диапазона значений коэффициентов траффика в узлах. Отметим, что известные ранее
модели процессов с долговременной зависимостью исключали их статистическое исследование
с помощью регенеративного подхода.
Проведен анализ имеющихся средств обработки IP-пакетов в операционной системе
Linux и установлена принципиальная возможность диагностики сетевых процессов
с использованием регенеративного подхода, основанного на А-циклах.
Установлена важная взаимосвязь между нестационарными пуассоновскими потоками
(НПП) и распределениями с почти отсутствующей памятью (ПОП-распределениями).
Такая взаимосвязь не только дает новые знания о поведении НПП, но и позволяет
эффективно использовать ее при статистическом анализе. Поскольку для потоков
информации, поступающей и обрабатываемой в телекоммуникационных и компьютерных
сетях, характерно наличие существенной периодичности, полученные результаты
имеют большое значение при моделировании и анализе загрузки телекоммуникационных
и компьютерных сетей. Для статистического анализа ПОП распределений в реальных
сетях разработаны вычислительные процедуры и компьютерные средства, которые
позволяют оценивать параметры распределений и проверять гипотезы относительно
ПОП-распределений.
Были продолжены начатые ранее (при поддержке гранта РФФИ 01-07-90259) исследования
управляемых многолинейных систем с неоднородными приборами относительно критериев
минимизации средних задержек и стоимости обслуживания. Модель имеет разнообразные
применения, в том числе для решения вопроса о маршрутизации сообщений в сетях
связи. Показано, что оптимальная политика управления такими системами требует
использования наиболее быстрого (экономичного) канала, а включение каналов носит
пороговый по длине очереди характер. Полученные ранее для марковского случая
результаты обобщены на случаи сложных потоков (например, MAP потоков) и распределений
фазового типа. Численные результаты, полученные с помощью разработанного авторами
программного средства, показали значительную устойчивость оптимальных политик
управления к изменениям структуры входящих потоков и длительностей обслуживания.
По результатам исследований подготовлена кандидатская диссертация.
Также продолжены исследования в области надежности сложных иерархических систем.
Разработана модель сложной иерархической системы с различными режимами восстановления.
Получены алгоритмы вычисления стационарных и нестационарных характеристик надежности
таких систем при различных режимах восстановления. Предложена новая модель управления
надежностью подсистемы в системе с контролируемыми отказами, а также разработаны
алгоритмы и программные средства построения оптимальных стратегий управления
такими системами. Продолжается разработка программного продукта анализа надежности
сложных иерархических систем.
В течение 2005 г. регенеративный метод успешно применен для
нахождения условий стационарности 2-х узловой тандемной сети с непрямым контролем
доступа следующего вида: когда очередь во втором узле превышает некоторый заданный
уровень, первый узел перестает принимать заявки внешнего входного потока восстановления.
Необходимо найти условия стационарности (неперегрузки) первого узла. Эта модель
может найти приложения к анализу коммуникационных сетей в условиях, когда не
вся необходимая информация о состоянии некоторого узла непосредственно доступна
по наблюдениям за данным узлом и решение о его блокировке принимается по косвенной
информации о состоянии другого/других узлов. Найдены необходимые условия стационарности
первого узла в предположении, что описывающий сеть процесс является классическим
регенерирующим. Для некоторого соотношения между интенсивностями обслуживания
в узлах найдены также достаточные условия. Достаточные условия сформулированы
и для общего случая, однако, их доказательство частично использует эвристические
соображения. Используемая при доказательстве техника теории восстановления опирается
на свойство вложенного процесса моментов регенерации и позволяет получить достаточные
условия, близкие к необходимым. Как еще раз показывают полученные результаты,
применяемый подход (основанный на асимптотических свойствах незавершенного времени
восстановления) обладает определенным преимуществом по сравнению с известными
методами доказательства устойчивости/стационарности, использующими пробные функции
(функции Ляпунова). Эти преимущества состоят как в относительной простоте доказательства,
так и в возможности получать минимальные условия стационарности. Кроме того,
сформулированы (и доказаны лишь в части необходимости) условия стационарности
К-узловой тандемной сети, где превышение некоторого заданного уровня величиной
очереди К-го узла вызывает блокировку входного потока в 1-й узел (по аналогии
с 2-х узловой сетью). В процессе анализа было использовано новое свойство монотонности
процесса загрузки относительно величины интервалов входного потока.
В 2005 году было предложено теоретическое обоснование различных подходов в
рамках регенеративного метода (сильная, слабая, квази-регенерация, метод А-циклов)
в терминах обобщенных полумарковских процессов. Эти подходы, в частности, определение
групп зависимости путем присвоения конечного идентификатора, позволяют применять
более эффективные алгоритмы обнаружения моментов квази - регенерации и моментов
начала А-циклов в некоторых регенеративных сетях обслуживания. Полученные результаты
позволяют сформулировать новые задачи для анализа систем обслуживания, в том
числе для узлов коммутации и маршрутизации пакетов данных в реальных локальных
сетях.
Дальнейшее развитие получили исследования с помощью имитационного моделирования
вопроса о сохранении свойства долговременной зависимости процесса текущей нагрузки
в тандемной сети при определенных моментных условиях на интервалы входного потока
в первый узел и времена обслуживания во всех узлах сети. В 2004 г. это свойство
(теоретически предсказанное значительно ранее) было подтверждено авторами проекта
с помощью регенеративного имитационного моделирования процесса незавершенной
нагрузки в изолированном узле обслуживания. В текущем периоде моделирование
распространено на тандемные сети с большим числом узлов (до 10-ти), а также
проведено доверительное оценивание стационарного времени прохождения заявкой
сети на основе регенеративного имитационного моделирования, использующего не
классическую, а квази-регенерацию (существенно упрощающую алгоритмическую реализацию
метода). При этом в качестве распределения времени обслуживания используется
распределение Парето (обладающее так называемым тяжелым хвостом). Начато исследование
также древовидной сети, где в последующие узлы поступает входной поток, являющийся
результатом «расщепления» выходного потока из предшествующего узла. Имитационный
анализ подтвердил сохранение свойства долговременной зависимости процесса нагрузки
во всех последующих узлах (при всех рассмотренных конфигурациях сети) при тех
же моментных ограничениях на время обслуживания, что и в первом узле. Теоретическое
доказательство этого экспериментального факта является одним из важных пунктов
дальнейшего исследования. (Основная проблема связана с построением соответствующего
случайного блуждания в условиях, когда входной поток уже не является процессом
восстановления.)
На основе регенеративного метода также найдены условия стационарности многосерверной
системы обслуживания с зависимостью между входным потоком, временем обслуживания
и величиной незавершенной нагрузки. Более точно, в момент прихода каждой заявки
в систему считаются заданными условные распределения времени до прихода следующей
заявки и времени ее обслуживания в зависимости как от величины времени ее ожидания
в очереди так и номера сервера, на котором она будет обслуживаться. Анализ такой
сложной системы оказался возможным за счет использования известного рекурсивного
соотношения Линдли, задающего марковским образом последовательность значений
вектора компонент незавершенной нагрузки (на серверах системы). Использование
многократно упомянутого выше асимптотического свойства незавершенного времени
восстановления (совместно со свойством регенерации) позволило получить минимальные
достаточные условия стационарности, близкие к необходимым. Свойство «минимальности»
установлено путем сравнения полученных условий с известным критерием стационарности
классической многоканальной системы с идентичными каналами обслуживания, входным
потоком восстановления и независимыми временами обслуживания.
Проведено исследование проблемы качества функционирования клиент-серверных
систем, а именно, проблемы перегрузки серверов, на которых установлены подобные
системы. Авторами проекта предлагается методика, которая основана на присвоении
всем заданиям одного класса, поступающим на сервер, фиксированного приоритета.
Разработана вероятностная оптимизационная модель, позволяющая увеличить число
обслуженных запросов в соответствии с их приоритетами. На основе данной модели
разработан алгоритм управления качеством обслуживания.
С дальнейшей перспективой применения к анализу локальных коммуникационных сетей
начаты исследования по эффективному имитационному моделированию и построению
состоятельных оценок вероятностей редких событий в некоторых системах обслуживания
на основе комбинации регенеративного метода с некоторыми специальными методами
ускоренного моделирования (Splitting, RESTART). Особое внимание уделено так
называемым распределениям времени обслуживания с тяжелым хвостом (в первую очередь,
распределению Парето, характерному для трафика телекоммуникационных сетей),
когда аналитическое нахождение стационарного распределения с помощью известного
уравнения Такача в принципе невозможно (из-за расходимости соответствующего
преобразования Лапласа). В качестве альтернативы используется недавно найденная
(асимптотически точная для больших уровней нагрузки) аппроксимация на основе
рекурсивного соотношения Линдли.
Разработана диалоговая компьютерная программа анализа надежности сложной иерархической
сети. Программа содержит диалоговую процедуру построения сети пользователем
в рамках заданной модели, оснащение ее исходными данными и вычисление стационарных
характеристик надежности. Программа также позволяет производить как одноразовые
оценки характеристик надежности, так и серией вычислений исследовать зависимость
характеристик от изменения различных исходных параметров модели. Таким образом,
предложенное средство позволяет выявлять слабые (в смысле надежности) места,
и, путем изменения структуры и параметров модели, предлагать различные допустимые
варианты ее структуры и параметров. В настоящее время программный комплекс проходит
всестороннюю проверку и готовится к использованию в ИНТЕРНЕТ сети путем его
размещения на сайте Лаборатории No 10 ИППИ РАН.
В области исследования информационных потоков в инфо-теле-коммуникационных
сетях сетях было продолжено изучение нестационарных пуассоновских потоков и
потоков марковского типа. В частности, на основе предыдущих исследований о взаимосвязи
между периодическими пуассоновскими потоками и распределениями с почти отсутствующей
памятью с помощью разработанного ранее программного обеспечения проведены исследования
по различению гипотез между различными типами нестационарных пуассоновских процессов.
В настоящее время проводится подготовка программного комплекса к широкому использованию
через средства сети ИНТЕРНЕТ.
В последнее время информационные потоки марковского типа привлекают широкое
внимание научной общественности. Установлено, что подобные потоки обладают долговременной
зависимостью и в некоторых случаях сильно влияют на выходные характеристики
модели. Однако анализу собственных статистических свойств подобных потоков и,
в частности, разработке процедур оценки их параметров и проверке соответствующих
гипотез до последнего времени уделялось недостаточно много внимания. Поэтому
в рамках данного проекта большое внимание было уделено разработке процедур статистического
оценивания параметров потоков марковского типа. Известно, что возможности и
процедуры статистического оценивания параметров модели сильно зависят от доступной
наблюдению информации. В проводимом исследовании предполагается, что доступным
наблюдению является лишь число событий потока за фиксированный интервал времени.
Именно такая информация обычно соответствует реальных наблюдениях. В качестве
метода оценивания использовался метод моментов, на основании которого разработаны
процедура и компьютерная программа статистического оценивания параметров марковского
потока сообщений. С помощью метода имитационного моделирования проведен масштабный
статистический эксперимент по оцениванию параметров, который показал статистическую
неустойчивость метода и выявил значительные трудности оценивания параметров
таких потоков в случае, если вспомогательная компонента имеет большое число
состояний.
Результаты проводимых исследований получили признание как среди российских
исследователей, так и среди зарубежных коллег.
Важность полученных по теме результатов в определенной мере выражается и в том,
что руководитель проекта участвовал в международной научной программе по математическим
перспективам развития теории очередей и теории телетрафика (1 сентября - 8 октября,
2004, Институт Миттаг-Леффлера, Стокгольм), где проблематика исследований по
теме проекта занимала одно из важных мест. Исследования по теме проекта (в частности,
метод слабой регенерации) составили основу интенсивного курса, прочитанного
преподавателям и аспирантам математического факультета университета Наварры
(Испания), июнь 2004 г.
Исполнители проекта поддерживают тесные научные контакты с ведущими специалистами
в области регенеративного моделирования, анализа управляемых систем обслуживания,
теории надежности. Результаты исследований докладывались на ряде международных
и российских конференций, в частности, на 6-й международной Петрозаводской конференции
"Вероятностные методы дискретной математики", июнь 2004, на ежегодной
конференции "Finnish Data Processing Week at the University of Petrozavodsk",
июнь 2004, на XXIV международном семинаре "Stability problems for stochastic
models" в Риге, сентябрь 2004, а также в институте Миттаг-Леффлера (сентябрь
2004), в университетах de Marne- la-Valee (Франция, май 2004), Наварры (Испания,
июнь 2004), Сарагосы (Испания, июнь 2004), на международной конференции "Reliability
Model for Biological Objects, Longevity, Aging and Degradation Models"
(Санкт-Петербург, июнь 2004), на международной конференции "MMR-2004"
(Санта Фе, США, июнь 2004). Руководитель проекта был приглашен в программный
комитет 5-го международного семинара по статистическому моделированию, организованного
Санкт-Петербургским университетом (июнь 2005 г.), в котором принимали активное
участие и другие авторы проекта. Кроме того, участники проекта были приглашены
на 25-й международный семинар «Stability problems for stochastic models»(Салерно,
Италия, сентябрь 2005). Также руководитель проекта прочитал интенсивный курс
лекций по математическому моделированию коммуникационных сетей на факультете
Computer Sciences Университета Куопио (Финляндия, февраль 2005), и на математическом
факультете университета Сарагосы (Испания, июнь 2005), а также выступил с научными
докладами в университетах гг. Пизы (Италия), Мадрида, Памплоны и Барселоны (Испания),
и в исследовательском центре INRIA (Франция), май-июнь 2005, где результаты
исследований по теме проекта (в частности, метод квази-регенерации) занимали
важное место. Кроме того, результаты исследований докладывались на ежегодном
семинаре "Finnish Data Processing Week at the University of Petrozavodsk",
май 2005 и на международном семинаре “Optimal stopping and stochastic control”,
август 2005, Петрозаводск.