Протоколы маршрутизации

Размещено на http://www.allbest.ru/

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

Этот протокол маршрутизации предназначен для сравнительно небольших и относительно однородных сетей. Маршрут характеризуется вектором расстояния до места назначения. Предполагается, что каждый маршрутизатор является отправной точкой нескольких маршрутов до сетей, с которыми он связан. Описания этих маршрутов хранится в специальной таблице, называемой маршрутной. Таблица маршрутизации RIP содержит по записи на каждую обслуживаемую машину (на каждый маршрут). Запись должна включать в себя:

IP-адрес места назначения.

Метрика маршрута (от 1 до 15; число шагов до места назначения).

IP-адрес ближайшего маршрутизатора по пути к месту назначения.

Таймеры маршрута.

Периодически (раз в 30 сек) каждый маршрутизатор посылает широковещательно копию своей маршрутной таблицы всем соседям-маршрутизаторам, с которыми связан непосредственно. Маршрутизатор-получатель просматривает таблицу. Если в таблице присутствует новый путь или сообщение о более коротком маршруте, или произошли изменения длин пути, эти изменения фиксируются получателем в своей маршрутной таблице. Протокол RIP должен быть способен обрабатывать три типа ошибок:

Циклические маршруты.

Для подавления нестабильностей RIP должен использовать малое значение максимально возможного числа шагов (не более 16).

Медленное распространение маршрутной информации по сети создает проблемы при динамичном изменении маршрутной ситуации (система не поспевает за изменениями). Малое предельное значение метрики улучшает сходимость, но не устраняет проблему.

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

Недостатки RIP

RIP не работает с адресами субсетей. Если нормальный 16-бит идентификатор ЭВМ класса B не равен 0, RIP не может определить является ли не нулевая часть cубсетевым ID, или полным IP-адресом.

RIP требует много времени для восстановления связи после сбоя в маршрутизаторе (минуты). В процессе установления режима возможны циклы.

Число шагов важный, но не единственный параметр маршрута, да и 15 шагов не предел для современных сетей.

OSPF (Open Shortest Path First) -- протокол динамической маршрутизации, основанный на технологии отслеживания состояния канала (link-state technology) и использующий для нахождения кратчайшего пути Алгоритм Дейкстры (Dijkstra's algorithm).

OSPF имеет следующие преимущества:

Высокая скорость сходимости по сравнению с дистанционно-векторными протоколами маршрутизации;

Поддержка сетевых масок переменной длины (VLSM);

Оптимальное использование пропускной способности (т. к. строится минимальный остовный граф по алгоритму Дейкстры);

Описание работы протокола

Маршрутизаторы обмениваются hello-пакетами через все интерфейсы, на которых активирован OSPF. Маршрутизаторы, разделяющие общий канал передачи данных, становятся соседями, когда они приходят к договоренности об определённых параметрах, указанных в их hello-пакетах.

На следующем этапе работы протокола маршрутизаторы будут пытаться перейти в состояние смежности со своими соседями. Переход в состояние смежности определяется типом маршрутизаторов, обменивающихся hello-пакетами, и типом сети, по которой передаются hello-пакеты. OSPF определяет несколько типов сетей и несколько типов маршрутизаторов. Пара маршрутизаторов, находящихся в состоянии смежности, синхронизирует между собой базу данных состояния каналов.

Каждый маршрутизатор посылает объявления о состоянии канала маршрутизаторам, с которыми он находится в состоянии смежности.

Каждый маршрутизатор, получивший объявление от смежного маршрутизатора, записывает передаваемую в нём информацию в базу данных состояния каналов маршрутизатора и рассылает копию объявления всем другим смежным с ним маршрутизаторам.

Рассылая объявления внутри одной OSPF-зоны, все маршрутизаторы строят идентичную базу данных состояния каналов маршрутизатора.

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

Каждый маршрутизатор строит таблицу маршрутизации из своего дерева кратчайших путей. протокол маршрутизация динамический канал

Протоколы внешней маршрутизации BGP

BGP (Border Gateway Protocol) это протокол внешних маршрутизаторов, предназначенный для связи между маршрутизаторами в различных автономных системах. BGP заменяет собой старый EGP.

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

IP датаграмма в АС может принадлежать как к локальному траффику, так и к транзитному траффику. Локальный - это траффик у которого источник и пункт назначения находятся в одной AS. При этом IP адреса источника и назначения указывает на хосты, принадлежащие одной автономной системе. Весь остальной траффик называется транзитным. Основное преимущество использования BGP в Internet заключается в уменьшении транзитного траффика.

Автономная система может принадлежать к следующим категориям:

Ограниченная (stub) AS автономная система имеет единственное подключение к одной внешней автономной системе. В такой автономной системе присутствует только локальный траффик.

Многоинтерфейсная (multihomed) AS имеет подсоединение к нескольким удаленным автономным системам, однако по ней запрещено прохождение транзитного траффика.

Транзитная (transit) AS имеет подключение к нескольким автономным системам и в соответствии с ограничениями может пропускать через себя как локальный, так и транзитный траффик.

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

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

BGP отличается от RIP или OSPF тем, что BGP использует TCP в качестве транспортного протокола. Две системы, использующие BGP, устанавливают TCP соединения между собой и затем обмениваются полными таблицами маршрутизации BGP. Обновления представляются в виде изменений таблицы маршрутизации (таблица не передается целиком).

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

BGP определяет выход из строя канала или хоста на другом конце TCP соединения путем регулярной отправки сообщения "оставайся в живых" (keepalive) своим соседям. Рекомендуемое время между этими сообщениями составляет 30 секунд. Сообщение "оставайся в живых", которое используется на уровне приложений, независимо от TCP опций "оставайся в живых"

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

Этот граф мы можем представить в виде матрицы С:

Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5.

Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.

Присвоим 1-й вершине метку равную 0, потому как эта вершина -- источник. Остальным вершинам присвоим метки равные бесконечности.

Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. Каждой из рассмотренных вершин назначим метку равную сумме метки W и длинны пути из W в рассматриваемую вершину, но только в том случае, если полученная сумма будет меньше предыдущего значения метки. Если же сумма не будет меньше, то оставляем предыдущую метку без изменений.

После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.

Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины.

Выполнив все действия получим такой результат:

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1}). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р -- Р[3]=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W -- P[4]=5. В результате получим вектор Р = {1, 1, 5, 5, 1}.

Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.

Размещено на Allbest.ru