Магистрант Галькевич А. В.

Белорусский Государственный Университет Информатики и Радиоэлектроники, Республика Беларусь

Определение показателей эффективности протокола динамической маршрутизации OSPF

На сегодняшний день широкое применение получили IP-сети. Одна из главных задач, которые решаются при построении сетей является динамическая маршрутизация. Примером большой ИП-сети, на которой применяются протоколы динамической маршрутизации, является глобальная сеть Интернет, представляющая собой совокупность так называемых автономных систем. Для организации маршрутизации внутри автономных систем широко применяется протокол динамической маршрутизации OSPF (Open Shortest Path First). В соответствии с ним решаются две основные задачи: определение оптимальных маршрутов и обмен маршрутной информацией между маршрутизаторами в сети. [2]

Протокол OSPF обеспечивает создание двухуровневой иерархической сетевой структуры, состоящей из магистральной области (Area 0) и других подключенных к ней областей. Он предусматривает, что все маршрутизаторы входящие в одну область имеют одинаковую базу данных о топологии своей области. Граничные маршрутизаторы областей распространяют обобщенные маршруты к каждой из областей. [2]

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

Документ RFC 2328 [1] регламентирует алгоритмы взаимодействия маршрутизаторов в соответствии с протоколом OSPF и форматы служебных пакетов. Для анализа рассмотрена предельно общая ситуация, приводящая к изменению топологии сети: момент соединения/отсоединения двух частей сети. Обмен маршрутной информацией при соединении двух маршрутизаторов, относящимся к разным частям сети, осуществляется в несколько этапов. В соответствии с алгоритмом Hello маршрутизаторы начинают предпринимать действия для установления так называемых соседских отношений. При первичной инициализации маршрутизаторов осуществляется передача 960 бит служебного трафика. Далее осуществляется обмен пакетов типа DD (Database Description) (T_DD, бит) описывающих базы данных маршрутизаторов и пакетов типа LSR (Link State Request) (T_LSR, бит) являющихся запросами на передачу частей маршрутной информации – анонсов LSA (Link State Advertisement).

(1)

(2)

где N_LSA – количество собственных LSA, шт.; N_{LSA_соседа} – количество LSA у соседа, шт.; L_{заг_кан} – длина заголовка протокола канального уровня, бит; MTU – значение величины MTU, бит.

После обмена запросами LSR начинается непосредственно этап лавинной рассылки анонсов LSA в пакетах LSU (Link State Update) (T_LSU, бит), прием которых подтверждается пакетами LSAck (Link State Acknowledgment) (T_LSAck, бит). Объем трафика, генерируемого этими пакетами, определяется как:

(3)

(4)

(5)

(6)

(7)

где T_routerLSA, T_networkLSA и T_summaryLSA – трафик, генерируемый пакетами LSU для передачи анонсов типа routerLSA, networkLSA и summaryLSA соответственно, бит; N_router – количество маршрутизаторов в области OSPF, шт.; N_subnet – количество подсетей в области OSPF, шт; N_area – количество областей OSPF в сети, шт.

Кроме служебного трафика, который передается при изменениях топологии сети, также генерируется периодический трафик (T_период, бит/с). Для определения работоспособности каналов с периодом HelloInterval секунд осуществляется передача пакетов типа Hello. Для увеличения показателей надежности сети с периодом LSRefreshTime осуществляется перегенерация и обмен всех анонсов LSA.

(8)

(9)

где t_{HelloInterval} – значение таймера HelloInterval, сек.; t_{LSRefreshTime} – значение таймера LSRefreshTime, сек.; T_hello – размер пакета Hello, бит; T_flooding – трафик генерируемый пакетами, содержащими анонсы LSA, за один период, бит.

Для оценки времени схождения проанализированы два случая: присоединение одной части сети к другой и отсоединение одной части сети от другой. При присоединении одной части сети к другой происходят следующие события: устанавливаются первичные отношения смежности между маршрутизаторами, между которыми непосредственно устанавливается физическое соединение кабелем, лавинная рассылка обновлений LSA (flooding) и перерасчет оптимальных маршрутов алгоритмом Дейкстри. При отсоединении одной части сети от другой происходят следующие события: разрушаются отношения смежности между маршрутизаторами при отсутствии приема пакета Hello от соседнего маршрутизатора за период DeadInterval секунд, лавинная рассылка обновлений LSA и перерасчет оптимальных маршрутов алгоритмом Дейкстри. Время схождения в этих ситуациях (t_{схождения+}, t_{схождения-}, сек.) рассчитывается как:

(10)

(11)

где t_neighbor – значение времени установления отношений смежности, сек.; t_flooding – значение времени, в течение которого осуществляется лавинная рассылка обновлений LSA, сек.; t_Dijkstra – значение времени, в течение которого осуществляется расчет по алгоритму Дейкстри, сек.; t_DeadInterval – значение таймера DeadInterval, сек.

Значение времени, затрачиваемое на установление отношений смежности (t_neighbor, сек.), зависит от объема трафика, генерируемого во время этих операций, и пропускной способности канала связи:

(12)

где T_exchange – объем трафика, генерируемого при установлении первичных отношений смежности, бит; T_loading – объем трафика, генерируемого при первичном описании своих баз данных, бит; F_{кан_сосед} – значение пропускной способности канала связи между непосредственно соединяемыми маршрутизаторами, бит/сек.

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

(13)

где T_flooding↓ и T_flooding↑ – объем трафика, генерируемого при передаче обновлений LSA между маршрутизаторами в одной и второй части сети соответственно, бит; F_{кан i} и F_{кан j} – значение пропускной способности канала связи на i-ом участке оптимального пути к самому удаленному маршрутизазатору в одной части сети и на j-ом участке оптимального пути к самому удаленному маршрутизазатору в другой части сети соответственно, бит/сек.

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

Литература:

1. RFC 2328 «OSPF Version 2», April 1998.

2. Томас М. «Структура и реализация сетей на основе протокола OSPF», 2-е изд.: Пер. с англ. — М.: Издательский дом "Вильямс", 2004.