Маршрутизация

 

 

 

 

Маршрутизация

 

 

 

 

Маршрутизация

 

• Сети соединяются между собой специальными устройствами, называемыми маршрутизаторами.
• Маршрутизатор — это устройство, которое собирает информацию о топологии межсетевых соединений и пересылает пакеты  сетевого уровня в сеть назначения. Чтобы передать сообщение от отправителя, находящегося в одной сети, получателю, находящемуся в другой сети, нужно совершить некоторое количество транзитных передач между сетями, или хопов (от слова hop — прыжок), каждый раз выбирая подходящий маршрут. Таким образом, маршрут представляет собой последовательность маршрутизаторов, через которые проходит пакет.
• Сетевой уровень должен обеспечить доставку пакета:
• между любыми двумя узлами сети с произвольной топологией;
• между любыми двумя сетями в составной сети;
• Сеть — совокупность компьютеров, использующих для обмена данными единую сетевую технологию;
• Маршрут — последовательность прохождения пакетом  маршрутизаторов в составной сети.

 

 

 

 

 

Маршруты движения пакетов

 

• На рисунке показаны четыре сети, связанные тремя маршрутизаторами. Между узлами А и В данной сети пролегает два маршрута:
• первый — через маршрутизаторы 1 и 3,
• второй — через маршрутизаторы 1, 2 и 3.

 

 

 

 

 

Задачи маршрутизации

 

• Проблема выбора наилучшего пути называется маршрутизацией, и ее решение является одной из главных задач сетевого уровня.
• Эта проблема осложняется тем, что самый короткий путь — не всегда самый лучший. Часто критерием при выборе маршрута является время передачи данных; оно зависит от пропускной способности каналов связи и интенсивности трафика, которая может с течением времени изменяться. Некоторые алгоритмы маршрутизации пытаются приспособиться к изменению нагрузки, в то время как другие принимают решения на основе средних показателей за длительное время.
• Выбор маршрута может осуществляться и по другим критериям, таким как надежность передачи.
• В общем случае функции сетевого уровня шире, чем функции передачи сообщений по связям с нестандартной структурой, которые мы рассмотрели на примере объединения нескольких локальных сетей.
• Сетевой уровень также решает задачи согласования разных технологий, упрощения адресации в крупных сетях и создания надежных и гибких барьеров на пути нежелательного трафика между сетями.

 

 

 

 

Маршрутизируемый протокол

 

• Маршрутизируемый протокол – любой сетевой протокол, который обеспечивает в адресе сетевого уровня достаточно информации, чтобы передавать пакет от одной хост-машины к другой на основе принятой схемы адресации.
• Маршрутизируемый протокол определяет формат и назначение полей внутри пакета.
• В общем случае пакеты переносятся от одной станции к другой.
• Примеры маршрутизируемых протоколов – IP, IPX.

 

 

 

 

Протоколы маршрутизации

 

• Протокол маршрутизации – поддерживает маршрутизируемый протокол за счет предоставления механизмов коллективного использования маршрутной информации.
• Сообщения протокола маршрутизации циркулируют между маршрутизаторами для обмена информации и атуализации данных таблиц маршрутизации.
• Примеры протоколов маршрутизации:
• RIP – протокол маршрутной информации;
• IGRP – протокол внутренней маршрутизации между шлюзами;
• EIGR – усовершенствованный протокол внутренней маршрутизации между шлюзами;
• OSPF – протокол маршрутизации с выбором кратчайшего пути.

 

 

 

 

Алгоритмы маршрутизации

 

• Большинство алгоритмов маршрутизации можно свести к трем основным:
• Маршрутизация на основе вектора расстояния – определяется направление (вектор) и расстояние до каждого канала в сети;
• Маршрутизация на основе оценки состояния канала (выбор на основе кратчайшего пути), при которой воссоздается точная топология всей сети (по крайней мере, где размещается маршрутизатор);
• Гибридный подход, объединяющий вышеуказанные алгоритмы.

 

 

 

 

Алгоритмы маршрутизации по вектору расстояния

 

• Алгоритмы маршрутизации на основе вектора расстояния (алгоритмы Беллмана-Форда) предусматривают периодическую передачу копий таблицы маршрутизации от одного маршрутизатора другому. Такие передачи позволяют актуализировать изменения в топологии сети.
• Каждый маршрутизатор получает информацию от соседнего маршрутизатора.
• При добавлении информации в таблицу маршрутизации добавляется величина, отражающая вектор расстояния (например, число переходов) и далее информация передается следующему маршрутизатору.

 

 

 

 

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

 

