13.3 Построение таблицы маршрутизации протоколом OSPF
цию для построения таблицы маршрутизации, которая используется при передаче трафика сети получателю. Каждый маршрутизатор обладает отдельной базой данных состояния связей для каждой зоны, к которой он подключен. Когда содержимое базы данных изменяется, маршрутизатор запускает алгоритм SPF для повторного построения таблицы маршрутизации. Алгоритм SPF выполняется для той таблицы топологии, в которой произошли изменения. Процесс построения маршрутизатором таблицы маршрутизации состоит из следующих основных пунктов. 1. Маршрутизатор выполняет алгоритм SPF для сообщений LSA 1 и 2 типов. Маршрутизатор производит расчет внутризональных записей таблицы маршрутизации для всех сетей получателей, имеющихся в пределах зоны. Кроме того, он генерирует записи маршрутизаторов для всех пограничных маршрутизаторов ABR и ASBR находящихся внутри данной зоны. Эти записи таблицы маршрутизации не используются для пересылки трафика, они используются только протоколом OSPF при создании межзональных маршрутов, а также маршрутов к сетям получателям находящихся в других автономных системах. 2. Маршрутизатор рассчитывает межзональные маршруты, используя суммарные LSA 3 и 4 типов. При создании межзональных маршрутов маршрутизатор должен проверить, имеется ли запись в таблице маршрутизации, созданная на 1 шаге, для ABR маршрутизатора, идентификатор которого указан в качестве объявляющего маршрутизатора суммарного сообщения LSA. Если такой записи не существует, межзональный маршрут не создается. Для пограничных маршрутизаторов ASBR, маршрутизаторы создают таблицы маршрутизации, которые не используются для пересылки трафика, а используются протоколом OSPF при создании внешних маршрутов. 3. Маршрутизаторы рассчитывают маршруты к внешним сетям получателям, используя информацию сообщений LSA 5 или 7 типов. При создании внешних маршрутов маршрутизатор должен проверить, имеется ли записи в таблице маршрутизации для маршрутизаторов ASBR, через который доступны внешние получатели созданные на шаге 2 для маршрутизатора ASBR, идентификатор, которого указан в качестве объявляющего маршрутизатора суммарного сообщения LSA. Если такой записи не существует, внешний маршрут не создается. Полное описание процесса расчета таблицы маршрутизации с обработкой всех возможных вариантов и обработкой исключений приводится в RFC 2328.
13.3.1 Типы маршрутов протокола OSPF
В соответствии с процессом построения таблицы маршрутизации протокол OSPF разделяет маршруты на четыре типа. В таблице 13.4 приведено описание типов маршрутов протокола OSPF.
Протоколы маршрутизации (RIP, OSPF и BGP)
Для того чтобы вычислить таблицы маршрутизации, применяется алгоритм Дейкстры для баз данных состояния линии этого маршрутизатора ( рис. 8.12). Алгоритм Дейкстры вычисляет кратчайший путь между двумя точками в сети, используя граф по методу узлов и границ. Алгоритм разделяет узлы на два множества: пробные и постоянные. Он выбирает узлы, делает их пробными, анализирует их и, если они проходят по критериям, делает их постоянными. Мы можем информативно определить алгоритм, используя нижеследующие шаги.
Работа алгоритма поясняется на рис. 8.13 На рис. 8.13 а приведен пример сети. Эта же сеть представлена в виде графа. На этом графе нанесена назначенная стоимость прохождения по участкам. Далее на рис. 8.13 б. приводится вычисление накопленной стоимости при прохождении.
Сам алгоритм заключается в прохождении графа и вычислении накопленной стоимости. Алгоритм прохождения графа приведен во многих книгах. Ниже рассматривается порядок вычисления наикратчайшего пути. Номер следующего узла представляет накопленную стоимость от корневого узла. Заметим, что сеть достигает маршрутизатора E через два направления с накопленной стоимостью 14 и 10. При этом сохраняется направление с накопленной стоимостью 10, а второе удаляется.
Таблицы маршрутизации
Каждый маршрутизатор применяет метод наикратчайшего пути по дереву для построения своей таблицы маршрутизации. Таблица маршрутизации показывает стоимость достижения каждого узла в зоне, маршрутизатор использует извещения: суммарной линии сети, суммарной линии пограничного маршрутизатора и внешней линии. Табл. 8.2. показывает таблицу маршрутизации для маршрутизатора A согласно результатам вычислений по рис. 8.13 в.
| Сеть | Стоимость | Следующий маршрутизатор | Другая информация |
|---|---|---|---|
| N1 | 5 | ||
| N2 | 7 | C | |
| N3 | 10 | D | |
| N4 | 11 | B | |
| N5 | 15 | D |
Типы пакетов
OSPF использует пять различных типов пакетов: пакет «hello», пакет распределения базы данных , пакет состояния линии, пакет обновления состояния линии и пакет подтверждения состояния линии.
Формат пакета
Все OSPF-пакеты имеют один и тот же состав заголовка ( рис. 8.14). Перед изучением различных типов пакетов рассмотрим этот общий заголовок.
Версия. Это поле 6 бит, определяющее версию протокола OSPF. Текущая версия — 2.
Тип. Это поле 8 бит определяет тип пакета. Как уже сказано раньше, мы имеем пять типов пакетов, со значением от 1 до 5, определяющих типы.
Длина сообщения. Это поле 16 бит определяет длину всего сообщения, включая заголовок.
- IP-адрес маршрутизатора источника. Это поле 32 бита определяет IP-адрес маршрутизатора, посылающего пакет.
- Идентификация зоны. Это поле 32 бит определяет зону, в которой работает маршрутизатор.
- Контрольная сумма. Это поле 16 бит используется для обнаружения ошибок во входящем пакете, исключая поля «аутентификация типа» и » аутентификация данных «.
- Тип аутентификации. Поле 16 бит, определяющее метод опознавания, который используется в этой зоне. Иногда определяют два типа опознавания: 0 для отсутствия и 1 для пароля.
- Аутентификация данных. Это поле 64 бита для действующего значения данных. В будущем, когда определится больше типов опознавания, это поле будет содержать результат вычисления аутентификации. В настоящее время, если тип опознавания 0, это поле заполнено нулями. Если тип 1 — поле содержит пароль длиной восемь символов.
Сообщение «hello»
OSPF использует сообщение «hello» ( рис. 8.15) для создания отображения окружающей его сети и для проверки достижимости соседей. Это первый шаг в маршрутизации по состоянию линий. Прежде чем маршрутизатор может заполнить все другие маршрутизаторы своей информацией о соседях, он должен сначала стать доступным для обмена своим соседям. Он должен определить, работоспособны ли они. И он должен знать, доступны ли они.
Маска сети. Это поле 32 бита определяет маску сети , по которой посылается сообщение «hello».
Интервал «hello». Это поле 16 бит определяет число секунд между сообщениями «hello».
E-флаг. Это поле 1 бит – флаг. Когда он установлен, это означает, что зона является ответвлением.
T-флаг. Это поле 1 бит флага. Когда он установлен, это означает, что маршрутизатор поддерживает множество метрик.
Приоритет. Это поле определяет приоритет маршрутизатора. Приоритет используется для выбора назначенного маршрутизатора. После того как все соседи объявят свои приоритеты, маршрутизатор с наивысшим приоритетом выбирается как назначенный. Один из них, имеющий второй наивысший приоритет, выбирается как резервный назначенный маршрутизатор. Если значение этого поля 0, это значит, что маршрутизатор не может никогда быть назначенным резервным маршрутизатором.
Интервал неисправности. Это поле 32 бита определяет число секунд до момента, когда маршрутизатор предположит, что сосед неисправен.
IP-адрес назначенного маршрутизатора. Это поле 32 бита — IP-адрес назначенного маршрутизатора для сети, через которую послано сообщение.
IP-адрес резервного назначенного маршрутизатора. Это поле 32 бита — IP-адрес резервного назначенного маршрутизатора для сети, через которую послано сообщение.
IP-адрес соседа. Это поле повторяет 32 бита, определяющее маршрутизаторы, которые согласованы как соседи для посылающего маршрутизатора. Другими словами, это текущий список всех соседей посылающего маршрутизатора, получивших сообщение «hello».
Сообщение описания базы данных
Когда маршрутизатор подключен к системе первый раз или после повреждения, ему нужно немедленно заполнить базу данных состояния связи. Чтобы создать свою собственную базу данных и вычислить таблицу маршрутов, он не может ждать, пока все состояния связи будут обновлены в соответствии с информацией, которая поступит от каждого из маршрутизаторов. Поэтому, после того как маршрутизатор подключен к системе, он посылает пакеты «hello» для того, чтобы оповестить соседей. Если соседи первый раз узнают об этом маршрутизаторе, они посылают пакет обновления с описанием собственной базы данных. Пакет обновления с описанием собственной базы данных не содержит полного описания информации о базе данных, он дает только краткое содержание, название каждой линейки в базе данных. Заново подключенный маршрутизатор анализирует общее описание и узнает, какие линейки информации у него отсутствуют. После чего он посылает один или более пакетов запросов состояния связи, чтобы иметь полную информацию об этих конкретных линиях. Когда два маршрутизатора хотят обменяться пакетами описания базы данных, один из них играет роль ведущего, а другой роль ведомого. Поскольку сообщение может быть очень длинным, содержание базы данных может быть разделено на несколько сообщений. Формат пакетов описания базы данных показан на рис. 8.16
- E-флаг. Это поле 1 бит – флаг, устанавливаемый на 1, если извещающий маршрутизатор — пограничный маршрутизатор автономной системы (E означает внешний, external).
- B-флаг. Это поле 1 бит – флаг, устанавливаемый на 1, если извещающий маршрутизатор принадлежит автономной системе.
- I-флаг. Это поле 1 бит – инициализирующий флаг, устанавливаемый на 1, если сообщение есть первое сообщение.
- M-флаг. Это поле 1 бит – флаг «еще больше», устанавливаемый на 1, если это не последнее сообщение.
- M/S-флаг. Это поле 1 бит – ведомый/ведущий, указывает, что источник пакета — ведомый (M/S=1) или ведущий (M/S=0).
- Порядковый номер сообщения. Это поле 32 бита содержит порядковый номер сообщения. Этот номер используется для сравнения запроса с откликом.
- LSA-заголовок. Это 20-байтное поле, используемое при каждом сообщении о состоянии связи ( LSA ). Формат этого заголовка обсуждался в разделе «сообщение обновления состояния линии» Этот заголовок — краткое описание каждой линии, без деталей. Он повторяется для каждой линии в линейке состояний базы данных.