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

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

Антипов Олег Владимирович

МОДЕЛИ И АЛГОРИТМЫ ВЗАИМОДЕЙСТВИЯ ПРИЛОЖЕНИЙ В РАСПРЕДЕЛЁННЫХ СИСТЕМАХ С АРХИТЕКТУРОЙ ПУБЛИКАЦИЯ/ПОДПИСКА

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

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

Рязань 2015

2 2 АПР 2015

005567712

Работа выполнена в ФГБОУ ВПО «Рязанский государственный радиотехнический университет» на кафедре «Вычислительная и прикладная математика».

Научный руководитель: Пылькин Александр Николаевич,

доктор технических наук, профессор, заслуженный работник высшей школы РФ, декан факультета вычислительной техники, заведующий кафедрой «Вычислительная и прикладная математика» ФГБОУ ВПО «Рязанский государственный радиотехнический университет», г. Рязань.

Официальные оппоненты: Малыш Владимир Николаевич,

доктор технических наук, профессор, декан физико-математического факультета, заведующий кафедрой « Электро ни кате ле-коммуникаций и компьютерные технологии ФГБОУ ВПО «Липецкий государственный педагогический университет», г. Липецк;

Саксонов Евгений Александрович,

доктор технических наук, профессор, профессор кафедры «Информационные системы» ФГБОУ ВПО «Институт инновационных технологий и предпринимательства Московского государственного университета технологий и управления имени К.Г. Разумовского», г. Москва. Ведущая организация: ФГБОУ ВПО «Московский государствен-

венный университет печати имени Ивана Федорова», г. Москва.

Защита состоится 27 мая 2015 г. в 12 часов 00 минут на заседании диссертационного совета Д 212.211.01 в ФГБОУ ВПО «Рязанский государственный радиотехнический университет» по адресу: 390005, г. Рязань, ул. Гагарина, 59/1, ауд. 235.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Рязанский государственный радиотехнический университет» и на официальном сайте университета http://www.rsreu.ru.

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

Учёный секретарь диссертационного совета кандидат технических наук, доцент

В.Н. Пржегорлинский

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

Актуальность темы. В архитектуре существующих крупномасштабных распределенных компьютерных систем в настоящее время преобладает синхронная платформа клиент-сервер (например, World Wide Web, Coiba, J2EE, COM+). В системах клиент-сервер существуют две роли: компонент действует как клиент, если он требует данные или функциональные возможности от другого компонента, или он действует как сервер, если отвечает на запрос клиента. Кроме того, клиент блокируется после того, как он отправил запрос, до тех пор, пока не придёт соответствующий ответ. Существуют приложения, которые не могут быть реализованы эффективно при использовании технологии запрос/ответ. Более того, при их реализации, когда информация, предоставляемая одной службой, зависит от информации, поставляемой другой службой, использование этой технологии приводит к решению, которое не масштабируется и предоставляет данные, которые могут быть неточными и неполными. В отличие от этого новая асинхронная платформа Публикация /Подписка непосредственно отражает поведение, свойственное информационно-управляемым приложениям, так как такая коммуникация является косвенной, инициируемой производителями информации. Гибкость механизма выбора уведомлений, используемого потребигелялш, является важнейшим фактором при реализации службы уведомлении таких систем. Использование наиболее избирательного механизма выбора уведомлений по их содержимому в сравнении с выбором на основе канала или выбором на основе темы позволяет повысить эффективность функционирования, гибкость всей системы, и, в целом, облегчает её расширяемость и непрерывное изменение с целью адаптации к изменениям в объединяемых ею приложениях.

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

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

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

Степень её разработанности. В развитие данного направления исследований весомый вклад внесли многие отечественные и зарубежные ученые: C.B. Востокин, В.В. Воеводин, JI.E. Карпов, A.C. Нариньяни, A.A. Цимбал, Э. Таненбаум, Грегор Хоп и другие. Значительных успехов в практической реализации существующих сервисов уведомлений достигли зарубежные ученые, такие как А. Карцанига, Д. Розенблюм, А. Вольф, Дж. Бриццони, Ди Нитго, Е. Трацанелла, Дж. Банавар, Л. Опирчал, Дж. Кугола, А. Фуджетта, Дж. Бэйкон.

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

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

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

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

2. Разработать и исследовать формальную спецификацию этих систем, которая позволила бы определить, что означает для системы передачи сообщений с архитектурой Публикация/Подписка с выбором уведомлений по содержимому «правильность» её функционирования и выполнение требований безопасности и живучести.

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

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

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

6. Провести сравнительный анализ предложенных алгоритмов маршрутизации и получить оценки их основных характеристик.

7. Полученные аналитические результаты сравнить с результатами экспериментов для подтверждения их адекватности.

Научная новизна.

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

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

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

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

Теоретическая н практическая значимость работы. Работа состоит из теоретической и практической частей.

