9 Протоколы маршрутизации по состоянию канала

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

Чтобы лучше понять различие между дистанционно-векторными алгоритмами Беллмана-Форда, алгоритмом DUAL, и алгоритмами маршрутизации по состоянию канала, взглянем на рисунки 9.1 – 9.3.

		22	25
		СП2	СП3	СП7
СП6	СП5	10	18
			R1
		14	10
		22	СП1

СП4

Рисунок 9.1 – Представление топологии сети алгоритмом Беллмана-Форда

На рисунке. 9.1 изображено представление топологии сети передачи данных маршрутизатором R1, который использует один из вариантов дистан- ционно-векторного алгоритма Беллмана-Форда. Маршрутизатор имеет информацию только о сетях получателях, показанных в виде сегментов Ethernet, о том, как далеко и в каком направлении они находятся.

На рисунке. 9.2 изображено представление той же сети передачи данных маршрутизатором R1, но на этот раз маршрутизатор использует протокол маршрутизации на основе алгоритма DUAL. Маршрутизатор знает о своих непосредственных соседях, о том, насколько далеко и в каком направлении они расположены, а также дистанции от соседей до всех известных сетей получателей.

160

			СП2
	12
СП6	СП5		10
	4	R4	R1
		16
			12
			R2
			СП4

СП3	СП7
18	7
	R6

10

СП1

Рисунок 9.2 – Представление топологии сети алгоритмом DUAL алгоритмом маршрутизации по состоянию канала связи

Как видно, кроме кратчайшего пути к сети получателю СП4, лежащего через маршрутизатор R2, маршрутизатор R1 смог также обнаружить альтернативный маршрут, лежащий через маршрутизатор R4. Метрика кратчайшего маршрута равна 22 (10 + 12), тогда как метрика альтернативного – 26 (10 + 16). Несмотря на более высокую метрику, маршрутизатор R1 все же рассматривает маршрут через маршрутизатор R4 как альтернативу, поскольку метрика собственного маршрута маршрутизатора R4 к СП4 равна всего 16, т.е. меньшему значению, чем метрика кратчайшего маршрута маршрутизатора R1. Следовательно, маршрутизатор R4 находится ближе к сети получателю, чем маршрутизатор R1, а значит, маршрутизатор R1 может мгновенно переключиться на маршрут через R4, если характеристики маршрута через R2 ухудшатся или он станет недоступен.

СП2

СП3

СП7

СП6

8

СП5	10	18	7
	R4	R1	R6
4		10
R5
	12	СП1
	R3	R2

СП4

Рисунок 9.3 – Представление топологии сети алгоритмом маршрутизации по состоянию канала связи

161

На рисунке 9.3 показано представление топологии сети передачи данных маршрутизатором R1 с использованием протокола маршрутизации по состоянию канала. Здесь маршрутизатор R1 знает полную топологию сети передачи данных. Следовательно, он знает не только об альтернативном маршруте к сети получателю СП4 через маршрутизатор R4, но также и об альтернативных маршрутах к СП6 и СП5 через маршрутизатор R2.

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

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

Однако превосходство протоколов маршрутизации по состоянию канала имеет свою цену. Такие протоколы обычно значительно сложнее реализовать, чем дистанционно-векторные протоколы Беллмана-Форда и протоколы на основе алгоритма DUAL. Вычисление маршрутов, исходя из топологической информации, обычно требует больше усилий по обработке, чем необходимо для выполнения дистанционно-векторных вычислений. Кроме того, чтобы обеспечить идентичность топологических сведений на всех маршрутизаторах, требуется более интенсивный обмен данными между маршрутизаторами.

Если протоколы маршрутизации по состоянию канала сходятся быстрее, чем протоколы Беллмана-Форда, этого нельзя сказать при сравнении этих протоколов с протоколами на основе алгоритма DUAL. Экспериментальные данные указывают на то, что в большинстве случаев протоколы маршрутизации на основе DUAL сходятся, по меньшей мере настолько же быстро, как и протоколы маршрутизации по состоянию канала.

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

Эта открытость позволила множеству различных производителей, включая Cisco, успешно реализовать протокол OSPF в своем оборудовании и программном обеспечении. Хотя протоколы маршрутизации, основанные на

162

конкурирующем алгоритме DUAL, работают быстро, практически единственный популярный экземпляр таких протоколов – это протокол EIGRP, являющийся фирменным протоколом корпорации Cisco.

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

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

9.1 Алгоритм «кратчайшего пути» Дейкстры

Алгоритм кратчайшего пути – shortest path algorithm (SPF) Дейкстры работает с графами, состоящими из вершин, соединенных ребрами. Каждое ребро соединяет ровно две вершины в одном направлении. Каждое ребро имеет стоимость, связанную с ним. Каждая вершина может быть связана с любым числом ребер.

Вершины можно представлять как точки, а ребра – как перемещение между этими точками. Перемещение обеспечивается лишь в одном направлении и за определенную стоимость – в направлении ребра и за стоимость ребра. Например, если ребро соединяет вершину A с вершиной B, это означает, в сущности, что имеется возможность за стоимость этого ребра переместиться из вершины A в вершину B. Это ребро, однако, не позволяет переместиться обратно из вершины B в вершину A. Такое перемещение требует наличия другого ребра – из вершины B в вершину A.

		1	B
	A
			3	3
		8	5		D
		4
	4	C
	2		7	2	8
		6
	E	4		F

Рисунок 9.4 – Пример графа

