автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Архитектуры и методы проектирования мигрирующих систем

На правах рукописи

Степанов Александр Геннадьевич

АРХИТЕКТУРЫ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МИГРИРУЮЩИХ СИСТЕМ

Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2005

Работа выполнена в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» имени В. И. Ульянова (Ленина)

Научный руководитель -

доктор технических наук, профессор Фомичев В. С.

Официальные оппоненты:

доктор технических наук, профессор Геппенер В. В., кандидат технических наук Глазунов А. Г.

Ведущая организация - Санкт-Петербургский институт информатики и автоматизации РАН (СПИИРАН)

Защита диссертации состоится «<9/» //o9¿>A>S 2005 г. в часов на заседании диссертационного совета Д 212.238.01 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» имени В. И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан 2005 г.

МОй-lf Я/PY/f/

libit 1

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. Современные темпы развития корпоративных сетей и Internet требуют создания эффективного и надежного программного обеспечения, удовлетворяющего потребностям огромного числа пользователей. Сложность среды выполнения и отсутствие единой точки администрирования распределенных сетевых приложений привело к появлению программных систем, способных динамически адаптироваться к изменениям в сети, обеспечивая гибкое решение масштабируемости.

Одним из видов таких приложений являются мигрирующие системы. Они могут использоваться в различных прикладных областях для получения гибких, надежных и производительных программных комплексов, выполняющих обслуживание запросов внешних клиентов. Работа мигрирующих систем в первую очередь ориентирована на обслуживающие приложения, не очень часто изменяющие свое внутреннее состояние, такие как Web-серверы со статическими Web-страницами, поисковые системы, Proxy-серверы, файловые серверы, доступные только для чтения. Наличие внутреннего состояния требует от распределенных компонентов мигрирующей системы координировать свои действия при изменении этого состояния для избежания конфликтов и сохранения целостности совместно используемых данных. С учетом этих ограничений мигрирующие системы могут успешно использоваться для серверов баз данных, почтовых серверов, файловых серверов с полным доступом при наличии, например, стандартных средств репликации баз данных.

Отсутствие теоретической базы и средств оценки характеристик различных архитектурных решений делают проектирование мигрирующих систем нетривиальной задачей. Важность выбора архитектуры и определения параметров всех компонентов системы обусловлена сложной зависимостью характеристик мигрирующей системы от тех решений, которые были приняты на этапах анализа и проектирования. Сложность разработки мигрирующих систем связана с их распределенным характером, работой в гетерогенной динамически изменяющейся среде и необходимостью автономно принимать решения с целью достижения оптимальных характеристик работы. Анализ существующих литературных источников показал, что хорошо изученными являются технологии, используемые при построении мигрирующих систем, такие как мобильные агенты, динамическое перераспределение нагрузки, контекстно-ориентированные приложения. Между тем, эти работы не рассматривают мигрирующие системы как единую технологию, и исследование архитектур и методов проектирования мигрирующих систем на сегодняшний день является актуальной задачей.

Цель работы. Целью данной работы является разработка обобщенной архитектуры и алгоритмов функционирования мигрирующих систем, использующих совокупность таких технологий как мобильные агенты, контекстно-ориентированные вычисления и системы перераспределения нагрузки, а также создание моделей и инструментов анализа, составляющих базу процесса проектирования мигрирующих систем. Для достижения поставленной цели в работе решаются следующие задачи:

- описываются свойства мигрирующей системы, и определяется круг задач, для решения которых могут использоваться системы данного класса;

- разрабатываются обобщенная и две специализированные архитектуры мигрирующих систем и сравниваются характеристики, полученные для различных архитектурных решений;

- выполняется построение модели мигрирующей системы в рамках теории массового обслуживания, позволяющей исследовать ограниченное число процессов, протекающих в системе;

РОС. НАЦИОНАЛЬНАЯ J I БИБЛИОТЕКА I