Теоретическая часть представляет формальную спецификацию систем Публикация/Подписка, обобщённую структуру и ряд алгоритмов маршрутизации.

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

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

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

Основные положения, выносимые на защиту.

1. Формальная спецификация поведения системы Публикация/Подписка, основанная на следах - последовательностях пар «состояние-операция» и использующая синтаксис линейной временной логики.

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

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

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

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

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

Реализация и внедренне результатов работы. Диссертация выполнялась в Рязанском государственном радиотехническом университете в рамках: НИР 32-11; НИР 11-12Г; НИР 12-14Г.

Теоретические и практические результаты работы использованы в ОАО «Моринформсистема - Агат - КИП» и НИ 11 «Технософт» в качестве системной организации единого информационного пространства и сетевой инфраструктуры асинхронного взаимодействия гетерогенных приложений, в учебном процессе ФГБОУ ВПО «Рязанский государственный радиотехнический университет», что подтверждается соответствующими актами внедрения.

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

Публикации. По теме диссертации опубликовано 18 печатных работ (6 - без соавторов), из них: 5 статей в журналах, входящих в перечень ВАК; 1 монография; 1 свидетельство о государственной регистрации программы для ЭВМ; 5 тезисов докладов, в том числе, 1 работа, индексированная Scopus.

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

Соответствие паспорту специальности. Содержание диссертации соответствует паспорту специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»: п.З. «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем»; п.9. «Модели, методы, алгоритмы и программная инфраструктура для организации глобально распределённой обработки данных».

Структура и объём диссертации. Диссертация состоит из введения, пяти глав, заключения, библиографического списка 109 наименований и 7 приложений; содержит 255 страниц, в том числе, 223 страницы основного текста, 72 рисунка и б таблиц

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

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

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

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

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

Вторая глава посвящена разработке формальной спецификации систем Публикация/Подписка. Концептуально эту систему можно рассматривать как «черный ящик» с определенным интерфейсом (рисунок 1).

Поведение системы описывается с помощью набора следов - последовательности чередующихся состояний и операций интерфейса ор„ (таблица 1):

о-=$ьорь52, ор2, 5з, ... (1)

След в этой модели представляет временную шкалу как упорядоченную связанную последовательность состояний и операций, например, след

СГ, = 5ь ХиЬ{Х, Е), 52, риЪ{\\ л), 5з, поЧ/у{Х, /?),... (2)

описывает процесс, когда в начальном состоянии клиент X подписывается на фильтр Г<\ затем в состоянии ,у2 клиент У издает уведомление и, что приводит к состоянию л3, в котором клиент X получает уведомление п и так далее.

Таблица 1

.тЬ(Х, Г) Клиент X подписывается на фильтр F

итиЬ(Х, /') Клиент X аннулирует подписку на фильтр F

иоп/\{Х, и) Клиенту X посылается уведомление п

риЫХ, п) Клиент X публикует уведомление и

Инаеракривкое еззимсдайстаяе

Ф О

/

/ по(1гу(п)

/ 8аЫГ) / оп&аЫП

Клиенты

г

А

риЬ{п)

Система

Рисунок 1 - Представление системы: «чёрный ящик»

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

Определение 1. Система Публикация/Подписка - это такая система, которая использует только следы, удовлетворяющие требованиям:

• безопасности:

п[ЛЬ///у(Г, п) => [оп ХоП/уО', и)] л [ЗХ. п&Рх\ л [ ЭFeSV. яеЛ'г(/')]]; (3)

• живучести:

□15(1/)(}', Р) => [0о(Ри6(Л; п)лпеЩ/'') =>0ХоИ/у(У, п))^ [01!жиЪ{У, /?)]]. (4)

Это означает, что ни одно ошибочное уведомление не будет доставлено клиенту, и что, если клиент осуществил подписку, в конце концов, все соответствующие уведомления будут ему доставлены.

На основе введенной спецификации рассмотрена модель системы с асинхронным способом передачи сообщений (рисунок 2), где топология взаимосвязей брокеров представлена как связный неориентированный ациклический граф О = (V, Е) с множеством вершин V- {В\,..., В„), соответствующих брокерам, и множеством рёбер Е с {(Д , В]), 1</<у <«}, представляющих двунаправленные связи между ними, определена функция направленности связи е{В, , Д,). Поведение каждого брокера В определяется его таблицей

маршрутизации Тв, содержащей набор маршрутизационных записей (F, U), где F - фильтр; Г/е Агв u LB- точка назначения. Поведение системы определяется текущей конфигурацией маршрутизации, включая граф системы (описывающий её структуру) и все таблицы маршрутизации (описывающие её поведение), состоящей из удаленной конфигурации маршрутизации (все записи, пунктом назначения которых является соседний брокер) и локальной конфигурации маршрутизации (все записи, пунктом назначения которых является локальный клиент брокера).

На основе рассмотренной модели и формального описания множества уведомлений, инициируемых каждым брокером согласно текущей конфигурации маршрутизации, предложен алгоритм перенаправления уведомлений, основанный на таблице маршрутизации брокера (рисунок 3). Входящие сообщения обрабатываются последовательно в порядке FIFO независимо от отправителя. Если брокер получает сообщение pub(n) от одного из своих клиентов, то он посылает иой-jy{n) сообщение всем своим клиентам, которые есть в ¡'¡¡'(п) -его множестве заинтересованных клиентов, и forward(ii) сообщение всем своим соседним брокерам, которые есть в соответствующем множестве F"(n). Если брокер получает for-магсЦп) сообщение от одного in своих соседей U, то он посылает notifyQi) сообщение всем своим клиентам, котрые есть в (/;), и for\vard(n) сообщение всем своим соседям, которые есть в

Брокеры распространяют отправки и приёма сообщений

Рисунок 2 - Распределенная система Публикация/Подписка

program begin

loop

JJi •:— ii'iill for (.'■<<: ¿if; i

mim

end end

proceduro begin if !

then

f i Г^

li

Рисунок 3 — Алгоритм статического перенаправления уведомлений

уведомления друг другу с помощью /отагс1(п). Брокер В получает от клиента риЬ{п) и посылает ему пои/у(п) сообщения. Брокеры функционируют на основе своей таблицы маршрутизации. Например, в ситуации, изображенной на рисунке 4, брокер В\ направляет уведомление, полученное от X], локальному клиенту Х2 и соседу В2. Введенные понятия конфигурации маршрутизации и перенаправления уведомлений на основе таблиц маршрутизации брокера позволили определить условия

корректного поведения как статических, так и динамических систем Публшсация/Подписка.

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

пе Г, п еГ4 л «Г,

г,'!»)*!*,)

Рисунок 4 - Диаграмма перенаправления уведомлений

Определение 2. Маршрутная конфигурация допустима, если выполняются требования удалённой и локальной допустимости:

е(В1,В ) еЕ =>ув ({В,}) э г/в в_ -удалённая допустимость

У I

(5)

