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

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

Городнлов Алексей Владиславович

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

Специальность: 05.13.01—Системный анализ, управление и обработка информации (в приборостроении)

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

005537788

4 НОЯ 2013

Москва —2013

005537788

Работа выполнена на кафедре информатики и программного обеспечения вычислительных систем Национального исследовательского университета

«МИЭТ»

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

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

Гагарина Лариса Геннадьевна

доктор технических наук, профессор, заведующий кафедрой ИПОВС

Щагин Анатолий Васильевич

доктор технических наук, профессор, заведующий кафедрой САУиК МИЭТ

Нагин Дмитрий Александрович

кандидат технических наук, доцент, технический директор ООО «Интернет-системы»

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

Открытое акционерное общество «ОТИК-групп»

Защита состоится 10 декабря 2013 г. в 16 часов 00 минут на заседании диссертационного совета Д.212.134.02 при Национальном исследовательском университете «МИЭТ»: 124498 Москва, Зеленоград, проезд 4806, д. 5, МИЭТ.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «МИЭТ».

Автореферат разослан 8 ноября 2013 г.

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

Гуреев А. В.

Общая характеристика работы

Актуальность работы. Проблема обработки информации о физической структуре и загруженности компьютерной сети на прикладном уровне в настоящее время является актуальной. Современные компьютерные сети, в том числе Интернет, используют для передачи информации стандартизированный стек протоколов ТСРЯР. Многоуровневая структура стека TCP/IP и изоляция уровней друг от друга обеспечивают функционирование приложений независимо от физических свойств каналов передачи, что позволяет сократить время разработки приложений и уменьшить количество ошибок в них.

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

Популярные в настоящее время сети с р2р-структурой (peer-to-peer, пиринговые сети) реализованы на верхних уровнях модели OSI, соответствующих прикладному уровню стека TCP/IP. Они обладают гибкостью и простотой внедрения, но создают непостоянную и трудно предсказуемую нагрузку на сеть. Для повышения надёжности и быстродействия приложениям, работающим в пиринговых сетях, необходимо знать физическую структуру и загруженность сети. Исследованиям в области анализа, моделирования пиринговых сетей и обработки информации об их структуре с целью повышения эффективности их функционирования посвящен ряд работ зарубежных специалистов, таких как К. В. Росс, Д. Рубинштейн, Прадееп Судаме, Фу Сядун и других. Все эти работы ориентированы на разработку новых нестандартных протоколов сетевого и канального уровней, внедрение которых требует замены всех существующих приложений новыми.

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

Целью диссертационной работы является создание модели сети, методики учёта особенностей сети и требований сетевых приложений (МУчОС) и реализующих её алгоритмов, обеспечивающих повышение надёжности и быстродействия при передаче мультимедийных данных, а также разработка на их основе комплекса программных средств передачи данных (КПС ПД), реализующего динамическую маршрутизацию на верхних уровнях модели OSI.

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

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

- разработать методику учёта особенностей сети и требований сетевых приложений (МУчОС);

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

- верифицировать МУчОС для различных типов приложений и оценить её эффективность с помощью имитационного моделирования;

- разработать программную реализацию предложенной методики и алгоритмов в виде КПС ПД.

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

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

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

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

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

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

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

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

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

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

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

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

Предложенный подход к построению систем передачи данных позволяет разрабатывать сетевые приложения с высокой надёжностью и быстродействием. КПС ПД доведён до практического использования и применяется для автоматизации обмена данными в локальной сети ООО «Компнет». Самостоятельное практическое значение имеют:

- методика учёта особенностей сети и требований приложений на верхних уровнях модели 081 (МУчОС);

- комплексный алгоритм функционирования узла в пиринговой сети;

- алгоритм динамической маршрутизации в пиринговой сети;

- алгоритм демаршрутизации и безопасного выхода узла из сети;

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

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

диссертационной работы в учебном процессе МИЭТ и ООО «Компнет». Личный вклад автора.

Все основные результаты диссертационной работы получены автором самостоятельно, в том числе:

1. Предложена методика МУчОС, применимая на верхних уровнях модели 081.

2. Для верификации МУчОС разработана имитационная модель пиринговой сети произвольного масштаба с динамически изменяемой структурой.

3. Получена оценка эффективности разработанной методики МУчОС; показано, что использование МУчОС уменьшает количество отказов при передаче мультимедийных данных в 8 раз при повышении скорости передачи данных в 1,5-2 раза по сравнению с существующими системами.

4. Разработан комплексный алгоритм функционирования узла.

5. Разработан алгоритм динамической маршрутизации, основанный на распределённой модификации алгоритма А*; предложена эвристическая функция, зависящая от пропускной способности и загруженности каналов.

6. Разработан алгоритм демаршрутизации и безопасного выхода узла из сети.

7. Осуществлена программная реализация методики и алгоритмов в виде КПС ПД.

