Дистанционно-векторная маршрутизация (:nvmguenkuuk-fytmkjugx bgjojrmn[genx)

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

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

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

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

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

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

Правила

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

Работа маршрутизатора

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

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

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

Достоинства и недостатки

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

Дистанционно-векторные протоколы

Протокол RIPv1

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

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

Основные параметры

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

Протокол RIPv2

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

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

Основные параметры

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

Сравнение RIPv1 и RIPv2

Сравнение RIPv1 и RIPv2

Протокол маршрутизации	RIPv1	RIPv2
Адресация	Классовый	Бесклассовый
Поддержка маски переменной длины	Нет	Да
Отправка маски в обновлениях	Нет	Да
Тип адресации	Broadcast	Multicast
Описание	RFC 1058	RFCs 1721, 1722, 2435
Поддержка суммирования маршрутов	Нет	Да
Поддержка аутентификации	Нет	Да

Протокол IGRP

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

Delay (Задержка)	Описывает (в десятках мкс) время на достижение точки назначения при отсутствии нагрузки в сети.
Bandwidth (Полоса пропускания)	Равна 10 000 000, деленным на наименьшую полосу пропускания по заданному маршруту (измеряется в Кбит/с). Например, наименьшая полоса пропускания в 10 Кбит/с соответствует метрике в 1 000 000 Кбит/с.
Load (Нагрузка)	Измеряется как доля полосы пропускания по заданному маршруту, используемая в текущий момент времени. Кодируется числами от 0 до 255 (255 соответствует нагрузке в 100%).
Reliability (Надежность)	Часть датаграмм, пришедшая без повреждения. Кодируется числами от 0 до 255 (255 соответствует 100-процентному отсутствию повреждений в датаграммах).
Hop count (Счетчик попаданий)	Определяет число попаданий до точек назначения.
Path MTU (MTU пути)	Наибольшее значение Maximum Transmission Unit (MTU) для датаграмм, которые можно переслать по любой связи общего пути.

Протокол EIGRP

Дистанционно-векторный протокол маршрутизации 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.