Использование методов дискретной оптимизации для решения задач распределения ресурсов при применении технологии виртуальных машин в корпоративных сетях

П.А. Рахман

(Москва, Московский Энергетический Институт, Российская Федерация)

На сегодняшний день технология виртуальных машин является одним из наиболее эффективных подходов к повышению загрузки вычислительных ресурсов корпоративной сети. Эта технология позволяет размещать на компьютере несколько ОС на базе виртуальных платформ, при этом ОС остаются изолированными друг от друга так же, как если бы они размещались бы на нескольких компьютерах. Однако, современные корпоративные сети – это, как правило, множество компьютеров и множество ОС, работающих на них. Компьютеры предоставляют некоторый набор ресурсов определенных типов и емкостей, а ОС предъявляет некоторые требования к этим ресурсам. Соответственно, для получения максимальной эффективности от применения технологии виртуальных машин необходим некоторый оптимальный план распределения виртуальных машин с установленным на них программным обеспечением (будем их называть логическими серверами) на компьютеры. Критериями оптимизации могут служить уровни загрузок ресурсов компьютеров. Таким образом, имеет место быть многокритериальная задача поиска оптимального распределения множества потребителей, требующих множества видов ресурсов, на множество поставщиков этих ресурсов. Ключевой особенностью задачи является то, что за счет использования технологии виртуальных машин, мы пытаемся освободить некоторое множество компьютеров, причем идем к этой цели, добиваясь максимально эффективного использования ресурсов компьютеров. Однако очень важно подчеркнуть то, что можно сделать ошибку и пытаться добиваться эффективной загрузки ресурсов физических компьютеров всех сразу и тем самым решить задачу балансировки нагрузки. В таком случае нагрузка будет распределена так, чтобы ни один физический компьютер не простаивал, и не было так, чтобы один компьютер сильно загружен, а другой очень слабо. Этим мы лишь добьемся приблизительно равномерной загрузки ресурсов среди множества физических компьютеров, и ни один физический компьютер не будет освобожден. Истинная цель – решить задачу, обратную задаче балансировки нагрузки, то есть сосредоточить логические серверы на некотором множестве компьютеров таким образом, чтобы задействованные компьютеры были загружены максимально, а все незадействованные компьютеры были совершенно свободны и могли бы быть использованы для альтернативных целей.

Целью работы являлось обзор методов решения задачи поиска оптимального распределения, и разработка комбинированного метода на базе нескольких известных методов дискретной оптимизации. Задача поиска оптимального распределения является достаточно трудоемкой, несмотря на то, что поиск ведется в дискретном булевом пространстве: конкретная виртуальная машина может размещаться либо не размещаться на конкретном компьютере. Однако, именно дискретность и усложняет задачу, поскольку существующие точные методы оптимизации, такие как симплекс-метод, рассчитаны на поиск решений в непрерывном пространстве, а целочисленные модификации симплекс-метода имеют определенные сложности из-за погрешностей машинной арифметики, кроме того они предназначены для решения задач небольших размерностей, поскольку в определенных случаях не застрахованы от полного перебора целочисленных решений. Соответственно, точное решение при решении задач оптимизации в булевом пространстве можно получить только полным перебором. При NS виртуальных машин и NH компьютеров объем полного перебора составляет (NH+1)^NS, очевидно то, что при больших размерностях задачи поиск решения за приемлемое время невозможно. Соответственно, в данной ситуации используются приближенные методы. В первом приближении, самое простое – это последовательное размещение логических серверов по компьютерам, при рассмотрении каждого компьютера по очереди. При этом для каждого компьютера в отдельности решается задача булевого линейного программирования для нахождения оптимального набора среди еще нераспределенных логических серверов. Таким образом, задача разбивается на два уровня: локальный уровень, оптимизация загрузки ресурсов конкретного компьютера, и глобальный уровень, простое последовательное рассмотрение компьютеров без каких-либо критериев или приоритетов выбора компьютера. Общий перебор при решении задачи распределения в худшем случае составляет NH*2^NS, в случае если на локальном уровне подзадачи решаются полным перебором. Однако, при таком подходе совсем не проводится оптимизация на глобальном уровне – компьютеры рассматриваются в произвольном порядке и не учитывается то, что выбор каких-либо конкретных компьютеров мог бы быть более оптимальным нежели чем выбор других. Поэтому здесь требуется некоторое компромиссное решение между полным перебором и простым последовательным размещением логических серверов на каждый компьютер до тех пор, пока все серверы не будут распределены. Соответственно, вместо простого последовательного рассмотрения компьютеров, можно на каждом шаге глобального уровня выбирать не произвольный, а наилучший по загрузке ресурсов компьютер. На каждом шаге глобального уровня решаются подзадачи булевого линейного программирования для всех еще незадействованных компьютеров для размещения на них набора из оставшихся нераспределенными логических серверов, и выбирается наилучший компьютер. Таким образом, если на локальном уровне подзадачи решаются полным перебором, то общий объем перебора при решении задачи распределения составит приблизительно NH*2^NS+1. На локальном уровне подзадачи представляют собой задачу булевого линейного программирования (задачу условной псевдобулевой оптимизации), для которой точное решение можно получить только полным перебором. Для решения задач псевдобулевой оптимизации на сегодняшний день существуют как точные методы решения, так и приближенные методы. Точные методы – это известные целочисленные модификации симплекс-метода [1]: метод сечений Гомори и метод ветвей и границ. Такие методы призваны находить точное решение, однако, на реальных практических задачах в силу сложных ограничений, приводят к бесконечному добавлению и удалению дополнительных сечений в методе Гомори и к полному перебору в методе ветвей и границ. Поэтому точные методы на практике пригодны для решения задач небольших размерностей. Приближенные методы [2]: локальной поиск, случайный поиск, гриди-методы, а также применение одновременно нескольких приближенных методов, например, задача решается методом локального поиска, но не однократно, а много раз для множества различных стартовых точек, выбираемых случайным образом. Такие методы позволяют решить задачи больших размерностей с линейными ограничениями любой сложности, причем за приемлемое время, однако, как правило, дают приближенное (субоптимальное) решение. Среди методов для решения подзадач на локальном уровне распределения метод локального поиска является одним из наиболее эффективных при использовании нескольких случайных стартовых точек.

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

ЛИТЕРАТУРА

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. – М.: Наука, 1979.

2. Антамошкин А.Н., Масич И.С. Эффективные алгоритмы условной оптимизации монотонных псевдобулевых функций. Вестник СибГАУ. Выпуск. 4 – Красноярск: СибГАУ, 2003.