ОБ ИССЛЕДОВАНИЯХ В 2006 ГОДУ ПО ГРАНТУ
04-07-90115 В
Руководитель:
Морозов Е.В. - д.ф-м.н., профессор,Институт
прикладных математических исследований Карельского научного центра РАН, г.
Петрозаводск;
Рыков В.В. - д.ф-м.н., профессор, Российский Государственный
университет нефти и газа им. И.М. Губкина, г.Москва;
Белый А.В. - преподаватель,
Петрозаводский государственный университет, г. Петрозаводск;
Боденов
Д.В. - аспирант, Петрозаводский государственный университет, г.
Петрозаводск;
Бородина А.В. - младший научный сотрудник,
Институт прикладных математических исследований Карельского научного центра РАН,
г. Петрозаводск;
В отчетном периоде дальнейшее развитие получил метод исследования стационарности регенеративных систем и сетей на основе использования методов теории восстановления и теории регенерирующих процессов. Этот метод использует асимптотические свойства незавершенного времени восстановления в процессе, порожденном моментами регенерации. Эффективность данного метода также связана с тем, что широкий класс процессов, рассматриваемых в качестве моделей для описания реальных сетевых процессов (в частности, сетевых трафиков), обладает свойством классической регенерации. Это, например, относится к любой модели, в описании которой присутствует экпоненциальное (пуассоновское) распределение, или распределение интервалов входного потока имеющее неограниченный носитель. С помощью данного метода уточнены необходимые условия стационарности первого узла в 2-х узловой тандемной сети с контролем доступа в виде обратной связи следующего вида: входной поток в первый узел блокируется, когда очередь во втором узле превышает заданный порог. В частности, данная задача полностью решена в случае, когда интенсивность первого узла больше интенсивности второго узла.
Кроме того, данный метод впервые успешно применен для выяснения минимальных достаточных условий стационарности широкого класса многоканальных систем с повторными вызовами, играющих важную роль в современных коммуникационных сетях, в первую очередь, в беспроводной телефонии. В частности, рассмотрены системы с конечным буфером и системы с нетерпеливыми заявками на орбите. Было установлено, что условия стационарности таких систем совпадают с известными условиями стационарности аналогичных систем с неограниченным буфером для ожидания. Этот на первый взгляд неожиданный результат(поскольку в системе с повторными вызовами происходит потеря мощности обслуживающего устройства) объясняется тем (установленным в процессе работы) фактом, что дисциплина обслуживания заявок в системе с повторными вызовами асимптотически сближается с классической дисциплиной обслуживания в системе с неограниченным буфером, когда величина орбиты неограниченно возрастает. Такой класс дисциплин был назван дисциплинами, асимптотически сохраняющими работу. Важно отметить, что метод доказательства легко применим не только к марковским, но и к широкому классу немарковских регенерирующих процессов.
Обнаружены интересные связи между поведением системы с повторными вызовами, где орбита моделируется обычной одноканальной очередью (а также и аналогичной тандемной сети) и работой сетевого протокола TCP, поскольку в некоторых случаях время задержки повторной передачи потерянных данных может моделироваться временем задержки заявки на орбите. Предполагается продолжить работу по развитию этого направления исследований.
Начаты исследования по оценке вероятностей редких событий в марковских процессах обслуживания на основе выявления регенеративной структуры в методе расщепления, используемого для ускорения процедуры имитационного моделирования. В частности, показана эффективность данного метода (по точности и скорости оценивания) при оценке вероятности переполнения очереди в одноканальной экспоненциальной системе (где известные аналитические результаты позволяют оценить качество имитационного моделирования). Основная задача этого исследования - установить состоятельность оценок, получаемых методом расщепления, а также обосновать доверительное оценивание вероятностей редких событий. Предложен принципиально новый подход к оцениванию вероятностей редких событий методом расщепления в немарковских процессах, путем рассмотрения соответствующей вложенной цепи Маркова. Данный подход нуждается в дальнейшем экспериментальном подтверждении ввиду появляющейся рандомизации пороговых значений, используемых в классическом методе расщепления.
Метод квази-регенеративного имитационного моделирования был использован для оценивания средней продолжительности ожидания заявок в локальной сети древовидной структуры, при условии долговременной зависимости процесса времени ожидания. Ранее, в 2004-2005, подобное оценивание выполнялось лишь для узлов тандемных сетей. В качестве распределений для времен обслуживания использовались распределения Парето и Вейбулла с сохранением моментных условий, при которых ранее было доказано существование долговременной зависимости для изолированного узла. При моделировании наблюдался эффект долговременной зависимости времен ожидания на всех узлах древовидной сети. При этом удалось продемонстрировать, что за приемлемое время моделирования возможно накопить необходимое число циклов квази-регенерации для построения доверительного интервала для оценки стационарного среднего времени пересечения заявкой сети. Также выполнялось оценивание параметра Херста по методу Уиттла.
Одним из направлений работы стало также построение регенеративной модели реально существующей распределенной сети с цепочкой прокси-серверов, где отсутствует физический буфер для ожидающих сообщений. Были определены условия возникновения моментов сильной регенерации в такой системе, а также моментов квази-регенерации. Эта возможность основана на том факте, что на периодах обновления основного процесса, которые всегда предшествуют моменту квази-регенерации, очередь ожидающих сообщений отсутствует, и процесс загрузки ведет себя стохастически также, как и процесс загрузки в системе с буфером. Параллельно отработан статистический и алгоритмический механизм выявления свойства долговременной зависимости основных процессов обслуживания в таких сетях. В частности, использована рекурсивная формула идентификации моментов квази-регенерации, позволяющая существенно упростить алгоритмическую реализацию метода. В настоящее время проводится численное имитационное моделирование по построенной модели, чтобы получить оценки характеристик (например, времени нахождения заявки в системе) и сравнить их с результатами наблюдений за реально действующей сетью.
В 2006 году разработан и реализован новый алгоритм определения квази регенерации на основе конечных идентификаторов. Алгоритм проверен при помощи имитационного моделирования работы некоторых сетей сложной структуры и показал свою эффективность (по частоте выявленных моментов квази-регенерации, по скорости построения доверительных оценок и по возможности встраивания в механизм сетевых протоколов). Начато описание метода в терминах обобщенных полумарковских процессов (ОПМП), а также его реализация в применении к новым протоколам маршрутизации, используемым в современных коммуникационных сетях, в частности, в передаче данных по технологиям IP/MPLS.
Квази-регенерация является адаптацией регенеративного метода к анализу трафика реальных коммуникационных сетей и опирается на тот факт, что некоторые заявки могут пересекать сеть без взаимодействия с другими заявками. Таким образом, наличие квази-регенерации можно трактовать как наличие скрытых разрывов в сетевом трафике. Этот подход особенно эффективен, когда загрузка сети достаточно высока и классическая регенерация, которую в данном контексте можно трактовать как явные (сильные) разрывы, отсутствует (или почти отсутствует).
В основе определения квази-регенерации лежит понятие группы зависимости, когда объединение заявок в группу происходит при их столкновении (одновременном присутствии в очереди какого-либо узла). В случае встречи заявок из разных групп эти группы объединяются в одну. Принцип группировки заявок, основанный на идентификаторах очередей, облегчает математическое описание групп зависимости в терминах ОПМП, однако при использовании нового подхода возрастает зависимость между циклами регенерации, что требует дальнейших теоретических разработок.
Для оценки эффективности реализации алгоритма управления потоком запросов на веб-сервере "Internet Information Services" было проведено тестирование работы веб-сервера путем генерации искусственного потока запросов c заданными параметрами к соответствующим сервисам и измерение показателей производительности и скорости их обработки. Результаты проведенного тестирования образовательного веб-сервера показали уменьшение среднего времени ответа на запрос, а также снижение процента ошибок перегрузки серверного аппаратного обеспечения. Результаты исследований вошли в кандидатскую диссертацию "Моделирование процессов управления качеством предоставления сервисов в системах дистанционного обучения, использующих технологии Интернет", успешно защищенную в марте 2006 г. в Петрозаводском госуниверситете.
В области исследования надежности сложных иерархических систем разработана общая структура программного обеспечения анализа надежности и рисков. Предложена модель деградации для технических и биологических объектов.
Основные результаты 2006 года в области анализа неоднородных сетей связаны с анализом характеристик производительности отдельного узла сети с неоднородными каналами. На основе предыдущих исследований разработаны программные средства расчета различных стационарных характеристик производительности узла сети: средней величины и дисперсии длины очереди, среднего и дисперсии времени ожидания и времени доставки сообщения, загрузки системы и отдельных каналов и т.п., а также функций распределения времени ожидания и времени доставки сообщений при оптимальной и некоторых эвристических дисциплинах обслуживания сообщений в узле. Проведенный широкомасштабный численный анализ модели позволил сформулировать полезные практические рекомендации по использованию каналов различной производительности.
Результаты исследований, проводимых в рамках проекта получили признание российских и зарубежных исследователей. В частности, руководитель проекта был приглашен в программный комитет 1-й Международной конференции по математическим методам анализа современных телекоммуникационных сетей "Valuetools" (Пиза, Италия, октябрь 2006), для чтения интенсивного курса лекций, связанных с темой проекта, для аспирантов телекоммуникационных специальностей Университета Пизы (октябрь 2006), а также посетил Университет Сарагосы в рамках проекта, связанного с исследованием монотонности сетей обслуживания (Испания, июнь 2006). Кроме того, руководитель проекта был приглашен и сделал доклады на 2-й международной Мадридской конференции по теории очередей (июль 2006), в исследовательском центр INRIA (Франция, ноябрь 2006), на семинаре в Технологическом Университете Хельсинки (Финляндия, май 2006), в университете г. Гента (Бельгия, май 2006).
Кроме того, участники проекта были приглашены с докладами на 26-й международный семинар "Stability problems for stochastic models" (Sovata-Bai, Румыния, август 2006).
Результаты исследований докладывались на ежегодном семинаре "Finnish Data Processing Week at the University of Petrozavodsk" (август 2006), на Российско-Скандинавском симпозиуме "Теория вероятностей и прикладная вероятность" (август 2006, Петрозаводск), в организации которого авторы проекта принимали активное участие, на международной конференции по статистическим моделям для биологических и технических систем (Лимасол, Кипр, май, 2006 г.)
Участие в международных конференциях и семинарах было осуществлено при финансовой поддержке РФФИ в рамках данного проекта.