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

005007789

На правах рукенш

/5^

Коваленко Татьяна Анатольевна

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

Специальность «05.13.15» Вычислительные машины, комплексы и компьютерные сети

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

2 С ЯНЗ Ы1

Самара-2012

005007789

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

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

Акчурин Эдуард Александрович

Официальные оппоненты: доктор технических наук, профессор

Орлов Сергей Павлович

Официальные оппоненты: доктор технических наук, доцент

Горячкин Олег Валерьевич

Ведущая организация - Самарский государственный университет (ФГБОУ ВПО СамГУ)

Защита состоится «22» февраля 2012 г. В 15.00 часоз на заседании диссертационного совета Д 219.003.03 при Поволжском государственном университете телекоммуникаций и информатики по адресу: 443010, г. Самара, ул. Л. Толстого, д.23.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО ПГУТИ.

Отзывы на автореферат в:двух экземплярах, заверенных печатью, просим направлять по адресу: Россия, 443010, г. Самара, ул. Льва Толстого, 23 на имя ученного секретаря диссертационного совета Д 219.003.03.

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

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

Диссертационного совета Д 219.003.03 Доктор технических наук, профессор /

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

Главная задача маршрутизации - это повышение скорости передачи данных в компьютерных сетях. Наиболее часто критерием выбора маршрута является время передачи данных, которое зависит от многих факторов: пропускной способности каналов, интенсивности трафика, который может изменяться с течением времени, загрузки интерфейса буфера и.т.д. Сложность проблемы маршрутизации заключается в ее многофакторности. Учет всех факторов сводит задачу маршрутизации к решению задачи оптимального распределения ресурсов сети. Значительный вклад в решение проблемы маршрутизации внесли отечественные и зарубежные ученые: В.Г. Олифер, H.A. Олифер, Брайн Хилл, Столинпс В., Стивен Браун, Оливер Ибе, Лихтциндер Б.Я., Росляков A.B., Мэтт Хайден и другие.

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

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

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

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

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

Основные задачи исследования: • анализ существующих алгоритмов маршрутизации в компьютерных сетях (КС) для решения задачи ускорения прохождения пакетов;

• разработка современного подхода, основанного на методах интеллектуального анализа данных;

• разработка интегрированной системы маршрутизации, с совместным использованием нечеткой логики (НЛ), нейронных сетей (НС) и стандартных маршрутизаторов для компьютерных сетей;

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

• обоснование области эффективного применения предложенной ИСМ Методы исследования

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