163

На рисунке 9.4 приводится пример графа. Этот граф содержит шесть вершин, помеченных буквами от A до F. Ребра обозначаются линиями со стрелками, которые соединяют вершины, а стоимость ребер указана в виде чисел, изображенных поверх ребер.

Говорится, что вершина X является смежной с вершиной Y, если имеется ребро, ведущее от вершины X к вершине Y. Например, на рисунке 9.4 вершина B является смежной с вершиной A. Необходимо обратить внимание, что обратное может быть неверно, например, вершина A не является смежной с вершиной B, поскольку ребра, ведущего от вершины A к вершине B, не существует.

Граф с большим количеством вершин может иметь множество путей между двумя вершинами. Среди этих путей лучший путь определяется как путь, совокупная стоимость которого, рассчитана как минимальная сумма стоимостей составляющих путь ребер. Например, кратчайший путь от вершины D к вершине A лежит через вершину B, его стоимость равна 4. Обратный путь, от вершины A к вершине D, имеет большую длину, он лежит через вершины C и B и имеет стоимость 15.

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

Алгоритм SFP решает задачу быстрого нахождения кратчайшего пути между любыми двумя вершинами в графе с произвольными связями.

Для работы алгоритм использует две вспомогательные структуры данных: базу данных вершин, для которых ищется кратчайший путь, и базу данных вариантов вершин, для которых кратчайший путь может быть найден. Обозначим эти базы как «Найденные» и «Кандидаты». Обе базы данных имеют идентичную структуру: они содержат два поля, содержащие ссылку на вершину и совокупную стоимость пути от начальной вершины к указанной.

Чтобы продемонстрировать работу алгоритма по шагам воспользуемся графом, изображенным на рисунке 9.4.

Работа алгоритма начинается с помещения начальной вершины в базу «Найденные» с совокупной стоимостью 0, а всех ее смежных вершин - в базу «Кандидаты» с совокупной стоимостью, равной стоимости соответствующих ребер. После этого алгоритм циклически проходит через следующие рекурсивные шаги:

Шаг 1. Найти в базе «Кандидаты» вершину с наименьшей совокупной стоимостью. Переместить вершину в базу «Найденные».

Шаг 2. Определить вершины, с которыми перемещенная вершина является смежной.

Шаг 3. Отбросить смежные вершины данной вершины, которые уже были перемещены в базу «Найденные».

164

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

Cсмеж. нов. = min(Cсмеж. стар., C перемещ. + Cребра)

(9.1)

где Cсмеж. нов. и Cсмеж. стар. – соответственно новая и старая записанные совокупные стоимости смежной вершины,

C перемещ. – записанная совокупная стоимость перемещенной вершины, Cребра – стоимость ребра от перемещенной вершины к смежной.

Шаг 5. Поместить каждую смежную вершину, не содержащуюся ни в базе «Найденные», ни в базе «Кандидаты», в базу «Кандидаты». Установить ее совокупную стоимость равной сумме совокупной стоимости перемещенной вершины и стоимости ребра, ведущего от перемещенной вершины к смежной, формула (9.2).

Cсмеж. = C перемещ. + Cребра

(9.2)

где Cсмеж. – совокупная стоимость смежной вершины.

Шаг 6. Если база «Кандидаты» пуста, завершить работу. В противном случае вернуться к Шагу 1 и повторить действия.

На рисунке 9.5 каждый из шести шагов помещен отдельно и помечен своим номером. Вершины, которые были помещены в базу «Найденные», отмечены жирной границей, а вершины с тонкой границей попали только в базу «Кандидаты». Числа на ребрах указывают совокупную стоимость пути от начальной вершины к вершине, к которой ребро ведет, тогда как на рисунке 9.4, числа обозначали стоимость ребер. Если на ребре находится вопросительный знак, это означает, что вершина, к которой ведет ребро, уже находится в базе «Найденные», и, поэтому совокупная стоимость для нее не рассчитывается.

Кроме того, для каждой итерации приведено содержимое баз «Найденные» и «Кандидаты». Вершина, которая только что была помещена в базу «Найденные», помечена звездочкой. Вершины, которые либо были помещены в базу «Кандидаты» либо имеют обновленные существующие записи в этой базе, помечены знаком «>». Если совокупная стоимость заменена меньшей величиной, в соответствующей записи базы «Кандидаты» показано старое значение, «>», а затем новое значение.

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

165

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

Шаг 1

A

Шаг 2

A

4

4

Найденные

4

4

Найденные

С

E

*

А

0

С

E

А

0

Кандидаты

12

*

C

4

>

C

4

B

Кандидаты

>

E

4

E

4

>

B

12

Шаг 3

A

Шаг 4

A

4

4

Найденные

4

4

Найденные

С

E

А

0

С

E

А

0

C

4

C

4

12

?

?

8

12

8

B

A

*

B

F

C F

E

4

E

4

Кандидаты

16

F

8

D

*

B

12

Кандидаты

>

F

8

B

12

>

D

16

Шаг 5

A

Шаг 6

A

4

4

Найденные

4

4

Найденные

12 С

E 8

А

0

12 С

E 8

А

0

C

4

C

4

?

B

F

E

4

B

F

E

4

?

15

16

B

12

15

B

12

*

*

A

C D

D

D

Кандидаты

?

?

Кандидаты

?

>

D

16→15

B E

F

<Пусто >

Рисунок 9.5 – Итерации алгоритма SPF

166