Основные подходы к выбору структуры информационно-вычислительной сети и оптимизации ее параметров

Лабораторная  работа №4

 

«Основные подходы к выбору структуры информационно-вычислительной сети

 и оптимизации  ее параметров.»

 

Цель работы: Освоить основные подходы выбора структуры информационно-вычислительной сети на основе оптимизации ее параметров.

 

Теоретические основы

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

Каждой вершине может  приписываться некоторый набор чисел:

• пропускная  способность  узла, 
• стоимость узла и т.п. 

Каждое ребро может  иметь вес в виде набора чисел: 

• длины линии,
• пропускной способности,
• стоимости и т.п.

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

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

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

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

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

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

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

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

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

Простейший  пример оптимизации отдельного критерия ВС, представляет собой решение сетевой  транспортной задачи методом Форда.

 

1. Постановка сетевой  транспортной задачи.

На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого – транспортные магистрали, а узлы – пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P₁,P₂,...,P_n, причем некоторые упорядоченные пары (P_i,P_j) пунктов назначения соединены дугами заданной длины r(P_i,P_j)=l_ij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.

На рис.1 построена  ориентированная транспортная сеть, содержащая шесть пунктов P₁,P₂,...,P₆, которые связаны между собой восьмью транспортными путями.

Необходимо  определить кратчайший маршрут из пункта P₁ в P₆. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.

Например маршрут из пункта P₁ в пункт P₆: P₁P₂P₄P₆; L=l₁₂+l₂₄+l₄₆=10.

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

 

2. Описание метода и алгоритма  решения.

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

Алгоритм метода Форда  содержит четыре этапа. На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры l_i и l_j по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р₁ в любой другой пункт назначения Р_j, j=1,2,...,n.

Рассмотрим подробнее  каждый из этих четырех этапов.

 

2.1 Первый этап: Составление исходной таблицы расстояний.

Данная таблица содержит n+1 строк и такое же количество столбцов; P_i – пункты отправления; P_j – пункты назначения. Во второй строке и втором столбце проставляется значения параметров l_i и l_j, определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний l_ij из i-го пункта в j-й пункт. Причем заполняются клетки таблицы, лежащие выше главной диагонали. Если пункт P_i не соединен отрезком пути с пунктом P_j, то соответствующая клетка таблицы не заполняется.

 

2.2 Второй этап: Определение l_i и l_j.

Определяется значение параметров в соответствии с формулой:

 

l_j=min(l_i+l_ij);  i=1,2,...,n; j=1,2,...,n,              (1)

 

где l₁=0.

Эти значения заполняются во второй строке и во втором столбце.

 

2.3 Третий этап: Определение  длины кратчайших путей.

Возможны два случая определения длины кратчайших путей  из пунктов P_i в пункты P_j, i=1,2,...,n; j=1,2,...,n.

В первом случае, если выполняются  неравенство:

 

l_j – l_i £ l_ij; l_ij¹0; j=1,2,...,n; j=1,2,...,n,          (2)

 

то значения параметров l₁,...,l_n удовлетворяют условиям оптимальности. Каждое значение l_j есть не что иное, как кратчайшее расстояние от пункта P_i до пункта P_j, j=2,3,...,n.

Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:

 

l_j – l_i > l_ij; i=1,...,n; j=1,...,n,                         (3)

 

то значения l_j и l_i могут быть уменьшены.

Если справедливо (3), тогда  исправим значение l_j0, пересчитав его по формуле:

 

l¢_j0=l_i0+l_i0,j0.                                                  (4)

 

2.4 Четвертый этап: Нахождение  кратчайшего пути.

Определения последовательности пунктов кратчайшего маршрута. С  этой целью для каждого столбца  определяют величину:

 

lr_j,r_i = lr_j – lr_i,                                                  (5)

 

где lr_j,r_i (i=2..n) берется из таблицы, причем lr_i выбирается так, чтобы выполнилось равенство (5). Таким образом, определим r_i. Далее продолжим ту же операцию, но будем считать, последней не P_n, а P_r1. Будем продолжать до тех пор, пока r_n не станет равной 1.

Таким образом, кратчайший маршрут проходит через P_r1,P_r2,...,Pr_n, а длина маршрута L_min=lr_2,r₁+lr_3,r₂+...+lr_n,r_n-1.

 

Практическая  часть

Для варианта 9 и 13 построим обобщенный критерий оптимальности  прокладки вычислительной сети

(топология сети представлена  на рис.1).

Критерий\№ дуги	1	2	3	4	5	6	7	8
Стоимость	1000	2000	900	2500	1000	1500	1200	2000
Вероятность отказа	0,1	0,15	0,2	0,17	0,11	0,1	0,1	0,1
Их произведение	100	300	180	425	110	150	120	200

 

1. Построим исходную  таблицу для произведения критериев  оптимальности для графа (рис.1)

 

Pi\Pj	1	2	3	4	5	6
1	X	100	300
2		X		180	425
3			X	110	150
4				X		120
5					X	200
6						X

2. Определим значения  параметров λ  

заполним таблицу с учетом рассчитанных коэффициентов

 

Pi\Pj	1	2	3	4	5	6
1	X	100	300	280	450	400
2	100	X		180	425
3	300		X	110	150
4	280			X		120
5	450				X	200
6	400					X

 

3. Определим длины  кратчайших путей. Знаком «+»  будем обозначать неравенство удовлетворяющее (2), а знаком «-» - неравенство удовлетворяющее (3).

 

Как видно, полученные    удовлетворяют условиям оптимальности.

 

4. Нахождение кратчайшего  пути.

У нас  =6, а значит . По формуле (5) найдем остальные и определим кратчайшее расстояние.

Это равенство выполняется при  . На самом деле:

Также равенству (5) удовлетворяют  и . Таки м образом кратчайший путь равен:

 

 

Рассчитаем все возможные значения маршрутов прокладки вычислительной сети, определим наилучший и сравним  его с полученным результатом.

 

 

Результат совпадает  с полученным ранее.

 

 

 

 

 

 

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