Бабич А.В. Оргранизация информационных сетей: Учебное пособие

Подождите немного. Документ загружается.

E=(3), (4), R=(1), (2), O=DB, C.

Результаты: ((4) : D)

Итерация 3

P=DB. Двигаясь по этому пути из (3), мы попадем в (1), то есть

V=(1). Так как V не находится в Е, то кратчайший путь (3) -> (1) есть

P. Добавляем этот факт в таблицу результатов, изымаем P из O,

переносим V из R в Е.

Строим новые пути: согласно базе данных из V=(1) существует

три односегментных пути: A, В и C. Добавив их к P=DB, получим

пути DBA, DBB и DBC с метриками 4, 3 и 5 соответственно. Эти

пути добавляются в упорядоченный список О.

E=(3), (4), (1), R=(2), O=C, DBB, DBA, DBC.

Результаты: ((4) : D; (1) : DB)

Итерация 4

P=С. V=(1). Так как V находится в Е, то исключаем P из О и

переходим к следующей итерации.

E=(3), (4), (1), R=(2), O=DBB, DBA, DBC.

Результаты: ((4) : D; (1) :DB)

Итерация 5

P=DBB. V=(4). Так как V находится в Е, то исключаем P из О и

переходим к следующей итерации.

E=(3), (4), (1) , R=(2), O=DBA, DBC.

Результаты: ((4) : D; (1) : DB)

Итерация 6

P=DBA, следовательно V=(2). Так как V не находится в Е, то

кратчайший путь (3) -> (2) есть P. Добавляем этот факт в таблицу

результатов, изымаем P из O, переносим V из R в Е.

Строим новые пути: согласно базе данных из V=(2) существует

один односегментный путь A. Добавив его к P=DBА, получим путь

DBAА с метрикой 6. Этот путь добавляется в упорядоченный спи-

сок О.

E=(3), (4), (1), (2), R=, O=DBC, DBAA.

Результаты: ((4) : D; (1) : DB, (2) : DBA)

Итерации 7 и 8

На этих итерациях из списка О будут удалены оставшиеся пути,

так как они ведут к вершинам, уже находящимся в множестве Е,

больше никаких изменений не произойдет.

Итерация 9

Так как список О пуст и множество R пусто, то кратчайшие пути

из S до всех вершин графа построены, недостижимых вершин нет.

Работа алгоритма закончена.

Результатом работы является таблица кратчайших путей от

маршрутизатора (3) до всех остальных маршрутизаторов:

(3) -> (1) : DB

(3) -> (2) : DBA

(3) -> (4) : D

На основе этой информации в узле (3) строится таблица марш-

рутов, ведущих ко всем узлам OSPF-системы. Для этого из выше-

приведенной таблицы нужно взять первую связь каждого пути.

Маршрутизатор, к которому ведет эта связь, будет являться следую-

щим маршрутизатором для данного маршрута. При этом алгоритм

SPF гарантирует, что и следующий маршрутизатор построил крат-

чайшие пути, соответствующие путям маршрутизатора (3): если

кратчайший путь из (3) в (2) (DBA) лежит через узел (4), в который

ведет связь D, то кратчайший путь из (4) в (2) будет ВА.

Таким образом, таблица маршрутов в узле (3) будет выглядеть

так:

(3) -> (1) : через (4), линия D

(3) -> (2) : через (4), линия D

(3) -> (4) : через линию D

§2. Разграничение хостов и маршрутизаторов

Выше мы разбирали систему сетей, состоящую только из марш-

рутизаторов, соединенных двухточечными линиями связи. В этой

системе отсутствовали хосты.

Предположим, что к маршрутизатору (4) подключена сеть N1

из некоторого количества хостов H

-H

. Следуя разобранной выше

модели, каждый хост должен быть также вершиной графа OSPF-

системы, хотя сам и не строит базу данных и не производит вы-

числения маршрутов. Тем не менее, информация о связях маршру-

тизатора (4) с каждым из хостов сети N1 и о метриках этих связей

должна быть внесена в базу данных, чтобы все остальные маршру-

тизаторы системы могли построить маршруты от себя до этих хо-

стов (рис. 9).

Рис. 9. OSPF-система с маршрутизаторами и хостами

Очевидно, что такая процедура неэффективна. Вместо информа-

ции о связях с каждым хостом в базу данных вносится информация

о связи с сетью, то есть сама IP-сеть становится вершиной графа

системы, соединенной с маршрутизатором (4) с помощью некоторой

связи P (рис. 10).

Рис. 10. OSPF-система с маршрутизаторами и тупиковой сетью

