Модели оптимального размещения файлов в вычислительной сети
Модели оптимального размещения файлов в
вычислительной сети
Модели оптимального размещения файлов в
вычислительной сети со звездообразной топологией
Задача1
Вычислительная сеть состоит из трех узлов, среди
которых следует распределить семь файлов.
Обозначения:- вероятность того, что запрос,
инициированный в узле Кs, использует для своего обслуживания файл, находящийся
в локальной БД узла Кr.
Для определения общей средней задержки при
выполнении запроса в сети введем следующие величины:
li
- средняя интенсивность запросов, инициированных в узле Ki;
lik
- средняя интенсивность поступления запросов k-того
типа во входную сеть узла Ki.ik
- среднее время обработки запросов k-того
типа на узле Ki;2ik
- дисперсия времени обработки запроса k-того
типа на узле Ki;
l - средняя интенсивность входного потока
сообщений в коммутаторе данных;
m - средняя скорость обслуживания сообщений в
коммутаторе данных;
Тi
- среднее время обслуживания запроса, инициированного на узле Ki;
Т - общее
среднее время ответа на запрос по всей вычислительной системе.
Вероятности pij
(i = 1,2,3; j
= 1,2, … , 7):
P
|
F1
|
F2
|
F3
|
F4
|
F5
|
F6
|
F7
|
K1
|
0,05
|
0,3
|
0,15
|
0,25
|
0,1
|
0,06
|
0,09
|
K2
|
0,4
|
0,1
|
0,05
|
0,08
|
0,12
|
0,1
|
0,15
|
K3
|
0,15
|
0,07
|
0,4
|
0,03
|
0,1
|
0,15
|
0,1
|
Распределение фалов по узлам вычислительной сети
задано ниже:
X
|
K1
|
K2
|
K3
|
F1
|
0
|
1
|
0
|
F2
|
1
|
0
|
0
|
F3
|
0
|
0
|
1
|
F4
|
1
|
0
|
0
|
F5
|
1
|
0
|
0
|
F6
|
0
|
1
|
0
|
F7
|
0
|
1
|
0
|
Таблица значений qsr будет иметь вид:
q
|
K1
|
K2
|
K3
|
K1
|
0,65
|
0,2
|
0,15
|
K2
|
0,3
|
0,65
|
0,05
|
K3
|
0,2
|
0,4
|
0,4
|
Задали самостоятельно li
- среднюю интенсивность запросов, инициированных в узле Ki:
λ
|
Значение
|
λ1
|
2
|
λ2
|
3
|
λ3
|
2
|
Выполняем расчет средней интенсивности
поступления запросов k-того типа во входную сеть узла Ki и средней
интенсивности входного потока сообщений в коммутаторе данных по следующим
формулам:
li1
= 2li
(1 - qii)
li2 =
l = .
Результаты расчетов приведены ниже:
λi
|
λi1
|
λi2
|
|
|
1
|
1,4
|
2,6
|
|
|
2
|
2,1
|
3,15
|
|
|
3
|
2,4
|
1,25
|
λ
|
5,9
|
Среднее время обработки запросов k-того
типа на узле Ki
и дисперсия времени обработки запроса k-того
типа на узле Ki
приведены в таблицах:
W
Wi1 Wi2 1 0,3 0,17 2
0,25 0,13 3
0,35 0,1
|
W2
Wi1 Wi2 1 0,14 0,075 2
0,115 0,055 3
0,165 0,04
|
Средняя скорость обслуживания сообщений в
коммутаторе данных равна m=6.
Выполняем расчет значений Qi1
и Ri1, Qi2
и Ri2 -
времени ожидания и обслуживания заявок определенного типа и Q
и R - время ожидания и
обслуживания на коммутаторе по приведенным ниже формулам:
Qi1
= i1
= i2
= i2
= = =
Результаты расчетов приведены таблицах:
Qi
Qi1 Qi2 Q 1
0,05684 0,015648 10 2
0,057356 0,006452 3
0,03168 0,001249
|
Ri Ri1 Ri2 R 1
0,517241 0,293103 0,166667 2
0,242105 0,273684 3
2,1875 0,625
|
Выполняем подсчет суммы li
по формуле:
S = = 7
На основании полученных данных
выполняем расчет среднего времени обслуживания запроса соответствующего типа,
инициированного на узле Ki и общее
среднее время ответа на запрос по всей вычислительной системе с помощью формул
приведенных ниже:
Тil = 2Qi1 + 2Ri1 + 2Q + 2R + Qj2 + Rj2
Тi2 = Qi2 + Ri2
Т =
Результаты расчетов приведены ниже:
Ti
|
Ti1
|
Ti2
|
Т
|
1
|
21,63146
|
0,308751
|
22,07032
|
2
|
21,6949
|
0,280136
|
|
3
|
21,84405
|
0,626249
|
|
Задача2
Обозначения:
n
- число узлов вычислительной сети;
m
- число независимых файлов РБД;
Fj
-
j-й файл РБД;
Ki
-
i-й узел сети;
λi
-
средняя интенсивность запросов, инициированных в узле Ki;
Wik
- среднее время обработки запроса k-го
(k=1,2) типа в
узле Ki;
pik
- вероятность того, что для обслуживания, запроса, инициированного в узле Ki,
необходим файл Fj.
qsr
- вероятность того, что запрос, инициированный в узле Ks
использует для своего
обслуживания файл, находящийся в локальной базе
данных узла Kr;
λik
- средняя интенсивность поступления запросов k-го
(k=1,2) типа
во входную очередь
узла Ki.
Вычислительная сеть состоит из трех узлов K1,
K2,
K3,
а РБД содержит семь файлов F1,
F2,
…, F7.
А λi
(i = 1, 2, 3)
имеют значения: λ1
= 2, λ2
= 3, λ3
= 2, а величины pij
(i = 1, 2, 3; j
=
1, 2,..., 8) и Wik
(i = 1, 2, 3; k
= 1, 2) приведены в таблицах 1 и 2 соответственно:
табл.1
P
|
F1
|
F2
|
F3
|
F4
|
F5
|
F6
|
F7
|
K1
|
0,05
|
0,3
|
0,15
|
0,25
|
0,1
|
0,06
|
0,09
|
K2
|
0,4
|
0,1
|
0,05
|
0,08
|
0,12
|
0,1
|
0,15
|
K3
|
0,15
|
0,07
|
0,4
|
0,03
|
0,1
|
0,15
|
0,1
|
табл.2
Wi
|
W1
|
W2
|
1
|
0,001
|
0,6
|
2
|
0,21
|
0,18
|
3
|
0,28
|
0,2
|
Найдем оптимальное распределение файлов по узлам
вычислительной сети.
Используя формулу Qjs = , находим Qjs (j =1, 2,...,
8; s = 1, 2, 3).
Эти величины имеют значения:
вычислительная сеть
топология файл
Q
|
K1
|
K2
|
K3
|
MIN
|
F1
|
1,5
|
0,4
|
1,3
|
0,4
|
F2
|
0,44
|
0,74
|
0,9
|
0,44
|
F3
|
0,93
|
1,08
|
0,45
|
0,45
|
F4
|
0,3
|
0,56
|
0,74
|
0,3
|
F5
|
0,58
|
0,42
|
0,56
|
0,42
|
F6
|
0,6
|
0,42
|
0,42
|
0,42
|
F7
|
0,65
|
0,38
|
0,63
|
0,38
|
В соответствии с выбранными начальное
распределение будет иметь вид:
|
K1
|
K2
|
K3
|
F1
|
0
|
1
|
0
|
F2
|
1
|
0
|
0
|
F3
|
0
|
0
|
1
|
F4
|
0
|
1
|
0
|
F5
|
0
|
1
|
0
|
F6
|
0
|
0
|
1
|
F7
|
0
|
1
|
0
|
Полученное начальное распределение является
оптимальным. Оптимальное значение линейной функции L
равно
.
МОДЕЛИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ
ФАЙЛОВ В ВЫЧИСЛИТЕЛЬНОЙ СЕТИ С КОЛЬЦЕВОЙ ТОПОЛОГИЕЙ
Обозначения:
n - число
узлов сети;
m - число
независимых файлов РБД;Kj - j-й узел
сети;
Fi
- i-й файл РБД;i - объем i-го файла;
bj - объем
памяти узла Kj,
предназначенной для размещения файлов;
dsj -
расстояние между узлами Ks и Kj (dss=0, s=1,2,…,n);
lij -
интенсивность запросов к файлу Fi,
инициированных в узле Kj;
aij - объем
запроса к файлу Fi, инициированного на терминале узла Kj;
bij - объем
запрашиваемых данных при выполнении запроса к файлу Fi,
поступившего на терминал узла Kj;
Задача 1
Вычислительная сеть состоит из трех
узлов, среди которых следует распределить пять файлов.
Размеры файлов:
Li
|
Значение
|
1
|
50
|
2
|
10
|
3
|
48
|
4
|
70
|
5
|
33
|
Расстояние между узлами:
dsj
|
K1
|
K2
|
K3
|
K1
|
0
|
1
|
1
|
K2
|
1
|
0
|
1
|
K3
|
1
|
1
|
0
|
Интенсивности запросов к файлу Fi,
инициированных в узле Kj:
λij
|
K1
|
K2
|
K3
|
F1
|
5
|
2
|
1
|
F2
|
2
|
3
|
1
|
F3
|
7
|
8
|
F4
|
4
|
2
|
9
|
F5
|
9
|
1
|
6
|
Объем памяти узла Kj,
предназначенной для размещения файлов:
Объемы запроса к файлу Fi,
инициированного на терминале узла Kj:
aij
|
K1
|
K2
|
K3
|
F1
|
5
|
6
|
1
|
F2
|
8
|
1
|
3
|
F3
|
3
|
8
|
2
|
F4
|
1
|
5
|
7
|
F5
|
8
|
9
|
2
|
Объемы запрашиваемых данных при выполнении
запроса к файлу Fi,
поступившего на терминал узла Kj:
bij
|
K1
|
K2
|
K3
|
F1
|
40
|
15
|
23
|
F2
|
10
|
8
|
6
|
F3
|
42
|
40
|
30
|
F4
|
53
|
49
|
20
|
F5
|
25
|
30
|
8
|
Сумма произведений объемов данных,
пересылаемых из узла Кs и в этот же
узел при функционировании системы в течение единицы времени, на расстояния, на
которые эти данные пересылаются, в случае хранения файла Fi в узле Ks
рассчитывается по формуле . Результаты
расчетов представлены в таблице 1:
табл. 1
Qij
|
K1
|
K2
|
K3
|
МИН
|
F1
|
66
|
249
|
267
|
66
|
F2
|
36
|
45
|
63
|
36
|
F3
|
592
|
391
|
471
|
391
|
F4
|
351
|
459
|
324
|
324
|
F5
|
99
|
357
|
336
|
99
|
Находим распределение файлов, т.е. определяем
матрицу Х={xij}m,n
хij
(i=1,2, …, m;
j=1,2,…,n)
- величины, определяемые по формуле
.
Результаты расчетов:
X
|
K1
|
K2
|
K3
|
F1
|
1
|
0
|
0
|
F2
|
1
|
0
|
0
|
F3
|
0
|
1
|
0
|
F4
|
0
|
0
|
1
|
F5
|
1
|
0
|
0
|
Выполняем проверку, достаточно ли памяти на
узлах для размещения файлов. Результаты проверки приведены ниже:
X*Li
|
K1
|
K2
|
K3
|
F1
|
50
|
0
|
0
|
F2
|
10
|
0
|
0
|
F3
|
0
|
48
|
0
|
F4
|
0
|
0
|
70
|
F5
|
33
|
0
|
0
|
СУММА
|
93
|
48
|
70
|
Полученное размещение является оптимальным.
Задача 2
Вычислительная сеть состоит из трех узлов, среди
которых следует распределить пять файлов.
Размеры файлов:
Li
|
Значение
|
1
|
50
|
2
|
10
|
3
|
48
|
4
|
70
|
5
|
33
|
Расстояние между узлами:
dsj
|
K1
|
K2
|
K3
|
К4
|
K1
|
0
|
1
|
1
|
2
|
K2
|
1
|
0
|
1
|
2
|
K3
|
1
|
1
|
0
|
1
|
К4
|
2
|
2
|
1
|
0
|
Интенсивности запросов к файлу Fi,
инициированных в узле Kj:
λij
|
K1
|
K2
|
K3
|
К4
|
F1
|
4
|
2
|
1
|
5
|
F2
|
2
|
5
|
1
|
4
|
F3
|
3
|
7
|
8
|
3
|
F4
|
4
|
2
|
9
|
7
|
F5
|
9
|
1
|
6
|
1
|
Объем памяти узла Kj,
предназначенной для размещения файлов:
Bj
|
1
|
2
|
3
|
4
|
|
812
|
564
|
702
|
250
|
Объемы запроса к файлу Fi,
инициированного на терминале узла Kj:
aij
|
K1
|
K2
|
K3
|
К4
|
F1
|
5
|
6
|
1
|
2
|
F2
|
8
|
1
|
3
|
7
|
F3
|
3
|
8
|
2
|
6
|
F4
|
1
|
5
|
7
|
3
|
F5
|
8
|
9
|
2
|
5
|
Объемы запрашиваемых данных при выполнении
запроса к файлу Fi,
поступившего на терминал узла Kj
:
bij
|
K1
|
K2
|
K3
|
К4
|
F1
|
40
|
15
|
23
|
48
|
F2
|
10
|
9
|
6
|
2
|
F3
|
42
|
40
|
30
|
44
|
F4
|
53
|
33
|
10
|
68
|
F5
|
25
|
30
|
8
|
21
|
Сумма произведений объемов данных,
пересылаемых из узла Кs и в этот же
узел при функционировании системы в течение единицы времени, на расстояния, на
которые эти данные пересылаются, в случае хранения файла Fi в узле Ks
рассчитывается по формуле . Результаты
расчетов:
Qij
|
K1
|
K2
|
K3
|
К4
|
МИН
|
F1
|
566
|
704
|
472
|
468
|
468
|
F2
|
131
|
117
|
122
|
181
|
117
|
F3
|
892
|
691
|
621
|
1198
|
621
|
F4
|
1223
|
1363
|
789
|
737
|
737
|
F5
|
151
|
409
|
362
|
732
|
151
|
Находим распределение файлов, т.е. определяем
матрицу Х={xij}m,n
хij
(i=1,2, …, m;
j=1,2,…,n)
- величины, определяемые по формуле
.
Результаты расчетов:
X
|
K1
|
K2
|
K3
|
К4
|
0
|
0
|
0
|
1
|
F2
|
0
|
1
|
0
|
0
|
F3
|
0
|
0
|
1
|
0
|
F4
|
0
|
0
|
0
|
1
|
F5
|
1
|
0
|
0
|
0
|
Выполняем проверку, достаточно ли памяти на
узлах для размещения файлов. Результаты проверки приведены в таблице 9:
X*Li
|
K1
|
K2
|
K3
|
К4
|
F1
|
0
|
0
|
0
|
50
|
F2
|
0
|
10
|
0
|
0
|
F3
|
0
|
0
|
48
|
0
|
F4
|
0
|
0
|
0
|
70
|
F5
|
33
|
0
|
0
|
0
|
СУММА
|
33
|
10
|
48
|
120
|
Полученное размещение является оптимальным.
МОДЕЛИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ
ФАЙЛОВ В ВЫЧИСЛИТЕЛЬНОЙ СЕТИ С ПРОИЗВОЛЬНОЙ ТОПОЛОГИЕЙ
Задача1
Вычислительная сеть состоит из трех узлов, среди
которых следует распределить пять файлов.
Размеры файлов:
Li
|
Значение
|
1
|
50
|
2
|
10
|
3
|
48
|
4
|
70
|
5
|
33
|
Расстояние между узлами:
табл.
2
dsj
|
K1
|
K2
|
K3
|
К4
|
K1
|
0
|
1
|
1
|
2
|
K2
|
1
|
0
|
1
|
2
|
K3
|
1
|
1
|
0
|
1
|
К4
|
2
|
2
|
1
|
0
|
Интенсивности запросов к файлу Fi,
инициированных в узле Kj:
λij
|
K1
|
K2
|
K3
|
К4
|
F1
|
4
|
2
|
1
|
5
|
F2
|
2
|
5
|
1
|
4
|
F3
|
3
|
7
|
8
|
3
|
F4
|
4
|
2
|
9
|
7
|
F5
|
9
|
1
|
6
|
1
|
Интенсивность корректирующих сообщений к файлу Fi
из узла Kj:
λ'ij
|
K1
|
K2
|
K3
|
К4
|
F1
|
1
|
3
|
6
|
1
|
F2
|
5
|
1
|
2
|
1
|
F3
|
2
|
4
|
3
|
2
|
F4
|
7
|
2
|
2
|
3
|
F5
|
1
|
1
|
3
|
2
|
Объем памяти узла Kj,
предназначенной для размещения файлов:
Bj
|
1
|
2
|
3
|
4
|
|
812
|
564
|
702
|
250
|
Объемы запроса к файлу Fi,
инициированного на терминале узла Kj:
aij
|
K1
|
K2
|
K3
|
К4
|
F1
|
5
|
6
|
1
|
2
|
F2
|
8
|
1
|
3
|
7
|
F3
|
3
|
8
|
2
|
6
|
F4
|
1
|
5
|
7
|
3
|
F5
|
8
|
9
|
2
|
5
|
Объемы запрашиваемых данных при выполнении
запроса к файлу Fi,
поступившего на терминал узла Kj:
bij
|
K1
|
K2
|
K3
|
К4
|
F1
|
40
|
15
|
23
|
48
|
F2
|
10
|
9
|
6
|
2
|
F3
|
42
|
40
|
30
|
44
|
F4
|
53
|
33
|
10
|
68
|
F5
|
25
|
30
|
8
|
21
|
Объемы корректирующих сообщений к файлу Fi
из узла Kj:
Tij
|
K1
|
K2
|
K3
|
К4
|
F1
|
20
|
15
|
8
|
10
|
F2
|
2
|
4
|
7
|
5
|
F3
|
18
|
10
|
25
|
12
|
F4
|
40
|
30
|
24
|
27
|
F5
|
10
|
15
|
8
|
10
|
Средний объем данных, необходимых
для пересылки при выполнении запроса в системе вычисляется по формуле . Результаты
расчетов представлены ниже:
V
|
K1
|
K2
|
K3
|
К4
|
F1
|
180
|
42
|
24
|
250
|
F2
|
36
|
50
|
9
|
36
|
F3
|
135
|
336
|
256
|
150
|
F4
|
216
|
76
|
153
|
497
|
F5
|
297
|
39
|
60
|
26
|
Средний объем данных, необходимых
для пересылки при обработке корректирующего сообщения в системе вычисляется по
формуле . Результаты
расчетов представлены ниже:
V'
|
K1
|
K2
|
K3
|
К4
|
F1
|
20
|
45
|
48
|
10
|
F2
|
10
|
4
|
14
|
5
|
F3
|
36
|
40
|
75
|
24
|
F4
|
280
|
60
|
48
|
81
|
F5
|
10
|
15
|
24
|
20
|
Находим распределение файлов, т.е. определяем
матрицу Х={xij}m,n
хij
(i=1,2, …, m;
j=1,2,…,n)
- величины, определяемые по формуле
.
Результаты расчетов представлены
ниже:
X
|
K1
|
K2
|
K3
|
К4
|
F1
|
0
|
1
|
1
|
0
|
F2
|
0
|
0
|
1
|
F3
|
1
|
0
|
0
|
1
|
F4
|
0
|
1
|
1
|
0
|
F5
|
0
|
1
|
0
|
1
|
Выполняем проверку, достаточно ли памяти на
узлах для размещения файлов. Результаты проверки:
X*Li
|
K1
|
K2
|
K3
|
К4
|
F1
|
0
|
50
|
50
|
0
|
F2
|
0
|
0
|
10
|
10
|
F3
|
48
|
0
|
0
|
48
|
F4
|
0
|
70
|
70
|
0
|
F5
|
0
|
33
|
0
|
33
|
СУММА
|
48
|
153
|
130
|
91
|
Полученное размещение является оптимальным.