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

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

Заливка(flooding)

Алгоритм заливки является одним из самых простых, в нем каждый приходящий пакет пересылается на все исходящие линии, кроме той по которой он пришел.

Дубликаты пакетов

Этот алгоритм порождает много лишних пакетов, а в сетях с замкнутыми контурами бесконечное число пакетов, поэтому в заголовок пакета помещают счетчик пройденных им транзитных участков, каждый маршрутизатор, при получении этого пакета и пересылкой дальше уменьшает этот счетчик на единицу. Как только значение счетчика достигает нуля пакет дальше не пересылается. Изначально этот счетчик можно задать равным длине максимального пути в сети, или длине пути от отправителя до получателя, если она известна. Тем не менее один и тот же маршрутизатор может отправлять один и тот же пакет несколько раз, если получил его с разных линий. Один из методов борьбы с отправкой одного и того же пакета много раз состоит в том, что каждый маршрутизатор нумерует каждый пакет получаемый от своих хостов и добавляет этот номер в заголовок. Все маршрутизаторы ведут для всех маршрутизаторов-источников счетчик, хранящий максимальный номер полученного от него пакета. Теперь, когда приходит пакет с номером меньшим, чем тот, что храниться в счетчике пакет вместо пересылки просто игнорируется, поскольку этот пакет уже был переслан.

Преимущества

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

Недостатки

• дублирование пакетов
• не практичен, так как увеличивает нагрузку на сеть