Подчеркнем, что в данном случае сеть, точнее ее адрес, исполь-

зуется как обобщающий идентификатор группы хостов, находя-

щихся в одной IP-сети, к которой маршрутизатор (4) непосредствен-

но подключен. Вершина N1 называется тупиковой сетью (stub

network); все узлы сети, обозначаемые этой вершиной, являются

хостами, у которых установлен маршрут по умолчанию, направлен-

ный на маршрутизатор (4).

Протокол OSPF производит разграничение хостов и маршрутиза-

торов. Если к IP-сети N1 подключен еще и один из интерфейсов

маршрутизатора (2), то связь между (2) и (4) будет установлена

отдельно, как если бы они были соединены двухточечной линией

связи (при этом у маршрутизатора (2) также будет связь с тупиковой

сетью N1).

При подключении тупиковой сети N1 в базе данных состояния

связей появится запись:

От->до Связь Метрика

(4)->N1 P 1

Связей, направленных из вершины N1, в базе данных не будет,

потому что вершина N1 не является маршрутизатором. Построение

маршрутов до вершины N1 (фактически сразу до всех хоcтов сети

N1) будет произведено каждым маршрутизатором обычным спосо-

бом по алгоритму SPF.

§3. Поддержка множественных маршрутов

Если между двумя узлами сети существует несколько маршру-

тов с одинаковыми или близкими по значению метриками, протокол

OSPF позволяет направлять части трафика по этим маршрутам в

пропорции, соответствующей значениям метрик. Например, если су-

ществует два альтернативных маршрута с метриками 1 и 2, то две

трети трафика будет направлено по первому из них, а оставшаяся

треть — по второму.

Положительный эффект такого механизма заключается в умень-

шении средней задержки прохождения дейтаграмм между отправи-

телем и получателем, а также в уменьшении колебаний значения

средней задержки.

Менее очевидное преимущество поддержки множественных

маршрутов состоит в следующем. Если при использовании только

одного из возможных маршрутов этот маршрут внезапно выходит

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

нативный маршрут, при этом во время процесса массового пере-

ключения больших объемов трафика с одного маршрута на другой

весьма велика вероятность образования затора на новом маршруте.

Если же до аварии использовалось разделение трафика по несколь-

ким маршрутам, отказ одного из них вызовет перемаршрутизацию

лишь части трафика, что существенно сгладит нежелательные эф-

фекты.

Рассмотрим теперь следующий пример (рис. 11).

Рис. 11. Пример особой ситуации при поддержке

множественных маршрутов

Узел (1) отправляет данные в (3), используя поддержку множе-

ственных маршрутов, по маршрутам С (2/3 трафика) и АВ (1/3 тра-

фика). Однако узел (2) тоже поддерживает механизм множественных

путей, и когда к нему пребывают дейтаграммы, адресованные в (3)

(в том числе, и отправленные из (1)), он применяет к ним ту же ло-

гику, то есть 2/3 из них отправляются в (3) по маршруту В, а одна

треть — по маршруту АС. Следовательно, 1/9 дейтаграмм, отправ-

ленных узлом (1) в узел (3), возвращаются опять в узел (1), и тот 1/3

из них опять отправляет в (3) по маршруту С, а 2/3 — по маршруту

АВ через узел (2) и т. д. В итоге сформировался «частичный цикл»

при посылке дейтаграмм из (1) в (3), который, помимо частичного за-

цикливания дейтаграмм, ведет к быстрой перегрузке линии А.

Избежать этого явления позволяет следующее правило.

Если узел Х отправляет данные в узел Y, он может пересылать

их через узел Q только в том случае, если Q ближе к Y, чем Х.

В разобранном выше примере, следуя этому правилу, (1) не мо-

жет посылать данные в (3) через (2), поскольку (2) не ближе к (3),

чем (1). Однако такая посылка возможна, если связи между узлами

имеют метрики, например, как изображено на рисунке 12.

Рис. 12. Пример корректной ситуации при поддержке

множественных маршрутов

Для реализации построения дополнительных альтернативных

маршрутов с учетом вышеприведенного правила в алгоритме SPF

требуется внести изменения в шаг 3 и добавить шаг 3А. Ниже при-

водится новая версия алгоритма SPF, в которой изменение и допол-

нение показаны курсивом.

Алгоритм SPF с поддержкой множественных маршрутов

Инициализировать E=S, R=все вершины графа, кроме S. По-

местить в О все односегментные (длиной в одно ребро) пути, начи-

нающиеся из S, отсортировав их в порядке возрастания метрик.

Если О пуст или первый путь в О имеет бесконечную метрику,

то отметить все вершины в R как недостижимые и закончить работу

алгоритма.

Рассмотрим P — кратчайший путь в списке О. Удалить P из О.

Пусть V — последний узел в P. Если V принадлежит E, перейти на

шаг 3а, иначе P является кратчайшим путем из S в V; перенести V

из R в E. Перейти на шаг 4.

3а. Рассмотрим W, узел, предшествующий V в пути Р. Если

расстояние от S до W меньше расстояния от S до V, обозна-

чить Р как приемлемый альтернативный путь к V. В любом

случае перейти на шаг 2.

Построить набор новых путей, подлежащих рассмотрению, путем

добавления к пути P всех односегментных путей, начинающихся из

V. Метрика каждого нового пути равна сумме метрики P и метрики

соответствующего односегментного отрезка, начинающегося из V.

Добавить новые пути в упорядоченный список О, поместив их на

места в соответствии со значениями метрик. Перейти на шаг 2.

§4. Внешние маршруты

Для достижения сетей, не входящих в OSPF-систему (в автоном-

ную систему), используются пограничные маршрутизаторы ав-

тономной системы (autonomous system border router, ASBR), име-

ющие связи, уходящие за пределы системы.

ASBR вносят в базу данных состояния связей данные о сетях за

пределами системы, достижимых через тот или иной ASBR. Такие

сети, а также ведущие к ним маршруты называются внешними

(external).

В простейшем случае, если в системе имеется только один ASBR,

он объявляет через себя маршрут по умолчанию (default route) и все

дейтаграммы, адресованные в сети, не входящие в базу данных си-

стемы, отправляются через этот маршрутизатор.

Если в системе имеется несколько ASBR, то, возможно, внутрен-

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

именно пограничный маршрутизатор нужно отправлять дейтаграм-

мы в ту или иную внешнюю сеть. Это делается на основе специаль-

ных записей, вносимых ASBR в базу данных системы. Эти записи

содержат адрес и маску внешней сети и метрику расстояния до нее,

которая может быть, а может и не быть сравнимой с метриками, ис-

пользуемыми в OSPF-системе. Если возможно, адреса нескольких

внешних сетей агрегируются в общий адрес с более короткой ма-

ской.

ASBR может получать информацию о внешних маршрутах от

протоколов внешней маршрутизации, а также все или некоторые

внешние маршруты могут быть сконфигурированы администратором

(в том числе единственный маршрут по умолчанию).

§5. Протокол Hello

После инициализации модуля OSPF (например, после загрузки

маршрутизатора) через все интерфейсы, включенные в OSPF-

систему, начинают рассылаться Hello-сообщения. Задача Hello-

протокола — обнаружение соседей и установление с ними отноше-

ний смежности.

Соседями называются OSPF-маршрутизаторы, подключенные к

одной сети (к одной линии связи) и обменивающиеся Hello-

сообщениями.

Смежными называются соседние OSPF-маршрутизаторы, кото-

рые приняли решение обмениваться друг с другом информацией,

необходимой для синхронизации базы данных состояния связей и

построения маршрутов. Не все соседи становятся смежными.

Другая задача протокола Hello — выбор выделенного маршрути-

затора в сети с множественным доступом, к которой подключено

несколько.

Hello-пакеты продолжают периодически рассылаться и после

того, как соседи были обнаружены. Таким образом маршрутизатор

контролирует состояние своих связей с соседями и может своевре-

менно обнаружить изменение этого состояние (например, обрыв свя-

зи или отключение одного из соседей). Обрыв связи может быть

также обнаружен и с помощью протокола канального уровня, кото-

рый просигнализирует о недоступности канала.

В сетях с возможностью широковещательной рассылки (broadcast

networks) Hello-пакеты рассылаются по мультикастинговому адресу

224.0.0.5 («Всем ОSPF-маршрутизаторам»). В других сетях все воз-

можные адреса соседей должны быть введены администратором.

Заголовок сообщения Hello представлен на рисунке 13.

Рис. 13. Заголовок сообщения Hello

Значения полей:

Network Mask (4 октета) — маска IP-сети, в которой находится

интерфейс маршрутизатора, отправившего сообщение.

Hello Interval (2 октета) — период посылки Hello-сообщений, в

секундах.

Options (1 октет) — используется для согласования возможно-

стей маршрутизаторов-соседей (маршрутизатор может прервать со-

седские отношения, если какие-то опции соседа его не устраивают)

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

нужно посылать маршрутизатору-соседу, потому что он все равно не

сможет ее обработать.

Priority (1 октет) — приоритет маршрутизатора; устанавливает-

