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

005009312

Панкратов Юрий Владимирович

//

АНАЛИЗ И РАЗРАБОТКА АЛГОРИТМОВ УПРАВЛЕНИЯ АДРЕСАЦИЕЙ В БОЛЬШИХ СЕТЯХ

Специальность 05.13.01 - "Системный анализ, управление и обработка информации (в науке и промышленности)" по техническим наукам

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

2 оез тг

Нижний Новгород, 2012 г.

005009312

Работа выполнена на кафедре «Теория Цепей и Телекоммуникации» Нижегородского государственного технического университета им. P.E. Алексеева.

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

доктор технических наук, профессор Крылов Владимир Владимирович

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

доктор технических наук, доцент, Хранилов Валерий Павлович

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

Ведущая организация:

ФГОБУ ВПО «Московский технический университет связи и информатики»

Защита диссертации состоится «16» февраля 2012 г. в {3 часов в аудитории 425$ на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева

Автореферат разослан «16» января 2012 года.

Ученый секретарь

диссертационного совета

A.C. Суркова

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

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

Актуальность работы. Любое устройство, подключенное к сети Интернет, идентифицируется уникальным сетевым адресом, представляющим собой 32 или 128-битное двоичное число, традиционно записываемое в виде последовательности десятичных или шестнадцатеричных чисел для различных версий сетевого адреса соответственно. Несмотря на то, что маршрутизация данных в Интернете осуществляется на основе сетевых адресов устройств, для человека гораздо легче запомнить буквенное, часто осмысленное имя, чем набор цифр сетевого адреса. Доменные имена играют важную роль в функционировании современного Интернета, так как поиск любого сетевого устройства, подключенного к сети Интернет, обычного начинается с его имени. При этом сами доменные имена хранятся в распределенной базе данных, называемой DNS (Domain Name System — система доменных имён). Таким образом, можно сказать, что система доменных имён участвует в управлении адресацией сетевых устройств и маршрутизации сетевого трафика.

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

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

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

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

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

Задачи работы. Для достижения поставленной цели в ходе выполнения диссертационной работы решались следующие основные задачи:

1. Исследование и анализ существующих иерархических и неиерархических архитектур систем разрешения имён.

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

3. Разработка теоретической модели относительно задачи построения децентрализованной системы преобразования имён. Теоретическое исследование свойств такой системы на основе построенной модели.

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

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

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

4

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

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

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

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

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

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

Результаты работы легли в основу вклада «Гетерархическая архитектура безопасности для распределенных сервисных сетей», направленного в Международный союз электросвязи (МСЭ-Т) от лица Министерства связи и массовых коммуникаций Российской Федерации. В августе 2011 года вклад получил номер ТЭ2026 на встрече Исследовательской Комиссии 17 МСЭ-Т.

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

рамках проекта «Cognitive Internet», посвященного проектированию архитектур компьютерных сетей.

Кроме того, полученные в ходе работы результаты были внедрены в учебный процесс НГТУ им. Р.Е. Алексеева по дисциплине «Основы построения телекоммуникационных систем и сетей» в виде курса лекций.

Апробация работы. Материалы диссертационной работы докладывались и обсуждались на 3-х международных научно-технических конференциях «Информационные системы и технологии» (Нижний Новгород, НГТУ им. Р.Е. Алексеева, 2009-2011 гг.), на международной конференции «Будущее технической науки» (Нижний Новгород, 2011) и на научной конференции «Сессия молодых ученых» (Нижний Новгород, 2009).

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

Публикации. Основное содержание диссертации опубликовано в 10 работах [1-10], в том числе 2-х статьях, одна из которых - публикация в ведущем рецензируемом журнале: «Вестник Нижегородского университета им. Н.И. Лобачевского» [1]. Полный список публикаций автора приведен в списке литературы.

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

1. Алгоритмы формирования и поиска данных на графах «тесного мира», примененные к задачам построения систем имён.

2. Математическая модель системы разрешения имён, основанная на

использовании графов «тесного мира».

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

распределенных сервисных сетях.

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

Структура и объем работы

Диссертационная работа состоит из введения, пяти глав, заключения и библиографического списка. Общий объем работы составляет 145 страниц, включая 131 страницу основного текста, 38 рисунков и 5 таблиц. Библиографический список содержит 50 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении даётся общая характеристика работы, обосновывается актуальность исследований, формулируется цель работы, раскрывается научная новизна и практическая значимость полученных результатов.

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

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

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

На основе работы Эрдёша-Реньи (изучавших случайные графы) учёные Дункан Уотте и Стивен Строгатц построили собственную модель (Watts-Strogatz model) формирования графов «тесного мира» (см. рис. 1), показав при этом, что сети «тесного мира» не являются полностью случайными, но обладают определенной внутренней структурой.

Регулярный граф Граф тесного мира Случайный граф

Р= О--р= 1

Вероятность создания случайной связи

Рисунок I. Формирование графов «тесного мира» в модели Уоттса-Строгатца

Распространённым свойством социальных сетей является образование групп, которые представляют собой круг друзей или знакомых, в котором все знают друг друга (то есть составляют полный подграф). Эта врожденная тенденция к кластеризации измеряется коэффициентом кластеризации. Рассмотрим узел i, обладающий k¡ ребер. Если ближайшие соседи исходного узла составляли группу (полный подграф), то они будут связаны k,(k,-1 )/2 рёбрами. Отношение числа E¡ всех рёбер между к, узлами к числу k¡(k,-l)/2 дает значение коэффициента кластеризации для узла i:

(1)

Коэффициент кластеризации всей сети в целом есть среднее арифметическое коэффициентов кластеризации всех узлов сети.

Существует отдельный подкласс сетей «тесного мира», называемый «безмасщтабными

сетями». Эти сети характеризуются функцией распределения Р(к), определяющей вероятность того что у случайно выбранного узла будет ровно к рёбер. Для большинства реально существующих сетей, включая сеть «Всемирная паутина» (World Wide Web) распределение степеней вершин подчиняется степенному закону,

Р(к)~к'г. (2)

Наибольшее практическое значение в данной области имеют работы Альберта Ласло Барабаши. Барабаши показал, что в том случае, если некоторая сетевая система эволюционирует без воздействия внешних регуляторов, количество связей, которое приобретают вершины графа, не случайно. Степень отдельно взятой вершины распределяется не по Пуассоновскому, но по логарифмическому закону (рис. 2). Динамика и структура свободно масштабируемых сетей не зависят от размера сети (количества вершин). Иными словами, свободно масштабируемая сеть сохраняет свои свойства независимо от своего размера.

Рисунок 2. Распределение степеней вершин 8

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

На основе проведенного анализа автором было принято решение об использовании в разрабатываемой архитектуре распределённой структуры данных «Метризованный тесный мир» (М8\\0, основанной на свойствах графов «тесного мира».

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

В целях описания алгоритмов на структуре МБ\У определим биективное отображение между строковыми данными и действительными числами в пределах (0, 1). Представив строку как множество символов ...,5„} введём отображение С(5) = , где В - число символов

используемого алфавита. При подобном отображении, порядок образов строк соответствует лексикографическому порядку данных строк. Определим метрику (расстояние) между двумя строками как М(51(52) = |С(52) — С(51)|.

Рассмотрим основной алгоритм, который выполняет добавление нового информационного объекта в структуру с учётом метрики

(расстояния) между элементами. Алгоритм добавления включает в себя алгоритм поиска. Чтобы гарантировать сохранение свойств «тесного мира» структуры \-lSW на любой стадии эволюции данной структуры, необходимо устанавливать ссылки между элементами сети таким способом, чтобы элементы, близкие друг с другом по метрике, были отделены небольшим количеством ссылок, то есть они принадлежали бы одному кластеру Алгоритм сборки сети МЗХУ.

1. Произвольно выберем элемент Ук где 1 < к < 1-1.

2. Пусть У15Йе<11л51 будет набором посещённых элементов.

3. Пусть СапсНсЫеЫБ! будет набором элементов-кандидатов для установления ссылки, сортированным по значениям псевдометрики до к в порядке возрастания.

4. Предположим, что СапсШагеЫБ! первоначально содержит только Рк.

5. Для у < -1 до п делают следующее

6. Сортируют Сап<Ша1е1л51 по значению псевдометрики до V, в порядке возрастания.

7. Выбирают первый элемент р из СапсНс^е^, не содержащийся в ХДзкесИлз! Если такой элемент не существует, выходят из цикла.

8. Добавляют р к У15Ье(ИЛ51.

9. Добавляют набор элементов-соседей по отношению к р в СапсПсШеЫБ!.

10. Взаимно соединяют м элемент с т ближайшими элементами из Ч^^есНив!.

Графическое представление данного алгоритма приведено на рисунке 3.

Рисунок 3. Блок-схема алгоритма сборки структуры М8\\' 10

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

В основе предлагаемой архитектуры системы разрешения имён лежит переход при построении систем управления адресацией в инфокоммуникационных сетях с иерархической архитектуры на гетерархическую. Гетерархия — система, образованная пересекающимися, разнообразными и одновременно сосуществующими структурами управления. Термин «гетерархия» введен в работе нейропсихолога и кибернетика У. Маккаллока «Гетерархия ценностей, обусловленная топологией нервных сетей» (1943 г.).

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

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

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

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

11

Приведем обобщенный алгоритм поиска сервиса в гетерархической сервисной сети в рамках сценария предоставления сервисов:

1. Имеется гетерархическая сервисная сеть НБМ, состоящая из некоторого множества узлов {Г^}, каждый узел N предоставляет другим участникам НБЫ некоторое множество сервисов {8(]Ч)}

2. В какой-то момент времени некоторый узел N1 данной сети HSN имеет необходимость в получении определенного сервиса 8.

3. Н формирует запрос (ДО) на поиск сервиса Э в сети НЬМ.

4. N1 осуществляет поиск Б в HSN путем инициации специального поискового процесса Р((ДО)) для обнаружения заданного сервиса.

5. В рамках данного процесса узел N1 выбирает множество соседних с ним по логической сети узлов {Е} и сортирует согласно метрике семантической и структурной близости информации кибер-паспортов последних к искомому сервису. После чего передает поисковый запрос (ДО) ближайшему по метрике к искомому узлу из {Е}. Обозначим этот узел как Ыь

6. Узел сортирует соседние с ним узлы {Е} согласно отношению по метрике структурной и семантической близости к искомому узлу. После чего передает запрос (ДО) узлу из {Е}, являющимся ближайшим к искомому.

7. Следующий узел повторяет шаг 6 в отношении соседних с ним узлов. Это продолжается до тех пор, пока искомый узел ^ не будет найден. При нахождении данного узла процесс поиска Р((ДО)) завершается.

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

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

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

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

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

Определим доступность сервиса А сервису В как состояние сервиса А, при котором сервиса В может получить доступ к сервису А в произвольный момент времени. Далее в тексте под словом «доступность» мы будем предполагать вероятность нахождения сервиса А в таком состоянии. Пусть ач (i-j availability) - доступность сервиса / сервису /; s -идентификатор структуры связей сервисов в сервисной сети, содержащей N сервисных узлов.

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

N

д*,ло=ГК, (1)

Положим для простоты прямую доступность любого сервиса равной 100%:

a,.,=lV/J(l,..J\0 (2)

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

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

Стоимость системной доступности

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

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

Коммуникативная стоимость

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

СМЮ = Р^1,у>\-,....у = Ъ12 (4)

Л = 1

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

Функция комбинированной стоимости. В качестве комбинированной стоимостной функции ниже будет рассматриваться выпуклая оболочка:

СЕ (*,Ю = Л-С,(*,Ю + 0-Л)-Сс(*,Ю (5)

Параметр X лежит в пределах от 0 до 1 и позволяет «взвешивать» «значимость» стоимостных функций.

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

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

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

STAR

CHAIN

TREE

RING

SMALL WORLD

FULL

Рисунок. 4. Графическое представление проанализированных топологий сервисных сетей

Сравнительные результаты вычислений стоимостных функций также приведены ниже в виде графиков на рисунках 5 и 6 (масштаб по оси ординат - логарифмический).

С.М), ед.

N. ед.

-*~СНМЯ ——

Рис. 6. График стоимости системной доступности для сетей различных топологий

15

TREE

CHAIN

RING

FULL

Рис. 7. График коммуникативной стоимости для сетей различных топологий

Результаты вычислений комбинированной стоимостной функции, являющейся интегральным критерием сравнения различных топологий, вычисленные по формуле (5) приведены в таблице 3 (для X = 0,5). Графическое изображение сравнительных результатов приведено на рисунке 8.

Таблица 3. Комбинированная стоимость

121,46

477,81

580,74

414,56

2415,41

5003,3

3645,12

Ccjs,N), ед.

10000

Рис. 8. График комбинированной стоимости для сетей различных топологий

16

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

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

Количество узлов, К <' '........ ■--------.............- -----------------

я 1000 В 5000 «10000 ¡в ¿0000

Рисунок 9. Сравнение распределения длины пути для различных размеров графа

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

у = 1,0799 1п(х) + 2,3225.

О :

О 1000 5000 10000 20М0 ЪЭ&Х

Количество вершин

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

„2 = аи,(а-у)2 (6)

2Г=0(У; - Я2

где уг - экспериментально полученное значение в точке хь у; - значение модели в точке а у - среднее значение экспериментальных данных по всем точкам. Коэффициент смешанной корреляции изменяется в диапазоне от 0 до 1. Коэффициент смешанной корреляции близкий к 1 указывает на то, что модель адекватно описывает экспериментальные данные. В нашем случае полученное значение коэффициента Л2 = 0,9916; что позволяет говорить о высокой точности выбранной модели. Таким образом, можно утверждать, что зависимость роста средней длины пути в графе от количества вершин графа носит логарифмический характер. Распределение степеней вершин графа

Был произведён эксперимент, позволяющий оценить распределение степеней вершин графа сети. При помощи алгоритмов обхода графов были исследованы все вершины собранной сети. Эксперимент был произведен для структур состоящих из 1000, 5000, 10000 и 20000 элементов.

Приведенный ниже график иллюстрирует распределение степеней вершин, полученное экспериментальным путем и результаты аппроксимации распределения степенной зависимостью вида: у(х) = с-х~к. На графике (рисунок 11) приведено распределение степеней вершин для графа из 20000 элементов, как наиболее репрезентативная выборка.

Степень вершины

Рисунок. 11. Распределение степеней вершин в графе из 20000 элементов

Для оценки качества модели был произведен, согласно формуле (6), расчет коэффициента смешанной корреляции R2 = 0,7341. Исходя из вышеизложенного можно с определенной долей уверенности утверждать, что полученная экспериментальная зависимость носит характер, близкий к степенному. Это может служить подтверждением того, что созданная сеть относится к классу свободно-масштабируемых.

Эффе1стивн0сть алгоритмов формирования графов MSW. В процессе исследования характеристик прототипа одноранговой системы имён были проведены эксперименты на добавление потоков данных в хранилище на основе графов тесного мира. В качестве тестовых входных данных использовались простейшие кортежи вида: адрес, имя устройства. В качестве адресов использовались сетевые адреса протокола IPv4, создаваемые в ходе эксперимента по шаблону: 192.ХХХ.ХХХ.ХХХ. Доменные имена создавались по шаблону: nameXXXXX.com, где X обозначает случайным образом генерируемые в пределах цифры от 0 до 9. Для генерации случайных чисел использовались методы класса java.util.Random языка Java. Числа генерировались с равномерным распределением от 0 до 255, для IP адресов и от 0 до 99999 для имен.

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

При добавлении элементов в случайном порядке (как описано выше) удалось получить нелинейную зависимость, по форме близкой к логарифмической. На рисунке 12 представлен график зависимости времени добавления элементов в систему М8\У от количества элементов в системе.

I, мс 4000

2000

1000

20 000

40000

Рисунок 20. Зависимость времени добавления 40000 элементов в систему М8\У от количества элементов в системе

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

В общем случае нелинейные регрессионные модели имеют вид:

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

/(ш,х) = (со,50:)) = д((х),

где со = [ш1,..., а>п] — параметры регрессионной модели, х — свободная переменная из пространства Еп, у — зависимая переменная, V — случайная величина и д = [дх, ...,дп] — функция из некоторого заданного множества.

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

В данном случае получили модель следующего вида:

= 1од1т7{300.561 + 997.826 х).

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

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

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

2. Разработана децентрализованная, распределенная архитектура систем преобразования имён на основе использования гетерархических структур - математических графов «тесного мира». Разработан алгоритм расчёта метрики (Глава 2) и алгоритм получения доступа к сетевому узлу по его имени (Глава 3).

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

4. Проведено экспериментальное исследование характеристик структуры "Метризованный тесный мир" путем создания программной реализации на языке Java. Исследованы зависимости среднего времени добавления вершины, распределения степеней вершин и распределения кратчайшего пути между двумя вершинами графа от общего числа вершин графа (Глава 5).

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК

1. Крылов В.В., Панкратов Ю.В. Архитектуры одноранговых систем разрешения имён в сети Интернет // Вестник Нижегородского университета им. Н.И. Лобачевского № 1. Нижний Новгород: Издательство Нижегородского госуниверситета.- 2011,- С. 213-221.

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

2. Панкратов Ю.В. Использование алгоритмов синтаксического разбора для эффективного хранения информации текстов естественных языков // Тезисы докладов VII Международной молодежной научно-технической конференции «Будущее технической науки». Нижний Новгород: Типография НГТУ, 2008,- С. 53.

3. Krylov V., Ponomarev D., Pankratov Y. Multi-radar system database integration using metrized small world technology // Proceedings of Microwave Radar and Wireless Communications (MIKON), 2010. pp. 532-534.

4. Крылов B.B., Панкратов Ю.В. Развитие архитектур IP-сетей: вызовы и прогнозы // Журн. Документальная Электросвязь №21. М.: Изд-во АДЭ. 2011.- С.12-17.

5. Панкратов Ю.В. Анализ производительности системы доменных имён и альтернативные архитектуры систем разрешения имён в сети Интернет // Тезисы 14-ой Нижегородской сессии молодых ученых (технические науки). - Нижний Новгород: Типография НГТУ.- 2009. С. 78.

6. Панкратов Ю.В. Анализ и методы увеличения производительности системы доменных имён сети Интернет // Материалы XV Международной научно-технической конференции "Информационные системы и технологии ИСТ-2009,- Нижний Новгород: Типография НГТУ.-2009, С. 127.

7. Панкратов Ю.В. Построение децентрализованных систем разрешения имён сетевых устройств в глобальных IP-сетях // Материалы XVI Международной научно-технической конференции «Информационные системы и технологии ИСТ-2010»,- Нижний Новгород: Типография НГТУ.-2010. С. 158.

8. Крылов В.В., Михайлов H.H., Пономарев Д.М., Панкратов Ю.В. Архитектура сервисных сетей повышенной безопасности // Материалы 10-ой международной конференции «Обеспечение доверия и безопасности при использовании ИКТ»,- М.: Изд-во АДЭ.- 2011,- С. 46-58.

9. Панкратов Ю.В. Аналитическое и экспериментальное исследование характеристик архитектуры одноранговой системы разрешения имён //

22

Материалы XVII Международной научно-технической конференции «Информационные системы и технологии ИСТ-2011».- Нижний Новгород: Типография НГТУ.- 2011. С. 183.

Ю.Панкратов Ю.В. Гетерархическая архитектура систем разрешения имён в сети Интернет // Материалы X Международной молодежной научно-технической конференции «Будущее технической науки». Нижний Новгород: Типография НГТУ, 2011.- С. 35.

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

Нижегородский государственный технический университет им. Р. Е. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

ВВЕДЕНИЕ.

ГЛАВА 1. АРХИТЕКТУРА СИСТЕМ ИМЁН.

1.1. Концепция и технологии систем имён.

1.1.1. Основные понятия и термины.

1.1.2. Основные функции системы имён.

1.2. Архитектура системы доменных имён.

1.2.1. Базовые определения.

1.2.2. Организация пространства имён. Домены.

1.2.3. Серверы имён. Файлы зоны.

1.3. Протоколы системы доменных имён.

1.4. Расширения системы доменных имён.

1.5. Альтернативные архитектуры систем имён.

1.5.1. Одноранговые системы имён.

1.5.2. Система разрешения идентификаторов Handle.

1.5.3. Система Цифровых идентификаторов объектов (DOI).

Выводы по Главе 1.

ГЛАВА 2. СПОСОБЫ ОРГАНИЗАЦИИ ДАННЫХ.

2.1. Классические структуры данных.

2.1.1. Двоичные деревья.

2.1.2. Б-деревья.

2.1.3. Хеш-таблицы.

2.2. Сложные сети.

2.2.1. Сети «тесного мира».

2.2.2. Безмасштабные сети.

2.3. Структура «Метризованный тесный мир».

Выводы по Главе 2.

ГЛАВА 3. ГЕТЕРАРХИЧЕСКАЯ АРХИТЕКТУРА СИСТЕМ ИМЁН .89 3.1. Гетерархический принцип организации.

3.2. Элементы системы.

3.3. Модель управления доверием.

Выводы по Главе 3.

ГЛАВА 4. ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ ДОСТУПНОСТИ ГЕТЕРАРХИЧЕСКИХ СЕТЕЙ.

4.1. Цели исследования.

4.2. Определения и начальные соотношения.

4.3. Анализ стоимостных функций.

4.4 Сравнение системной доступности сетей различных топологий.

ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ.

5.1. Исследование свойств графов MSW.

5.1.1. Распределение длины пути в графе.

5.1.2. Распределение степеней вершин графа.

5.2. Эффективность алгоритмов формирования графов MSW.

5.2.1. Условия проведения экспериментов.

5.2.2. Детерминированный поток данных.

5.2.3. Случайный поток данных.

Выводы по Главе 5.

Актуальность темы исследований

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

Любое устройство, подключенное к сети Интернет, идентифицируется уникальным сетевым адресом, представляющим собой 32 или 128-битное двоичное число, традиционно записываемое в виде последовательности десятичных или шестнадцатеричных чисел для различных версий сетевого адреса соответственно. Несмотря на то, что маршрутизация данных в Интернете осуществляется на основе сетевых адресов устройств, для человека гораздо легче запомнить буквенное, часто осмысленное имя, чем набор цифр сетевого адреса. Доменные имена играют важную роль в функционировании современного Интернета, так как поиск любого сетевого устройства, подключенного к сети Интернет, обычного начинается с его имени. При этом сами доменные имена хранятся в распределенной базе данных, называемой Системой доменных имен (Domain Name System, DNS). Таким образом, можно сказать, что система доменных имён участвует в управлении адресацией сетевых устройств и маршрутизации сетевого трафика.

Система доменных имён не является единственной системой имён в сети Интернет. В последние годы возросло значение системы цифровых идентификаторов объектов (DOI), планируется создание отдельного руководящего органа DONA (Digital Object Numbering Authority), регулирующего выделение идентификаторов. Пространство имён системы DOI организовано в двухуровневую иерархическую структуру, преобразование идентификаторов в информацию о цифровых объектах происходит при помощи системы Handle, чья структурная организация совпадает с организацией пространства имён. Стоит отметить, что система DOI является более гибким инструментом, чем система доменных имён.

Сегодняшний Интернет вырос далеко за пределы того, каким его видели и проектировали, он перерос те агентства и организации, которые его создавали. Количество устройств, подключенных к Интернету, растет экспоненциально с 1983-го года [1], [2,с.53]. Непрекращающийся рост числа сетевых устройств и постоянно повышающаяся нагрузка выявили неадекватность методов управления адресацией, основанных на иерархических структурах, применительно к большим компьютерным сетям, в частности, к Интернету. Для решения проблем масштабируемости таких систем необходима разработка архитектур систем управления адресацией, в частности, систем преобразования имён, основанных на неиерархических, децентрализованных архитектурах. Разработка подобной архитектуры является целью настоящей работы, что обуславливает её актуальность.

Объект исследования

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

Предметом исследования в настоящей диссертационной работе выступают алгоритмы управления адресацией в компьютерных сетях. Под адресацией понимается процесс получения доступа к устройству в выбранной сети. Управление адресацией это процесс, ставящий в соответствие одну систему адресов (т.е. идентификаторов сетевых устройств) другой системе адресов. Цель диссертационной работы

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

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

1. Исследование и анализ существующих иерархических и неиерархических архитектур систем разрешения имён.

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

3. Разработка теоретической модели относительно задачи построения децентрализованной системы преобразования имён. Теоретическое исследование свойств такой системы на основе построенной модели.

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

Методы исследования

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

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

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

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

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

Теоретическая значимость

Теоретическая значимость работы заключается в исследовании характеристик графов «тесного мира», разработке алгоритмов эволюции и поиска на таких графах.

Практическая значимость

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

Полученные в диссертации результаты, в частности, модель децентрализованной системы преобразования имён, основанной на использовании свойств математических графов «тесного мира», применяются в исследовательской компании «МераЛабс» в рамках проекта «Cognitive Internet», посвященного проектированию архитектур компьютерных сетей.

Кроме того, полученные в ходе работы результаты были внедрены в учебный процесс НГТУ им. Р.Е. Алексеева по дисциплине «Основы построения телекоммуникационных систем и сетей» в виде курса лекций. Апробация работы

Материалы диссертационной работы докладывались и обсуждались на 3-х международных научно-технических конференциях «Информационные системы и технологии» (Нижний Новгород, НГТУ им. Р.Е. Алексеева, 20092011 гг.), на международной конференции «Будущее технической науки» (Нижний Новгород, 2011) и на научной конференции «Сессия молодых ученых» (Нижний Новгород, 2009). Публикации

Основное содержание диссертации опубликовано в 10 работах [39-48], в том числе 2-х статьях, одна из которых - публикация в ведущем рецензируемом журнале: «Вестник Нижегородского университета им. Н.И. Лобачевского» [46]. Полный список публикаций автора приведен в списке литературы.

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

1. Алгоритмы формирования и поиска данных на графах «тесного мира», примененные к задачам построения систем преобразования имён.

2. Математическая модель системы разрешения имён, основанная на использовании графов «тесного мира».

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

Личный вклад

Разработка и исследование математической модели архитектуры системы разрешения имён, проведенное экспериментальное исследование, а также все основные научные результаты, изложенные в диссертационной работе, получены автором лично. Структура и объем работы

Диссертационная работа состоит из введения, пяти глав, заключения и библиографического списка. Общий объем работы составляет 145 страниц, включая 131 страницу основного текста, 38 рисунков и 5 таблиц. Библиографический список содержит 50 наименований.

Выводы по Главе 5

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

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

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

3. Были экспериментально изучены свойства алгоритмов сборки и поиска данных на графах MSW. Экспериментально получена логарифмическая зависимость времени добавления новых элементов от размера графа. Доказанное свойство, логарифмическое время поиска элементов по хранилищу структуры MSW, позволяет говорить об адекватности выбранных алгоритмов применительно к задачам построения высокомасштабируемых решений в области создания распределенных систем управления адресацией, в частности систем разрешения имён.

Заключение

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

В работе проведен анализ существующих архитектур систем разрешения имён в TCP/IP сетях, исследованы их свойства, проанализированы достоинства и недостатки с точки зрения параметров качества обслуживания. Разработана архитектура системы разрешения имён, основанная на гетерархическом принципе организации данных. Произведено компьютерное моделирование прототипа системы разрешения имён имплементированного на языке программирования Java. Экспериментально исследованы свойства структуры данных Metrized Small World.

В процессе работы над диссертацией выявлены и обоснованы следующие научные и практические положения:

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

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

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

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

5. Структурами отвечающими всем вышеописанным требованиям являются неиерархические (гетерархические) структуры описываемые математическими графами «тесного мира». Путем введения метрики разности (или расстояния) между элементами данных, хранимых в узлах графа, были созданы эффективные алгоритмы {0(log(n)) создания структуры, названной Метризованным Тесным Миром (МЗДУ).

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

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

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

При работе над диссертацией решены следующие исследовательские задачи:

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

2. Разработана децентрализованная, распределенная архитектура систем преобразования имён на основе использования гетерархических структур - математических графов «тесного мира».

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

4. Проведено экспериментальное исследование характеристик структуры "Metrized Small World" путем создания программной реализации на языке Java. Исследованы зависимости распределения степеней вершин и кратчайшего пути между двумя вершинами графа при росте общего количества вершин графа.

Основными результатами работы являются:

1. Исследование и разработка алгоритмов формирования и поиска данных на графах тесного мира. Исследование эффективности применения данных алгоритмов к задачам построения систем преобразования имён.

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

3. Теоретическое исследование и доказательство адекватности использования гетерархических структур для организации распределенных децентрализованных информационных структур.

Доказательство основано на разработанной модели гетерархических сервисных сетей.

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

1. Веб-сайт организации Internet Systems Consortium Электронный ресурс. Режим доступа: http://www.isc.org/solutions/survey

2. Яновский Г.Г. Современные проблемы науки в области телекоммуникаций (эволюция и конвергенция): Электронный учебник. СПб.: СПбГУТ им. проф. М.А. Бонч-Бруевича, 2008. 163 с.

3. Mockapetris P. V., Dunlap К. J. Development of the domain name system // Symposium proceedings on Communications architectures and protocols, August 16-18, 1988.- P.123-133,

4. Стандарт IETF RFC 1034. Domain names concepts and facilities Электронный ресурс. - Режим доступа: http://www.ietf.org/rfc/rfcl034.txt

5. Стандарт IETF RFC 1035. Domain names implementation and specification Электронный ресурс. - Режим доступа: http://www.ietf.org/rfc/rfcl035.txt

6. Стандарт IETF RFC 1886. DNS Extensions to support IP version 6 Электронный ресурс. Режим доступа: http://www.ietf.org/rfc/rfcl886.txt

7. Chandramouli R., Rose S. Secure Domain Name System (DNS) Deployment Guide. Recommendations of the National Institute of Standards and Technology.- Gaithersburg, MD: U.S. Dept. of Commerce, National Institute of Standards and Technology.- 118 p.

8. Cox R., Muthitacharoen A., Morris R. Serving DNS using a Peer-to-Peer Lookup Service // Proceedings of First International Workshop on Peer-to-Peer Systems, Cambridge, MA, Mar. 2002. P. 45-49.

9. Cox R., Muthitacharoen A., Morris R. DNS and DHTs: Not Quite Perfect Together // Proceedings of the First International Peer-to-Peer Symposium, March 2002. P. 35-39.

10. Druschel P., Rowstron A. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems // Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), 2001.- P. 54-60.

11. Waldman M., Rubin A., Cranor L. Publius: A robust, tamper-evident, censorship-resistant, web publishing system // Proceedings of the 9th USENIX Security Symposium, August 2000.- P. 59-72.

12. Ratnasamy S., Francis P., Handley M., Karp R., Shenker S. A scalable content-addressable network // Proceedings of the ACM SIGCOMM 2001 Technical Conference, San Diego, CA, USA, August 2001.- P.35-47.

13. Stoica I., Morris R., Karger D., Kaashoek F., Balakrishnan H. Chord: A scalable content-addressable network // Proceedings of the ACM SIGCOMM 2001 Technical Conference, San Diego, CA, USA, August 2001.- P. 48-62.

14. Zhao В., Kubiatowicz К., Joseph A. Tapestry: An infrastructure for fault-resilient wide-area location and routing. Technical Report UCB//CSD-01-1141, University of California at Berkeley Technical Report, April 2001.- P 42-54.

15. Cholvi V., Felber P., Biersack E. Efficient search in unstructured peer-to-peer networks / European Transactions on Telecommunications: Special Issue on P2P Networking and P2P Services. 2004. №15. P. 23-27.

16. Веб-сайт проекта Netskuku Электронный ресурс. Режим доступа: http://lab.dyne.org/Netsukuku

17. Веб-страница проекта Entangled Электронный ресурс. Режим доступа: http:// entangled, sourceforge.net/

18. Рекомендация ITU-T Х.1161. Framework for secure peer-to-peer communications. 2008. Электронный ресурс. Режим доступа: http://www.itu.int/rec/T-REC-X. 1161 -200805-1

19. Рекомендация ITU-T X.l 162 Security architecture and operations for peer-to-peer networks. 2008. Электронный ресурс. Режим доступа: http://www.itu.int/rec/T-REC-X. 1162-200805-1

20. Kahn R., Wilensky R. A Framework for Distributed Digital Object Services // International Journal on Digital Libraries, Springer, Volume 6, Number 2. 2006.-P. 115-123.

21. Стандарт IETF RFC 3761, The E.164 to Uniform Resource Identifiers (URI) Dynamic Delegation Discovery System (DDDS) Application (ENUM) Электронный ресурс. — Режим доступа: http://tools.ietf.org/html/rfc3761

22. NAPTR Records in .tel, whitepaper Telnic Ltd., September 2008. Электронный ресурс. — Режим доступа: dev.telnic.org/docs/naptr.pdf

23. Кнут Д. Искусство программирования, том 1. Основные алгоритмы— 3-е изд. — М.: «Вильяме», 2006. — С. 720. — ISBN 0-201-89683-4.

24. Кнут Д. Искусство программирования, том 3. Сортировка и поиск — 2-е изд. — М.: «Вильяме», 2007. — С. 824. — ISBN 0-201-89685-0.

25. Erdos P., Renyi A. On the Evolution of Random Graphs / Publ. Math. Inst. Hungarian Acad. Sci. №5, 1960. P. 17 - 61.

26. Watts D.J.; Strogatz S.H. Collective dynamics of 'small-world' networks // Nature, №393 (6684).- 1998.- P. 409 410.

27. Watts D. J. Small Worlds: The Dynamics of Networks between Order and Randomness / New Jersey: Princeton University Press, 1999.- 264 p.

28. Aiello W., Lu L. Random evolution in massive graphs. Proceedings of the 42nd IEEE on Foundations of Computer Science, FOCS, IEEE Computer Society, 2001.- P. 510.

29. Schmitz C. Self-organization of a small world by topic // In Proceedings of the 1st Intl. Workshop on Peer-to-Peer Knowledge Management, Boston, MA, USA, 2004.- P. 65-69.

30. Albert R., Barabasi A. Statistical Mechanics of Complex Networks // Reviews of Modern Physics №74 (Issue 1), March 2002.- P. 47-97.

31. Barabasi A., Bonabeau E., Scale-Free Networks // Scientific American. 2003. №288. P. 50-59.

32. Krylov V., Logvinov A., Ponomarenko A., Ponomarev D. Metrized Small World Properties Data Structure // Proceedings of SEDE. ISCA, 2008.- P. 203208.

33. Krylov V., Logvinov A., Ponomarenko A., Ponomarev D. Active Database Architecture for XML Documents // Proceedings of 21st International

34. Conference on Computer Applications in Industry and Engineering, 2008.- P. 118-123.

35. Крылов B.B., Пономарев Д.М. Способ и система хранения, поиска и извлечения информации на основе слабоорганизованных и децентрализованных наборов данных // Патент RU2007000475. 2007.

36. Gelernter D., Carriero N. Coordination languages and their significance // Communications of the ACM, V. 35(2), February 1992. P. 97-107.

37. Ranjan R., Harwood A., Buyya R. Peer-to-peer tuple space: a novel protocol for coordinated resource provisioning. Technical Report GRIDS-TR-2007-14 / Grids Laboratory, CSSE Department, The University of Melbourne, Australia, 2007.- 17 p.

38. Krylov V., Ponomarev D., Pankratov Y. Multi-radar system database integration using metrized small world technology // Proceedings of Microwave Radar and Wireless Communications (MIKON), 2010.- P. 532-534.

39. Крылов B.B., Панкратов Ю.В. Развитие архитектур IP-сетей: вызовы и прогнозы // Документальная Электросвязь. №21. М.: Изд-во АДЭ, 2011.-С.12-17.

40. Панкратов Ю.В. Анализ производительности системы доменных имён и альтернативные архитектуры систем разрешения имён в сети Интернет //

41. Тезисы 14-ой Нижегородской сессии молодых ученых (технические науки). Нижний Новгород: Типография НГТУ, 2009.- С. 78.

42. Крылов В.В., Михайлов Н.Н, Пономарев Д.М., Панкратов Ю.В. Архитектура сервисных сетей повышенной безопасности // Материалы 10-ой международной конференции «Обеспечение доверия и безопасности при использовании ИКТ». М.: Изд-во АДЭ, 2011.- С. 46-58.

43. Крылов В.В., Панкратов, Ю.В. Архитектуры одноранговых систем разрешения имён в сети Интернет // Журн. Вестник Нижегородского университета им. Н.И. Лобачевского № 1. Нижний Новгород: Издательство Нижегородского госуниверситета, 2011,- С. 213-221.

44. Панкратов Ю.В. Гетерархическая архитектура систем разрешения имён в сети Интернет // Материалы X Международной молодежной научно-технической конференции «Будущее технической науки». Нижний Новгород: Типография НГТУ, 2011.- С. 35.

45. Bricklin D. Friend-to-Friend Networks Электронный ресурс. Режим доступа: http://www.bricklin.com/f2f.htm

46. Крылов В.В., Самохвалова С.С. Теория Телетрафика и её приложения.

47. СПб.: БХВ-Петербург, 2005.- 288 с.