УДК 004.7

ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ФАЙЛОВ ПО УЗЛАМ КОМПЬЮТЕРНОЙ СЕТИ

Первоисточник: Лазебная Л. А., Едемская Е. Н., Бельков Д. В. Динамическое распределение файлов по узлам компьютерной сети // Программная инженерия: методы и технологии разработки информационно-вычислительных систем (ПИИВС-2018): сб. науч. трудов II Междунар. науч.-практ. конф. Т. 1. 14–18 нояб. 2018 г. – Донецк: ДонНТУ, 2018. – 308 с. – URL: https://pi.conf.donntu.ru/collection/seics2018.pdf .

Л. А. Лазебная, Е. Н. Едемская, Д. В. Бельков
Донецкий национальный технический университет
E-mail: l_lazebnay@mail.ru, 6otba@list.ru, belkov65@list.ru

Введение

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

Для статического размещения файлов по узлам компьютерной сети необходимо при фиксированных значениях интенсивностей запросов к файлам так распределить файлы по узлам компьютерной сети, чтобы время отклика сети было минимальным [1, 2]. В процессе длительной работы распределённой системы интенсивность потока запросов к файлам со временем изменяется. Исходное размещение файлов может стать не оптимальным, поэтому размещение файлов должно корректироваться. Непрерывный мониторинг уровней локальных запросов к файлам требует значительных вычислительных и временных затрат, поэтому мониторинг целесообразно проводить периодически [3].

Целью статьи является разработка метода динамического размещения файлов по узлам компьютерной сети. Задача работы – определение оптимального интервала между мониторингами уровней локальных запросов к файлам для уменьшения трудоёмкости размещения файлов.

Метод динамического распределения файлов

Введём обозначения:

• суммарная интенсивность сетевых запросов к файлам узла j – N_j;
• суммарная интенсивность локальных запросов к файлам узла j – L_j;
• функция полезности узла j: Y_j = 0, если L_j > N_j, иначе Y_j = 1.

Во время мониторинга узел j выполняет следующие шаги:

1. измерить текущий уровень локальных запросов L_j;
2. если L_j > N_j, то положить Y_j := 0, иначе Y_j := 1;
3. перейти к шагу 1.

Узел, в котором хранится наибольшее число файлов, является сервером. Он выполняет следующий метод динамического размещения файлов.

1. В текущий момент времени t распределить файлы по узлам сети и ожидать Ω_opt единиц времени.
2. В момент времени t + Ω_opt выдать узлам сети сигнал начать мониторинг за уровнем локальных запросов; мониторинг длится t_mon единиц времени.
3. В момент времени (t + Ω_opt) + t_mon выдать узлам сети сигнал завершить мониторинг и присвоить переменной t значение (t + Ω_opt) + t_mon.
4. Если число узлов с низкой локальной нагрузкой превысило допустимый порог Δ, то есть выполнено условие ∑_j=1ⁿ Y_j ≥ Δ, установить сигнал RD. Требование перераспределить файлы системы: RD = 1 и перейти к шагу 1; иначе установить сигнал RD = 0 и перейти к шагу 2.

Величина Δ характеризует чувствительность метода к уменьшению уровней локальных запросов в узлах. Она может принимать значения в диапазоне от 1 до n с шагом 1. При Δ = Δ_min = 1 метод имеет наибольшую чувствительность к уменьшению локальной нагрузки узлов. При Δ = Δ_max = n метод имеет наименьшую чувствительность к уменьшению локальной нагрузки узлов.

Обозначим: k – номер мониторинга, k = 1, 2, …; Ω_k^opt – период, в течение которого сеть функционирует от k-го мониторинга до (k + 1)-го мониторинга.

Процесс динамического размещения файлов состоит в следующем. Пусть в момент времени t_k завершён k-й мониторинг и установлен счётчик шагов s := k. Осуществляется шаг по времени длиной Ω_k^opt из точки с координатами (0, t_k) в точку с координатами (0, t_k+1). Если в момент t_k+1 выполняется условие ∑_j=1ⁿ Y_j ≥ Δ, то устанавливается сигнал требования перераспределить файлы системы (RD = 1), иначе выполняются действия: RD := 0, s := s + 1, и процесс повторяется с момента t_k+1. Таким образом, интервал между перераспределениями файлов равен сумме ∑_k=1^s Ω_k^opt.

