close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
Городилов Алексей Владиславович
Разработка методики и алгоритмов повышения
эффективности взаимодействия сетевых
приложений на верхних уровнях модели OSI
Специальность: 05.13.01— Системный анализ, управление и обработка
информации (в приборостроении)
АВТОРЕФЕРАТ
диссертации на соискание учёной степени
кандидата технических наук
Москва — 2013
Работа выполнена на кафедре информатики и программного обеспечения
вычислительных систем Национального исследовательского университета
«МИЭТ»
Научный руководитель:
Гагарина Лариса Геннадьевна
доктор технических наук, профессор,
заведующий кафедрой ИПОВС
Официальные оппоненты:
Щагин Анатолий Васильевич
доктор технических наук, профессор,
заведующий кафедрой САУиК МИЭТ
Нагин Дмитрий Александрович
кандидат технических наук, доцент,
технический директор
ООО «Интернет-системы»
Ведущая организация:
Открытое акционерное общество
«ОТИК-групп»
Защита состоится 10 декабря 2013 г. в 16 часов 00 минут на заседании диссертационного совета Д.212.134.02 при Национальном исследовательском университете «МИЭТ»: 124498 Москва, Зеленоград, проезд 4806, д. 5, МИЭТ.
С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «МИЭТ».
Автореферат разослан 8 ноября 2013 г.
Учёный секретарь
диссертационного совета,
доктор технических наук, доцент
Гуреев А. В.
2
Общая характеристика работы
Актуальность работы. Проблема обработки информации о физической
структуре и загруженности компьютерной сети на прикладном уровне в настоящее время является актуальной. Современные компьютерные сети, в том
числе Интернет, используют для передачи информации стандартизированный
стек протоколов TCP/IP. Многоуровневая структура стека TCP/IP и изоляция
уровней друг от друга обеспечивают функционирование приложений независимо от физических свойств каналов передачи, что позволяет сократить время разработки приложений и уменьшить количество ошибок в них.
Существенными недостатками изоляции прикладного уровня от физических свойств сети являются невозможность анализа и обработки информации
о режиме передачи транспортного уровня и ниже, что приводит к неэффективному использованию каналов связи, а также к совершенно новым источникам сбоев и ошибок. В частности, в IP-телефонии снижается качество звука,
если во время разговора загружается файл, а в файлообменной сети выход из
сети каких-либо узлов влечёт потерю фрагментов передаваемых файлов.
Популярные в настоящее время сети с p2p-структурой (peer-to-peer, пиринговые сети) реализованы на верхних уровнях модели OSI, соответствующих прикладному уровню стека TCP/IP. Они обладают гибкостью и простотой внедрения, но создают непостоянную и трудно предсказуемую нагрузку
на сеть. Для повышения надёжности и быстродействия приложениям, работающим в пиринговых сетях, необходимо знать физическую структуру и загруженность сети. Исследованиям в области анализа, моделирования пиринговых сетей и обработки информации об их структуре с целью повышения
эффективности их функционирования посвящён ряд работ зарубежных специалистов, таких как К. В. Росс, Д. Рубинштейн, Прадееп Судаме, Фу Сядун
и других. Все эти работы ориентированы на разработку новых нестандартных
протоколов сетевого и канального уровней, внедрение которых требует замены всех существующих приложений новыми.
На сегодняшний день не существует простого во внедрении способа получить с прикладного уровня данные о физической структуре и загруженности сети, поэтому создание методики обработки информации об особенностях сети и потребностях приложений на верхних уровнях модели OSI
и управления структурой пиринговой сети является весьма актуальной проблемой.
Целью диссертационной работы является создание модели сети, методики учёта особенностей сети и требований сетевых приложений (МУчОС)
и реализующих её алгоритмов, обеспечивающих повышение надёжности
и быстродействия при передаче мультимедийных данных, а также разработка
на их основе комплекса программных средств передачи данных (КПС ПД), реализующего динамическую маршрутизацию на верхних уровнях модели OSI.
3
Для достижения данной цели необходимо решить следующие задачи:
– проанализировать существующие методы сбора данных о структуре сети
и обработки этой информации на верхних уровнях модели OSI;
– разработать методику учёта особенностей сети и требований сетевых
приложений (МУчОС);
– разработать комплексный алгоритм функционирования узла сети, алгоритм динамической маршрутизации в сети (АДМ) и алгоритм демаршрутизации и безопасного выхода узла из сети;
– верифицировать МУчОС для различных типов приложений и оценить её
эффективность с помощью имитационного моделирования;
– разработать программную реализацию предложенной методики и алгоритмов в виде КПС ПД.
Методы исследования. Теоретическую и методологическую базу исследования составили методы алгебры логики, теории графов, теории вероятностей и математической статистики, теории массового обслуживания, теории информации. Для валидации результатов применяется имитационное моделирование.
Научная новизна. Диссертационная работа представляет собой совокупность научно обоснованных технических разработок, направленных на
создание методики и алгоритмов, обеспечивающих повышение надёжности
и быстродействия передачи данных в пиринговых сетях и разработки КПС ПД
на их основе.
В процессе исследований и разработок получены следующие новые научные результаты.
1. На основе анализа современного состояния проблемы повышения надёжности и быстродействия предложено формализованное представление
пиринговой сети, основанное на теории графов и приводящее к использованию для маршрутизации алгоритма построения кратчайшего пути A*.
2. Предложена методика учёта особенностей сети и требований сетевых
приложений на верхних уровнях модели OSI (МУчОС), повышающая надёжность и быстродействие передачи мультимедийных данных в распределённых пиринговых сетях.
3. Разработан комплексный алгоритм функционирования узла в пиринговой сети на основе предложенной методики, позволяющий поддерживать
самоорганизующееся функционирование сети.
4. Разработан алгоритм динамической маршрутизации, основанный на распределённой модификации алгоритма A*, обеспечивающий быстрый
расчёт сетевых путей; предложена эвристическая функция, зависящая
от пропускной способности и загруженности каналов.
5. Разработан алгоритм демаршрутизации и безопасного выхода узла из сети, обеспечивающий целостность структуры сети при отключении от неё
части узлов.
4
6. Проведена верификация МУчОС с помощью имитационной модели пиринговых сетей различного масштаба и назначения, подтвердившая эффективность МУчОС.
7. Создан КПС ПД, функционирование которого подтвердило, что количество отказов при передаче мультимедийных данных уменьшилось в 8
раз, и скорость передачи возросла в 1,5–2 раза (в зависимости от типа
приложения) по сравнению с существующими системами.
Достоверность полученных результатов подтверждается соответствием результатов моделирования результатам теоретических расчетов,
проведённых с применением методов теории графов, математической статистики и теории массового обслуживания, а также опытной эксплуатацией.
Разработанное программное обеспечение фактически используется на
предприятии ООО «Компнет» и обеспечивает повышение скорости передачи
мультимедийных данных в 1,5 раза по сравнению с существующими системами.
Практическая значимость заключается в том, что основные положения, выводы и рекомендации диссертации ориентированы на широкое применение методики учёта особенностей сети и требований приложений в архитектуре пиринговых сетей.
Предложенный подход к построению систем передачи данных позволяет разрабатывать сетевые приложения с высокой надёжностью и быстродействием. КПС ПД доведён до практического использования и применяется для
автоматизации обмена данными в локальной сети ООО «Компнет».
Самостоятельное практическое значение имеют:
– методика учёта особенностей сети и требований приложений на верхних
уровнях модели OSI (МУчОС);
– комплексный алгоритм функционирования узла в пиринговой сети;
– алгоритм динамической маршрутизации в пиринговой сети;
– алгоритм демаршрутизации и безопасного выхода узла из сети;
– имитационная модель пиринговой сети произвольного масштаба с динамически изменяемой структурой;
– программная реализация методики и алгоритмов в виде КПС ПД.
Практическая значимость подтверждена актом внедрения результатов
диссертационной работы в учебном процессе МИЭТ и ООО «Компнет».
Личный вклад автора.
Все основные результаты диссертационной работы получены автором самостоятельно, в том числе:
1. Предложена методика МУчОС, применимая на верхних уровнях модели
OSI.
2. Для верификации МУчОС разработана имитационная модель пиринговой сети произвольного масштаба с динамически изменяемой структурой.
5
3. Получена оценка эффективности разработанной методики МУчОС; показано, что использование МУчОС уменьшает количество отказов при
передаче мультимедийных данных в 8 раз при повышении скорости передачи данных в 1,5–2 раза по сравнению с существующими системами.
4. Разработан комплексный алгоритм функционирования узла.
5. Разработан алгоритм динамической маршрутизации, основанный на распределённой модификации алгоритма A*; предложена эвристическая
функция, зависящая от пропускной способности и загруженности каналов.
6. Разработан алгоритм демаршрутизации и безопасного выхода узла из сети.
7. Осуществлена программная реализация методики и алгоритмов в виде
КПС ПД.
Реализация полученных результатов. Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры
«Информатика и программное обеспечение вычислительных систем» НИУ
«МИЭТ» и являлась составной частью НИР «Визуализация эволюции нелинейных динамических систем в области управления техническими и синергетическими объектами на основе информационных технологий и методов»
в рамках АВЦП «Развитие научного потенциала высшей школы» (шифр ГБ
7.1534.2011). Работа заняла II место на проводившемся в 2013 году Третьем
Международном молодёжном промышленном форуме «Инженеры будущего
2013» по номинации «Мой завод будущего».
Результаты диссертационной работы внедрены в учебный процесс кафедры ИПОВС в материалах курсов «Основы UNIX» и «Системный анализ и математическое моделирование», читаемых для старших курсов
специальностей № 230105.65, 230105.62, 230105.68; а также использованы
в ООО «Компнет» при проектировании отказоустойчивой сети абонентских
терминалов IP-телефонии.
Научные положения, выносимые на защиту:
1. Формализованное представление пиринговой сети, основанное на теории
графов, определяет выбор алгоритма построения кратчайшего пути A*
для распределённой реализации динамической маршрутизации на верхних уровнях модели OSI.
2. Методика учёта особенностей сети и требований приложений на верхних уровнях модели OSI (МУчОС) позволяет эффективно использовать
пропускную способность сети и повышает надёжность и быстродействие
распределённой передачи мультимедийных данных в пиринговых сетях.
3. Комплексный алгоритм функционирования узла позволяет поддерживать самоорганизующееся функционирование сети в соответствии
с предложенной методикой.
6
4. Алгоритм динамической маршрутизации, основанный на распределённой
модификации алгоритма A* с использованием предложенной эвристической функции обеспечивает быстрый расчёт сетевых путей.
5. Алгоритм демаршрутизации и безопасного выхода позволяет сохранять
целостность пиринговой сети при отключении от неё части узлов.
6. Программная реализация предложенной методики и алгоритмов в виде
КПС ПД позволяет уменьшить количество отказов при передаче мультимедийных данных в 8 раз при повышении быстродействия в 1,5–2 раза
по сравнению с существующими системами.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях:
1. Всероссийский молодежный научно-инновационный конкурс-конференция «Электроника 2006».
2. 14-я Всероссийская межвузовская научно-техническая конференция
студентов и аспирантов «Микроэлектроника и информатика — 2007»,
Москва, МИЭТ, 2007.
3. 13-я Международная телекоммуникационная конференция студентов
и молодых учёных «Молодёжь и наука», Москва, МИФИ, 2010.
4. 17-я Всероссийская межвузовская научно-техническая конференция
студентов и аспирантов «Микроэлектроника и информатика — 2010»,
Москва, МИЭТ, 2010.
5. Восьмая международная конференция разработчиков и пользователей свободного программного обеспечения «Linux Vacation / Eastern
Europe», Белоруссия, Гродно, 2012.
6. 5-я Всероссийская межвузовская научно-практическая конференция
«Актуальные проблемы информатизации в науке, образовании и экономике — 2012», Москва, МИЭТ, 2012.
7. VI международная заочная научно-практическая конференция «Теоретические и практические аспекты развития современной науки», научно-информационный центр «Институт Стратегических Исследований», 2012.
8. Вторая зимняя сессия международной конференции разработчиков
и пользователей свободного программного обеспечения «Linux Vacation
/ Eastern Europe» — LVEE Winter 2013, Белоруссия, Минск, 2013.
9. Девятая международная конференция разработчиков и пользователей свободного программного обеспечения «Linux Vacation / Eastern
Europe», Белоруссия, Гродно, 2013.
10. Третий Международный молодёжный промышленный форум «Инженеры будущего 2013», Иркутск, 2013.
По результатам исследований опубликовано 16 печатных работ (4 работы —
без соавторов), из них 4 статьи — в изданиях, входящих в перечень ВАК.
7
Структура и объём диссертации. Диссертация состоит из введения,
четырёх глав, заключения, списка литературы и приложений, содержащих листинги программ и акты о внедрении результатов работы. Общий объём диссертационной работы: 127 страниц машинописного текста, 9 таблиц и 41 рисунок.
Содержание работы
Во введении обоснована актуальность диссертационной работы, сформулирована цель и аргументирована научная новизна исследований, показана
практическая значимость полученных результатов, представлены выносимые
на защиту научные положения.
В первой главе проведен обзор современного состояния проблемы повышения надёжности и быстродействия пиринговой сети.
Основными характеристиками пиринговой сети, где каждый узел может
быть как клиентом, так и сервером, являются перечень узлов, составляющих
сеть, и такие параметры каждого из соединяющих их каналов, как пропускная
способность, колебания пропускной способности и латентности.
Проведённый анализ существующих технологий передачи данных показал, что большая часть существующих протоколов вообще не учитывает характеристики сети, что не обеспечивает выбора оптимального маршрута и не
позволяет просачиваться через брандмауэры и трансляторы сетевых адресов
(NAT). Протоколы, учитывающие особенности сети, делятся на группы соответственно используемому уровню модели OSI. При этом обеспечивается
оптимальность одной из характеристик при неудовлетворительном качестве
других.
Предлагается разработка открытой сетевой инфраструктуры, обеспечивающей выбор оптимального маршрута, реализованной на наиболее высоких
уровнях модели OSI и учитывающей как особенности сети, так и требования
приложений. Прототипом такой инфраструктуры является сетевой протокол,
разработанный на основе математического и имитационного моделирования
сети.
Во второй главе определены возможности для исследования физических свойств сети по данным, доступным на верхних уровнях модели OSI.
На рис. 1 показаны узлы и каналы физического уровня одного из возможных вариантов компьютерной сети. Девять узлов этой сети (, ,...) на
прикладном уровне образуют пиринговую сеть.
Формально пиринговая сеть представима как взвешенный сильно связный ориентированный граф, вершинами которого являются узлы сети, а рёбрами — соединяющие их каналы прикладного уровня. При этом граф, включающий все возможные соединения прикладного уровня (рис. 2, а), назовём
максимальным графом пиринговой сети (). На практике узел может установить соединение только с теми узлами, адрес которых хранится в его памя8
E
C
D
B
F
A
G
H
J
- узлы, участвующие в пиринговой сети
- широкополосный проводной или wi-fi-канал
- 2G или 3G канал (более медленный или дорогой)
- пути передачи файла от узла A узлам B, C, D, F, H в традиционной пиринговой сети
- пути передачи файла от узла A узлам B, C, D, F, H в пиринговой сети с возможностью учета
особенностей сети
(F, C получают файл через B, который к ним ближе, H использует J и C для обхода NAT,
что позволяет задействовать широкополосный канал)
Рис. 1. Физическая структура пиринговой сети
ти. Назовём граф , включающий только рёбра, соответствующие возможным
без дополнительного поиска маршрута соединениям, рабочим (рис. 2, б).
Для сохранения целостности сети рабочий граф должен быть сильно
связным остовным подграфом . Выбор рабочего графа сети определяется
методикой самоорганизации сети.
Структура рабочего графа  обеспечивает:
1. Поддержание целостности сети и устойчивости к отказам отдельных узлов или каналов связи, для чего числа вершинной связности () и рёберной связности () должны значительно превышать вероятные количества одновременных отказов узлов и каналов соответственно.
2. Возможность быстрой маршрутизации, для чего в  необходимо включать наиболее короткие рёбра .
3. Балансировка нагрузки на узлы и объёма данных, хранящихся на различных узлах, что ограничивает степень вершин  некоторой величиной .
9


















