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

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

Заливка(flooding)

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

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

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

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

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

Недостатки

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

Маршрутизация по вектору расстояний(distance vector routing)

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

Каждая запись таблицы состоит из двух частей: предпочитаемые номер линии для данного адресата и предполагаемое расстояние до него. Будем считать, что каждый маршрутизатор знает расстояние до своих соседей(если расстояние изменяется в транзитных участках то оно равно 1, а если же расстояние измеряется временем задержки распространения, то маршрутизатор может измерить его с помощью специального пакета [math]ECHO[/math], в который отправитель помещает время отправления, а получатель отправляет обратно как можно быстрее). Каждые [math]T[/math] мс все маршрутизаторы посылают свои таблицы всем своим соседям и получают подобные вектора от них. Пусть одна из таких таблиц пришла от соседа [math]X[/math] и в ней указано расстояние от маршрутизатора [math]X[/math] до маршрутизатора [math]Y[/math], обозначим его [math]T_{xy}[/math]. Если маршрутизатор знает, что расстояние между ним и маршрутизатором [math]X[/math] равно [math]T_x[/math], то расстояние до маршрутизатора [math]Y[/math] через маршрутизатор [math]X[/math] равно [math]T_x + T_{xy}[/math]. Выполнив такие расчеты для всех своих соседей маршрутизатор может выбрать наилучшие пути и поместить их в соответствующую запись таблицы.

Проблема счета до бесконечности

Рассмотрим ситуацию: пусть в сети 5 маршрутизаторов [math]A, B, C, D, E[/math], соединенных последовательно. Изначально все они включены и расстояние измеряется в количестве транзитных участков. Внезапно связь между маршрутизаторами [math]A[/math] и [math]B[/math] теряется, либо [math]A[/math] просто отключается. При первом обмене пакетами [math]B[/math] не слышит ответа от [math]A[/math], но маршрутизатор [math]C[/math] сообщает, что он знает путь до [math]A[/math] длиной 2. Маршрутизатор [math]B[/math] изменяет запись в таблице и считает, что теперь у него есть путь длиной 3 до маршрутизатора [math]A[/math]. Аналогично, при следующей рассылке маршрутизатор [math]C[/math] установит в своей таблице путь до [math]A[/math] равным 4, так как получит от маршрутизаторов [math]B[/math] и [math]D[/math] таблицы, по которым они знают путь до маршрутизатора [math]A[/math] длиной 3. С каждой следующей итерацией обновления таблиц расстояние до маршрутизатора [math]A[/math] будет только увеличивается и через какое-то время уйдет в бесконечность.

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

• относительно небольшой объем хранимых каждым маршрутизатором данных
• простой алгоритм пересчета расстояний на каждой итерации
• быстрое распространение хороших новостей

Недостатки

• проблемы счета до бесконечности

Маршрутизация с учетом состояния линий

В основе данного алгоритма лежит простая идея каждый маршрутизатор должен уметь:

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

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

Знакомство с соседями

Как только маршрутизатор загружается ему нужно получить информацию от соседей, для этого он посылает специальный пакет [math]HELLO[/math]. В ответ маршрутизатор на другом конце линии посылает ответ, содержащий свое имя. Имена маршрутизаторов должны быть совершенно уникальными. В случае соединений [math]point-to-point[/math] проблем не возникает, но если некоторые маршрутизаторы соединены широковещательной связью ситуация усложняется. Пусть, например, маршрутизаторы [math]A, B, C[/math] соединены широковещательной связью. Моделирование данной модели в виде связей [math]point-to-point[/math] будет сильно увеличивать размер топологии, поэтому создает искусственный узел, назовем его [math]N[/math], соответствующий самой широковещательной связи. На самом деле роль этого узла будет играть один из маршрутизаторов [math]A, B, C[/math]. Теперь, передача пакетов от [math]A[/math] к [math]C[/math] будет следовать по пути [math]ANC[/math].

Задание метрики расстояний

Метрика расстояния между двумя соседними маршрутизаторами может быть задана автоматически или оператором сети. Чаще всего ее задают обратно пропорциональной пропускной способности линии, благодаря этому будут выбираться пути с большей пропускной способностью. Второй способ заключается в определении задержки специального пакета [math]ECHO[/math], на который принимающий его маршрутизатор должен незамедлительно ответить. В это случае будут выбираться пути с наименьшей задержкой.

Создание пакета состояния линий

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

Распространение пакетов состояния линий

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