Протокол маршрутизации вектора расстояния
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Протокол маршрутизации с вектором расстояния в сетях передачи данных определяет лучший маршрут для пакетов данных на основе расстояния. Протоколы маршрутизации с вектором расстояния измеряют расстояние количеством маршрутизаторов, которые должен пройти пакет; один маршрутизатор считается за один переход. Некоторые протоколы вектора расстояния также учитывают задержку сети и другие факторы, влияющие на трафик на данном маршруте. Чтобы определить лучший маршрут в сети, маршрутизаторы, использующие протокол вектора расстояния, обмениваются информацией друг с другом, обычно таблицами маршрутизации, а также количеством переходов для сетей назначения и, возможно, другой информацией о трафике. Протоколы маршрутизации на основе вектора расстояния также требуют, чтобы маршрутизатор периодически информировал своих соседей об изменениях топологии сети .
Протоколы маршрутизации на основе вектора расстояния используют алгоритм Беллмана-Форда для расчета наилучшего маршрута. Другой способ расчета наилучшего маршрута в сети основан на стоимости канала и реализуется с помощью протоколов маршрутизации по состоянию канала .
Термин «вектор расстояния» относится к тому факту, что протокол манипулирует векторами ( массивами ) расстояний до других узлов в сети. Алгоритм вектора расстояния был исходным алгоритмом маршрутизации ARPANET и получил более широкое распространение в локальных сетях с помощью протокола информации о маршрутизации (RIP).
Обзор
[ редактировать ]Протоколы маршрутизации с вектором расстояния используют алгоритм Беллмана-Форда . В этих протоколах каждый маршрутизатор не обладает информацией о полной топологии сети . Он объявляет свое значение расстояния (DV), рассчитанное для других маршрутизаторов, и получает аналогичные рекламные объявления от других маршрутизаторов, если изменения не вносятся в локальную сеть или соседями (маршрутизаторами). Используя эти объявления маршрутизации, каждый маршрутизатор заполняет свою таблицу маршрутизации. В следующем цикле объявления маршрутизатор объявляет обновленную информацию из своей таблицы маршрутизации. Этот процесс продолжается до тех пор, пока таблицы маршрутизации каждого маршрутизатора не придут к стабильным значениям.
Недостатком некоторых из этих протоколов является медленная сходимость.
Примеры протоколов маршрутизации с вектором расстояния:
- Протокол информации о маршрутизации (RIP)
- Протокол информации о маршрутизации версии 2 (RIPv2)
- Протокол информации о маршрутизации следующего поколения (RIPng), расширение RIP версии 2 с поддержкой IPv6.
- Протокол маршрутизации внутреннего шлюза (IGRP)
- Расширенный протокол маршрутизации внутреннего шлюза (EIGRP)
Методология
[ редактировать ]Маршрутизаторы, использующие протокол вектора расстояния, определяют расстояние между собой и пунктом назначения. Лучший маршрут для интернет-протокола передаются [[]], по которому данные по сети передачи данных , измеряется количеством маршрутизаторов (прыжков), которые должен пройти пакет, чтобы достичь сети назначения. Кроме того, некоторые протоколы вектора расстояния учитывают другую информацию о трафике, например задержку сети . Чтобы установить лучший маршрут, маршрутизаторы регулярно обмениваются информацией с соседними маршрутизаторами, обычно своей таблицей маршрутизации , количеством переходов для сети назначения и, возможно, другой информацией, связанной с трафиком. Маршрутизаторы, реализующие протокол вектора расстояния, полагаются исключительно на информацию, предоставляемую им другими маршрутизаторами, и не оценивают топологию сети . [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]
Среди протоколов вектора расстояния, которые были описаны как гибридные, поскольку они используют методы маршрутизации, связанные с протоколами маршрутизации по состоянию канала , есть собственный протокол расширенной маршрутизации внутреннего шлюза (EIGRP). Он был разработан Cisco в 1980-х годах и был разработан для обеспечения лучшей конвергенции и уменьшения сетевого трафика между маршрутизаторами, чем протокол маршрутизации по состоянию канала Open Shortest Path First (OSPF). [5]
Другим примером протокола маршрутизации на основе вектора расстояния является Babel .
Задача посчитать до бесконечности
[ редактировать ]Алгоритм Беллмана-Форда не предотвращает петель маршрутизации возникновение и страдает от проблемы счета до бесконечности . Суть проблемы счета до бесконечности заключается в том, что если А сообщает 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 to A = 2 + 1». Позже B пересылает обновление C, и в связи с тем, что A доступен через B (с точки зрения C), C решает обновить свою таблицу до «C to A = 3 + 1». Оно медленно распространяется по сети, пока не достигнет бесконечности (в этом случае алгоритм корректирует себя из-за свойства релаксации Беллмана-Форда).
Обходные пути и решения
[ редактировать ]RIP использует разделенный горизонт с методом обратного отравления, чтобы уменьшить вероятность образования петель, и использует максимальное количество переходов для решения проблемы «счета до бесконечности». Эти меры позволяют избежать образования петель маршрутизации в некоторых, но не во всех случаях. [6] Добавление времени удержания (отказ от обновления маршрута в течение нескольких минут после отзыва маршрута) практически во всех случаях позволяет избежать образования петель, но приводит к значительному увеличению времени сходимости.
Совсем недавно был разработан ряд протоколов вектора расстояния без петель — яркими примерами являются EIGRP , DSDV и Babel . Они во всех случаях позволяют избежать образования петель, но страдают от повышенной сложности, а их внедрение замедлилось из-за успеха протоколов маршрутизации по состоянию канала, таких как OSPF .
Пример
[ редактировать ]В этой сети у нас есть 4 маршрутизатора A, B, C и D:
Мы отмечаем текущее время (или итерацию) в алгоритме буквой T и начинаем (в момент времени 0 или T=0) с создания матриц расстояний для каждого маршрутизатора до его непосредственных соседей. При построении таблиц маршрутизации ниже кратчайший путь выделяется зеленым цветом, а новый кратчайший путь — желтым. Серые столбцы обозначают узлы, которые не являются соседями текущего узла и поэтому не считаются допустимым направлением в его таблице. Красный цвет обозначает недопустимые записи в таблице, поскольку они относятся к расстояниям от узла до самого себя или через себя.
| Т=0 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| На этом этапе все маршрутизаторы (A, B, C, D) имеют новые «кратчайшие пути» для своего DV (список расстояний от них до другого маршрутизатора через соседа). Каждый из них транслирует этот новый DV всем своим соседям: от A к B и C, от B к C и A, от C к A, B и D и от D к C. Когда каждый из этих соседей получает эту информацию, они теперь пересчитывают кратчайший путь с его использованием.
Например: A получает DV от C, который сообщает A, что существует путь через C к D с расстоянием (или стоимостью) 5. Поскольку текущий «кратчайший путь» к C равен 23, тогда A знает, что у него есть путь к D, который стоит 23+5=28. Поскольку других более коротких путей, о которых знает A, нет, он использует это как текущую оценку кратчайшего пути от себя (A) к D через C. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Т=1 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Опять же, все маршрутизаторы получили на последней итерации (при T=1) новые «кратчайшие пути», поэтому все они транслируют свои DV своим соседям; Это побуждает каждого соседа снова пересчитывать свои кратчайшие расстояния.
Например: A получает DV от B, который сообщает A, что существует путь через B к D с расстоянием (или стоимостью) 7. Поскольку текущий «кратчайший путь» к B равен 3, тогда A знает, что у него есть путь к D, который стоит 7+3=10. Этот путь к D длиной 10 (через B) короче существующего «кратчайшего пути» к D длиной 28 (через C), поэтому он становится новым «кратчайшим путем» к D. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Т=2 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| На этот раз только маршрутизаторы A и D имеют новые кратчайшие пути для своих DV. Таким образом, они транслируют свои новые DV своим соседям: A передает B и C, а D передает C. Это заставляет каждого из соседей, получающих новые DV, пересчитывать свои кратчайшие пути. Однако, поскольку информация от DV не дает более коротких путей, чем они уже есть в их таблицах маршрутизации, в таблицах маршрутизации не происходит никаких изменений. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Т=3 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Ни один из маршрутизаторов не имеет новых кратчайших путей для широковещательной передачи. Таким образом, ни один из маршрутизаторов не получает никакой новой информации, которая могла бы изменить их таблицы маршрутизации. Алгоритм останавливается. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ссылки
[ редактировать ]- ^ Тамара Дин (2009). Network+ Руководство по сетям . Cengage Обучение. стр. 274 . ISBN 9781423902454 .
- ^ К. Хедрик (июнь 1988 г.). Протокол информации о маршрутизации . Сетевая рабочая группа. дои : 10.17487/RFC1058 . РФК 1058 . Исторический. Обновлено RFC 1388 и 1723 .
- ^ Тамара Дин (2009). Network+ Руководство по сетям . Cengage Обучение. стр. 274 . ISBN 9781423902454 .
- ^ Тамара Дин (2009). Network+ Руководство по сетям . Cengage Обучение. стр. 274–275 . ISBN 9781423902454 .
- ^ Тамара Дин (2009). Network+ Руководство по сетям . Cengage Обучение. стр. 275 . ISBN 9781423902454 .
- ^ К. Хедрик (июнь 1988 г.). Протокол информации о маршрутизации . Сетевая рабочая группа. дои : 10.17487/RFC1058 . РФК 1058 . Исторический. сек. 2.2.2. Обновлено RFC 1388 и 1723 .
- Г. Малкин (ноябрь 1998 г.). РИП версии 2 . Сетевая рабочая группа. дои : 10.17487/RFC2453 . СТД 53. RFC 2453 . Интернет-стандарт. Устаревшие RFC 1723 and 1388. Updated by РФК 4822 .
- «Алгоритм поиска пути для маршрутизации без петель» , Дж. Дж. Гарсиа-Луна-Асевес и С. Мерти, Транзакции IEEE/ACM в сети, февраль 1997 г.
- «Обнаружение недействительных объявлений маршрутизации в протоколе RIP», Д. Пей, Д. Мэсси и Л. Чжан, Конференция по глобальным коммуникациям IEEE (Globecom), декабрь 2003 г.
Дальнейшее чтение
[ редактировать ]- Раздел «Состояние канала и вектор расстояния». Архивировано 14 декабря 2010 г. на Wayback Machine в главе «Основы маршрутизации» в Cisco . «Справочнике по технологиям межсетевого взаимодействия»
- Раздел 5.2 «Алгоритмы маршрутизации» в главе «5 СЕТЕВОЙ УРОВЕНЬ» из «Компьютерные сети» 4-й. Издание Эндрю С. Таненбаума