• В данных алгоритмах каждый маршрутизатор начинает с идентификации или исследования своих соседей. Порт к каждой непосредственно подключенной сети имеет расстояние 0.
• Продолжая процесс исследования векторов расстояния в сети, маршрутизаторы открывают наилучший путь до сети пункта назначения на основе информации от каждого соседа.
• Каждая запись в талице маршрутизации имеет коммулятивное значение вектора расстояния, показывающая насколько далеко данная сеть находится в этом направлении.

 

 

 

 

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

 

• При изменении топологии сети, использующей протокол на основе вектора расстояния, таблицы маршрутизации должны быть обновлены.
• Обновление содержания таблиц маршрутизации выполняется шаг за шагом от одного маршрутизатора к другому.
• Алгоритмы с вектором расстояния заставляют каждый маршрутизатор отсылать всю таблицу маршрутизации каждому своему непосредственному соседу.
• Таблицы маршрутизации, генерируемые в рамках метода вектора расстояния, содержат информацию об общей стоимости пути (метрика) и логический адрес маршрутизатора, стоящего на пути к каждой известной ему сети.

 

 

 

 

Маршрутизация с учетом состояния канала связи 

 

• Алгоритмы маршрутизации с учетом канала связи также называются алгоритмы выбора первого кратчайшего пути (shortest path first, SPF).
• Данные алгоритмы поддерживают базу данных топологической информации.
• Для выполнения маршрутизации по данному алгоритму используются специальные сообщения объявлений о состоянии канала (link state advertisements, LSA), база данных топологии, SPF-алгоритм, результирующее SPS-дерево и таблица маршрутизации, содержащая пути и порты к каждой сети.

 

 

 

 

Режим исследования сети

 

• В режиме исследования сети при маршрутизации с учетом состояния канала связи выполняются следующие процессы:
• Маршрутизаторы обмениваются LSA-сообщениями, начиная с непосредственно подключенных маршрутизаторов;
• Маршрутизаторы параллельно друг с другом топологическую базу данных, содержащую все LSA-сообщения;
• SPF-алгоритм вычисляет достижимость сетей, определяя кратчайший путь до каждой сети комплекса. Маршрутизатор создает эту логическую топологию кратчайших путей в виде SPF-дерева, помещая себя в корень. Это дерево отображает пути от маршрутизатора до всех пунктов назначения.
• Наилучшие пути и порты, имеющие выход на эти сети назначения, сводятся в таблицы маршрутизации. Также формируется базы данных с топологическими элементами и подробностями о статусе.

 

 

 

 

Обработка изменений топологии в протоколах маршрутизации 

 

• Алгоритмы учета состояния канала связи полагаются на маршрутизаторы, имеющие общее представление о сети.
• Для достижения сходимости каждый маршрутизатор выполняет:
• Отслеживает своих соседей: имя, рабочее состояние и стоимость линии связи;
• Создает LSA-пакетов, в котором приводится перечень имен соседних маршрутизаторов и стоимость линий связи, а также данные о новых соседях и об изменениях в стоимости линий;
• Посылает LSA-пакет на другие маршрутизаторы;
• Получая LSA-пакет, записывает его в базу данных;
• Используя накопленные данные LSA-пакетов для создания полной карты топологии сети, маршрутизатор запускает на исполнение SPF-алгоритм и рассчитывает оптимальные маршруты до каждой сети.

 

 

 

 

Сравнение методов маршрутизации 

 

• Процесс маршрутизации по вектору расстояния получает топологические данные из таблиц маршрутизации соседних маршрутизаторов. Процесс маршрутизации SPF получает широкое представление обо всей топологии сетевого комплекса, собирая данные из всех LSA-пакетов;
• Процесс маршрутизации по вектору расстояния определяет лучший путь с помощью сложения метрик по мере того как таблица движется от одного маршрутизатора к другому. При использовании маршрутизации SPF каждый маршрутизатор работает отдельно, вычисляя свой собственный оптимальный путь;

 

 

 

 

Сравнение методов маршрутизации 

 

• В большинстве протоколов маршрутизации по вектору расстояния пакеты актуализации, содержащие сведения об изменениях топологии, являются периодически посылаемыми пакетами актуализации таблиц. Эти таблицы передаются от одного маршрутизатора к другому, что приводит к медленной сходимости;
• В протоколах маршрутизации SPF пакеты актуализации генерируются и рассылаются по факту возникновения изменения топологии. Относительно небольшие LSA-пакеты передаются всем маршрутизаторам, что приводит к более быстрой сходимости при любом изменении топологии сети.