т?и1%^°гЙТМломЕРтаб0та данных Па°ДИЛ0СЬ с использованием пакетов МАТив, $(аЫ,са, ОРЫЕГ и разработанного автором программного обеспечения

Научная новизна заключается в том, что: 1- Предложена интегрированная система маршрутизации, отличающаяся совме-стшм использованием стандартных маршрутизаторов, подсистемы нечеткой логики и нечеткого вывода, что позволяет находить оптимальные по критерию времени маршруты передачи пакетов в компьютерных сетях 7„е/™Н0 нов^ представление объема трафика в виде нечеткой величины и разработана формализованная модель сети, позволяющая оперировать прогнозируемыми данными о трафике и вычислительной загрузке сети ™™жена методика исследования процессов маршрутизации в компьютерных сетях, отличающаяся совместным использованием нечеткой логики и нейронных сетей как инструмента моделирования. Достоверность результатов работы

™ВерН0СТЬ НЭУЧНЬ,Х положений Рекомендаций и выводов подтверждена путем сравнения статистического материала, собранного в процессе мовднга

профа1^?йИсредГУЛЬТаТаМИ МОдешрования <™чной сети в разработанной

Личный вклад: предложена Интегральная система маршрутизации теорети-™ ™Г6СК°е исследо!ание ^Чессов маршрутизации с помощ ю совме-шГ™ьзованИЯ ниткой логики и нейронной сети, применение нечеткой

логики и нейронной сети как инструмент для моделирования

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

ппп1^1ФГаННаЯ система маРшРУ™зации, отличающаяся совместным ис-четаговыводаСТаНДаРТНЫХ Маршрутизаторов' ^истемы нечеткой ложки и не-

пи,™И!!0е представление объема трафика в виде нечеткой величины и форма-

;п ГЛа1МОДеЛЬ Се™' "озволяюЧая оперировать прогнозируемыми данными о трафике и вычислительной зафузке сети.

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

• разработана интегрированная система маршрутизации, которая обеспечивает ускорение процесса передачи данных в многосегментных компьютерных сетях;

• предложенный метод маршрутизации в КС на основе ИСМ обеспечивает повышение эффективности доставки пакетов для сетей сложной конфигурации в условиях локальных перегрузок;

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

Реализация результатов работы Основные результаты, полученные в ходе работы над диссертацией, использовались при создании компьютерных сетей ООО «Вопготехпласт», ООО «Самара - Авиагаз», ОАО СЗ «Экран» для определения загруженности сети, управления трафиком и распределения данных по сети. Результаты исследований также используются в учебном процессе и подтверждены актами о внедрении.

Апробация работы Основные положения, теоретические выводы и практические рекомендации диссертационной работы докладывались и обсуждались на заседаниях кафедры «Информатика и вычислительная техника» ФГОБУ ВПО ПГУТИ, а так же на конференциях и семинарах различного уровня:: XV Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, Самара 2008; XVI Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, Самара 2009; XVII Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов, Самара 2010; XVIII Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов Самара 2011; X Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения», Пенза 2009; XI Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения», Пенза 2009; XII Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения», Пенза 2010, Публикации

По теме диссертации опубликовано 14 печатных работ, в том числе 4 статьи в научных журналах, входящих в перечень ВАК РФ, 3 научных статьи на Международных конференциях, 7 тезисов и докладов.

Структура и объем диссертации. Диссертационная работа состоит из введения 4 глав и заключения, изложенных на 125 страницах машинописного текста, содержит 79 рисунков, 14 таблиц, список литературы из 105 наименований. Краткое содержание работы

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

достоверность материалов исследования, представлены методы исследования основные положения, выносимые на защиту. Кратко изложено ¿дерГи"

В главе 1 выполнен анализ современных методов маршрутизации Показано что на сегодняшний день критерии оценки методов маршрЕ™ отдельные частные цели их разработки: оптимальность^S^JSbSI

—'ЖИВуЧбаь И Юность, сходимость и гибкость JopLTZöo e также показано, что используемые методы зависят в общем случаГот про!оша

ПРИНЯТ°ГО 8 КС' 0б1чая развития Маршрутизаторов

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

тов может решаться с использованием новых подходов. Одним из таких пол*™™

ГГ Й ИСМ> ^^"нГГеЖд8

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

mtomZZlT тШОаЩ МарШрута'делать Р^Фаничение маршргно информации, обеспечить ускорение прохождение пакетов п

и, iL 2 предложена и описана ИСМ с использованием НЛ и НС и обоснована область ее применения в компьютерных сетях. ИСМ представляет ISZI

рГМа1Е?1РееГ0ВаННЫХ ЗНаЛИ™Чес-м при«™ ™

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

«JW™ принадлежности нечеткой логики формируются двумя

ГЙК=Г СТаТИСТИЧеШХ ИЛИ ^периментальныхданньГпри Гда НИИ ИСМ предлагается использовать в качестве функции принадлежности пап£

rtEESS ffiSiT1 ПЗРаМеТРЫ

ритма ofyla^^ —' ** «ЧГ— с -о^ю 2о-

"РТЖеННаЯ интегрированной системы маршрутизации позволит

н иТн'й сГюТЖ Г" М0Г Раб0ТЭТЬ с ««иГстемамП нейронной сетью (Рисунок 1). В данной структуре маршрутизатор работает еле-

«им образом: после обработки информации комму?ГциоЗМ бтшм она поступает на маршрутный процессор, затем на блок фа ифшцш- где чеше величины преобразуются в нечеткие. Затем нечеткие величинь. описывайся с сГп—Т™™ ПвреМеННЫХ 8 «системе "Ченок принятых решений» "0СТуПаЮТ В Нейронн^ сеть' г«е с применений «нХ ра правил и нечетких термов» строится нейронная сеть, после чего идет обоатный

НеЧ6ТКИХ ееличин в че™е значения при ГоГбш едефазификации», поступившие данные обрабатываются блоков выбора и пГе

We ПР°ИСХ0ЯЙТ новой таблицы

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

Рисунок 1 Интегрированная система маршрутизации Предлагаемый метод формирования сети с помощью ИСМ обеспечивает ряд преимуществ: перенаправление информации по сети в автоматическом режиме; стабилизация загруженности сети; упрощенный алгоритм формирования сети; сведение человеческого фактора при составлении таблиц маршрутизации к минимуму.

В Главе 3 исследуется ИСМ. На основе анализа существующих методов маршрутизации разработана модель, которая представляет собой совокупность основных компонентов ИСМ: М1 = <Тс, О, Рт, 1> - стандартная модель маршрутизации, где, Тс - топология сети; О - пропускная способность сети; Рт - метрика маршрута; 2 - заданные компоненты сети,

М2 =< Тс, О, Рт, Ткем, Рисм, Иисм> - модель разработанной ИСМ. Во вторую модель добавлены обобщенные переменные, которые характеризуют ИСМ: Тисм - топология сети полученная с помощью ИСМ; Рисм - метрика маршрута, определенная с помощью ИСМ; 2исм - новые заданные компоненты интегрированной системы маршрутизации.

Во второй модели объем трафика можно определить как компонент входящий в Ъкм и представить в виде нечеткого отношения, согласно правилу «Если х есть А, то у есть В нечеткое отношение К» задается декартовым произведением, их х иу где их(иу) - универсальное множество входной (выходной) переменной». Расчет нечеткого отношения Й осуществляется так:

МяО.у) = тт(Ол(>),,ЦвО)), О-У) е 1>ххиу (1)

