Алгоритмы маршрутизации. Маршрутизация с учетом состояния линии.

Сейчас в крупных сетях и сети Интернет используются варианты — алгоритмы маршрутизации IS-IS и OSPF. Каждый маршрутизатор должен:

• обнаруживать своих соседей и узнавать их сетевые адреса;

• задавать метрику расстояния или стоимости связи с каждым из своих соседей;

• создавать пакет, содержащий всю собранную информацию;

• посылать этот пакет всем маршрутизаторам и принять все пакеты, отправленные другими маршрутизаторами;
вычислять кратчайший путь ко всем маршрутизаторам.

В результате каждому маршрутизатору высылается полная топология. После этого для обнаружения кратчайшего пути ко всем остальным маршрутизаторам каждый маршрутизатор может использовать алгоритм Дейкстры. Ниже мы рассмотрим каждый из этих пяти этапов более подробно.

Знакомство с соседями. Когда маршрутизатор загружается, его первая задача состоит в получении информации о своих соседях. Он достигает этой цели, посылая специальный пакет HELLO по всем линиям «точка-точка». При этом маршрутизатор на другом конце линии должен послать ответ, содержащий его имя. Имена маршрутизаторов должны быть совершенно уникальными, поскольку если удаленный маршрутизатор слышит, что три маршрутизатора являются соседями маршрутизатора F, то не должно возникать разночтений по поводу того, один и тот же маршрутизатор F имеется в виду или нет. Когда два или более маршрутизаторов соединены с помощью широковещательной связи (например, коммутатора, кольцевой сети или классической сети Ethernet), ситуация несколько усложняется. Широковещательная ЛВС обеспечивает связь между каждой парой подключенных маршрутизаторов. Однако моделирование такой сети в виде системы связей «точка—точка» существенно увеличивает размер топологии и приводит к нерациональной передаче сообщений. Более подходящий способ моделирования локальной сети со- стоит в том, что ЛВС рассматривается в виде узла графа, как и маршрутизаторы. Для исполнения роли N в протоколе маршрутизации выбирается один из маршрутизаторов сети, который называется отмеченным маршрутизатором (designated router). Возможность передачи пакетов от A к C по локальной сети отражается здесь наличием пути ANC.

Задание стоимости связи. Алгоритм маршрутизации с учетом состояния линии требует, чтобы каждая связь обладала метрикой расстояния или стоимости, необходимой для вычисления кратчайшего пути. Стоимость пути до соседних маршрутизаторов может быть задана автоматически или определена оператором сети. Чаще всего стоимость обратно пропорциональна пропускной способности связи.

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

Распространение пакетов состояния линий. Основная идея алгоритма отправки пакетов состояния линии на все маршрутизаторы состоит в использовании алгоритма заливки. Чтобы держать этот процесс под контролем, в каждый пакет помещают порядковый номер, увеличивающийся на единицу для каждого следующего пакета. Маршрутизаторы записывают все пары (источник, порядковый номер), которые им попадаются. Когда приходит новый пакет состояния линий, маршрутизатор ищет адрес его отправителя и порядковый номер пакета в своем списке. Если это новый пакет, он рассылается дальше по всем линиям, кроме той, по которой он пришел. Если же это дубликат, он удаляется. Если порядковый номер прибывшего пакета меньше, чем номер уже полученного пакета от того же отправителя, то такой пакет также удаляется как устаревший, поскольку очевидно, что у маршрутизатора есть более свежие данные.

Вычисление новых маршрутов. Собрав полный комплект пакетов состояния линий, маршрутизатор может построить полный граф сети, так как он располагает данными обо всех линиях. На самом деле, каждая линия представлена даже дважды, по одному значению для каждого направления. У разных направлений может быть разная стоимость. Поэтому результаты вычисления кратчайшего пути от A до B и от B до A могут не совпадать. Теперь для построения кратчайших путей ко всем возможным адресатам может быть локально применен алгоритм Дейкстры. Результат вычислений сообщает маршрутизатору, какое соединение следует выбрать, чтобы добраться до нужного адреса назначения. Эта информация добавляется в таблицы маршрутов, после чего возобновляется нормальная работа маршрутизатора.