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