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

Метод дистанционно-векторной маршрутизации иногда называют также методом Беллмана или методом Форда-Фалкерсона по имени исследователей, которые первыми опубликовали идею алгоритма. Сама эта идея довольно проста. Маршрутизатор хранит в таблице список всех известных маршрутов с указанием в каждом элементе таблицы сети получателя и целого числа – количества пересылок до этой сети. Время от времени каждый маршрутизатор отсылает копию своей таблицы другим маршрутизаторам, к которым он имеет прямой доступ. Получив такую копию от 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);

· тупиковые, имеющие только один выход в Интернет (single-homed);

· многоканальные транзитные сети (multihomed transit).

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

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

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

Маршрутизаторы BGP

Имеется три типа маршрутизаторов BGP: спикеры, пограничные шлюзы и равноправные маршрутизаторы BGP.

Спикерами BGP (BGP speakers) являются все маршрутизаторы автономной системы BGP.

Спикеры BGP, соединяющие две или несколько автономных систем, называются пограничными шлюзами (Border Gateways). Они нужны автономным системам только в том случае, если AS использует для связи с другими автономными системами MPLS /IP-сети протокол EBGR. Задача пограничного шлюза – извещать о внутренних маршрутах автономной системы (и о других известных ему маршрутах) любой внешний спикер BGP, с которым этот шлюз связан.

Согласно принципам сетевой маршрутизации, во время сеансов связи спикеры BGP обмениваются маршрутной информацией о топологии и метрических характеристиках соответствующих участков сети. Такой обмен происходит между равноправными маршрутизаторами ( BGP peer) автономной системы.

Равноправные маршрутизаторы BGP не обязательно должны иметь прямые связи друг с другом; однако между двумя спикерами BGP всегда должен существовать стандартный способ коммуникации для того, чтобы они могли инициировать сеанс связи.

Когда BGP устанавливает сеанс связи двух равноправных маршрутизаторов, между которыми нет прямого соединения, такая связь называется одноранговой связью с пересылкой по протоколу EBGP (EBGP multihop peering). Используя внешние соединения по протоколу EBGP, спикер BGP может инициировать сеанс связи с другими спикерами, находящимися на расстоянии нескольких пересылок. Во всех таких случаях для организации сеансов BGP использует протокол TCP.

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

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

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

Протокол EBGP

Протокол EBGP (Exterior Border Gateway Protocol) используется для установления соединения между спикерами BGP разных автономных систем, включая коммуникации между Интернет-провайдерами и точками доступа РоР, а также между большими корпоративными сетями и провайдерами услуг.

Протокол IBGP

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

Отличие IBGP от EBGP состоит в том, что при извещении о маршруте соседнего маршрутизатора, находящегося в той же AS, в список номеров автономных систем AS_Path не вводится номер собственной автономной системы (AS_Path — список номеров автономных систем, через которые должна пройти дейтаграмма по пути в указанную сеть).