Применение алгоритма Дейкстры в протоколах маршрутизации

Построения маршрутной таблицы на базе алгоритма Дейкстры требует, чтобы каждый узел, кроме собственно реализации алгоритма, выполнял следующие процедуры:

· оповещение о присутствии в сети, обнаружение соседних маршрутизаторов и получение их имен (адресов);

· измерение «стоимости» линий связи с «соседями»;

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

· формирование полной топологической схемы объединенной сети.

Рассмотрим некоторые ососбенности выполнения перечисленных процедур.

Оповещение о присутствии и обнаружение соседей

При включении маршрутизатор отправляет специальный пакет HELLO по всем своим интерфейсам, помещая в него собственное имя (адрес). Каждый маршрутизатор, получив этот пакет, считывает с него адрес отправителя и отвечает собственным пакетом HELLO. Так узлы формируют таблицу «соседей». Ясно, что используемые имена маршрутизаторов должны быть глобально уникальны.

Измерение «стоимости» линий связи

«Стоимость» линий может определяться различными метриками, в том числе: величиной задержки передачи, номинальной пропускной способностью, доступной пропускной способностью, учитывающей текущий уровень загрузки, какой-либо сверткой этих критериев. Метрика выбирается администратором сети, и все маршрутизаторы должны использовать единую метрику. Заметим, что в сети могут использоваться одновременно несколько метрик, благодаря чему каждый узел коммутации будет располагать маршрутными таблицами, оптимальными в смысле разных критериев, и применяться будет та из их, которая лучше соответствует параметрам качества обслуживания, указанным в заголовке обрабатываемого пакета. Собственно измерения соответствующих «стоимостей» линий являются отдельными оригинальными задачами и здесь не рассматриваются. В качестве примера, можно указать на использование специального пакета ECHO для измерения времени задержки передачи. Каждый узел, получив такой пакет, обязан в срочном порядке дать на него ответ отсылкой аналогичного пакета. Тем самым, узел, инициировавший этот обмен, получает время двойного оборота, половина которого и дает время задержки передачи по данной линии. Для повышения достоверности измерений проводится несколько обменов пакетами ECHO и результаты измерения усредняются. Важными вопросами при измерении значений любых метрик является периодичность их повторения, пределы изменения полученных параметров, требующие оповещения «соседей», трудоемкость таких измерений и т.п.

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

Маршрутизатор формирует пакет состояния линий, включая в него поля, представленные на рис. 5.8. «Характеристиками линии» могут быть и скорость интерфейса и перечень непосредственно присоединенных сетей. Пакеты «состояния линий» рассылаются в режиме «заливки» периодически (раз в минуту, например), либо «по событию», т.е. при обнаружении изменения состояния линий, либо состава непосредственно присоединенных сетей. Более предпочтительным является второй вариант, но и первый имеет свои преимущества.

Каждый узел, получив такой пакет, сохраняет у себя ранее неизвестную ему информацию и отправляет его дальше через все свои интерфейсы, кроме того, с которого он был получен. Благодаря этому, информация о маршрутизаторах сети, о существующих парциальных сетях и к каким узлам они непосредственно присоединены, о состояниях линий, соединяющих маршрутизаторы, становится известной всем. Однако, множественность путей в многосвязной сети делает возможным получение собственных пакетов состояния, либо пакетов дубликатов; и те и другие не должны распространяться далее. Для этого введена нумерация сообщений (32-х битное поле). Получив пакет состояния, маршрутизатор сравнивает его номер с номером ранее полученного сообщения от этого же узла. Если номер прибывшего пакета меньше, либо равен номеру пакета, информация из которого уже зафиксирована в топологической таблице узла, то прибывший пакет уничтожается. Хотя переполнение счетчика отсылаемых пакетов едва ли возможно (2³²=4294967296 и при отсылке 1 сообщения в секунду счетчика «хватит» на 136,2 года), но, например, при перезагрузке маршрутизатора нумерация начнется с нуля и сообщения, не являющиеся дубликатами, могут интерпретироваться как таковые. Для предотвращения таких ошибок в заголовке введено поле «Возраст сообщения». В это поле при формировании сообщения записывается достаточно большая величина (например, 3600), которая уменьшается на единицу каждую секунду. Следовательно, неопределенность, возникающая при получении двух пакетов состояния с одинаковыми порядковыми номерами, легко разрешается: пакет, в котором значение поля «Время жизни» меньше, чем в ранее полученном с тем же номером, удаляется; в противном случае – информация из него считывается и пакет ретранслируется «соседям».

Формирование полной топологической схемы сети

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

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