Вычисление обьема памяти узлов компьютерной сети при рациональном размещении файлов

Аннотация

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

Общая постановка проблемы

При проектировании распределенной системы необходимо стремиться к рациональному размещению файлов по узлам компьютерной сети. Если задача рационального размещения файлов не будет решена, то это может привести к перегрузке каналов связи и неэффективной работе распределенной системы. Поэтому одной из целей проектирования компьютерной сети является синтез оптимального плана размещения m файлов по n узлам сети с учетом особенностей функционирования распределенной системы [1]. В работах [2] показано, что рациональное размещение файлов может быть получено жадными методами. Однако влияние объема памяти узлов на качество размещения не исследовано.

Если память узлов не ограничена, то размещение файла i не зависит от размещения файла (i-1) и матрица размещений представляет собой систему независимых векторов (матроид). Известно [3], что строго точное решение задачи на матроиде определяется с помощью жадного метода. Если память узлов ограничена, то жадный метод находит только приближенное решение задачи размещения файлов. Относительную погрешность метода можно вычислить по формуле: Q ? (M ? A /) M , где M - максимально возможное решение задачи (решение задачи на матроиде), A - приближенное решение задачи, получаемое жадным методом. Чрезмерно большой запас памяти для размещения файлов в узлах экономически невыгоден. Поэтому важной задачей, возникающей при проектировании распределенных систем, является выбор оптимального объема памяти узлов компьютерной сети, который обеспечивает минимальную погрешность решения задачи распределения файлов по узлам.

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

Исследования

В задаче размещения файлов по узлам компьютерной сети необходимо так распределить файлы по узлам компьютерной сети, чтобы время отклика сети было минимальным. Критерием оптимальности размещения файлов является суммарный поток локальных запросов, инициированных в узлах в единицу времени. Чем больше суммарный поток локальных запросов, тем меньше время отклика сети. Исходные данные задачи размещения файлов показаны в таблице 1.

Таблица 1 – Исходные данные задачи размещения файлов

Пусть X_ij=1, если i-й файл расположен в j –м узле, иначе - X_ij=0.Введем условные обозначения, показанные в таблице 2.

Коэффициент заполнения a_ij характеризует объем памяти j-го узла, оставшийся свободным после размещения i-го файла в этот узел. Переполнение узлов недопустимо, поэтому a_ij≤1.Для экономии памяти коэффициент заполнения узлов необходимо максимизировать.

Таблица 2 – Условные обозначения

Коэффициент использования ρ_ij является индикатором перегрузки узлов при обработке запросов к файлам. Очереди запросов возникают, если ρ_ij≥1. Для предотвращения перегрузки можно регулировать время обработки файлов в узлах T_ij так, чтобы выполнялось условие 0<ρ_ij<1.

Маршрутный коэффициент β_ij характеризует маршрутизацию запросов к файлам. Число промежуточных узлов на любом маршруте не превышает значения (n-1) поэтому 1/n≤β_ij<1. Для ускорения обработки запросов за счет сокращения длины их маршрутов коэффициент β_ij необходимо максимизировать. Наименее нагруженные маршруты между узлами могут быть найдены сетевыми процессорами

Уровень запросов к файлам характеризует объем сетевого трафика. Для повышения эффективности функционирования сети за счет снижения времени отклика можно максимизировать уровень локальных запросов в сети, решив задачу рационального размещения файлов по узлам (1)-(3).

Максимизация уровня локальных запросов в сети:

Ограничения на число копий файлов:

Ограничения на объемы памяти узлов:

раммирования с булевскими переменными. В задаче (1)-(3) необходимо найти матрицу размещений файлов X. В задаче максимизируется суммарный поток локальных запросов. Увеличение потока локальных запросов связано с увеличением эффективности функционирования сети следующим образом.

Пусть - суммарная интенсивность всех запросов, - суммарная интенсивность локальных запросов, - суммарная интенсивность сетевых запросов, R₀ - среднее время выполнения сетевого запроса, X₀- максимальная пропускная способность сети, R - среднее время отклика сети. Среднее время отклика на один запрос совпадает со средним временем ожидания обслуживания сетевого запроса. Оно состоит из среднего времени доступа к каналу связи и среднего времени выполнения запроса. Значение R определяется по формуле: . Критерий задачи размещения файлов обеспечивает максимизацию значений и, следовательно, минимизацию значения R .

Для размещения файлов используется жадный метод, работа которого состоит из двух этапов. На первом этапе находятся для файла i те узлы, в которые файл помещается по размеру. Второй этап выполняется, пока не размещены все копии файла. На втором этапе, среди найденных узлов определяется узел с наибольшим значением L_ij=F_ijV_i/B_j,i=1,2,...,m,j=1,2,...,n и файл размещается в этот узел. Временная сложность метода -

Для проверки полученных теоретических результатов проведены вычислительные эксперименты. В каждой серии экспериментов решены задачи распределения m файлов по n узлам жадным методом, r_i=1,i=1...m.

На первом этапе метода определяются те узлы, в которые файл помещается по размеру. На втором этапе, среди найденных узлов определяется узел с наибольшей интенсивностью запросов, и файл размещается в этот узел. Временная сложность метода - O(mn).

Результаты вычислительных экспериментов подтверждают зависимость относительной погрешности распределения файлов от памяти узлов. На рис. 1 – 3 показано, что в переходной зоне относительная погрешность решения снижается с увеличением размера памяти компьютеров.

Выводы

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

Список использованной литературы

1. Зинкин С.А., Белецкий П.А. Оптимизация размещения данных по узлам информационно-вычислительной сети. Материалы международной научной конференции «Современные тенденции технических наук». – Уфа: 2013. – С. 29-31.
2. Бєльков Д.В. Методи і обчислювальні структури для розміщення файлів в комп’ютерних мережах. Автореферат дисертації. Донецьк: 2004.–21 с.
3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985. - 512 с.
4. Баранов В.И. Применение методов комбинаторного анализа при проектировании алгоритмов управления распределением памяти ЭВМ. //Программирование. – 1985. - № 4. - C. 33-38.
5. Стечкин Б.С. Экстремальные свойства разбиения чисел. //Доклады АН СССР. – 1982. - т. 264. - № 4. - С. 833-836.