Математическая модель оптимального размещения распределённой базы данных по узлам ЛВС на базе файл – серверной архитектуры

Размещено на http://www.allbest.ru/

Южно-Российский государственный политехнический университет (НПИ) им. М. И. Платова

Математическая модель оптимального размещения распределённой базы данных по узлам ЛВС на базе файл - серверной архитектуры

Скоба А. Н., Состина Е. В.

Новочеркасск

Аннотация

В данной статье с использованием аппарата замкнутых экспоненциальных сетей массового обслуживания (СеМО), разработана математическая модель для решения задачи получения интегральных показателей распределённой информационной системы на базе локальной вычислительной сети (ЛВС) с использованием файл-серверной архитектуры. Представлен алгоритм оптимального размещения распределённой базы данных (РБД) по узлам ЛВС по критерию минимума среднего времени реакции системы на запросы пользователей. Приведены результаты численных экспериментов.

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

Как было отмечено в работах [1,2], одной из важных задач, без решения которой невозможна разработка распределённой информационной системы, является рациональная организация вычислительного процесса, реализованного в среде ЛВС. В процессе работы ЛВС поддерживает распределённую базу данных (РБД) [3], которая обладает несомненными преимуществом перед централизованной (меньшее время ответа для пользователей, меньшее время блокировки записей, более простое планирование заявок). Однако при проектировании таких систем будут существовать большие общие пересекающиеся массивы данных, в которых определенная информация будет присутствовать многократно. Неоптимальное обращение с информационными ресурсами может с одной стороны увеличить время реакции системы на запросы пользователей, а с другой стороны, может стать очень дорогим для пользователей [4]. Поэтому в одной из задач, возникающих при проектировании распределённой информационной системы на базе ЛВС, является задача оптимального размещения информационных ресурсов (частей РБД) по узлам ЛВС, включающая выбор топологии сети, критерия эффективности, конструирование математической модели, разработку алгоритма оптимизации и ее программную реализацию.

Для формализации постановки задачи приняты следующие допущения [5]: топология сети - моноканал односегментный; тип запроса - однократный; предметная область - информационное обслуживание; однородность сети - выделенный файл-сервер; тип процесса - простой; режим информационного обслуживания - чтение; способ обеспечения целостности данных - отсутствует.

Математическая постановка задачи. Имеется ЛВС, включающая: множество узлов сети - U={U₁,…,U_s,…,U_n}; множество пользователей - A={A₁,…,A_s,…,A_n}; множество отношений - R={R₁,…,R_j,…,R_d}; множество интенсивностей формирования запросов - Л={л₁,…,л_s,…,л_n}; множество запросов на чтение - Q={Q₁,…,Q_l,…,Q_q}; множество объёмов отношений - V={V₁,…,V_j,…,V_d}; скорость считывания в узлах - VV={VV₁,…,VV_s,…,VV_n}; скорость записи в узлах - VD={VD₁,…,VD_s,…,VD_n}; скорость передачи данных по каналу связи - и; постоянная задержка при передаче данных по каналу связи - и₀; постоянная задержка при обработке в узле - б₀; производительность процессора U_z-го узла - PU_z,; матрица вероятностей формирования запросов пользователями - , где элемент f_sl представляет собой вероятность того, что s-й пользователь сформировал l-й запрос; матрица объёмов считываемой информации, где b_lj-объём считываемой информации по l-му запросу на чтение из j-го отношения; файл информационный бузен

,

Где

причём ; матрица распределения отношений по узлам ЛВС - , где причём.

Концептуальная модель. Ввиду того, что интенсивности формирования запросов пользователями различны, а также принимая во внимание то, что времена обслуживания заявок в узлах являются взаимно независимыми случайными величинами, распределёнными по экспоненциальному закону, изучение интегральных характеристик данной информационной системы (ИС) можно свести к исследованию замкнутой экспоненциальной сети массового обслуживания (СеМО) [6-8]. Концептуальная модель функционирования рассматриваемой ИС содержит: приборы - P₀, P₁,…, P_n, моделирующие работу соответственно канала и узлов U₁,…U_n; буферные памяти канала, предназначенные для хранения запросов пользователей -BPC₁,…,BPC_s,…,BPC_n; буферные памяти узлов - BPU₁,…,BPU_s,…,BPU_n. Данная концептуальная модель представлена на рис.1.

Рис. 1. Концептуальная модель информационной системы

Определение стационарных вероятностей состояний сети. Для идентификации состояний сети введём векторное пространство состояний:

E{E_i(i₁₁,…,i_1s,…,i_1n;i₂₁,…,i_2s,…,i_2n;…;i_s+1,₁,…,i_s+1,_s,…,i_s+1,n;…;i_n+1,1,…,i_n+1,s,…,i_n+1,n;

i_n+2,1,…,i_n+2,s,…,i_n+2,n;…;i_n+s+1,1,…,i_n+s+1,s,…,i_n+s+1,n;…;i_2n+1,1,…,i_2n+1,s,…,i_2n+1,n),},

где

описывает очереди к каналу и состояние канала, где i_sr - количество запросов r-го пользователя в s-ой буферной памяти канала и на обслуживании в канале; описывает очереди к узлам и состояния узлов (ПЭВМ), где i_sr - количество сообщений r-го пользователя в буферной памяти узла и на обслуживании в узле. При этом имеют место следующие ограничения:

;

;

.

Представляющие интерес характеристики СеМО определяются стационарными вероятностями состояний сети. Пусть стационарная вероятность того, что сеть находится в состоянии , где Можно показать, что процесс изменения состояний сети описывается однородным регулярным марковским процессом [9]. Тогда уравнение глобального баланса относительно для стационарного режима функционирования имеет вид [6-8,10,11]:

, (1)

где интенсивность обслуживания в s-м узле сообщения r-го пользователя; вектор, в s-ой координате которого на r-м месте стоит 1, а все остальные значения равны нулю; P_lk(r) - вероятность того, что сообщение r-го пользователя после обслуживания в l-м центре попадёт в k-й центр.

Согласно [6-8] выражения для стационарных вероятностей состояний сети, описываемой уравнением (1), имеют мультипликативную форму и могут быть представлены в виде

.(2)

Здесь G(N₁,…,N_n) - нормализующая константа, выражение для которой, исходя из (2) и условия нормировки:, (где, имеет вид

, (3)

- общее число сообщений в центре

s,. (4)

В выражение (4) входят величины , которые находятся из решения системы линейных алгебраических уравнений

. (5)

Число независимых уравнений в системе (5) на единицу меньше количества переменных, так что её решение единственно с точностью до мультипликативной константы. Для отыскания однозначного решения системы (5) достаточно произвольно задать значение e_sr, например, положить. В этом случае величины e_sr можно интерпретировать как среднее число посещений сообщением r-го пользователя центра s между двумя последовательными посещениями им первого центра [6].

При расчёте величины учитываются следующие три группы потока заявок [5]: первая группа включает запросы, формируемые пользователем, прикреплённым к U_s-му узлу, т.е. запросы пользователя к базам данных, размещённым в собственной ПЭВМ; вторая группа включает запросы, сформированные пользователем U_s-го узла, для выполнения которых необходимо обращение к базам данных, расположенным в других узлах. После реализации такого обращения должна быть выполнена окончательная обработка полученной информации в собственной ПЭВМ пользователя; третья группа включает запросы, формируемые пользователями других узлов, т.е. в U_s-м узле размещены базы данных, которые необходимы для выполнения запросов, формируемых пользователями, прикреплёнными к другим узлам. Исходя из этого:

Элементы матрицы переходных вероятностей для запросов s-го пользователя определим следующим образом:

Расчёт среднего времени реакции системы. Пусть среднее время реакции системы на запрос пользователей. Величину определим как

, (6)

где интенсивность формирования запросов r-м пользователем; среднее время реакции системы на запрос r-го пользователя. Величину определим как

, (7)

где среднее количество заявок r-го пользователя в системе; средняя интенсивность формирования заявок r-м пользователем. Величины и определим как , , где P_r(1) - вероятность того, что r-й пользователь системы находится в активном состоянии (формирует запрос). С учётом этого формула (6) примет вид

. (8)

Здесь ,

где , .

Несложно показать, что

,(9)

где . Согласно (4) выражение (9) может быть приведено к виду

, (10)

где .

Как видно из (10), расчёт величины сводится по существу к расчёту нормализующей константы G(N₁,…,N_n), вычисление которой по формуле (3) сопряжено со значительными вычислительными сложностями (при увеличении числа центров, классов сообщений, мощность пространства состояний быстро растёт). В работах [7,12] описан рекуррентный метод Бузена для расчёта G(N₁,…,N_n), в соответствии с которым расчёт нормализующей константы сводится к простой итерационной процедуре:

, (11)

где . Предполагается также, что, если все и , если хотя бы одна из координат вектора . Значение нормализующей константы G(N₁,…,N_n) получается по формуле (11) при и , где .

Решение оптимизационной задачи. Задача оптимального размещения РБД по узлам ЛВС по критерию среднего времени реакции системы сводится к задаче

при ограничении, (12)

где X = || ||, () - матрица, задающая взаимосвязь между ПЭВМ и размещаемыми на них отношениями; имеет вид (8), для данного размещения, задаваемого матрицей Х.

Задача (12) является задачей нелинейной комбинаторной оптимизации с буквенными переменными. Ввиду того, что функция имеет сложный вид, а так же ввиду отсутствия в настоящее время алгоритмов решения такого класса задач (кроме как метод полного перебора) [5,12], для решения задачи (12) может быть применен следующий разработанный эвристический алгоритм, основанный на численном прогнозировании поведения целевой функции. Обозначим - вероятность того, что i-й пользователь обратится к j-му отношению; - средний объем информации, циркулирующий между i-м пользователем и j-м отношением.

1. Полагаем (i=, j=), k=0.

2. Выбираем для j=: K_sj=max{K_ij}, (i=) и отношение помещаем в s-ю ПЭВМ.

3. Вычисляем значения {}, (r=) по формуле (7), а значение по формуле (8). Если k?0 - переходим на шаг 7, в противном случае - на следующий шаг.

4. Полагаем {}={}, i= и .

5. Выбираем ={}, i= и =max({}/{}), где : =, =1.

6. Если или {}/{}={}, то переходим на шаг 8, иначе отношение помещаем в м-ю ПЭВМ, полагаем k=k+1 и переходим на шаг 3.

7. Если < переходим на шаг 4, в противном случае полагаем и переходим на шаг 5.

8. Конец. (Полученное распределение будет оптимальным).

Результаты численных экспериментов. Составлена программа расчета данной модели (среднего времени реакции системы на запросы пользователей) и алгоритма оптимизации на языке С++. Расчет проводился на компьютере на базе процессора фирмы Intel, с тактовой частотой 3,0 ГГц. В таблице №1 приведены некоторые результаты машинных экспериментов.

Таблица 1 Результаты машинных экспериментов

Здесь МПП - метод полного перебора; ЭА - эвристический алгоритм; - среднее время реакции системы для оптимального размещения РБД, полученного МПП; среднее время реакции системы для оптимального размещения РБД, полученного ЭА; ? относительная погрешность, выраженная в % между оптимальным размещением, полученным МПП и квазиоптимальным размещением, полученным с помощью ЭА.

Разработанная модель оптимального размещения РБД по узлам ЛВС может быть использована при внедрении интегрированных информационно-справочных систем на промышленных предприятиях.

Литература

1. Теоретические основы автоматизированного управления / А.В. Меньков, В.А. Острейковский. Учебник для вузов. М.: Издательство Оникс, 2005. 640с.

2. Проектирование экономических информационных систем: Учебник / Г.Н. Смирнова, А.А. Сорокин, Ю.Ф. Тельнов; Под ред.Ю.Ф. Тельнова. М.: Финансы и статистика,2001. 512с.

3. Воробьёв С.П., Горобец В.В. Исследование модели транзакционной системы с репликацией фрагментов базы данных, построенной по принципам облачной среды // Инженерный вестник Дона. 2012. №4. URL: ivdon.ru/ru/magazine/archive/n4y2012/1149.

4. Павлов С.В., Самойлов А.С. Проектирование структуры распределённой базы пространственных данных в сложно структурированных иерархических географических информационных системах // Инженерный вестник Дона. 2015. №1. URL: ivdon.ru/ru/magazine/archive/n1y2015/2755.

5. Черноморов Г.А. Теория принятия решений: Учебное пособие / Юж.-Рос.гос. техн.ун-т.-3-е изд. перераб. и доп. Новочеркасск : Ред. журн. «Изв. Вузов. Электроомеханика», 2005. 448с.

6. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003.- 512 с.

7. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. 192с.

8. Герасимов А.И. Теория и практическое применение стохастических сетей. М.: Радио и связь,1994.-175с.

9. Клейнрок Л. Вычислительные системы с очередями: Пер. с англ.-М.Мир,1979. 600с.

10. Antunes C.H. et al. A Multiple Objective Routing Algorithm for Integrated Communication Network // Proc. ITC-16.-1999.V.3b. pp.1291-1300.

11. Chakka R., Harrison P.G. A Markov modulated multi-server queue with negative customers. Ihe MM CPP/GE/c/LG-queue // Acta Informatika/-2001.-v.37. pp.785-799.

12. Круглый З.Л. Алгоритмы расчёта моделей структур вычислительных систем с различными классами заданий // Управляющие системы и машины. 1980. №4. С.73-79.

Размещено на Allbest.ru