Протокол маршрутизации на основе вектора расстояния в сетях передачи данных определяет наилучший маршрут для пакетов данных на основе расстояния. Протоколы маршрутизации на основе вектора расстояния измеряют расстояние по количеству маршрутизаторов , которые должен пройти пакет; один маршрутизатор считается одним переходом. Некоторые протоколы на основе вектора расстояния также учитывают задержку сети и другие факторы, влияющие на трафик на заданном маршруте. Чтобы определить наилучший маршрут по сети, маршрутизаторы, использующие протокол на основе вектора расстояния, обмениваются информацией друг с другом, обычно таблицами маршрутизации, а также количеством переходов для сетей назначения и, возможно, другой информацией о трафике. Протоколы маршрутизации на основе вектора расстояния также требуют, чтобы маршрутизатор периодически информировал своих соседей об изменениях топологии сети .
Протоколы маршрутизации на основе вектора расстояния используют алгоритм Беллмана–Форда для расчета наилучшего маршрута. Другой способ расчета наилучшего маршрута по сети основан на стоимости соединения и реализуется с помощью протоколов маршрутизации на основе состояния соединения .
Термин «вектор расстояния» относится к тому факту, что протокол манипулирует векторами ( массивами ) расстояний до других узлов в сети. Алгоритм вектора расстояния был оригинальным алгоритмом маршрутизации ARPANET и был более широко реализован в локальных сетях с протоколом маршрутной информации (RIP).
Протоколы маршрутизации на основе вектора расстояния используют алгоритм Беллмана–Форда . В этих протоколах каждый маршрутизатор не обладает информацией о полной топологии сети . Он объявляет другим маршрутизаторам свое рассчитанное значение расстояния (DV) и получает аналогичные объявления от других маршрутизаторов, если только в локальной сети или соседями (маршрутизаторами) не вносятся изменения. Используя эти объявления маршрутизации, каждый маршрутизатор заполняет свою таблицу маршрутизации. В следующем цикле объявлений маршрутизатор объявляет обновленную информацию из своей таблицы маршрутизации. Этот процесс продолжается до тех пор, пока таблицы маршрутизации каждого маршрутизатора не сойдутся к стабильным значениям.
Недостатком некоторых из этих протоколов является медленная сходимость.
Примеры протоколов маршрутизации на основе вектора расстояния:
Маршрутизаторы, использующие протокол вектора расстояния, определяют расстояние между собой и пунктом назначения. Лучший маршрут для данных через сеть передачи данных измеряется в терминах количества маршрутизаторов (прыжков), через которые пакет должен пройти, чтобы достичь своей сети назначения. Кроме того, некоторые протоколы вектора расстояния учитывают другую информацию о трафике, такую как задержка сети . Чтобы установить наилучший маршрут, маршрутизаторы регулярно обмениваются информацией с соседними маршрутизаторами, обычно своей таблицей маршрутизации , количеством прыжков для сети назначения и, возможно, другой информацией, связанной с трафиком. Маршрутизаторы, реализующие протокол вектора расстояния, полагаются исключительно на информацию, предоставленную им другими маршрутизаторами, и не оценивают топологию сети . [1]
Протоколы вектора расстояния обновляют таблицы маршрутизации маршрутизаторов и определяют маршрут, по которому пакет будет отправлен следующим узлом , который является выходным интерфейсом маршрутизатора и IP-адресом интерфейса принимающего маршрутизатора. Расстояние — это мера стоимости достижения определенного узла. Наименее затратный маршрут между любыми двумя узлами — это маршрут с минимальным расстоянием.
Обновления выполняются периодически в протоколе маршрутизации на основе вектора расстояния, где вся или часть таблицы маршрутизации маршрутизатора отправляется всем его соседям, настроенным на использование того же протокола маршрутизации на основе вектора расстояния. Как только маршрутизатор получает эту информацию, он может внести поправки в свою собственную таблицу маршрутизации, чтобы отразить изменения, а затем сообщить об этом своим соседям. Этот процесс был описан как «маршрутизация по слухам», поскольку маршрутизаторы полагаются на информацию, которую они получают от других маршрутизаторов, и не могут определить, является ли эта информация действительной и правдивой. Существует ряд функций, которые можно использовать для решения проблемы нестабильности и неточной информации о маршрутизации.
Самый старый протокол маршрутизации и самый старый протокол вектора расстояния — это версия 1 протокола маршрутной информации (RIPv1). RIPv1 был официально стандартизирован в 1988 году. [2] Он устанавливает кратчайший путь по сети исключительно на основе переходов, то есть количества маршрутизаторов, которые необходимо пройти, чтобы достичь сети назначения. RIP — это протокол внутреннего шлюза , поэтому его можно использовать в локальных сетях (LAN) на внутренних или пограничных маршрутизаторах. Маршрутизаторы с реализацией RIPv1 обмениваются своими таблицами маршрутизации с соседними маршрутизаторами, транслируя пакет RIPv1 каждые 30 секунд во все подключенные сети. RIPv1 не подходит для больших сетей, поскольку он ограничивает количество переходов до 15. Это ограничение на количество переходов было введено для предотвращения петель маршрутизации, но также означает, что сети, подключенные через более чем 15 маршрутизаторов, недоступны. [3]
Протокол вектора расстояния, разработанный для использования в глобальных сетях (WAN), — это протокол пограничного шлюза (BGP). BGP — это протокол внешнего шлюза , поэтому он реализован на пограничных и внешних маршрутизаторах в Интернете . Он обменивается информацией между маршрутизаторами через сеанс протокола управления передачей (TCP). Маршрутизаторы с реализацией BGP определяют кратчайший путь через сеть на основе ряда факторов, отличных от переходов. BGP также может быть настроен администраторами таким образом, чтобы определенные маршруты были предпочтительными или избегались. BGP используется поставщиками интернет-услуг (ISP) и телекоммуникационными компаниями. [4]
Среди протоколов с вектором расстояния, которые были описаны как гибридные, поскольку они используют методы маршрутизации, связанные с протоколами маршрутизации по состоянию канала , есть фирменный протокол Enhanced Interior Gateway Routing Protocol (EIGRP). Он был разработан Cisco в 1980-х годах и был разработан для обеспечения лучшей конвергенции и создания меньшего сетевого трафика между маршрутизаторами, чем протокол маршрутизации по состоянию канала Open Shortest Path First (OSPF). [5]
Другим примером протокола маршрутизации на основе векторов расстояний является Babel .
Алгоритм Беллмана–Форда не предотвращает возникновение циклов маршрутизации и страдает от проблемы подсчета до бесконечности . Суть проблемы подсчета до бесконечности заключается в том, что если A сообщает B, что у него где-то есть путь, то B не может узнать, является ли этот путь частью B. Чтобы увидеть проблему, представьте себе подсеть, соединенную как A–B–C–D–E–F, и пусть метрика между маршрутизаторами будет «количеством переходов». Теперь предположим, что A отключен. В процессе обновления вектора B замечает, что маршрут к A, который был на расстоянии 1, не работает — B не получает обновление вектора от A. Проблема в том, что B также получает обновление от C, а C все еще не знает о том, что A не работает — поэтому он сообщает B, что A находится всего в двух переходах от C (от C до B до A). Поскольку B не знает, что путь от C до A проходит через него самого (B), он обновляет свою таблицу новым значением «B до A = 2 + 1». Позже B пересылает обновление в C, и поскольку A достижим через B (с точки зрения C), C решает обновить свою таблицу до "C to A = 3 + 1". Это медленно распространяется по сети, пока не станет бесконечным (в этом случае алгоритм корректирует себя из-за свойства релаксации Беллмана-Форда).
RIP использует метод split horizon с poison reverse для снижения вероятности образования петель и использует максимальное количество переходов для противодействия проблеме «счет до бесконечности». Эти меры позволяют избежать образования петель маршрутизации в некоторых, но не во всех случаях. [6] Добавление времени удержания (отказ от обновлений маршрута в течение нескольких минут после отзыва маршрута) позволяет избежать образования петель практически во всех случаях, но приводит к значительному увеличению времени сходимости.
Совсем недавно был разработан ряд протоколов векторов расстояний без петель — яркими примерами являются EIGRP , DSDV и Babel . Они избегают образования петель во всех случаях, но страдают от повышенной сложности, и их развертывание было замедлено успехом протоколов маршрутизации состояния канала, таких как OSPF .
В этой сети у нас есть 4 маршрутизатора A, B, C и D:
Мы отмечаем текущее время (или итерацию) в алгоритме как T и начинаем (в момент времени 0 или T=0) с создания матриц расстояний для каждого маршрутизатора до его непосредственных соседей. Когда мы строим таблицы маршрутизации ниже, кратчайший путь выделяется зеленым цветом, а новый кратчайший путь выделяется желтым цветом. Серые столбцы обозначают узлы, которые не являются соседями текущего узла и, следовательно, не считаются допустимым направлением в его таблице. Красный цвет обозначает недопустимые записи в таблице, поскольку они относятся к расстояниям от узла до самого себя или через себя.