4 Дистанционно-векторная маршрутизация

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

Как говорилось ранее, все дистанционно-векторные протоколы маршрутизации основываются на дистанционно-векторном алгоритме, который был впервые описан Фордом и Фулкерсоном в работе «Потоки в Сетях». Их работа опиралась в свою очередь на уравнение Беллмана из его книги «Динамическое программирование».

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

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

Дистанционно-векторный алгоритм можно определить в виде следующего набора правил:

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

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

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

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

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

–Если новый путь заменяет существующий, последний отбрасывается.

–Если стоимость существующего пути меньше или равна стоимости нового пути, последний будет отброшен.

–После запоминания нового пути вершина должна объявить смежным вершинам вершину адресат и стоимость нового пути.

65

Математически доказано, что описанный алгоритм вычисляет кратчайшие пути между всеми парами вершин за конечный промежуток времени (Рисунок 4.1).

Рисунок 4.1 – Функционирование дистанционно-векторного алгоритма

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

66

пути - это дистанция, а вершина-адресат и следующая вершина представляют собой вектор.

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

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

4.1.1 Дистанционно-векторный алгоритм для протокола IP

В версии дистанционно-векторного алгоритма для протокола IP или другого маршрутизируемого протокола вершины представляют маршрутизаторы, а ребра – соединения между ними.

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

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

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

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

67

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

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

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

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

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

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

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

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

68