Лекция: Пример маршрутизации по алгоритму OSPF

Представим себе один день из жизни транзитной локальной сети. Пусть у нас имеется сеть Ethernet, в которой есть три маршрутизатора — Джон, Фред и Роб (имена членов рабочей группы Internet, разработавшей протокол OSPF). Эти маршрутизаторы связаны с сетями в других городах с помощью выделенных линий.

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

Гипотетическая сеть с OSPF маршрутизаторами

На протяжении интервала отказа маршрутизаторы продолжают посылать сообщения HELLO. Когда какой-либо маршрутизатор посылает такое сообщение, другие его получают и отмечают, что в локальной сети есть другой маршрутизатор. Когда они посылают следующее HELLO, они перечисляют там и своего нового соседа.

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

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

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

Посмотрим теперь, как Робин вычисляет маршрут через сеть. Две из связей, присоединенных к его портам, представляют линии T-1, а одна — линию 56 Кб/c. Робин сначала обнаруживает двух соседей — Роба с метрикой 65 и Мило с метрикой 1785. Из объявления о связях Роба Робин обнаружил наилучший путь к Мило со стоимостью 130, поэтому он отверг непосредственный путь к Мило, поскольку он связан с большей задержкой, так как проходит через линии с меньшей пропускной способностью. Робин также обнаруживает транзитную локальную сеть с выделенным маршрутизатором Джоном. Из объявлений о связях Джона Робин узнает о пути к Фреду и, наконец, узнает о пути к маршрутизаторам Келли и Джеффу и к их тупиковым сетям.

После того, как маршрутизаторы полностью входят в рабочий режим, интенсивность обмена сообщениями резко падает. Обычно они посылают сообщение HELLO по своим подсетям каждые 10 секунд и делают объявления о состоянии связей каждые 30 минут (если обнаруживаются изменения в состоянии связей, то объявление передается, естественно, немедленно). Обновленные объявления о связях служат гарантией того, что маршрутизатор работает в сети. Старые объявления удаляются из базы через определенное время.

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

Алгоритм Дейкстры для поиска кратчайшего пути в графе (используется в ospf)

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых uявляется предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

15)Алгоритм работы протокола EIGRP. Метрики маршрута в EIGRP

EIGRP — усовершенствованный дистанционно-векторный протокол динамической маршрутизации разработанный компанией Cisco.

Основными преимуществами EIGRP являются:

низкое потребление сетевых ресурсов в режиме нормальной эксплуатации (в условиях стабильной сети передаются только

пакеты «hello»)

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

целиком; это позволяет уменьшить нагрузку на сеть, создаваемую протоколом маршрутизации

малое время конвергенции в случае изменения в топологии сети (в отдельных случаях сходимость обеспечивается почти

мгновенно)

Основные принципы(здесь же говорится что будет если одна из связей отвалится)

Вместо того, чтобы рассчитывать на полные регулярные обновления для выполнения повторной сходимости, EIGRP (вместо

отбрасывания данных) строит таблицу топологии используя для этого все объявления своих соседей и выполняет сходимость либо

посредством поиска подходящего беспетлевого маршрута в таблице топологии, либо (если о таком маршруте ничего не известно)

посредством опроса своих соседей. Второй маршрутизатор сохраняет информацию, полученную от первого и третьего

маршрутизаторов. Он выбирает путь через маршрутизатор 1 как лучший путь («преемник»), а путь через маршрутизатор 3 – как путь

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

Обновления eigrp в отличие от RIP, отсылаются не периодически, а только при изменениях или по запросу:
Частичные (parted) — отсылается не вся таблица маршрутизации, а только изменившиеся маршруты.
Ограниченные (bounded) — обновления отсылаются только тем соседям на которых они влияют.

Помимо таймера hello, у eigrp есть таймер hold time. Он используется для определения работает ли сосед или же отключился. По умолчанию равен трем интервалам hello.

Для расчёта наилучшего, без петлевого маршрута в eigrp используется cобственный алгоритм DUAL. Некоторые определения используемые в eigrp.

Роутер с наилучшей метрикой до сети называется successor. Именно он фигурирует в таблице маршрутизации как next-hop. Метрика до сети через него называется feasible distance. Именно она указывается в таблице маршрутизации после административной дистанции. Reported distance это метрика до сети которую нам сообщает next-hop. Для ускорения сходимости сети, а так же чтобы лишний раз не пересчитывать маршруты eigrp хранит резервные маршруты в таблице топологии. Исходя из условия feasible condition =feasible successor это next-hop в туже сеть что и successor, но с reported distance меньше чем feasible distance. Резервный next-hop всегда выбирается исходя из данного условия. Если next-hop не соответствует условию, то он не станет feasible successor.