а)
б)
Рис. 2. Максимальный (а) и рабочий (б) граф пиринговой
сети
Для преобразования рабочего графа к виду, удовлетворяющему вышеперечисленным критериям и поддержания функционирования пиринговой сети
разработана методика учёта особенностей сети и требований приложений
(МУчОС), которая включает следующие основные стадии:
1. Каждый узел (назовём его ) набирает  известных узлов и продолжает
поиск более близких узлов.
2. В случае, если узел  теряет связь с одним из связанных с ним узлов  ,
он ищет новый узел.
3. Если к узлу  подключается новый узел , то для поддержания связности  узел  принимает , даже если количество узлов, известных ,
превосходит , а затем ищет узел, которому он может его отдать.
4. При преднамеренном выходе из системы узел  передаёт каждый известный ему адрес узла  следующему в списке известных +1 и затем
исключает переданный узел  из списка. Последний узел  не передаётся никому и исключается из списка известных. После очистки списка
известных узлов узел  отключается от сети.
5. Последний узел  ищет себе в сети другой известный узел (в соответствии с пунктом 2).
6. Далее процесс стабилизируется по пункту 1.
Для реализации этой методики разработаны следующие алгоритмы:
– общий алгоритм работы узла в сети;
– динамической маршрутизации (построения пути передачи);
– демаршрутизации и безопасного выхода узла из сети.
10
Далее на основе предложенной методики разработаны алгоритмы.
В частности, следующие.
Комплексный алгоритм функционирования узла обладает низкой вычислительной сложностью. В то же время алгоритм предотвращает циклические пути поиска и передачи данных, в противном случае использование
ресурсов сети неэффективно. Для этого алгоритм должен соответствовать
предложенной методике МУчОС.
После построения сети в соответствии с предложенной методикой
МУчОС каждый узел имеет сведения о связанных с ним узлах. Это позволяет
узлам организовать динамическую маршрутизацию (построение эффективных сетевых путей). Для построения пути предложено использование алгоритмов поиска кратчайшего пути на графе.
В соответствии с формализованным представлением пиринговой сети
как её рабочего графа  ⊆ , информация о структуре сети представляет
собой его матрицу инцидентности (). При этом для реализации алгоритма построения кратчайшего пути в графе каждый узел должен иметь доступ
к данным об остальных узлах сети, то есть ко всем элементам (). В памяти
каждого узла  хранится строка (), соответствующая  ( () — информация об известных узлах), доступ к остальным данным осуществляется
по сети.
Так как матрица () и, соответственно, её строка  (), сильно разрежена и имеет большую размерность, она представляется в виде списка ненулевых ячеек. Для каждого ребра   соответствующая ячейка  () содержит идентификатор и адрес  , а также скорость передачи данных ( ,  )
и задержку (латентность)  ( ,  ) канала от  до  . Для вычислений используется эффективная пропускная способность ( ,  ):
( ,  ) =  · ( ,  ) +  ·  ( ,  )
(1)
где коэффициенты  и  определяются решаемой задачей.
Для маршрутизации традиционно применяется алгоритм Дейкстры, и наличие у узлов сведений о связанных с ними других узлах позволяет применить
его распределённую реализацию. Недостатком этой реализации будет необходимость передавать большое количество служебного трафика. Для уменьшения объёма передаваемых данных и увеличения быстродействия предложено
вместо алгоритма Дейкстры использовать алгоритм A*, достигающий более
высокой производительности (по времени) с помощью эвристики.
Алгоритм A* использует вместо расстояния (,  ) между двумя произвольными узлами  и  метрику (,  ) — сумму расстояния (,  )
и значения эвристической функции ℎ( ):
(,  ) = (,  ) + ℎ( )
11
(2)
Начало
Запрос на поиск узла, список
пройдённых узлов,  =
значение эвристической
функции последнего участка
да
нет
Узел является
искомым?
Сообщить
о достижении цели
нет
Есть непройдённые
узлы?
Увеличить  на значение
эвристической функции
ближайшего из узлов, вернувших
запрос, вернуть запрос обратно
да
 > значения
