Вступление
По первоначальной задумке создателя алгоритм предназначался для ориентированных графов с положительными весами рёбер. Ориентированный граф содержит ориентированные рёбра. Пройти по такому ребру можно только в одном направлении. В ip-сетях это требование, на первый взгляд, кажется невыполнимым. Любой интерфейс или порт является дуплексным, т.е. может как принимать, так и отправлять данные, поэтому каждое ребро в реальной сети двунаправленно.
Простая замена одного такого ребра на два направленных позволяет обойти ограничение:
В данной реализации направленному ребру было дано название "линк смежности" (adjacency link). Между любыми двумя узлами должно быть по два линка смежности, ну или по крайней мере очень желательно, чтобы было именно так.
Полное описание графа это массив из таких линков, где каждый представлен структурой :
struct {
u32i nodeID;
u32i localIP;
u32i mask;
u32i cost;
u32i neighIP;
u32i neighID;
};
Здесь и далее u32i это краткая запись для типа uint32_t и является полным аналогом адреса IPv4.
переменная | описание |
|---|---|
NodeID | идентификатор узла в виде ip-адреса |
localIP | ip-адрес на локальном интерфейсе этого узла |
mask | маска интерфейса |
cost | локальная стоимость интерфейса в диапазоне : 1 - 65535 |
( лупбеки могут иметь стоимость = 0 ) | |
neighIP | ip-адрес на удалённом интерфейсе |
neighID | идентификатор удалённого узла в виде ip-адреса |
Пара любых соседних узлов требует две записи типа adjLnk.
Например следующая простейшая топология
описывается двумя линками смежности :
NodeID | localIP | mask | cost | neighIP | neighID |
|---|---|---|---|---|---|
192.0.2.1 | 198.51.100.5 | 255.255.255.252 | 20000 | 198.51.100.6 | 203.0.113.4 |
203.0.113.4 | 198.51.100.6 | 255.255.255.252 | 10000 | 198.51.100.5 | 192.0.2.1 |
Стоимость линка с противоположных сторон может отличаться (в нашем случае 10'000 vs 20'000). Это нормальная практика для современных сетей.
Репозиторий
Весь код, о которым пойдёть речь дальше, можно забрать здесь :
https://github.com/fluorohead/gia_djk
Вспомогательная библиотека для манипуляций с ip-адесами :
https://github.com/fluorohead/gia_ipmnp
Дизайн библиотеки
В основе лежат два класса :
GraphIPv4 - граф
DjkIPv4 - дерево
В первую очередь необходимо пополнить линками объект класса GraphIPv4. Затем передать граф в конструктор DjkIPv4 для расчёта дерева кратчайших путей.
Для пополнения графа используются методы :
void addLink(nodeIDv4_t nodeID, linkAdjv4_t link); // добавляет один линк смежности
void addLinks(vector <linkAdjStr_t> *table); // добавляет все линки смежности из переданной таблицы
void addLinksFromFile(const string &fn); // загружает все линки смежности из двоичного файла
В случае простых топологий можно вносить каждый линк через отдельные вызовы ::addLink(), либо построить вектор и передать его в ::addLinks().
Метод пополнения из двоичного файла ::addLinksFromFile() больше подходит для крупной базы данных, взятой из реальной сети.
Если имеется доступ к боевому маршрутизатору Cisco ASR, работающему под IOS XR, можно воспользоваться конвертором из архива xroconv.zip. В текстовый файл собирается вывод команды "show ospf database router" и передаётся на обработку конвертору. К сожалению поддерживаются только анонсы LSA Type 1, другие типы будут игнорироваться. Сгенерированный файл представляет собой бинарник из записей типа adjLnk, следующих один за другим без каких-либо дополнительных разделителей. Порядок байтов в файле : младшие идут первыми (при разглядывании в hex-редакторе, ip-адреса отобразятся в перевёрнутом виде).
Компиляция полного проекта из main.cpp даст рабочую утилиту. При запуске, в аргументах передаётся полученный двоичный файл. После расчёта дерева на экран будет выводится результирующая таблица маршрутизации (Router Information Base).
В реальных сетях, построенных по технологии Ethernet (и не только), встречаются интересные особенности. Например, несколько узлов, включенных через коммутатор в один широковещательный домен. Для полного описания такого сегмента понадобится n * (n - 1) направленных линков смежности (т.е. в два раза больше ненаправленных). А поскольку это задача того, кто подготавливает таблицу линков, а не самого алгоритма, можем считать, что алгоритму всё-равно какого типа физическое подключение : широковещательное, точка-точка или множественный доступ без широковещания. Главное описать все возможные линки смежности на данном сегменте сети между каждой парой узлов.
В протоколах OSPF, IS-IS и CSPF TE, а в ip-сетях это основные "пользователи" алгоритма Дейкстры, встречаются параллельные пути с одинаковой стоимостью, называемые equal-cost multi-path (ECMP). В данном коде параллельные пути учтены.
Пример топологии
Рассмотрим пример сети, построенной на основе протокола IPv4 :
Интерфейс между двумя маршрутизаторами это ненаправленное ребро, раскладывающееся на два линка смежности, что упоминалось выше. Адресация интерфейсов (ip-сегментов) не приводится, чтобы не загромождать рисунок. Указаны только loopback-сети и локальные стоимости всех интерфейсов. Loopback - тоже интерфейс, требующий только одного линка смежности. На рисунке указаны и два "тупиковых" сегмента, смотрящие в сторону коммутаторов switch02 и switch03. Термин "тупиковый" в разных контекстах может означать немного разные понятия. В нашем примере такие сегменты не имеют соседних узлов. Тупиковое ребро тоже описывается лишь одним линком смежности, о чём будет ниже.
Стоимости (cost'ы) рассчитываются либо назначаются для разных сущностей :
локальная стоимость интерфейса (1 - 65535) : назначаемая.
локальная стоимость подключенного ip-сегмента (1 - 65535) : назначаемая.
кумулятивная стоимость маршрута до удалённого узла (1 - UINT32MAX) : расчётная.
кумулятивная стоимость маршрута до удалённого ip-сегмента (1 - UINT32MAX) : расчётная.
Кумулятивная стоимость корневого узла всегда = 0. Это единственное исключение из правила, требующего, чтобы КК до удалённого узла был минимум 1.
Локальная стоимость ip-сегмента автоматически равна локальной стоимости интерфейса, которому назначен этот сегмент.
Кумулятивная стоимость значит суммарная, т.е. сумма всех участков пути от Source до Destination. Суммарная стоимость 0 может быть только у корневого узла, и это важное исходное значение, без которого алгоритм не начнёт правильно работать. Каждый узел рассматривает себя в качестве корневого, и каждый рассчитывает свою копию дерева кратчайших путей до всех остальных узлов сети. Далее будет использоваться сокращение КК для обозначения кумулятивного коста.
Рассчитываются пути именно до узлов, а не до ip-сегментов. Получив стоимость пути до узла, мы автоматически получаем и кумулятивную стоимость любого ip-сегмента, подключенного к узлу :
кумулятивная стоимость ip-сегмента = сумме кумулятивной стоимости узла и локальной стоимости интерфейса, которому назначен ip-адрес из данного сегмента.
Здесь и далее будем считать, что интерфейс и назначенный ему ip-адрес это одно и то же.
В файле example_table.h содержится вектор всех линков смежности, описывающих данную топологию.
Рассмотрим несколько примеров из этого файла :
...
{"10.0.0.1", "10.254.241.2", "255.255.255.252", 5, "10.254.241.1", "172.16.0.1"}, // S to A
...
{"172.16.0.1","10.254.241.1", "255.255.255.252", 5, "10.254.241.2", "10.0.0.1"} // A to S
...
{"172.16.0.1","8.8.8.2", "255.255.255.0", 17, "0.0.0.0", "0.0.0.0"}, // A to switch (stub, no neighbor)
...
{"10.0.0.1", "10.0.0.1", "255.255.255.255", 0, "10.0.0.1", "10.0.0.1"}, // loopback S
{"172.16.0.1", "172.16.0.1", "255.255.255.255", 0, "172.16.0.1", "172.16.0.1"}, // loopback A
NodeID | localIP | mask | cost | neighIP | neighID |
|---|---|---|---|---|---|
10.0.0.1 | 10.254.241.2 | 255.255.255.252 | 5 | 10.254.241.1 | 172.16.0.1 |
172.16.0.1 | 10.254.241.1 | 255.255.255.252 | 5 | 10.254.241.2 | 10.0.0.1 |
172.16.0.1 | 8.8.8.2 | 255.255.255.0 | 17 | 0.0.0.0 | 0.0.0.0 |
10.0.0.1 | 10.0.0.1 | 255.255.255.255 | 0 | 10.0.0.1 | 10.0.0.1 |
172.16.0.1 | 172.16.0.1 | 255.255.255.255 | 0 | 172.16.0.1 | 172.16.0.1 |
Первые две строки описывают ненаправленное ребро, т.е. нетупиковый сегмент сети, между узлами "S" и "A" (либо "A" и "S", что одно и то же). Поскольку это полноценные маршрутизаторы, то здесь два линка смежности для одного сегмента.
Третья строка описывает тупиковый сегмент, т.к. за коммутатором switch02 нет других маршрутизаторов. Именно поэтому поля neighIP и neighID равны 0.0.0.0, что тоже важный момент, на который стоит обратить внимание. С помощью таких значений мы указываем коду не искать узлы за данным интерфейсом.
Последние две строки описывают лупбеки. Как и тупиковые сети, они не участвуют в рассчётах. Лупбек это локальный петлевой интерфейс, как бы смотрящий обратно на узел. Для лупбеков маска не всегда /32, но вот поля localIP, neighIP, neighID обязательно должны быть равны NodeID - таким образом мы отличим лупбек от тупиковой сети либо обычной сети.
Теперь рассмотрим другой интересный участок :
Так называемые L2-коммутаторы не являются участниками ip-сетей и в алгоритме кратчайших путей не участвуют. Да, разумеется, они передают кадры, внутри которых нагрузка (payload) с ip-пакетами, но знать им об этом совершенно не обязательно. С таким же успехом они передают ARP, MPLS и много чего ещё. Некоторые модели L2-свитчей умеют заглядывать и в ip-пакеты, например, для реализации функционала igmp snooping'а или защиты от dhcp-атак. В нашем примере коммутаторы являются обычными мостами для организации взаимодействия подключенных маршрутизаторов, позволяя экономить физические порты роутеров и уменьшать количество настроек. В реальности свитчи чаще используются в локальных сетях (LAN) и ЦОД'ах.
Через коммутатор switch01 три маршрутизатора образуют смежность друг с другом. Виртуально организуются три ненаправленных ребра :
Но у нас был ещё один линк не через свитч, вернём его сюда :
Два верхних параллельных ненаправленных ребра в реальных сетях могли бы использоваться для балансировки нагрузки. Их можно агрегатировать в один интерфейс, либо оставить разделёнными, тогда наша реализация алгоритма Дейкстры обнаружит два параллельных пути от "S" до "C" с одинаковой стоимостью 11. В обратную сторону от "C" до "S" стоимости окажутся разными (10 vs 11), и будет выбран только один линк со стоимостью 10. Вообще стоит сказать, что изначально алгоритм не работал с ECMP. Небольшие доработки кода позволили обучить его и этому.
Следующие линки смежности описывают вышеобозначенный кусок сети :
{"10.0.0.1", "10.254.241.49", "255.255.255.248", 11, "10.254.241.50", "10.0.0.3"}, // S to C
{"10.0.0.1", "10.254.241.45", "255.255.255.252", 11, "10.254.241.46", "10.0.0.3"}, // S to C
{"10.0.0.1", "10.254.241.49", "255.255.255.248", 11, "10.254.241.51", "10.0.0.4"}, // S to G
{"10.0.0.3","10.254.241.50", "255.255.255.252", 10, "10.254.241.49", "10.0.0.1"}, // C to S
{"10.0.0.3","10.254.241.46", "255.255.255.252", 11, "10.254.241.45", "10.0.0.1"}, // C to S
{"10.0.0.3","10.254.241.50", "255.255.255.252", 10, "10.254.241.51", "10.0.0.4"}, // C to G
{"10.0.0.4","10.254.241.51", "255.255.255.248", 10, "10.254.241.49", "10.0.0.1"}, // G to S
{"10.0.0.4","10.254.241.51", "255.255.255.252", 10, "10.254.241.50", "10.0.0.3"}, // G to C
{"10.0.0.1", "10.0.0.1", "255.255.255.255", 0, "10.0.0.1", "10.0.0.1"}, // loopback S
{"10.0.0.3","10.0.0.3", "255.255.255.255", 0, "10.0.0.3", "10.0.0.3"}, // loopback C
{"10.0.0.4","10.0.0.4", "255.255.255.255", 0, "10.0.0.4", "10.0.0.4"}, // loopback G
Пример проекта
У нас есть исходные данные, теперь можно написать несложный код для рассчёта кратчайших путей.
Файл main.cpp из репозитория мы использовать не будем, т.к. он у нас для компиляции утилиты. Напишем другой. Понадобится подключить к новому проекту следующие файлы:
gia_ipmnp.h // из соседнего репо
gia_ipmnp.cpp // из соседнего репо
gia_djk.h
gia_djk.cpp
example_table.h
Примерно такой код добавим в новый main.cpp :
#include <iostream>
#include "gia_ipmnp.h"
#include "gia_djk.h"
#include "example_table.h"
using namespace std;
extern const array <string,4> djkStStr;
int main()
{
GraphIPv4 graph01;
graph01.addLinks(&adjVec);
graph01.printGraph();
DjkIPv4 tree01(v4mnp::to_u32i("10.0.0.1"), &graph01, true);
cout << " Dijkstra state : " << djkStStr[u32i(tree01.getState())] << endl;
tree01.printREI();
tree01.printRIB();
return 0;
}
Пока всё просто. Создали объект графа и через вызов ::addLinks() наполнили данными об узлах и рёбрах. Напечатали на экране через ::printGraph(). Затем создали объект дерева, передав параметры конструктору : NodeID корневого узла "S", указатель на объект графа, и последним параметром (true) включили режим отладки, чтобы каждая итерация алгоритма вываливала в консоль кучу интересной информации.
Вызов ::printREI() отображает таблицу достижимости узлов (REachability Information) из корневого узла. Это полуфабрикат окончательной таблицы маршрутизации RIB, которая в свою очередь выводится методом ::printRIB().
Прежде чем перейти к описанию внутренней работы кода, необходимо всё же ещё раз пройтись по сути алгоритма Дейкстры и подробно рассмотреть каждую итерацию.
Алгоритм
Выбрали корневой узел и обошли подключенные интерфейсы.
За каждым из интерфейсов нашли соседа и просчитали кумулятивный кост до этого соседа. Он будет равен косту корневого узла + кост интерфейса на корневом узле. Запомнили эти данные, а точнее подписали их найденным соседям.
Далее забыли про корневой узел, он больше не будет рассматриваться.
Выбрали среди оставшихся узлов такой, у которого сейчас наименьший кумулятивный кост.
Снова обошли подключенные интерфейсы выбранного узла, нашли за ними соседей.
Для каждого соседа высчитали кум. кост, равный косту выбранного узла + стоимость интерфейса, за которым сидит сосед.
Важный момент : у любого узла уже есть какой-то кумулятивный кост, в том числе и у корневого узла кстати. О том, какой именно, будет рассказано ниже.
Сравниваем новый рассчитанный кост с текущим.
Если новый меньше (лучше), значит удаляем старый и назначаем ему новый.
Если новый равен текущему, значит мы нашли параллельный путь с той же стоимостью. Это хорошо, но кум. кост не изменяется.
Если новый больше (хуже), то такой путь нам не интересен, забыли про него.
Забыли про выбранный узел, он больше не будет рассматриваться.
Т.к. мы постоянно вычёркиваем уже рассмотреные узлы, то рано или поздно их не останется - это состояние завершения работы алгоритма. В ином случае снова переходим к п.4.
Дерево готово.
Обратите внимание на разницу в понятиях узел и сосед, т.к. не все узлы являются соседями друг другу. Когда мы говорим про узел, подразумевается, что на текущей итерации мы выбрали его из графа и обходим подключенные интерфейсы в поисках смежных сущностей. После обновления кумулятивных костов, выбирается следующий узел, которым теперь может стать и какой-нибудь сосед из предыдущего шага. Когда-то он был чьим-то соседом, а сейчас он выбранный узел. Выбранный - это переходящий титул. Узел может стать выбранным только один раз. А вот соседом, для которого пересматривается кум. кост, может становиться несколько раз за время работы алгоритма. В литературе чаще встречается понятие рассматриваемый, вместо выбранный - в данном случае это идентичные понятия.
Ещё несколько важных моментов. В списке шагов не указано, но на самом деле имеется следующее : мы не просто подписываем новый лучший либо равный кум. кост соседу, но так же и запоминаем через какого предка (parent) и какой интерфейс предка должен быть проложен путь, чтобы у соседа была именно такая кумулятивная стоимость. Ещё раз напомню, что кумулятивная стоимость узла это сумма всех участков пути от корня до конкретного узла. Далее эта информация поможет пройти в обратном направлении от конечного узла до корня и таким образом понять через какой интерфейс корня достижим удалённый узел. Этот процесс было решено назвать обратной трассировкой.
Особо отметим подготовительную часть, условно назвав это шагом №0, когда происходит инициализация дерева начальными значениями. Благодаря этому можно особо не выделять шаги с 1 по 3, а переходить сразу к 4-му. Давайте вообще их вычеркнем и упростим описание алгоритма, а то получилось как-то избыточно.
Подготовительная часть логически вытекает из предположения, что первоначальное состояние нерассчитанного дерева это просто набор разрозненных узлов, не соединённых между собой. Т.е. корень не знает через какие интерфейсы ему добраться до других участников топологии, а значит они недостижимы. У недостижимых узлов стоимость наихудшая (максимальная) и равна максимальному положительному целому, которое умещается в 32 битах : 0xFFFFFFFF или десятичное 4'294'967'295. Для большей наглядности оно будет заменяться на строковое представление 'INFINITY' или 'Inf'.
Вот как выглядит наше дерево в исходном состоянии :
Пока есть только корень и узлы, но нет веток.
Обратите внимание на КК корневого узла = 0. Это позволяет начать работу алгоритма сразу с 4 пункта. Нулевая стоимость может быть только у корневого узла. Нельзя назначать нулевые косты на интерфейсы : в таком случае алгоритм может простроить путь обратно к выбранному узлу, т.е. породить петлю маршрутизации.
Перечислим ещё раз основные шаги, но в более сжатом виде :
Инициализация дерева : КК = 0 для корня и КК = Inf для всех остальных.
Создаём список узлов для посещения (назовём его unseen) : добавляем туда все узлы.
Выбираем из unseen узел с наименьшим КК.
Обходим все интерфейсы выбранного узла. За каждым интерфейсом обновляем КК для соседа, если рассчитанный КК лучше, чем текущий.
Удаляем выбранный узел из unseen.
Если unseen пустой, то конец. В ином случае переходим к 2.
Под капотом
Переходим к рассмотрению работы кода библиотеки.
Шаги 0 и 1 : Инициализация дерева и создание списка unseen выполняются методом DjkIPv4::initTree().
Получаем дерево :
---------------------|-------------------|----------------------|----------------------|----------------------|
Child node | Node cumul. cost | Best parent | Parent iface | Child iface |
---------------------|-------------------|----------------------|----------------------|----------------------|
10.0.0.1 : 0 : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.2 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.3 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.4 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
172.16.0.1 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
172.16.172.10 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
172.16.172.66 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
192.168.0.5 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
192.168.168.7 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
---------------------------------------------------------------------------------------------------------------
И список :
Unseen nodes:
[ 10.0.0.1, 10.0.0.2, 10.0.0.3, 10.0.0.4, 172.16.0.1, 172.16.172.10, 172.16.172.66, 192.168.0.5,192.168.168.7, ]
Шаг 2 : Выбираем из unseen узел с наименьшим КК. Очевидно, что это узел 10.0.0.1 ("S").
Шаг 3 : Обходим все интерфейсы выбранного узла "S" :
{"10.0.0.1", "10.254.241.2", "255.255.255.252", 5, "10.254.241.1", "172.16.0.1"},
{"10.0.0.1", "10.254.241.9", "255.255.255.252", 10, "10.254.241.10", "192.168.168.7"},
{"10.0.0.1", "10.254.241.49", "255.255.255.248", 11, "10.254.241.50", "10.0.0.3"},
{"10.0.0.1", "10.254.241.45", "255.255.255.252", 11, "10.254.241.46", "10.0.0.3"},
{"10.0.0.1", "10.254.241.49", "255.255.255.248", 11, "10.254.241.51", "10.0.0.4"},
{"10.0.0.1", "10.0.0.1", "255.255.255.255", 0, "10.0.0.1", "10.0.0.1"}, // loopback
А именно :
10.254.241.2
10.254.241.9
10.254.241.49
10.254.241.45
10.0.0.1
Нас интересуют соседи, сидящие за этими линками :
172.16.0.1
192.168.168.7
10.0.0.3
10.0.0.4
Обратим внимание, что сосед 10.0.0.3 достижим через два интерфейса : 10.254.241.45 и 10.254.241.49; причём стоимость интерфейсов одинаковая. О подобном уже упоминалось. Если два данных маршрута (а их может быть и больше, кстати) окажутся лучшими по стоимости, то получим два equal-cost-пути. Позже мы это проверим, т.к. пока не знаем будут ли такие маршруты лучшими в сравнении с другими. А вдруг нет? Окончательно можно сказать только после полной калькуляции дерева.
Cейчас нужно рассчитать оценочные и сравнить с теми КК, которые уже ассоциированны с каждым соседом. Оценочный КК соседа будет равен сумме КК выбранного узла и стоимости интерфейса в сторону соседа.
Сосед | Текущий КК | Оценочный КК | Результирующий КК |
|---|---|---|---|
172.16.0.1 | Inf | 5 | 5 |
192.168.168.7 | Inf | 10 | 10 |
10.0.0.3 | Inf | 11 | 11 |
10.0.0.4 | Inf | 11 | 11 |
Понятно, что на данной итерации все результирующие КК победили текущие, т.к. любая другая стоимость меньше, а значит лучше, чем бесконечность.
Отлично, сделаем результирующие данные текущими. Таблица дерева приобретает вид :
---------------------|-------------------|----------------------|----------------------|----------------------|
Child node | Node cumul. cost | Best parent | Parent iface | Child iface |
---------------------|-------------------|----------------------|----------------------|----------------------|
10.0.0.1 : 0 : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.2 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.3 : 11 : 10.0.0.1 : 10.254.241.49 : 10.254.241.50 :
10.0.0.3 : 11 : 10.0.0.1 : 10.254.241.45 : 10.254.241.46 :
10.0.0.4 : 11 : 10.0.0.1 : 10.254.241.49 : 10.254.241.51 :
172.16.0.1 : 5 : 10.0.0.1 : 10.254.241.2 : 10.254.241.1 :
172.16.172.10 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
172.16.172.66 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
192.168.0.5 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
192.168.168.7 : 10 : 10.0.0.1 : 10.254.241.9 : 10.254.241.10 :
---------------------------------------------------------------------------------------------------------------
Кстати мы не только обновили текущие КК, но и запомнили через какого ближайшего предка и какие интерфейсы предка достижим данный узел.
Это уже что-то. Начало положено. Идём дальше.
Шаг 4 : удаляем выбранный узел "S" из unseen :
Теперь unseen стал короче на одну запись
Unseen nodes:
[ 10.0.0.2, 10.0.0.3, 10.0.0.4, 172.16.0.1, 172.16.172.10, 172.16.172.66, 192.168.0.5,192.168.168.7, ]
Шаг 5 : список unseen пустой? Нет, там ещё много узлов - значит снова перескакиваем на Шаг 2.
Шаг 2 : опять выбираем из unseen узел с минимальным КК :
Теперь это узел "A" 172.16.0.1
Шаг 3 : Обходим все интерфейсы выбранного узла “A” :
{"172.16.0.1","10.254.241.1", "255.255.255.252", 5, "10.254.241.2", "10.0.0.1"},
{"172.16.0.1","10.254.241.5", "255.255.255.252", 16, "10.254.241.6", "192.168.0.5"},
{"172.16.0.1","8.8.8.2", "255.255.255.0", 17, "0.0.0.0", "0.0.0.0"}, // stub
{"172.16.0.1", "172.16.0.1", "255.255.255.255", 0, "172.16.0.1", "172.16.0.1"}, // loopback
За которыми видим соседей :
10.0.0.1
192.168.0.5
Посчитаем оценочные КК :
Сосед | Текущий КК | Оценочный КК | Результирующий КК |
|---|---|---|---|
10.0.0.1 | 0 | 5 | 0 |
192.168.0.5 | Inf | 21 | 21 |
Помним, что 10.0.0.1 это узел "S", который был первым выбранным узлом, интерфейсы которого мы рассматривали. Но сейчас это просто сосед узла "A", поэтому мы точно так же рассчитываем для "S" оценочный КК, не смотря на то, что у него уже есть какой-то от предыдущих рассчётов. И затем точно так же сравниваем оценочный с текущим. Это очень удобно, когда для всех участников применяется один и тот же подход. Нам не нужно заморачиваться и как-то особо выделять корень и корневые интерфейсы.
Что у нас с деревом :
---------------------|-------------------|----------------------|----------------------|----------------------|
Child node | Node cumul. cost | Best parent | Parent iface | Child iface |
---------------------|-------------------|----------------------|----------------------|----------------------|
10.0.0.1 : 0 : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.2 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.3 : 11 : 10.0.0.1 : 10.254.241.49 : 10.254.241.50 :
10.0.0.3 : 11 : 10.0.0.1 : 10.254.241.45 : 10.254.241.46 :
10.0.0.4 : 11 : 10.0.0.1 : 10.254.241.49 : 10.254.241.51 :
172.16.0.1 : 5 : 10.0.0.1 : 10.254.241.2 : 10.254.241.1 :
172.16.172.10 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
172.16.172.66 : INFINITY : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
192.168.0.5 : 21 : 172.16.0.1 : 10.254.241.5 : 10.254.241.6 :
192.168.168.7 : 10 : 10.0.0.1 : 10.254.241.9 : 10.254.241.10 :
---------------------------------------------------------------------------------------------------------------
Обновилось ещё немного информации.
Шаг 4 : удаляем выбранный узел "A" из unseen :
Список unseen стал короче ещё на одну запись
Unseen nodes:
[ 10.0.0.2, 10.0.0.3, 10.0.0.4, 172.16.172.10, 172.16.172.66, 192.168.0.5,192.168.168.7, ]
Шаг 5 : список unseen пустой? Нет, там ещё много узлов - значит снова перескакиваем на Шаг 2.
И так далее.
Давайте пропустим оставшиеся итерации, сразу посмотрев на окончательный результат :
---------------------|-------------------|----------------------|----------------------|----------------------|
Child node | Node cumul. cost | Best parent | Parent iface | Child iface |
---------------------|-------------------|----------------------|----------------------|----------------------|
10.0.0.1 : 0 : 0.0.0.0 : 0.0.0.0 : 0.0.0.0 :
10.0.0.2 : 21 : 192.168.0.5 : 10.254.241.37 : 10.254.241.38 :
10.0.0.3 : 11 : 10.0.0.1 : 10.254.241.49 : 10.254.241.50 :
10.0.0.3 : 11 : 10.0.0.1 : 10.254.241.45 : 10.254.241.46 :
10.0.0.4 : 11 : 10.0.0.1 : 10.254.241.49 : 10.254.241.51 :
172.16.0.1 : 5 : 10.0.0.1 : 10.254.241.2 : 10.254.241.1 :
172.16.172.10 : 12 : 10.0.0.3 : 10.254.241.25 : 10.254.241.26 :
172.16.172.10 : 12 : 10.0.0.4 : 10.254.241.13 : 10.254.241.14 :
172.16.172.66 : 29 : 10.0.0.2 : 10.254.241.53 : 10.254.241.54 :
192.168.0.5 : 13 : 172.16.172.10 : 10.254.241.34 : 10.254.241.33 :
192.168.168.7 : 10 : 10.0.0.1 : 10.254.241.9 : 10.254.241.10 :
---------------------------------------------------------------------------------------------------------------
Рисунок более нагляден :
Странно дерево получилось : сросшиеся ветки это наверное ошибки рассчётов? А ещё кажется будто участок "S-C-E-G" образует петлю, и всё в таком духе. Но нет, петли не образуется : линки-то направленные! По таким линкам можно пройти только в одном направлении, значит никаких петель нет.
В нашей реальности подобный вид деревьев кратчайших путей является абсолютной нормой.
Алгоритм рассчитал, что узел "C" достижим двумя параллельными путями с одинаковой стоимостью.
Узлы "E", "D", "F" и "X" - эти вообще достижимы балансировкой по трём параллельным интерфейсам : двум в сторону "C" и ещё одним в сторону "G". Именно то, что было заложено в граф. Мы отбросили всё лишнее, оставив только лучшие пути в сторону каждого участника топологии.
Но и это ещё не конец. Да, это завершение работы алгоритма Дейкстры, но на этом вычисления не заканчиваются. Осталась самая малость : вычислить кумулятивные стоимости ip-сетей и построить наконец то, что строит любой роутер - таблицу маршрутизации.
Таблица маршрутизации (RIB)
Поскольку корневым узлом мы указывали узел "S", то и таблицу маршрутизации будем формировать для этого узла.
Что вообще такое RIB?
Это список всех ip-сегментов топологии с информацией через какой интерфейс локального узла они достижимы.
Например, нам нужно узнать через какой интерфейс узла "S" начать передавать ip-пакеты, адресованные 10.0.0.2. Мы знаем, то 10.0.0.2 это лупбек узла "F". На узле "F" данный лупбек имеет локальную стоимость 0, а кумулятивная стоимость узла "F" рассчитана алгоритмом и составляет 21. Значит КК для лупбека составит 0 + 21 = 21. Это нужная информация, но пока не самая необходимая, т.к. мы всё ещё не знаем из какого интерфейса узла "S" выплюнуть пакет, чтобы тот смог достичь адреса 10.0.0.2.
Вспомним, что таблица дерева имеет информацию о предках. Мы заранее позаботились о сохранении такой информации именно для того, чтобы потом сформировать RIB.
Но какой из 5 интерфейсов на последнем рисунке использовать? Это точно не ".2|.1" и не ".9|.10", т.к. они ведут к листьям "A" и "B", а листья это узлы-окончания, за которыми нет других узлов. Обратите внимание на нотацию ребра : именно таким образом мы делаем ребро уникальным и отличным от стальных. Например на узле "S" есть два ребра, начинающихся с .49, тогда как их отличить друг от друга? - С помощью нотации, где указано не только начало, но и конец ребра.
Человеку абсолютно очевидно, что нужно использовать 3 equal-cost пути через рёбра ".45|.46", ".49|.50" и ".49|.51". Но то, что очевидно человеку, не очевидно машине. Поэтому самым логичным будет взять узел "F" и пройти в обратном направлении : мы узнаем через какой интерфейс корня вернёмся в узел "S". Это и будет тем интерфейсом, через который достижим узел "F".
Смотрим в последнюю таблицу дерева :
---------------------|-------------------|----------------------|----------------------|----------------------|
Child node | Node cumul. cost | Best parent | Parent iface | Child iface |
---------------------|-------------------|----------------------|----------------------|----------------------|
...
10.0.0.2 : 21 : 192.168.0.5 : 10.254.241.37 : 10.254.241.38 :
...
Эта строка говорит нам вернуться из "F" (10.0.0.2) в "D" (192.168.0.5) по ребру ".37|.38".
Хорошо, вернулись в "D".
Вот наш "D" :
---------------------|-------------------|----------------------|----------------------|----------------------|
Child node | Node cumul. cost | Best parent | Parent iface | Child iface |
---------------------|-------------------|----------------------|----------------------|----------------------|
...
192.168.0.5 : 13 : 172.16.172.10 : 10.254.241.34 : 10.254.241.33 :
...
Кто у него предок :
---------------------|-------------------|----------------------|----------------------|----------------------|
Child node | Node cumul. cost | Best parent | Parent iface | Child iface |
---------------------|-------------------|----------------------|----------------------|----------------------|
...
172.16.172.10 : 12 : 10.0.0.3 : 10.254.241.25 : 10.254.241.26 :
172.16.172.10 : 12 : 10.0.0.4 : 10.254.241.13 : 10.254.241.14 :
...
А у него их целых два. Совершенно нормальная ситуация. Обратная трассировка разветвляется на проход через "C" 10.0.0.3 и "G" 10.0.0.4.
Произведя ещё несколько откатов, предком становится "S". Запоминаем через какие рёбра мы в него вернулись : ".45|.46", ".49|.50", ".49|.51".
Это значит, что "F" достижим через :
Node: [10.0.0.2]; cost [21]
> via iface: 10.254.241.45; next-hop: 10.254.241.46
> via iface: 10.254.241.49; next-hop: 10.254.241.50
> via iface: 10.254.241.49; next-hop: 10.254.241.51
А поскольку мы знаем о всех подключенных к "F" сегментах, то сразу можем сфомировать и таблицу маршрутов до них :
Net: 10.0.0.2/32
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 21; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 21; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 21; origin.: 10.0.0.2
Net: 10.254.241.52/30
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 29; origin.: 10.0.0.2
> via iface:10.254.241.49; next-hop: 10.254.241.50; cost: 29; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 29; origin.: 10.0.0.2
Вопрос: куда делся сегмент 10.254.241.36/30 ? Он ведь тоже подключен к "F". Да, это так, но зачем идти до "F", если можно остановиться на "D" и не совершать лишних операций?
Net: 10.254.241.36/30
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 21; origin.: 192.168.0.5
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 21; origin.: 192.168.0.5
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 21; origin.: 192.168.0.5
Очевидно, что путь через "D" короче просто потому, что "D" ближе к "S".
В общем аналогичным образом, т.е. обратной трассировкой из Destination в Source, мы повторяем процедуру для каждого узла, получая в итоге таблицу достижимости узлов (REI-таблица) :
Node: [10.0.0.1]; cost [0]
> via iface: 0.0.0.0; next-hop: 0.0.0.0
Node: [10.0.0.2]; cost [21]
> via iface: 10.254.241.45; next-hop: 10.254.241.46
> via iface: 10.254.241.49; next-hop: 10.254.241.50
> via iface: 10.254.241.49; next-hop: 10.254.241.51
Node: [10.0.0.3]; cost [11]
> via iface: 10.254.241.45; next-hop: 10.254.241.46
> via iface: 10.254.241.49; next-hop: 10.254.241.50
Node: [10.0.0.4]; cost [11]
> via iface: 10.254.241.49; next-hop: 10.254.241.51
Node: [172.16.0.1]; cost [5]
> via iface: 10.254.241.2; next-hop: 10.254.241.1
Node: [172.16.172.10]; cost [12]
> via iface: 10.254.241.45; next-hop: 10.254.241.46
> via iface: 10.254.241.49; next-hop: 10.254.241.50
> via iface: 10.254.241.49; next-hop: 10.254.241.51
Node: [172.16.172.66]; cost [29]
> via iface: 10.254.241.45; next-hop: 10.254.241.46
> via iface: 10.254.241.49; next-hop: 10.254.241.50
> via iface: 10.254.241.49; next-hop: 10.254.241.51
Node: [192.168.0.5]; cost [13]
> via iface: 10.254.241.45; next-hop: 10.254.241.46
> via iface: 10.254.241.49; next-hop: 10.254.241.50
> via iface: 10.254.241.49; next-hop: 10.254.241.51
Node: [192.168.168.7]; cost [10]
> via iface: 10.254.241.9; next-hop: 10.254.241.10
Используя данные о подключенных ip-сегментах, вычисляем RIB :
Net: 8.8.8.0/24
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 22; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 22; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 22; origin.: 10.0.0.2
> via iface: 10.254.241.2; next-hop: 10.254.241.1; cost: 22; origin.: 172.16.0.1
Net: 10.0.0.1/32
> via iface: 0.0.0.0; next-hop: 0.0.0.0; cost: 0; origin.: 10.0.0.1
Net: 10.0.0.2/32
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 21; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 21; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 21; origin.: 10.0.0.2
Net: 10.0.0.3/32
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 11; origin.: 10.0.0.3
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 11; origin.: 10.0.0.3
Net: 10.0.0.4/32
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 11; origin.: 10.0.0.4
Net: 10.254.241.0/30
> via iface: 0.0.0.0; next-hop: 0.0.0.0; cost: 5; origin.: 10.0.0.1
Net: 10.254.241.4/30
> via iface: 10.254.241.2; next-hop: 10.254.241.1; cost: 21; origin.: 172.16.0.1
Net: 10.254.241.8/30
> via iface: 0.0.0.0; next-hop: 0.0.0.0; cost: 10; origin.: 10.0.0.1
Net:10.254.241.12/30
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 12; origin.: 10.0.0.4
Net: 10.254.241.16/30
> via iface: 10.254.241.9; next-hop: 10.254.241.10; cost: 12; origin.: 192.168.168.7
Net: 10.254.241.20/30
> via iface: 10.254.241.9; next-hop: 10.254.241.10; cost: 18; origin.: 192.168.168.7
Net: 10.254.241.24/30
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 12; origin.: 10.0.0.3
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 12; origin.: 10.0.0.3
Net: 10.254.241.28/30
> via iface: 10.254.241.9; next-hop: 10.254.241.10; cost: 30; origin.: 192.168.168.7
Net: 10.254.241.32/30
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 13; origin.: 172.16.172.10
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 13; origin.: 172.16.172.10
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 13; origin.: 172.16.172.10
Net: 10.254.241.36/30
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 21; origin.: 192.168.0.5
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 21; origin.: 192.168.0.5
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 21; origin.: 192.168.0.5
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 21; origin.: 192.168.0.5
Net: 10.254.241.40/30
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 24; origin.: 172.16.172.10
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 24; origin.: 172.16.172.10
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 24; origin.: 172.16.172.10
Net: 10.254.241.44/30
> via iface: 0.0.0.0; next-hop: 0.0.0.0; cost: 11; origin.: 10.0.0.1
Net: 10.254.241.48/29
> via iface: 0.0.0.0; next-hop: 0.0.0.0; cost: 11; origin.: 10.0.0.1
Net: 10.254.241.52/30
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 29; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 29; origin.: 10.0.0.2
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 29; origin.: 10.0.0.2
Net: 172.16.0.1/32
> via iface: 10.254.241.2; next-hop: 10.254.241.1; cost: 5; origin.: 172.16.0.1
Net: 172.16.172.10/32
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 12; origin.: 172.16.172.10
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 12; origin.: 172.16.172.10
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 12; origin.: 172.16.172.10
Net: 172.16.172.66/32
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 29; origin.: 172.16.172.66
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 29; origin.: 172.16.172.66
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 29; origin.: 172.16.172.66
Net: 192.168.0.5/32
> via iface: 10.254.241.45; next-hop: 10.254.241.46; cost: 13; origin.: 192.168.0.5
> via iface: 10.254.241.49; next-hop: 10.254.241.50; cost: 13; origin.: 192.168.0.5
> via iface: 10.254.241.49; next-hop: 10.254.241.51; cost: 13; origin.: 192.168.0.5
Net: 192.168.168.7/32
> via iface: 10.254.241.9; next-hop: 10.254.241.10; cost: 10; origin.: 192.168.168.7
Все маршруты из корня построены.
Послесловие
Алгоритм кратчайших путей это довольно простое для понимания открытие Эдсгера Дейкстры. В Сети существует достаточно много материала на данную тему, и на Хабре в том чисе. Поиск по ресурсу выдал примерно 20 страниц со статьями, но к сожалению среди них не было ни одной достаточно подробной по работе алгоритма в ip-сетях. Возможно где-то есть англоязычные материалы, но вот с подробными русскоязычными беда - это и стало причиной собственного небольшого исследования.
Список использованной литературы :
"Грокаем алгоритмы", Адитья Бхаргава, 2024
"Алгоритмы. Руководство по разработке.", 3-е изд., Стивен Скиена, 2020
"Язык программирования С++", 6-е изд., Стивен Прата, 2020
Замечания и критика приветствуются.