Процесс функционирования узла j показан на рисунке 2. Пусть S_j = L_j − N_j. В момент t₁ сделано первоначальное распределение файлов. В момент t₂ = t₁ + Ω₁^opt проведён первый мониторинг. Так как в момент t₂ условие S_j ≤ 0 выполняется, формируется сигнал Y_j = 1. В момент t₃ = t₂ + Ω₂^opt проведён второй мониторинг. Так как в момент t₃ условие S_j ≤ 0 не выполняется, сигнал не формируется: Y_j = 0. В момент t₄ = t₃ + Ω₃^opt проведён третий мониторинг; поскольку условие S_j ≤ 0 выполняется, в этот момент вновь формируется сигнал Y_j = 1.

Определение оптимальной периодичности мониторингов

Обозначим: τ_k – среднее время выполнения запроса к файлу; s – число запросов к файлам при выполнении вычислительного задания.

Состояния, в которых может находиться система, разделяются на два класса. Один класс содержит единственное состояние перераспределения файлов, другой – множество состояний функционирования. В состоянии перераспределения файлов выполняется процесс размещения файлов по узлам сети, запросов к файлам не возникает. После размещения файлов по узлам сети система начинает функционировать: в каждом узле выполняются запросы к файлам. В одном состоянии функционирования система выполняет один запрос к файлу, поэтому количество состояний равно s. Момент завершения выполнения запроса, совпадающий с моментом перехода системы к выполнению другого запроса, является моментом перехода системы в другое состояние функционирования. Из любого состояния функционирования система может перейти в другое состояние функционирования или в состояние перераспределения файлов. Граф состояний системы показан на рисунке 3.

Пусть в i-м состоянии функционирования система пребывает случайное время с произвольной функцией распределения и средним значением τ_i; q_i – вероятность перехода из i-го состояния функционирования в состояние перераспределения файлов; p_ij – вероятность перехода из i-го состояния функционирования в j-е состояние функционирования (j = 1, …, s), причём ∑_j=1^s p_ij < 1. Вектор начального распределения состояний обозначим p₁ = {p₁₁, p₁₂, …, p_1s}.

Такой процесс функционирования системы является полумарковским. Отличие от марковского процесса состоит в том, что матрица переходов является полустохастической, а случайное время пребывания системы в состояниях функционирования имеет произвольную функцию распределения.

Для определения среднего времени пребывания системы в классе состояний функционирования до перехода в состояние перераспределения файлов используем методику [4]. Пусть α_i – среднее время пребывания системы в классе состояний функционирования до перехода в состояние перераспределения файлов при условии, что начальным состоянием является состояние i. Время α_i состоит из времени τ_i и суммарного времени, накопленного в состояниях j:

α_i = τ_i + ∑_j=1^s p_ij α_j. (1)

Для реальных компьютерных сетей трудно определить точные значения переходных вероятностей p_ij. Число состояний s может достигать 10⁵, и решение системы уравнений (1) становится трудоёмким. Поэтому среднее время T пребывания системы в классе состояний функционирования до перехода в состояние перераспределения файлов целесообразно определять приближённо.

В реальных условиях работы распределённая система редко находится в состоянии перераспределения файлов. Поэтому вероятности переходов между состояниями функционирования близки к единице (p_ij ≈ 1), а вероятность перехода системы из класса состояний функционирования в состояние перераспределения файлов мала (q_i ≈ 0). Следовательно, выполняются условия укрупнения полумарковских систем, и для определения значения T можно использовать метод фазового укрупнения сложных систем.

Для оценки погрешности, возникающей при укрупнении состояний системы, введём идеальную систему, которая отличается от реальной тем, что для неё никогда не требуется перераспределять файлы. Идеальная система не имеет состояния перераспределения файлов, все её состояния являются состояниями функционирования. Обозначим p^*_ij – вероятность перехода из i-го состояния идеальной системы в j-е состояние идеальной системы, p^*₁ = {p^*₁₁, …, p^*_1s} – вектор начального распределения идеальной системы. Переходные вероятности идеальной системы связаны с переходными вероятностями реальной системы соотношением p^*_ij = p_ij + q_ij, где q_ij – вероятность перехода из i-го состояния функционирования в состояние перераспределения файлов при условии, что следующим состоянием функционирования будет j-е состояние.

Матрица Q характеризует параметр близости идеальной системы реальной системе γ = max γ_ij, где γ_ij = p^*_ij / p_ij. Для реальной распределённой системы значение γ близко к единице; следовательно, в системе (1) возможно заменить значения p_ij значениями p^*_ij:

α_i = τ_i + ∑_j=1^s p^*_ij α_j. (2)

Погрешность, возникающая при укрупнении состояний системы, определяется величиной (1 − γ).

Обозначим q – вероятность перехода системы из класса состояний функционирования в состояние перераспределения файлов, p = 1 − q – вероятность пребывания системы в классе состояний функционирования. Все состояния функционирования системы «склеиваются» в одно состояние функционирования. Граф состояний укрупнённой системы показан на рисунке 4.

Процесс переходов укрупнённой системы является марковским с двумя состояниями. Переключения состояний управляются дискретной цепью Маркова с матрицей переходов

P = \[ \begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} \] .

Основные характеристики укрупнённой системы с хорошей точностью (с погрешностью порядка 1 − γ) могут быть приняты в качестве характеристик реальной системы. Поэтому время пребывания реальной системы в классе состояний функционирования приблизительно равно времени пребывания укрупнённой системы в состоянии функционирования. Это время распределено показательно с параметром λ, где λ – интенсивность переходов системы из состояния функционирования в состояние перераспределения файлов.

На укрупнённую систему, находящуюся в состоянии функционирования, действует пуассоновский поток событий с интенсивностью λ, переводящий её в состояние перераспределения файлов. Из состояния перераспределения файлов система переходит в состояние функционирования. Пусть t_a – среднее время перераспределения файлов, тогда интенсивность переходов из состояния перераспределения файлов в состояние функционирования μ = 1 / t_a. Граф переходов укрупнённой системы показан на рисунке 5.

Поведение вероятностей p₁(t) и p₂(t) состояний укрупнённой системы описывается уравнениями Колмогорова [4]:

dp₁(t)/dt = μ p₂(t) − λ p₁(t),
dp₂(t)/dt = λ p₁(t) − μ p₂(t). (3)

Пусть в начальный момент времени укрупнённая система находилась в состоянии функционирования: p₁(0) = 1, p₂(0) = 0. Тогда решения уравнений (3) имеют вид:

p₁(t) = μ/(λ + μ) + (λ/(λ + μ)) e^−(λ+μ)t,
p₂(t) = λ/(λ + μ) − (λ/(λ + μ)) e^−(λ+μ)t. (4)

При больших значениях времени в укрупнённой системе устанавливается стационарный режим: p₁ = μ/(λ + μ), p₂ = λ/(λ + μ).

Обозначим τ_i – среднее время пребывания системы в i-м состоянии функционирования, ρ_i – вероятность пребывания системы в этом состоянии, q_i – вероятность перехода системы из i-го состояния функционирования в состояние перераспределения файлов. Для определения значений T и D_T (математического ожидания и дисперсии времени пребывания системы в классе состояний функционирования) используются известные соотношения [4].

Пусть состояния функционирования системы равновероятны: ρ_i = 1/s, а переходы системы из каждого состояния функционирования в состояние перераспределения файлов также равновероятны: q_i = 1/s. В этом случае среднее время T пребывания системы в классе состояний функционирования до перехода в состояние перераспределения файлов определяется по формуле

T = ∑_i=1^s τ_i. (7)

Обозначим θ – среднее значение интервала между событиями при использовании мониторингов. Поскольку длительность мониторинга значительно меньше времени T, для определения θ можно использовать известную формулу [4]: θ = T + D_T/T, из которой, с учётом свойств экспоненциального распределения, получаем θ = 2T.

Таким образом, если мониторинги применяются, поток событий представляет собой поток Эрланга второго порядка с интенсивностью Λ = 1/θ = λ/2.

Определим оптимальную периодичность мониторингов. Обозначим Ω – пауза между мониторингами, t_mon – время проведения мониторинга. Целевая функция при периодическом мониторинге состоит из двух частей. Во-первых, число мониторингов и время t_mon должны быть минимальными, чтобы задержка обработки запросов к файлам, вызванная мониторингом, была минимальной. Для выполнения этого условия необходимо минимизировать величину t_mon/Ω. Во-вторых, на интервале θ событие (момент необходимости перераспределения файлов) должно быть распознано с минимальной задержкой. Максимальная задержка опознания события возникает, если событие произошло сразу после окончания мониторинга и равна Ω + t_mon, минимальная – если событие возникло во время мониторинга и не превышает t_mon. Для минимизации задержки необходимо, чтобы время между мониторингами на интервале θ было минимальным, то есть чтобы отношение Ω/θ было минимально.

Таким образом, целевая функция задачи определения оптимального времени между мониторингами имеет вид E(Ω) = t_mon/Ω + Ω/θ → min. Решив уравнение dE/dΩ = 0, найдём значение Ω, при котором функция E достигает минимума:

Ω_opt = t_mon · θ. (9)

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

Выводы

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

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