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

Дистанционно-векторная маршрутизация (Distance Vector Routing, DVR) - маршрутизация, протоколы которой основаны на дистанционно-векторном алгоритме^[1]. Дистанционно-векторные алгоритмы относятся к классу алгоритмов адаптивной (или динамической) маршрутизации.

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

Дистанционно-векторные алгоритмы маршрутизации также называются алгоритмами Беллмана–Форда.

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

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

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

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

Получив от некоторого соседа вектор расстояний (дистанций) до известных тому сетей, маршрутизатор наращивает компоненты вектора на величину расстояния от себя до данного соседа. Кроме того, он дополняет вектор информацией об известных ему самому других сетях, о которых он узнал непосредственно (если они подключены к его портам) или из аналогичных объявлений других маршрутизаторов. Обновленное значение вектора маршрутизатор рассылает своим соседям. В конце концов, каждый маршрутизатор узнает через соседние маршрутизаторы информацию обо всех имеющихся в составной сети сетях и о расстояниях до них.^[2]

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

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

Дистанционно-векторный протокол RIPv1 (Routing Information Protocol) является первым протоколом динамической маршрутизации и очень часто применяется в настоящее время.

Этот протокол используется в качестве протокола внутренней маршрутизации в небольших сетях и поддерживается оборудованием всех производителей.^[3]

• RIP - дистанционно-векторный протокол.
• Административная дистанция - 120.
• Метрика - число хопов.
• Максимальное число хопов - 15.
• Метрика недоступного маршрута - 16.
• Рассылка обновлений маршрутной информации - широковещательно каждые 30 секунд.
• Счетчик ожидания сходимости (Hold-Down Timer) – 180 сек.
• Маска подсети – используется маска по умолчанию, определяющаяся классом сети, в обновлении не посылается.

Дистанционно-векторный протокол RIPv2 является модификацией протокола RIPv1.

Этот протокол используется в качестве протокола внутренней маршрутизации в небольших сетях и поддерживается оборудованием всех производителей.^[3]

• RIPv2 - дистанционно-векторный протокол.
• Административная дистанция – 120.
• Метрика - число хопов.
• Максимальное число хопов - 15.
• Метрика недоступного маршрута - 16.
• Рассылка обновлений маршрутной информации – с использованием группового адреса 224.0.0.9 каждые 30 секунд.
• Счетчик ожидания сходимости (Hold-Down Timer) – 180 сек.
• Поддержка триггерных обновлений. Маска подсети – используется маска переменной длины, посылаемая в обновлении.

Как и в RIP, маршрутизатор IGRP периодически распространяет среди соседей содержимое своей таблицы через широковещательные рассылки. Однако в отличие от RIP маршрутизатор IGRP начинает работу с уже сформированной таблицей маршрутизации для подключенных к нему подсетей. Эта таблица расширяется далее благодаря сведениям от ближайших соседей-маршрутизаторов. В сообщениях об изменениях протокола IGRP не содержится сведений о маске подсети. Вместо простого счетчика попаданий RIP применяются различные типы информации о метриках, а именно^[4]:

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

Для поддержки маршрутизации протокол EIGRP использует следующие средства:

• Таблица соседей – содержит список соседних маршрутизаторов, что обеспечивает двухстороннее 59 взаимодействие между непосредственно соединенными маршрутизаторами.
• Топологическая таблица – содержит записи о маршрутах для всех сетей назначения, о которых известно маршрутизатору.
• DUAL (diffusing update algorithm) – алгоритм диффузионных обновлений используемый, для вычисления маршрутов.
• Таблица маршрутизации – содержит наилучшие маршруты в сети назначения, выбранные из топологической таблицы.
• Успешный (Successor) – наилучший маршрут (основной), найденный для достижения сети назначения. Он заносится в таблицу маршрутизации.
• Возможный успешный (Feasible successor) - резервный маршрут. Резервные маршруты выбираются в то же время, что и наилучший. Эти маршруты хранятся в топологической таблице. Возможно существование нескольких резервных маршрутов до сети назначения.

• Граф
• Алгоритм Форда — Фалкерсона
• Алгоритм Беллмана — Форда
• Уравнение Беллмана
• RIP(сетевой протокол)
• Interior Gateway Routing Protocol
• EIGRP

1. М.В. ДИБРОВ. Маршрутизаторы. — Красноярск, 2008. — 389 с.
2. Голдовский Я.М. , Желенков Б.В., Цыганова Н.А. Маршрутизация в компьютерных сетях: Учебное пособие. - М.: РУТ (МИИТ), 2017. – 114 с.
3. Золотарёв С.П.. "Дистанционно-векторные алгоритмы маршрутизации" Вологдинские чтения, no. 69, 2008, pp. 43–48.
4. Сидни Фейт. TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security). — Лори, 2000. — ISBN 5-85582-072-6.

1. ↑ ^{1 2} М.В. ДИБРОВ. Маршрутизаторы. — Красноярск, 2008. — 389 с.
2. ↑ Золотарёв, С. П. Дистанционно-векторные алгоритмы маршрутизации (рус.) // Вологдинские чтения. — 2008. — № 69. — С. 43-48. Архивировано 12 декабря 2020 года.
3. ↑ ^{1 2} Голдовский Я.М. , Желенков Б.В., Цыганова Н.А. Маршрутизация в компьютерных сетях. — М.: РУТ (МИИТ), 2017. — 114 с с.
4. ↑ Сидни Фейт. TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security). — Лори, 2000. — ISBN 5-85582-072-6.

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (19 октября 2024)