Разработка моделей и алгоритмов размещения информационных ресурсов в корпоративных сетях

Актуальность темы

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

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

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

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

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

2. анализ топологий сетей и проектирование топологий по заданному среднему расстоянию.

Основные задачи. В работе поставлены и решены следующие основные задачи:

— исследование существующих способов описания и построения топологий информационно-вычислительных сетей и многопроцессорных систем, способов размещения на них информационных ресурсов;

— обоснование использование суммарного потока как критерия при оптимизации размещения информационных ресурсов;

— размещение одного и множества информационных ресурсов в сети по критерию минимума суммарного потока без ограничений и при существовании количественных и структурных ограничений;

— размещение информационных ресурсов при возможности их копирования;

— размещение информационных ресурсов, минимизирующее суммарный поток на заданном подмножестве линий связи;

— исследование влияния топологических характеристик сети, в частности среднего расстояния, на функционирование сети;

— анализ сетей с малыми диаметрами и построение сетей с диаметром 2 по заданному среднему расстоянию;

— определение точек соединения сетей подразделений для получения объединенной корпоративной сети с минимальным средним расстоянием.

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

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

— предложены алгоритмы размещения информационных ресурсов в корпоративных сетях по критерию минимума суммарного потока в линиях связи;

— предложены алгоритмы размещения информационных ресурсов в корпоративных сетях по критерию минимума суммарного потока на произвольном подмножестве линий связи;

— сформулирована и решена обобщенная задача о назначениях;

— разработан алгоритм растущей функции для решения задачи минимизации линейной формы на бинарных матрицах, имеющих ограничения на структуру;

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

— предложен алгоритм синтеза сетей с диаметром 2 по заданному среднему расстоянию;

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

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

Практическая ценность работы. Результаты, полученные в диссертационной работе, внедрены и использованы при размещении информационных ресурсов в сети Рязанской государственной радиотехнической академии, в ФГУП ОКБ «Спектр» (г. Рязань) при разработке корпоративной сети УВД Рязанской области, используются в учебном процессе РГРТА. Полученные результаты использованы при проведении следующих научно-исследовательских работ: «Разработка проекта программы развития единой образовательной среды Рязанской области» в рамках программы «Государственная поддержка региональной научно-технической политики высшей школы и развитие ее научного потенциала" — «Разработка программы развития единой информационной среды сферы образования Рязанской области на 2001 — 2005 гг." — «Разработка методологии личностно-ориентированных моделей знаний для создания тестовых интернет-систем в образовании «.

Апробация результатов диссертации. Результаты, полученные при работе над диссертацией, докладывались на 35 научно-технической конференции РГРТА, Рязань, 2−6 февраля 1998 г.- 10-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 14−16 ноября 2001 г.- Четвертой Всероссийской научной конференции с международным участием молодых ученых и аспирантов, Таганрог, ноябрь 2001 г.- Четвертой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.8 Выводы.

В главе получены следующие результаты:

1. показано влияние среднего расстояния на параметры сети;

2. проведен анализ сетей с диаметром В=2, в результате которого определена сеть с наибольшим средним расстоянием, получено численное значение максимального среднего расстояния;

3. разработаны алгоритмы синтеза графов с Б=2 по заданному среднему расстоянию;

4. проведен анализ сетей с Э=3, в результате которого определен класс сетей с максимальным средним расстоянием и получено численное значение максимального среднего расстояния;

5. проведена оценка количества добавляемых ребер в произвольный граф для достижения требуемого среднего расстояния;

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

7. проведен анализ топологий многопроцессорных систем с точки зрения среднего расстояния.

102 Глава 4.

Экспериментальная проверка результатов.

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

1. оптимизируют суммарный поток либо во всей сети, либо на выбранном подмножестве ребер сети;

2. уменьшают (как правило) среднее время доступа к информационным ресурсам.

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

4.1 Проведение эксперимента на физической модели.

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

1 2.

Рис. 1. Структура подсети, используемой для проведения эксперимента.

Для проведения эксперимента использовался файл размером 541 808К, который одновременно копировался в компьютеры, обозначенные на рисунке 1 номерами 1, 2, 8, 9, 10 с двух возможных мест расположения, обозначенных на рисунке 1 — 3 и 4.

В таблице 1 представлены полученные результаты.

Заключение

.

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

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

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

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

4. Разработаны алгоритмы определения возможности построения сетей с заданным средним расстоянием и диаметром и способов построения таких сетей.

5. Проведен эксперимент с физической моделью и вычислительный эксперимент с имитационной моделью, подтверждающий достоверность полученных результатов. Результаты, полученные при выполнении диссертационной работы, использованы при проведении 3 научно-исследовательских работ.