эвристической
функции ближайшего
узла?
да
Добавить текущий узел в список
пройдённых, передать запрос
ближайшему узлу
нет
Добавить текущий узел в список
пройдённых, вернуть запрос
обратно
Конец
Рис. 3. Алгоритм работы узла во время построения пути
Для вычисления эвристической функции ℎ от произвольного узла 
предложена формула (3), зависящая от пропускной способности и загруженности каналов связи узла  с целевым узлом  .
(︁
)︁−1
ℎ() = вых · (,  ) + вх · (, ) + вых · (,  ) + вх · (, )
(3)
где  — текущий узел;
(,  ) — пропускная способность исходящего канала связи узла ;
(, ) — пропускная способность входящего канала связи узла ;
(,  ) — загруженность исходящего канала связи узла ;
(, ) — загруженность входящего канала связи связи узла .
Коэффициенты вых , вх , вых и вх характеризуют класс сетевых приложений. Эвристическая функция должна отличаться для различных классов
приложений, что и обеспечивается подбором коэффициентов. Это позволяет
учесть особенности сети и приложений при построении маршрута.
12
Поскольку узел имеет информацию только о некотором подмножестве
узлов, А* не может быть реализован на отдельно взятом узле. Его реализация
должна быть распределённой, то есть разные шаги алгоритма должны выполняться на разных узлах, имеющих необходимые для шага данные (рис. 3).
Результаты работы должны быть эквивалентны выполнению алгоритма
A* с той же эвристической функцией ℎ() на одном гипотетическом компьютере, имеющем сведения обо всей сети.
Алгоритм демаршрутизации узла — процесс, реализующий четвёртую
стадию методики учёта особенностей сети, описанной выше. Его схема представлена на рис. 4. При условии реализации процессов «поиск дополнительных узлов», «поиск первого узла», «передача узла другому узлу» со сложностью (1), не зависящей от целевого количества известных узлов , алгоритм
работы узла имеет линейную сложность (), что позволит выбирать  исключительно из соображения эффективности работы сети на большинстве современных персональных компьютеров. Это также упростит аппаратную реализацию при использовании во встраиваемых системах, например, в мобильных устройствах связи, если производительности такого устройства будет не
хватать для поддержки работы в системе.
Алгоритм демаршрутизации позволяет узлу выйти из системы с минимальным влиянием на её работоспособность. Несмотря на то, что теоретически сложность этого алгоритма может достигать (3 ), в наиболее вероятном
частном случае — при выходе из системы, в которой насыщены все связи —
сложность алгоритма будет ().
В третьей главе приведена верификация МУчОС, проведённая путём
имитационного моделирования, а также исследование эффективности методики и алгоритмов для различных областей применения.
Рассмотрим различные стратегии выбора известных узлов, что определяет структуру рабочего графа и, в частности, степень его вершин . Если
каждый узел полностью хранит информацию о всей сети ( = ), алгоритм
построения кратчайшего пути может быть реализован полностью локально,
что даёт выигрыш в скорости. Недостатком такой стратегии является большой объём памяти для хранения этой информации ((||2 )) и необходимость
извещать все узлы сети о любом изменении её структуры, что приводит к передаче большого количества служебных данных. Такая стратегия применима
только для очень малых и стабильных сетей.
В случае, когда узел имеет информацию только о ближайших узлах, для
хранения требуется минимальный объём памяти ((˜
), где 
˜ — количество
узлов, соединённых с текущим), а для поддержания этой информации в актуальном состоянии нужен минимальный объём служебного трафика. Недостатком является трудность расчёта кратчайшего пути, так как при расчёте
требуется передача большого количества информации о структуре сети.
13
Начало
Обработка системного вызова
или команды пользователя
о завершении работы.
Определение лимита времени
Перебор известных узлов
 = 1; ; 1
