Алгоритм маршрутизации по состоянию канала spf

В результате освоения главы 10 студент должен: знать

• • алгоритм построения дерева SPT;
• • особенности реализации алгоритма SPF для IP-сетей;
• • принцип представления СПД алгоритмом SPF; уметь
• • проводить расчет дерева SPT для реальных СПД; владеть
• • методами построения графа SPF для реальных СПД.

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

Чтобы лучше понять различие между дистанционно-векторным алгоритмом Веллмана — Форда, алгоритмом DUAL и алгоритмами маршрутизации по состоянию канала, рассмотрим рис. 10.1—10.3.

На рис. 10.1 изображено представление топологии СПД маршрутизатором R1, который использует в своей работе дистанционно-векторный алгоритм Веллмана — Форда. Маршрутизатор имеет информацию о сетяхнолучателях СП1 — СП7, о том, как далеко и в каком направлении они находятся. Никакой другой информации, например о соседних маршрутизаторах, R1 не имеет.

По этой причине время сходимости сети под управлением алгоритма Веллмана — Форда будет наибольшим в сравнении с другими алгоритмами маршрутизации.

На рис. 10.2 изображено представление той же СПД маршрутизатором R1, но на этот раз маршрутизатор использует в своей работе алгоритм DUAL. Маршрутизатор знает не только о сетях-получателях, но и о существовании соседних маршрутизаторов, использующих тот же алгоритм, а также дистанции от соседей до всех известных им сетей-1юлучателей.

Как видно из рис. 10.2, кроме кратчайшего пути к сети-получателю СП4, лежащего через R2, маршрутизатор R1 смог также обнаружить альтернативный маршрут, лежащий через маршрутизатор R4. Метрика кратчайшего маршрута равна 22, тогда как метрика альтернативного — 26. Несмотря.

Рис. 10.1. Представление топологии сети алгоритмом Веллмана — Форда.

Рис. 10.2. Представление топологии сети алгоритмом DUAL на большую метрику, R1 все же рассматривает маршрут через маршрутизатор R4 как альтернативу, поскольку заявленная метрика маршрута маршрутизатора R4 к СП4 равна 16, т. е. она меньше, чем метрика кратчайшего маршрута R1. Следовательно, маршрутизатор R4 находится ближе к сетиполучателю, чем маршрутизатор R1, а значит, маршрутизатор R1 может мгновенно переключиться на маршрут через R4, если характеристики маршрута через R2 ухудшатся или он станет недоступен.

Если немедленное переключение на альтернативный маршрут невозможно, маршрутизатор R1 может спросить своих соседей о наличии альтернативных маршрутов. Это позволяет значительно уменьшить время сходимости СПД.

На рис. 10.3 показано представление топологии СПД маршрутизатором R1 с использованием алгоритма SPF протокола маршрутизации, но состоянию канала.

В данном случае маршрутизатор R1 знает полную топологию СПД. Следовательно, он знает не только об альтернативном маршруте к сети СП4 через R4, но и об альтернативных маршрутах к СПб и СП5 через маршрутизатор R2.

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

Второе преимущество следует из первого. Оно заключается в том, что если маршрутизатор имеет точную информацию о топологии СПД в домене маршрутизации, он может самостоятельно, не прибегая к механизму рассылки запросов соседним маршрутизаторам, вносить изменения в ТМ после того как он обнаружил недоступность того или иного маршрута. Следовательно, время сходимости протоколов маршрутизации по состоянию канала значительно меньше, чем у дистанционно-векторных протоколов маршрутизации, использующих как алгоритм Веллмана — Форда, так и алгоритм DUAL (в том случае если алгоритм DUAL не смог вычислить вероятного преемника).

Однако превосходство протоколов маршрутизации по состоянию канала имеет свою цену. Алгоритм SPF требует больших вычислительных ресурсов, чем дистанционно-векторные алгоритмы Веллмана — Форда и DUAL.

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

Сходимость сетей при использовании протоколов маршрутизации по состоянию канала выше, чем у протоколов, использующих алгоритм Веллмана — Форда. Но этого нельзя сказать при сравнении этих протоколов с протоколами на основе алгоритма DUAL.

Рис. 10.3. Представление топологии сети алгоритмом SPF.

Учитывая центральное место алгоритма SPF в работе протоколов маршрутизации по состоянию канала, необходимо сначала подробно рассмотреть сам алгоритм и получить понятие о его работе.