Протоколы маршрутизации на основе алгоритма состояния канала

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

Принципы работы маршрутизаторов в соответствии с этими протоколами можно сформулировать в виде пяти правил:

1. при включении в сеть получить информацию о своих соседях;
2. узнать стоимость пути до каждого из соседей (т. е. узнать о состоянии каналов);
3. подготовить пакет-объявление, содержащий полученную информацию;
4. разослать этот пакет всем соседям;
5. построить дерево кратчайших расстояний до всех остальных маршрутизаторов.

 

OSPF

Протокол OSPF (Open Shortest Path Fisrt - открытый протокол, базирующийся на алгоритме поиска наикратчайшего пути RFC-1245-48, RFC-1583-1587, алгоритмы предложены Дикстрой) является альтернативой RIP в качестве внутреннего протокола маршрутизации. OSPF представляет собой протокол состояния соединения (Link State).

Протокол разработан для сетей IP рабочей группой Internet Engineering Task Force (IETF), занимающейся разработкой протоколов для внутрисистемных роутеров (interior gateway protocol - IGP).

Протокол относится к иерархическим протоколам маршрутизации. В нем определяется область маршрутизации.

Самым крупным объектом в этой иерархии является автономная система (Autonomous System - AS) AS является набором сетей, которые находятся под единым управлением и совместно используют общую стратегию маршрутизации. OSPF является протоколом маршрутизации внутри AS, хотя он и способен принимать маршруты из других AS и отправлять маршруты в другие AS.

Любая AS может быть разделена на ряд областей (area). Область - это группа смежных сетей и подключенных к ним хостов.

Протокол требует отправки объявлений о состоянии канала (link-state advertisement - LSA) во все роутеры, которые находятся в пределах одной и той же области. Роутеры, имеющие несколько интерфейсов, могут участвовать в нескольких областях. Такие роутеры, которые называются роутерами границы областей (area border routers), поддерживают отдельные топологические базы данных для каждой области.

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

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

Магистральная часть OSPF (backbone) отвечает за распределение маршрутной информации между областями. Она включает в себя все роутеры границы области, сети, которые не принадлежат полностью како-либо из областей, и подключенные к ним роутеры. На Рис. представлен пример сети с несколькими областями.

 

На этом рисунке роутеры 4, 5, 6, 10, 11 и 12 образуют магистраль. Если хост Н1 Области 3 захочет отправить пакет хосту Н2 Области 2, то пакет отправляется в роутер 13, который продвигает его в роутер 12, который в свою очередь отправляет его в роутер 11. Роутер 11 продвигает пакет вдоль магистрали к роутеру 10 границы области, который отправляет пакет через два внутренних роутера этой области (роутеры 9 и 7) до тех пор, пока он не будет продвинут к хосту Н2.

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

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

После получения подтверждения о работоспособности своих интерфейсов роутер использует приветственный протокол (hello protocol) OSPF, чтобы приобрести соседей (neighbor). Соседи - это роутеры с интерфейсами с общей сетью. Описываемый роутер отправляет своим соседям приветственные пакеты и получает от них такие же пакеты. Помимо оказания помощи в приобретении соседей, приветственные пакеты также действуют как подтверждение дееспособности, позволяя другим роутерам узнавать о том, что другие роутеры все еще функционируют.

В сетях с множественным доступом (multi-access networks) (сетях, поддержиающих более одного роутера), протокол Hello выбирает назначенный роутер (designated router) и дублирующий назначенный роутер. Назначеный роутер, помимо других функций, отвечает за генерацию LSA для всей сети с множественным доступом. Назначенные роутеры позволяют уменьшить сетевой трафик и объем топологической базы данных.

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

Опишем алгоритм Дикстры по выбору оптимального пути. На рис. приведена схема узлов (A-J) со значениями метрики для каждого из отрезков пути. Анализ графа начинается с узла A (Старт). Пути с наименьшим суммарным значением метрики считаются наилучшими. Именно они оказываются выбранными в результате рассмотрения графа (“кратчайшие пути“).

 

 

Пусть D(v) равно сумме весов связей для данного пути.
Пусть c(i,j) равно весу связи между узлами с номерами i и j.