Реализация полученных результатов. Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры «Информатика и программное обеспечение вычислительных систем» НИУ «МИЭТ» и являлась составной частью НИР «Визуализация эволюции нелинейных динамических систем в области управления техническими и синер-гетическими объектами на основе информационных технологий и методов» в рамках АВЦП «Развитие научного потенциала высшей школы» (шифр ГБ 7.1534.2011). Работа заняла П место на проводившемся в 2013 году Третьем Международном молодёжном промышленном форуме «Инженеры будущего 2013» по номинации «Мой завод будущего».

Результаты диссертационной работы внедрены в учебный процесс кафедры ИПОВС в материалах курсов «Основы UNIX» и «Системный анализ и математическое моделирование», читаемых для старших курсов специальностей №230105.65, 230105.62, 230105.68; а также использованы в ООО «Компнет» при проектировании отказоустойчивой сети абонентских терминалов 1Р-телефонии.

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

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

2. Методика учёта особенностей сети и требований приложений на верхних уровнях модели OSI (МУчОС) позволяет эффективно использовать пропускную способность сети и повышает надёжность и быстродействие распределённой передачи мультимедийных данных в пиринговых сетях.

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

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

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 статьи — в изданиях, входящих в перечень ВАК.

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и приложений, содержащих листинги программ и акты о внедрении результатов работы. Общий объём диссертационной работы: 127 страниц машинописного текста, 9 таблиц и 41 рисунок.

Содержание работы

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

В первой главе проведен обзор современного состояния проблемы повышения надёжности и быстродействия пиринговой сети.

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

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

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

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

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

Формально пиринговая сеть представима как взвешенный сильно связный ориентированный граф, вершинами которого являются узлы сети, а рёбрами — соединяющие их каналы прикладного уровня. При этом граф, включающий все возможные соединения прикладного уровня (рис. 2, а), назовём максимальным графом пиринговой сети (G). На практике узел может установить соединение только с теми узлами, адрес которых хранится в его памя-

- уалы, участвующие а пиринговой сети

- широкополосный проводной или ууЬП-канал

" 20 или ЗС канал {более медленный или дорогой)

*-

■ пути передачи файла от узла А узлам В, С, И, Р, н в традиционной пиринговой сети

- пути передачи файла от узла А узлам В, с, О, Р, н в пиринговой сети с возможностью учета особенностей сети у

<р' с получают файл через В, который к ним ближе, н использует 0 и с для обхода МАТ что позволяет задействовать широкополосный канал)

Рис. 1. Физическая структура пиринговой сети

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

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

Структура рабочего графа <3 обеспечивает:

1. Поддержание целостности сети и устойчивости к отказам отдельных узлов или каналов связи, для чего числа вершинной связности х(<3) и рёберной связности А (С) должны значительно превышать вероятные количества одновременных отказов узлов и каналов соответственно.

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

3. Балансировка нагрузки на узлы и объёма данных, хранящихся на различных узлах, что ограничивает степень вершин С некоторой величиной п.

а)

б)

Рис. 2. Максимальный (а) и рабочий (б) граф пиринговой

сети

Для преобразования рабочего графа к виду, удовлетворяющему вышеперечисленным критериям и поддержания функционирования пиринговой сети разработана методика учёта особенностей сети и требований приложений (МУчОС), которая включает следующие основные стадии:

1. Каждый узел (назовём его X) набирает п известных узлов и продолжает поиск более близких узлов.

2. В случае, если узел X теряет связь с одним из связанных с ним узлов У, он ищет новый узел.

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