Перебор известных узлов
для рассылки им адреса узла 
 = 1; ; 1
Отправка служебного
сообщения узлам  и 
нет
Узел  знает адрес ?
Передача адреса узла  узлу 
да
Передача успешна
Переход к следующему ,
пока  6 
нет
нет
Процесс прерван
или достигнут лимит
времени
Переход к следующему ,
пока  6 
да
да
Количество
известных узлов
=−1
>1
да
нет
Закрытие сетевых подключений,
завершение работы или переход
в автономный режим
Конец
Рис. 4. Алгоритм демаршрутизации и безопасного выхода
узла из сети
Для соединения достоинств этих двух стратегий предлагается следующий вариант: в список известных узлов включаются не только узлы, непосредственно обменивавшиеся данными с текущим, но и некоторые другие. Для
14
определения рекомендуемого количества известных узлов  получено экспериментальное распределение длин маршрутов.
Показано, что маршруты сетевого уровня протокола BitTorrent являются адекватной моделью маршрутов, прокладываемых АДМ на прикладном
уровне. Для определения количества рёбер в маршрутах в интернете проведён
эксперимент на различных трекерах, различных корневых узлах и в различное
время. На каждом из рассмотренных трекеров получена выборка IP-адресов.
С помощью специально созданного комплекса скриптов определён путь от
выбранного корневого узла до каждого узла выборки; измерена полная длина
пути и длина пути, не включающая подсеть провайдера корневого узла.
Обозначим ненорм () количество соединений длины , то есть частоты
длин, а () — нормированное количество соединений, то есть долю соединений длины  в выборке:
ненорм ()
(4)
() = ∑︀
ненорм ()

