Автореферат

Трубицын К.Ю.

Тема: «Алгоритмы оптимальной маршрутизации в сетях сложной топологии»

1. Актуальность работы
2. Новизна работы
3. Краткое описание алгоритмов и протоколов маршрутизации
4. Требования к алгоритму маршрутизации
5. Классификация алгоритмов и протоколов маршрутизации
6. Практические результаты
7. Выводы
8. Литература

В последнее время в Украине сложилась тенденция к замене старого, морально и физически устаревшего оборудования на новое цифровое, отвечающее всем современным требованиям. Примеров того может служить цифровизации таких шахт-гигантов как “Красноармейская-Западная №1”, “Комсомолец Донбасса”, промышленные гиганты “Донецкий металлургический завод”, “Азовсталь” и многие другие. Однако с ростом качества оборудования возрастает и нагрузка на существующие линии связи. Поэтому острым становится вопрос либо и замене линий связи на более современные (оптику например), что неизбежно влечет за собой огромные затраты как финансового, так и временного характера, либо оптимизировать уже существующую на сегодняшний день структуру сети. Вариантов оптимизации множество и главный вопрос в том, чтобы правильно подобрать нужный алгоритм исходя из реального состояния вещей. Задачей моей магистерской работы является математическое исследование алгоритмов оптимальной маршрутизации исходя из реального значения требуемой пропускной способности канала связи и постороение виртуальных маршрутных топологий сетей.

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

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

Основными формами каждого маршрутизатора, реализуемым в соответствии с протоколами маршрутизации, являются:

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

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

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

1. Сетевой адрес получателя.
2. Адрес следующего маршрутизатора, пересылка к которому соответствует оптимальному пути до пункта назначения.
3. Характеристику пути, например, пропускная способность канала связи и отметку времени, когда эта характеристика была определена.
4. Информацию о способе пересылки, например, номер выходного порта.

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

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

1. Длина маршрута, измеренная количеством маршрутизаторов, через которое необходимо пройти до пункта назначения.
2. Пропускная способность канала связи.
3. Прогнозируемое суммарное время пересылки.
4. Стоимость канала связи.

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

1. Считывает из заголовка пакета, соответствующий сетевому уровню модели OSI, адрес назначения, т.е. сетевой адрес получателя.
2. По таблице маршрутизации определяется адрес следующего транзитного маршрутизатора, пересылка к которому соответствует оптимальному пути до пункта назначения.
3. Заменяет в заголовке пакета, соответствующий канальному уровню модели OSI, свой МАС- адрес на МАС- адрес выбранного транзитного маршрутизатора.
4. Отсылает пакет выбранному транзитному маршрутизатору.

По мере того, как пакет передвигается через сеть, физический адрес (МАС- адрес) его получателя меняется, но логический адрес пункта назначения, соответствующий сетевому уровню модели OSI, остается без изменений.

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

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

1. По оптимизации определенных маршрутов – способности определять наилучший маршрут в зависимости от заданных показателей и их весовых коэффициентов.
2. По гибкости – способность быстро и точно адаптироваться к изменениям структуры и условий функционирования сети.
3. По сходимости – способности достичь быстрого соглашения между маршрутизаторнами сети по оптимальным маршрутам.

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

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

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

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

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

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

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

Теоретический анализ идеи подробно описан в моей статье [1].

В ходе работы по данной тематике в рамках Научно-исследовательской работы был проведен теоретический анализ модели алгоритма по исходным данным одного из провайдеров города Донецка и полученные некоторые результаты.

Рассмотрим пример расчета исходя из теоретического обоснования. Например, возьмем граф (6 терминальных узлов и 1 тандем):

Рассмотрим маршрут 2-5. Проставим соединения узлов друг с другом:

Проставим соединения узлов с другими узлами:

Где N₁-количество транков в маршруте 1-Т;
N₂-количество транков в маршруте 2-Т;
- Количество транков необходимое чтобы обеспечить переполняющий трафик от узла 1 к Т;
dN₂ - Количество транков необходимое чтобы обеспечить переполняющий трафик от узла 1 к Т;
N - количество транков в маршруте 2-1;
dN - Количество транков необходимое чтобы обеспечить переполняющий трафик от узла 1 к 2;
M – значение трафика для маршрута (1-2);
dM– значение трафика переполнения для маршрута (1-Е);
N₁ - Количество транков необходимое чтобы обеспечить переполняющий трафик от узла 2 к Т;
С₁- пропускная способность канала 1-Т (10);
С₂- пропускная способность канала 2-Т (10);
С- пропускная способность канала 1-2 (8).

Далее из известной нагрузки (зададимся ее величиной сами) необходимо найти необходимое количество транков для маршрута с учетом трафика переполнения от смежных узлов (будем считать, что трафик переполнения идет только от ближайшего узла и метрики всех узлов (т.е. их взаимные приоритеты при передачи трафика) одинаковы). Например, величина трафика-15 Эрлангов. Далее по графикам и используя аппроксимацию Рапса находим величины F(показатель улучшения использования транка)

Аппроксимация Рапса:

Отсюда с учетом исходных данных получим F=0,4*(0,7+0,3*0,4*0,4)=0,2992 Далее с использованием графика найдем необходимое количество транков для 1-2 с учетом транков, необходимых для транзита трафика переполнения. Получаем, что ближайшее N при А=15 и F=0,2992 равно 19, следователь, для нашого случая между узлами 1 и 2 необходима линия с 19 транками!

Далее рассмотрим пример с использованием метода Вилкинсона:

Метод Вилкинсона заключается в нахождении значения трафика переполнения на маршруте. Возмем наш пример и найдем это значение для маршрута 2-Т. На этом маршруте кроме своего трафика влияет также ызбыточный трафик от узлов 1,3,5. Он находится такои образом: - где А*-фиктивный трафик (т.е. единый трафик, который учитывает и влияние избыточного), N*-фиктивное количество транков, которое включает в себя транзит избыточного трафика.

С помощью формул, приведенных в теоретической части, и соответствующих графиков, находим их:

Т.е. мы видим, что при уровне трафика 15 Эрлангов и рпи количестве транков (найдено раньше) нам необходимо М (значение трафика переполнения)= 0,9 и V (изменения трафика переполнения)=3,4 Далее находим A* и N*. Они будут равны соответственно 34,88 и 42,46. Далее по формуле Эрланга (приведена выше) находим mт. Итак, оно получилось равно:

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

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

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

1. Трубицын К.Ю. Альтернативные сети маршрутизации
2. Джон Вакка. Секреты безопасности в Internet. Перевод с английского. – Киев; Диалектика, 1997г.
3. Джеймс Саймино. Сети интранет: внутреннее движение. Превод с английского. – М.: ООО «Бук Медиа Паблишер». 1997г.
4. Владимир Зима. Безопасность глобальных сетевых технологий /В.М. Зима, А.А. и Н.А. Молдавян. СПб и др.: БХВ – Санкт – Петербург, 2000 г.
5. H.Leijon, ITU. Alternative Routing Networks