Методические указания к лабораторным работам по дисциплине "Распределенные информационно-вычислительные сети. Лабораторный практикум. /Составители: В.Ф. Гузик, В.Н. Решетняк, В.Г. Сидоренко, Б.И. Левин (ТРТУ), В.П. Ильин, В.К. Шмидт, Н.А. Буренев (СПбГЭТУ). - Таганрог, ТРТУ, 1995. - _с.

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

1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОДХОДЫ К ВЫБОРУ СТРУКТУРЫ

ГЛОБАЛЬНОЙ ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНОЙ СЕТИ

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

ли структуры сети наиболее часто используются графовые модели. Граф G(A,B) имеет множество вершин a4ij7eA0, соответствующих пунктам сети, и множество дуг (ребер) b4ij7e0B - линий связи между a4i0 и a4j0. Каждой вершине может приписываться некоторый набор чисел: пропускная способность узла c4i0, стоимость узла s4i0 и т.п. Каждое ребро может иметь вес в виде набора чисел: длины линии l4ij0, пропускной способности c4ij0, стоимости s4ij0 и т.п.

Для записи структуры сети и количественных оценок ее элементов используют следующие матрицы:

1. Матрица связности (смежности) G=7220g4ij7220, где g4ij0=1, если есть ребро, связывающее вершину a4i0 с вершиной a4j0, и g4ij0=0, если ребро отсутствует.

2. Матрица длин ребер (каналов связи) L=7220l4ij7220, где l4ij - расстояние от пункта a4i0 до пункта a4j0.

3. Матрица пропускных способностей (емкостей) ребер С=7220с4ij7220, где с4ij0 - максимальное число бит в секунду, которое может быть пропущено по ребру b4ij0.

4. Матрица стоимости S=7220s4ij7220, где s4ij0 - стоимость ребра между пунктами a4i0 ди a4j0

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

Путь7 m4st0 из узла a4s0 в узел a4t0 - упорядоченная последовательность ребер, начинающаяся в a4s 0и оканчивающаяся в a4t0, не проходящая дважды через один и тот4 0же узел.4 0Путь4,0 намеченный для доставки сообщений между заданной парой узлов, называется м а р ш р у т о м, а процесс установления таких маршрутов -

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

Пропускная способность пути определяется наиболее узким местом - минимальной пропускной способностью ребер, образующих путь. С в я з н о с т ь ю сети называется минимальное число независимых путей между любой парой узлов. С е ч е н и е сети - неизбыточная совокупность ребер, которые надо изъять из сети, чтобы нарушилась ее связность. Сечениями 7s4st 0по отношению к узлам a4s0 и a4t0 называются такие сечения, при которых эти узлы

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

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

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

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

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

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

к надежности задаются обычно в виде требования k-связности. Число линий связи, их длина и пропускные способности в значительной мере определяют стоимость всей сети. Для радиальной и последовательной (цепочечной) структуры сети число линий связи N4c0=N-1, для кольцевой N4c0=N, для полносвязной N4c0=N770(N-1)/2, где N - общее количество пунктов сети. Полносвязная структура является наиболее надежной и живучей, но наименее экономичной. С увеличением размерности сети, а, следовательно, и с увеличением объемов информации целесообразен переход к иерархическим сетям. На нижних уровнях иерархии повышение эффективности использования линий связи достигается применением концентраторов.

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