PDF de programación - Utilizando la calidad de las respuestas como política de distribución de la información de recursos en Grid Computing

Utilizando la calidad de las respuestas como
política de distribución de la información de

recursos en Grid Computing

Paula Verghelet

Laboratorio de Sistemas Complejos, Departamento de Computación,

Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires

Buenos Aires (C1428EGA), Argentina.

[email protected]

Resumen La computación de alto rendimiento (HPC, High Performan-
ce Computing) tiene como objetivo el estudio de los procedimientos y
estrategias computacionales necesarios para resolver eficientemente pro-
blemas complejos que demandan gran poder de cómputo.
En sistemas distribuidos de gran escala como las Grids o las Federaciones
de Clouds, resulta crucial saber dónde están los recursos y su disponibi-
lidad para poder coordinar su utilización. Cómo se obtiene y disemina
la información sobre estos recursos es lo que se denomina política de
distribución de la información de recursos.
Una clasificación posible para políticas de distribución de la informa-
ción es considerarlas centralizadas o descentralizadas. Estas últimas se
dividen en estructuradas o no-estructuradas. Las políticas Jerárquica,
Super-Peer, Random y Best-Neighbor resultan representativas dentro de
esta clasificación.
Contar con una política de distribución que sea a la vez escalable, to-
lerante a fallas, que no demande mantenimiento en exceso ni consuma
recursos de red y procesamiento del sistema en forma desmedida, resulta
un desafío tecnológico remarcable.
El principal resultado de esta tesis son dos políticas basadas en Best
Neighbor que evidenciaron muy buena performance siendo, a la vez, es-
calables, distribuidas y sin gran dependencia de administración manual.

Keywords: Cómputo Distribuido, Grid Computing, Información sobre
Recursos, Políticas de Distribución de la Información, Best Neighbor.

1.

Introducción

La simulación numérica es una herramienta con la cual se estudian diversos
fenómenos dentro de una gran variedad de ramas de la ciencia y de la inge-
niería. Uno de los ejemplos paradigmáticos resulta ser la predicción del clima.
Esta disciplina no solo necesita de modelos matemáticos que logren capturar la
complejidad de los diversos procesos que lo gobiernan, sino de la tecnología y
las técnicas para que estos puedan ser utilizados de manera de poder obtener
resultados en tiempo y forma.

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761103 Paula Verghelet

Por otro lado, durante los últimos años, el continuo aumento de la veloci-
dad de los procesadores se ha detenido, siendo reemplazado por un aumento en
la cantidad de núcleos de procesamiento cuya velocidad individual no presen-
ta incrementos notables [1]. Este hecho ha vuelto indispensable el desarrollo de
aplicaciones que realicen el cómputo de manera cooperativa, es decir, utilizan-
do paralelismo. La computación de alto rendimiento (HPC, High Performance
Computing) tiene por objetivo estudiar los procedimientos y estrategias compu-
tacionales necesarios para resolver eficientemente problemas complejos que de-
mandan un gran poder de cómputo.

Una de las tecnologías que ha emergido y se ha consolidado en los últimos
años es Grid Computing, que permite el acceso a prestaciones de supercómputo
(como clusters para procesamiento o unidades de almacenamiento) de manera
remota, así como la utilización de instrumentos de medición de alta complejidad
que se encuentran on-line o aplicaciones de cómputo científico que usualmente
se encuentran distribuidas geográficamente [2].

Como describen Ranjan et al. [3] y Navimipour et al. [4], pueden distinguirse
distintas clases de Grids según su prioridad de uso: (i) Cómputo, (ii) Datos,
(iii) Inalámbrica y (iv) Multimedia. En adelante nos referiremos a las Grids de
Cómputo1 simplemente como Grids.

Al utilizar Grid Computing es importante saber dónde están los recursos y
su disponibilidad de manera de poder coordinar su utilización (task scheduling),
siendo esta una problemática común a Cloud Computing y a sistemas distribui-
dos en general [5–7].

La optimización de la asignación de tareas y solicitudes de recursos de los
usuarios requiere que la información sobre los mismos se mantenga tan actualiza-
da como sea posible, tal como se menciona en Iamnitchi et al. [8] y en Pipan [9].
Cómo se obtiene y distribuye la información sobre estos recursos es lo que
se denomina política de distribución de la información de recursos, lo que en el
artículo de Iamnitchi, [8], se denomina Resource Discovery Problem. Una clasifi-
cación posible de las políticas de distribución de la información es considerarlas
centralizadas o descentralizadas, y a éstas últimas a su vez, como estructuradas
o no-estructuradas.

Las propuestas iniciales para los servicios de indexación y recolección de
información de estado de los recursos incluían modelos centralizados y jerárqui-
cos [3, 10]. Estos modelos tienen como principal problema la baja tolerancia a
fallas (single point of failure), así como una probable congestión de la red.

