Г) Найдем T

Расчетная работа №4

Тема: Задачи оптимизации компьютерных сетей

Вариант 18

Дисциплина: Методы оптимизации

 

 

Выполнила студентка гр. 5172/10 _______________ Пономарева Н.Н.

^{(подпись)}

Преподаватель _______________ Сиднев А.Г.

^{(подпись)}

«__» _______ 2012г.

 

Санкт-Петербург

 

Задание 5.16, вариант 18:

Рассмотрите идеализированную сеть связи с N = 4 узлами, для которой справедлива простая модель с M/M/1. Предполагается, что μ = 1, а матрица трафика (γ_jk) и матрица маршрутов (r_ij) (где r_ij – номер следующего узла, в который должно быть передано сообщение, если сейчас оно находится в узле j и окончательно адресовано узлу i) имеют вид:

=> модифицированная матрица траффика

а) Найдите среднюю длину пути .

б) Пусть задана полная пропускная способность . Найдите пропускные способности {C_i}, которые минимизируют среднюю задержку сообщения T.

в) Изобразите сеть, снабдите каждое ребро стрелкой и парой (λ_i, C_i).

г) Найдите T.

д) Найдите все кратчайшие маршруты (9 штук) из узла в узел, используя один из следующих подходов:

– применение алгоритма Флойда, дополненного процедурой сбора и правильной расстановки транзитных узлов;

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

– применение любого другого алгоритма, решающего эту же задачу с кратким пояснением и указанием источника.

е) Пусть сделан пропорциональный выбор пропускных способностей. Найдите {C_i} и T и проведите сравнение с результатами п. d.

 

Решение:

а) Вычислим среднюю длину пути:

Средняя длина пути вычисляется согласно формуле:

где – длина пути , где под длиной понимается число каналов в пути, γ – сумма всех элементов матрицы трафика;

С помощью матрицы маршрутов построим сеть:

Рис.1. Граф сети

На рисунке также пронумерованы все возможные каналы (№№1-9)

По заданной матрице маршрутов составим таблицу: начальный-конечный узел пути, подробный маршрут, длина пути.

 

Таблица 1. Пути в сети.

Начальный узел пути	Конечный узел пути	Маршрут	Длина пути	Проходимые каналы по заданному маршруту
		-		-
		1-3-4-2		6-5-4
		1-2-3		1-9
		1-3-2-4		6-8-3
		2-1
		-		-
		2-3
		2-4
		3-4-2-1		5-4-2
		3-4-2		5-4
		-		-
		3-2-4		8-3
		4-2-1		4-2
		4-2
		4-1-2-3		7-1-9
		-		-

 

Т.о. матрица

Матрица трафика

>> y = [0 2 1 2; 1 0 1 1; 1 1 0 1; 1 1 1 0];

Матрица длин путей

>> n = [0 3 2 3; 1 0 1 1; 3 2 0 2; 2 1 3 0];

Матрицы поэлементно перемножим

>> y_n = y.*n

 

y_n =

 

0 6 2 6

1 0 1 1

3 2 0 2

2 1 3 0

Просуммируем элементы матрицы y_n и делим на сумму всех элементов матрицы траффика:

>> n_ = (sum(sum(y_n)))/(sum(sum(y)))

 

n_ =

 

2.1429

 

Ответ:

 

 

б) Вычислим пропускные способности , которые минимизируют среднюю задержку сообщения T

 

 

Полная пропускная способность задана .

Данная задача – задача ВПС.

 

Запишем выведенную формулу для данного класса задач:

где – средняя длина пути, – коэффициент загрузки (отношение внешнего траффика в битах от суммарной пропускной способности).

 

 

 

 

Используем для расчетов Mathlab:

>> a_i = [(y(1,3)+y(4,3));

(y(2,1)+y(3,1)+y(4,1));

(y(1,4)+y(3,4));

(y(1,2)+y(3,1)+y(3,2)+y(4,1)+y(4,2));

(y(1,2)+y(3,1)+y(3,2));

(y(1,2)+y(1,4));

(y(4,3));

(y(1,4)+y(3,4));

(y(2,3)+y(4,3));]

 

a_i =

 

 

Полная пропускная способность

>> C = 32;

Средняя длина пути, найденная в пункте а

>> n_ = 2.1429;

Проверка соответствия

>> n_*((sum(sum(y)))/C)

 

ans =

 

0.8824

Расчет пропускных способностей

>> C_i = a_i + C*(1-n_*((sum(sum(y)))/C))*(a_i.^0.5)/sum(a_i.^0.5)

 

C_i =

 

2.3656

3.4477

3.4477

6.6332

4.5170

4.5170

1.2585

3.4477

2.3656

 

 

в) Изобразим сеть, указав над каждым каналом

 

г) Найдем T

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

>> T = n_*(sum((a_i/(sum(a_i))).^0.5)^2)/(C*(1-n_*(sum(sum(y)))/C))

T =

 

4.5813

Д) Найдем все кратчайшие маршруты (9 штук) из узла в узел, с применением алгоритма перечисления путей из узла в узел, предполагающего возведение в степень булевой примитивной матрицы.

Длины каналов:

Данный алгоритм будет наиболее простым в применении, т.к. размерность матриц 4х4, а алгоритм предполагает возведение в степень , т.е. .

.

Алгоритм предполагает возведение в степень матрицы, пока не будет выполнено условие:

Составим матрицу Q по графу сети.

 

- матрица полных связей. По ней возможно отследить все возможные маршруты между узлами.

Матрица кратчайших маршрутов: