68
правок
Изменения
→Роутинг на сетевом уровне
В больших сетях топология постоянно изменяется, поэтому необходимо изменять стратегии доставки сообщений в зависимости от этих изменений, а также в зависимости от загруженности сети. Для решения этой задачи существуют алгоритмы маршрутизации, благодаря которым роутер понимает, какому устройству нужно отправить сообщение, чтобы добиться хороших результатов в его доставке.
==== Алгоритмы на основе расстояния между устройствами ====
Используют [[алгоритм Форда-Беллмана]]. Каждому ребру в сети присваивается некоторая цена и узлы выбирают маршрут для отправки данных, используя путь наименьшей цены.
Алгоритм:
Когда узел запускается, он знает только о своих ближайших соседях и цену для достижения каждого из них. Каждый узел регулярно отправляет своим соседям информацию о цене достижения всех узлов в сети, для которых он знает эту цену. Соседи получают эту информацию и сравнивают с имеющейся у них. Если за счет полученной информации можно улучшить цену достижения некоторой вершины, то они записывают эту информацию в своей таблице маршрутизации. Через какое-то время все узлы сети будут знать наилучшую цену доставки и оптимальный маршрут доставки сообщения от себя до некоторого узла В, благодаря чему смогут отправлять данные оптимально.
Если топология сети изменяется, например, в следствии отказа какого-нибудь узла, то его соседи с использованием описанного выше алгоритма могут перестроить маршруты, которые использовали этот узел.
==== Link-state algorithm ====
Для данного алгоритма каждый узел в сети должен знать структуру графа, которым является сеть. Это достигается следующим образом: каждый узел при запуске знает только о своих соседях. Узел регулярно отправляет информацию о той части сети, про которую он что-то знает (уже узнал на предыдущих итерациях) своим непосредственным соседям, добавляя к этой информации число- версию отправляемых данных. Узел, получая данные от своего соседа, сравнивает версию в данных с собственной версией и если версия в данных больше, чем его собственная, то он использует данные для изменения своего представления о структуре графа и переплывает сообщение своим соседям. Если же версия в сообщении меньше, чем версия у узла, то данное сообщение игнорируется.
Когда узнали информацию о структуре сети, можно построить граф сети для поиска кратчайших путей. На графе запускается [[алгоритм Дейкстры]], в результате выполнения которого узел узнает кратчайший путь от себя до любого другого узла сети, а также ближайшего соседа на этом пути, которому и будет пересылаться сообщение.
Когда у вершины построен граф, используется специальный протокол, который позволяет понять, доступны ли все соседи вершины. Если с каким-то соседом что-то случилось, то вершина начинает перестраивать свой граф, используя алгоритм, аналогичный алгоритму для изначального построения графа.
==== ====
