Алгоритм маршрутизации по выбору кратчайшего пути

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

Пример:

Кратчайший путь от А к D.

Алгоритм маршрутизации «Заливка»

Идея: каждый приходящий пакет посылается на все исходящие линии кроме той, откуда он пришел. Недостаток: порождается большое количество дублированных пакетов которые гуляют по сети. С целью их упорядочивания в заголовок пакета помещается счетчик преодоления транзитных участков уменьшаемый на 1 после прохождения каждого маршрутизатора. В идеальном случае первоначальное значение счетчика устанавливается в максимальную длину в пути без петлей. Когда, двигаясь по пути пакета, значение счетчика становится равным нулю, он удаляется, либо другим способом является учет прохождения маршрутизаторов. В этом случае все маршрутизаторы ведут список маршрутизаторов – источников. В списке сохраняются порядковые номера пакетов. Если пакет от данного маршрутизатора с таким номером уже приходил он удаляется. Если нет – распространяется дальше.

При «выборочной заливке» пакеты направляются не по всем линиям, а только по тем, которые «приблизительно» идут по выбранному адресатом направлению.

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