8. Методы анализа сетевых структур информационных систем

8.1 Особенности информационных сетей

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

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

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

Особенности информационных сетей заключаются в следующем:

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

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

3. Методы обслуживания абонентов разнообразные: от предоставления приборов сети в кратковременную аренду до выполнения по их заказам определенных преобразований информации.

4. пользователи (абоненты) сети конкурируют друг с другом в различные моменты времени за право использования услуг.

5. Пользователи и приборы обслуживания распределены в пространстве.

6. Случайный характер возникновения потребностей в обслуживании у абонентов.

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

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

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

1. Структурой (число узлов, их расположение, число ветвей, связывающих узлы).

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

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

4. Надежностью и живучестью узлов и ветвей.

5. Информационной безопасностью.

6. Экономическими затратами на строительство и

эксплуатацию.

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

• некоммутируемые;

• коммутируемые;

• с коммутацией сообщений.

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

В коммутируемых сетях на узлах имеются устройства коммутации (УК) для оперативного переключения каналов.

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

Структуры сетей могут быть различные. Различают:

1. Топологические структуры.

2. Функциональные структуры.

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

Для повышения живучести и надежности сетей иногда используются решетчатые структуры. В них в узлах решетки организуются опорные узлы (У I) - узлы высшего ранга. К ним (к одному или двум) подключаются узлы - концентраторы (У II), к которым подходят абонентские линии.

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

Предусматривается система управления сетью. Она предназначена для:

• сбора информации о состоянии элементов сети;

• определения работоспособности системы;

• принятия мер по поддержанию в допустимых пределах характеристик сети;

Рассмотрим метод построения дерева путей на примере сети, представленной на рис 8.2 для двух узлов: узла 2 и узла 1.

Рис.8.2

Матрица связности этой сети:

Строим дерево путей для узла 2 по рис 8.3. Для этого выписываем узел 2 и определяем узлы 1-го яруса. Это будут узлы 1,3 и 4.

3 ярус

1 ярус

5

5

5

4

5

4

1

1

5

2

2 ярус

3

3

3

1

4

Ядро

4

Рис. 8.3

Они видны из рис. 8.2, проще пользоваться матрицей связности . Узлы 1-го яруса определяются по 2-ой строке этой матрицы (т.к. строится дерево путей для 2-го яруса). Учитываются те узлы, которые в матрице по 2-ой строке отмечены единицами. Узлы 2-го яруса находим аналогично, но с учетом, что:

1. исходными являются узлы 1-го яруса (1,3 и 4) и соответственно должны будем использовать 1,3 и 4 строки матрицы ;

2. исключаются узлы, для которых были образованы подмножества узлов в предыдущем ярусе (т.е. узел 2);

Тогда 2-ой ярус будет иметь узлы: 5-ый от 1-го; 4-ый и 5-ый от 3-го; 3-ий и 5-ый от 4-го узлов.

Узлы 3-го яруса находим аналогично: для 5-го – по пятой строке матрицы имеем «1» на 1,3 и 4. Но с 1 связь есть предыдущая. Остаются узлы 3 и 4. Для 4-го по четвертой строке имеем «1» на позициях 2,3 и 5. Для узлов 2 и 3 были уже образованы подмножества раньше. Остается узел 5. Для 5-го имеем 1,3 и 4. Но 3 было раньше. Остаются узлы 1 и 4. Для 3-го имеем единицы по третьей строке в 2,4 и 5 столбцах. Но 2 и 4 было. Остается узел 5. Наконец, для 5-го единицами отмечены позиции 1,3 и 4. Ранее было 4. Остаются узлы 1 и 3.

Построение дерева путей продолжается до h-го яруса, где h- максимально допустимое число переприемных участков в пути.

Аналогично могли бы построить дерево путей для узла 1 (см. рис. 8.4)

3 ярус

Ядро

2 ярус

4

1 ярус

3

5

2

4

2

4

3

3

3

4

2

1

Рис. 8.4

Интерес представляет машинный алгоритм построения дерева путей для произвольного к-го узла:

1. Отмечаем узел К и выбираем к-ую строку матрицы .

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

3. Образуем подмножества узлов r-го яруса (r=2,3,…,h), где h- максимально допустимое число переприемных участков пути:

а)поочередно выбираем узлы (r-1)-го яруса;

б)для каждого узла i в (r-1)-ом ярусе выбираем i-ю строку в матрице и выписываем номера столбцов с ;

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

4. Построение дерева путей продолжается до h-го яруса.

По дереву путей легко проследить пути от заданного узла к другим. Перечень путей между узлами удобно записать в виде таблице путей размера k  m, где k – число путей, а m- число ветвей сети. Пусть, например, h  3 пути между узлами 2 и 5 будут (рис. 5.2)

M₂₅={2,1,5; 2,3,5; 2,4,5; 2,3,4,5; 2,4,3,5}

Эти данные занесены в табл. 7.1. В ней каждый столбец соответствует ветви , а каждая строка – одному пути. Элемент таблицы , если ветвь принадлежит пути , и в противном случае. Для упрощения записей случаи в таблицу не заносятся.

Таблица 7.1.

	1	1
			1			1
				1			1
			1		1		1
				1	1	1

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

Общая математическая постановка задачи о кратчайшем пути:

минимизировать

где i, j – номера узлов:

- длина (стоимость, время, живучесть и т.д.) пути;

= 1, если i-ый узел связан с j-ым узлом, а в остальных случаях = 0;

при ограничениях

для всех (i,j)  сети.

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

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

при следующих ограничениях:

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

2. суммарная емкость путей между произвольной парой (k, l) узлов должна быть равна числу каналов , которые обеспечат требуемое качество обслуживания;

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

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