Ubicaci´ on ´ optima de m´ aquinas virtuales. Un enfoque multiobjetivo. 1

Fabio L´ opez Pires1 , Elias Melgarejo2 y Benjam´ın Bar´ an 3 . Centro de Datos, Parque Tecnol´ ogico Itaipu, Hernandarias, Paraguay. 2,3 Facultad Polit´ ecnica, Universidad Nacional del Este. Ciudad del Este, Paraguay. 1 2

[email protected] [email protected] 3 [email protected]

Resumen El proceso de seleccionar qu´e m´ aquina virtual ser´a ubicada (i.e. ejecutada) en las m´aquinas f´ısicas disponibles en un Centro de datos es conocido como problema de ubicaci´ on de m´ aquina virtual. Este trabajo propone por primera vez una formulaci´on del problema con enfoque multiobjetivo de las principales funciones objetivos estudiadas. En el estado del arte hasta el presente, el citado problema se ha venido estudiando como problema monobjetivo. Tambi´en se propone un algoritmo mem´etico multiobjetivo para resolver el mismo problema. La validaci´ on de la formulaci´ on planteada es probada por comparaci´on experimental de resultados del algoritmo propuesto contra un algoritmo de fuerza bruta. Finalmente se verifica la escalabilidad experimental de la metaheur´ıstica empleada. Descriptores: virtualizaci´ on, asignaci´on de recursos, centro de datos, computaci´on en la nube, eficiencia energ´etica, optimizaci´ on multiobjetivo.

Abstract The process of selecting which virtual machines will be placed (i.e. executed) in the physical machines available in a Data center is known as virtual machine placement problem. This work proposes for the first time a formulation of the problem, with a multi-objective approach of the main objective functions, which so far in the state of the art have been studied as monoobjective. Also it is proposed a multi-objective memetic algorithm for solving the proposed problem. The validity of the proposed formulation is checked by comparing experimental results of the proposed algorithm with a brute force algorithm. Finally it is experimentally verified the scalability of the used meta-heuristics. Keywords: Virtualization, Resources Allocation, Datacenter, Cloud Computing, Energy Efficiency, Multi-Objective Optimization.

1. Introducci´ on. En el pasado, el dise˜ no de Centros de datos (Datacenters) se centr´ o en maximizar la capacidad de c´omputo de los sistemas, sin considerar necesariamente el alto consumo de energ´ıa y la elevada potencia requerida como factores de gran importancia ecol´ ogica y econ´ omica [9]. Debido a la creciente demanda y los constantes cambios del entorno, el dise˜ no de Centros de datos debe hoy considerar otros factores relevantes como: el consumo energ´etico, el tr´afico de red, el tiempo de configuraci´ on y los ingresos econ´omicos, entre otros factores [2].

En la actualidad, la virtualizaci´ on se ha convertido en una tecnolog´ıa muy utilizada en los Centros de datos gracias a la posibilidad de abstracci´on que posibilita crear entornos independientes de ejecuci´ on (m´aquinas virtuales) para atender los requerimientos de los usuarios con las m´ aquinas f´ısicas disponibles. As´ı, la virtualizaci´ on posibilita que un conjunto de m´ aquinas f´ısicas, gestionadas de forma centralizada, pueda alojar m´ ultiples m´aquinas virtuales, posibilitando adem´as el movimiento transparente de una m´aquina virtual entre diversas m´ aquinas f´ısicas mediante lo que se conoce como live migration [4]. En este contexto, se conoce como problema de

