Протоколы маршрутизации
Метод дистанционно-векторной маршрутизации иногда называют также методом Беллмана или методом Форда-Фалкерсона по имени исследователей, которые первыми опубликовали идею алгоритма. Сама эта идея довольно проста. Маршрутизатор хранит в таблице список всех известных маршрутов с указанием в каждом элементе таблицы сети получателя и целого числа – количества пересылок до этой сети. Время от времени каждый маршрутизатор отсылает копию своей таблицы другим маршрутизаторам, к которым он имеет прямой доступ. Получив такую копию от LSR -B, маршрутизатор LSR -A анализирует полученный набор адресатов и расстояний до них. Маршрутизатор LSR -A заменяет данные в своей таблице, если маршрутизатору LSR -B известен более короткий, чем имеющийся в ней, маршрут к получателю, или если в его списке есть неизвестный ему до сих пор получатель, а также если LSR -A выполняет маршрутизацию через LSR -B, но расстояние от LSR -B до получателя изменилось.
На основе этой таблицы, согласно алгоритму Беллмана-Форда, и рассчитывается значение метрики (например стоимости маршрута, задержки и т.п.) для каждой пересылки в сети и поиск минимального суммарного числа пересылок. Обратим внимание на то, что понятие «дистанционный вектор» связано с характером периодически передаваемой протоколом информации. В сообщениях содержится пара чисел , где 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 — список номеров автономных систем, через которые должна пройти дейтаграмма по пути в указанную сеть).
Доставка пакетов. Маршрутизация. Rip, ospf.
Исходной точкой при анализе протоколов маршрутизации является принцип оптимальности маршрута. Он состоит в том, что маршрутизатор B, находящийся на оптимальном маршруте между A и C, соединен с ними оптимальными маршрутами. Поэтому множество оптимальных маршрутов от всех источников к приемнику является деревом и называется входным деревом узла. Критерием оптимальности являются расстояния между узлами на маршруте, измеренные в каких-либо единицах критерия оценки расстояния (метрики): длины, загруженности, пропускной способности, времени задержки, стоимости, веса маршрута.
Определение маршрута может базироваться на отдельных показателях (метриках) или комбинационных показателях. Программные реализации алгоритмов маршрутизации высчитывают метрику маршрута и используют ее в качестве критерия для определения оптимальных маршрутов к пункту назначения.
Главным параметром при маршрутизации пакета в Интернет является ip-адрес его места назначения. Проблема оптимальной маршрутизации в современном Интернет, насчитывающем десятки миллионов узлов, весьма сложна. Использование иерархической структуры сетевых адресов позволяет укрупнять (агрегировать) блоки маршрутной информации.
Типы алгоритмов маршрутизации.
Алгоритмы маршрутизации могут быть адаптивные (динамические) и неадаптивные (статические). Адаптивный алгоритм учитывает изменение топологии и загруженности соединительных каналов. Динамические алгоритмы маршрутизации подстраиваются к изменяющимся связям между узлами сети в масштабе реального времени. Они выполняют это путем анализа поступающих сообщений об обновлении маршрутизации. Если в сообщении указывается, что имело место изменение связей в сети, программы маршрутизации пересчитывают маршруты и рассылают сообщения о корректировке маршрутизации. Динамические алгоритмы маршрутизации могут дополнять статические маршруты там, где это уместно. Например, можно ввести в сеть статический маршрут на «маршрутизатор последнего обращения» (т.е. маршрутизатор, в который отсылаются все неотправленные по определенному маршруту пакеты). Такой маршрутизатор выполняет роль хранилища неотправленных пакетов, гарантируя, что все сообщения будут хотя бы определенным образом обработаны.
Неадаптивный алгоритм определяет процесс статической маршрутизации.
Одномаршрутные или многомаршрутные алгоритмы
Некоторые сложные протоколы маршрутизации обеспечивают множество маршрутов к одному и тому же пункту назначения. Такие многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям и балансировку загрузки каналов передачи данных. Преимущества многомаршрутных алгоритмов очевидны — они могут обеспечить заначительно большую пропускную способность и надежность. Одномаршрутные алгоритмы не могут делать этого.
Одноуровневые или иерархические алгоритмы
В одноуровневой системе маршрутизации все маршрутизаторы равноправны и содержат однородную информацию о структуре сети. В иерархической системе маршрутизации некоторые маршрутизаторы формируют то, что составляет основу (backbone — базу) маршрутизации. Эти маршрутизаторы выполняют функцию агрегирования маршрутной информации. Пакеты из небазовых маршрутизаторов перемещаются к базовыи маршрутизаторам и пропускаются через них до тех пор, пока не достигнут общей области пункта назначения. Начиная с этого момента, они перемещаются от последнего базового маршрутизатора через один или несколько небазовых маршрутизаторов до конечного пункта назначения.
Иерархические системы маршрутизации определяют логические группы узлов, называемые доменами маршрутизации, автономными системами (AS), или областями маршрутизации. В иерархических системах отдельные граничные маршрутизаторы какого-либо домена могут обмениваться агрегированной маршрутной информацией с граничными маршрутизаторами других доменов. Остальные маршрутизаторы доменов обмениваются данными о маршрутах только в пределах своего домена.
Основным преимуществом иерархической маршрутизации является то, что она позволяет агрегировать данные о структуре сети и снизить объем информации, передаваемой по протоколам маршрутизации между узлами сети. Внутридоменным маршрутизаторам необходимо знать только о других маршрутизаторах в пределах своего домена, поэтому их алгоритмы маршрутизации могут быть упрощенными. Соответственно может быть уменьшен и трафик обновления маршрутизации, зависящий от используемого алгоритма маршрутизации
Иерархическая структура маршрутизации сети может соответствовать организационной структуре сети.
Внутридоменные или междоменные алгоритмы
Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие — как в пределах доменов, так и между ними. Оптимальный алгоритм внутридоменной маршрутизации не обязательно будет оптимальным алгоритмом междоменной маршрутизации.
Алгоритмы состояния канала (Link State Protocol) (известные также как алгоритмы «первоочередности наикратчайшего маршрута», Дикстры)) направляют потоки маршрутной информации во все узлы об’единенной сети. Каждый маршрутизатор посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов.
Алгоритмы вектора расстояния (Distance Vector Protocol) (известные также как алгоритмы Бэлмана-Форда) требуют от каждогo маршрутизатора посылки всей или части своей маршрутной таблицы, но только своим соседям.
Алгоритмы состояния каналов фактически направляют небольшие корректировки всем узлам сети, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в соседние маршрутизаторы.
Достоинства алгоритмов состояния каналов:
Устойчивость к образованию петель маршрутизации.
Повышенные требования к производительности процессора и объему памяти.