где цц - Функция принадлежности элементов х, у подмножеству я

Тогда все входящие и выходящие термы множества будут состоять т

¡Е£ЗЕГ(М)| а,"а9е и ,Р)'Тада"

• Если х1=М и х2=М, то у=М;

• Если х1=С и х2=С, то у=С;

• Еслих1=Рих2=Р, то у=Р;

пп»пгг*а8ра6°1е "р08еден анашз второй модеш- СлеДУет °™етить, что модель представляет собой сложный комплекс, описания которого в явном аналитическом

виде не существует. Для проверки работоспособности и подтверди эГешв

мод~ - —=

Анализ разрабатываемой ИСМ происходит в сопоставлении с известными Д ЖГ — «ится анализ процесса Га^

С0СТаВН0Й №0, исполь-

цтп Проанализировав работу сети при разной заФуженности приходим к выводу что при увеличении объема передаваемой информации нагрузка на участках сети тановится неравномерной. Появляются критические участки где нэгр^Гдоход до 95%, при малой загруженности других возможных путей (Рисунок 2)

Рисунок 2 Модель сети

Для подтверждения адекватности модели, просчитан маршрут с помощью алгоритма Деикстры, который применяется в стандартных маршрутизаторах и ПР=Г3аТ0Р направляет пакеты согласно данным таблицы маршрутизации

ТГГ" ПЗКеТ0В Происходит на 0СН08е однотипнь.х графов ЕуГк 2). Маршрут Р в данном случае представлен взвешенным фафомЕ е) непределен как некоторый {Щ путь по формуле (2): }

Ел Е-> ¥.

р = у0 Л ц 4 ... =

Длина маршрута Р определена как с(Р) по формуле (3V с(Р)=с(Е1)+с(Е2)+..лс(Е4)

с6(Р)=с(Е1)+с(Е2)+с(Е9) Время прохождения пакетов по сети определяется для каздого маршрута (4): с =(* + ^+а_2£а ^

лЯи!,е,1=-°£Ск" Задержка передачи в шнт связи; Ь = «орость передачи данных, 8р - 6104 бит - размер пакета данных, совершающего переход; 5о„,= 320

бит-длина очереди в маршрутизаторе, а =1.....4- количество переходов

"С1ЛЬ30ВаНЫ ДаННЫе' хаРактеРиые Д™ ВС со скоростью 100 Мбит/с.' Результаты расчетов представлены в таблице 1.

-Таблица 1 Путь и время прохождения пакетов по сети

ЦУГЬ __ * I уу1 | уу2 ууЗ Туй" ш5

Трафик (Мбит) 15 1 - ^--1

w6

Время (мкс)

490

78 187

56

59

64

284

329

71

214

52

D -^- —*1 193 jas

пя JT™™ ИССЛедоаания показали'что необходима система маршрутизации аЮЦИИ СЛедуЮЩие паР^етры: приоритет сообщений, возмото

ES^SXT" КаНаП0В' " -И» "о S

пи 470 ИС.М наиболее подходит для решения поставленной задачи. Це-

ZSSZZÍZ" <ЖГеМЫ ~ ЭТ° 0ПТИМИЗЗЧИЯ скорос™- «ение потер

пакетов, уменьшение ожидания в сети и поддержка различных классов загрузш :тГГ^"ГДпеЛеНИе инФ°РмаЧионных потоков при возникновении вн* ДЛЯ моделиР°вания вышеописанных ситуаций необходимо определить описанные характеристики сети с помощью нечетких параметров

rS'SrТ6МУ НеЧеТК0Г° МН0ЖеСтаа Ис« Данные для

ния ИСМ брались из модели с простым маршрутизатором с целью сравнения по-

Г==Т0В- °Ценки «W™ ивыходшхперемен

пе ехоГю^ терм-множества: х1 - максимальное количество

Z ¡S v", ' Р Д 66 количество пеРех°Д°в КС; минимальное количество перехо-~СК0р0сть пеРедачи ^формации по сети максимальная Т, скорость ¡КГ ИЙ°РМаЦИИ П0 сети средняя ТС, минимальная скорость передачи информации МТ; у - максимальное время прохождения пакета G, среднее время

356

№ х1 х2 у

1 К МТ G

2 КС Т GC

3 КС тс GC

4 мк т MG

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

• Если х1 = К и х2=МТ, то y=G;

• Если х1=КС и х2=Т, то y=GC;

• Если х1=КС и х2=ТС, то y=GC;

• Если х1=МК и х2=Т, Toy=MG;

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

По данным полученным, при расчете системы нечеткого логического вывода построим НС, которая - является адаптивной системой, состоящей из узлов и направленных связей. НС - состоит из четырех слоев нейронов.

Слой 1 (inputmf) представлен радиальными базисными нейронами и моделирует функции принадлежности Выходы узлов этого слоя представляют собой значения функции принадлежности при конкретных значения входов (х1, х2), терм множества (х1 -у К, КС, МК; х2 —Т, ТС, МТ)

Слой 2 (rule) моделирует логическую связку. Выходами нейронов этого слоя являются степени истинности предпосылок каждого правила базы знаний системы, вычисляемые по формулам: =Л:(*1)алщ*2)ЛС?(*3)

«2 = КС(хх) л ТС(х2) л МЭС*3) (5)

