Модели оптимального размещения файлов в вычислительной сети

Модели оптимального размещения файлов в вычислительной сети со звездообразной топологией

Задача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):

PF1F2F3F4F5F6F7
K10,050,30,150,250,10,060,09
K20,40,10,050,080,120,10,15
K30,150,070,40,030,10,150,1

Распределение фалов по узлам вычислительной сети задано ниже:

XK1K2K3
F1010
F2100
F3001
F4100
F5100
F6010
F7010

Таблица значений qsr будет иметь вид:

QK1K2K3
K10,650,20,15
K20,30,650,05
K30,20,40,4

Задали самостоятельно li – среднюю интенсивность запросов, инициированных в узле Ki:

λЗначение
λ12
λ23
λ32

Выполняем расчет средней интенсивности поступления запросов k-того типа во входную сеть узла Ki и средней интенсивности входного потока сообщений в коммутаторе данных по следующим формулам:

Li 1 = 2li (1 – qii )

Li 2 =

L = .

Результаты расчетов приведены ниже:

λiλi1λi2
11,42,6
22,13,15
32,41,25λ5,9

Среднее время обработки запросов k – того типа на узле Ki и дисперсия времени обработки запроса k – того типа на узле Ki приведены в таблицах:

WWi1Wi2
10,30,17
20,250,13
30,350,1
W2Wi1Wi2
10,140,075
20,1150,055
30,1650,04

Средняя скорость обслуживания сообщений в коммутаторе данных равна m=6.

Выполняем расчет значений Qi1 и Ri1, Qi2 и Ri2 – времени ожидания и обслуживания заявок определенного типа и Q и R – время ожидания и обслуживания на коммутаторе по приведенным ниже формулам:

Qi1 =

Ri1 =

Qi2 =

Ri2 =

Q =

R =

Результаты расчетов приведены таблицах:

QiQi1Qi2Q
10,056840,01564810
20,0573560,006452
30,031680,001249
RiRi1Ri2R
10,5172410,2931030,166667
2

0,

42105

0,273684
32,18750,625

Выполняем подсчет суммы li по формуле:

S = = 7

На основании полученных данных выполняем расчет среднего времени обслуживания запроса соответствующего типа, инициированного на узле Ki и общее среднее время ответа на запрос по всей вычислительной системе с помощью формул приведенных ниже:

Тil = 2Qi1 + 2Ri1 + 2Q + 2R + Qj2 + Rj2

Тi2 = Qi2 + Ri2

Т =

Результаты расчетов приведены ниже:

TiTi1Ti2Т
121,631460,30875122,07032
221,69490,280136
321,844050,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.

Вычислительная сеть состоит из трех узлов K 1 , K 2 , K 3 , а РБД содержит семь файлов F 1 , F 2 , …, F 7 . А λ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

PF1F2F3F4F5F6F7
K10,050,30,150,250,10,060,09
K20,40,10,050,080,120,10,15
K30,150,070,40,030,10,150,1

Табл.2

WiW1W2
10,0010,6
20,210,18
30,280,2

Найдем оптимальное распределение файлов по узлам вычислительной сети.

Используя формулу Qjs = , находим Qjs (j =1, 2,…, 8; s = 1, 2, 3). Эти величины имеют значения:

Вычислительная сеть размещение файл

QK1K2K3MIN
F11,50,41,30,4
F20,440,740,90,44
F30,931,080,450,45
F40,30,560,740,3
F50,580,420,560,42
F60,60,420,420,42
F70,650,380,630,38

В соответствии с выбранными начальное распределение будет иметь вид:

K1K2K3
F1010
F2100
F3001
F4010
F5010
F6001
F7010

Полученное начальное распределение является оптимальным. Оптимальное значение линейной функции 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Значение
150
210
348
470
533

Расстояние между узлами:

DsjK1K2K3
K1011
K2101
K3110

Интенсивности запросов к файлу Fi, инициированных в узле Kj :

λijK1K2K3
F1521
F2231
F3378
F4429
F5916

Объем памяти узла Kj, предназначенной для размещения файлов:

Bj123
812564702

Объемы запроса к файлу Fi, инициированного на терминале узла Kj :

AijK1K2K3
F1561
F2813
F3382
F4157
F5892

Объемы запрашиваемых данных при выполнении запроса к файлу Fi, поступившего на терминал узла Kj :

bijK1K2K3
F1401523
F21086
F3424030
F4534920
F525308

