18c0693f

Алгоритм Беллмана-Форда


Метод дистанционно-векторной маршрутизации иногда называют также методом Беллмана или методом Форда-Фалкерсона по имени исследователей, которые первыми опубликовали идею алгоритма. Сама эта идея довольно проста. Маршрутизатор хранит в таблице список всех известных маршрутов с указанием в каждом элементе таблицы сети получателя и целого числа – количества пересылок до этой сети. Время от времени каждый маршрутизатор отсылает копию своей таблицы другим маршрутизаторам, к которым он имеет прямой доступ. Получив такую копию от LSR-B, маршрутизатор LSR-A анализирует полученный набор адресатов и расстояний до них. Маршрутизатор LSR-A заменяет данные в своей таблице, если маршрутизатору LSR-B известен более короткий, чем имеющийся в ней, маршрут к получателю, или если в его списке есть неизвестный ему до сих пор получатель, а также если LSR-A выполняет маршрутизацию через LSR-B, но расстояние от LSR-B до получателя изменилось.

На основе этой таблицы, согласно алгоритму Беллмана-Форда, и рассчитывается значение метрики (например стоимости маршрута, задержки и т.п.) для каждой пересылки в сети и поиск минимального суммарного числа пересылок. Обратим внимание на то, что понятие "дистанционный вектор" связано с характером периодически передаваемой протоколом информации. В сообщениях содержится пара чисел {R, D}, где R – вектор, определяющий получателя, a D – расстояние до этого получателя, т.е. один маршрутизатор сообщает другому о своей возможности достичь получателя R за D пересылок.

При маршрутизации по протоколу BGP пересылка возможна как между внутренними маршрутизаторами (расположенными внутри одной AS), которые работают под управлением протокола IBGR так и между внешними маршрутизаторами, соединяющими разные автономные системы AS, когда маршрутизация выполняется под управлением протокола EBGR.

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


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

Существует три класса автономных систем AS:



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

Многие автономные системы на самом деле являются тупиковыми (stub) или одноканальными (single-homed) и имеют лишь один выход во внешнюю сеть. Соответственно, они не требуют никаких дополнительных правил для управления ими и обслуживания большого списка BGP-маршрутов в шлюзе, у которого имеется только один выход в Интрасеть.

Третий тип автономной системы – транзитная сеть. Транзитные AS – это системы с множественной адресацией, которые принимают информацию от внешних автономных систем и выполняют маршрутизацию этой информации к другим внешним AS.