4. При преднамеренном выходе из системы узел X передаёт каждый известный ему адрес узла У{ следующему в списке известных и затем исключает переданный узел У{ из списка. Последний узел Уп не передаётся никому и исключается из списка известных. После очистки списка известных узлов узел X отключается от сети.

5. Последний узел Уп ищет себе в сети другой известный узел (в соответствии с пунктом 2).

6. Далее процесс стабилизируется по пункту 1.

Для реализации этой методики разработаны следующие алгоритмы:

- общий алгоритм работы узла в сети;

- динамической маршрутизации (построения пути передачи);

- демаршрутизации и безопасного выхода узла из сети.

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

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

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

В соответствии с формализованным представлением пиринговой сети как её рабочего графа (? С (3, информация о структуре сети представляет собой его матрицу инцидентности 1{С). При этом для реализации алгоритма построения кратчайшего пути в графе каждый узел должен иметь доступ к данным об остальных узлах сети, то есть ко всем элементам /((3). В памяти каждого узла Х{ хранится строка 1{С), соответствующая Х{ (1Х.(0)— информация об известных узлах), доступ к остальным данным осуществляется по сети.

Так как матрица 1(С?) и, соответственно, её строка /*,(£)> сильно разрежена и имеет большую размерность, она представляется в виде списка ненулевых ячеек. Для каждого ребра Х,У соответствующая ячейка 1Х {С) содержит идентификатор и адрес У, а также скорость передачи данных у(Хи У) и задержку (латентность) т(ХиУ) канала от Х{ до У. Для вычислений используется эффективная пропускная способность С{Хи У):

С(Хи У) = с„ • у(Хи У) + ст ■ т(Хи У) (1)

где коэффициенты с„ и Ст определяются решаемой задачей.

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

Алгоритм А* использует вместо расстояния ¿{X, У) между двумя произвольными узлами X и У метрику Ь(Х, У) —сумму расстояния с1(Х,У) и значения эвристической функции Д(У):

Ь(Х,У) = с1(Х,У) + Н(У) (2)

Рис. 3. Алгоритм работы узла во время построения пути

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

Н(Х)={авы х-С(Х,Т)+а„-С(Т,Х)+/ЗвЬ1Х-5(Х,Т) + ^-5(Т1Х))~1 (3) где X — текущий узел;

С(Х, Т) — пропускная способность исходящего канала связи узла Х\ С{Т, X) — пропускная способность входящего канала связи узла Х\ 5(Х, Т) — загруженность исходящего канала связи узла Х\

X) — загруженность входящего канала связи связи узла X. Коэффициенты авых, ам, /3„ы* и /Звх характеризуют класс сетевых приложений. Эвристическая функция должна отличаться для различных классов приложений, что и обеспечивается подбором коэффициентов. Это позволяет учесть особенности сети и приложений при построении маршрута.

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

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

Алгоритм демаршрутизации узла — процесс, реализующий четвёртую стадию методики учёта особенностей сети, описанной выше. Его схема представлена на рис. 4. При условии реализации процессов «поиск дополнительных узлов», «поиск первого узла», «передача узла другому узлу» со сложностью 0(1), не зависящей от целевого количества известных узлов п, алгоритм работы узла имеет линейную сложность О(п), что позволит выбирать п исключительно из соображения эффективности работы сети на большинстве современных персональных компьютеров. Это также упростит аппаратную реализацию при использовании во встраиваемых системах, например, в мобильных устройствах связи, если производительности такого устройства будет не хватать для поддержки работы в системе.

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

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

Рассмотрим различные стратегии выбора известных узлов, что определяет структуру рабочего графа и, в частности, степень его вершин п. Если каждый узел полностью хранит информацию о всей сети (й = <?), алгоритм построения кратчайшего пути может быть реализован полностью локально, что даёт выигрыш в скорости. Недостатком такой стратегии является большой объём памяти для хранения этой информации (0(|С?|2)) и необходимость извещать все узлы сети о любом изменении её структуры, что приводит к передаче большого количества служебных данных. Такая стратегия применима только для очень малых и стабильных сетей.

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

Рис. 4. Алгоритм демаршрутизации и безопасного выхода узла из сети

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

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

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

Обозначим Сненорм(а;) количество соединений длины х, то есть частоты длин, а ((х) —нормированное количество соединений, то есть долю соединений длины х в выборке:

С(х) =

Сненорм (%)

У, Сненорм 00

(4)

Это позволит сравнивать результаты, полученные на выборках разного размера.

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

0,3

О,'2

0,1

Ф) АШ: //іЛЇ V Ця !

ш/Аі \ ЦЩ/1 їх уШ і /Ш/ / \\СТД і ШЦ/ \\ш\|/ г/Л \ау\\і/ /¡/¡А 'л^Шіґ

X

10 15

а)

20

Рис. 5. Экспериментально полученное распределение длин

путей

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

Рассмотрим не частоты, а экспериментально полученные функции распределения (рис. 6, а)

Р(х) = Р(длина пути < х) = ((г).

¿=о

(5)

Г)

10

15

20

25

5

10

15

20

25

а)

б)

Рис. б. Экспериментальная функция распределения Р(х) и её аппроксимация

Полученные кривые наиболее точно аппроксимируются модифицированной функцией Лоренца (рис. 6, б):

В соответствии со свойствами распределения не менее 50% путей имеют длину, не превышающую пяти рёбер, и более 80% — не превышающую семи рёбер. Таким образом, при п = п5 для более 50% путей адрес конечного узла определяется локально, что ускоряет работу АДМ.

Определены цели для верификации и исследования эффективности алгоритмов, в том числе путём моделирования при различных значениях параметров.

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

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

N — общее количество переданных данных, файлов или сообщений. ЕЯ — количество отказов (потерянных файлов, сообщений, прерванных или

неустановленных вызовов). У/Т — скорость передачи: для потоковых данных и сообщений — достигнутая пропускная способность канала (кбит/с); для файлов — время передачи (с).

5У/5Т — относительная погрешность измерений.

1

(б)

Результаты имитационного моделирования

Таблица 1

N ЕЯ У/Т 6У/5Т

Существующие приложения Файловый сервер 500 13 157 0,12

Файлообменная сеть 500 55 94 0,06

Потоковое видео 1000 94 400 0,08

1Р-телефония 2000 82 321 0,10

Мгновенные сообщения 10000 19 0,23 0,01

Использование МУчОС и АДМ Файловый сервер 500 5 75 0,13

Файлообменная сеть 500 21 78 0,04

Потоковое видео 1000 10 523 0,04

1Р-телефония 2000 10 510 0,11

Мгновенные сообщения 10000 20 0,26 0,03

Предельное значение Файловый сервер 500 2 60 0,13

Файлообменная сеть 500 1 55 0,04

Потоковое видео 1000 10 523 0,04

1Р-телефония 2000 9 510 0,10

Мгновенные сообщения 10000 7 0,26 0,03

Исходя из данных таблицы 1 и параметров моделирования, были рассчитаны количество отказов на 10 000 соединений (рис. 7) и средняя скорость передачи данных (кбит/с) (рис. 8) для всех вариантов.

Файловый Файлообменная Потоковое 1Р-телефония Мгновенные сервер сеть видео сообщения

Рис. 7. Количество отказов на 10000 соединений в сетях различного типа

Из результатов проведённого эксперимента (рис. 7) сделан вывод, что надёжность файлообменной сети возрастает более чем в 2 раза при внедрении предложенной методики и алгоритмов. Файлообменная сеть состоит из множества независимых узлов, особенности взаимодействия которых современные системы практически неспособны учитывать.

Файловый Файлообменная Потоковое ІР-телефония Мгновенные сервер сеть видео сообщения

Рис. 8. Скорость передачи данных (кбит/с) в сетях различного типа

Из рис. 7-8 видно, что для большинства типов приложений выигрыш при внедрении методики МУчОС незначительно отличается от предельного, практически нереализуемого варианта с полным учётом всех особенностей взаимодействия всех узлов. На практике обмен служебными данными в этом случае вызвал бы перегрузку сети и, как следствие, большое количество отказов, что не учитывалось при моделировании, а предполагался идеальный обмен.

Для оценки масштабируемости моделировалась локальная сеть (local area network, LAN) из 100 узлов с топологией «звезда», сеть среднего масштаба (metropolitan area network, MAN) и глобальная (wide area network, WAN) с магистральными каналами с пропускной способностью 10 ООО МБит/с (табл. 2).

Средняя пропускная способность (битрейт, кбит/с)

Таблица 2

Протоколы Современная сеть (IPv4) Перспективные протоколы (IPv6, 802.11s)

Масштаб LAN MAN WAN LAN MAN WAN

Существующие приложения 100 75 48 110 105 95

Использование МУчОС и АДМ 100 85 80 115 120 115

Сделан вывод, что предложенная методика позволяет эффективно использовать преимущества перспективных протоколов, таких как 1Ру6 или 802.11 э, и не утратит своего значения с повсеместным внедрением этих протоколов. Наибольший прирост эффективности достигается для сетей масштаба города, но также значителен для локальных и глобальных сетей, что говорит о достаточно хорошей масштабируемости МУчОС.

Моделирование IP-телефонии и передачи потокового видео при различной нагрузке на сеть показало большую устойчивость МУчОС и АДМ по сравнению с существующим протоколом SIP (рис. 9).

■Ю-2

ея> ; ; | i

JV....................................................... —О— МУчОС+АДМ (ПК) МУчОС+АДМ (моб. устройства) -o-SlP

1 1

: —О N

200 400 GOO 800 1000 1200 1400 1S00 1800 2000 2200 2400 2600

Рис. 9. Относительное количество сорванных соединений (ERi) при различном количестве соединений в час (N)

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

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

В четвёртой главе приведена программная реализация предложенных методики и алгоритмов для практического приложения IP-телефонии. Продемонстрирована возможность эффективной интеграции сетевого модуля, разработанного на основе предложенных методики и алгоритмов в систему, использующую другие COTS'-компоненты. Среди этих компонентов библиотека для сжатия аудиоданных в реальном времени Speex, графический интерфейс на основе wxWidgets и стек протоколов TCP/IP.

На рис. 10 представлена структурная схема КПС ПД.

Для реализации данной структуры потребуется разработать следующие компоненты, которые не доступны в СОТЭ-зиде:.

1 COTS (Commercial off-the-shelf, коробочный программный продукт) — технология (индустриальная технология), ориентированная на широкий круг специалистов-непрофессионалов в области информационных технологий, и использующая единые автоматизированные методы разработки, сопровождения и модернизации систем автоматики на основе использования готовых объектно-ориентированных средств (инструментов) и компонентов (кубиков).

о

тз к о

О ->

•а

я н

-а р>

^

Я

О

я

закодированный паи

пакеты для передачи""]

"передачи

шаэ эаллллсизр эпннеУ аиннакі?

поденная информация

функциональный блок

распределенные алгоритмы и хранилище данных

сетевой блок

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

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

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

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

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

- адрес узла назначения;

- адрес узла отправления;

- список промежуточных узлов;

- тип сообщения (служебное или информационное);

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

- срок актуальности сообщения (ТТЬ).

О байт 8 байт 16 байт 24 байта 32 байта 40 байт

версия протокола адрес назначения адрес отправления идентификатор сообщения тп 5И. список адресов 11 промежуточных\\ список важных 1 \ сообщений \\ содержание сообщения \

узлов ]]

Рис. 11. Формат дейтаграммы протокола

Информационное сообщение должно содержать:

- формат и назначение передаваемых данных;

- фрагмент кодированного звукового потока, или другие полезные данные;

- порядковый номер сообщения в потоке.

Служебное сообщение (рис. 11, а, Ь) используется в следующих случаях:

- построение пути передачи информационных сообщений по алгоритму А*;

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

- построение альтернативного пути передачи;

- измерение задержки передачи;

- сообщение о выходе узла из системы;

- организация обмена известными узлами;

О байт 8 байт

а)

сообщения

0 байт 8 байт 16 байт

адрес рас-

тип узла стояние

сообщения для До

передачи узла

О байт 8 байт 16 байт 24 байта

тип порядковый номер блока размер блок (

сообщения блока полезных \

данных данных данных

Рис. 12. Содержание сообщения протокола: а — большинство служебных сообщений, Ъ — служебное сообщение для обмена известными узлами, с — информационное сообщение

- сообщение о пропускной способности канала между двумя узлами.

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

Сообщения могут передаваться как с использованием транспортного протокола без гарантии доставки, например UDP из стека TCP/IP, так и с гарантией доставки (TCP).

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

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

В приложениях приведены фрагменты кода разработанного КПС ПД и акты внедрения результатов.

Основные результаты и выводы

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

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

При этом получены следующие основные научные и практические результаты:

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

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

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

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

- комплексный алгоритм функционирования узла;

- алгоритм динамической маршрутизации, основанный на распределённой модификации алгоритма А* (АДМ);

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

5. Разработана имитационная модель пиринговой сети различного масштаба и назначения с динамически изменяемой структурой.

6. На основе имитационного моделирования выполнена верификация МУчОС и алгоритмов, а также получена оценка их эффективности.

7. Исследована возможность улучшения качества работы различных классов сетевых приложений при применении МУчОС. Показано, что наиболее перспективное приложение МУчОС передача мультимедийных данных (IP-телефония и потоковая трансляция видео и звука).

8. Создана программная реализация предложенной методики и алгоритмов в виде программного комплекса интернет-телефонии (КПС ПД), учитывающего особенности сети и обеспечивающего снижение количества отказов при передаче звука в 8 раз по сравнению с существующими системами при повышении быстродействия в 1,5-2 раза.

9. Результаты работы внедрены в учебный процесс кафедры ИПОВС в материалах курсов «Основы UNIX» и «Системный анализ и математическое моделирование», а также использованы в ООО «Компнет» при про-

ектировании отказоустойчивой сети абонентских терминалов ГР-телефо-нии.

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

1. Городилов А. В., Ананьина Е. В. Программно-аппаратная система пиринговой передачи видео // Всероссийский молодежный научно-инновационный конкурс-конференция «Электроника 2006»: тезисы докладов конференции. М.: МИЭТ, 2006. С. 38.

2. Городилов A.B., Ананьина Е.В. Алгоритм управления пиринговой сетью // Микроэлектроника и информатика — 2007. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. М.: МИЭТ, 2007.

3. Городилов A.B., Гагарина Л.Г., Ананьина Е.В., Апрелов С. А. Эстафетная передача видеосигнала в компьютерных сетях общего пользования // Межотр. науч.-техн. сборник «Оборонный комплекс — научно-техническому прогрессу России» (ВАК). 2007. № 2. С. 51-54.

4. Городилов А. В. Новые информационные технологии преобразования графических форматов для web-анимационного проектирования // Иннова-тика и информационные технологии: проблемы, перспективы, решения: Сборник научных трудов / Под ред. д. т. н.,'проф. Л. Г. Гагариной; МИЭТ. М.: МИЭТ, 2009. С. 70-73.

5. Городилов A.B. Автоматизация процесса управления интернет-форумом // Микроэлектроника и информатика — 2010. 17-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. М.: МИЭТ, 2010. С. 160.

6. Городилов А. В., Кондратов О. О., Гагарина JI. Г. Система управления версиями для свободной компьютерной анимации // Научная сессия МИФИ— 2010. Сборник научных трудов. МИФИ, 2010. С. 150-151.

7. Городилов А. В. Повышение эффективности передачи данных в одноранговой сети // Актуальные проблемы современной науки. 2011. № 2. С. 200-201.

8. Городилов A.B. Подход к моделированию работы городских вычислительных сетей // Аспирант и соискатель. 2011. № 2. С. 183.

9. Городилов А. В. Разработка методики обмена данными и хранения данных о структуре сети // Оборонный комплекс — -научно-техническому прогрессу России (ВАК). 2011. №3. С. 86-88, '

10. Городилов А. В., Кононова А. И. Имитационное моделирование пиринговых сетей // Актуальные проблемы информатизации в науке, образовании

и экономике — 2012. 5-я Всероссийская межвузовская научно-практическая конференция. М.: МИЭТ, 2012. С. 95.

11. Городилов A.B., Кононова А.И. Особенности разработки имитационных моделей сетей передачи данных // Теоретические и практические аспекты развития современной науки [Текст]: материалы VI международной научно-практической конференции. М.: Изд-во «Спецкнига», 2012. С. 89-92.

12. Городилов A.B., Кононова А.И. Применение свободного ПО для исследования поведения нелинейных динамических систем II Открытые технологии. Материалы восьмой международной конференции Linux Vacation / Eastern Europe 2012, Гродно, 07-10 июня 2012 г. Т. 1. Брест: 2012. С. 31-35.

13. Городилов A.B., Кононова А.И. Проект пиринговой сети, учитывающей особенности сети и требования приложений // Открытые технологии. Материалы восьмой международной конференции Linux Vacation / Eastern Europe 2012, Гродно, 07-10 июня 2012 г. Т. 1. Брест: 2012. С. 41^3.

14. Городилов A.B., Кононова А.И., Шаньгин В.Ф. Особенности передачи данных в децентрализованных пиринговых сетях // Изв. вузов. Электроника (ВАК). 2012. № 6(98). С. 95.

15. Городилов А. В., Кононова А. И., Шаньгин В. Ф. Особенности разработки высокоэффективного протокола для пиринговых сетей II Естественные и технические науки (ВАК). 2012. № 6. С. 467-469.

16. Городилов A.B., Кононова А.И. Визуализация результатов имитационного моделирования сети NS-3 через web-интерфейс. Материалы зимней сессии международной конференции разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe 2013. http://lvee.org/en/abstracts/54. 2013.

17. Городилов A.B., Кононова А.И. Подход к преподаванию десктопных и сетевых возможностей GNU/Linux в университете // Открытые технологии: сборник материалов Девятой международной конференции разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe 2013, Гродно, 27-30 июня 2013 г. / Под ред. Д. А. Костюка. Брест: Альтернатива, 2013. С. 62-63.

18. Городилов А. В., Акулёнок М. В., Гагарина JI. Г., Кононова А. И. Программа самооценки системы менеджмента качества организации по ГОСТ-Р-ИСО-9004-2010. Свидетельство о государственной регистрации программы для ЭВМ №2012661306. 2012.

19. Городилов A.B., Акулёнок М.В., Гагарина Л.Г., Кононова А.И. Программа создания тестов самооценки системы менеджмента качества организации по ГОСТ-Р-ИСО-9004-2010. Свидетельство о государственной регистрации программы для ЭВМ № 2012661305. 2012.

20. Городилов A.B., Гагарина Л.Г., Кононова А.И. Программа передачи данных через компьютерную сеть с учётом особенностей сети (протокол Городилова-Кононовой). Свидетельство о государственной регистрации программы для ЭВМ № 2013614722. 2013.

21. Городилов А. В., Козин А. Г., Козина О. С. и др. Программа автоматизации построения информационных хранилищ данных — АПХД. Свидетельство о государственной регистрации программы для ЭВМ № 2013616694. 2013.

Подписано в печать:

Заказ № ? 6 Тираж 87 экз. Уч.-изд. л. 1,2 Формат 60x84 1/16 Отпечатано в типографии МИЭТ 124498, Москва, МИЭТ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«МИЭТ»

Городилов Алексей Владиславович

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

Специальность: 05.13.01 - Системный анализ, управление и обработка

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

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

доктор технических наук, профессор

Гагарина Л. Г.

Москва —2013

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

04201451788

информации (в приборостроении)

ДИССЕРТАЦИЯ

Содержание

Введение....................................................................9

Глава 1. Анализ современного состояния компьютерных сетей . 17

1.1. Модели межсетевого взаимодействия..........................18

1.2. Анализ существующих протоколов передачи данных .... 21

1.2.1. Протоколы сетевого, транспортного и сеансового уровней.........................23

1.2.2. Протоколы прикладного уровня...........24

1.3. Проблема одновременного учёта особенностей сети и требований приложений в сложной системе передачи данных . 26

1.4. Использование компонентно-ориентированного подхода

для построения сетевых приложений.............28

1.5. Выбор уровня для решения задачи передачи данных с учётом особенностей сети.....................30

1.6. Надёжность сети передачи данных ..............32

1.7. Постановка задачи диссертации................35

Выводы по главе............................36

Глава 2. Разработка методики и алгоритмов обеспечения качества передачи данных на верхних уровнях модели 081.....38

2.1. Исследование возможностей определения свойств сети

с верхних уровней модели ОБ1.................39

2.2. Использование информации о структуре сетей различной конфигурации..........................45

2.3. Математическая модель пиринговой сети......................51

2.4. Распределённое представление данных о структуре сети . . 57

2.5. Разработка методики обмена и хранения данных о структуре сети..............................59

2.6. Комплексный алгоритм функционирования узла сети .... 62

2.7. Алгоритм динамической маршрутизации в сети (АДМ) ... 65

2.8. Алгоритм демаршрутизации узла...............70

Выводы по главе............................72

Глава 3. Экспериментальное исследование параметров передачи

различных видов сетевого трафика................................74

3.1. Определение объёма списка известных узлов.........74

3.2. Экспериментальное исследование распределения длин маршрутов........................................................76

3.3. Цели, задачи и методы экспериментального исследования . 84

3.4. Моделирование различных типов приложений........86

3.5. Цели, задачи и методы экспериментального исследования . 88

3.6. Оценка масштабируемости МУчОС и АДМ .........90

3.7. Моделирование работы системы передачи данных в глобальной сети для оценки универсальности МУчОС.....92

3.7.1. Оценка универсальности и эффективности МУчОС 92

3.7.2. Оценка предельных значений скорости и надёжности 94

3.8. Моделирование влияния загруженности каналов связи на надёжность сети.........................99

Выводы по главе............................103

Глава 4. Программная реализация предложенных решений . . . 106

4.1. Требования к программной реализации............106

4.1.1. Системообразующие требования к параметрам

и функциям.......................106

4.1.2. Технические требования ...............106

4.1.3. Состав и параметры технических средств программной реализации МУчОС и АДМ для ПК . . . 108

4.1.4. Состав и параметры технических средств программной реализации МУчОС и АДМ для мобильных устройств.....................110

4.2. Реализация предложенных методики и алгоритмов для практического приложения IP-телефонии...........111

4.3. Разработка протокола прикладного уровня передачи данных с учётом особенностей сети (протокол Городи-лова-Кононовой)........................115

4.4. Программный интерфейс сетевого компонента КПС ПД . . 120

4.5. Пользовательский интерфейс КПС ПД........... . 123

4.6. Case study мобильного IP-телефона, использующего протокол Городилова-Кононовой..................124

4.6.1. Аппаратное ускорение вычислительно сложных фрагментов.......................124

4.6.2. Архитектура платформы...............125

4.6.3. Компоненты и стоимость изготовления.......126

Выводы по главе............................126

Заключение................................128

Литература................................130

Приложение А. Акты внедрения...................139

Приложение Б. Результаты экспериментального исследования распределения длин маршрутов передачи данных в пиринговой сети...................................142

Приложение В. Сообщения протокола Городилова-Кононовой версии 1.0.1.4 .............................148

Приложение Г. Листинги фрагментов КПС ПД..........153

Приложение Д. Копия свидетельств о регистрации программ для ЭВМ, дипломов и сертификатов..................161

API

COTS

LAN

MAN

NAT

WAN

Основные обозначения и сокращения

Application programming interface — интерфейс программирования приложений.

Commercial off-the-shelf, коробочный программный продукт — серийный компонент промышленного назначения.

Local area network, локальная сеть.

Metropolitan area network, городская сеть.

Network Address Translation — механизм в сетях TCP/IP, позволяющий преобразовывать IP-адреса транзитных пакетов, а также маршрутизатор, реализующий этот механизм.

Wide area network, глобальная сеть.

Битрейт Скорость прохождения битов информации.

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

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

Демаршрутизация Процесс корректного отключения узла от сети.

Жёсткое ограничение Ограничение, которое не может быть нарушено.

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

Латентность Задержка между посылкой запроса и фактическим получением пакета удалённой стороной.

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

Метрика Функция, определяющая расстояния в метрическом пространстве.

Мультимедийные данные Аудио- и видеоданные.

Мягкое ограничение Ограничение, которое может быть нарушено в течении некоторого периода времени.

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

Отказоустойчивость Способность системы скрыть от пользователя отказ отдельных её элементов.

ПК Персональный компьютер.

ПО Программное обеспечение.

Пиринговая (одноранговая, децентрализованная) сеть

Компьютерная сеть, основанная на равноправии участников (англ. реег-Ю-реег, р2р — равный к равному). В пиринговой сети отсутствуют выделенные серверы, а каждый узел (реег) является как клиентом, так и сервером.

Пропускная способность Максимально допустимая скорость обработки трафика, которая определяется стандартами сети.

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

Узел Компьютер, терминал или другое устройство, подключён-

ное к сети.

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

Хост Устройство, предоставляющее сервисы формата «клиент-

сервер» в режиме сервера по каким-либо интерфейсам и уникально определённое на этих интерфейсах.

Целевой узел Узел, с которым необходимо установить соединение.

Введение

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

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

Популярные в настоящее время сети с р2р-структурой (peer-to-peer, пиринговые сети) реализованы на верхних уровнях модели OSI, соответствующих прикладному уровню стека ТСРЛР. Они обладают гибкостью и простотой внедрения, но создают непостоянную и трудно предсказуемую нагрузку на сеть. Для повышения надёжности и быстродействия приложениям, работающим в пиринговых сетях, необходимо знать физическую структуру и загруженность сети. Исследованиям в области анализа, моделирования пиринговых сетей и обработки информации об их структуре с целью повышения эффективности их функционирования посвящён ряд работ зарубежных специалистов, таких как К.В.Росс, Д.Рубинштейн [15], Прадееп Судаме [33], Фу Сядун [35, 36] и других. Все эти работы ориен-

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

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

Целью диссертационной работы является создание модели сети, методики учёта особенностей сети и требований сетевых приложений (МУчОС) и реализующих её алгоритмов, обеспечивающих повышение надёжности и быстродействия при передаче мультимедийных данных, а также разработка на их основе комплекса программных средств передачи данных (КПС ПД), реализующего динамическую маршрутизацию на верхних уровнях модели 081.

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

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

- разработать методику учёта особенностей сети и требований сетевых приложений (МУчОС);

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

- верифицировать МУчОС для различных типов приложений и оценить её эффективность с помощью имитационного моделирования;

- разработать программную реализацию предложенной методики и алгоритмов в виде КПС ПД.

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

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

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

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

2. Предложена методика учёта особенностей сети и требований сетевых приложений на верхних уровнях модели ОБ1 (МУчОС), повышающая надёжность и быстродействие передачи мультимедийных данных в распределённых пиринговых сетях.

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

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

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

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

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

/ *

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

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

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

Предложенный подход к построению систем передачи данных позволяет разрабатывать сетевые приложения с высокой надёжностью и быстродействием. КПС ПД доведён до практического использования и применяется для автоматизации обмена данными в локальной сети ООО «Компнет».

Самостоятельное практическое значение имеют:

- методика учёта особенностей сети и требований приложений на верхних уровнях модели 081 (МУчОС);

- комплексный алгоритм функционирования узла в пиринговой сети;

- алгоритм динамической маршрутизации в пиринговой сети;

- алгоритм демаршрутизации и безопасного выхода узла из сети;

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

- программная реализация методики и алгоритмов в виде КПС ПД. Практическая значимость подтверждена актом внедрения результатов диссертационной работы в учебном процессе МИЭТ и ООО «Комп-нет».

Личный вклад автора.

Все основные результаты диссертационной работы получены автором самостоятельно, в том числе:

Предложена методика МУчОС, применимая на верхних уровнях модели 081.

2. Для верификации МУчОС разработана имитационная модель пиринговой сети произвольного масштаба с динамически изменяемой структурой.

3. Получена оценка эффективности разработанной методики МУчОС; показано, что использование МУчОС уменьшает количество отказов при передаче мультимедийных данных в 8 раз при повышении скорости передачи данных в 1,5-2 раза по сравнению с существующими системами.

4. Разработан комплексный алгоритм функционирования узла.

5. Разработан алгоритм динамической маршрутизации, основанный на распределённой модификации алгоритма А*; предложена эвристическая функция, зависящая от пропускной способности и загруженности каналов.

6. Разработан алгоритм демаршрутизации и безопасного выхода узла из сети.

7. Осуществлена программная реализация методики и алгоритмов в виде КПС ПД.

Реализация полученных результатов. Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры «Информатика и программное обеспечение вычислительных систем» НИУ «МИЭТ» и являлась составной частью НИР «Визуализация эволюции нелинейных динамических систем в области управления техническими и синергетическими объектами на основе информационных технологий и методов» в рамках АВЦП «Развитие научного потенциала высшей школы» (шифр ГБ 7.1534.2011). Работа заняла II место на проводившемся в 2013 году Третьем Международном молодёжном промышленном форуме «Инженеры будущего 2013» по номинации «Мой завод будущего».

Результаты диссертационной работы внедрены в учебный процесс кафедры ИПОВС в материалах курсов «Основы UNIX» и «Системный анализ и математическое моделирование», читаемых для старших курсов специальностей №230105.65, 230105.62, 230105.68; а также использованы в ООО «Компнет» при проектировании отказоустойчивой сети абонентских терминалов 1Р-телефо