формализует требования, предъявляемые к множеству уведомлений, направляемых соседним брокерам: ув ({В;

ву

-локальная допустимость (6)

формализует требования к множеству уведомлений, направляемых локальным клиентам: ({Г}); где т]в в - множество всех уведомлений, которые

интересны хотя бы одному клиенту любого соседнего брокера; - множество уведомлений, соответствующих фильтру /•'; 5У - множество активных подписок локального клиента Г.

Диаграммы удалённой и локальной допустимости маршрутной конфигурации приведены на рисунках 5 и 6.

(За. г,

в В!. В! '

Рисунок 5 - Диаграмма удалённой допустимости маршрутной конфигурации

Рисунок 6 - Диаграмма локальной допустимости маршрутной конфигурации

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

Теорема 1. Если допустимая маршрутная конфигу рация используется в сочетании с алгоритмом статического перенаправления уведомлений (рисунок 3), то система Публикация/Подписка удовлетворяет требованиям безопасности и живучести, сформулированным в определении 1.

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

ческого перенаправления уведомлений (рисунок 3) для удовлетворения требованиям безопасности и живучести, сформулированным в определении 1.

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

Определение 3. Маршрутная конфигурация слабо допустима, если выполняются требования слабо удалённой допустимости и локальной допустимости:

е(Ви В ) е Е =>ув ({В }) ^эг]в в -слабая удалённая допустимость, (7) ' J J' >

У £ => Уд^ ({У}) = ^(Л - локачьная допустимость, (8)

где Лв .,в{ 1в> Ь = N(!Г) ; ^Л' - подмножество

всех активных подписок клиента X, чей процесс обновления завершился.

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

Теорема 3. Если маршрутная конфигурация слабо допустима, и каждый процесс обновления заканчивается, то система Публикация/Подписка удовлетворяет требованиям безопасности и живучести, сформулированным в определении 1. Доказательство следует из приведённых в работе лемм. Поскольку введенная спецификация основывается на предположении, что либо ни одна ошибка не появится, либо все ошибки могут быть маскированы, причем первое довольно нереалистично, а второе практически невозможно реализовать, то в работе рассматривается понятие самостабилизирующейся системы Публикация/Подписка, которая может восстановиться от произвольных сбоев в течении конечного времени.

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

Определение 5. Система Публикация/Подписка является самостабилизирующейся, если все её следы удовлетворяют требованиям:

• возможной безопасности:

Оа[Ыоф(Х,п) => [оп -,МоИ/у(У, и)] а [ЗХ. п6 Рх] л [З/^еЗУ. и£#(/=)]]; (9)

• живучести:

□ [£м£(У,/0=> [0а(РиЬ(Х,п)лпеЩК)=>0МоИ]уОг,п))] V [0(10)

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

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

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

Дано определение системы публикации/подписки с рекламными объявлениями.

Определение 6. Система Публикация/Подписка с рекламными объявлениями является самостабилизирующейся, если показывает только следы, удовлетворяющие требованиям:

• безопасности:

u[{Notify{Y,n)=> [оa-,Notify(Y,ri)] л [ЭХ /?<Е/^| л[ 3 .FESy. п£ А^/7)])

л (РиЬ(Х, п) л [V F&AX. <£N{F)] => [□ Notify^'.,«)])]; (11)

• живучести:

□ [[[^6(7, F) a 0Adv(Z, G)] v [Ad\>(Z, G) л 0Suh(Y, /•)]] => [On (Pub(X, n) лие N(F) ГЛ N(G) => 0 Not if у {Y, и))]

V [0Unsub(Y, /0] V [QUnacMZ, G)]],' (12)

где adv(X, /') - операция вьшуска рекламного объявления клиентомX с фильтром F и предикатом по следам AdvQi, /-); wiadv(X, F) - операщш отмены рекламного объявления клиентом А' с фильтром F и предикатом по следам Unad\>(X, F).

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

Формализация конфигурации маршрутизации введена на основе поняли допустимой маршрутной конфигурации для статических систем и слабо допустимой конфигу рации маршрутизации для динамических систем. Предлагаемая структура определяет общую стратегию передачи сообщений в системах публикации/подписки и позволяет реализовывать на её основе конкретные алгоритмы маршрутизации посредством настройки в реализуемых экземплярах алгоритма работы управляющих сообщений. Конкретный алгоритм маршрутизации настраивает работу- управляющих сообщений типа admin с помощью определенной реализации процедуры администрирования - administer. Предложен универсальный критерий корректности, позволяющий определять допустимые алгоритмы маршрутизации, приводящие к корректному поведению системы.

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

Для связи между брокерами используются сообщения fonvard(n) и ad-min(S, II), где S, U - множества фильтров, элементы которых интерпретируются как подписка и отмена подписки.

Процедура administer вызывается брокером В при получении сообщения admin от соседа или сообщений siib/imsub от клиента:

program

begin

Шнв&ге Та loop

m u-'.ut fw and return тл

if m is ''fmvorii-ji)" w *ytib(rt)" mesmne thtm

admin Mf-isanfisim)

tl end «ml

procedure я»)

begin

Sf in i* f:>:rm bmit t I ' then

«

if fit t fV fmm iikvi X then

-M «■■■ s&lalKsrtX.fFM)

«

If «а I» *«e«ai<l1')* vmoitft fivm ciimlX thea M«SWaWwiirfX.». {?•'})

fl

- сообщение admin брокера U инищцфует вызов процедуры administer(f/, S,U);

- сообщения sub(F)/imsttb(F) клиента X инициируют вызов adminis-ter(X, {F}, 0) и administertV, 0, {F}) соответственно.

Процедура administer возвращает сформированное множество Ai троек (Я, S, 11), и каждому соседу В, кроме S, направляется сообщение admin UJ, где 8Л и 11А -производные всех кортежей относительно соседей.

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

ГогаИ Н <г- Л1;,- \ (,*■>'}

»Л >■•■ {8 !

«пй ст!

Рисунок 7 - Обобщённый алгоритм маршрутизации

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

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

Основная идея маршрутизации на основе идентичности фильтров заключается в том, что, если множество уведомлений, которые один брокер В! направляет другому брокеру Вр соответствует нескольким маршрутам (/% Щ в таблице 'Гщ маршрутизации первого брокера Д, то один из этих маршрутов достаточен. Этот фажт используется в алгоритме маршрутизации во избежание си-

сгематического появления лишних маршрутов и ненужных отправок подписок и их отмен. Примеры работы алгоритма при обработке новой подписки от соседа/брокера и от клиента показаны на рисунках 8 и 9.

©

1

3. adtnfa({F>,e)

l. siîbiFi

3. «1тЦ(Г),е) --( В,

<F>S)

2.-е- {F,S)

Г s F

D'niF) \ [■?} - {[h, j5;j} OUF) \ {5} = {*}

Рисунок 8 - Идентичность Рисунок 9 - Идентичность

фильтров. Новая подписка от соседа фильтров. Новая подписка от клиента Фильтры F и G являются идентичными, обозначается как F=G, если множества соответствующих им уведомлений N{F) = N(G). DrB (F) - множество всех соседей Я брокера В, для которых в его таблице Тв не существует ни одного маршрута (G, D), в котором бы G было идентично FuD отлично от Я.

Маршрутизация на основе покрытия фильтров. Основная идея «покрытия»: подписка не отправляется соседу, если этому соседу была направлена не аннулированная подписка, покрывающая первую. При получении подписки брокер удаляет все маршруты, чьи фильтры охватываются новой подпиской и которые относятся к тому же пункту назначения, с целью избавиться от устаревших маршрутов. На рисунках 10 и 11 приведены примеры обработки новой подписки от соседа и от клиента. Такой подход используется в алгоритмах маршрутизации во избежание систематического появления лишних маршрутов, приводящих к ненужным отправкам подписок и их отмен. Более сложной стороной этого алгоритма является процедура отмены подписки. Этот случай, как и сам алгоритм с доказательством его корректности, подробно рассматривается в полном тексте диссертации.

Фильтр F покрывает (охватывает) фильтр G, обозначается как

F Э G, тогда и только тогда, когда N(F) э Ar(G), поэтому маршрут G становится устаревшим Dg(F) - множество всех соседей Я, для которых в таблице брокера В не существует ни одного маршрута (G, D), где G покрывает F и D отличен от Я. Св (F, D) - множество, включающее все маршруты в таблице маршрутизации брокера В, охваченные фильтром F и по направлению к заданному пункту назначения D.

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

13

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

I жЬтя({Р}.

\С=.{К5)

5. ж!тт!{К},Й

РЗО

5. «аЦР)

{С": В,)

Л

Сб(Р,в)« {((7,5)} Рисунок 10 - Покрытие фильтров. Новая подписка от соседа

0%т\ - (В:,}

Рисунок 11 - Покрытие фильтров. Новая подписка от клиента

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

Фильтр Р является слиянием/объединением множества фильтров

{/^ь ...,У7),'}, обозначается как /•'Э {1<\,....тогда и только тогда, когда Л'(/*') э (V, Лг(7'|)). В"'(К) - множество всех соседей Н, для которых в таблице брокера В не существует ни одного маршрута {О, Д), где О является строгим покрытием ЕпО отличен отН.

Рассмотрено использование в предложенных алгоритмах рекламных объявлений, которые клиенты вводят для рекламы своего намерения опубликовать определенные виды уведомлений, и только те уведомления, которые соответствуют активному объявлению, будут доставлены заинтересованным потребителям, так как достаточно отправить подписку только в те подсети, где изданы соответствующие объявления. В этом случае брокер управляет двумя маршрутными таблицами: 7'/ - таблицей на основе подписок (ранее Тв) для маршрутизации уведомлений от производителей к потребителям; Тв - таблицей на основе объявлений для маршрутизации подписок и их отмен от заинтересованных потребителей к производителям. Уведомление п направляется только в пункт

назначения Д если существует маршрут (Г), Р)е Тв с пеА'(Р). Подписка (отмена подписки) F направляется только соседу Н, если существует маршрут (Я, в)еТ^ и МТ') П Л'((7) ф 0.

Для использования рекламных объявлений в алгоритм маршрутизации вводятся дополнительные сообщения и процедуры. Новые сообщения: ад\> и

unadv - для новых и отмененных объявлений. Две категории административных сообщений: admins и adminА - относящиеся к подпискам и объявлениям. Два типа процедур администрирования: administers и administerA - в соответствии с получаемыми сообщениями sub/unsub и advhmadv.

t шые>

ir;i{t\c)

»({О}, ¡iiii

й 5 {ГМ}

"у

а-с}

i>gi«)\{S} ~ {В-,./!;,} \ {i?} « {lh, fk}, h - 1

Рисунок 13 - Слияние маршрутов. Отправка отмененного слияния

Рисунок 12 - Слияние маршрутов.

Отправка нового слияния Рассмотрена возможность расширения предложенных алгоритмов, чтобы они отвечали требованиям самостабилизирующихся систем при наличии случайных неустойчивых отказов. В работе рассматривается возможность достижения отказоустойчивости системы в смысле её самостабилизации, поэтому была расширена структура алгоритмов маршрутизации для удовлетворения требованиям возможной безопасности и живучести (определение 5). Для реализации таких алгоритмов использовалась концепция аренды подписки. Такой подход не только позволяет системам публикации/подписки восстанавливаться после внутренних сбоев, но также и после внешних отказов, связанных с клиентами. В этом случае подписки клиентов сдаются в аренду, и д ля того, чтобы поддерживать подписку д ля фильтра клиент должен регулярно продлевать её аренду путем «повторной подписки», что осуществляется таким же образом, что и подписка: отправляя я!Ь(Р) брокеру. Брокеры управляют актуальностью маршрутов: в таблице маршрутов каждый брокер хранит срок прекращения аренды для каждой загаси. Продление аренды, вдемпотенгная вставка маршрутов, обновляет этуг временную метку. Брокеры периодически проверяют свои таблицы и удаляют записи с истекшим сроком аренды, что можно сделать путем запуска параллельной задачи по отношению к процедуре маршрутизации. Рассмотрены условия выбора и прекращения срока аренды.

Рассмотрен вопрос соотношения введенных временных показателей: а0 = /0 + d■ дтш - лучший случай задержки; (13)

а, - [\ + d ■ 5тах - худший случай задержки; (14)

л> р > d (8тах - 8тг„) - срок аренды; (15)

АТ = Зтах + d (¿тах - 8тШ) + п-полное время стабилизации, (16) где /¡) - начало аренды; ^ = ?0 + Р - момент времени для продления аренды; р -период обновления - период времени, по истечении которого клиенты инициируют продление аренды; 5— задержка связи — период времени, который занимает процесс установления связи при обработке и отправки сообщения в диапазоне 8тш и бпшх\ d-диаметр сети - длина самого продолжительного маршрута.

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

Реализация систем обмена сообщениями на основе архитектуры Публикация/Подписка, являющаяся практической частью диссертации, представлена в четвертой главе. Приведены примеры трёх событийно-управляемых приложений, где использована служба уведомлений Rebeca и предложенные алгоритмы маршрутизации. Использование в качестве единой среды для анализа и сравнения алгоритмов маршрутизации сервиса Rebeca обосновано тем, что эта служба полагается на разработанную обобщённую структуру фильтрации, позволяет добавлять новые алгоритмы в общую схему маршрутизации, предоставляет возможность сравнения этих алгоритмов в единой унифицированной среде, и, следовательно, может быть использована для оценки представленных положений. Кроме того, инфраструктура сервиса Rebeca предоставляет базовую поддержку воспроизведения прошедших событий и фабрики сервисов. Необходимость использования этих концепций стала очевидной во время реализации приложения торговли акциями, использующего журналы и фабрики.

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

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

Самообновляющиеся веб-страницы. Пои реализации самообновляющихся веб-страниц рассмотрено два аспекта. Во-первых, при возникновении конкретных уведомлений должен обновляться контент статических веб-страниц, и. во-вторых, необходимо использовать уведомления, чтобы инициировать v клиентов обновление отображаемых ими страниц. Эти две части названы серверной и клиентской. На серверной части статические веб-страницы обновляются при возникновении конкретных событий, например, страница, контент которой зависит от текущей цены акции, должна обновляться при изменении этой цены. Компонент, отвечающий за обновление веб-страниц, подписывается на уведомления, связанные с этими страницами, и обновляет их с приходом данного уведомления. Обновление страниц на веб-сервере не означает их обновления в браузере веб-клиента для эффективного обновления отображаемой страницы используются специальные механизмы уведомления веб-клиента об изменениях, позволяющие клиенту всегда отображать текущую версию: Pull — клиент периодически посылает запросы для обновления текущей веб-страницы; Push — клиент

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

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

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

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

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

На рисунке 15 представлена структура ВМО. Определены фазы ее жизненного цикча и рассмотрены наиболее важные: фаза Формирования FtPh и фаза Функционирования OptPh, которые требуют организации сетевой инфраструктуры единого информационного пространства, где можно достаточно эффективно использовать разработанные алгоритмы маршрутизации. Для формализации процесса формирования и функционирования ВМО. предложено использовать мето-

is".'«

Время

Рисунок 14 - График, самообновляющийся в режиме реального времени

дологию мультиагентных систем. Разработан сценарий функционирования муль-тиагентной системы моделирования рынка платных медицинских услуг с определением типов используемых агентов - распределённых программных приложений, взаимодействие которых осуществляется на основе инфраструктуры сервиса Rebeca с использованием предложенных алгоритмов маршрутизации (программный продукт зарегистрирован как «Программа взаимодействия компонентов виртуапьной организации на основе парадигмы Публикация/Подписка»),

В пятой главе приведена оценка разработанных алгоритмов маршрутизации, исследованы их основные характеристики: размер таблиц маршрутизации, сложность фильтров, продвигающих уведомления, эффект местоположения потребителей, «несовершенное» слияние фильтров. Эксперименты, основанные на рабочем прототипе (службе уведомлений Rebeca), позволившем осуществить корректное сравнение алгоритмов, проводились в рамках информационной системы по обороту ценных бумаг. Предложен простой, но эффективный сценарий исследования, в котором варьируются определенные основные параметры, например, количество активных подписок х, а остальные параметры остаются фиксированными (таблица 2). Учитывая существующий опыт исследования подобных систем, использовалась иерархическая, симметричная и ациклическая брокерская топология. Выделены брокеры, имеющие и не имеющие локальных клиентов: локальные брокеры и маршрутизаторы Топология имеет 5 уровней брокеров (40 маршрутизаторов и 67 локальных брокеров). Начиная с корневого маршрутизатора, каждый маршрутизатор, кроме оконечных, подключен к трём другим низшего уровня. К каждому такому маршрутизатору подключается отдельный локальный брокер, а к каждому оконечному маршрутизатору подключаются два локальных брокера. На рисунке 16 показана топология такого же типа, но с 4 уровнями, где кружки обозначают маршрутизаторы, а квадратики -локальных брокеров. Рассмотрены наиболее важные характеристики потребителей (их количество; количество, тип и распределение подписок; принадлежность подписок потребителям; принадлежность потребителей брокерам; соотношение подписок и отказов) и производителей (их количество; количество, тип и распределение объявлений; принадлежность объявлений производителям; принадлежность производителей брокерам).

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

Рисунок 15 - Структура ВМО (СПД - система передачи данных)

и в

Таблица 2 - Параметры настройки

Количество потребителей 1 -200

Количество подписок на одного потребителя 10

Количество фондов т 1000

Количество источников уведомлений 1

Количество маршрутизаторов 40

Количество локальных брокеров 67

Количество соседних брокеров МБ фиксировано

Количество уровней иерархии 5

Распределение клиентов по брокерам случайное

Распределение фондов по клиентам случайное

Рисунок 16 - Брокерская топология с 4 уровнями

Для простой маршрутизации количество удаленных маршрутов 21Я | линейно возрастает с числом активных подписок х и числом брокеров V: 2 | 7? | = (| V | -1) • х. При использовании объявлений количество удаленных маршрутов вычисляется по формуле 21 Л | = Рау;, • х. где - средняя длина пути от

потребителя к источнику уведомлений. Для рассмотренной топологии с источником в корневом маршрутизаторе = (54 ■ 4 + 9 • 3 + 3 • 2 +1-1 )/67 = 3,73 минимальна.

Использование объявлений уменьшает 2 | Я | в (| V | -1 = 28,4 раза и не зависит от числа активных подписок

Использование алгоритма маршрутизации на основе идентичности фильтров существенно сокращает количество маршрутов. Размер таблицы маршрутизации брокера В ограничен величиной т- \ Nв |. где т - количество фондов; Ад- количество соседей В. В исследуемом сценарии 21 Л | для большого количества подписок стремится к числу 212,000. Использование объявлений ещё больше уменьшает 2 | Я |. Коэффициент, на который использование объявлений уменьшает 21 Л |, зависит от числа заявленных подписок и приближенно равен (\У\- 1)/Р = 28,4

для малого числа подписок, но резко уменьшается для большого их числа, и, наконец, стремится к 2, что означает минимальное улучшение на 50 %.

Для исследования и сравнения поведения маршрутизации на основе покрытия и слияния фильтров использовался более интересный для практики сценарий подписок на интервал котировок: акция л цена е [50-/,, 50 +1-, ],

где ¡2 е [0, 50] выбирались случайным образом, который показал, что слияние, по сути, улучшает масштабируемость системы. На рисунке 17 показаны результирующие кривые, иллюстрирующие эффект от слияния фильтров. Для маршрутизации на основе слияния фильтров количество всех удаленных маршрутов равно К | = У | Ыв |= 2-1Е [= 2- ([ V | -1).

ВнУ

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

ееТ^) Вч& ВеУ

= 2-\Е\-\Г\ + 1 = 2-т-\)-\У\ + \=\У\-\.

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

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

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

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

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

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

700000

еооооо

1 мсоос

3

| 400000'

| 300000

| гооооо

2 1

100000-11

о-г о

Рисунок 17 - Сравнение маршрута- Рисунок 18 - Относительное влияние заций на основе покрытия ' использования объявлений

и слияния фильтров

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

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

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

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

ЗАКЛЮЧЕНИЕ

В заключении приведены основные научные выводы и практические результаты диссертационной работы.

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых журналах из списка ВАК РФ

1. Анпшов, О.В. Интеграция распределённых программных приложений на основе маршрутизации по содержимому сообщений / В.А. Антипов, О.В. Ангипов,

A.Н. Пылъкин // Вес-шик РГРТУ. - 2014. - № 1 (47). - С. 75 - 83.

2.Антипов, О.В. Обобщенная структура алгоритмов маршрутизации на основе содержимого сообщений / В.А. Антипов, О.В. Анпшов, А.Н. Пылькин // Вестник РГРТУ. - 2014. - № 2 (48). - С. 76 - 82.

3. Антипов, О.В. Сетевая инфраструктура единого информационного пространства виртуальных медицинских организаций / В.А. Анпшов, О.В. Анпшов, А.П. Чехов // Биомедицинская радиоэлектроника. - 2014. - №7. - С. 73 - 81.

4. Анпшов, О.В. Формирование медицинской виртуальной организации /

B.А. Анпшов, О.В. Анпшов, О.М. Богомолов, Д.А. Кутаков // Биомедицинская радиоэлектроника. - 2013. - №7. - С. 70 - 77.

5. Антипов, О.В. Построение телемедицинской системы на основе коммуникационной парадигмы Публикация/Подписка / В.А. Анпшов, О.В. Анпшов, А.П. Чехов // Биомедицинская радиоэлектроника - 2012. - № 7. - С. 64 - 69.

Публикации в материалах меяздународных конференций, индексированные Scopus

6. Antipov, O.V. Dynamic Publish/Subscribe Systems / V.A. Antipov, O.V. Antipov, A.N. Pilkin // 2014 international conference on computer technologies in physical and engineering applications. - SPb., 2014. - P. 11.

Монография

7. Антипов, О.В. Глава 3. Интеграция распределенных программных приложений на основе коммуникационной парадигмы Публикация/Подписка / В.А. Ангипов, О.В. Аншпов, А.Н. Пылькин // Математические и компьютерные методы в технических, гуманитарных и общественных шуках: коллективная монография. - Выл 3 - Пенза; Москва: Приволжский Дом знаний; Московский университет им С.Ю. Вште, 2013. - С. 36 - 67.

Публикации в других изданиях

8. Анпшов, О.В. Алгоритмы маршрутизации на основе содержимого сообщения / О.В. Анпшов // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник научных трудов. -Рязань: РГРТУ, 2014. - С. 14-25.

9. Анпшов, О.В. Самостабилизируюшаяся система пубтжацт/подписки / О.В. Антипов // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник тучных трудов. -Рязань: РГРТУ, 2013. - С. 135 -140.

10. Антипов, О.В. Асинхронная программная платформа для распределенной телемедицинской системы / О.В. Анпшов // Биотехнические, медицинские и экологические системы и комплексы. Биомедсистемы - 2012: Материалы XXV Всероссийской научно-техшмеской конференции студентов, молодых ученых и специалистов. - Рязань: РГРТУ, 2012. - С. 202 - 204.

11. Антипода, О.В. Анализ и выбор метода маршрутизации сообщений в МОМ / О.В. Антипов // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Материалы 17-й Международной научно-технической конференции. - Ч. 1. -Рязань: РГРТУ, 2012. - С. 25 - 27.

12. Ангипов, О.В. Модель взаимодействия / В .А Лг пилон, О.В. Антипов, АП Чехов // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник шучныхтрудов. -Рязань: РГРТУ, 2012. -С. 14 -19.

13. Антипов, О.В. Асинхронная платформа распределенных информационно-управляемых приложений на основе коммуникационной парадигмы Публикация/Подписка / О.В. Антипов // Новые информационные технологии в научных исследованиях: Материалы XVI Всероссийской научно-технической конференции студентов, молодых ученых и специалистов, посвященной празднованию юбилея

РГРТУ.-Рязань: РГРТУ, 2011.-С. 128-130.

14. Ангипов, О.В. Формальная спецификация систем Публикация/Подписка / ВА. Антипов, О.В. Анпшов, АН Пылькин // Программные информационные системы-Межвузовский сборник научных трудов. - Рязань: РГРТУ, 2011. - С. 89 - 95.

15. Антипов, О.В. Выбор механизма уведомления в распределенных системах публикации/подписки / О.В. Антипов, А.Н. Пылькин // Математическое и программное обеспечение вычислительных систем: Межвузовский сборшпс научных трудов -Рязань: РГРТУ,2011.-С. 187- 198.

16. Ашипов, О.В. Разработка архитектуры мультимедавшой библиотеки / О.В. Анпшов // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник научтгых трудов. - М.: Горячая линия - Телеком, 2009. - С. 104

17. Антипов, О.В. Мультиагеншые системы / О.В. Аптипов, О.М. Богомолов // Программное обеспечение вычислительных и информационных систем' Тезисы докладов 55-й СНТК РГРТУ. - Рязань: РГРТУ, 2008. - С. 32 - 33.

Свидетельство о регистрации программы для ЭВМ

18. Антипов, О.В. Программа взаимодействия компонентов виртуальной организации па основе парадигмы Публикация/Подписка / О.В. Антипов А Н Пылькин // Программа для ЭВМ№ 2014661095. - 2014.

Личный вклад автора. В работах [1, 6-7, 12-14] предложены формальная спецификация и модели систем Публикация/Подписка, в работах [2, 8,11] - обобщенная структура и алгоритмы маршрутизации на основе содержимого сообщений, в работах [3-5, 9-10,15-18] - возможные реализации предложенных моделей и алгоритмов.

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

Антипов Олег Владимирович

Модели н алгоритмы взаимодействия приложений в распределённых системах с архитектурой Публикация/Подписка

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 25.03.2015. Формат бумаги 60x84 1/16. Бумага офсетная. Печать трафаретная. Усл. печ. л. 1,0 Тираж 100 экз. Заказ 1761. Рязанский государственный радиотехнический университет. 390005, г. Рязань, ул. Гагарина, 59/1.

Отпечатано в НПЦ «Информационные технологии». 390035, г. Рязань, ул. Островского, 21/1. Тел.:(4912) 98-69-84.