Маршрутизатор это устройство, в котором выполняются 2 основных процесса:
Как правило алгоритмы маршрутизации должны обрабатывать изменение топологии сетей, произошедших в следствие сбоя или других причин без прекращения выполнения задач обмена информацией. Алгоритмы выбора маршрутов можно разбить на 2 основных класса:
В основном все основываются на т.н. принципе оптимальности. Он заключается в следующем: если маршрутизатор B располагается на оптимальном маршруте между A и C, то от B к C тоже является оптимальным маршрутом.
В этом случае происходит рассмотрение множества оптимальных маршрутов от всех источников к приемнику в виде дерева.
Расстояния между узлами измеряется количеством транзитных участков. Входное дерево может быть неуникально, то есть их может быть несколько.
Цель всех алгоритмов построение входного дерева для маршрутизаторов. Недостаток: линии связи маршрутизаторов могут выходить из строя и могут быть у каждого маршрутизатора разные представления о сети.
В этом случае сеть представляется в виде графа. Способ измерения длины дуг может выбираться исходя из физической длины линии между маршрутизаторами, временем задержки при передаче пакетов, длиной очереди и т.д. Имеется несколько алгоритмов вычисления кратчайшего пути. Наиболее известный алгоритм Дейкстры. Работу алгоритма рассмотрим на примере.
Пример:
Кратчайший путь от А к D.
Идея: каждый приходящий пакет посылается на все исходящие линии кроме той, откуда он пришел. Недостаток: порождается большое количество дублированных пакетов которые гуляют по сети. С целью их упорядочивания в заголовок пакета помещается счетчик преодоления транзитных участков уменьшаемый на 1 после прохождения каждого маршрутизатора. В идеальном случае первоначальное значение счетчика устанавливается в максимальную длину в пути без петлей. Когда, двигаясь по пути пакета, значение счетчика становится равным нулю, он удаляется, либо