Далее следует последовательность шагов, реализующих алгоритм.

1. Устанавливаем множество узлов N = {1}.

2. Для каждого узла v не из множества N устанавливаем D(v)= c(1,v).

3. Для каждого шага находим узел w не из множества N, для которого D(w) минимально, и добавляем узел w в множество N.

4. Актуализируем D(v) для всех узлов не из множества N
D(v)=min{D(v), D(v)+c(w,v)}.

5. Повторяем шаги 2-4, пока все узлы не окажутся в множестве N.

Топология маршрутов для узла A приведена на нижней части рис. В скобках записаны числа, характеризующие метрику отобранного маршрута согласно критерию пункта 3.

 

Таблица реализации алгоритма

 

	Множество	Метрика связи узла a с узлами
Шаг	N	B	C	D	E	F	G	H	I	J
	{A}	3	-		-	-	-	-	-	-
	{A,B}	(3)	4			-		-	-	-
	{A,B,C}	(3)	(4)	6		-		-	-	-
	{A,BC,D}	(3)	(4)	(6)	6	-		-	-	-
	{A,B,C,D,E}	(3)	(4)	(6)	(6)			8	-	-
	{A,B,C,D,E,H}	(3)	(4)	(6)	(6)			(8)	9	-
	{A,B,C,D,E,H,I}	(3)	(4)	(6)	(6)	10		(8)	(9)
	{A,B,C,D,E,H,I,F}	(3)	(4)	(6)	(6)	(10)	10	(8)	(9)
	{A,B,C,D,E,H,I,F,G}	(3)	(4)	(6)	(6)	(10)	(10)	(8)	(9)	14
	{A,B,C,D,E,H,I,F,G,J}	(3)	(4)	(6)	(6)	(10)	(10)	(8)	(9)	(14)

 

Качество сервиса (QoS), выступающее в качестве метрики протокола, может характеризоваться следующими параметрами:

· пропускной способностью канала;

· задержкой (время распространения пакета);

· числом дейтограмм, стоящих в очереди для передачи;

· загрузкой канала;

· требованиями безопасности;

· типом трафика;

· числом шагов до цели;

· возможностями промежуточных связей (например, многовариантность достижения адресата).

Определяющими являются три характеристики: задержка, пропускная способность и надежность. Для транспортных целей OSPF использует IP непосредственно, т.е. не привлекает протоколы UDP или TCP. OSPF имеет свой код (89) в протокольном поле IP-заголовка. Код TOS (type of service) в IP-пакетах, содержащих OSPF-сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF. Маршрутизация в этом протоколе определяется IP-адресом и типом сервиса. Так как протокол не требует инкапсуляции пакетов, сильно облегчается управление сетями с большим количеством бриджей и сложной топологией (исключается циркуляция пакетов, сокращается транзитный трафик).

 

Любое сообщение OSPF начинается с 24-октетного заголовка:

 

Поле версия определяет версию протокола (= 2). Поле тип идентифицирует функцию сообщения согласно таблице

 

Тип	Значение
	Hello (используется для проверки доступности маршрутизатора).
	Описание базы данных (топология). Database Description.
	Запрос состояния канала. Link-State Request
	Изменение состояния канала. Link-State Update
	Подтверждение получения сообщения о статусе канала. Link-State Acknowledgement

 

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

Поле контрольная сумма содержит контрольную сумму IP-пакета, включая поле типа идентификации.

Поле тип идентификации может принимать значения 0 при отсутствии контроля доступа, и 1 при наличии контроля. В дальнейшем функции поля будут расширены. Важную функцию в OSPF-сообщениях выполняет одно-октетное поле опции, оно присутствует в сообщениях типа Hello, объявление состояния канала и описание базы данных. Особую роль в этом поле играют младшие биты E и Т:

Бит E характеризует возможность внешней маршрутизации и имеет значение только в сообщениях типа Hello, в остальных сообщениях этот бит должен быть обнулен. Если E=0, то данный маршрутизатор не будет посылать или принимать маршрутную информацию от внешних автономных систем. Бит T определяет сервисные возможности маршрутизатора (TOS). Если T=0, это означает, что маршрутизатор поддерживает только один вид услуг (TOS=0) и он не пригоден для маршрутизации с учетом вида услуг.

