Дистанционно-векторная маршрутизация (Distance Vector Routing, DVR) - маршрутизация, протоколы которой основаны на дистанционно-векторном алгоритме[1]. Дистанционно-векторные алгоритмы относятся к классу алгоритмов адаптивной (или динамической) маршрутизации.
Данный алгоритм был впервые описан Фордом и Фалкерсоном в работе «Потоки в Сетях». Их работа опиралась в свою очередь на уравнение Беллмана из его книги «Динамическое программирование».
Свое название алгоритм получил вследствие того, что ни по завершении работы алгоритма, ни в процессе её, ни одна вершина не обладает топологическими сведениями ни об одном маршруте. Каждый обнаруженный путь представлен лишь вершиной-адресатом, стоимостью пути и следующей вершиной на пути к вершине-адресату, и представление пути не содержит промежуточных вершин и ребер. Стоимость пути - это дистанция, а вершина-адресат и следующая вершина представляют собой вектор.[1]
Задача, которую решает дистанционно-векторный алгоритм, – это задача нахождения кратчайших путей между вершинами графа. Граф – это математическая абстракция, в которой вершины соединены между собой ребрами. Каждое ребро имеет некоторую стоимость его использования. Путь между двумя вершинами является набором промежуточных ребер и вершин, соединяющих две исходные вершины. Стоимость пути определяется как сумма стоимостей ребер, составляющих его. Кратчайшим путем между двумя вершинами при этом считается путь с наименьшей стоимостью.
В дистанционно-векторных алгоритмах каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния (измеренные в той или иной метрике) от данного маршрутизатора до всех известных ему сетей. Пакеты протоколов маршрутизации обычно называют объявлениями о расстояниях, так как с их помощью маршрутизатор объявляет остальным маршрутизаторам известные ему сведения о конфигурации сети.
Получив от некоторого соседа вектор расстояний (дистанций) до известных тому сетей, маршрутизатор наращивает компоненты вектора на величину расстояния от себя до данного соседа. Кроме того, он дополняет вектор информацией об известных ему самому других сетях, о которых он узнал непосредственно (если они подключены к его портам) или из аналогичных объявлений других маршрутизаторов. Обновленное значение вектора маршрутизатор рассылает своим соседям. В конце концов, каждый маршрутизатор узнает через соседние маршрутизаторы информацию обо всех имеющихся в составной сети сетях и о расстояниях до них.[2]