Модели оптимального размещения файлов в вычислительной сети
Модели оптимального размещения файлов в вычислительной сети созвездообразной топологией
Задача1
Вычислительная сетьсостоит из трех узлов, среди которых следует распределить семь файлов.
Обозначения:
qsr — вероятность того,что запрос, инициированный в узле Кs, использует для своего обслуживания файл,находящийся в локальной БД узла Кr.
Для определения общейсредней задержки при выполнении запроса в сети введем следующие величины:
li — средняя интенсивность запросов,инициированных в узле Ki;
lik — средняя интенсивность поступлениязапросов k-того типа во входную сеть узла Ki.
Wik – среднее время обработки запросов k-того типа на узле Ki;
W2ik – дисперсия времени обработкизапроса 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 1
F2 1
F3 1
F4 1
F5 1
F6 1
F7 1
Таблица значений 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= />
Ri1= />
Qi2= />
Ri2= />
Q = />
R = />
Результаты расчетовприведены таблицах: 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 соответственно:
табл.1P
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
табл.2Wi 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 1
F2 1
F3 1
F4 1
F5 1
F6 1
F7 1
Полученное начальноераспределение является оптимальным. Оптимальное значение линейной функции L равно
/>.
МОДЕЛИ ОПТИМАЛЬНОГОРАСПРЕДЕЛЕНИЯ ФАЙЛОВ В ВЫЧИСЛИТЕЛЬНОЙ СЕТИ С КОЛЬЦЕВОЙ ТОПОЛОГИЕЙ
Обозначения:
n – число узлов сети;
m – число независимых файлов РБД;Kj – j-й узел сети;
Fi– i-й файл РБД;
Li – объем 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 1 1 K2 1 1 K3 1 1
Интенсивности запросов кфайлу Fi, инициированных в узле Kj:λij K1 K2 K3 F1 5 2 1 F2 2 3 1 F3 3 7 8 F4 4 2 9 F5 9 1 6
Объем памяти узла Kj, предназначенной для размещенияфайлов:Bj 1 2 3 812 564 702
Объемы запроса к файлу 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:
табл. 1Qij 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 F2 1 F3 1 F4 1 F5 1
Выполняем проверку,достаточно ли памяти на узлах для размещения файлов. Результаты проверкиприведены ниже:X*Li K1 K2 K3 F1 50 F2 10 F3 48 F4 70 F5 33 СУММА 93 48 70
Полученное размещениеявляется оптимальным.
Задача 2
Вычислительная сетьсостоит из трех узлов, среди которых следует распределить пять файлов.
Размеры файлов:Li Значение 1 50 2 10 3 48 4 70 5 33
Расстояние между узлами:dsj K1 K2 K3 К4 K1 1 1 2 K2 1 1 2 K3 1 1 1 К4 2 2 1
Интенсивности запросов кфайлу 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 F1 1 F2 1 F3 1 F4 1 F5 1
Выполняем проверку,достаточно ли памяти на узлах для размещения файлов. Результаты проверкиприведены в таблице 9:X*Li K1 K2 K3 К4 F1 50 F2 10 F3 48 F4 70 F5 33 СУММА 33 10 48 120
Полученное размещениеявляется оптимальным.
МОДЕЛИ ОПТИМАЛЬНОГОРАСПРЕДЕЛЕНИЯ ФАЙЛОВ В ВЫЧИСЛИТЕЛЬНОЙ СЕТИ С ПРОИЗВОЛЬНОЙ ТОПОЛОГИЕЙ
Задача1
Вычислительная сетьсостоит из трех узлов, среди которых следует распределить пять файлов.
Размеры файлов:Li Значение 1 50 2 10 3 48 4 70 5 33
Расстояние между узлами:
табл. 2dsj K1 K2 K3 К4 K1 1 1 2 K2 1 1 2 K3 1 1 1 К4 2 2 1
Интенсивности запросов кфайлу 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 1 1 F2 1 1 F3 1 1 F4 1 1 F5 1 1
Выполняем проверку,достаточно ли памяти на узлах для размещения файлов. Результаты проверки:X*Li K1 K2 K3 К4 F1 50 50 F2 10 10 F3 48 48 F4 70 70 F5 33 33 СУММА 48 153 130 91
Полученное размещение являетсяоптимальным.