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

 

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

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

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

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

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

XK1K2K3F1 010F2 100F3001F4 100F5 100F6010F7010

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

qK1K2K3K10,650,20,15K20,30,650,05K30,20,40,4

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

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

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

li1 = 2li (1 - qii)

li2 =

l = .

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

?i?i1?i211,42,622,13,1532,41,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

Т =

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

TiTi1Ti2Т121,631460,30875122,07032221,69490,280136321,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.

Вычислительная сеть состоит из трех узлов 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

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

табл.2

WiW1W210,0010,620,210,1830,280,2

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

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

вычислительная сеть топология файл

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

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

K1K2K3F1 010F2 100F3001F4 010F5 010F6001F7010

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

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

dsjK1K2K3K1011K2101K3110

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

?ijK1K2K3F1521F2231F3378F4429F5916

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

Bj123 812564702

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

aijK1K2K3F1561F2813F3382F4157F5892

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

bijK1K2K3F1401523F21086F3424030F4534920F525308

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

табл. 1

QijK1K2K3МИНF16624926766F236456336F3592391471391F4351459324324F59935733699

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

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

.

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

XK1K2K3F1100F2100F3010F4001F5100

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

X*LiK1K2K3F15000F21000F30480F40070F53300СУММА934870

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

Задача 2

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

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

Li Значение150210348470533

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

dsjK1K2K3К4K10112K21012K31101К42210

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

?ijK1K2K3К4F14215F22514F33783F44297F59161

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

Bj1234 812564702250

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

aijK1K2K3К4F15612F28137F33826F41573F58925

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

bijK1K2K3К4F140152348F210962F342403044F453331068F52530821

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

QijK1K2K3К4МИНF1566704472468468F2131117122181117F38926916211198621F412231363789737737F5151409362732151

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

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

.

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

XK1K2K3К4F10001F20100F30010F40001F51000

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

X*LiK1K2K3К4F100050F201000F300480F400070F533000СУММА331048120

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

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

Задача1

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

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

Li Значение150210348470533

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

табл. 2

dsjK1K2K3К4K10112K21012K31101К42210

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

?ijK1K2K3К4F14215F22514F33783F44297F59161

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

?'ijK1K2K3К4F11361F25121F32432F47223F51132

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

Bj1234 812564702250

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

aijK1K2K3К4F15612F28137F33826F41573F58925

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

bijK1K2K3К4F140152348F210962F342403044F453331068F52530821

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

TijK1K2K3К4F12015810F22475F318102512F440302427F51015810

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

VK1K2K3К4F11804224250F23650936F3135336256150F421676153497F5297396026

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

V'K1K2K3К4F120454810F2104145F336407524F4280604881F510152420

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

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

.

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

XK1K2K3К4F10110F20011F31001F40110F50101

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

X*LiK1K2K3К4F1050500F2001010F3480048F4070700F5033033СУММА4815313091

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

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

Больше работ по теме: