Актуальность темы
исследований
В информационном обществе большую роль играют коммуникационные сети. Такие сети позволяют производить быстрый обмен информацией и осуществлять координацию действий. В настоящее время на возможности сети Интернет опираются банковские операции, электронный документооборот в государственных и коммерческих структурах. Электронная почта и социальные сети становятся основой общения для многих людей.
Любое устройство, подключенное к сети Интернет, идентифицируется уникальным сетевым адресом, представляющим собой 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-х международных научно-технических конференциях «Информационные системы и технологии» (Нижний Новгород, НГТУ им. Р. Е. Алексеева, 20 092 011 гг.), на международной конференции «Будущее технической науки» (Нижний Новгород, 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. Теоретическое исследование и доказательство адекватности использования гетерархических структур для организации распределенных децентрализованных информационных структур.
Доказательство основано на разработанной модели гетерархических сервисных сетей.
Практическая значимость результатов диссертационной работы заключается в том, что разработанная модель и алгоритмы позволяют производить анализ, моделирование и осуществлять реализацию высокомасштабируемых решений в области создания распределенных децентрализованных информационных систем, в частности систем разрешения имен в компьютерных сетях.