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

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

Используется два подхода к выбору критериев оптимизации:

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

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

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

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

Требования к передаваемым потокам сообщений в большинстве случаев задаются в виде матрицы требований на передачу потоков (трафика) 7F0=722f4ij7220, где 7f4ij7 0- средняя интенсивность потока из узла a4i0, предназначенного узлу a4j0. Стоимости оборудования сети должны быть заданы для всех потенциальных линий связи в зависимости от их пропускной способности с4i0:

s4i0(с4i0), i = 1, 2, ., m, где s4i0(с4i0) - стоимость i-й линии связи

при ее пропускной способности с4i0; m - число линий связи.

Множество линий связи, соответствующее возможной топологии, обозначим B. Число линий связи при N узлах может доходить до N770(N-1)/2, если допустима любая связь между узлами.

Обозначим7 L0=(7l410,7l420, .,7l4m0) - вектор средней величины потока через линии связи при оптимальных маршрутах потоков сообщений, 7l4i0 - средний поток сообщений (информации) в i-линии. Такой вектор 7L0 называется многопродуктовым потоком. Он является результатом суммирования однопродуктовых потоков:

где 7l0 - поток от узла a4j0 к узлу a4k0, направляемый

5i0 по i-й линии связи.

Матрица 7F0 и способ выбора путей передачи информации (маршрутов) однозначно определяют вектор 7L0.

Обозначим также C=(c410,c420, .,c4m0) - вектор пропускных способностей линий связи, T - средняя величина задержки передачи, [T] - максимально допустимая величина средней задержки. Тогда задача выбора топологии ГИВС может быть сформулирована так:

- заданы расположение источников и получателей информации сети, матрица требований на передачу потоков Ф, функции затрат s4i0(с4i0) для всех потенциальных линий связи; m

- требуется минимизировать S(B,C)=7S0 s4i0(с4i0)5,0 5i=1

где B - множество линий связи мощностью m, соответствующих возможной топологии, при условиях 7L , 0C,7 0T7 ,0 [T]. Под мощностью будем понимать число реальных (проводных) линий связи в канале связи.

Кроме того, обычно накладываются некоторые ограничения на множество B. Например, можно учесть надежностные требования, поставив ограничение, чтобы сеть была двусвязной (чтобы между любой парой узлов было не менее двух независимых путей) или трехсвязной. Если не накладывать ограничений на множество B, то полученная топологическая структура, очевидно, будет в классе деревьев.

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

2. НАЗНАЧЕНИЕ И ТЕХНИЧЕСКАЯ РЕАЛИЗАЦИЯ ПРОГРАММНОГО

ЛАБОРАТОРНОГО КОМПЛЕКСА NET_LAB

В ходе выполнения лабораторных работ для облегчения этапа проектирования структуры ГИВС используется программный лабораторный комплекс (ПЛК) NET_LAB.

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

Основные функциональные возможности: в диалоговом режиме ПЛК представляет пользователю возможность для построения и исследования радиальных, древовидных и распределенных информационно-вычислительных сетей.

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

текущее состояние работы. Таким образом, студент может выполнить работы за несколько сеансов без потери каких-либо результатов.

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

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