Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 681.3

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

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

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

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

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

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

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

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

 

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

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

 

Цель статьи

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

 

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

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

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

,

(1)

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

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

 

f(x)→min, xÎX,

(2)

 

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

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

,

(3)

 

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

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

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

 

,

(4)

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

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

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

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

 

Выводы

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

 

In given article the questions of optimization of job of corporate computer networks are considered, the basic principles of construction of such networks are formulated and the algorithm of optimization of their job is offered.

 

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.

 





Ответы на вопросы [_Задать вопроос_]

Информационно-управляющие комплексы и системы

Теленик С.Ф., Ролік О.І., Букасов М.М., Андросов С.А. Генетичні алгоритми вирішення задач управління ресурсами і навантаженням центрів оброблення даних

Богушевский В.С., Сухенко В.Ю., Сергеева Е.А., Жук С.В. Реализация модели управления конвертерной плавкой в системе принятия решений

Бень А.П., Терещенкова О.В. Применение комбинированных сетевых методов планирования в судоремонтной отрасли

Цмоць І. Г., Демида Б.А., Подольський М.Р. Методи проектування спеціалізованих комп’ютерних систем управління та обробки сигналів у реально-му час

Теленик С.Ф., РолікО.І., Букасов М.М., РимарР.В., Ролік К.О. Управління навантаженням і ресурсами центрів оброблення даних при виділених серверах

Селякова С. М. Структура інтелектуальної системи управління збиральною кампанією

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

Львов М.С. Алгоритм перевірки правильності границь змінення змінних у послідовних програмах

Ляшенко Е.Н. Анализ пожарной опасности сосновых насаждений в зоне Нижне-днепровских песков – самой большой пустыни в Европе

Кучеров Д.П., Копылова З.Н. Принципы построения интеллектуального автору-левого

Касаткина Н.В., Танянский С.С., Филатов В.А. Методы хранения и обработки нечетких данных в среде реляционных систем

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Применение когнитивного подхода для решения задачи поддержки принятия управленческих решений при ликвидации лесных пожаров

Гончаренко А.В. Моделювання впливу ентропії суб’єктивних переваг на прийняття рішень стосовно ремонту суднової енергетичної установки

Фарионова Н.А. Системный подход построения алгоритмов и моделей систем поддержки принятия решений при возникновении нештатных ситуаций

Биленко М.С., Серов А.В., Рожков С.А., Буглов О.А. Многоканальная система контроля качества текстильных материалов

Мотылев K.И., Михайлов M.В., Паслен В.В. Обработка избыточной траекторной информации в измерительно-вычислительных системах

Гончаренко А.В. Вплив суб’єктивних переваг на показники роботи суднової енергетичної установки

Гульовата Х.Г., Цмоць І.Г., Пелешко Д.Д. Архітектура автоматизованої системи моніторингу і дослідження характеристик мінеральних вод

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

ПотапенкоЕ.М., Казурова А.Е. Высокоточное управление упругой электромеханической системой с нелинейным трением.

Кузьменко А.С., Коломіц Г.В., Сушенцев О.О. Результати розробки методу еквівалентування функціональних особливостей fuzzy-контролерів

Кравчук А. Ф., Ладанюк А.П., Прокопенко Ю.В. Алгоритм ситуационного управления процессом кристаллизации сахара в вакуум-аппарате периодического действия с механическим циркулятором

Абрамов Г.С., Иванов П.И., Купавский И.С., Павленко И.Г. Разработка навигационного комплекса для автоматического наведения на цель системы груз-управляемый парашют

Литвиненко В.И., Четырин С.П. Компенсация ошибок оператора в контуре управления следящей системы на основе синтезируемых вейвелет-сетей

Бардачев Ю.Н., Дидык А.А. Использование положений теории опасности в искусственных иммунных системах

Рожков С.О., Кузьміна Т.О., Валько П.М. Інформаційна база як основа для створення асортименту лляних виробів.

Ускач А.Ф., Становский А.Л., Носов П.С. Разработка модели автоматизированной системы управления учебным процессом

Мазурок Т.Л., Тодорцев Ю.К. Актуальные направления интеллектуализации системы управления процессом обучения.

Ускач А.Ф., Гогунский В.Д., Яковенко А.Е. Модели задачи распределения в теории расписания.

Сідлецький В.М., Ельперін І.В., Ладанюк А.П. Розробка алгоритмів підсистеми підтримки прийняття рішень для контролю якості роботи дифузійного відділення.

Пономаренко Л.А., Меликов А.З., Нагиев Ф.Н. Анализ системы обслуживания с различными уровнями пространственных и временных приоритетов.

Коршевнюк Л.О. Застосування комітетами експертів системи нечіткого логічного виводу із зваженою істинністю.. – С. 73 – 79.

Кирюшатова Т.Г., Григорова А.А Влияние направленности отдельных операторов и направленности всей группы на конечный результат выполнения поставленной задачи.

Петрушенко А.М., Хохлов В.А., Петрушенко І.А. Про підключення до мови САА/Д деяких засобів паралельного програмування пакету МРІСН.

Ходаков В.Е., Граб М.В., Ляшенко Е.Н. Структура и принципы функционирования системы поддержки принятия решений при ликвидации лесных пожаров на базе новых геоинформационных технологий.

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

Нагорный Ю.И. Решение задачи автоматизированного расчета надежности иасуп с использованием модифицированного метода вероятностной логики

Козак Ю.А. Колчин Р.В. Модель информационного обмена в автоматизированной системе управления запасами материальных ресурсов в двухуровневой логистической системе

Гожий А.П., Коваленко И.И. Системные технологии генерации и анализа сценариев

Вайсман В.А., Гогунский В.Д., Руденко С.В. Формирование структур организационного управления проектами

Бараненко Р.В., Шаганян С.М., Дячук М.В. Аналіз алгоритмів взаємних виключень критичних інтервалів процесів у розподілених системах

Бабенко Н.И., Бабичев С.А. Яблуновская Ю.А. Автоматизированная информационная система управления учебным заведением

Яковенко А.Е. Проектирование автоматизированных систем принятия решений в условиях адаптивного обучения с учетом требований болонского процесса

Бараненко Р.В Лінеаризація шкали і збільшення діапазону вимірювання ємностей резонансних вимірювачів

Головащенко Н.В. Математичні характеристики шумоподібно кодованих сиг-налів.

Шерстюк В.Г. Формальная модель гибридной сценарно-прецедентной СППР.

Шекета В.І. Застосування процедури Append при аналізі абстрактних типів даних модифікаційних запитів.

Цмоць І.Г. Алгоритми та матричні НВІС-структури пристроїв ділення для комп'-ютерних систем реального часу.

Кухаренко С.В., Балтовский А.А. Решение задачи календарного планирования с использованием эвристических алгоритмов.

Нестеренко С.А., Бадр Яароб, Шапорин Р.О. Метод расчета сетевых транзакций абонентов локальных компьютерных сетей.

Григорова А.А., Чёрный С. Г. Формирование современной информационно-аналитической системы для поддержки принятия решений.

Шаганян С.Н., Бараненко Р.В. Реализация взаимных исключений критических интервалов как одного из видов синхронизации доступа процессов к ресурсам в ЭВМ

Орлов В.В. Оценка мощности случайного сигнала на основе корреляционной пространственной обработки

Коджа Т.И., Гогунский В.Д. Эффективность применения методов нечеткой логики в тестировании.

Головащенко Н.В., Боярчук В.П. Аппаратурный состав для улучшения свойств трактов приёма – передачи информации в системах промышленной автоматики.