J С. Петербург/* (V* J ' 08

- описывается формальная теоретико-множественно-событийная модель, включающая основные компоненты мигрирующей системы, среду ее выполнения, внешних пользователей, а также определяются множества событий, которые происходят в системе;

- разрабатывается методика построения мигрирующих систем на основе теоретико-множественно-событийных моделей;

- проводится анализ, проектирование и реализация пакета программ для имитационного моделирования мигрирующих систем, учитывающего широкий круг параметров системы и ее окружения;

- проводятся эксперименты, связанные с анализом и синтезом мигрирующих систем, и выполняется сравнение результатов экспериментов с характеристиками, полученными для модели массового обслуживания;

реализуется прототип мигрирующей системы, и сравниваются результаты, полученные для прототипа и построенных моделей.

Предмет исследования. Объектом исследования являются мигрирующие системы, а предметом - методы анализа, моделирования, проектирования и реализации мигрирующих систем обслуживания.

Методы исследования. Для решения поставленных задач в работе используются методы теории множеств, теории систем массового обслуживания, теории автоматов, теории вероятности, исследования алгоритмов, моделирования, анализа и проектирования распределенных, многозадачных и многопоточных программных систем.

Научная новизна. В работе были получены следующие научные результаты:

- построена полностью децентрализованная обобщенная архитектура мигрирующих систем, отличающаяся тем, что она включает совокупность трех технологий -мобильных агентов, контекстно-ориентированных вычислений и перераспределения нагрузки, применяемых независимо в различных корпоративных системах;

- построена модель системы массового обслуживания, рассматривающая мигрирующую систему как обслуживающую систему, которая изменяет свое состояние под воздействием потоков событий. Модель позволяет уже на этапе проектирования получить такие характеристики системы как абсолютная пропускная способность или среднее время нахождения запроса в системе;

- построена формальная теоретико-множественно-событийная модель, описывающая как контекст выполнения, так и все компоненты мигрирующей системы, их взаимосвязь, события и операции, и позволяющая определять текущее состояние системы в зависимости от ее архитектуры и производимых воздействий;

- разработана методика построения мигрирующих систем на основе теоретико-множественно-событийных моделей, позволяющая выполнять анализ создаваемых распределенных мигрирующих приложений и получать их характеристики.

Достоверность. Достоверность полученных результатов подтверждается совпадением экспериментальных данных, полученных с помощью имитационной модели и разработанного прототипа мигрирующей системы.

Практическая значимость. В результате выполнения данной работы были получены следующие практические результаты:

- разработаны две специализированные архитектуры, дающие готовые проектные решения при реализации распределенных программных комплексов на основе мигрирующих систем, работающих в локальных и глобальных сетях;

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

- написан прототип мигрирующей системы, позволяющий убедиться в корректности построенных моделей и методики, а также демонстрирующий использование методики на примере разработки распределенной системы поиска.

Апробация. Основные результаты работы докладывались на Международных конференциях по мягким вычислениям и измерениям (SCM) в 2002 - 2004 гг.

Публикации. По теме диссертации опубликовано 6 печатных работ, из них - 3 статьи и тезисы к 3-м докладам на международных конференциях.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы, включающего 108 работ, и трех приложений. Основная часть работы изложена на 164 страницах машинописного текста. Работа содержит 51 рисунок и 14 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится обоснование актуальности темы диссертационной работы, описывается цель работы, определяется круг задач, формулируется объект и предмет исследования, указываются методы исследования, сообщается научная новизна и практическая значимость и подтверждается достоверность полученных результатов.

В первой главе, носящей обзорный характер, выделяется класс исследуемых приложений, а также описываются технологии, лежащие в основе построения таких приложений. Эти технологии включают системы мобильных агентов, динамическое перераспределение нагрузки и контекстно-ориентированные вычисления.

Исследуемым классом приложений являются системы, обеспечивающие высокую доступность услуг. Высокая доступность заключается в непрерывном обеспечении пользователей определенными услугами независимо от сбоев, происходящих в программном и аппаратном обеспечении, и изменения нагрузки, создаваемой пользователями. К таким системам относятся почтовые системы, сохраняющие способность принимать и отправлять почту даже при полном выходе из строя почтового сервера, на котором располагаются почтовые ящики пользователей.

В настоящее время обеспечение высокой доступности услуг решается одним из трех способов:

- перемещением отдельных элементов системы, находящихся на вышедшем из строя сервере (используется в технологии мобильных агентов);

- переключением пользователей с вышедшего из строя сервера на доступные рабочие серверы (используется в контекстно-ориентированных системах);

- созданием групп серверов, распределяющих между собой поступающие запросы пользователей (используется в системах перераспределения нагрузки и кластеризации).

Основными недостатками технологии мобильных агентов для построения систем, обеспечивающих высокую доступность услуг, являются:

наличие стационарной части (платформ или контейнеров), в контексте которой выполняются мобильные агенты, что существенно снижает гибкость системы при перераспределении ресурсов;

- большинство систем мобильных агентов имеют централизованную архитектуру, в которой основные компоненты (система управления, служба именования) существуют в единственном экземпляре и являются узким местом в надежности;

- системы мобильных агентов в основном ориентированы на выполнение действий от имени пользователя, а не на обслуживание потоков запросов.

Основными недостатками контекстно-ориентированных систем являются:

- контекстно-ориентированные системы в основном разрабатываются для приложений, связанных с управлением информационным и реальным миром на основании заложенного профиля и собираемого в процессе работы контекста, и не рассматривают вопросы обслуживания потоков запросов;

- большинство существующих контекстно-ориентированных систем для сбора информации используют различные физические датчики (положения, скорости, давления), а не средства анализа программных систем, такие как счетчики производительности или сетевые мониторы.

Основными недостатками систем перераспределения (балансировки) нагрузки и кластеризации являются:

- использование дополнительного дорогостоящего программного или аппаратного обеспечения;

- расширение кластера требует вмешательства администратора для добавления нового сервера в состав кластера и изменения настроек кластерной системы, а также приостановки работы кластера на время выполнения модификации;

- кластерные системы не обеспечивают автоматического масштабирования и используют набор серверов, входящих в кластер, в течение всего времени работы независимо от текущей загрузки;

- большинство систем балансировки нагрузки имеют централизованный диспетчер, являющийся узким местом в надежности системы;

- для эффективного распределения запросов, учитывающего производительность серверов и их текущую загрузку, системы балансировки требуют установки на все серверы программных агентов, которые расходуют вычислительные ресурсы.

Мигрирующие системы объединяют рассмотренные подходы в единую технологию и позволяют устранить ряд проблем, возникающих при построении систем, обеспечивающих высокую доступность услуг.

Мигрирующими системами называются обслуживающие системы, обеспечивающие высокую надежность, отказоустойчивость, гибкое изменение производительности и динамическое распределение нагрузки за счет перемещения по сети всех своих компонентов.

Мигрирующая система представляет собой набор сервисов, каждый из которых обеспечивает внешних пользователей одной или несколькими услугами. Сервис является перемещаемой сущностью мигрирующей системы и, как правило, независим от остальных сервисов. Общение пользователей с сервисами происходит посредством передачи запросов, которые могут содержать исходные данные решаемой задачи, критерии поиска, результаты работы. Перемещение сервиса с одного узла на другой происходит в ответ на асинхронные события, получаемые от внутренних или внешних источников. В качестве внутренних источников событий могут выступать специальные компоненты сервиса, анализирующие изменения параметров и характеристик среды выполнения и состояния самого сервиса. Источниками внешних событий могут являться команды, поступающие от пользователя и других систем.

Основным направлением использования мигрирующих систем являются корпоративные и промышленные программные решения, обеспечивающие высокую доступность

сервисов в условиях нестабильности среды выполнения и постоянно изменяющейся внешней нагрузки:

- почтовые системы, обеспечивающие пользователей непрерывным доступом к электронной почте при выходе из строя почтового сервера путем миграции на свободные почтовые сервера;

- системы проведения конференций, выполняющие равномерное распределение трафика, поступающего от участников конференции, между несколькими серверами, географически приближенными к участникам;

- системы управления, контролирующие работу стратегически важных объектов и перемещающие свои функции на резервные вычислительные машины или управляющие устройства в случае возникновения сбоев в работе головной системы;

- распределенная обработка данных, требующая сложных и ресурсоемких вычислений при относительно малых размерах исходных данных и вычисляемых результатов;

- системы безопасности, выполняющие удаленную авторизацию сетевых пользователей путем распределения функции контроля доступа между несколькими сервисами, перемещаемыми с целью предотвращения утечки информации в ту же самую локальную сеть, в которой находятся пользователи.

Для обеспечения возможности создания приложений на основе мигрирующих систем, в диссертационной работе решаются следующие задачи:

- уточняется понятие мигрирующих систем, включающее свойства, алгоритмы функционирования и области применения приложений данного класса;

- разрабатывается обобщенная архитектура мигрирующих систем, которая может служить основой для построения специализированных архитектур и реализации мигрирующих приложений, выполняющих заданные прикладные задачи;

- выполняется построение математических моделей, позволяющих описывать мигрирующие системы и исследовать их поведение;

- разрабатываются инструментальные средства, позволяющие на этапе проектирования оценить характеристики мигрирующей системы для заданной архитектуры и набора параметров;

- разрабатывается методика построения мигрирующих систем, описывающая последовательность этапов разработки от формирования идеи до программной реализации системы;

- разрабатывается прототип, подтверждающий адекватность созданных моделей реальным системам.

Во второй главе рассматривается принцип работы мигрирующих систем, приводится обобщенная архитектура на уровне функциональных компонентов, рассматриваются варианты построения каждого компонента, на основании которых создаются две специализированные архитектуры мигрирующих систем.

Работа мигрирующей системы, состоящей для простоты из единственного сервиса 5, включает себя следующие шаги:

- при запуске системы создается сервис 5] на узле сети й<, / = 1, ..., п, который либо явно назначаться администратором, либо выбираться системой по заданному критерию;

- сервис создает свою копию $2 на некотором узле Ц, / Ф у. Отдельные копии сервиса называются репликами. Реплика ¿2 находится в холодном резерве, т.е. приостановлена и не обслуживает запросы пользователей. Такая реплика называется пассивной. Реплика л может обслуживать запросы пользователей и называется активной;

- реплики сервиса 5 взаимодействуют друг с другом для выявления ситуаций отказа одной или нескольких реплик;

- если пассивная реплика определяет, что она осталась в сети одна, то она переходит в активный режим;

- если активная реплика определяет отсутствие пассивной реплики, то она создает новую пассивную реплику на узле йц, выбранном по заданному критерию;

- активные реплики взаимодействуют друг с другом для выяснения того, кто из них меньше загружен, чтобы обработать очередной запрос клиента;

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

- если суммарная загруженность реплик снижается до некоторого значения, называемого порогом дерепликации, то одна из реплик удаляется из системы.

Обобщенная архитектура сервиса мигрирующей системы может быть представлена в виде двух взаимодействующих частей (рис. 1):

- функциональной части, реализующей набор услуг, обеспечивающих решение прикладной задачи пользователя;

- управляющей части, включающей ряд системных функций, связанных с обеспечением надежности, масштабируемости, производительности, а также управлением ресурсами, которые потребляются системой (анализ состояния системы и среды ее выполнения, управление перемещением сервиса, диспетчеризация пользовательских запросов).

Рис. 1. Обобщенная архитектура сервиса мигрирующей системы

Сервис мигрирующей системы состоит из следующего набора компонентов: - модуля взаимодействия с другими репликами, обеспечивающего механизм обмена информацией между всеми репликами сервиса;

- модуля получения контекстной информации, собирающего данные о состоянии других реплик сервиса и среды выполнения системы;

- модуля принятия решений, определяющего необходимость создания и удаления реплик сервиса;

- модуля репликации и дерепликации сервиса, выполняющего создание и уничтожение реплик на удаленных узлах в сети;

модуля удаленной загрузки и запуска приложений, производящего инсталляцию реплики сервиса на другой машине и запуск ее на выполнение;

- интерфейса с клиентами, обеспечивающего точку доступа к услугам, предоставляемым сервисом, со стороны внешних пользователей;

- диспетчера запросов, выполняющего распределение поступающих запросов между репликами сервиса;

- очереди запросов, хранящей запросы, ожидающие обслуживания;

- модуля обработки запросов, реализующего прикладную функциональность сервиса (набор услуг).

В главе подробно описываются варианты построения всех компонентов мигрирующей системы, указываются их достоинства, недостатки и области применения. На основании представленных вариантов разрабатываются две специализированные архитектуры мигрирующих систем, предназначенные для обслуживания потоков запросов пользователей в локальных и глобальных сетях. Эти архитектуры могут служить основой для проектирования и реализации мигрирующих приложений.

В целях дальнейшего исследования мигрирующих систем выбирается вариант архитектуры для локальных сетей, являющийся полностью децентрализованным и использующий групповую адресацию для взаимодействия между репликами сервиса мигрирующей системы и внешними пользователями.

В третьей главе описываются две математические модели мигрирующих систем, построенные на основе теории массового обслуживания и теории множеств.

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

Теория массового обслуживания накладывает ряд ограничений на моделируемые системы. В связи с этим, в модели мигрирующей системы были сделаны следующие допущения:

- мигрирующая система устанавливается в сети Я = { Ъ\, Ы,..., й„ }, содержащей л узлов, связи между которыми образуют полный граф р = Я х Я;

- мигрирующая система состоит из единственного сервиса 8, т.е. множество сервисов 5 = { 4 };

- все реплики сервиса з являются активными;

- в начальный момент времени t = 0 в системе нет ни одной реплики;

- узлы А,, / = 1,л сети Я могут выходить из строя; поток отказов узлов - простейший с интенсивностью V;

- после отказа узла начинается его восстановление; поток восстановления узлов - простейший с интенсивностью

- на каждом узле А,,)' = 1,и сети Я может быть создана только одна реплика сервиса л; если на всех узлах сети уже существуют реплики сервиса то очередной запрос на репликацию получает отказ;

- на вход системы поступают однотипные запросы гр которые обслуживаются сервисом поток запросов - простейший с интенсивностью X;

- поступивший в систему запрос гу может быть обслужен любой репликой / = \,т сервиса 5; поток обслуживания запросов - простейший с интенсивностью ц;

- каждая реплика я,, / = 1 ,т сервиса $ имеет очередь ц, длиной /;

- если сервис 5 имеет свободную (незанятую выполнением запроса) реплику 5„ то при поступлении в систему очередного запроса гу он направляется на обслуживание в реплику ${,

- если все реплики / = 1, т сервиса ^ заняты, то поступивший запрос г, помещается в конец очереди реплики !„ имеющей наименьший индекс / и свободные места в очереди;

- если очереди всех реплик = 1 ,т сервиса 5 заполнены, то при поступлении очередного запроса выполняется процедура репликации (создается новая реплика сервиса запрос ^ помещается на обслуживание в реплику s^;

- если очереди всех реплик , / = 1, т сервиса 5 заполнены, и процедура репликации невозможна, то вновь поступивший запрос Гу получает отказ;

- если после завершения выполнения запроса гу реплика 5, оказывается пустой (не содержит запросов ни в своей очереди д;, ни на обслуживании), то выполняется процедура дерепликации реплики (реплика 8, удаляется из системы);

- если на узле Л, выполняется реплика 5*, и узел А/ выходит из строя, то реплика теряется (вместе с запросами, находящимися на обслуживании и в очереди реплики

В качестве примера была рассмотрена модель мигрирующей системы со следующими параметрами: количество узлов сети п -3, длина очереди реплики / = 1, интенсивность потока обслуживания запросов ц ■= 1, интенсивность потока отказов узлов и = 0,01, интенсивность потока восстановления узлов £ = 0,1, интенсивность входящего потока запросов X изменяется в серии экспериментов.

Граф состояний системы представлен на рис. 2. Вершины графа представляют состояния системы и помечены тройками чисел (к, т, г), где к - количество работоспособных узлов сети, к = 0,п; т - количество реплик, т = 0, к, г - количество запросов, находящихся в системе (в очередях реплик и на обслуживании), г = 0,(/ + 1)-т. Дуги графа взвешены интенсивностями переходов между состояниями.

На основании графа состояний была составлена система дифференциальных уравнений А.Н. Колмогорова, решение которой позволяет получить финальные вероятие. 2. Граф состоянии системы состояний системы. Финальные ве-

роятности используются для вычисления характеристик системы с применением формул теории массового обслуживания (таблица 1).

Таблица 1. Значения характеристик системы

Интенсивность входящего потока запросов X 1 2 5 10 100

Вероятность отказа в обслуживании запроса Рrefuse 0,016 0,073 0,335 0,580 0,947

Вероятность потери запроса в результате выхода из строя узлов PfaU 0,015 0,009 0,012 0,015 0,019

Вероятность потери запроса Plast 0,022 0,081 0,347 0,595 0,966

Вероятность обслуживания запроса Рreh- 0,978 0,919 0,653 0,405 0,034

Абсолютная пропускная способность A.serv 0,978 1,837 3,264 4,050 3,423

Интенсивность потока потерянных запросов Xlast 0,022 0,163 1,736 5,950 96,577

Среднее число реплик в системе m 0,948 1,672 2,421 2,607 2,678

Средняя длина очереди 4 0,325 0,507 0,670 0,788 0,969

Среднее число запросов в системе r 1,496 2,917 4,520 5,007 5,303

Сред, время нахождения запроса в очереди 'wau 0,325 1,013 _ » - -

Сред, время пребывания запроса в системе 'System 1,496 5,835 - - -

* - ограничение формул Литтла для больших значений вероятности потери запроса (Лм,>0,1).

Теория массового обслуживания имеет ограниченную применимость для исследования мигрирующих систем, связанную с трудностью построения графа состояний для большого числа параметров, ограниченностью вероятностной модели экспоненциальным законом распределения и законами Эрланга к-го порядка, невозможностью моделирования целого ряда свойств системы, в том числе характеристик узлов, сетевых соединений и пользователей системы.

Теоретико-множественно-событийная модель снимает ряд ограничений, накладываемых моделью массового обслуживания, и описывает работу мигрирующей системы как последовательную смену состояний, инициатором которой выступают различные события. Состояние системы представляется в виде набора множеств, элементы которых соответствуют компонентам мигрирующей системы и ее окружения.

Состояние мигрирующей системы M(t) в момент времени t определяется как множество состояний составляющих ее сервисов, сети и пользователей:

МО = W), £('),£/(')}.

Сеть N{t) - { #(/), р(/) } в момент времени t содержит п узлов H(t) = { h\, fa, ..., h„ }. Отношение p(f) e H(t) x H(t) определяет множество физических связей между узлами.

Мигрирующая система S(t) устанавливается в сети N(1) и в момент времени t представляет собой набор из m сервисов 5(/) = {s*\(t), i*2(i).....s*Jf) }.

Каждый сервис s*,{t) представляется в системе в виде к своих копий (реплик), которые размещаются на узлах H(t) сети. Таким образом, сервис s*,(t) в каждый момент времени t определяется множеством реплик s,{t) = { sa,..., s ¡к } и отношением сг^/) ç s/(г) х #(*), которое задает расположение реплик сервиса j<(0 на узлах сети H(t) в момент времени t.

В начальный момент времени 1 = 0 сервис $/*(0) имеет ровно одну свою копию sn, расположенную на некотором узле hj, т.е. î/(0) = { s,i } и о/(0) = { (î,i, hj) }.

В процессе работы в систему S поступают запросы (задачи) R = { п, гг, ..., гт } на обслуживание (выполнение). Количество разновидностей запросов m соответствует количеству сервисов в системе.

Каждый сервис системы s*,{t) имеет очередь q{t) = { q,i, qa, ..., qü }, в которую помещаются поступающие в систему запросы г-, и из которой запросы выбираются на обслуживание некоторой репликой сервиса stl.

Таким образом, состояние сервиса s,*(t) в каждый момент времени t определяется множеством реплик s,{t), размещенных на узлах сети, и множеством запросов пользователей q/(t), находящихся в очереди, т.е. s,*(t) = {s^t), äff), qft) }.

Множество пользователей U(t) = { щ, иг, ..., ир }, генерирующих запросы, совместно с сетью N(1) определяют окружение (контекст) мигрирующей системы.

Для описания влияния окружения на работу мигрирующей системы был определен следующий набор событий:

отказ (отключение) узла Л, - событие ф„ приводящее к удалению узла h, из списка доступных узлов Я сети и разрыву всех связей р, между узлом А, и другими узлами сети Ау:

H(t+ 1) = H(f) \ А/, А/ е #(/),

p(f + 1) = р(/) \ р,, р, = { (А/, hj) | (А/, hj) б р(0, hj е Я(0 }; восстановление (подключение) узла А/ - событие приводящее к добавлению узла А; к списку доступных узлов Я и установлению связей р, между узлом А,- и некоторыми узлами сети hf.

H(t+ 1) = H(f) и А„ А, г Я(/),

р(/ + 1) = р(/) и р,, р, = {(Л„ hj) \ (А„ Ау) г р(0, Ау е Я(/)};

- разрыв соединения pij = (А/, Aj) - событие приводящее к удалению соединения между узлами А/ и Ау:

р(Г + 1) = р(/) \ (А,, Ау), (А,, hj) б р(г), А, е Я(0, Ау б Я(/);

- восстановление соединения р(у = (А,, Ау) - событие у/0", приводящее к добавлению соединения между узлами А, и Ау:

Р(/+ 1) = р(0 и (А„ АД (А„ Ау) г р(/), А, е Я(/), h, е Я(/); репликация сервиса - событие е,, приводящее к созданию новой реплики sg на некотором узле А* сети Я:

+ 1) = i,{/) и i,y, s,y г jj(0»

ait + 1) = afi) u (sj, А*), А* e Я(/ + 1); дерепливсация сервиса s, - событие 5„ приводящее к удалению существующей реплики sij с узла А* сети Я:

s,{t + l) = Si(t)\ s^ s,j e sf/),

o,</ + 1) = а<0 \ (sij, hi), ht €= Я(0;

- поступление нового запроса г( на обслуживание сервисом st - событие а„ приводящее к постановке запроса г,- в очередь qt сервиса si на позицию qif.

qft+\) = qff)\Jqi,qitqff)-,

- завершение обслуживания запроса rt сервисом si - событие ß„ приводящее к удалению запроса г,- из очереди qi сервиса s, в позиции q,f.

qft + 1) = <?.{') \ ЧФ Чи б ?/(')■

Теоретико-множественно-событийная модель рассматривается как общее описание мигрирующей системы, которое задает ее функционирование на макроуровне.

В четвертой главе приводится методика проектирования мигрирующих систем, разрабатывается пакет программ для имитационного моделирования мигрирующих систем и проводится серия экспериментов, демонстрирующих решение задач анализа и синтеза мигрирующих систем с использованием разработанного пакета программ.

Представленная в работе методика позволяет проводить исследование мигрирующих систем на основе имитационного моделирования и учитывает все аспекты построения мигрирующей системы от создания теоретико-множественно-событийной модели до программной реализации. Методика включает следующие шаги.

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

2. Построение концептуальной схемы модели мигрирующей системы. Осуществляется переход от множественно-событийной модели к концептуальной диаграмме классов. Множествам ставятся в соответствие классы, элементам множеств - объекты классов, событиям - методы интерфейсов, действиям - реализация этих методов.

3. Разработка алгоритмов работы системы. В соответствии с выбранным вариантом архитектуры, прорабатываются вопросы, связанные с алгоритмами выбора места репликации и дерепликации, определением порогов репликации и дерепликации, управлением очередями запросов, ожидающих обслуживания, перераспределением запросов в очередях при репликации и дерепликации и др. Разработанные алгоритмы вносятся в концептуальную схему в виде методов классов или отдельных классов.

4. Построение диаграммы классов модели. Определяются функции каждого класса и интерфейсы взаимодействия между частями системы и средой выполнения.

5. Погружение модели в систему имитационного моделирования. Модель мигрирующей системы дополняется вспомогательными модулями для поддержки процесса моделирования и сбора результатов.

3.1. Управление модельным временем. Система дополняется таймером, разбивающим непрерывное модельное время на такты, к которым привязываются различные события, происходящие в системе

5.2. Введение в модель случайной составляющей. Для всех потоков событий определяются их вероятностные характеристики в виде законов распределения случайных величин.

5.3. Визуализация процесса моделирования. Объекты модели мигрирующей системы представляются в графическом виде, что позволяет визуально следить за ходом процесса моделирования.

5.4. Сбор статистической информации. Накопленная при моделировании статистика используется для расчета характеристик модели мигрирующей системы.

5.5. Хранение истории процесса моделирования. Все события, происходящие в модели, протоколируются и могут быть использованы для анализа работы системы.

6. Программная реализация мигрирующей системы. Определяются физические компоненты системы, их размещение на узлах сети и протоколы обмена информацией между компонентами. Для каждого компонента реализуются алгоритмы работы, которые были исследованы при имитационном моделировании.

В отличие от языка UML, в предложенной методике осуществляется переход от формальной теоретико-множественно-событийной модели непосредственно к диаграмме классов, минуя диаграммы вариантов использования.

Разработанная система имитационного моделирования (MSS) позволяет проводить исследование целого класса мигрирующих систем, предназначенного для использования в локальных и корпоративных сетях и основанного на архитектуре без централизованного диспетчера и общей очередью.

В MSS мигрирующая система описывается в виде нескольких моделей объектов системы и окружающей среды:

модели пользователя, учитывающей моменты генерации запросов, размеры входных и выходных пакетов данных и сложность обработки запросов;

- модели сети, включающей список узлов, соединения между узлами, пропускную способность и фоновую загрузку сети;

- модели узла, характеризующейся производительностью, фоновой нагрузкой, временем безотказной работы и временем восстановления узла;

- модели сервиса, определяющей начальный узел, на котором запускается первая реплика сервиса, максимальную длину очереди, величины порогов репликации и дереп-

ликации, алгоритмы выбора мест репликации и дерепликации, поддержку прерывания об- /

служивания запроса и отложенной дерепликации.

Система моделирования позволяет спрогнозировать поведение сервисов при изменении параметров системы и экспериментально оценить основные характеристики мигрирующей системы:

- характеристики сети, включающие среднюю фоновую загрузку сети, среднюю загрузку сети за счет миграции реплик и среднюю загрузку сети за счет передачи запросов;

- характеристики сервисов, включающие общее количество сгенерированных запросов, количество обработанных запросов, количество обслуженных запросов, количество запросов, получивших отказ в обслуживании, количество потерянных запросов, общее количество необслуженных запросов, количество репликаций и дерепликаций, среднюю длину очереди, вероятность обслуживания запроса, вероятность отказа в обслуживании, вероятность потери запроса, вероятность необслуживания запроса, среднее время обслуживания запроса, среднее время ожидания обслуживания, среднее время пребывания запроса в системе.

С использованием системы Мвв была проведена серия экспериментов, связанных с решением двух классов задач:

- задач анализа (исследование характеристик мигрирующей системы, состоящей из единственного сервиса и выполняющейся в «абсолютно надежной» сети, влияние конфигурации сети и отказов ее элементов на характеристики мигрирующей системы, изменение характеристик мигрирующей системы при одновременной работе нескольких сервисов в одной сети);

- задач синтеза (поиск оптимальных параметров мигрирующей системы, обеспечивающих безотказное обслуживание запросов пользователей).

В завершение главы было проведено сравнение результатов (рис. 3), полученных для модели системы массового обслуживания ((ЗвМ) и имитационной модели (МББ).

Рис. 3. Сравнение результатов модели массового обслуживания и имитационной модели

Представленные результаты подтверждают адекватность разработанных моделей мигрирующей системы с учетом введенных в систему ограничений. Между тем, система Мвв учитывает большее число свойств и может быть расширена путем добавления новых моделей объектов мигрирующей системы (например, модели диспетчера для исследования поведения системы в глобальных сетях) или увеличения списка параметров моделей (например, учета времени установления соединения при передаче запросов).

В пятой главе с использованием созданной методики был разработан прототип мигрирующей системы, которая реализует распределенную систему поиска, обслуживающую запросы пользователей.

Построение прототипа мигрирующей системы обслуживания позволяет решить следующие задачи, связанные с исследованием систем данного класса:

- проверить основные алгоритмы работы мигрирующей системы на выбранном языке программирования и оценить возможную трудоемкость построения полнофункциональной системы, пригодной для коммерческого использования;

- экспериментально проверить соответствие результатов математического и имитационного моделирования, полученные на предыдущих этапах работы, с результатами работы прототипа, а также выбрать набор входных параметров модели таким образом, чтобы они наиболее точно описывали мигрирующую систему и среду ее выполнения;

- проработать ряд технических вопросов, связанных с реализацией протоколов межсетевого взаимодействия частей мигрирующей системы, удаленной загрузкой и инсталляцией приложений, синхронизацией работы компонентов мигрирующего сервиса при выполнении процедур репликации и дерепликации.

Прототип системы состоит из четырех исполняемых модулей (рис. 4):

- консоли администратора (М8Со1Ио1е), предназначенной для запуска сервисов мигрирующей системы на произвольной удаленной машине;

- станции (МБЗШгоп), устанавливаемой на удаленных машинах и обеспечивающей загрузку по сети кода и данных сервисов мигрирующей системы;

- сервиса (Мввегугсе), обслуживающего запросы клиентов и перемещающегося по сети под воздействием ряда событий;

- клиента (МЗСПетй), создающего запросы, которые обслуживаются сервисами мигрирующей системы.

Рис. 4. Структура прототипа мигрирующей системы

Алгоритм работы системы можно представить следующим образом. Администратор, работающий на машине Host 1, с использованием консоли выбирает станцию той ма-

шины, на которой требуется запустить сервис (на рис. 4 станции установлены на машинах Host 2, Host 3 и Host 4). Консоль при помощи выбранной станции загружает на удаленную машину код и данные указанного администратором сервиса и запускает его. В свою очередь, на машинах Host 5, Host б и Host 7 устанавливаются клиентские приложения, с помощью которых пользователи создают запросы на поиск в базе данных и отправляют их сервису системы. Сервис, обработав запрос, возвращает результаты клиенту.

При повышении нагрузки, создаваемой клиентами, сервис принимает решение о создании своей новой копии (реплики). Для этих целей сервис находит свободную станцию, на которой пока нет данного сервиса, и создает новую копию аналогично тому, как это делает консоль администратора. После запуска реплики запросы клиентов обслуживаются параллельно на двух машинах. Процедура репликации может продолжаться до тех пор, пока на всех машинах с установленными станциями не будут выполняться копии сервиса.

При снижении нагрузки возможно удаление лишних реплик сервиса. Это позволяет сократить потребление мигрирующей системой сетевых и вычислительных ресурсов. Последняя реплика сервиса не удаляется.

Для сравнения результатов, полученных для имитационной модели и для прототипа мигрирующей системы, был проведен ряд экспериментов. В качестве критерия сравнения был выбран коэффициент ускорения, который показывает, во сколько раз быстрее сервис обслуживает запросы пользователя при одновременной работе нескольких реплик по сравнению с одной репликой.

График на рис. 5 показывает значения коэффициентов ускорения, полученные в системе имитационного моделирования (MSS) и в прототипе для двух и трех реплик сервиса мигрирующей системы.

Коэффициент ускорения

Прототип (1->2)

---Прототип (1->Э)

----MSS (1->2)

.....MSS(1->3)

10 20 30 40 50 60 70 80 SO 100 Длина лосладовател ьности запросов

Рис. 5. Коэффициенты ускорения имитационной модели и прототипа

Полученные зависимости показывают, что коэффициенты ускорения для системы MSS и прототипа имеют близкие значения. Максимальное отклонение значений имеет место при небольшом количестве создаваемых запросов. Такое отклонение объясняется тем, что при небольшом количестве запросов существенный вклад в величину коэффициента ускорения вносят процессы репликации сервиса. Временные характеристики этих процессов зависят от таких параметров, как время установления соединения, алгоритм поиска места репликации, время запуска процесса на удаленной машине. Эти параметры не учитываются в текущей реализации системы MSS, но могут быть добавлены при возникновении потребности в более детальном исследовании данных процессов.

Прототип был разработан на языке Java с использованием пакета Borland JBuilder Foundation версии 10.0. Для межсетевого взаимодействия компонентов применялся программный интерфейс сокетов, включающий обмен по протоколам Transmission Control

Protocol (TCP) и User Datagram Protocol (UDP). В протоколе UDP использовалась как адресация «точка-точка», так и групповая адресация.

На разработку прототипа было потрачено приблизительно 50 человеко-дней, что составляет около 10-20% от трудоемкости реализации коммерческой версии мигрирующей системы обслуживания, которая обладает необходимыми механизмами безопасности и надежностью, требуемой для использования продукта в крупных локальных и корпоративных сетях.

В заключении представлены результаты теоретического и экспериментального исследования мигрирующих систем, показана их научная новизна и практическая значимость.

В приложениях приводится руководство пользователя системы имитационного моделирования (MSS), листинги файлов моделей MSS, используемых в экспериментах, и пример программы, демонстрирующей удаленную инсталляцию и запуск приложений средствами Window Management Instrumentation (WMI).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Сформулировано понятие мигрирующей системы, определены ее основные свойства, а также описаны области применения распределенных систем данного класса.

2. Предложен набор архитектур и варианты построения модулей мигрирующей системы, которые являются готовыми проектными решениями и упрощают процесс разработки специализированных мигрирующих систем.

3. Построена модель мигрирующей системы в виде системы массового обслуживания, позволяющая определить ряд динамических характеристик системы, но не учитывающая архитектуру системы и алгоритмы работы ее компонентов.

4. Построена формальная теоретико-множественно-событийная модель, описывающая мигрирующую систему как совокупность множеств объектов, внешних и внутренних событий и правил, в соответствии с которыми каждому событию ставится в соответствие некоторая операция над одним или несколькими множествами объектов.

5 Представлена методика создания мигрирующих приложений, обеспечивающая простой переход от проектирования к реализации за счет использования теоретико-множесгвенно-событийной модели.

6. Написан пакет программ для имитационного моделирования мигрирующих систем, с помощью которого на этапе проектирования можно проверить алгоритмы работы и оценить характеристики системы для заданной архитектуры и набора основных параметров.

7. Реализован прототип мигрирующей системы, демонстрирующий возможности созданной методики проектирования на примере разработки распределенной системы поиска и показывающий адекватность разработанных моделей оригиналу.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Фомичев В. С., Холод И. И., Першин А. В., Степанов А. Г. Поток сообщений в системах мобильных агентов // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2002). - СПб., 25 - 27 июня, 2002, СПбГЭТУ.

2. Степанов А. Г. Свойства мигрирующих систем // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2003). - СПб., 25 - 27 июня, 2003, СПбГЭТУ.

3. Степанов А. Г. Применение моделей массового обслуживания для анализа мигрирующих систем // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2004). - СПб., 17-19 июня, 2004, СПбГЭТУ.

4. Степанов А. Г., Фомичев B.C. Имитационная модель мигрирующей системы // Известия СПБГЭТУ «ЛЭТИ». - СПб., 2004.

5. Степанов А Г., Фомичев B.C. Имитация мигрирующих систем обслуживания // Известия вузов. Приборостроение. - СПб., 5, 2005.

6. Степанов А. Г, Фомичев В С. Пакет программ для имитации мигрирующих систем обслуживания // Известия вузов. Приборостроение. - СПб., 7, 2005.

Подписано в печать 05.09.05. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Тираж 100 экз. Заказ 74.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

»173 S

РНБ Русский фонд

2006-4 16611

Сокращения и условные обозначения.

• Введение.

Глава 1. Мигрирующие системы.

1.1. Введение

1.2. Понятие мигрирующих систем.

1.3. Свойства мигрирующих систем.

1.4. Системы мобильных агентов.

1.4.1. Введение

1.4.2. Основные понятия.

1.4.3. Стандарты.

1.4.4. Области применения.

1.4.5. Сравнение с мигрирующими системами.

1.5. Контекстно-ориентированные системы.

1.5.1. Введение

1.5.2. Основные понятия.

1.5.3. Области применения.

1.5.4. Сравнение с мигрирующими системами. 1.6. Системы перераспределения нагрузки.

1.6.1. Введение

1.6.2. Основные понятия.

1.6.3. Области применения.

1.6.4. Сравнение с мигрирующими системами.

1.7. Применение мигрирующих систем.

1.8. Выводы.

Глава 2. Архитектура и работа мигрирующих систем.

I 2.1. Принцип работы мигрирующих систем

2.2. Обобщенная архитектура сервиса мигрирующей системы.

2.2.1. Модуль взаимодействия с другими репликами сервиса. i 2.2.2. Очередь запросов.

2.2.3. Диспетчер запросов.

2.2.4. Интерфейс с клиентами.

2.2.5. Модуль обработки запросов.

2.2.6. Модуль получения контекстной информации.

2.2.7. Модуль принятия решений.

2.2.8. Модуль репликации и дерепликации сервиса.

2.2.9. Модуль удаленной загрузки и запуска приложений.

2.3. Специализированные архитектуры мигрирующих систем.

2.3.1. Архитектура мигрирующей системы для локальных сетей

2.3.2. Архитектура мигрирующей системы для глобальных сетей.

2.4. Выводы.

Глава 3. Математическое моделирование мигрирующих систем.

3.1. Модель системы массового обслуживания

3.1.1. Определения

3.1.2. Ограничения, накладываемые на модель системы.

3.1.3. Классификация.

3.1.4. Модель системы.

3.2. Теоретико-множественно-событийная модель.

3.3. Выводы.

Глава 4. Имитационное моделирование мигрирующих систем.

4.1. Методика построения мигрирующих систем

4.2. Архитектура системы моделирования.

4.2.1. Задачи моделирования

4.2.2. Модель пользователя.

4.2.3. Модель сети.

4.2.4. Модель сервиса.

4.2.5. Модуль сбора статистики.

4.2.6. Модуль визуализации.

4.2.7. Модуль хранения истории процесса моделирования.

4.2.8. Случайные величины

4.3. Проектирование системы моделирования.

4.3.1. Структура модели.

4.3.2. Управление процессом моделирования.

4.3.3. Модель сети.

4.3.4. Модель узла.

4.3.5. Модель сервиса.

4.3.6. Модель реплики.

4.3.7. Модель пользователя.

4.3.8. Модель запроса

4.3.9. Модель очереди.

4.4. Эксперименты с системой моделирования.

4.4.1. Анализ системы с одним сервисом в сети без отказов

4.4.2. Анализ системы в сети с отказами узлов.

4.4.3. Анализ системы с несколькими сервисами.

4.4.4. Определение параметров системы.

4.4.5. Сравнение имитационной модели с моделью системы массового обслуживания.

4.4.6. Оценка возможностей системы моделирования.

4.5. Выводы.

Глава 5. Реализация прототипа мигрирующей системы.

5.1. Инструменты разработки

5.2. Функции и структура системы.

5.2.1. Консоль администратора (MSConsole).

5.2.2. Станция (MSStation).

5.2.3. Сервис (MSService).

5.2.4. Клиент (MSClient).

5.3. Исследование прототипа мигрирующей системы.

5.4. Сравнение результатов имитационной модели и прототипа мигрирующей системы.

5.5. Удаленная загрузка и запуск приложений средствами ОС.

5.6. Выводы.

Актуальность. Современные темпы развития корпоративных сетей и Internet требуют создания эффективного и надежного программного обеспечения, удовлетворяющего потребностям огромного числа пользователей. Сложность среды выполнения и отсутствие единой точки администрирования распределенных сетевых приложений привело к появлению программных систем, способных динамически адаптироваться к изменениям в сети, обеспечивая гибкое решение масштабируемости.

Одним из видов таких приложений являются мигрирующие системы. Они могут использоваться в различных прикладных областях для получения гибких, надежных и производительных программных комплексов, выполняющих обслуживание запросов внешних клиентов. Работа мигрирующих систем в первую очередь ориентирована на обслуживающие приложения без сложного внутреннего состояния, такие как Web-серверы со статическими Web-страницами, поисковые системы, Proxy-серверы, файловые серверы, доступные только для чтения. Наличие внутреннего состояния требует от распределенных компонентов мигрирующей системы координировать свои действия при изменении этого состояния для избежания конфликтов и сохранения целостности совместно используемых данных. С учетом этих ограничений мигрирующие системы могут успешно использоваться для серверов баз данных, почтовых серверов, файловых серверов с полным доступом при наличии, например, стандартных средств репликации баз данных.

Мигрирующие системы являются слабоизученной областью в сфере организации распределенных вычислений. Отсутствие теоретической базы и средств оценки характеристик различных архитектурных решений делают проектирование мигрирующих систем нетривиальной задачей. Важность выбора оптимальной архитектуры и определения параметров всех компонентов системы обусловлена сложной зависит мостью характеристик мигрирующей системы от тех решений, которые были приняты на этапах анализа и проектирования. Сложность разработки мигрирующих систем связана с их распределенным характером, работой в гетерогенной динамически изменяющейся среде и необходимостью автономно принимать решения с целью достижения оптимальных характеристик работы. Анализ существующих литературных источников показал, что хорошо изученными являются технологии, используемые при построении мигрирующих систем, такие как мобильные агенты, динамическое перераспределение нагрузки, контекстно-ориентированные приложения. В общем случае представляет интерес возможность построения мигрирующей системы, в которой одновременно использовались бы все перечисленные технологии. Кроме того, в публикациях не рассматриваются модели и методы проектирования мигрирующих систем. Эти положения позволяют сформулировать цель работы следующим образом.

Цель работы. Целью работы является разработка обобщенной архитектуры и алгоритмов функционирования мигрирующих систем, использующих совокупность таких технологий как мобильные агенты, контекстно-ориентированные вычисления и системы перераспределения нагрузки, а также создание моделей и инструментов анализа, составляющих базу процесса проектирования мигрирующих систем. Для достижения поставленной цели в работе решаются следующие задачи:

- описание свойств мигрирующих систем и определение круга задач, для решения которых может использоваться данный класс распределенных приложений;

- разработка обобщенной и двух специализированных архитектур мигрирующих систем и сравнение характеристик, полученных для различных архитектурных решений;

- построение модели мигрирующей системы в рамках теории массового обслуживания, позволяющей исследовать ограниченное число процессов, протекающих в системе;

- построение формальной теоретико-множественно-событийной модели, включающей основные компоненты мигрирующей системы, среду ее выполнения и внешних пользователей, и определение множества событий, происходящих в системе;

- построение методики разработки мигрирующих систем на основе теоретико-множественно-событийных моделей;

- анализ, проектирование и реализация пакета программ для имитационного моделирования мигрирующих систем, учитывающего широкий круг параметров системы и ее окружения;

- проведение серии экспериментов, связанных с анализом и синтезом мигрирующих систем, и сравнение результатов, полученных с использованием теории массового обслуживания и системы имитации; и

- реализация прототипа мигрирующей системы обслуживания и сравнение характеристик прототипа с результатами, полученными для построенных моделей.

Предмет исследования. Объектом исследования являются мигрирующие системы, а предметом - методы анализа, моделирования, проектирования и реализации мигрирующих систем обслуживания.

Методы исследования. Для решения поставленных задач в работе используются методы теории множеств, теории систем массового обслуживания, теории автоматов, теории вероятности, исследования алгоритмов, моделирования, анализа и проектирования распределенных, многозадачных и многопоточных программных систем.

Научная новизна. В работе были получены следующие научные результаты:

- построена полностью децентрализованная обобщенная архитектура мигрирующих систем, отличающаяся тем, что она включает совокупность трех технологий - мобильных агентов, контекстно-ориентированных вычислений и перераспределения нагрузки, применяемых независимо в различных корпоративных системах;

- построена модель системы массового обслуживания, рассматривающая мигрирующую систему как обслуживающую систему, которая изменяет свое состояние под воздействием потоков событий. Модель позволяет уже на этапе проектирования получить такие характеристики системы как абсолютная пропускная способность или среднее время нахождения запроса в системе;

- построена формальная теоретико-множественно-событийная модель, описывающая как контекст выполнения, так и все компоненты мигрирующей системы, их взаимосвязь, события и операции, и позволяющая определять текущее состояние системы в зависимости от ее архитектуры и производимых воздействий;

- разработана методика построения мигрирующих систем на основе теоретико-множественно-событийных моделей, позволяющая выполнять анализ создаваемых распределенных мигрирующих приложений и получать их характеристики.

Достоверность. Достоверность полученных результатов подтверждается совпадением экспериментальных данных, полученных с помощью имитационной модели и разработанного прототипа мигрирующей системы.

Практическая значимость. В результате выполнения данной работы были получены следующие практические результаты:

- разработаны две специализированные архитектуры, дающие готовые проектные решения при реализации распределенных программных комплексов на основе мигрирующих систем, работающих в локальных и глобальных сетях;

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

- написан прототип мигрирующей системы, позволяющий убедиться в корректности построенных моделей и методики, а также демонстрирующий использование методики на примере разработки распределенной системы поиска.

Апробация. Основные результаты работы докладывались на Международных конференциях по мягким вычислениям и измерениям (SCM) в 2002 - 2004 гг.

Публикации. По темам, связанным с проблематикой диссертации, опубликовано 6 печатных работ, включающих 3 статьи и 3 доклада на научно-технических конференциях:

- Фомичев В. С., Холод И. И., Першин А. В., Степанов А. Г. Поток сообщений в системах мобильных агентов // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2002). - СПб., 25 - 27 июня, 2002, СПбГЭ-ТУ.

- Степанов А. Г. Свойства мигрирующих систем // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2003). - СПб., 25 - 27 июня, 2003, СПбГЭТУ.

- Степанов А. Г. Применение моделей массового обслуживания для анализа мигрирующих систем // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2004). - СПб., 17-19 июня, 2004, СПбГЭТУ.

- Степанов А. Г., Фомичев B.C. Имитационная модель мигрирующей системы // Известия СПбГЭТУ «ЛЭТИ». - СПб., 2004.

- Степанов А. Г., Фомичев B.C. Имитация мигрирующих систем обслуживания // Известия вузов. Приборостроение. - СПб., 5, 2005.

- Степанов А. Г., Фомичев B.C. Пакет программ для имитации мигрирующих систем обслуживания // Известия вузов. Приборостроение. - СПб., 7, 2005.

5.6. Выводы

Разработанный прототип мигрирующей системы обслуживания позволяет решить ряд задач, связанных с исследованием систем данного класса:

1. проверить основные алгоритмы работы мигрирующей системы на выбранном языке программирования и оценить возможную трудоемкость построения полнофункциональной системы, пригодной для коммерческого использования;

2. экспериментально проверить соответствие результатов математического и имитационного моделирования, полученные на предыдущих этапах работы, с результатами работы прототипа, а также выбрать набор входных параметров модели таким образом, чтобы они наиболее точно описывали мигрирующую систему и среду ее выполнения;

3. проработать ряд технических вопросов, связанных с реализацией протоколов межсетевого взаимодействия частей мигрирующей системы, удаленной загрузкой и инсталляцией приложений, синхронизацией работы компонентов мигрирующего сервиса при выполнении процедур репликации и дерепликации.

Трудоемкость разработки прототипа равна приблизительно 50 человеко-дней, что составляет около 10-20% от трудоемкости реализации коммерческой версии мигрирующей системы обслуживания, которая обладает необходимыми механизмами безопасности и надежностью, требуемой для использования продукта в крупных локальных и корпоративных сетях.

Заключение

В работе было проведено теоретическое и практическое исследование мигрирующих систем и получены следующие результаты:

1. сформулировано понятие мигрирующей системы, определены ее основные свойства, а также определены области применения распределенных систем данного класса;

2. предложен набор архитектур и варианты построения модулей мигрирующей системы, которые являются готовыми проектными решениями и упрощают процесс разработки специализированных мигрирующих систем;

3. построена модель мигрирующей системы в виде системы массового обслуживания, позволяющая определить ряд динамических характеристик системы, но не учитывающая архитектуру системы и алгоритмы работы ее компонентов;

4. построена формальная теоретико-множественно-событийная модель, описывающая мигрирующую систему как совокупность множеств объектов, внешних и внутренних событий и правил, в соответствии с которыми каждому событию ставится в соответствие некоторая операция над одним или несколькими множествами объектов;

5. представлена методика создания мигрирующих приложений, обеспечивающая простой переход от проектирования к реализации за счет использования теоретико-множественно-событийной модели;

6. написан пакет программ для имитационного моделирования мигрирующих систем, с помощью которого можно на этапе проектирования проверить алгоритмы и оценить характеристики системы для заданной архитектуры и набора основных параметров;

7. реализован прототип мигрирующей системы, демонстрирующий возможности созданной методики проектирования на примере разработки распределенной системы поиска и показывающий адекватность разработанных моделей оригиналу.

1. Abowd G. D., Atkeson С. G., Brotherton J. Investigating the capture, integration and access problem of ubiquitous computing in an educational setting // Proceeding of Human Factors in Computing Systems (СНГ98), ACM Press, Los Angeles, CA, 1998.

2. Agents that move around and think / Toshiba Corporation, 1999, http://www.toshiba.co.jp/cright/index.htm.

3. Ajanta: A mobile agent research project in Java / http://www.cs.umn.edu/ajanta.

4. Anind K., Dey A. K. Understanding and using context // Personal and Ubiquitous Computing, Springer, 5/1, 2001.

5. Baumann J., Hohl F. Mole: Concepts of a mobile agent system. Technical report 1997/15 // Fakultaet Informatik, University of Stuttgart, August 1997.

6. Baumann J., Hohl F., Rothermel K. Mole: Concepts of a mobile agent system // World Wide Web, #3, 1998.

7. Bee-gent: Bonding and Encapsulation Enhancement Agent / Toshiba Corporation, 1999, http://www.toshiba.co.jp/cright/index.htm.

8. Benelli G., Bianchi A., Marti P., Not E., Sennati D. HIPS: Hyper Interaction within the Physical Space // IEEE, Multimedia System'99, Firenze, 1999.

9. Brody А. В., Gottsman E. J. Pocket bargain finder: a handheld device for augmented commerce // First International Symposium on Handheld and Ubiquitous Computing (HUC'99), Karlsruhe, Germany, 1999.

10. Cheverst K., Davies N., Mitchell K., Efstratiou C. Using context as a crystal ball: Rewards and pitfalls // Personal and Ubiquitous Computing, Springer, 5/1,2001.

11. Cluster strategy: High availability and scalability with industry-standard hardware. Microsoft Clustering Service technical articles // Microsoft Corporation, November 1996.

12. Concordia, version 1.1.2 / http://www.meitca.com/hsl/projects/concordia.

13. CORBA facilities: Mobile agent system interoperability facilities submission. MASIF revision / Object Management Group Framingham Corporate Center, March 1998, http://www.omg.com.

14. Dasgupta P. Narasimhan N. E-Commerce: Mobile Agents for Networked Electronic Trading / 1999, http://alpha.ece.ucsb.edu/~pdg/research/papers/ictechtml.

15. Dasgupta P., Narasimhan N. MAgNET: Mobile Agents for Networked Electronic Trading / March 1999, http://alpha.ece.ucsb.edu/~pdg/research/papers/magnethtml/nodel.html.

16. Deploying notes for Windows NT Load Balancing Service. Windows NT 4.0 technical articles // Microsoft Corporation, January 1999.

17. Fabio В., Giovanni C. JADE administrator's guide // CSELT S.p.A., 2000.

18. Fabio В., Giovanni C. JADE programmer's guide // CSELT S.p.A., 2000.

19. Fano A. Shopper's eye: Using location-based filtering for a shopping agent in the physical world // Proceedings of the Second International Conference on Autonomous Agents, Minneapolis, MN, 1998.

20. Fano A. What are a location's "File" and "Edit" menus? // Personal and Ubiquitous Computing, Springer, 5/1, 2001.21 . Foundation for intelligent physical agents / FIPA Organization, 1998 2001, http://www.fipa.org.

21. Glass G. Voyager: The new face of distributed computing // Object Magazine, June 1997.

22. Gray R. S. Agent Tel: A flexible and secure mobile-agent system // Fourth Annual Tcl/Tk Workshop (TCL 96), Monterey, California, July 1996.

23. Gray R. S. Agent Tel: A transportable agent system / Department of Computer Science, Dartmouth College, Hanover, http://www.dartmouth.edu.

24. Gray R. S. Agent Tel: A transportable agent system / Gray Department of Computer Science Dartmouth College, http://www.dartmouth.edu.

25. Gray R. S. Agent Tel: Alpha release 1.1/ Department of Computer Science, Dartmouth College, Hanover, http://www.dartmouth.edu.

26. Gray R. S., Cybenko G. Agent Tel. In mobile agents: Explanations and examples // Manning Publishing, 1997.

27. Green S., Hurst L. Software agents: A review. Technical report // Trinity Collega, Dublin, Ireland, May 1997.

28. Holger P. The Ara platform for mobile agents / October 1997, http://www.uni-kl.de.

29. JATLite: Java Agent Template, Lite / Stanford University, http://java.stanford.edu/processLink/papers/jatl.html.

30. Jazayeri M., Lugmayr W. Gypsy: A component-based mobile agent system. Technical report TUV-1841-99-09 // Distributed Systems Group, Technical University of Vienna, April 1999.

31. Johansen D., Schneider F. В., Renesse R. What TACOMA taught us //Addison Wesley Publishing Company, 1998.

32. Koblick R. Concordia // CACM, March 1999.

33. Laerhoven K., Aidoo K. Teaching context to applications // Personal and Ubiquitous Computing, Springer, 5/1,2001.

34. Lange D. B. Java Aglet application programming interface. White paper, draft 2 / IBM, Tokyo Research Laboratory, February 1997, http://www.trl.ibm.co.jp/aglets.

35. Lange D. В., Oshima M. Programming and deploying Java mobile agents with Aglets. // Addison-Wesley, 1998.

36. Lugmayer W. Gypsy: A component-oriented mobile agent system / Wiena, http://www.infosys.tuwien.ac.at/gypsy.

37. Microsoft Windows NT Load Balancing Service. Windows NT 4.0 technical articles // Microsoft Corporation, January 1999.

38. Microsoft расширяет кластерные возможности Windows NT Server 4.0 Enterprise Edition // Компьютерная Столица, 1999.

39. Minghua H., Ho-fung L. Agents in E-Commerce: State of the art // Knowledge and Information Systems, Springer, 4/3,2002.

40. Mobile agents white paper / General Magic, 1998, http://www.genmagic.com.

41. Mobile Agents: Going beyond the Web. TRYLLIAN ВV. Version 1.0 / May 2000, http://www.tryllian.com.

42. Moran T. P., Palen L., Harrison S. "I'll get that off the audio": A case study of salvaging multimedia-meeting records // Proceeding of Human Factors in Computing Systems (CHI'97), ACM Press, Atlanta, GA, 1997.

43. Nakanishi Y., Tsuji Т., Ohyama M., Hakozaki K. Context aware messaging service: A dynamical messaging delivery using location information and schedule information // Personal and Ubiquitous Computing, Springer, 4/4, 2000.

44. Not E., Petrelli D., Sarini M., Stock O., Strapparava C., Zancanaro M. Hyper navigation in the physical space: Adapting presentations to the user and to the situational context // The New Review of Hypermedia and Multimedia, 1998,4.

45. Nwana H. S. Software agents: An overview // Knowledge Engineering Review, 1996.

46. ObjectSpace overview of Voyager: ObjectSpace's Product Family for State-of-the-Art / Distributed Computing By Graham Glass, 1999, http://www.objectspace.com/voyager.

47. Oshima M., Karjoth G., Ono K. Aglets specification 1.1 draft / IBM, http://www.ibm.co.jp/trl/aglets.

48. Pascoe J. Adding generic contextual capabilities to wearable computers // Proceeding of Second International Symposium on Wearable Computers, 1998.

49. Petrelli D., Not E., Sarini M., Stock O., Strapparava C., Zancanaro M. HyperAudio = Location Awareness + Adaptivity // Extended Abstract CHI'99, Pittsburgh, May 1999.

50. Petrelli D., Not E., Zancanaro M., Strapparava C., Stock O. Modeling and adapting to context // Personal and Ubiquitous Computing, Springer, 5/1,2001.

51. Quest High Availability for Exchange. User Guide // Quest Software Inc., 2005.

52. Salber D., Dey A. K., Abowd G. D. The context toolkit: Aiding the development of context-enabled applications // Proceedings of CHI'99, 1999.

53. Schilit B. N., Golovchinsky G., Price M. N. Beyond paper: Supporting active reading with free form digital ink annotations // Proceeding of Human Factors in Computing Systems (CHI'98), ACM Press, Los Angeles, CA, 1998.

54. Schilit В., Adams N., Want R. Context-aware computing applications // First International Workshop on Mobile Computing Systems and Applications, 1994.

55. Schilit В., Theimer M. Disseminating active map information to mobile hosts // IEEE Network, 8, 1994.

56. Schmidt A. Implicit human computer interaction through context // Proceedings of the 2nd Workshop on Human Computer Interaction with Mobile Devices, Edinburgh, Scotland, 1999.

57. Sommers B. Agents: Not just for Bond anymore // Java World, April 1997.

58. Sundsted T. An introduction to agents // Java World, June 1998.

59. Urnes Т., Hatlen A. S., Johansen R., Myhre 0. Using mobile code to build a smart kitchen // Personal and Ubiquitous Computing, Springer, 4/4,2000.

60. Urnes Т., Hatlen A. S., Malm P. S., Myhre 0. Building distributed context-aware applications // Personal and Ubiquitous Computing, Springer, 5/1, 2001.

61. Venners B. Under the Hood: The architecture of aglets // Java World, April 1997.

62. Windows NT Server Clustering: Frequently asked questions. Microsoft Clustering Service technical articles // Microsoft Corporation, April 1997.

63. Wong D., Paciorek N. Concordia: An infrastructure for collaborating mobile agents / Mobile Agents First International Workshop (MA'97), Berlin, Germany, April 1997.

64. Александров П.С. Введение в общую теорию множеств и функций. М.: ОГИЗ, 1988.

65. Андронов А. М., Копытов Е. А., Гринглаз JI. Я. Теория вероятностей и математическая статистика. СПб.: Питер, 2004.

66. Боггс У., Боггс М. UML и Rational Rose. М.: Лори, 2000.71 . Бруно Ч., Килмартин Г., Толли К. Средства повышения производительности Web-узлов //Сети, 1,2002.

67. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. СПб.: Бином, Невский Диалект, 1998.

68. Буч Г., Рамбо Дж, Джекобсон А. Язык UML. Руководство пользователя: Пер. с англ. М: ДМК, 2000.

69. Вальковский В., Малышкин В. А. Синтез параллельных программ и систем на вычислительных моделях. Новосибирск: Наука, 1988.

70. Вентцель Е.С. Исследование операций: задачи, принципы, методология. 2-е изд. — М.: Наука, 1988.

71. Вересов И., Колушев Ф. Кластеры: суперкомпьютеры на каждый день // Мир Internet, 6-7, 2002.

72. Верещагин Н. К., Шень А. Начала теории множеств. Математическая логика и теория алгоритмов. М.: Изд-во МЦНМО, 1999.

73. Волков И. К., Зуев С. М., Цветкова Г. М. Случайные процессы. М.: Изд-во МГТУ им. Н. Э. Баумана, 1999.

74. Горбатов В. А. Основы дискретной математики. — М.: Высшая школа, 1986.

75. Дегтярев Ю.И. Исследование операций: Учеб. пособие для вузов по специальности АСУ. М.: Высшая школа, 1986.81 . Джекобе Э. В центре внимания Web-ускорение // Сети, 10,2001.

76. Дрейган Р. Будущее программных агентов // PC Magazine, March 1997.

77. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания: Учеб. пособие для вузов. М.: Высшая школа, 1982.

78. Калинина В. Н., Панкин В. Ф. Математическая статистика. М.: Высшая школа, 1998.

79. Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2002.

80. Клейнрок JI. Теория массового обслуживания. М.: Машиностроение, 1979.

81. Клини С. К. Математическая логика. М.: Мир, 1973.

82. Котов В. Е. Сети Петри. М.: Наука, 1984.

83. Краткий курс лекций по математической статистике и теории вероятностей / apol-lyonl986.narod.ru/docs/tvims/np/lekziitv/soderzhanie.htm.

84. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988.

85. Лавров И. А., Максимова JI. JI. Задачи по теории множеств, математической логике и теории алгоритмов. М.: ФИЗМАТЛИТ, 2004.

86. Марков А. А., Нагорный Н. М. Теория алгоритмов. М.: Наука, 1984.

87. Мендельсон Э. Введение в математическую логику. М.: Наука, 1976.

88. Петерсен P. Linux: полное руководство. 3-е изд. К.: Издательская группа BHV, 2000.

89. Питерсон Дж. Теория сетей Петри и моделирование систем. — М.: Мир, 1984.

90. Прохоров Ю. В., Розанов Ю. А. Теория вероятностей. Основные понятия. Предельные теоремы. Случайные процессы. М.: Наука, 1967.

91. Свами А. А., Тхуласирман К. Графы, сети и алгоритмы. М.: Мир, 1984.

92. Степанов А. Г. Свойства мигрирующих систем // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2003). СПб., 25 - 27 июня, 2003, СПбГЭТУ.

93. Судоплатов С. В., Овчинникова Е. В. Математическая логика и теория алгоритмов. Учебник. Новосибирск: Изд-во НГТУ, Инфра-М, 2004.

94. Табке Б. Как работают поисковые системы // 2003, www.searchengines.ru.

95. Темерев А. Контекстно-ориентированные технологии // Мир Internet, 9, 2002.

96. Технологические и методические вопросы разработки имитационных моделей / ДАСИМ, www.ospu.odessa.ua/adss/indru.htm.

97. Тихонов В. Поисковые системы в сети Интернет // 2000, www.searchengines.ru.

98. Фаррелл Р. Способы выравнивания нагрузки // Сети, 1, 2002.

99. Фаулер М., Скотт К. UML в кратком изложении. Применение стандартного языка объектного моделирования. М.: Мир, 1999.

100. Чжоу Т. Системы балансировки нагрузки Web-серверов // Windows 2000 Magazine, 3,2000.

101. Шенфилд Дж. Математическая логика. — М.: Наука, 1975.

102. Якобсон А., Буч Г., Рамбо Дж. Унифицированный процесс разработки программного обеспечения. СПб.: Питер, 2002.Ш