3.4 Методы локальной оптимизации маршрутов. Алгоритм Дейкстры и Форда-Фалкерсона, их различие в получении маршрутной таблицы. Децентрализованный алгоритм маршрутизации, обработка событий
1. Введение: Контекст локальной оптимизации
В сетевых технологиях локальная оптимизация маршрутов означает поиск наилучшего пути в условиях ограниченной информации. В отличие от глобальной оптимизации (где известна вся топология), локальная оперирует данными от соседей. Однако классические алгоритмы Дейкстры и Форда-Фалкерсона (чаще говорят о Форде-Беллмане, но в контексте потоков упоминают и Фалкерсона) являются фундаментом для расчета этих маршрутов.
2. Алгоритм Дейкстры (Link-State подход)
Алгоритм Дейкстры — это централизованный (или территориальный) алгоритм, работающий по принципу “жадного” поиска в графе с неотрицательными весами ребер.
- Суть: Поиск кратчайшего пути от одной вершины (источника) до всех остальных.
- Механизм: Вершины делятся на два множества: обработанные (с известным расстоянием) и необработанные. Алгоритм постоянно выбирает вершину с наименьшей текущей меткой расстояния, релаксирует (ослабляет) все исходящие из неё ребра и перемещает её в обработанные.
- Результат: Дерево кратчайших путей (Shortest Path Tree).
Как строится маршрутная таблица?
При использовании Дейкстры каждый узел (роутер) должен иметь полную карту сети (Link-State Database). Алгоритм запускается локально на каждом роутере.
- Роутер получает топологию сети (через LSA-пакеты).
- Запускает алгоритм Дейкстры, считая себя корнем.
- В таблицу маршрутизации записывается Next-Hop (следующий роутер), который ведет к каждой подсети.
Итог таблицы: Статичен до следующего пересчета. Данные в таблице — это точное математическое решение (оптимум) для текущего состояния топологии.
3. Алгоритм Форда-Фалкерсона (в контексте маршрутизации — Distance-Vector / Беллмана-Форда)
Строго говоря, Форд-Фалкерсон — это алгоритм поиска максимального потока. Однако в теории маршрутизации часто упоминают алгоритм Беллмана-Форда, который является итеративным методом распределенного расчета. Для целей данного ответа мы рассматриваем его как векторно-дистанционный (Distributed) алгоритм.
- Суть: Динамическое программирование. Уравнение Беллмана: d(u, v) = min( c(u, n) + d(n, v) ), где n — сосед.
- Механизм: Роутеры не знают топологии целиком. Они знают только расстояние (метрику) до сетей от своих соседей.
- Особенность: Алгоритм может работать с отрицательными весами (но в IP-сетях это не актуально) и гарантирует сходимость, если нет циклов с отрицательным весом.
Как строится маршрутная таблица?
Здесь процесс децентрализованный и итеративный.
- Каждый роутер создает вектор (список) расстояний до известных сетей.
- Отправляет этот вектор всем соседям.
- Получив векторы соседей, роутер прибавляет к ним стоимость своего линка до этого соседа.
- Если новая стоимость меньше существующей, таблица обновляется: меняется метка расстояния и меняется Exit Interface (выходной интерфейс) на того соседа, кто прислал это улучшение.
Итог таблицы: Таблица строится снизу-вверх (bottom-up). В отличие от Дейкстры, здесь маршрут до удаленной сети запоминается целиком через ближайшего соседа. Роутер не знает полного пути, он знает только “Идти к узлу X, а тот уже знает дальше”.
4. Ключевое различие в получении маршрутной таблицы
| Критерий | Алгоритм Дейкстры (OSPF/IS-IS) | Алгоритм Беллмана-Форда (RIP/EIGRP частично) |
|---|---|---|
| Знание сети | Глобальное (Link-State). Роутер знает всю карту. | Локальное (Distance-Vector). Роутер знает только “направление” и “дистанцию” до сетей. |
| Способ заполнения | Pull + Расчет: Запрашивает топологию, рисует граф и запускает алгоритм с корнем в себе. | Push + Итерация: Соседи сами присылают свои таблицы, текущий роутер просто выбирает лучший вариант из полученных. |
| Содержимое записи | Лучший путь до сети (Next-Hop), рассчитанный как сумма минимальных весов вдоль маршрута. | Лучший путь до сети (Next-Hop), определенный как минимум из сумм (расстояние соседа + стоимость линка до него). |
| Сложность памяти | Высокая (хранит базу данных всех LSA). | Низкая (хранит только таблицу маршрутов). |
| Скорость сходимости | Быстрая (мгновенный пересчет по топологии). | Медленная (счет до бесконечности, таймеры обновлений). |
5. Децентрализованный алгоритм маршрутизации: Обработка событий
Когда мы говорим о децентрализованном алгоритме, мы выходим за рамки простого математического расчета. В реальных сетях (особенно в SDN или динамических mesh-сетях) алгоритм работает как конечный автомат, управляемый событиями (Event-driven).
Децентрализованный алгоритм не имеет “главного” сервера. Каждый узел принимает решения самостоятельно на основе двух типов событий:
Типы событий:
- Топологические изменения (линк упал/поднялся).
- Обновление вектора расстояний от соседа (пришел новый Distance-Vector).
- Истечение таймера (периодическое обновление маршрутов).
Обработка событий (Цикл работы):
Сенсорный слой: Обнаружение изменения состояния линка (Link Down/Up) через механизмы Keepalive или BFD (Bidirectional Forwarding Detection).
Генерация события: При обнаружении изменения алгоритм не пересчитывает всё заново (в отличие от периодических протоколов), а инициирует локализованный пересчет.
- В децентрализованной модели (например, DSDV или AODV в мобильных сетях) обработка события выглядит так:
- Событие: Получен RREQ (запрос маршрута).
- Обработка: Узел проверяет, есть ли у него путь в таблице. Если есть — отправляет RREP (ответ). Если нет — ретранслирует запрос, увеличивая счетчик прыжков (метрику).
- Событие: Получен RREP (ответ).
- Обработка: Узел создает обратный маршрут к источнику данных, записывая в таблицу интерфейс, откуда пришел ответ.
Диффузионные вычисления (Diffusing Computations): В продвинутых децентрализованных алгоритмах (например, EIGRP) используется концепция Active/Passive states. При потере маршрута узел отправляет запросы соседям (Query) и ждет ответов (Reply), пока не найдет альтернативу. Если ответа нет — маршрут переводится в активное состояние, и алгоритм распространяет запрос глубже в сеть.
Влияние на таблицу маршрутизации:
При децентрализованной обработке маршрутная таблица не пересчитывается целиком (как у Дейкстры), а мутирует (обновляются только записи, затронутые событием):
- Если линк упал, удаляются все маршруты, использующие этот линк.
- Если пришел лучший вектор от соседа — запись перезаписывается.
- Если пришел худший вектор — он игнорируется (Split Horizon или Poison Reverse для предотвращения петель).
6. Итоговый вывод
- Алгоритм Дейкстры — это превентивный метод. Он строит таблицу по карте, гарантируя 100% оптимальность маршрута в момент расчета, но требует больших ресурсов CPU при каждом изменении топологии.
- Алгоритм Форда-Фалкерсона (Беллмана-Форда) — это реактивный (или итеративный) метод. Он строит таблицу по слухам (rumor-based). Это экономит память, но дает риск появления петель и медленной сходимости.
- Децентрализованная обработка событий — это поведенческая модель, которая комбинирует эти алгоритмы в условиях нестабильной сети. Она фокусируется не на “как найти путь с нуля”, а на “как скорректировать таблицу при сбое”, используя локальные запросы (Queries) и обновления (Updates), чтобы минимизировать время простоя (convergence time) без участия центрального координатора.