Это позволит сравнивать результаты, полученные на выборках разного размера.
Сравнение нормированных частот длин полных (включающих подсеть
провайдера корневого узла) путей (рис. 5, а) показывает, что кривые разделяются на группы в соответствии с корневым узлом.
0,3
0,3
()
0,2
0,2
0,1
0,1
()

5
10
15
20

25
5
10
а)
15
20
25
б)
Рис. 5. Экспериментально полученное распределение длин
путей
Сравнение нормированных частот длин путей, включающих только узлы, не входящие в подсеть провайдера (рис. 5, б) показывает, что положение
главного максимума приблизительно постоянно и лежит в пределах от 4 до 6.
Рассмотрим не частоты, а экспериментально полученные функции распределения (рис. 6, а)

∑︁
 () =  (длина пути 6 ) =
().
(5)
=0
15
1
1
 ()
 ()
0,8
0,8
0,6
0,6
0,4
0,4
0,2
0,2

5
10
15
20

25
5
а)
10
15
20
25
б)
Рис. 6. Экспериментальная функция распределения  ()
и её аппроксимация
Полученные кривые наиболее точно аппроксимируются модифицированной функцией Лоренца (рис. 6, б):
 () =
1+
1
(︀ − )︀
(6)

В соответствии со свойствами распределения () не менее 50% путей
имеют длину, не превышающую пяти рёбер, и более 80% — не превышающую
семи рёбер. Таким образом, при  = 
˜ 5 для более 50% путей адрес конечного
узла определяется локально, что ускоряет работу АДМ.
Определены цели для верификации и исследования эффективности алгоритмов, в том числе путём моделирования при различных значениях параметров.
Для верификации и исследования эффективности предложенных
МУчОС и алгоритмов разработана дискретно-событийная имитационная модель. При этом оценивались масштабируемость, перспективность и универсальность МУчОС.
В течение 10 часов для 20 прогонов с различной топологией пиринговой
сети, которая генерировалась случайным образом, отслеживались следующие
параметры (табл. 1):
 — общее количество переданных данных, файлов или сообщений.
 — количество отказов (потерянных файлов, сообщений, прерванных или
неустановленных вызовов).
 / — скорость передачи: для потоковых данных и сообщений — достигнутая пропускная способность канала (кбит/с); для файлов — время передачи (с).
 / — относительная погрешность измерений.
16
Результаты имитационного моделирования
Таблица 1
Файловый сервер
Существующие
Файлообменная сеть
приложения
Потоковое видео
IP-телефония
Мгновенные сообщения
Файловый сервер
Использование
Файлообменная сеть
МУчОС и АДМ
Потоковое видео
IP-телефония
Мгновенные сообщения
Файловый сервер
Файлообменная сеть
Предельное значение
Потоковое видео
IP-телефония
Мгновенные сообщения
 
500 13
500 55
1000 94
2000 82
10000 19
500
5
500 21
1000 10
2000 10
10000 20
500
2
500
1
1000 10
2000
9
10000
7
 /  /
