ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В РАМКАХ ПРОЕКТА,
ПОДДЕРЖАННОГО ГРАНТОМ РФФИ 01-07-90259 в 2001-2003 гг.
« Разработка методов и инструментальных средств анализа устойчивости и оценки
характеристик производительности элементов телекоммуникационных сетей (на примере
Петрозаводского государственного университета)»
Рыков В.В. - д.ф-м.н., профессор, Российский Государственный
университет нефти и газа им. И.М. Губкина, г.Москва;
Морозов Е.В. - д.ф-м.н., профессор,Институт прикладных математических
исследований Карельского научного центра РАН, г. Петрозаводск;
Богоявленский Ю.А. - к.т.н., доцент, Петрозаводский государственный
университет, г. Петрозаводск;
Аминова И.В. - к.ф-м.н., преподаватель, Петрозаводский государственный
университет, г. Петрозаводск;
Белый А.В. - преподаватель, Петрозаводский государственный
университет, г. Петрозаводск;
Ефросинин Д.В. - аспирант, Российский университет дружбы народов,
г. Москва;
Жуков А.В. - преподаватель, Петрозаводский государственный
университет, г. Петрозаводск;
Проект направлен на развитие методов предпроектного анализа устойчивости и
оценки характеристик телекоммуникационных сетей на основе регенеративного моделирования
и теории фрактальных процессов. В процессе реализации проекта создан определенный
задел (опирающийся на алгоритмическую и программную базу) для включения регенеративного
метода как важного и эффективного метода анализа состояния телекоммуникационной
сети. Известные до настоящего времени применения регенеративного метода к анализу
сетевых процессов основаны на методе сильной регенерации и используют в качестве
точек регенерации моменты полного опустошения сети. В современных коммуникационных
сетях такие моменты или полностью отсутствуют, или слишком редки, чтобы быть
полезными при статистическом анализе в реальном режиме времени.
Проведенные исследования впервые показывают принципиально новые возможности
регенеративного подхода (в его более общей форме слабой регенерации) для надежного
статистического анализа сетевых процессов. При этом данный подход позволяет
использовать аналоги классических процедур статистического оценивания, опираясь
на центральную предельную теорему для слабо-зависимых случайных величин. Надо
отметить, что алгоритмы идентификации моментов регенерации базируются на модифицированном
методе обновляющих событий, разработанном академиком РАН А.А.Боровковым. Детальное
описание метода классической и слабой регенерации можно найти в работах [2,3,8].
Проблема управления сетевыми ресурсами является одной из важнейших задач исследования
сетей. В рамках настоящего проекта исследовались оптимальная стратегия выбора
неоднородных заявок на обслуживание из очереди и стратегия занятия неоднородных
приборов с целью оптимизации заданных показателей производительности и эффективности
функционирования сети.
Другим направлением исследований управления в текоммуникационных сетях является
проблема маршрутизации. В проекте предложен подход к решению этой проблемы в
рамках задачи обслуживания заявок в узле с неоднородными приборами. При этом
приборы можно рассматривать, как каналы связи с различной пропускной способностью
и стоимостью. Задача состоит в построении оптимальной дисциплины обслуживания
заявок. В простейших предположениях задача сводится к управляемому марковскому
процессу. Задача оптимального управления обслуживанием требований в системе
с двумя неоднородными приборами была решена Лином и Куммаром в 1984, и обобщена
в последних работах В.В. Рыкова. Однако дальнейшее продвижение требовало численного
анализа, что и составило одну из основных задач, решаемых в рамках данного проекта.
Проведенные исследования позволили сформулировать условия на структуру сети
и на параметры, характеризующие трафик и процессы обслуживания заявок, при которых
метод слабой регенерации оказывается существенно более эффективным в сравнении
с классическим методом сильной регенерации. Суть найденных условий, определяющих
эффективность слабой регенерации, заключается в том, что загрузки узлов должны
быть умеренны, в то время, как вероятность пересечения заявкой сети до появления
следующей заявки должна быть близка к нулю. Эти условия являются конструктивными
(причем, легко проверяемыми) и в наибольшей степени соответствуют условиям реальных
коммуникационных сетей, которые практически никогда не бывают полностью свободными.
Эффективность метода выражается в скорости доверительного оценивания с заданной
точностью стационарных характеристик сети, таких как время ожидания заявки в
очередях и время прохождения заявкой сети. Показана возможность увеличения точности
оценивания с помощью техники уменьшения дисперсии оценки, основанной на монотонности
исследуемых сетевых процессов. Разработаны алгоритмы идентификации моментов
слабой регенерации для ациклических сетей. Проведено тестирование этих алгоритмов
путем численного моделирования некоторых сетей тандемного типа в условиях, когда
метод сильной регенерации является неэффективным. Данное тестирование показало
высокую эффективность предложенной конструкции слабой регенерации и разработанного
на ее основе алгоритма оценивания. Проведен предварительный анализ числа обращений
в единицу времени для веб-ресурса http://www.kp.karelia.ru.
Данный анализ подтвердил фрактальную структуру сетевого трафика. [см.
результаты].
Задача диспетчеризации обслуживания заявок нескольких классов в узле сети
сформулирована в терминах составления оптимального расписания их выполнения
с целью минимизации общих затрат на обслуживание в условиях, когда каждая заявка
после завершения обслуживания порождает группу новых заявок различных классов.
Решение задачи получено в виде алгоритма оптимального динамического назначения
приоритетов при обслуживании заявок нескольких классов одним прибором с обратной
связью. Исследование оптимального расписания сведено к задаче линейного программирования,
(оптимальное) решение которой обеспечивает минимизацию общих затрат на обслуживание.
Предложенный метод позволяет также исследовать чувствительность оптимального
расписания к изменениям параметров модели. Получены аналитические решения в
частных случаях. Для решения задачи оптимального динамического назначения приоритетов
использовались методы теории управляемых марковских процессов, имитационного
моделирования, теории расписания, линейного программирования. Новизна подхода
состоит в применении данных методов к новым задачам, что приводит к значительному
практическому эффекту. Исследованы качественные свойства оптимальной стратегии
управления, [2]. Качество управления зависит от доступной наблюдению информации.
Зачастую стоимость дополнительной информации значительно превосходит эффект
от ее использования. Поэтому в рамках проекта проведено исследование влияния
наблюдаемости и управляемости на качество оптимального управления в задаче назначения
приоритетов. Разработан метод и проведено сравнение оптимальных дисциплин обслуживания
в системе с неоднородными приборами при различных возможностях наблюдения за
системой и различных ограничениях на доступность управления. Сравнение различных
дисциплин при обслуживании заявок неоднородными приборами показало, что расширение
возможностей наблюдения системы может значительно улучшить качество обслуживания.
С другой стороны, это исследование позволило выявить достаточно просто реализуемые
политики обслуживания, близкие к оптимальным [3]. Все полученные результаты
являются принципиально новыми либо существенно обобщают известные результаты.
Доказано свойство устойчивости выходного потока коммуникационной сети типа
Джексона по отношению к возмущениям входного потока в сеть. Данный результат
указывает новые подходы к анализу очень актуальной проблемы устойчивости сетевых
процессов. Доказательство базируется на развитии эволюционных уравнений динамики
сети и некоторых неравенствах для потоков между узлами, которые позволяют свести
анализ сети общего вида к анализу более простой сети без циклов [5].
Получена характеризация неустойчивости процессов в сети Джексона в терминах
величины коэффициента трафика в узлах, [8]. Именно, если максимум коэффициентов
больше 1, то нагрузка (и число заявок) в сети растет с вероятностью 1 (сильная
неустойчивость), если же этот максимум равен 1, то рост происходит по вероятности
(слабая неустойчивость). Ранее не был рассмотрен случай слабой неустойчивости.
Отметим, что последний результат не удается получить весьма популярным методом
жидкостной аппроксимации,[32].
Проведены новые численные исследования по проверке эффективности метода слабой
регенерации при оценивании суммарного времени ожидания заявки в очередях, а
также времени прохождения заявкой тандемной сети, содержащей несколько односерверных
узлов и 2-узловой тандемной сети с несколькими серверами на втором узле. Показано,
в частности, что время моделирования на основе классической регенерации нелинейно
возрастает с ростом числа узлов сети и быстро становится неприемлемым для моделирования
в реальном времени, оставаясь вполне приемлемым (и практически неизменным) при
использовании слабой регенерации [6,7].
Начата разработка алгоритмов идентификации моментов более общей, квази-регенерации,
которая объединяет множество различных типов точек слабой регенерации в один
тип, а также теоретическое обоснование такого подхода. Предварительный анализ
показывает, что такой подход может быть особенно эффективен, когда среди различных
типов есть доминирующие (по частоте точек регенерации, получаемых в процессе
моделирования).
Установлено наличие тяжелого хвоста и свойство самоподобия (фрактальности) у
распределения трафика (числа обращений в единицу времени) веб-ресурса www.energy-links.com
[см.результаты].
Продолжены исследования оптимальных политик управления обслуживанием требований
в системе с неоднородными приборами. Численными методами исследована модель
с несколькими неоднородными приборами относительно двух критериев: минимизации
среднего числа требований в системе и минимизации полной стоимости обслуживания.
Для первой модели численный анализ подтвердил полученные ранее теоретические
результаты относительно порогового характера оптимального управления с использованием
наиболее быстрого из свободных приборов в случае необходимости, а также позволил
найти количественные значения порогов для рассмотренных примеров. Для задачи
минимизации средней стоимости обслуживания численные исследования позволяют
предложить простое квази-оптимальное правило обслуживания, также обладающее
пороговым свойством с использованием наиболее "эффективного" из свободных
приборов в случае необходимости. Приведены алгоритмы и выполнены численные исследования
оптимальной дисциплины обслуживания требований в системе с неоднородными приборами.
Полученные результаты могут быть использованы в системах с восстановлением порядка
обслуживания в моделях телекоммуникационных сетей.
Одной из важных составляющих качественного обслуживания заявок в телекоммуникационных
сетях является их надежность. Телекоммуникационные сети обладают сложной иерархической
структурой с контролируемыми или частично контролируемыми отказами. Проведено
исследование надежности систем сложной иерархической структуры с постепенными
отказами и различными стратегиями их контроля и восстановления. Исследована
модель надежности сложной иерархической системы с постепенными отказами и различными
стратегиями восстановления системы в случае обнаружения отказа: a) полное восстановление
системы; б) восстановление лишь отказавшего элемента. Показано, что марковские
процессы, описывающие функционирование сложных ненадежных иерахических систем,
хотя и не обладают свойством мультипликативности стационарных вероятностей,
тем не менее, допускают аналитическое или достаточно простое алгоритмическое
представление. Получены алгоритьмы вычисления стационарных и нестационарных
характеристик надежности таких систем. Модели надежности сложных иерархических
систем с постепенными отказами очень важны для приложений, но среди огромного
количества исследований в области надежности ранее отсутствовали.
В рамках исследования структуры потоков информации в телекоммуникационных сетях
проводились исследования распределений с почти отсутствующей памятью (ПОП-распределений),
введенных недавно в связи с различными моделями случайных периодических явлений.
Разработана методика и предложены алгоритмы статистического анализа ПОП-распределений.
Эти исследования проводились в сотрудничестве с проф. Б. Димитровым и факультетом
науки и математики Кеттеринг университета штата Мичиган (США).
Велась дальнейшая разработка и тестирование алгоритмов выявления моментов
квази-регенерации и оценивания характеристик в моделях локальных сетей. Осуществлен
анализ сетевых IP-протоколов низкого уровня для оценки их возможности по идентификации
моментов слабой регенерации. Удалось установить связи между свойством регенерации
и свойством долговременной зависимости. В частности, на теоретическом уровне
удалось выяснить, что регенеративный метод моделирования может быть успешно
применен к процессам со свойством долговременной зависимости. Например, это
имеет место для процесса незавершенной загрузки в одноканальной системе обслуживания
общего вида с конечным третьим и бесконечным четвертым моментом времени обслуживания,
[9,33]. Ранее сочетание регенеративного моделирования со свойством долговременной
зависимости считалось невозможным.
Предложена конструкция слабой регенерации для сетей с несколькими входными потоками
восстановления. Этот подход опирается на метод расщепления и сведение однозависимого
процесса к слаборегенеративному процессу с независимыми длинами циклов регенерации.
Затем для доказательства положительной возвратности вложенного процесса восстановления,
порожденного точками (слабой) регенерации, используются асимптотические свойства
незавершенного времени восстановления, [29,33].
Коснемся возможностей включения регенеративного метода для мониторинга и оценивания
характеристик локальной коммуникационной сети как средства открытой операционной
системы Unix. В настоящее время большая часть локальных сетей во всем мире объединены
между собой при помощи семейства протоколов пакетной передачи данных TCP/IP
(Transmission Control Protocol/Internet Protocol). Это семейство протоколов
позволяет обмениваться информацией между компьютерами, расположенными в разных
сетях с различными технологиями, применяемыми в работе локальной сети для передачи
данных на физическом уровне. Однако, наиболее распространенные технологии локальных
коммуникационных сетей (Ethernet) предоставляют пользователям лишь средство
для передачи данных со слабо развитыми возможностями управления этими данными.
Например, большинство программных средств позволяют лишь оценивать трафик (количество
информации в единицу времени). С другой стороны, вследствие возросших требований
к качеству обслуживания (QoS), последние разработки на уровне сетевых протоколов
и сетевых компонентов операционных систем уже содержат некоторый инструментарий
для работы с очередями пакетов данных (iproute2). Данные специальные средства
представлены в последних версиях сетевых операционных систем семейства Unix
(ОС Linux) на уровне реализации сетевых функций и позволяют управлять очередями
пакетов. Однако они не содержат информации о динамике движения пакета. В то
же время, именно учет динамики движения является ключевым элементом возможного
применения метода квази-регенерации, суть которого состоит в обнаружении моментов
появления заявок, обрабатываемых в сети без ожидания в очередях. Идентификация
таких моментов (моментов квази-регенерации), алгоритмически опирается на выявление
моментов ухода групп так называемых зависимых пакетов, то есть пакетов, которые
одновременно ожидают в очереди на обработку на одном и том же сетевом интерфейсе.
Эффективность данного метода оценивания характеристик сети установлена для некоторых
моделей описывающих локальные коммуникационные сети без циклов, [27].
Как показывает проведенный анализ, в принципе возможно развитие пакета iproute2
(за счет создания набора утилит на сетевом уровне в стеке протокола IP) для
осуществления мониторинга динамики движения пакетов по сети таким образом, чтобы
включить метод доверительного оценивания характеристик сети в реальном времени
на основе метода квази-регенерации.
По итогам исследований в рамках данного проекта его участница И.В.Аминова в
2003 г. успешно защищена диссертация на соискание ученой степени кандидата физико-математических
наук "Моделирование сетей обслуживания методом слабой регенерации".
Среди основных, полученных ею результатов, надо выделить нахождение конструктивных
условий, когда метод слабой регенерации оказывается существенно более эффективным,
чем классическая регенерация при доверительном оценивании стационарных характеристик
сетевых процессов, а также ряд результатов об уменьшении дисперсии статистической
оценки, основанных на свойстве монотонности сетевых процессов и некоторых специальных
методах генерирования случайных чисел. Исследования И.В.Аминовой поддержаны
грантом по проекту МАС в 2003 г.
Результаты участников проекта по исследованию эффективности метода слабой
регенерации включены в перечень "Важнейшие достижения Российской Академии
Наук" за 2002 г.
Продолжались исследования в области оптимального управления системой с неоднородными
приборами. Разработаны программы определения оптимальных дисциплин обслуживания
заявок в системе с неоднородными приборами и вычисления основных характеристик
их производительности для широкого класса входящих потоков и механизмов обслуживания
заявок. В частности, такие программы разработаны для марковского входного потока
и PH - распределений длительностей обслуживания. Проведен численный анализ различных
стратегий управления обслуживанием требований. Показано, что оптимальные стратегии
обладают пороговым свойством, причем при необходимости следует включать либо
наиболее мощный из достапных приборов в задаче минимизации длины очереди, либо
наиболее эффективный прибор в задаче минимизации суммарных затрат на обслуживание.
Были продолжены исследования в области настационарных потоков и распределений
с почти отсутствующей памятью (ПОП-распределений). Были установлены тесные связи
периодических потоков с ПОП-распределениями и разработаны методы и алгоритмы
статистического анализа таких потоков. На основе алгоритмов разработаны программы,
которые проверены на модельных данных. Полученные разработки могут служить прототипом
пакета прикладных программ для анализа потоков данных и процессов их передачи
в локальных сетях. Разработана программа проверки статистических гипотез относительно
ALM-распределений.
Разработана базовая программа численного исследования характеристик стационарных
характеристик надежности сложных иерархических систем и алгоритм пользовательского
интерфейса, позволяющего пользователю самому задавать необходимую структуру
модели и ее параметры в диалоговом режиме.
Результаты работы по проекту 01-07-90259 докладывались на
Список библиотек, где можно ознакомиться с авторефератом диссертации Аминовой И.В.: