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

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

Заливка(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] будет только увеличивается и через какое-то время уйдет в бесконечность.

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

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

Недостатки

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

Маршрутизация с учетом состояния линий(link state routing)

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

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

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

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

Как только маршрутизатор загружается ему нужно получить информацию от соседей, для этого он посылает специальный пакет [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], на который принимающий его маршрутизатор должен незамедлительно ответить. В это случае будут выбираться пути с наименьшей задержкой.

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

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

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

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

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

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

Вычисление новых маршрутов

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

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

• отсутствие проблем медленного распространения новостей

Недостатки

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

Источники информации

• Э. Таненбаум, Д.Уэзеролл - Компьютерные сети (5-е издание, 2012)
• Алгоритмы маршрутизации - Википедия