---

         Оптимизация работы корпоративных компьютерных систем

    Авторы: Бараненко Р.В., Козел В.Н., Дроздова Е.А., Плотников А.О.

    Источник: Публикация [Перейти]

   Постановка проблемы

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

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

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

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

   Анализ последних исследований

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

   Цель статьи

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

   Основной материал

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

Задача оптимизации формулируется в общем виде, когда заданы множество Х и функция f(x), определенная на Х; и требуется найти точки минимума функции f на X, получаем следующую запись: f(x)→min, x, при этом f называется целевой функцией, Х – множеством решений, любой элемент x – решением задачи.

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

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

Для поиска кратчайшего маршрута предлагается использовать алгоритм SPF (Shortest Path First), разработанный Дейкстрой.

Для больших гетерогенных сетей реализацией алгоритма SPF является протокол OSPF (Open Shortest Path First). В OSPF процесс построения таблицы маршрутизации разбивается на два круп­ных этапа. На первом этапе каждый маршрутизатор строит граф связей сети, в котором вершинами графа являются маршрутизаторы и IP-сети, а ребрами – ин­терфейсы маршрутизаторов. Все маршрутизаторы для этого обмениваются со сво­ими соседями той информацией о графе сети, которой они располагают к данному моменту времени. Второй этап состоит в нахождении оптимальных маршрутов с помощью полу­ченного графа. Каждый маршрутизатор считает себя центром сети и ищет опти­мальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг – до следующего маршрутизато­ра, в соответствии с принципом одношаговой маршрутизации. Данные об этом шаге и попадают в таблицу маршрутизации. Задача нахождения оптимального пути на графе является достаточно сложной и трудоемкой.

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

Пусть

S – заданная вершина (источник путей);

E – множество обработанных вершин, т.е. вершин, кратчайший путь к которым уже найден;

R – множество оставшихся вершин графа (т.е. множество вершин графа за вычетом множества E);

O –упорядоченный список путей.

Предлагаемый алгоритм состоит из повторяемых выполнений следующих шагов:

1. Инициализировать E={S}, R={все вершины графа, кроме S}. Поместить в О все односегментные (длиной в одно ребро) пути, начинающиеся из S, отсортировав их в порядке возрастания метрик.

2. Если О пуст или первый путь в О имеет бесконечную метрику, то отметить все вершины в R как недостижимые и закончить работу алгоритма.

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

Если V принадлежит E, перейти на шаг 2; иначе P является кратчайшим путем из S в V; перенести V из R в E.

4. Построить набор новых путей, подлежащих рассмотрению, путем добавления к пути P всех односегментных путей, начинающихся из V. Метрика каждого нового пути равна сумме метрики P и метрики соответствующего односегментного отрезка, начинающегося из V. Добавить новые пути в упорядоченный список О, поместив их на места в соответствии со значениями метрик. Перейти на шаг 2.

Протокол OSPF разрешает хранить в таблице маршрутизации несколько марш­рутов к одной сети. Если такие записи образуются в таблице маршрутизации, то маршрутизатор реализует режим балан­са загрузки маршрутов (load balancing), отправляя пакеты попеременно по каждо­му из маршрутов.

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

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

   Выводы

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

  Список литературы

 

1. Ю.Н. Бардачев, Н.А. Соколова, В.Е. Ходаков / Под редакцией В.Е. Ходакова. Основы дискретной математики: учебное пособие – Херсон: Издательство ХГТУ – 2000. – 356 с.

    2. Оре О. Теория графов. – М.: Наука, 1968.

3. Гудман С., Хидитмиеми С. Введение в разработку и анализ алгоритмов. – К.: Вища школа, 1985. – 350с.

4. Коршунов Ю.М. Математические основы кибернетики: Учеб. пособие для вузов. – 2-е изд., перераб. и доп. – М.: Энергия, 1980. – 424 с., ил.

5. Петров Э.Г., Новожилова М.В., Гребенник И.В., Соколова Н.А. Методы и средства принятия решений в социально-экономических и технических системах. Учебное пособие /Под общей редакцией Э.Г. Петрова – Херсон: ОЛДІ – плюс, 2003. – 380 с.

6. Зайченко Ю.П. Исследование операций. – К.: Выща школа, 1986.

7. Горелик В.А., Ушаков И.А. Исследование операций. – М.: Машиностроение, 1986. – 288 с.

8. Компьютерные сети. Принципы, технологии, протоколы / В.Г. Олифер, Н.А. Олифер. – СПб.: Питер, 2001. – 672 с.: ил.

9. Dijkstra E. Cooperating Sequential Processes. Technological University, Eindhoven, The Netherlands, 1965. (Reprinted in Great Papers in Computer Science, P. Laplante, ed. New York, NY: IEEE Press, 1996).

10. Свідоцтво про реєстрацію авторського права на твір №7258, “Комп'ютерна програма пошуку найкращого маршруту між двома вершинами графа “ShorW”. Автори: Р.В. Бараненко, Д.В. Санін, А.Г. Степаненко, А.С. Шаповалов. Опубл. 06.03.2003.

11. Вычислительные системы, сети и телекоммуникации. Пятибратов и др. – ФИС, 1998.

12. Высокопроизводительные сети. Энциклопедия пользователя. Марк А. Спортак и др.; перев. с англ. – К.: ДиаСофт, 1998.