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

Рефераты / Программирование, компьютеры и кибернетика / Исследование процессов маршрутизации

Алгоритм Беллмана-Форда относится к алгоритмам DVA (Distance Vector Algoriths). В DVA рельеф Ra(d) - это оценка кратчайшего пути от узла a к узлу d. Оценка (условно назовем ее расстоянием) может выражаться временем доставки, надежностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. В ТМ узла а каждому из остальных узлов отводится одна строка со следующей информаци

ей:

- узел назначения;

- длина кратчайшего пути;

- номер N ближайшего узла, соответствующего кратчайшему пути;

- список рельефов от а к d через каждый из смежных узлов.

Хотя алгоритм Беллмана-Форда сходится медленно, для сетей сравнительно небольших масштабов он вполне приемлем. В больших сетях лучше себя зарекомендовал алгоритм OSPF. Он основан на использовании в каждом маршрутизаторе информации о состоянии всей сети. В основе OSPF лежит алгоритм Дейкстры поиска кратчайшего пути в графах. При этом сеть моделируется графом, в котором узлы соответствуют маршрутизаторам, а ребра - каналам связи. Веса ребер - оценки (расстояния) между инцидентными узлами.

Находит применение еще один алгоритм маршрутизации - IGRP (Interior Gateway Routine Protocol), разработанный фирмой Cisco. Он аналогичен алгоритму RIP, но развивает его в направлениях: а) возможны различные метрики (целевые функции); б) трафик может распределяться по нескольким каналам с близкими значениями метрики.

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

2.2 Характеристика протокола RIP

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

Вектором расстояний называется набор пар ("Сеть", "Расстояние до этой сети"), извлеченный из таблицы маршрутов. Расстояние до сети, к которой маршрутизатор подключен непосредственно, примем равным 1.

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

Протокол RIP (Routing Information Protocol) описан в документе RFC 1058. Он представляет собой один из старейших протоколов обмена маршрутной информацией между маршрутизаторами в сети, построенной на базе протокола IP. Помимо версии протокола RIP для сетей IP существует также версия этого протокола для сетей IPX/SPX компании Novell. Сообщения об обновлении таблиц маршрутизации в этом протоколе касаются только устройств, которые разделяют общую сеть. Эти устройства называются соседями. В этом протоколе все сети имеют номера. При этом способ образования номера зависит от используемого в сети протокола сетевого уровня. А все маршрутизаторы имеют свои идентификаторы.

Исторически протокол RIP имеет близкую связь с семейством сетевых протоколов фирмы Xerox. Протокол известен довольно давно, Впервые он появился в 1982 году как часть стека протокола TCP/IP в версии UNIX, разработанной организацией Berkley Software Distribution. При использовании протокола RIP работает эвристический алгоритм динамического программирования Беллмана — Форда. Решение, найденное с его помощью, является близким к оптимальному. Преимуществом протокола RIP является его вычислительная простота. Недостатком — увеличение трафика при периодической рассылке широковещательных сообщений.

Базовый алгоритм обновления маршрута в RIP