157
0,12
94
0,06
400
0,08
321
0,10
0,23
0,01
75
0,13
78
0,04
523
0,04
510
0,11
0,26
0,03
60
0,13
55
0,04
523
0,04
510
0,10
0,26
0,03
Исходя из данных таблицы 1 и параметров моделирования, были рассчитаны количество отказов на 10 000 соединений (рис. 7) и средняя скорость
передачи данных (кбит/с) (рис. 8) для всех вариантов.
103

(ед.
на 10 000
соед.)
Существующие системы
Использование МУчОС
Предельное значение
102
101
Файловый
сервер
Файлообменная
сеть
Потоковое
видео
IP-телефония
Мгновенные
сообщения
Рис. 7. Количество отказов на 10 000 соединений в сетях
различного типа
Из результатов проведённого эксперимента (рис. 7) сделан вывод, что
надёжность файлообменной сети возрастает более чем в 2 раза при внедрении предложенной методики и алгоритмов. Файлообменная сеть состоит из
множества независимых узлов, особенности взаимодействия которых современные системы практически неспособны учитывать.
17
103

(кбит/с)
Существующие системы
Использование МУчОС
Предельное значение
102
101
100
10−1
Файловый
сервер
Файлообменная
сеть
Потоковое
видео
IP-телефония
Мгновенные
сообщения
Рис. 8. Скорость передачи данных (кбит/с) в сетях
различного типа
Из рис. 7–8 видно, что для большинства типов приложений выигрыш при
внедрении методики МУчОС незначительно отличается от предельного, практически нереализуемого варианта с полным учётом всех особенностей взаимодействия всех узлов. На практике обмен служебными данными в этом случае вызвал бы перегрузку сети и, как следствие, большое количество отказов,
что не учитывалось при моделировании, а предполагался идеальный обмен.
Для оценки масштабируемости моделировалась локальная сеть (local
area network, LAN) из 100 узлов с топологией «звезда», сеть среднего масштаба (metropolitan area network, MAN) и глобальная (wide area network,
WAN) с магистральными каналами с пропускной способностью 10 000 МБит/с
(табл. 2).
Средняя пропускная способность (битрейт, кбит/с)
Таблица 2
Протоколы
Масштаб
Существующие
приложения
Использование
МУчОС и АДМ
LAN
100
MAN
75
WAN
48
Перспективные протоколы
(IPv6, 802.11s)
LAN
MAN
WAN
110
105
95
100
85
80
115
Современная сеть (IPv4)
120
115
Сделан вывод, что предложенная методика позволяет эффективно использовать преимущества перспективных протоколов, таких как IPv6 или
802.11s, и не утратит своего значения с повсеместным внедрением этих протоколов. Наибольший прирост эффективности достигается для сетей масштаба
города, но также значителен для локальных и глобальных сетей, что говорит
о достаточно хорошей масштабируемости МУчОС.
18
Моделирование IP-телефонии и передачи потокового видео при различной нагрузке на сеть показало бо́льшую устойчивость МУчОС и АДМ по сравнению с существующим протоколом SIP (рис. 9).
·10−2
8


МУчОС+АДМ (ПК)
МУчОС+АДМ (моб. устройства)
SIP
6
4
2