1. Сообщения типа Hello содержат, в частности, следующую информацию: уровень приоритета маршрутизатора (целое положительное число), используется при выборе резервного (backup) маршрутизатора. Если приоритет равен нулю, данный маршрутизатор никогда не будет использован в качестве резервного.

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

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

4. Сообщения об изменениях маршрутов могут быть вызваны следующими причинами:

1. Возраст маршрута достиг предельного значения (lsrefreshtime).
2. Изменилось состояние интерфейса.
3. Произошли изменения в маршрутизаторе сети.
4. Произошло изменение состояния одного из соседних маршрутизаторов.
5. Изменилось состояние одного из внутренних маршрутов (появление нового, исчезновение старого и т.д.)
6. Изменение состояния межзонного маршрута.
7. Появление нового маршрутизатора, подключенного к сети.
8. Вариация виртуального маршрута одним из маршрутизаторов.
9. Возникли изменения одного из внешних маршрутов.
10. Маршрутизатор перестал быть пограничным для данной as (например, перезагрузился).

5. В составе информации о состоянии канала передаются значения типов сервиса (TOS), поддерживаемые маршрутизатором, рассылающим маршрутную информацию.

6.

TOS(RFC-1349)

Обычный сервис

Минимизация денежной стоимости

Максимальная надежность

Максимальная пропускная способность

Минимальная задержка

 

Передается так же информация о месте маршрутизатора в области и АС.

Существуют 4 типа LSA:

Router links advertisements (RLA)

Об'явления о каналах роутера. Описывают собранные данные о состоянии каналов роутера, связывающих его с конкретной областью. Любой роутер отправляет RLA для каждой области, к которой он принадлежит. RLA направляются лавинной адресацией через всю область, но они не отправляются за ее пределы.

Network links advertisements (NLA)

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

Summary links advertisements (SLA)

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

AS external links advertisements

Об'явления о внешних каналах AS. Описывают какой-либо маршрут к одному из пунктов назначения, который является внешним для данного AS. Об'явления о внешних каналах AS вырабатываются граничными роутерами AS. Этот тип об'явлений является единственным типом об'явлений, которые продвигаются во всех направлениях данной AS; все другие об'явления продвигаются только в пределах конкретных областей.

 

Маршрутная таблица OSPF содержит в себе:

· IP-адрес места назначения и маску;

· тип места назначения (сеть, граничный маршрутизатор и т.д.);

· тип функции (возможен набор маршрутизаторов для каждой из функций TOS);

· область (описывает область, связь с которой ведет к цели, возможно несколько записей данного типа, если области действия граничных маршрутизаторов перекрываются);

· тип пути (характеризует путь как внутренний, межобластной или внешний, ведущий к AS);

· цена маршрута до цели;

· очередной маршрутизатор, куда следует послать дейтограмму;

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

 

Преимущества OSPF:

1. Для каждого адреса может быть несколько маршрутных таблиц, по одной на каждый вид IP-операции (TOS).

2. Каждому интерфейсу присваивается безразмерная цена, учитывающая пропускную способность, время транспортировки сообщения. Для каждой IP-операции может быть присвоена своя цена (коэффициент качества).

3. При существовании эквивалентных маршрутов OSFP распределяет поток равномерно по этим маршрутам.

4. Поддерживается адресация субсетей (разные маски для разных маршрутов).

5. При связи точка-точка не требуется IP-адрес для каждого из концов. (Экономия адресов!)

6. Применение мультикастинга вместо широковещательных сообщений снижает загрузку не вовлеченных сегментов.

Недостатки:

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

2. OSPF является лишь внутренним протоколом.

 

Оба этих протокола предназначены для внутренних маршрутизаторов автономных систем. Под автономной системой принято понимать некоторую совокупность IP-сетей, использующих общую политику маршрутизации в Internet. Эта общая политика реализуется пограничными маршрутизаторами данной автономной системы с использованием, например, протокола BGP (Border Gateway Protocol, протокол граничного шлюза) — основного протокола динамической маршрутизации в Интернете.

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