Para sistemas de medianos a grandes, la dinámica de la información sobre
recursos no puede ser capturada utilizando una jerarquía estática. El crecimiento
en tamaño y recursos de los sistemas con el correr del tiempo trajo consigo
la búsqueda de métodos más eficientes y robustos, despertándose un creciente
interés en lo desarrollado en el paradigma P2P [2–4, 8, 11, 12].

A continuación se presenta una breve descripción de las políticas de distri-

bución más usuales:

1

Sistemas con gran capacidad de cómputo disponible para aplicaciones

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761104 Políticas de distribución de la información basadas en Best Neighbor

Jerárquica (H): Se establece con antelación una jerarquía entre los nodos.
Los nodos intercambian información sólo con los del nivel inmediato inferior
o inmediato superior de la jerarquía establecida, Figura 8(a). Esta política
es la utilizada por MDS [10].
Random (R): Cada nodo elige de manera aleatoria otro nodo de la red
del cual obtener información, Figura 8(b). Suele utilizarse para comparar
comportamiento de peor caso [10]. Completamente distribuida.
Super Peer (SP): Sistema híbrido entre los sistemas completamente dis-
tribuidos y los cache-based (basados en la utilización de cache local para
aminorar la carga general de la red). Una red Super Peer opera como una
P2P (Peer to Peer) no estructurado [12], pero algunos nodos son definidos
como super-peers (sp), trabajando como servidores de un subconjunto de
nodos (peers) y como peers en la red de super-peers, quedando así definida
una estructura de dos niveles, Figura 8(c). Los nodos peers se comunican
directamente con un único super-peer y a través de él con los demás nodos.
Best Neighbor (BN): Inicialmente, el nodo posee un desconocimiento to-
tal acerca de los demás nodos en la red y selecciona alguno de manera aleato-
ria. A medida que recibe respuestas, genera una lista de vecinos (neighbors)
para luego seleccionar al que mejor satisface sus requerimientos (provee el
mejor servicio, tiene mayor disponibilidad de recursos, etc.), Figura 8(d).
Cada nodo mantiene también una pequeña probabilidad de elegir de manera
aleatoria a quien consultar, aún cuando ya tiene la información de todo el
sistema, de manera de poder adecuarse a eventuales cambios en la topología
de la red.

Del estudio de la performance obtenida por cada una de estas cuatro políti-
cas, encontramos que Best Neighbor presenta algunos resultados inesperados,
similares a los obtenidos al utilizar la política Random, a pesar de utilizar infor-
mación histórica obtenida en base a consultas previas para guiar la política de
distribución.

Los principales objetivos de este trabajo consisten en identificar las causas de
la baja performance de la política Best Neighbor, estudiar la forma de mitigar
los efectos negativos de estas causas y aplicar este conocimiento en mejorar la
performance de esta política completamente distribuida.

2. Metodología

En esta Sección se describe la metodología que se siguió para realizar el
estudio de la política Best Neighbor y su comparación con las políticas de dis-
tribución de la información previamente mencionadas: Jerárquica, Super Peer y
Random.

Para el análisis y comparación de la performance de estas políticas de distri-
bución se consideran los resultados obtenidos mediante la simulación en diversos
escenarios, tanto desde el punto de vista de la topología de red subyacente como
de la cantidad de nodos del sistema, del siguiente conjunto de métricas presenta-

EST 2015, 18º Concurso de Trabajos Estudiantiles. 44 JAIIO - EST 2015 - ISSN: 2451-761105 Paula Verghelet

das en Mocskos et al. [10]. En el Apéndice B.1 se detalla la definición completa
de las mismas, aquí las describiremos como:

LIR (Local Information Rate): Indica cuánta información tiene un nodo en
particular sobre toda la red en un cierto momento, teniendo en cuenta el
tiempo de expiración de dicha información. Para el host k, LIRk es:

N
h=1 f (ageh, expirationh) · resourceCounth

totalResourceCount

LIRk =

GIR (Global Information Rate): Indica la cantidad de información con la
que cuenta el sistema sobre el total de recursos disponibles. Se obtiene por
medio del promedio de los LIR de cada nodo.

Utilizamos para las simulaciones Gridmatrix [10, 13], herramienta Open Source
basada en SimGrid [14]. Este framework sobre el que se desarrolló, y que ac-
tualmente utiliza Gridmatrix, es un simulador para aplicaciones distribuidas en
escenarios heterogéneos.

Se supondrá en este trabajo que la información que se obtiene en respuesta
a una solicitud de recursos es siempre válida, es decir, si un nodo responde
se supone que este puede satisfacer el pedido realizado en la solicitud. No se
consideran requer