200
400
600
800
1000
1200
1400
1600
1800
2000
2200
2400
2600
Рис. 9. Относительное количество сорванных соединений
( ) при различном количестве соединений в час ( )
В результате имитационного моделирования было установлено, что
больше всего выигрывают от внедрения предложенных методики и алгоритмов приложения для IP-телефонии и передачи потокового видео. Методика
и алгоритмы также эффективны для централизованной и децентрализованной передачи файлов, но оказались неэффективными для сервиса мгновенных сообщений. Для всех рассмотренных применений методики и алгоритмы
обладают хорошей масштабируемостью и будут ещё более эффективны при
внедрении перспективных сетевых протоколов.
В результате верификации на имитационной модели сделан вывод о целесообразности построения опытной системы передачи данных, реализующей
одно из сетевых приложений, для которого методика оказалась наиболее эффективной в современных сетях.
В четвёртой главе приведена программная реализация предложенных
методики и алгоритмов для практического приложения IP-телефонии. Продемонстрирована возможность эффективной интеграции сетевого модуля, разработанного на основе предложенных методики и алгоритмов в систему, использующую другие COTS1 -компоненты. Среди этих компонентов библиотека для сжатия аудиоданных в реальном времени Speex, графический интерфейс на основе wxWidgets и стек протоколов TCP/IP.
На рис. 10 представлена структурная схема КПС ПД.
Для реализации данной структуры потребуется разработать следующие
компоненты, которые не доступны в COTS-виде:
1
COTS (Commercial off-the-shelf, коробочный программный продукт) — технология (индустриальная
технология), ориентированная на широкий круг специалистов-непрофессионалов в области информационных
технологий, и использующая единые автоматизированные методы разработки, сопровождения и модернизации
систем автоматики на основе использования готовых объектно-ориентированных средств (инструментов) и компонентов (кубиков).
19
интерфейс получателя
драйвер
устройства
ввода
Декодер
ОС API
параметры передачи
блок передачи данных
определение
адреса
получателя
контроль
целостности
полученные пакеты
построение маршрутов
внешние данные
о структуре сети
сеть
Рис. 10. Структура КПС ПД
20
локальные данные о
струтуре сети
распределенные алгоритмы
и хранилище данных
прием/передача пакетов
по протоколу сетевого
уровня
блок
получения
данных
распаковка
пакетов
пакеты для передачи
формирование
пакетов
выработка
контрольных
значений
драйвер
устройства
вывода
ОС API
закодированный поток
данных
закодированный поток
данных
Кодировщик
функциональный блок
интерфейс источника
сетевой блок
полученная
информация
информация для
передачи
пользователь
1. Протокол передачи прикладного уровня, позволяющий реализовать
предложенную методику любому приложению, поддерживающему данный протокол.
2. Библиотеку компонентов, реализующих протокол передачи данных
и программный интерфейс, позволяющий построить сетевое приложение.
3. Экспериментальное приложение, использующее эту библиотеку компонентов для организации выбранного сетевого сервиса (IP-телефонии).
В качестве экспериментального сервиса был выбран сервис IP-телефонии, так как он является одним из тех сервисов, для которых применение
предложенных методик даёт максимальный эффект, а также в связи с актуальностью построения нового приложения для IP-телефонии.
Для реализации указанных функций протокола разработан формат дейтаграмы (рис. 11), который включает в себя обязательные и необязательные
поля:
– адрес узла назначения;
– адрес узла отправления;
– список промежуточных узлов;
– тип сообщения (служебное или информационное);
– список важных сообщений, переданных до этого сообщения тому же узлу, для обеспечения повторной передачи;
– срок актуальности сообщения (TTL).
0 байт
8 байт
версия
протокола
16 байт
24 байта
адрес
адрес
идентификатор
назначения отправления сообщения
32 байта
TTL
40 байт
размер
списка
адресов
промежуточных
узлов
список адресов
промежуточных
узлов
размер
списка
важных
сообщений
список важных
сообщений
содержание сообщения
зависящее от типа
Рис. 11. Формат дейтаграммы протокола
Информационное сообщение должно содержать:
– формат и назначение передаваемых данных;
– фрагмент кодированного звукового потока, или другие полезные данные;
– порядковый номер сообщения в потоке.
–
–
–
–
–
–
Служебное сообщение (рис. 11, a, b) используется в следующих случаях:
построение пути передачи информационных сообщений по алгоритму
A*;
сообщение о невозможности построения пути через заданный узел;
построение альтернативного пути передачи;
измерение задержки передачи;
сообщение о выходе узла из системы;
организация обмена известными узлами;
21
0 байт
a)
тип
сообщения
0 байт
b)
тип
сообщения
0 байт
c)
8 байт
тип
сообщения
8 байт
16 байт
адрес
узла
для
передачи
8 байт
24 байта
расстояние
до
узла
16 байт
порядковый
номер
блока
данных
размер
блока
данных
24 байта
блок
полезных
данных
Рис. 12. Содержание сообщения протокола: a —
большинство служебных сообщений, b — служебное
сообщение для обмена известными узлами, c —
информационное сообщение
– сообщение о пропускной способности канала между двумя узлами.
Многие служебные сообщения, например, сообщение для измерения задержки, не требуют передачи других данных, кроме факта передачи сообщения (рис. 11, a).
Сообщения могут передаваться как с использованием транспортного
протокола без гарантии доставки, например UDP из стека TCP/IP, так и с гарантией доставки (TCP).
Для сжатия голосовых данных применено кодирование Speex. Этот алгоритм не имеет патентных ограничений и существуют свободные реализации
алгоритма, позволяющие быстро и с минимальными затратами интегрировать
его в приложение. Кроме того, существуют успешные аппаратные реализации
этого алгоритма сжатия. В качестве кросс-платформенного интерфейса для
вывода звука используется библиотека SDL, так как она предоставляет доступ к звуковым данным в требуемом виде (поток двоичных данных), и также
является свободной и кросс-платформенной.
В заключении отражены основные выводы и результаты диссертации.
В приложениях приведены фрагменты кода разработанного КПС ПД
и акты внедрения результатов.
Основные результаты и выводы
В диссертационной работе осуществлено решение научной проблемы создания методики и алгоритмов, реализуемых на верхних уровнях модели OSI
22
для управления передачей данных по компьютерным сетям с учетом характеристик сети и требований приложения.
При этом получены следующие основные научные и практические результаты:
1. Исследованы методы и алгоритмы управления передачей данных по компьютерным сетям для приложений с особыми требованиями к параметрам канала связи, а также способы реализации и архитектура систем
и компонентов, реализующих эти методы.
2. Разработана графовая и имитационная модели компьютерных сетей, использующих как существующее оборудование и низкоуровневые протоколы, так и перспективные технологии, не получившие ещё широкого
распространения (IPv6, 802.11s).
3. Предложена методика учёта особенностей сети и требований приложений на верхних уровнях модели OSI (МУчОС), решающая проблему
управления передачей данных на прикладном уровне OSI и повышающая
надёжность и быстродействие передачи мультимедийных данных в пиринговых сетях.
4. Разработаны алгоритмы для реализации данной методики в современных сетевых приложениях, работающих с существующей сетевой инфраструктурой:
– комплексный алгоритм функционирования узла;
– алгоритм динамической маршрутизации, основанный на распределённой модификации алгоритма A* (АДМ);
– алгоритм демаршрутизации и безопасного выхода узла из сети.
Эти алгоритмы позволяют поддерживать самоорганизующееся функционирование сети и быстрый расчёт сетевых путей прикладного уровня.
5. Разработана имитационная модель пиринговой сети различного масштаба и назначения с динамически изменяемой структурой.
6. На основе имитационного моделирования выполнена верификация
МУчОС и алгоритмов, а также получена оценка их эффективности.
7. Исследована возможность улучшения качества работы различных классов сетевых приложений при применении МУчОС. Показано, что наиболее перспективное приложение МУчОС — передача мультимедийных
данных (IP-телефония и потоковая трансляция видео и звука).
8. Создана программная реализация предложенной методики и алгоритмов
в виде программного комплекса интернет-телефонии (КПС ПД), учитывающего особенности сети и обеспечивающего снижение количества отказов при передаче звука в 8 раз по сравнению с существующими системами при повышении быстродействия в 1,5–2 раза.
9. Результаты работы внедрены в учебный процесс кафедры ИПОВС в материалах курсов «Основы UNIX» и «Системный анализ и математическое моделирование», а также использованы в ООО «Компнет» при про23
ектировании отказоустойчивой сети абонентских терминалов IP-телефонии.
Основные результаты диссертационной работы представлены
в следующих публикациях
1. Городилов А. В., Ананьина Е. В. Программно-аппаратная система пиринговой передачи видео // Всероссийский молодежный научно-инновационный конкурс-конференция «Электроника 2006»: тезисы докладов конференции. М.: МИЭТ, 2006. С. 38.
2. Городилов А. В., Ананьина Е. В. Алгоритм управления пиринговой сетью // Микроэлектроника и информатика — 2007. 14-я Всероссийская
межвузовская научно-техническая конференция студентов и аспирантов:
Тезисы докладов. М.: МИЭТ, 2007.
3. Городилов А. В., Гагарина Л. Г., Ананьина Е. В., Апрелов С. А. Эстафетная передача видеосигнала в компьютерных сетях общего пользования //
Межотр. науч.-техн. сборник «Оборонный комплекс — научно-техническому прогрессу России» (ВАК). 2007. № 2. С. 51–54.
4. Городилов А. В. Новые информационные технологии преобразования графических форматов для web-анимационного проектирования // Инноватика и информационные технологии: проблемы, перспективы, решения:
Сборник научных трудов / Под ред. д. т. н., проф. Л. Г. Гагариной; МИЭТ. М.: МИЭТ, 2009. С. 70–73.
5. Городилов А. В. Автоматизация процесса управления интернет-форумом // Микроэлектроника и информатика – 2010. 17-я Всероссийская
межвузовская научно-техническая конференция студентов и аспирантов:
Тезисы докладов. М.: МИЭТ, 2010. С. 160.
6. Городилов А. В., Кондрашов О. О., Гагарина Л. Г. Система управления
версиями для свободной компьютерной анимации // Научная сессия МИФИ — 2010. Сборник научных трудов. МИФИ, 2010. С. 150–151.
7. Городилов А. В. Повышение эффективности передачи данных в одноранговой сети // Актуальные проблемы современной науки. 2011. № 2.
С. 200–201.
8. Городилов А. В. Подход к моделированию работы городских вычислительных сетей // Аспирант и соискатель. 2011. № 2. С. 183.
9. Городилов А. В. Разработка методики обмена данными и хранения данных
о структуре сети // Оборонный комплекс — научно-техническому прогрессу России (ВАК). 2011. № 3. С. 86–88.
10. Городилов А. В., Кононова А. И. Имитационное моделирование пиринговых сетей // Актуальные проблемы информатизации в науке, образовании
24
11.
12.
13.
14.
15.
16.
17.
18.
19.
и экономике — 2012. 5-я Всероссийская межвузовская научно-практическая конференция. М.: МИЭТ, 2012. С. 95.
Городилов А. В., Кононова А. И. Особенности разработки имитационных
моделей сетей передачи данных // Теоретические и практические аспекты развития современной науки [Текст]: материалы VI международной научно-практической конференции. М.: Изд-во «Спецкнига», 2012.
С. 89–92.
Городилов А. В., Кононова А. И. Применение свободного ПО для исследования поведения нелинейных динамических систем // Открытые технологии. Материалы восьмой международной конференции Linux Vacation
/ Eastern Europe 2012, Гродно, 07–10 июня 2012 г. Т. 1. Брест: 2012.
С. 31–35.
Городилов А. В., Кононова А. И. Проект пиринговой сети, учитывающей
особенности сети и требования приложений // Открытые технологии. Материалы восьмой международной конференции Linux Vacation / Eastern
Europe 2012, Гродно, 07–10 июня 2012 г. Т. 1. Брест: 2012. С. 41–43.
Городилов А. В., Кононова А. И., Шаньгин В. Ф. Особенности передачи
данных в децентрализованных пиринговых сетях // Изв. вузов. Электроника (ВАК). 2012. № 6(98). С. 95.
Городилов А. В., Кононова А. И., Шаньгин В. Ф. Особенности разработки
высокоэффективного протокола для пиринговых сетей // Естественные
и технические науки (ВАК). 2012. № 6. С. 467–469.
Городилов А. В., Кононова А. И. Визуализация результатов имитационного моделирования сети NS-3 через web-интерфейс. Материалы зимней
сессии международной конференции разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe 2013.
http://lvee.org/en/abstracts/54. 2013.
Городилов А. В., Кононова А. И. Подход к преподаванию десктопных
и сетевых возможностей GNU/Linux в университете // Открытые технологии: сборник материалов Девятой международной конференции разработчиков и пользователей свободного программного обеспечения Linux
Vacation / Eastern Europe 2013, Гродно, 27–30 июня 2013 г. / Под ред.
Д. А. Костюка. Брест: Альтернатива, 2013. С. 62–63.
Городилов А. В., Акулёнок М. В., Гагарина Л. Г., Кононова А. И. Программа самооценки системы менеджмента качества организации по ГОСТ-РИСО-9004-2010. Свидетельство о государственной регистрации программы для ЭВМ № 2012661306. 2012.
Городилов А. В., Акулёнок М. В., Гагарина Л. Г., Кононова А. И. Программа создания тестов самооценки системы менеджмента качества организации по ГОСТ-Р-ИСО-9004-2010. Свидетельство о государственной
регистрации программы для ЭВМ № 2012661305. 2012.
25
20. Городилов А. В., Гагарина Л. Г., Кононова А. И. Программа передачи
данных через компьютерную сеть с учётом особенностей сети (протокол
Городилова–Кононовой). Свидетельство о государственной регистрации
программы для ЭВМ № 2013614722. 2013.
21. Городилов А. В., Козин А. Г., Козина О. С. и др. Программа автоматизации
построения информационных хранилищ данных — АПХД. Свидетельство
о государственной регистрации программы для ЭВМ № 2013616694. 2013.
26
Подписано в печать:
Заказ №
Тираж 87 экз. Уч.-изд. л. 1,2 Формат 60х84 1/16
Отпечатано в типографии МИЭТ
124498, Москва, МИЭТ
1/--страниц
Пожаловаться на содержимое документа