Одно из важных отличий EIGRP в том, что он может балансировать нагрузку как на маршрутах с одинаковой метрикой, так и на маршрутах с неодинаковой метрикой.

Для конфигурации eirgp используется команда router eigrp AS. AS в данном случае не настоящий номер автономной системы, а номер процесса eigrp запущенного на роутере. Главное условие, AS номера должны совпадать на всех маршрутизаторах. Иначе не будет соседства.

Для распространения маршрутной информации по сети в EIGRP используется непериодическое инкрементное обновление маршрутов.

Это означает, что EIGRP пересылает обновления только для изменяющихся маршрутов и только в тот момент, когда такие маршруты

изменяются.

EIGRP работает согласно алгоитму DUAL

Согласно алгоритму DUAL протокол EIGRP не проводит периодический обмен объемными обновлениями (update) маршрутной информации, а использует небольшие пакеты Hello для контроля связи с соседними маршрутизаторами. Обмен маршрутной информацией производится только при возникновении изменений в сети (появление новых связей, недоступных узлов и сетей, изменение метрики). Причем производится обмен неполной (partial) маршрутной информацией, касающейся только изменений в сети, и с ограниченным (bounded) числом тех маршрутизаторов, которые затрагивают эти изменения. Кроме того, алгоритм DUAL не использует таймеры удержания информации holddown (см. раздел 9.3), как это делает алгоритм Беллмана-Форда протокола RIP. Поэтому сходимость (convergence) сетей EIGRP – более быстрая.

Время удержания – время, в течение которого маршрутизатор

будет считать соседнее устройство действующим, не получая при этом от него пакет «hello».

метрика = [K1 * пропускная способность + (K2 * пропускная способность) / (256 — нагрузка) + K3 * задержка] * [K5 / (надежность

+ K4)]

Обратный запрет – это еще один способ предотвратить появление петель. Правило обратного запрета выглядит следующим образом:

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

через тот же самый интерфейс.

Режим инициализации

Когда два маршрутизатора впервые становятся «соседями», они, находясь в режиме инициализации, обмениваются таблицами

топологии. Каждая запись в таблице, которую маршрутизатор принял в режиме инициализации, повторно объявляется (принимающим

маршрутизатором) новому соседу, при этом к этой записи применяется максимальная метрика (это так называемый «запрещенный

маршрут» – poison route, букв. отравленный маршрут).

Для того чтобы маршрутизаторы стали соседями должны выполняться такие условия:

§ маршрутизаторы должны пройти аутентификацию,

§ маршрутизаторы должны быть в одной AS,

§ отношения соседства должны устанавливаться на primary-адресах (когда приходит hello-пакет, маршрутизатор проверяет принадлежит ли адрес отправителя сети на primary-адресе интерфейса),

§ должны совпадать значения K-коэффициентов.

EIGRP использует 5 типов сообщений:

§ Hello — маршрутизаторы используют hello-пакеты для обнаружения соседей. Пакеты отправляются multicast и не требуют подтверждения о получении.

§ Update — содержится информация об изменении маршрутов. Они отправляются только маршрутизаторам, которых касается обновление. Эти пакеты могут быть отправлены конкретному маршрутизатору (unicast) или группе маршрутизаторов (multicast). Получение update-пакета подтверждается отправкой ACK.

§ Query — когда маршрутизатор выполняет подсчет маршрута и у него нет feasible successor, он отправляет query-пакет своим соседям для того чтобы определить нет ли feasible successor для этого destination у них. Обычно query-пакеты отправляются multicast, но могут быть и unicast. Получение query-пакета подтверждается отправкой ACK получателем пакета.

§ Reply — маршрутизатор отправляет reply-пакет в ответ на query-пакет. Reply-пакеты отправляются unicast тому, кто отправил query-пакет. Получение reply-пакета подтверждается отправкой ACK.

§ ACK — пакет, который подтверждает получение пакетов update, query, reply. ACK-пакеты отправляются unicast и содержат в себе acknowledgment number. Фактически это hello-пакеты, которые не передают данных. Используется негарантированная доставка.

Процесс обмена обновлениями:

§ изначально отправляются полные обновления, в которые включены все маршруты, за исключением тех, которые попадают под правило split horizon;

§ после того как обмен маршрутами завершился, обновления не отправляются;

§ в дальнейшем обновления отправляются, если изменился один или более маршрутов;

§ если отношения соседства разрываются, а затем восстанавливаются, то отправляются полные обновления.

Обновления EIGRP:

§ Непериодические (Nonperiodic) — обновления отправляются не через регулярные интервалы времени, а при изменении топологии или метрики;

§ Частичные (Partial) — в обновлениях передается не вся информация из таблицы маршрутизации, а только изменения;

§ Ограниченные (Bounded) — обновления отправляются только задействованным маршрутизаторам.