Ubicaci´ on ´optima de m´ aquinas virtuales. Un enfoque multiobjetivo. ubicaci´on de m´ aquinas virtuales, en ingl´es virtual machine placement (VMP) [3], al proceso de seleccionar que m´aquinas virtuales ser´an ubicadas (i.e., ejecutadas) en cada m´ aquina f´ısica disponible en un Centro de Datos. La existencia de una considerable cantidad de m´aquinas f´ısicas y virtuales en los modernos Centros de Datos, conlleva una gran cantidad de criterios que pueden ser tenidos en cuenta al momento de seleccionar una posible soluci´ on, dependiendo de las prioridades y criterios de optimizaci´on, pudiendo incluso estos cambiar en determinados momentos, lo que implica una variedad de posibles formulaciones del problema y de los objetivos a optimizar [2]. En este contexto, L´opez y Bar´ an presentaron en [2] una taxonom´ıa de los trabajos m´as relevantes relacionados al problema de la ubicaci´ on de m´ aquinas virtuales, publicados en los u ´ltimos a˜ nos en la biblioteca digital de la IEEE Xplore (http://ieeexplore.ieee.org). Seg´ un esta taxonom´ıa, los objetivos de optimizaci´ on m´ as estudiados son: (1) la minimizaci´ on del consumo energ´etico, (2) la minimizaci´on del tr´afico de red y (3) la maximizaci´ on de ingresos econ´ omicos.Estos objetivos han sido estudiados separadamente en la literatura, con un enfoque esencialmente monobjetivo, por lo que este trabajo propone por primera vez una formulaci´ on del problema, considerando simult´aneamente estos tres objetivos, con un enfoque puramente multiobjetivo [6]. Una vez formulado el problema de ubicaci´on de m´ aquinas virtuales como un problema de optimizaci´ on multiobjetivo, resulta importante la selecci´ on de una t´ecnica adecuada para resolver esta nueva formulaci´on matem´ atica. Como antecedente, se destaca que las t´ecnicas de resoluci´ on estudiadas en [2] abarcan tanto t´ecnicas determin´ısticas como heur´ısticas y meta-heur´ısticas alternativas. Entre las t´ecnicas determin´ısticas se estudiaron tanto la programaci´ on lineal como los algoritmos basados en reglas, los cuales resultan impracticables en Centros de Datos con grandes cantidades de m´ aquinas f´ısicasy virtuales. Como t´ecnicas alternativas, se sugieren en [2] heur´ısticas como algoritmos voraces (Greedy Algorithm) y heur´ısticas distribuidas, as´ı como meta-heur´ısticas bioinspiradas como algoritmos gen´eticos (del ingl´es Genetic Algorithm, abreviado GA) y optimizaci´on con enjambres de part´ıculas (del ingl´es Particle Swarm Optimization, abreviado PSO). Analizadas las alternativas, este trabajo propone por primera vez la utilizaci´on de un algoritmo mem´etico multiobjetivo [7] para resolver el problema de ubicaci´ on de m´ aquinas virtuales en un contexto puramente multiobjetivo. En la siguiente secci´on se trata la formulaci´on matem´ atica de la optimizaci´ on multiobjetivo. La secci´ on 3 presenta el modelo matem´atico propues-

to para el problema de ubicaci´on ´ optima de m´ aquinas virtuales con un enfoque multiobjetivo. En la secci´ on 4 se detalla la formulaci´on de cada funci´ on objetivo considerada en este trabajo. El algoritmo mem´etico multiobjetivo propuesto es introducido en la secci´on 5, mientras la secci´on 6 muestra los resultados experimentales. Finalmente, la secci´on 7 presenta las conclusiones de este trabajo y propone posibles trabajos futuros.

2. Optimizaci´ on multiobjetivo. Los problemas de optimizaci´on multiobjetivo intentan encontrar un vector (variable independiente) que simult´aneamente optimice (maximice o minimice) m´ ultiples variables dependientes (u objetivos). Los objetivos generalmente est´an en competencia, es decir, mejorar un objetivo puede empeorar otro, por lo que no siempre resulta posible obtener una u ´nica soluci´on al problema que sea totalmente mejor que las dem´ as soluciones, como ocurre en la optimizaci´ on monobjetivo. Consecuentemente, en la optimizaci´ on de m´ ultiples objetivos generalmente se termina calculando un conjunto de soluciones o´ptimas de compromiso (trade-off ) conocido como conjunto Pareto [6]. Formalmente, un problema de optimizaci´ on de m´ ultiples objetivos puede definirse como: Optimizar: y = f(x) = [f1 (x) f2 (x) . . . fk (x)] Sujeto a: e(x) = [e1 (x) e2 (x) . . . em (x)] donde x = [x1 x2 . . . xn ] ∈ X y = [y1 y2 . . . yn ] ∈ Y En esta formulaci´on, X representa el dominio de definici´ on del problema mientras que Y representa el espacio objetivo; en este contexto, se denomina soluci´on factible a una soluci´on x que atiende las restricciones del problema. Es relevante destacar que para hablar de la relaci´ on entre posibles soluciones de un problema de m´ ultiples objetivos (k > 1), se debe introducir formalmente el concepto de Dominancia Pareto. Se dice que una soluci´ on factible u ∈ X, domina a otra soluci´on factible v ∈ X, si u no es peor que v al considerar cada funci´on objetivo y es estrictamente mejor en al menos un objetivo. El conjunto de todas las soluciones factibles no dominadas se conoce como conjunto Pareto mientras que su imagen en el espacio objetivo se conoce como frente Pareto. Finalmente, se destaca que al referirse a la relaci´ on de dominancia entre dos soluciones factibles u y v , se utiliza la siguiente notaci´ on: 12

Ubicaci´ on ´optima de m´ aquinas virtuales. Un enfoque multiobjetivo. u  v u domina a v (i.e., u es mejor que v ), u ≺ v u es dominada por v (i.e., v es mejor que u), u ∼ v u no es comparable con v (i.e., ninguna soluci´ on es mejor que la otra.

3. Modelo matem´ atico. Dado un conjunto de m´aquinas f´ısicas H = H1 , H2 , . . . , Hn y un conjunto de m´aquinas virtuales V = V1 , V2 , . . . , Vm , se desea encontrar la ubicaci´on ´optima de las m´ aquinas virtuales en las m´aquinas f´ısicas de forma a satisfacer los requerimientos de recursos del conjunto V, optimizando las tres funciones objetivos arriba citadas (minimizar el consumo energ´etico, minimizar el tr´afico de red y maximizar los ingresos econ´omicos) que se formalizar´an en la siguiente secci´ on. A. Datos de entrada. Cada m´ aquina f´ısica Hi cuenta con recursos de procesamiento (MIPS), memoria (MB), almacenamiento (GB) y consumo m´ aximo de potencia (W) representados como: Hi = {Hcpui , Hrami , Hhddi , ρmaxi }. Cada m´ aquina virtual Vj requiere recursos de procesamiento (MIPS), memoria (MB) y almacenamiento (GB), adquiridos a un costo econ´ omico ($), representados como: Vj = {V cpuj , V ramj , V hddj , Rj }. Cada m´ aquina virtual Vj requiere de recursos de comunicaci´ on (Kbps) con otras m´aquinas virtuales. Estos recursos de comunicaci´ on son representados como: Tj = {Tj1 , Tj2 , . . . , Tjm , }, donde Tjk representa la tasa promedio de comunicaci´ on, medida en Kbps, entre la m´ aquina virtual Vj y la m´ aquina virtual Vk . B. Datos de salida. Lo que se precisa calcular es la ubicaci´ on de las m´aquinas virtuales Vj en las m´ aquinas f´ısicas Hi necesarias, atendiendo los criterios de optimizaci´ on multiobjetivo a ser descritos en la secci´on 4. Una ubicaci´ on (o posible soluci´ on del problema) es representada por una matriz P = {Pji } de dimensi´ on (mxn), conocida como Placement, donde Pji ∈ {0, 1} indica si la m´ aquina virtual Vj es ubicada (Pji = 1) o no es ubicada (Pji = 0) para su ejecuci´ on en la m´ aquina f´ısica Hi (i.e. Pji : Vj → Hi ). C. Restricciones. Una m´ aquina virtual Vj puede ser ubicada para su ejecuci´on en una u ´nica m´aquina f´ısica Hi o alternativamente, puede no ser ubicada para su ejecuci´on en ninguna m´aquina f´ısica Hi . En consecuencia, esta restricci´ on se expresa como: n  i=1

Pij ≤ 1 ∀ j ∈ {1, 2, . . . m}

(1)

donde: n: Cantidad de m´aquinas f´ısicas Hi Pji : Variable binaria que vale 1 si la m´aquion en la na virtual Vj es ubicada para su ejecuci´ m´ aquina f´ısica Hi . Caso contrario vale 0. m: Cantidad de m´ aquinas virtuales Vj Una m´ aquina f´ısica Hi debe contar con suficientes recursos disponibles para atender los requerimientos de todas las m´ aquinas virtuales Vj que sean ubicadas para su ejecuci´ on en Hi . En consecuencia, este conjunto de restricciones puede formularse matem´aticamente como: m 

V cpuj × Pji ≤ Hcpui

(2)

V ramj × Pji ≤ Hrami

(3)

j=1 m  j=1 m 

V hddj × Pji ≤ Hhddi

(4)

j=1

∀ i ∈ {1, 2, . . . , n}, i.e., para cada una de las m´ aquinas Hi donde: m: cantidad de m´ aquinas virtuales Vj n: cantidad de m´ aquinas f´ısicas Hi Pji : variable binaria que vale 1 si la m´ aquina virtual Vj es ubicada para su ejecuci´ on en la m´ aquina f´ısica Hi . Caso contrario vale 0. V cpuj : requerimientos de procesamiento de la m´ aquina virtual Vj Hcpui : recursos de procesamiento de la m´ aquina f´ısica Hi V ramj : requerimientos de memoria de la m´ aquina virtual Vj Hrami : recursos de memoria de la m´aquina f´ısica Hi V hddj : requerimientos de almacenamiento de la m´ aquina virtual Vj Hhddi : recursos de almacenamiento de la m´ aquina f´ısica Hi

4. Funciones objetivos. El problema de ubicaci´on o´ptima de m´ aquinas virtuales puede ser definido como un problema de optimizaci´ on multiobjetivo (presentado en la secci´on 2, usando la notaci´on definida en la secci´on anterior, al considerarse la optimizaci´on simultanea de varios objetivos. En este trabajo, se propone optimizar las siguientes tres funciones objetivos: A. Minimizaci´ on del consumo energ´etico. En [9], Wang et al. presentan la ecuaci´ on 5 para calcular el consumo energ´etico por unidad de tiempo, representado por la sumatoria del consumo energ´etico de cada m´ aquina f´ısica Hi . 13

Ubicaci´ on ´optima de m´ aquinas virtuales. Un enfoque multiobjetivo.

E=

n 

(ρmaxi − ρmini ) × U cpui + ρmini

(5)

i=1

Inspirado en la ecuaci´ on 5, este trabajo propone la ecuaci´ on 6 que contempla la posibilidad de apagar las m´ aquinas f´ısicas Hi que no ejecutan m´ aquina virtual alguna, de forma a minimizar el consumo energ´etico E=

n 

((ρmaxi −ρmini )×U cpui +ρmini )×Yi (6)

i=1

E: consumo energ´etico total por unidad de tiempo (W) de las m´aquinas f´ısicas. n: cantidad de m´ aquinas f´ısicas Hi ρmaxi : consumo m´aximo de potencia de la m´aquina f´ısica Hi ρmini : consumo m´ınimo de potencia de la m´aquina f´ısica Hi . Seg´ un [9] ρmaxi ≈ ρmini ∗ 0,01 on de recursos U cpui : porcentaje de utilizaci´ de procesamiento de la m´aquina f´ısica Hi Yi : variable binaria que vale 1 si Hi est´ a encendida. Caso contrario vale 0. B. Minimizaci´ on del tr´ afico de red. En [10], Shrivastava et al. proponen minimizar el tr´ afico de red mediante la maximizaci´ on de la localidad. En este trabajo se propone la ecuaci´on 7 para calcular el tr´afico de red, representado por la sumatoria del tr´afico de cada m´ aquina virtual Vj , que se encuentre ubicada para su ejecuci´on en una m´ aquina f´ısica Hi , con las otras m´aquinas virtuales Vk que se encuentren ubicadas para su ejecuci´on en otra m´ aquina f´ısica Hq , (i = q). T =

m m  

(Tjk × Djk )

(7)

j=1 k=1

donde: T: tr´ afico de red total (Kbps) entre las m´ aquinas f´ısicas. m: cantidad de m´ aquinas virtuales. Tjk : tasa promedio de comunicaci´on (Kbps) entre Vj y Vk . Djk : variable binaria que vale 1 si Vj y Vk est´ an ubicadas en m´aquinas f´ısicas diferentes. Caso contrario vale 0. Se hace notar que dos m´ aquinas virtuales Vj y Vk que est´an ubicadas para su ejecuci´on en una misma m´ aquina f´ısica Hi no contribuyen a incrementar el tr´afico de red total T dado por la ecuaci´on 7, pues en este caso Djk = 0. C. Maximizaci´ on del ingreso econ´ omico. En este trabajo se propone la ecuaci´ on 8 para calcular el ingreso econ´omico que recibir´a un Centro de datos al atender los requerimientos de sus clientes, representado por la sumatoria de los ingresos econ´ omicos proporcionados por cada

m´ aquina virtual Vj que sea efectivamente ubicada para su ejecuci´ on en una m´ aquina f´ısica Hi . m 

(Rj × Xj )

(8)

j=1

donde: R: ingreso econ´omico total ($) m: cantidad de m´ aquinas virtuales Rj : ingreso econ´ omico por ubicar para su ejecuci´ on la m´ aquina virtual Vj Xj : variable binaria que vale 1 si Vj est´ a ubicada para su ejecuci´ on en una m´ aquina f´ısica. Caso contrario vale 0.

5. Agoritmo mem´ etico multiobjetivo. Este trabajo propone resolver el problema multiobjetivo de ubicaci´on de m´ aquinas virtuales, utilizando por primera vez un algoritmo mem´etico [7], cuyos detalles se presentan a continuaci´on, recordando que un algoritmo mem´etico puede ser entendido como un algoritmo evolutivo que adem´as de utilizar los tradicionales operadores de selecci´on, cruzamiento y mutaci´on, incluye un optimizador local que ayuda a obtener buenas soluciones, a´ un en las primeras generaciones de un algoritmo evolutivo [7]. A. Representaci´ on del Cromosoma. En [11], Jing y Fortes proponen la representaci´ on del cromosoma (representado como C) presentada en la Fig. 1. La misma se basa en las m´ aquinas f´ısicas (representadas como H ), adjuntando a cada una de ellas un conjunto de m´aquinas virtuales (representadas como V ) que est´ an ubicadas para su ejecuci´on en cada m´ aquina f´ısica.

Figura 1. Representaci´ on del cromosoma propuesto por Jing y Fortes.

La representaci´on propuesta por Jing y Fortes presenta desventajas en complejidad de estructuras de datos para su programaci´on y costos de acceso para su evaluaci´ on. En consecuencia, en este trabajo se propone representar el cromosoma como un vector de dimensi´on m, C = [C1 , C2 , . . . , Cm ], donde Ck representa la m´ aquina f´ısica en la que se ejecuta una m´ aquina virtual, por lo que Ck ∈ N; 0 ≤ Ck ≤ n, donde Ck representa la m´ aquina f´ısica Hi en la que se ubica para su ejecuci´ on la m´ aquina virtual Vk . Si Ck = 0, la m´ aquina virtual Vj no ha sido ubicada para su ejecuci´ on en ninguna m´aquina f´ısica, por lo que no 14

Ubicaci´ on ´optima de m´ aquinas virtuales. Un enfoque multiobjetivo. redituar´ a ingresos econ´ omicos a la hora de calcular la funci´ on objetivo R, dada por la ecuaci´on (8). Con esto se simplifica la estructura de datos para su programaci´ on y el acceso para la evaluaci´on de los datos. La representaci´on del cromosoma, propuesta en este trabajo, es presentada en la Fig. 2.

Figura 2. Representaci´ on del cromosoma propuesto.

B. Pseudoc´ odigo. En el pseudoc´odigo 1 se presenta el algoritmo mem´etico multiobjetivo propuesto en este trabajo como t´ecnica para la soluci´on del problema de ubicaci´ on de m´ aquinas virtuales. Este pseudo-c´ odigo utiliza como base el algoritmo mem´etico patr´ on definido en [7]. B´asicamente, el algoritmo mem´etico presentado en el pseudoc´ odigo 1 trabaja de la siguiente forma: En el paso 01 se genera un conjunto de soluciones aleatorias P0, cuyas soluciones se reparan (paso 02) para asegurar que sean factibles, para luego intentar optimizarlas (paso 03) utilizando b´ usqueda local. Con las soluciones no dominadas as´ı obtenidas, se genera en el paso 04 el primer conjunto Pc (aproximaci´ on al conjunto Pareto). Una vez inicializada la poblaci´on evolutiva Pt (pasos 05 y 06), se inicia la evoluci´on en los ciclos comprendidos entre los pasos 07 y 15. El proceso evolutivo sigue b´asicamente el mismo comportamiento: se seleccionan soluciones de la uni´ on de Pc con Pt (paso 08), se aplican los operadores de cruzamiento y mutaci´ on (paso 09), y eventualmente las soluciones son reparadas, ya que pueden haber soluciones no factibles (paso 10). En el paso 11 se intenta mejorar las soluciones obtenidas utilizando b´ usqueda local (con operadores de optimizaci´ on local), mientras que en el paso 12 se actualiza el contador de generaciones (o iteraciones). En el paso 13 se actualiza la aproximaci´ on al conjunto Pareto Pc (si corresponde), mientras que en el paso 14 se actualiza la nueva poblaci´ on evolutiva Pt. El proceso evolutivo se repite hasta cumplir con un criterio de parada (como un n´ umero m´ aximo de generaciones), retornando finalmente el conjunto de soluciones no dominadas Pc encontradas por el algoritmo. C. Inicializaci´ on de soluciones. La inicializaci´on de soluciones es el proceso de generaci´on aleatoria de la poblaci´on P0 compuesta de individuos C = [C1 , C2 , . . . , Cm ]. Los posibles valores que puede tomar Ck para m´aquinas virtuales Vj est´ an en el rango [0; n]. Cada cromosoma C

puede ser mapeado un´ıvocamente a una soluci´on P (descrita en la secci´ on 3), como se ilustra en el siguiente ejemplo. Ejemplo 1. El cromosoma C = [1, 1, 1, 2, 2, 2, 2, 3, 3] de la Fig. 2 es representado en la ec. (9) utilizando la notaci´ on matem´atica de la secci´ on 3 para la matriz soluci´on P. ⎡ ⎤ 1 0 0 ⎢1 0 0⎥ ⎢ ⎥ ⎢1 0 0⎥ ⎢ ⎥ ⎢0 1 0⎥ ⎢ ⎥ ⎥ Soluci´ on P = ⎢ (9) ⎢0 1 0⎥ ⎢0 1 0⎥ ⎥ ⎢ ⎢0 1 0⎥ ⎢ ⎥ ⎣0 0 1⎦ 0 0 1 Es importante recordar que: − Si Cj = 0, entonces Pji = 0, ∀ i ∈ {1, 2, . . . , n}, i.e., Vj no se ubica en ninguna m´ aquina f´ısica (por lo que no redituar´a el ingreso econ´omico Rj ). − Si Cj = k, entonces Pjk = 1, mientras Pjk = 0, ∀ k  = k, i.e., Vj solo se ubica en la m´ aquina f´ısica Hk . Pseudoc´ odigo 1. Algoritmo mem´etico multiobjetivo propuesto.

P0 P0

Qt Q t

01: Inicializar conjunto de soluciones P0 02: P0 ← reparar las soluciones de P0 03: P0 ← aplicar b´ usqueda local a soluciones de 04: Actualizar soluciones no dominadas Pc desde 05: 06: 07: 08: 09: 10: 11:

t←0 Pt ← P0 Mientras no se cumple criterio de parada Qt ← seleccionar soluciones de Pt ∪ Pc Qt ← variar individuos de Qt Qt ← reparar soluciones de Qt Q usqueda local a soluciones de t ← aplicar b´

12: incrementar t 13: Actualizar soluciones no dominadas Pc desde 14: Pt ← selecci´ on por ranking desde Pt ∪ Q t 15: Fin mientras 16: Retornar aproximaci´ on al conjunto Pareto Pc

D. Reparaci´ on de soluciones no factibles. Con la generaci´on aleatoria de soluciones de la inicializaci´ on (paso 01 del peudoc´odigo 1) y/o soluciones generadas por operadores gen´eticos (paso 09 del pseudoc´odigo1) se podr´ıan obtener soluciones no factibles en las que los recursos requeridos por las m´ aquinas virtuales ubicadas para su ejecuci´ on en determinadas m´aquinas f´ısicas podr´ıan superar los recursos disponibles. 15

Ubicaci´ on ´optima de m´aquinas virtuales. Un enfoque multiobjetivo. La
reparaci´ on
de
estas
soluciones
no
factibles
crowding distance. (l´ıneas
02
y
10
del
pseudoc´ odigo
1)
se
realiza
en
G. Selecci´ on y Cruzamiento. dos
etapas:
Inicialmente,
en
el
proceso
de
verifiEn este trabajo se propone realizar la selecci´on caci´ on
de
factibilidad,
se
clasifican
las
soluciones
de individuos para el cruzamiento y mutaci´ on mede
la
poblaci´on
en
factibles
y
no
factibles
(pseudiante el m´etodo de Torneo binario (Binary Tourdoc´ odigo
2).
Posteriormente,
en
el
proceso
de
renament) [6]. paraci´ on
de
soluciones
no
factibles
(pseudoc´ odigo
El m´etodo de cruzamiento utilizado en esta 3),
se
reparan
las
soluciones
que
no
cumplen
con
propuesta es el cruzamiento de corte en un solo los
criterios
de
factibilidad.
N´ otese
que
en
el
paso
punto [6]. En este trabajo, los individuos selec03
del
pseudoc´ odigo
3,
la
migraci´ on
de
Vj
a












cionados son reemplazados en la poblaci´ on ascenaquinas
f´ısicas
Hi}
Hi}puede
realizarse
a
otras
m´ diente por los individuos descendientes. que
se
encuentren
encendidas
o
apagadas. E. B´ usqueda local. Pseudoc´ odigo 2. Verificaci´ on de factibilidad. 01: Mientras existan soluciones no verificadas haCuando todas las soluciones de una poblaci´ on cer son factibles, se realiza una b´ usqueda local ( paso 02: factible ← verdadero, i ← 1 03 y 11 del pseudoc´odigo 1 con el objetivo de me03: Mientras (i < n y factible = verdadero) haga jorar las soluciones hasta el momento encontradas 04: Si Hi no cuenta con suficientes recursos pausqueda local en la poblaci´ on Pt . El proceso de b´ ra alojar todas las m´ aquinas virtuales que le se presenta en el pseudoc´odigo 4. han sido asignadas Por cada individuo de la poblaci´ on Pt se realiza 05: factible ← falso un intento de optimizarlo con una b´ usqueda local 06: incrementar i (paso 02 del pseudoc´ odigo 4). Para esto, con una 07: Fin mientras probabilidad de 1/2, se intenta maximizar la can08: Si (factible = falso) tidad de m´ aquinas virtuales atendidas ubicando 09: reparar la soluci´ on en lo posible a las m´ aquinas virtuales que queda10: Fin mientras ron apagadas, lo que incrementa directamente el ingreso econ´omico total (paso 03 a 05 del pseuPseudoc´ odigo 3. Reparaci´ on de soluciones no doc´ odigo 4). Por otro lado, tambi´en con probafactibles. bilidad de 1/2, se realizan operaciones tendien01: Mientras la soluci´ on sea no factible tes a minimizar la cantidad de m´aquinas f´ısicas Identificar Hi que no cuente con suficientes 02: encendidas, reduciendo directamente el consumo recursos para alojar todas las m´ aquinas virenerg´etico total (pasos 06 a 08 del pseudoc´ odigo tuales que le han sido asignadas 4). Con este m´etodo probabil´ıstico de b´ usqueda loon de Vj a 03: Si es posible, hacer migraci´ cal se pretende lograr una equilibrada exploraci´ on Hi (i = i) del espacio de soluciones a lo largo del Frente Paun Hi , apa04: Si no es posible migrar Vj a ning´ reto para las funciones objetivo de maximizaci´ on gar Vj de ingresos y minimizaci´ on de consumo energ´etico 05: Fin mientras respectivamente. F. Funci´ on de aptitud (Fitness). Pseudoc´ odigo 4. B´ usqueda local. 01: probabilidad = n´ umero aleatorio entre 0 y 1 La funci´on de aptitud utilizada en el algoritmo 02: Para todas las m´ aquinas f´ısicas haga mem´etico multiobjetivo propuesto en este trabajo 03: Si (probabilidad ¡0,5) es la presentada por Deb et al. en [12]. Esta fun04: Intentar apagar la mayor cantidad de Hi mici´ on de aptitud define un nondomination rank en grando Vj ubicadas en Hi a Hi con capaciel que a cada individuo se le asigna un valor igual  dad disponible (i = i). a su nivel de dominancia Pareto (1 es el mayor 05: Intentar encender la mayor cantidad de Vj nivel de dominancia, 2 es el siguiente, y as´ı sucesiapagadas ubic´ andolas en Hi con capacidad vamente) [12]. Entre dos individuos con diferentes disponible. nondomination rank se considera mejor al indivi06: Si (probabilidad ≥ 0,5) duo con menor valor (mayor nivel de dominancia). 07: Intentar encender la mayor cantidad de Vj Para comparar individuos con el mismo nonapagadas ubic´ andolas en Hi con capacidad domination rank se define un crowding distance, disponible. cuya idea b´ asica es hallar la distancia euclidia08: Intentar apagar la mayor cantidad de Hi migrando na (debidamente normalizada cuando los objetiH. Mutaci´ on. vos tienen unidades diferentes) entre cada par de Para este trabajo se propone un m´etodo de individuos, bas´andose en los k objetivos que se mutaci´ on en el que cada gen es mutado seg´ un una tengan en un hiperespacio k-dimensional [12]. Enprobabilidad ρ = 1/m , donde m representa la tre dos individuos con el mismo nondomination cantidad de m´ aquinas virtuales. rank se considera mejor al individuo con mayor 16

Ubicaci´ on ´optima de m´aquinas virtuales. Un enfoque multiobjetivo. Este m´etodo brinda la posibilidad de una mutaci´on completa de los genes, con una probabilidad muy baja pero no nula, lo que en principio resulta beneficioso para la exploraci´ on del espacio de b´ usqueda, disminuyendo la posibilidad de estancamientos en ´optimos locales. I. Evoluci´ on de Poblaciones. La evoluci´on de poblaciones en este trabajo se realiza en base a lo propuesto por Deb et al. en[10]. Una poblaci´ on Pt+1 se forma de la uni´on de la mejor poblaci´ on conocida Pt y la poblaci´on descendiente Qt, aplicando los operadores de nondomination rank y crowding distance. El proceso de evoluci´on de poblaciones se muestra en la Fig. 3.

Figura 3. Evoluci´ on de poblaciones.

4. Resultados experimentales. Para validar la formulaci´ on matem´atica propuesta en este trabajo y el correcto funcionamiento del algoritmo mem´etico multiobjetivo propuesto para la soluci´on del problema de ubicaci´on de m´ aquinas virtuales en un contexto multiobjetivo, se obtuvieron datos reales de m´ aquinas f´ısicas, m´ aquinas virtuales y tr´ afico de red entre las m´ aquinas virtuales del Centro de datos del Parque Tecnol´ ogico Itaipu, Paraguay (http://www.pti.org.py). Adem´ as, se obtuvieron algunos datos reales de m´ aquinas virtuales de proveedores mundiales de servicios de “Computaci´ on en la nube” (Cloud Computing) como Amazon EC2 (http://aws.amazon.com/es/ec2) y RackSpace Cloud (http://www.rackspace.com). Las pruebas experimentales de este trabajo se realizaron en diferentes escenarios, considerando diversos n´ umeros de m´aquinas f´ısicas y m´aquinas virtuales. Para facilitar la generaci´on de escenarios de prueba, se desarroll´ o un “Generador de escenarios” que basado en los datos reales obtenidos, escala estos datos para proponer diversos escenarios posibles con diferentes n´ umeros de m´aquinas f´ısicas, m´ aquinas virtuales y tr´ afico de red entre las m´ aquinas virtuales. Por medio del Generador de Escenarios desarrollado se generaron los siguientes escenarios de prueba para este trabajo: − 3x5: con 3 m´aquinas f´ısicas y 5 m´aquinas virtuales.

− 4x10: con 4 m´aquinas f´ısicas y 10 m´aquinas virtuales. − 10x20:con 10 m´ aquinas f´ısicas y 20 m´aquinas virtuales. Para comparar los resultados obtenidos por el algoritmo mem´etico multiobjetivo propuesto en este trabajo y validar su correcto funcionamiento, se implement´ o tambi´en un algoritmo de fuerza bruta para encontrar todas las soluciones posibles de una determinada instancia del problema de ubicaci´ on de m´ aquinas virtuales, cuando esto resulta computacionalmente posible. Los algoritmos utilizados en este trabajo fueron implementados en el lenguaje de programaci´on ANSI C (Compilador GNU C) y las pruebas de ejecuci´ on fueron realizadas sobre el sistema operativo Linux Ubuntu 11.10 en una m´ aquina con procesador Intel Core i7 de 1.2 GHz y 8 GB de memoria RAM. El algoritmo de fuerza bruta genera (n + 1)m posibles soluciones, donde n es el n´ umero de m´ aquinas f´ısicas y m es el n´ umero de m´ aquinas virtuales. Estos resultados son comparados con los obtenidos por el algoritmo propuesto despu´es de evolucionar una poblaci´ on de 100 individuos durante 100 generaciones. A. Prueba 1. Para el algoritmo de fuerza bruta se ha realizado una corrida para los escenarios de 3x5 y 4x10, obteni´endose as´ı el frente Pareto y el conjunto Pareto o´ptimo. Por otro lado, se han realizado diez corridas del algoritmo propuesto para los escenarios de 3x5 y 4x10. Los resultados de cada corrida fueron combinados para obtener el conjunto Pareto y su correspondiente frente Pareto calculados por el algoritmo. En las Tablas tab:frentePareto y 2 se presentan res´ umenes de la cantidad de elementos de los frentes Pareto y conjuntos Pareto encontrados por cada uno de los algoritmos en las pruebas experimentales realizadas. El algoritmo mem´etico multiobjetivo propuesto muestra buenos resultados al compararlo con el algoritmo de fuerza bruta a trav´es de los valores ´optimos encontrados. Para el escenario de prueba de 3x5 (3 m´ aquinas f´ısicas y 5 m´ aquinas virtuales), el algoritmo propuesto ha obtenido el 100 % de los elementos del frente Pareto ´ optimo y cerca del 51 % de los elementos del conjunto Pareto o´ptimo, mientras que para el escenario de prueba de 4x10 (4 m´ aquinas f´ısicas y 10 m´ aquinas virtuales) el algoritmo propuesto ha obtenido el 75 % de los elementos del frente Pareto o´ptimo y cerca del 80 % de los elementos del conjunto Pareto o´ptimo. 17

Ubicaci´ on ´optima de m´ aquinas virtuales. Un enfoque multiobjetivo. Tabla 1. Elementos del frente Pareto.

Escenario 3x5 4x10

Algoritmo mem´ etico multiobjetivo propuesto 55 42

Algoritmo de fuerza bruta 108 53

Tabla 2. Elementos del conjunto Pareto.

Escenario 3x5 4x10

Algoritmo mem´ etico multiobjetivo propuesto 5 18

Algoritmo de fuerza bruta 5 24

Los resultados obtenidos hacen suponer que con una mayor cantidad de corridas, el algoritmo llegar´ a a encontrar mayor cantidad de elementos del frente Pareto y del conjunto Pareto, pues no llegaron a su punto de estancamiento al momento de pararlos. En las Fig. 4 y Fig. 5 se grafican los frentes Pareto encontrados por cada uno de los algoritmos para el escenario de 4x10 (4 m´aquinas f´ısicas y 10 m´aquinas virtuales). El eje de abscisas representa el consumo energ´etico mientras que el eje de ordenadas indica el ingreso econ´omico. El tercer objetivo (tr´ afico de red) est´ a representado por el tama˜ no del c´ırculo.

Figura 4. Frente Pareto encontrado en escenario 4x10 por el algoritmo de fuerza bruta. El radio de la circunferencia de cada soluci´ on es proporcional al tr´ afico de red promedio.

Figura 5. Frente Pareto encontrado en escenario 4x10 por el algoritmo propuesto. El radio de la circunferencia de cada soluci´ on es proporcional al tr´ afico de red promedio.

A. Prueba 2. Para el escenario de 10x20, no se ha realizado una corrida del algoritmo de fuerza bruta, pues resulta impracticable generar 1120 posibles soluciones con los recursos computacionales disponibles. Claramente, para problemas de esta dimensi´on se necesita de heur´ısticas alternativas como la propuesta en este trabajo. En consecuencia, se han realizado diez corridas del algoritmo propuesto para el escenario de 10x20. Los resultados de cada corrida fueron combinados para obtener el frente Pareto y el conjunto Pareto generados por el algoritmo, que para este caso cuenta con aproximadamente 200 soluciones (tanto en el conjunto Pareto como en el frente Pareto). Con esta segunda prueba experimental se verifica la limitada escalabilidad de la b´ usqueda exhaustiva y la ventaja de utilizar meta heur´ısticas bio inspiradas como el algoritmo mem´etico propuesto en este trabajo.

7. Conclusiones y trabajos futuros. En este trabajo se propone por primera vez una formulaci´ on matem´atica del problema de ubicaci´on de m´ aquinas virtuales con un enfoque puramente multiobjetivo de las principales funciones objetivo estudiadas en la taxonom´ıa propuesta por L´ opez y Bar´ an en [2]. Seg´ un esta taxonom´ıa, los objetivos de optimizaci´ on m´ as estudiados son: (1) la minimizaci´ on del consumo energ´etico, (2) la minimizaci´on del tr´afico de red y (3) la maximizaci´on de los ingresos econ´ omicos. Estos objetivos que habr´ıan sido estudiados separadamente en la literatura, con un enfoque esencialmente monobjetivo, son as´ı considerados simult´ aneamente, con un enfoque puramente multiobjetivo. Adem´as, se ha propuesto por primera vez un algoritmo mem´etico multiobjetivo para solucionar el problema de ubicaci´ on de m´ aquinas virtuales formulado y se ha demostrado su correcto funcionamiento compar´ andolo con un algoritmo de b´ usqueda exhaustiva por fuerza bruta. Tambi´en se ha verificado experimentalmente la escalabilidad de la meta heur´ıstica utilizada en el algoritmo propuesto para escenarios con una considerable cantidad de m´aquinas f´ısicas y virtuales en un Centro de datos. Considerando los buenos resultados obtenidos en este trabajo y el crecimiento que vienen teniendo los Centros de datos, se ha empezado a trabajar en una formulaci´ on matem´atica m´as avanzada, basada en la formulaci´ on propuesta en este trabajo, que adem´ as contempla las posibles dependencias entre las aplicaciones que se ejecutan en cada m´ aquina virtual. En este caso, se tendr´ıan m´aquinas virtuales con niveles de criticidad que indiquen qu´e m´ aquinas virtuales deben ser ubicadas para su 18

Ubicaci´ on ´optima de m´ aquinas virtuales. Un enfoque multiobjetivo. ejecuci´on de forma obligatoria para garantizar el correcto funcionamiento de las dem´ as aplicaciones de un cliente. Un ejemplo de esto ser´ıa la m´aquina virtual que ejecuta la aplicaci´ on del Domain Name System (DNS), la cual deber´a ser ubicada para su ejecuci´ on de forma obligatoria o caso contrario las aplicaciones asociadas no funcionar´ an correctamente. Se propone adicionalmente como trabajo futuro la formulaci´ on del problema con otras funciones objetivo estudiadas en la taxonom´ıa propuesta en [2], as´ı como la utilizaci´on de otras meta heur´ısticas bio inspiradas existentes que a´ un no han sido utilizadas para resolver el problema de ubicaci´ on de m´ aquinas virtuales dada la novedad del nuevo planteamiento en un contexto multiobjetivo.

Referencias bibliogr´ aficas [1] Z. Wang, K. Shuang, L. Yang, F. Yang. “Energy-aware and revenue-enhancing combinatorial scheduling in virtualized of cloud datacenter”. Journal of Convergence Information Technology (JCIT, AICIT), vol. 7, no. 1, pp.6270, 2012. [2] F. L´ opez Pires, B. Bar´an. “Taxonom´ıa de ubicaci´ on ´optima de m´ aquinas virtuales en Centros de Datos eficientes”. ARANDUCON, 2012 Proceedings IEEE, 28-30 Noviembre. [3] T. Hirofuchi, H. Nakada, S. Itoh, S. Sekiguchi. .Enabling Instantaneous Relocation of Virtual Machines with a Lightweight VMM Extension”. 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid), pp.73-83, 17-20 Mayo 2010. [4] X. Wen, K. Chen, Y. Chen, Y. Liu, Y. Xia, C. Hu, “VirtualKnotter: Online virtual machine shuffling for congestion resolving in virtualized datacenter”. 2012 IEEE 32nd International Conference on Distributed Computing Systems (ICDCS), pp.12-21, 18-21 Junio 2012. [5] C. Kleineweber, A. Keller, O. Niehorster, A. Brinkmann. “Rule-based mapping of virtual

machines in clouds” 2011 19th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), pp.527534, 9-11 Febrero 2011. [6] C. Coello Coello, G. Lamont, D. Van Veldhuizen. “Evolutionary algorithms for solving multiobjectives problems”. Second Edition, Springer, pp.1-121, ISBN: 978-0-387-33254-3. [7] M. B´ aez, D. Z´ arate, B. Bar´ an. “Algoritmos mem´eticos adaptativos para optimizaci´ on multi-objetivo”. XXXIII Conferencia Latinoamericana de Inform´ atica ? CLEI’2007, 2007. [8] H. Goudarzi, M. Pedram. ”Maximizing profit in cloud computing system via resource allocation”. 2011 31st International Conference on Distributed Computing Systems Workshops (ICDCSW), pp.1-6, 20-24 Junio 2011 [9] Z. Wang, K. Shuang, L. Yang, F. Yang. “Energy-aware and revenue-enhancing combinatorial scheduling in virtualized of cloud datacenter”. Journal of Convergence Information Technology (JCIT, AICIT), vol. 7, no. 1, pp.6270, 2012. [10] V. Shrivastava, P. Zerfos, L . Kang-won, H. Jamjoom, L. Yew-Huey, S. Banerjee. .Application-aware virtual machine migration in data centers”. 2011 Proceedings IEEE INFOCOM, pp.66-70, 10-15 Abril 2011. [11] X. Jing, J. Fortes. “Multi-objective virtual machine placement in virtualized datacenter environments”. 2010 IEEE/ACM Int’l Conference on Green Computing and Communications (GreenCom) & Int’l Conference on Cyber, Physical and Social Computing (CPSCom), pp.179188, 18-20 Diciembre 2010. [12] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan. “A fast and elitist multiobjective genetic algorithm: NSGA-II”. IEEE Transactions on Evolutionary Computation, vol.6, no.2, pp.182-197, April 2002.

19