ИССЛЕДОВАНИЕ АЛГОРИТМОВ МАРШРУТИЗАЦИИ И ИХ РЕАЛИЗАЦИЯ НА ЯЗЫКЕ VHDL

Манов П.А.

Владимирский Государственный университет

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

Алгоритмы маршрутизации классифицируются на статические и динамические (рис.1). Те алгоритмы, которые явно не причисляются к этим типам, определяют стратегию маршрутизации, не определяя конкретные принципы построения протоколов.

Рис. 1. Классификация алгоритмов маршрутизации.

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

Все алгоритмы используют одну из трех математических моделей -Дийкстра, Беллмана-Форда, Флойда-Уоршелла. Исчерпывающее их описание приведено в [2]. Но если статические алгоритмы распространяют их на всю описываемую подсеть, то динамические только локально, используя развитые метрики оптимальности.

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

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

Динамические алгоритмы для оценки оптимальности пути используют механизм метрик. Метрикой для дистанционно-векторной маршрутизации является число отрезков сети (хопов) между отравителем и получателем. На основании данной метрики выбирается оптимальный маршрут, локально используя алгоритм Дийкстры. Данный метод глобально использовался в коммерческих сетях и сетях общего назначения до начала 80х годов XX века. Данный алгоритм имеет ряд недостатков, главным из которых является проблема счета до бесконечности. Практическая реализация алгоритма выполнена в. виде протокола RIP[1]. Сейчас же данный метод уступил место более совершенным, но его еще поддерживает подавляющий процент выпускаемого оборудования, операционных систем (MVS, Unix, семейство MS Windows Server).

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

Целью исследования было построение модели одного из реально существующих протоколов для исследования принципов функционирования протокола, оценка его эффективности. Для выбора одного из протоколов маршрутизации были выявлены следующие критерии: распространенность, затраты на реализацию, наглядность модели, возможность использования модели для обучения теоретическим основам маршрутизации в объединенных сетях. Эти критерии были выбраны для построения общей оценки. Для исследований была выбрана версия первая версия протокола RIP (действующий на основе алгоритма дистанционно-векторной маршрутизации), т.е. реализация без учета масок IP-адресов. Модель была создана на языке VHDL, чтобы оценить не только эффективность алгоритма, но и трудности при аппаратной реализации данного протокола. Логическая схема маршрутизатора, работающего по протоколу RIPvl, представлена на рис. 2. Модель оперировала IP-пакетами, поступающими на четыре порта. Согласно таблице маршрутизации они коммутировались через порт с наилучшей метрикой маршрута. Таблица маршрутизации создавалась на основе входных тестовых данных, которые фактически задавали топологию сети, состоящую из аналогичных маршрутизаторов. В результате работы блока оптимизации таблицы маршрутизации в памяти маршрузатора создается дерево минимальных путей. В процессе исследования модели были практически выявлены все достоинства и недостатки данного протокола. Особое затруднение вызвало устранение эффекта счета до бесконечности, когда моделирование проходило по бесконечному циклу.

Рис. 2 Логическая структура маршрутизатора

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

Литература:

1. Олифер В.Г., Олифер Н.А. Компьютерные сети. 2-е изд. - СПб.: Питер, 2002 - 811 с.
2. Современные компьютерные сети. 2-е изд./В. Столингс. - СПб.: Питер, 2003. - 783 с.
3. Таненбаум Э. Компьютерные сети. - СПб.: Питер, 2002. - 848 с.