ся администратором, используется при выборах выделенного марш-

рутизатора; маршрутизатор с нулевым приоритетом никогда не бу-

дет избран.

Dead Interval (4 октета) — время в секундах, по истечении

которого маршрутизатор-сосед, не посылающий сообщения Hello,

считается отключенным.

Designated Router (DR) (4 октета) — идентификатор выделен-

ного маршрутизатора с точки зрения маршрутизатора, посылающего

сообщение (0, если выделенный маршрутизатор еще не выбран).

Backup Designated Router (BDR) (4 октета) — идентификтор

запасного выделенного маршрутизатора с точки зрения маршрутиза-

тора, посылающего сообщение (0, если запасной выделенный марш-

рутизатор еще не выбран).

Neighbor, ..., Neighbor — список идентификаторов соседей, от

которых получены Hello-сообщения за последние Dead Interval се-

кунд; число полей «Neighbor» определяется из общей длины сообще-

ния, указанной в OSPF-заголовке. Длина одного поля — 4 октета.

После того, как пара маршрутизаторов начинает обмениваться

Hello-сообщениями с каким-то соседом, этот процесс проходит через

несколько стадий:

DOWN — сосед не обнаружен или отключился; x

INIT — послано Hello-сообщение или получено от маршрутиза- x

тора, еще не зачисленного в список соседей;

2-WAY (двусторонняя связь) — получено Hello-сообщение, в ко- x

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

соседей, а отправитель этого сообщения также зачислен в список

соседей данного маршрутизатора;

WAIT — ожидание в течение Dead Interval секунд для обнару- x

жения всех соседей; в это время маршрутизатор передает Hello-

сообщения, но не участвует в выборах выделенного маршрутиза-

тора и в синхронизировании баз данных;

EXSTART — установление ролей главный-подчиненный и ини- x

циализация структур данных для обмена описаниями баз дан-

ных (протокол обмена);

EXCHANGE — обмен описаниями баз данных (протокол обмена); x

LOADING — синхронизация баз данных, пересылка сообщений- x

запросов о состояниях связей и ответов на них (протокол обмена);

FULL — базы данных синхронизированы. x

Каждый маршрутизатор самостоятельно производит выборы

выделенного и запасного выделенного маршрутизаторов на основа-

нии имеющихся у него данных о соседях и о том, кого каждый из

соседей назначил на эту роль. Фактически процесс выборов проис-

ходит постоянно, после получения каждого Hello-сообщения, но ал-

горитм гарантирует, что при стабильном состоянии сети всеми марш-

рутизаторами будут выбираться одни и те же DR и BDR.

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

либо запасным, поместив свой идентификатор в соответствующее

поле своих Hello-сообщений. Иначе он может поместить туда адреса

других маршрутизаторов, если он считает их занимающими соответ-

ствующие роли. Если маршрутизатор не определился с выбором DR

и (или) BDR (например, после включения), он заполняет соответ-

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

тор в качестве собственного идентификатора использует наибольший

IP-адрес из всех IP-адресов на активных интерфейсах. Например,

если интерфейс FastEthernet 0/0 имеет IP-адрес 10.0.0.1, а интер-

фейс FastEthernet 0/1 имеет IP-адрес 192.168.0.1, то идентификатор

маршрутизатора будет равен 192.168.0.1. Из этого правила есть два

исключения. Если на маршрутизаторе имеются loopback интерфейсы,

то наибольший IP-адрес выбирается только из множества IP-адресов,

принадлежащих loopback интерфейсам. И второе исключение: иден-

тификатор маршрутизатора может быть явно задан с помощью ко-

манды (config-router)router-id ip_адрес.

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

двусторонняя связь и приоритет которых не равен нулю; в этот список

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

Итак, после получения очередного Hello-сообщения маршрутиза-

тор приступает к выбору DR и BDR. Он помнит мнения своих сосе-

дей по поводу того, кто является DR и BDR, которые он узнал из

получаемых Hello-сообщений, а также свой собственный предыду-

щий выбор.

Сначала выбирается BDR, на эту должность назначается маршру-1.

тизатор с наивысшим приоритетом из всех, объявивших себя в ка-

честве BDR, при этом маршрутизаторы, объявившие себя в качестве

DR, не рассматриваются. Если никто не объявил себя в качестве

BDR, выбирается маршрутизатор с высшим приоритетом из тех, кто

не объявил себя в качестве DR. В случае равных приоритетов вы-

бирается маршрутизатор с большим идентификатором.

На должность DR выбирается маршрутизатор с наивысшим при-2.

оритетом из всех, объявивших себя в качестве DR. В случае рав-