Сумма произведений объемов данных, пересылаемых из узла Кs и в этот же узел при функционировании системы в течение единицы времени, на расстояния, на которые эти данные пересылаются, в случае хранения файла Fi в узле Ks рассчитывается по формуле . Результаты расчетов представлены в таблице 1:

Табл. 1

QijK1K2K3МИН
F16624926766
F236456336
F3592391471391
F4351459324324
F59935733699

Находим распределение файлов, т. е. определяем матрицу Х={xij }m, n

Хij (i=1,2, …, m; j=1,2,…,n) – величины, определяемые по формуле

.

Результаты расчетов:

XK1K2K3
F1100
F2100
F3010
F4001
F5100

Выполняем проверку, достаточно ли памяти на узлах для размещения файлов. Результаты проверки приведены ниже:

X*LiK1K2K3
F15000
F21000
F30480
F40070
F53300
СУММА934870

Полученное размещение является оптимальным.

Задача 2

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

Размеры файлов:

LiЗначение
150
210
348
470
533

Расстояние между узлами:

DsjK1K2K3К4
K10112
K21012
K31101
К42210

Интенсивности запросов к файлу Fi, инициированных в узле Kj :

λijK1K2K3К4
F14215
F22514
F33783
F44297
F59161

Объем памяти узла Kj, предназначенной для размещения файлов:

Bj1234
812564702250

Объемы запроса к файлу Fi, инициированного на терминале узла Kj :

AijK1K2K3К4
F15612
F28137
F33826
F41573
F58925

Объемы запрашиваемых данных при выполнении запроса к файлу Fi, поступившего на терминал узла Kj :

BijK1K2K3К4
F140152348
F210962
F342403044
F453331068
F52530821

Сумма произведений объемов данных, пересылаемых из узла Кs и в этот же узел при функционировании системы в течение единицы времени, на расстояния, на которые эти данные пересылаются, в случае хранения файла Fi в узле Ks рассчитывается по формуле . Результаты расчетов:

QijK1K2K3К4МИН
F1566704472468468
F2131117122181117
F38926916211198621
F412231363789737737
F5151409362732151

Находим распределение файлов, т. е. определяем матрицу Х={xij }m, n

Хij (i=1,2, …, m; j=1,2,…,n) – величины, определяемые по формуле

.

Результаты расчетов:

XK1K2K3К4
F10001
F20100
F30010
F40001
F51000

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

X*LiK1K2K3К4
F100050
F201000
F300480
F400070
F533000
СУММА331048120

Полученное размещение является оптимальным.

МОДЕЛИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ФАЙЛОВ В ВЫЧИСЛИТЕЛЬНОЙ СЕТИ С ПРОИЗВОЛЬНОЙ ТОПОЛОГИЕЙ

Задача1

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

Размеры файлов:

LiЗначение
150
210
348
470
533

Расстояние между узлами:

Табл. 2

DsjK1K2K3К4
K10112
K21012
K31101
К42210

Интенсивности запросов к файлу Fi, инициированных в узле Kj :

λijK1K2K3К4
F14215
F22514
F33783
F44297
F59161

Интенсивность корректирующих сообщений к файлу Fi из узла Kj :

λ’ijK1K2K3К4
F11361
F25121
F32432
F47223
F51132

Объем памяти узла Kj, предназначенной для размещения файлов:

Bj1234
812564702250

Объемы запроса к файлу Fi, инициированного на терминале узла Kj :

AijK1K2K3К4
F15612
F28137
F33826
F41573
F58925

Объемы запрашиваемых данных при выполнении запроса к файлу Fi, поступившего на терминал узла Kj :

Bij

K1K2K3К4
F140152348
F210962
F342403044
F453331068
F52530821

Объемы корректирующих сообщений к файлу Fi из узла Kj :

TijK1K2K3К4
F12015810
F22475
F318102512
F440302427
F51015810

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

VK1K2K3К4
F11804224250
F23650936
F3135336256150
F421676153497
F5297396026

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

V’K1K2K3К4
F120454810
F2104145
F336407524
F4280604881
F510152420

Находим распределение файлов, т. е. определяем матрицу Х={xij }m, n

Хij (i=1,2, …, m; j=1,2,…,n) – величины, определяемые по формуле

.

Результаты расчетов представлены ниже:

XK1K2K3К4
F10110
F20011
F31001
F40110
F50101

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

X*LiK1K2K3К4
F1050500
F2001010
F3480048
F4070700
F5033033
СУММА4815313091

Полученное размещение является оптимальным.


1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...
Модели оптимального размещения файлов в вычислительной сети