Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

УДК 681.3

ОПТИМИЗАЦИЯ РАБОТЫ КОРПОРАТИВНЫХ

КОМПЬЮТЕРНЫХ СЕТЕЙ

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

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

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

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

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

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

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

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

Цель статьи

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

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

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

Задача о кратчайшем пути на графе в общем виде может быть сформулирована следующим образом [4]. Дан неориентированный граф . Каждому ребру этого графа приписано некоторое число , назы­ваемое длиной ребра. В частных случаях  может быть расстоянием между вершинами, соединяемыми реб­ром , временем или стоимостью проезда по этому ребру и т. п. При этом любая цепь , будет характеризоваться длиной

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

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

При этом f называется целевой функцией, Х – множеством решений, любой элемент xÎX – решением задачи.

Необходимо найти точку глобального минимума функции f на множестве X такую, что

Эта задача решается с помощью методов исследования операций и средств теории принятия решений [5-7].

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

Для поиска кратчайшего маршрута предлагается использовать алгоритм SPF (Shortest Path First), разработанный Дейкстрой [9]. В соответствии с этим алгоритмом кратчайший путь между вершинами графа равен [3]:

где        - расстояния в сети между смежными узлами  и ;

 - кратчайший путь между «источником» -  и  - -ым узлом;

 - кратчайший путь между «источником»  и  - предыдущим узлом в сети.

Разработанная программная реализация алгоритма представлена в [10].

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

Алгоритм 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). Маршрутизаторы, принадлежащие некоторой области, строят граф связей только для этой области, что сокращает размерность сети. Между областями информация о связях не передается, а пограничные для областей марш­рутизаторы обмениваются только информацией об адресах сетей, имеющихся в каждой из областей, и расстоянием от пограничного маршрутизатора до каждой сети [8].

Протокол 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.