Geum.ru

Применение алгоритмов адаптивной маршрутизации в протоколе igrp

Вид материалаДокументы

Содержание


N/2, а его максимальное значение не превышает N
Подобный материал:

УДК 004.4 (06) Компьютерные системы и технологии

Д.А. ПЕРЕПЕЛКИН

Научный руководитель – Н.В. КРАВЧУК, к.т.н., доцент
Рязанский государственный радиотехнический университет


ПРИМЕНЕНИЕ АЛГОРИТМОВ АДАПТИВНОЙ

МАРШРУТИЗАЦИИ В ПРОТОКОЛЕ IGRP


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


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

Протокол IGRP (Interior Gateway Routing Protocol – протокол внутреннего шлюза) используется в корпоративных вычислительных сетях на базе маршрутизаторов CISCO. Для построения таблиц маршрутизации в нем применяется алгоритм Беллмана – Форда. Однако трудоемкость этого алгоритма достаточно высокая, порядка O(N3).

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

В работе [2] предложены методы и алгоритмы адаптивной маршрутизации, основанные на частичном использовании ранее вычисленных маршрутов, а также дополнительной информации о предполагаемых изменениях структуры корпоративной сети. Данные алгоритмы позволяют уменьшить трудоемкость построения таблиц маршрутизации до величины порядка O(N).

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

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

В таблице 1 приведены обобщенные статистические характеристики для задачи средней размерности, где через МО обозначено математическое ожидание, а через СКО – среднее квадратичное отклонение.

Таблица 1

Число узлов

Min

значение
Max

значение
МО
СКО

10
0,30
0,8182
0,5047
0,0943

100
0,06
0,7401
0,2185
0,1368

500
0
0,9192
0,0594
0,1173


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

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

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


Список литературы

  1. Леохин Ю.Л. Роль корпоративных сетей в создании и развитии ИТ-инфраструктуры // Качество. Инновации. Образование. – 2009. № 4, С. 42-46.
  2. Перепелкин Д.А., Перепелкин А.И. Разработка алгоритмов адаптивной маршрутизации в корпоративных вычислительных сетях // Вестник Рязанской государственной радиотехнической академии. 2006. № 19. С. 114-116.