а} = ) л 7С(*2) л GC(*3)

.а4 = МК(х^) л Т(х^) л MG(x^)

Все нейроны этого слоя реализовывают произвольную Т- норму для моделирования операции «И». На этом этапе также рассчитывается и нормированная сила правила (pi)

А--S-

+ а2 + а3 + а4 — аг

~ at + аг + а3 + а4 ^

А- аз

h

«1 + аг + а3 + а4

«4

ai + аг + аз +

3 (°uiPutmf). Формирует значения выходной переменной у. Нейроны этого

слоя выполняют следующие операции: Ал =№~\а1)

/?2У2=/?2МС-1(а2) (7)

/?зУз = РзСС-\а3)

Р*Ул = fi4.MG~1(a4)

Слой 4 (output) Единственный нейрон этого слоя вычисляет выход сети тем самым выполняет дефазификацию. Д '

У = Р1У1 + РгУг + РзУз + &У4 (8)

По результатам тестирования сеть необходимо обучить, тем самым осуществив корректировку параметров посылок. УЩСТ

Ыо['°1ле 0б^ения на основе метода градиентного спуска значения функций разбиваются на составляющие, что определяет необходимые условия, которые буш обеспечивать корректную работу сети (Рисунок 3) , которые оудут

Рисунок 3 Правила кодирования графиков и структура сети (а) до обучения, (б) после обучения.

Динамика данной модели характеризуется событиями следующих типов' генерация нового пакета на начальной стадии; начало обработки сетевого пакета и продвижение его по сети; окончание обработки сетевого пакета и отправка его в исходную точку; получение сетевого пакета и обработка его с помощ ю ИСМ по строение архитектуры продвижения пакета с помощью ИСМ. Время обрабош

таких событии можно подсчитать по формуле (9): р ки

Т = 4-Ст + 1§ + 2-Ч (9)

трафика в :тие применением

аса

Рисунок 4 Справа модель сети, слева графики загрузки сети и потери трафика

где Т - суммарное время обработки простого события, tm - среднее время обработки события маршрутизатором ( равное 26,5 мкс), при этом в модели использовалось 4 маршрутизатора, tg - среднее время настройки гибридной системы. Так как подобного оборудования пока в производстве нет, берем среднее время обработки данных компьютером последнего поколения, равное 65 мкс; tp1 = 340 мкс-время, затраченное на продвижение пакета в одну сторону, полученное по расчетам сделанным с помощью ИСМ. Время обработки события в среднем будет равно, 851 мкс.

Время обработки пакета сети с применением маршрутизатора Т = 4 • tm + 2 • tp 2 (10)

tp 2 - время, затраченное на продвижение пакета в одну сторону и полученное с помощью алгоритма Дейкстры, отклик системы равен 1086 мкс. При этом выигрыш по времени в предложенной системе маршрутизации составляет 20 %. Применение ИСМ обеспечивает следующие преимущества:

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

• Учитывается необходимая стратегия маршрута, время передвижения пакетов при любом маршруте.

• Функционирование ИСМ позволит свести человеческий фактор к минимуму. Глава 4 посвящена исследованию разработанной ИСМ. Для конкретного примера в виде типовой компьютерной сети вычисляется загруженность и проводится моделирование сети для распределения потока данных с помощью ИСМ.

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

ШВаю

1:

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

Загруженность сети в результате применения ИСМ становится равномерной и как следствие уменьшается потеря пакетов.

* эт°й главе делается сравнительный анализ работы протоколов RIP и OSPF с ИСМ и без нее. Рассматриваются две топологии сетей простая и избыточная (Ри-

'■О 0-3 3-8 15-18 i s 17-1910-20 4-11 J.J5 И-М ripofTK ТОИО.10ГЯЯ «ето

0 ---,--------------- -

1146 »■» »'12 12-17 17-19 r-4 4-ц И-20 И-16

HifluToiau топология

3-е 15-18 1-5 17-1919-20 4-11 8-15 1413

IMS JS-20 13-12 12-17 17-1S r-4 4-11 10-20 10-16

~^-Лгр.14 щр

Эыр.% OSPF

-»-иъ.к нем

~»~ИП1. к OSPF +Л1 ИСМ

Рисунок 5 Сравнительный анализ работы сети

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

Вывод. При средней загрузке каналов ИСМ позволяет снизить время доставки

на 15% в сравнении с RIP и на 10% в сравнении с OSPF,

nnJ^a ппп0С? ИСМ n^TBeP^eHb' экспериментами с реальными сетями предприятии ООО «Самара - Авиагаз» и «Волготехпласт». Так как на сегодняшний день не существует протокола маршрутизации, который может работать с нечеткими данными, использовались данные, которые были получены в результате расчетов по предложенной схеме.

Было проведено формирование и моделирование общего трафика в КС «Самара- Авиагаз», состоящей из 20 маршрутизаторов, 40 каналов, 2 серверов, и КС «Волготехпласт» состоящей из 8 маршрутизаторов (типа МЕТСЕАР РРо8а?е) 22 каналов, 2 серверов. Загруженность сетей была различной КС «Самара- Авиагаз» максимальная загруженность 7000 Кбайт/с, а КС «Волготехпласт» - 9000 Кбайтт/с. Следует отметить, эти сети имеют топологию «дерево с избыточностью», у КС «Волготехпласт» архитектура сети сложнее. Таблица маршрутизации в сетях строится на основе протокола ОБРР.

Проведены замеры трафика до изменения таблицы в маршрутизаторах КС и после. На рисунке 6 изображена загрузка каналов связи до и после оптимизации. График оптимизации обозначен ИСМ, а начальный график М. Измерения оптимизированного трафика ИСМ показали, что время выполнения задачи сократилось с

Рисунок 6 Загрузка каналов связи до и после оптимизации На рисунке 7 изображена загрузка каналов связи до и после оптимизации КС «Волготехпласт». График оптимизации обозначен ИСМ, а начальный график М. Измерения оптимизированного трафика показали, что время выполнения задачи сократилось с 11 секунд до 9.

Результаты экспериментов проведенных в ходе исследования подтвердили, выводы сделанные, на основе моделирования сети, в результате применения ИСМ время выполнения задачи в среднем уменьшается на 15 %. Использование подобного инструмента ведет к существенному повышению качества эксплуатируемых КС.

— нем В?п<'' гьшол!1г1и» JMS1S (от»

Заключение^™ ? 3афуЗКа КаНал0В Связи до и после оп™мизации JÄ? проведенных исследований была разработана ИСМ с совмест-

заГоТ И?м ГГ №ЧеТК0И Л°ГИКИ' НеЙр°ННЫХ Сетей и ™ндартных маршрутизаторов ИСМ позволяет автоматизировать процесс выбора маршрута на систематической основе путем изменения набора правил для работы Зютерно™

Р ТЫ СМ ВЫЯВИЛ° W преим^еств ло сравнению с традай TS маршруша4ии: матема™ческий аппарат анализа струны с ¡ Л?! Н6 усложняется; потеРя пакетов уменьшается, причем эффеТуве-ГмгпЛя укрупнением се™- На основе Результатов серии акп^и-

м —ГпплДИаПа3°Н применения предложенной систеш

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

Основное содержание диссертации опубликовано в следующих работах:

Статьи в журналах, рекомендованных ВАК России

1 ■ Акчурин, Э. А. О модификации процесса маршрутизации в вычислительных сетях с помощью нечеткой логики ГТекст] / Э. А. Акчурин, Т. А. Коваленко II Инфокошу-никационные технологии. - 2010, - Т. 8, № 4 - С 32-36 ^ у

Z nlvTtr I'v Анализ,/аглг°Ри™ов маршрутизации'в вычислительных сетях [ i eKCTj / I.A. Коваленко // Глобальный научный потенциал - 2011. - № 9. - С. 41-

Коваленко ТА. Модель введения гибридной системы в маршрутизатоо [Текст11Т А. Коваленко II Перспективы науки - 2011. - № 11(26) - С 106-108 Коваленко Т.А. О модификации процесса передачи данных в вычислительных

ssrÄÄÄf-'t-t-;

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

5. Акчурин, Э. А. Имитационное моделирование канала связи с использованием нечеткой логики [Текст] / Э. А. Акчурин, Т. А. Коваленко II Информационно-вычислительные технологии и их приложения : сб. науч. тр. XI Междунар науч -техн. конф. - Пенза: Изд-во РИО ПГСХА, 2009. - С. 3-5.

6. Коваленко, Т. А, Алгоритмы маршрутизации [Текст! / Т. А. Коваленко IIXVI Рос. науч. конф. лроф.-препод. состава, науч. сотрудников и асп.: сб. науч. то - Самара: ПГАТИ, 2009. - С. 10.

7. Коваленко, Т. А. Вопросы программного обеспечения в процессе обучения [Текст] I Т. А. Коваленко IIXV Рос. науч. конф. проф.-препод. состава, науч. сотрудников и асп.: сб. науч. тр. - Самара: ПГАТИ, 2008. - С. 184.

8. Коваленко, Т. А. Имитационное моделирование работы протокола РРР с использованием нечеткой логики [Текст] / Т. А. Коваленко II Информационно-вычислительные технологии и их приложения : сб. науч. тр. XI Междунар науч -техн. конф. - Пенза: Изд-во РИО ПГСХА, 2009. - С. 144-147.

9. Коваленко, Т. А. Исследование процесса передачи данных в вычислительных сетях с помощью гибридной сети [Текст] / Т. А. Коваленко IIXVIII Рос. науч. конф. проф.-препод. состава, науч. сотрудников и асп.: сб. науч. тр. - Самара- ПГУТИ 2011.-С. 209.

10. Коваленко, Т. А. Исследование процессов маршрутизации с помощью гибридной системы [Текст] / Т. А. Коваленко //XVIII Рос. науч. конф. проф.-препод. состава науч. сотрудников и асп.: сб. науч. тр. - Самара: ПГУТИ, 2011. - С. 208.

11. Коваленко, Т. А. Исследование статической маршрутизации с помощью нечеткой логики [Текст] I Т. А. Коваленко IIXVII Рос. науч. конф. проф.-препод. состава, науч. сотрудников и асп.: сб науч. тр. - Самара: ПГАТИ, 2010. - С. 165.

12. Коваленко, Т. А. Моделирование процесса маршрутизации в вычислительных сетях с помощью нечеткой логики [Текст] / Т. А. Коваленко// Информационно-вычислительные технологии и их приложения : сб. науч. тр. XII Междунар науч -техн. конф. - Пенза: Изд-во РИО ПГСХА, 2010. - С. 94-96.

13. Коваленко, Т. А. Моделирование процессов маршрутизации в вычислительных сетях с помощью нечеткой логики [Текст] / Т. А. Коваленко IIXVII Рос. науч. конф. проф.-препод. состава, науч. сотрудников и асп.: сб. науч. тр. - Самара : ПГАТИ 2010.-С. 166.

14. Коваленко, Т. А. Эффективное сетевое подключение компьютеров посредством протокола РРР [Текст] / Т. А. Коваленко IIXVI Рос. науч. конф. проф.-препод. состава, науч. сотрудников и асп.: сб. науч. тр. - Самара: ПГАТИ, 2009. - С. 11.

_Отпечатано фотоспособом в соответствии с материалами, представленными заказчика»

Подписано в печать 11.10.2012г. Формат 60x847ц; Бумага писчая№1. Гарнитура Тайме.

_Заказ 1170. Печать оперативная .Усл. печ. л. 0.92. ТиражЮОэю.

Отпечатано в издательстве учебной и научной литературы Поволжского государственного университета телекоммуникаций и информатики 443090, г. Самара, Московское шоссе 77. т.(846)228-00-44

61 12-5/1577

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

Коваленко Татьяна Анатольевна

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

Специальность «05.13.15» Вычислительные машины, комплексы и компьютерные сети

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

Научный руководитель Доктор технических наук Профессор Э.А. Акчурин

Самара - 2012

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 4

Глава 1 Современное состояние проблемы маршрутизации 11

1.1. Понятие алгоритма маршрутизации.........................................................11

1.2. Статическая маршрутизация.....................................................................14

1.3. Динамическая маршрутизация.................................................................18

1.3.1. Дистанционно - векторный алгоритм................................................20

1.3.2. Алгоритм маршрутизации с учетом состояния каналов..................21

1.3.3. Гибридный алгоритм............................................................................25

1.4. Маршрутизация на основе математического анализа............................26

1.5. Методы на основе нечеткой логики.........................................................30

1.6. Современные методы маршрутизации.....................................................32

Глава 2 Разработка интегрированной системы маршрутизации 37

2.1. Параметры алгоритмов маршрутизации.................................................37

2.2 Нейронная сеть и нечеткая логика..........................................................40

2.3. Современные маршрутизаторы................................................................45

2.3.1. Анализ архитектур маршрутизаторов................................................47

2.3.2 Интегрированная система маршрутизации.......................................50

Глава 3 Исследование интегрированной системы маршрутизации 54

3.1 Исследование процесса маршрутизации известными............................54

методами.............................................................................................................54

3.2 Исследование сети с помощью ИСМ.......................................................69

Глава 4 Моделирование маршрутизации в компьютерных сетях с

использованием ИСМ 83

4.1.Анализ работы ИСМ в компьютерной сети.............................................83

4.2.Сравнение со стандартными протоколами RIP и OSPF..........................91

4.2.1. Внутренний протокол маршрутизации RIP.....................................91

4.2.2. Протокол состояния связей OSPF.....................................................92

4.2.3. Сравнение протоколов - RIP и OSPF - по затратам - на

широковещательный трафик.............................................................94

4.2.4. Сравнение работы простой сети и с применением ИСМ...............96

4.3.Маршрутизация пакетов с учетом важности сообщений.....................103

4.4.Протокол РРР с использованием ИСМ...................................................114

4.5.Применение ИСМ для распределения потока данных..........................118

ЗАКЛЮЧЕНИЕ 129

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 132

ПРИЛОЖЕНИЕ 1 144

ПРИЛОЖЕНИЕ 2 145

ПРИЛОЖЕНИЕ 3 146

ПРИЛОЖЕНИЕ 4 147

ПРИЛОЖЕНИЕ 5 148

ВВЕДЕНИЕ

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

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

Значительный вклад в решение проблемы маршрутизации внесли отечественные и зарубежные ученые: В.Г. Олифер, H.A. Олифер, Брайн Хилл, Столингс В., Стивен Браун, Оливер Ибе, Щербо В.К., Джо Хабрейкен, Мэтт Хайден и другие.

Известные алгоритмы маршрутизации можно свести к трем основным:

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

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

3. Гибридный подход, объединяющий аспекты алгоритмов с определением вектора расстояния и оценки состояния канала. [2]

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

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

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

• возможность нечеткой формализации критериев оценки и сравнения; проведение качественных оценок, как входных данных, так и выходных результатов;

• разрешает оперировать степенью достоверности данных с использованием их при распределении потока информации;

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

Развитию в данной области знаний способствовали труды следующих ученых: Алтунин А.Е., Андрейчиков A.B., Андрейчикова О.Н., Асаи К., Гольдберг Д., Заде Д., Ковалёв С.М., Коско Б., Кофман А., Круглов В.В.,

Мамдани Е., Мелихов А.Н., Минаев Ю.Н., Пилиньский М., Рутковский Л., Семухин М.В., Сугэно М., Тэрано Т., Филимонова О.Ю., Холланд Дж., Ягер Р. и многих др.

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

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

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

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

• анализ существующих алгоритмов маршрутизации в компьютерных сетях (КС) для решения задачи ускорения прохождения пакетов;

• разработка современного подхода, основанного на методах интеллектуального анализа данных;

• разработка интегрированной системы маршрутизации, с совместным использованием нечеткой логики (НЛ), нейронных сетей (НС) и стандартных маршрутизаторов для компьютерных сетей ;

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

• обоснование области эффективного применения предложенной ИСМ.

Методы исследования В работе использовались теория графов, теория нечетких систем, методы имитационного моделирования, методы математической статистики, теория искусственных нейронных сетей, эволюционные алгоритмы. Исследование разработанных в работе алгоритмов обработки данных проводилось с использованием пакетов МАТЬАВ, 81аЙ81:юа, ОРЫЕТ и разработанного автором программного обеспечения.

Научная новизна заключается в том, что:

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

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

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

Достоверность результатов работы

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

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

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

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

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

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

• разработана интегрированная система маршрутизации, которая обеспечивает ускорение процесса передачи данных в многосегментных компьютерных сетях;

• предложенный метод маршрутизации в КС на основе ИСМ обеспечивает повышение эффективности доставки пакетов для сетей сложной конфигурации в условиях локальных перегрузок;

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

Реализация результатов работы.

Основные результаты, полученные в ходе работы над диссертацией, использовались при создании компьютерных сетей ООО «Волготехпласт», ООО «Самара - Авиагаз», ОАО СЗ «Экран» для определения загруженности сети, управления трафиком и распределения данных по сети. Результаты исследований также используются в учебном процессе и подтверждены актами о внедрении.

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

• ХУ Российская научная конференция профессорско-преподавательского состава, научных сотрудников и аспирантов Самара 2008,

• ХУ1 Российская научная конференция профессорско-преподавательского состава, научных сотрудников и аспирантов Самара

2009,

• ХУП Российская научная конференция профессорско-преподавательского состава, научных сотрудников и аспирантов Самара

2010,

• Информационно-Вычислительные технологии и их приложения X Международная научно-техническая конференция Пенза 2009,

• Информационно-Вычислительные технологии и их приложения XI Международная научно-техническая конференция, Пенза 2009,

• Информационно-Вычислительные технологии и их приложения XII Международная научно-техническая конференция, Пенза 2010,

• ХУ1П Российская научная конференция профессорско-преподавательского состава, научных сотрудников и аспирантов Самара 2011.

Публикации

По теме диссертации опубликовано 14 печатных работ, в том числе 4 статьи в научных журналах, входящих в перечень ВАК РФ, 3 научных статьи на Международных конференциях, 7 тезисов и докладов на Российских конференциях.

Структура работы

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

Глава 1 Современное состояние проблемы маршрутизации

1.1. Понятие алгоритма маршрутизации

Сеть Internet с ее протоколами изначально задумывалась, как протяженная (WAN - Wide Area Network), состоящая из большого количества машин, соединенных с помощью разных сред обмена данными (как локальных, так и глобальных соединений). Принцип маршрутизации является одним из тех факторов, который обеспечил гибкость сети Internet и ее победу в соревновании с другими сетевыми технологиями. Простейший способ проведения маршрутизации состоит в установке маршрутов при запуске системы с помощью специальных команд.

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

В литературе [52, 55, 60, 67] проводится анализ используемых протоколов маршрутизации по разработанным стандартам.

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

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

В соответствии со стандартами ISO (International Organization for Standardization - международная организация по стандартизации, разработавшая стандартную модель взаимодействия открытых систем) в

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

• Конечная система (End System - ES) - любой узел сети, который не занимается маршрутизацией, т.е устройство сети, не обладающее способностью пересылать пакеты между подсетями;

• Промежуточная система (Intermediate System - IS) - маршрутизатор, т.е устройство сети, способное пересылать пакеты между подсетями;

• Область (Area) - группа смежных сетей и подключенных к ним хостов, которые определяются как область администратором сети;

• Домен (Domain) - набор соединенных областей. Домены маршрутизации обеспечивают полную связанность со всеми конечными системами, находящимися в их пределах.

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

СПЕЦИФИКАЦИЯ ПРОТОКОЛОВ МАРШРУТИЗАЦИИ

АЛГОРИТМ МАРШРУТИЗАЦИИ

правила конструирования метрики

алгоритм вычисления маршрута

ФОРМАТ ДАННЫХ

формат пакетов обмена маршрутной информации

правила приема передача маршрутной информации

Рисунок 1. 1 Структура протокола маршрутизации

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

Анализ литературы [50-59, 66] показал, что определение маршрута может базироваться на отдельных показателях, таких как, топология сети, скорость передачи, надежность, загруженность и т.д. Программные реализации алгоритмов маршрутизации вычисляют показатели маршрутов для определения наиболее оптимальных из них.

Критерии оценки алгоритмов маршрутизации характеризуют отдельные частные цели их разработки:

1. Оптимальность маршрута. Она характеризует способность алгоритма выбирать «наилучший» мар