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 совместимых машин и обладает способностью самонастройки под архитектуру. Персональные данные каждого пользователя сохраняются в защищенной базе данных.
Требования к техническим средствам : IBM PC/XT/AT, MS DOS не ниже 3.0, видео-адаптер VGA (EGA, Hercules, SVGA, MDA). Объем комплекса: 127 Кбайт.
Программный комплекс разработан на кафедре ВТ ТРТУ по программе "Перспективные информационные технологии" (подпрограмма" Информатика") Государственного Комитета Российской Федерации по высшему образованию.
4. ОРГАНИЗАЦИЯ ГЛОБАЛЬНЫХ СЕТЕЙ В РАМКАХ СТАНДАРТА ISO
4.1. Вводная лабораторная работа.
OSI - многоуровневая организация глобальных сетей
5. ПРОЕКТИРОВАНИЕ ГЛОБАЛЬНЫХ СЕТЕЙ
5.1. Лабораторная работа N 1.
Синтез глобальной сети радиальной структуры
Цель работы
Ознакомление с методами анализа и синтеза централизованных информационных сетей.
Исходные данные и задание к работе
Заданы места расположения источников информации, интенсивности запросов к центру обработки информации. Каждый узел-концентратор обслуживает сообщения терминалов, связанных с ним (в кружке каждого города выводится число терминалов). Будем полагать, что все терминалы генерируют одинаковый поток сообщений. Интенсивность и средняя длина сообщений одного терминала выводится в окне "Terminal params".
Необходимо оптимизировать структуру сети (выбрать местоположение центрального узла и пропускные способности линий связи). При выборе центрального узла сети использовать алгоритм "центр масс". Критерий оптимизации задается преподавателем.
Исходные данные генерируются ПЛК NET_LAB индивидуально для каждого студента (либо бригады) и выводятся на экран.
Теоретическое введение к работе
Рассмотрим алгоритм построения информационной сети звездообразной структуры - "центр масс". Исходными данными являются:
- множество мест расположения на заданной территории абонентских пунктов А{i}, где i=1,...,N;
- матрица пропускных способностей каналов связи С=7220с4ij7220;
- матрица стоимости линий связи S=7220s4ij7220.
При построении сети абонентские пункты подключаются к концентраторам, либо непосредственно к единственному центру сети. На первом этапе задача упрощается путем группирования абонентских пунктов и замены каждой группы терминалов эквивалентным узлом, расположенным в центре масс и имеющим вес, пропорциональный количеству абонентских пунктов в группе. При этом вес нового центра масс W=W4i0+W4j0, где W4i0 и W4j0 - соответственно веса узлов A4i0 и A4j0. В качестве веса любого узла может использоваться количество терминалов или суммарный поток сообщений, генерируемый этим узлом ко всем остальным узлам сети. Координаты нового центра масс вычисляются как
где X4i0, X4i0, X4j0, Y4j0 - декартовые или географические координаты узлов сети A4i0 и A4j0 соответственно.
Процесс группирования начинается с выбора ближайшей пары абонентских пунктов, которая затем заменяется одним пунктом с весом, пропорциональным двум абонентским пунктам, и расположенном в "центре масс" исходных двух узлов, далее выбирается ближайший к данному "центру масс" абонентский пункт и определяется новый "центр масс" с учетом весов абонентских пунктов и т.д. Размер группы ограничен пропускной способностью концентратора. Определенный таким образом "центр масс" является местом расположения концентратора, либо концентратор размещается в ближайшем к "центру масс" допустимом месте расположения.
На втором этапе работа осуществляется на множестве узлов, являющихся "центрами масс" групп, с весами, пропорциональными количеству объединенных в группы абонентских пунктов. Полученный таким образом "центр масс" является пунктом, в котором целесообразно разместить обрабатывающий центр информационной сети.
В лабораторной работе процесс построения сети начинается со второго этапа. При этом число абонентских пунктов, присоединенных к узлу-концентратору, указано в кружке каждого города. Интенсивность и средняя длина сообщений одного терминала выводится в окне "Terminal params".
В качестве модели канала информационной сети принята система массового обслуживания М/М/1. Среднее время задержки сообщения в канале с номером i вычисляется как: где: 1/7m4i0 - средняя длина сообщения (бит/сообщение), c4i0 - пропускная способность этого канала (бит/сек.),
7l4i0 - интенсивность потока сообщений (сообщений/сек.)
в этом канале.
Очевидно, что нагрузка на канал должна быть меньше его пропускной способности.
Среднее время задержки для всей сети вычисляется как:
где 7l4ij0 - интенсивность обмена между i-м и j-м узлом сети,
n - число узлов в сети.
Стоимость канала зависит от пропускной способности и длины, и может быть представлена как
S4j0 = V(c4j0) + S(c4j0)770l4j0 ,
где l4j0 - длина канала,
V(c4j0) - постоянная составляющая,
S(c4j0) - переменная составляющая.
Стоимость сети определяется как сумма всех S4j0.
Порядок выполнения работы
Путем выбора центра радиальной сети и подбором пропускных способностей каналов студент должен найти оптимальную конфигурацию.
На первом этапе на основе алгоритма "центр масс" с учетом числа терминалов в каждом пункте проектируемой сети (указано в кружке, соответствующем пункту (городу) сети) и расстояний между пунктами определяется местоположение центра сети. Центр сети выбирается в окне меню "Set net center". На экране центр сети помечен квадратом.
Расчет требуемых пропускных способностей каналов связи производится с учетом передаваемых по каналам потоков информации (исходя из интенсивности потока от одного терминала, числа терминалов, средней длины сообщений). Пропускная способность канала задается в окне меню "Channel params". Перебор каналов осуществляется опцией меню "Select channel". Выбранный канал помечен темным квадратом, параметры канала отображаются в окне Channel status.