Algoritmo de distribuição de réplicas em Grid de Dados

Vista previa del material en texto

UN ALGORITMO BASADO EN INTELIGENCIA 
COMPUTACIONAL PARA DISTRIBUCIÓN DE RÉPLICAS EN 
UN GRID DE DATOS 
 
 
 
 
 
 
 
 
 
 
 
 ING. LEONARDO FERNEY BUSTAMANTE ARCHICUE 
 
 
 
 
 
 
 
 
 
 
 
 
ESCUELA DE INGENIERIA DE SISTEMAS Y COMPUTACION 
UNIVERSIDAD DEL VALLE 
2016 
 
 
 
 
UN ALGORITMO BASADO EN INTELIGENCIA 
COMPUTACIONAL PARA DISTRIBUCIÓN DE RÉPLICAS EN 
UN GRID DE DATOS 
 
 
 
 
 ING. LEONARDO FERNEY BUSTAMANTE ARCHICUE 
 
 
 
Proyecto de grado para optar al título de MAGISTER EN 
INGENIERIA con énfasis en INGENIERIA DE SISTEMAS Y 
COMPUTACION 
 
 
 
 
 
Dirigido por: 
PH.D. JOHN ALEXANDER SANABRIA ORDOÑES 
 
 
 
 
 
 
ESCUELA DE INGENIERIA DE SISTEMAS Y COMPUTACION 
UNIVERSIDAD DEL VALLE 
2016 
 
 
 
Nota de Aceptación 
 
 
 
 
 
 
PhD. Cesar Diaz 
Jurado 
 
 
 
 
MSc. Jairo Enrique Serrano 
Jurado 
 
 
 
 
 
 
 
 
 
 
Santiago de Cali, 19 de Octubre de 2016 
 
 
 
Agradecimientos 
 
 
Quiero realmente manifestar mis más sinceros agradecimientos a muchas personas que con 
su compañía, comprensión, paciencia y conocimiento hicieron posible la culminación de este 
trabajo. 
A mi familia paterna, mi padre Fabio y mi madre María Mercedes, que me apoyaron en la 
realización de mis estudios sin pedir nada a cambio. Por su amor, comprensión y paciencia. 
Mis hermanos y sobrinos, pues ellos estaban ahí cuando necesitaba cambiar de aire y 
divertirme un poco. 
A mi familia, mi esposa Nathalia, por su amor, compañía, conocimiento y comprensión, 
también por impulsarme a seguir estudiando, pues era un proyecto que mantenía postergando. 
Mi hija Verónica, por su amor, su ternura y comprensión, por sacrificar y compartir mi 
tiempo de juegos y locuras con la realización de este proyecto, es una deuda que tengo 
contigo. Juliana has sido como una hija para mí y me has permitido ensayar mi tarea como 
padre, espero que haya sido positivo el resultado. 
A mi director, John Sanabria, gracias por sus consejos, apoyo incondicional y paciencia. Su 
experiencia y conocimiento han sido un aporte importante en la consecución de los objetivos 
propuestos en este trabajo. 
A mis compañeros de trabajo en Calipso, quienes muchas veces se leyeron y corrigieron el 
presente documento, gracias por sus consejos. A mis jefes que me dieron el espacio y tiempo 
para realización de este trabajo. 
A Talento Digital, este programa permite que nuestra mente esté ocupada en estudiar y 
aportar al país desde las TIC’s y no se encuentre ocupada pensando en endeudarse para pagar 
el semestre. Muchas gracias por su financiación y aportes. 
 
 
 
Leonardo Ferney Bustamante Archicué 
 
Resumen 
 
La replicación aporta tres importantes características en los Data Grids: disponibilidad, 
rápido acceso a los datos y bajo consumo del ancho de banda. La copia de los datos en 
múltiples ubicaciones, permite la disponibilidad, dado que la información es accesible, a 
pesar de la pérdida, el daño o faltade acceso en una de las ubicaciones. Transferir un 
archivo múltiples veces de un servidor central a un cliente puede requerir de canales de 
comunicación con un alta capacidad en su ancho de banda. En un Data Grid, el rápido 
acceso a los datos y ahorro en consumo de ancho de banda es proporcionado por las copias 
cercanas a los clientes. 
En el presente trabajo se diseñan dos algoritmos que utilizan computación inteligente para 
ubicar réplicas en un grid de datos. Por último, se implementan estos algoritmos usando un 
software para la simulación de ambientes grid como Optorsim para la evaluación de 
réplicas, revisamos su desempeño y finalmente los comparamos con otros algoritmos 
disponibles en el simulador. 
 
Keywords: Optorsim, Data Grid, simuladores, inteligencia computacional, sistemas de 
archivos distribuidos, Swarm Intelligence 
 
 
1 TABLA DE CONTENIDO 
3 Introducción .................................................................................................................. 13 
4 Motivación ..................................................................................................................... 14 
5 Objetivos ....................................................................................................................... 16 
5.1 Objetivo General .................................................................................................... 16 
5.2 Objetivos Específicos ............................................................................................. 16 
6 Bibliografía .................................................................................................................... 16 
7 Grid Computing............................................................................................................. 19 
7.1 Introducción............................................................................................................ 19 
7.2 Arquitectura del Grid .............................................................................................. 20 
7.2.1 Infraestructura................................................................................................. 21 
7.2.2 Conectividad: Comunicación fácil y segura ................................................... 21 
7.2.3 Recurso........................................................................................................... 22 
7.2.4 Recursos, La capa colectiva coordinando múltiples recursos ....................... 22 
7.2.5 Aplicaciones .................................................................................................... 23 
7.3 Computational Grid ................................................................................................ 23 
7.4 Data Grid ................................................................................................................ 24 
7.4.1 XtreemFS ........................................................................................................ 26 
7.4.2 dCache............................................................................................................ 26 
7.4.3 Gfarm .............................................................................................................. 27 
7.5 Bibliografia ............................................................................................................. 28 
8 Simuladores de Ambientes Grid .................................................................................. 30 
8.1 Introducción............................................................................................................ 30 
8.2 Microgrid ................................................................................................................ 31 
8.3 Gridsim ................................................................................................................... 31 
8.4 Simgrid ................................................................................................................... 32 
8.5 Optorsim ................................................................................................................. 33 
8.6 Gangsim ................................................................................................................. 33 
8.7 MONARC ............................................................................................................... 34 
8.8 Resumen ................................................................................................................ 35 
8.9 Bibliografia ............................................................................................................. 35 
9 Inteligencia Computacional .......................................................................................... 38 
9.1 Introducción............................................................................................................ 38 
9.2 Aprendizaje ............................................................................................................38 
9.3 Técnicas de inteligencia computacional ................................................................ 39 
9.4 Inteligencia de Enjambres ..................................................................................... 40 
9.4.1 Ant Colony Optimization (ACO) ..................................................................... 42 
9.4.2 Particle Swarm Optimization (PSO) ............................................................... 43 
9.5 Resumen ................................................................................................................ 45 
9.6 Bibliografía ............................................................................................................. 45 
10 Estado del arte.............................................................................................................. 48 
10.1 Introducción ........................................................................................................ 48 
10.2 Ubicación de Réplicas ........................................................................................ 48 
10.3 Reemplazo de Réplicas ..................................................................................... 51 
10.4 Selección de Réplicas ........................................................................................ 52 
10.5 Globus Toolkit .................................................................................................... 53 
10.5.1 Movimiento de los datos ................................................................................. 54 
10.5.2 Réplica de Datos ............................................................................................ 54 
10.6 Resumen ............................................................................................................ 56 
10.7 Bibliografía.......................................................................................................... 57 
11 Modelo Propuesto ........................................................................................................ 61 
11.1 Introducción ........................................................................................................ 61 
11.2 Análisis del problema ......................................................................................... 62 
11.3 Características de la solución ............................................................................ 62 
11.4 Modelo propuesto............................................................................................... 64 
11.5 Resumen ............................................................................................................ 66 
11.6 Bibliografía.......................................................................................................... 66 
12 Estrategia de localización de réplicas basado en algoritmo de colonia de hormigas . 68 
12.1 Introducción ........................................................................................................ 68 
12.2 ACO para localización de réplicas en ambientes grid ....................................... 69 
12.3 Algoritmo basado en ACO ................................................................................. 70 
12.4 Resumen ............................................................................................................ 72 
12.5 Bibliografía.......................................................................................................... 72 
13 Estrategia de localización de réplicas basado en la técnica de optimización por 
enjambre de partículas ......................................................................................................... 73 
13.1 Introducción ........................................................................................................ 73 
13.2 PSO para localización de réplicas en ambientes grid ....................................... 74 
13.3 Algoritmo basado en PSO ................................................................................. 77 
13.4 Resumen ............................................................................................................ 79 
13.5 Bibliografía.......................................................................................................... 80 
14 Implementación y evaluación de los algoritmos para la distribución de réplicas 
propuestos ............................................................................................................................ 81 
14.1 Introducción ........................................................................................................ 81 
14.2 Simulador ........................................................................................................... 81 
14.3 Ambiente de simulación ..................................................................................... 84 
14.4 Métricas de evaluación ...................................................................................... 85 
14.5 Equipo de pruebas ............................................................................................. 86 
14.5.1 Hardware ........................................................................................................ 86 
14.5.2 Software .......................................................................................................... 87 
14.6 Resultados de la simulación .............................................................................. 88 
14.6.1 Last Frequently Used (LFU) ........................................................................... 88 
14.6.2 Estrategias basadas en economía ................................................................. 88 
14.6.3 Patrón de acceso secuencial ......................................................................... 89 
14.6.4 Patrón de acceso Gaussiano ......................................................................... 91 
14.6.5 Patrón de acceso Zipf..................................................................................... 92 
14.7 Conclusiones ...................................................................................................... 93 
14.8 Bibliografía.......................................................................................................... 95 
15 Apéndice A: Taxonomía de herramientas de simulación de ambientes grid. ............. 97 
15.1 Introducción ........................................................................................................ 97 
15.2 Trabajos relacionados ........................................................................................ 98 
15.3 Taxonomía........................................................................................................ 100 
15.4 Tipo de Herramienta ........................................................................................ 100 
15.4.1 Interfaz De usuario ....................................................................................... 101 
15.4.2 Tipo de GRID ................................................................................................ 101 
15.4.3 Parametrización ............................................................................................ 102 
15.4.4 Implementación ............................................................................................ 102 
15.5 Herramientas de investigación......................................................................... 102 
15.5.1 Microgrid ....................................................................................................... 102 
15.5.2 Simgrid .......................................................................................................... 103 
15.5.3 Gridsim .......................................................................................................... 104 
15.5.4 Optorsim .......................................................................................................104 
15.5.5 Gangsim........................................................................................................ 105 
15.6 Clasificación de las herramientas de simulación usando la taxonomía propuesta
 105 
15.7 Conclusiones .................................................................................................... 107 
15.8 Bibliografía........................................................................................................ 107 
 
 
2 LISTA DE FIGURAS 
 
Figura 1 Arquitectura Grid(I Foster et al., 2001) .................................................................. 20 
Figura 2 Planificación de tareas de una aplicación grid (Berstis, 2002). ............................ 24 
Figura 3 Arquitectura de Microgrid (Xia et al., 2004) ........................................................... 31 
Figura 4 Arquitectura de GridSim (Buyya & Murshed, 2002) .............................................. 32 
Figura 5 Arquitectura de componentes Simgrid (URL, n.d.) ............................................... 33 
Figura 6 Arquitectura de OptorSim (D. Cameron & Millar, 2004) ........................................ 34 
Figura 7 Usando Feromonas para la selección de la mejor ruta (Sehrawat 2013) ............ 43 
Figura 8 Globus Toolkit (R) Versión 5 (GT5) ) (URL8 2015) ............................................... 55 
Figura 9 Asociación entre el Logical File Name y réplicas en 3 diferentes sitios (Chervenak 
n.d.) ....................................................................................................................................... 55 
Figura 10 Arquitectura de OptorSim (Cameron et al. 2004) ................................................ 83 
Figura 11 Topología de red CMS - European Data Grid (Bell & Cameron 2003; Vashisht et 
al. 2014) ................................................................................................................................ 84 
Figura 12 Especificaciones técnicas plataforma de pruebas. ............................................. 87 
Figura 13 Software instalado en la plataforma de pruebas ................................................. 87 
Figura 14 Comparación el uso efectivo de la red en las estrategias variando el número de 
tareas utilizando un patrón de acceso secuencial ............................................................... 90 
Figura 15 Comparación del promedio de ejecución de tarea en las estrategias variando el 
número de tareas utilizando un patrón de acceso secuencial ............................................ 90 
Figura 16 Comparación del uso efectivo de la red en las estrategias variando el número de 
tareas y utilizando un patrón de acceso Gaussiano ............................................................ 91 
Figura 17 Comparación del tiempo promedio de la ejecución de las tareas en las estrategias 
variando el número de tareas y utilizando un patrón de acceso Gaussiano ...................... 92 
Figura 18 Comparación del uso efectivo de la red en las estrategias variando el número de 
tareas y utilizando un patrón de acceso Zipf ....................................................................... 93 
Figura 19 Comparación del tiempo promedio de ejecución de las tareas en las estrategias 
variando el número de tareas y utilizando un patrón de acceso Zipf .................................. 93 
Figura 20 Taxonomía de herramientas de investigación en ambientes grid .................... 100 
Figura 21 Arquitectura de Microgrid [11] ............................................................................ 103 
Figura 22 Arquitectura de componentes Simgrid [20] ....................................................... 103 
Figura 23 Arquitectura de GridSim [10] ............................................................................. 104 
Figura 24 Arquitectura de OptorSim [15] ........................................................................... 105 
 
 
INTRODUCCIÓN 
3 INTRODUCCIÓN 
 
Grid Computing se ha convertido en un paradigma de computación ampliamente adoptado 
en la comunidad científica debido a que provee acceso a elementos de cómputo 
geográficamente distribuidos y conectados a través de Internet. Grid computing propicia la 
consolidación de organizaciones virtuales bajo las cuales los investigadores de diferentes 
áreas del conocimiento pueden ejecutar modelos y simulaciones que generan o necesitan 
de una gran cantidad de datos; estos datos deben ser almacenados y posteriormente 
procesarse (Sato & Matsuoka 2007). Algunas áreas de investigación como bioinformática, 
física y astronomía generan estos altos volúmenes de datos (del orden de los petabytes) 
en poco tiempo y requieren ser procesados de forma inmediata. Se necesita, entonces, un 
servicio de administración de almacenamiento para esta cantidad de datos. Este servicio 
es proporcionado por una arquitectura especial de Grid Computing llamada Data Grid. 
Un Data Grid es una arquitectura enfocada en proporcionar servicios especializados para 
manejar clústeres de datos distribuidos y heterogéneos (Brezany et al. 2006). Una 
arquitectura Data Grid es desarrollada para permitir el intercambio de datos entre 
organizaciones virtuales ubicadas en lugares geográficamente dispersos. Este intercambio 
puede ser complejo sin el uso de componentes que permitan el acceso fácil y rápido a los 
datos, la replicación es uno de los componentes que facilita el acceso de los usuarios o 
aplicaciones a los datos, localizando copias cercanas (Rahman et al. 2007). Uno de los 
retos importantes de investigación en Data Grids es la administración de la réplica de los 
datos. 
La replicación es la creación y administración de copias de archivos en un sistema de 
almacenamiento determinado (Brezany et al. 2006). La replicación aporta tres importantes 
características en los Data Grids: disponibilidad, rápido acceso a los datos y bajo consumo 
del ancho de banda. La copia de los datos en múltiples ubicaciones, permite la 
disponibilidad, dado que la información es accesible, a pesar de la pérdida, el daño o falta 
de acceso en una de las ubicaciones. Transferir un archivo múltiples veces de un servidor 
central a un cliente puede requerir de canales de comunicación con un alta capacidad en 
su ancho de banda. En un Data Grid, el rápido acceso a los datos y ahorro en consumo de 
ancho de banda es proporcionado por las copias cercanas a los clientes. 
Los nodos tienen un espacio limitado de almacenamiento, y por esto no es posible hacer 
réplicas de todos los archivos que se encuentran en el Data grid. Además, el ancho de 
banda limita la capacidad para transferirlos. Un Data grid debe tener un sistema de 
administración de réplicas, que administre los archivos de datos en un ambiente grid con el 
objetivo de optimizar su desempeño. La presente propuesta tiene como objeto diseñar un 
algoritmo que utilice computación inteligente para ubicar réplicas en una malla de datos. 
Por último, se pretende implementar este algoritmo y, usando un software para la 
simulación de ambientes grid, como Optorsim, para la evaluación de réplicas (Bell & 
Cameron 2003), revisar su desempeño. 
4 MOTIVACIÓN 
Un Grid es un conjunto de computadores heterogéneos dispersos geográficamente pero 
interconectados a través de redes heterogéneas de datos que orquestados ofrecen 
servicios no triviales de computación (Foster et al. 2001). Grid Computing permite el acceso 
fácil y a bajo costo, a sistemas de computación de última tecnología a investigadores. 
Frecuentemente, los investigadores en diversas áreas como bioinformática, astronomía, 
genética, entre otras, necesitan ejecutar sus aplicaciones en ambientes 
computacionalmente complejo y con altos niveles de almacenamiento y procesamiento. 
Estas áreas generan gran cantidad de información debido a la avanzada precisión de sus 
sensores. 
La información es clave en el mundo moderno,donde encontramos términos acuñados y 
bastante populares como Big Data. Actualmente la información es producida en cada tarea 
que realizamos a diario, tales como, procesamiento digital, intercambios en las redes 
sociales, recopilados por miles de sistemas, sensores y dispositivos móviles (Bajaber et al. 
2016). Los datos obtenidos crecen a gran velocidad, volumen y variedad. Según IBM 
estamos produciendo 2.5 quintillones de bytes de datos a diario (IBM 2016; Zikopoulos et 
al. 2015). Por ejemplo, un carro eléctrico genera 25GB de información en una hora mientras 
está cargando (Zikopoulos et al. 2015). Otro ejemplo es el juego popular de Zynga “Farm 
Ville”, Zynga obtiene aproximadamente 25TB de datos diariamente, y la compañía diseña 
iteraciones de juego, basadas en esas interacciones. Desde hace unos cuantos años se 
crea un usuario cada 3 segundos en Facebook, ahora estos usuarios más de 3.5 billones 
de posts y cerca de 155 millones de reacciones diariamente, los que representan varios 
terabytes de datos. Uno de los proyectos que genera más cantidad de datos sobre la tierra 
es el acelerador de partículas LHC (Large Hadron Collider) operado por la Organización 
Europea para la investigación nuclear (CERN), entre las muchas hipótesis que los físicos 
de partículas investigan es el origen del universo y replicar las condiciones de la teoría del 
Big Bang. Cuando el acelerador de partículas está en operación genera un volumen alto de 
datos, del orden de los PetaBytes. 
De esta manera se hace necesario encontrar herramientas para el almacenamiento de 
datos que no solamente brinden las opciones de guardar y recuperar la información, si no 
que también proporciona un medio confiable, manejable, escalable y almacenamiento 
distribuido de alto rendimiento. Al utilizar un sistema de almacenamiento distribuido se 
cumple el requerimiento de escalabilidad, agregando un sistema de réplicas a este sistema, 
podemos obtener un sistema confiable. Cuando optimizamos la gestión de réplicas 
obtenemos un sistema de almacenamiento distribuido de alto rendimiento, en esta trabajo 
nos enfocaremos en eje y de alguna manera optimizar los tiempos de acceso a los archivos 
que se encuentran en el grid. La manejabilidad depende de la semántica pero este punto 
no se abordará en el presente trabajo. 
Estos datos necesitan ser accedidos desde los nodos de cómputo que se encuentran 
lugares dispersos conectados por una red de área amplia. Un sistema de archivos 
distribuido de área amplia permite el acceso en este tipo de ambientes. Estos sistemas de 
archivos deben considerar la semántica, seguridad, tolerancia a fallos y velocidad de 
acceso a estos archivos. 
Un Data Grid es una arquitectura que provee estos sistemas de archivos, proporciona el 
servicio de acceso a datos y a metadatos. Existen múltiples componentes en los niveles 
altos de una arquitectura de un Data Grid, tales como la administración de réplicas. La 
administración de réplicas es uno de los retos importantes en investigación en un Data Grid. 
La replicación es la creación y administración de copias de archivos en un sistema de 
almacenamiento (Brezany et al. 2006). 
Las preguntas que nos surgen en este trabajo y que vamos a revisar son las siguientes: 
¿Cuáles son las técnicas clásicas utilizadas para llevar a cabo el proceso de réplica en Data 
Grid? ¿Se pueden incorporar técnicas de inteligencia computacional de modo que se lleve 
a cabo una gestión eficiente de las réplicas en estos ambientes de almacenamiento a gran 
escala? 
5 OBJETIVOS 
5.1 OBJETIVO GENERAL 
Diseñar, implementar y evaluar un algoritmo usando técnicas de computación inteligente 
para optimizar la ubicación de réplicas en un Grid de almacenamiento. 
5.2 OBJETIVOS ESPECÍFICOS 
 Obtener un estado del arte de las aproximaciones usadas para el almacenamiento 
de datos en ambientes grid. 
 Ponderar y seleccionar una técnica de computación inteligente compatible con el 
contexto de almacenamiento en los grid de datos. 
 Proponer y evaluar un algoritmo basado en inteligencia computacional para la 
ubicación de réplicas en grid de datos. 
 
6 BIBLIOGRAFÍA 
Bajaber, F. et al., 2016. Big Data 2.0 Processing Systems: Taxonomy and Open Challenges. 
Journal of Grid Computing, pp.379–405. Available at: 
http://link.springer.com/10.1007/s10723-016-9371-1. 
Bell, W. & Cameron, D., 2003. Optorsim: A grid simulator for studying dynamic data 
replication strategies. … Journal of High …, pp.1–20. Available at: 
http://hpc.sagepub.com/content/17/4/403.short [Accessed June 4, 2013]. 
Brezany, P., Woehrer, a. & Tjoa, a. M., 2006. The Grid: vision, technology development 
and applications. e & i Elektrotechnik und Informationstechnik, 123(6), pp.251–258. 
Available at: http://link.springer.com/10.1007/s00502-006-0344-0 [Accessed June 3, 
2013]. 
Foster, I., Kesselman, C. & Tuecke, S., 2001. The anatomy of the grid: Enabling scalable 
virtual organizations. International journal of high …. Available at: 
http://dl.acm.org/citation.cfm?id=1080667 [Accessed September 14, 2013]. 
IBM, 2016. What is Big Data? 
Rahman, R.M., Barker, K. & Alhajj, R., 2007. Replica Placement Strategies in Data Grid. 
Journal of Grid Computing, 6(1), pp.103–123. Available at: 
http://link.springer.com/10.1007/s10723-007-9090-8 [Accessed June 2, 2013]. 
Sato, H. & Matsuoka, S., 2007. Data Management on Grid Filesystem for Data-Intensive 
Computing. Proceedings of the 2007 International Symposium on Applications and the 
Internet Workshops (SAINTW’07). 
Zikopoulos, P. et al., 2015. Big Data Beyond the Hype, 
 
 
 
 
 
 
 
Parte II 
Marco conceptual 
 
Este marco conceptual pretende acercar al lector a algunos conceptos relevantes en 
ambientes grid, en el uso de herramientas de simulación y en los algoritmos revisados para 
la solución propuesta en el presente documento. Esta parte del trabajo de grado la 
componen tres capítulos, divididos así: en el primer capítulo se revisarán conceptos claves 
de grid computing, su arquitectura y dos tipos de grid, computation grid y data grid. El 
segundo capítulo nos muestra la importancia y necesidad de herramientas de simulación 
para ambientes grid, se muestra una vista general y se exponen algunas herramientas. En 
el último capítulo de este marco conceptual revisamos la inteligencia computacional y que 
aportes pueden proporcionar al presente trabajo; exponemos tres algoritmos de inteligencia 
computacional que han sido usados en trabajos parecidos y que pueden aportar a la 
solución del problema de ubicación de réplicas en sistemas distribuidos para grid. 
 
7 GRID COMPUTING 
7.1 INTRODUCCIÓN 
Grid Computing es una tecnología innovadora de sistemas distribuidos, una rama de la 
computación de alto desempeño donde los centros de supercomputadores, clústeres y los 
recursos distribuidos tradicionales son integrados en una infraestructura de hardware y 
software. A un alto nivel, esta idea propone que el poder de cómputo y la capacidad de 
almacenamiento puedan ser accesibles y profesionalmente administrados, como el agua o 
la energía eléctrica. A diferencia de los sistemas distribuidos convencionales, las máquinas 
pueden estar en sitios dispersos, controladas por diversas instituciones. Grid Computing 
permite compartir recursos (almacenamiento, cómputo, memoria, entre otras) de manera 
coordinada sin un control centralizado. Grid Computing es un sistema que integra varias 
tecnologías, clustering, web services, arquitectura orientada al servicio, utility computing 
entre otras, para resolver algunas tareas complejas que pueden ser desde estudio de 
mercados, atención de emergencias hasta investigaciones científicas como predicción de 
terremotos, tsunamis, simuladores de física de alta energía y bioinformática. 
En (Ian Foster, 2002) Ian Foster propone una lista de tres características para determinar 
si un sistema distribuido es ungrid. La primera es “coordinar recursos que no están sujetos 
a un control central”, recursos que se encuentren en diferentes dominios, pueden ser 
unidades dentro de la misma compañía o compañías diferentes que administren sus 
políticas, seguridad, membresía y pago de manera independiente. Sin embargo un clúster 
de computadores conectados en una red de área local puede ser un recurso importante de 
un grid pero este sistema no será un grid. 
La segunda es “usando un protocolos e interfaces estándar, abiertas y de propósito 
general”, protocolos e interfaces para autenticación, autorización, búsqueda y acceso a 
recursos deben ser no sólo abiertos y de propósito general, si no también estándar. Los 
estándares nos permiten establecer acuerdos dinámicamente entre cualquier parte 
interesada y construir sistemas distribuidos compatibles e interoperables. 
La tercera es “entregar calidades de servicio no triviales”, un sistema grid debe permitir 
coordinar sus recursos para ofrecer diferentes calidades de servicio en tiempos de 
respuesta, desempeño, disponibilidad y seguridad para satisfaces las demandas del 
usuario, de manera que la utilidad del sistema combinado es significativamente mayor que 
el de la suma de sus partes 
Aunque un grid puede estar dedicado a una operación, a menudo son usadas para una 
amplia variedad de problemas. Para permitir el uso en múltiples tareas un sistema grid 
puede enfocarse en el servicio de computación que permite el uso de sistema para ejecutar 
tareas complejas, llamados generalmente Computational Grid. O también puede enfocarse 
en el almacenamiento de datos en gran escala llamados Data Grid o una combinación de 
las dos (URL3, 2012)(Thain, 2004). En la siguiente sección realizamos una revisión general 
de la arquitectura Grid, en la tercera sección hacemos una vista general de Computational 
Grid y en la cuarta sección revisamos las características de un Data Grid. 
7.2 ARQUITECTURA DEL GRID 
Debido a la gran cantidad de componentes heterogéneos, es necesaria una arquitectura 
abierta que permita cumplir con los requerimientos de las organizaciones virtuales. La 
arquitectura presentada en (I Foster, Kesselman, & Tuecke, 2001)Los componentes en 
cada nivel comparten características comunes pero pueden ser construidos sobre 
capacidades y comportamientos proporcionados por cualquier nivel inferior (Figura 1). 
 
 
Figura 1 Arquitectura Grid(I Foster et al., 2001) 
 
7.2.1 Infraestructura 
La capa de grid Infraestructura proporciona los recursos que se comparten en el grid por 
ejemplo, los recursos computacionales, sistemas de almacenamiento, catálogos, recursos 
de red, y sensores. Un "recurso" puede ser una entidad lógica, como un sistema distribuido 
de archivos, clúster de computadores, o un conjunto de sistemas distribuidos; En tales 
casos, una implementación de recursos puede implicar protocolos internos. Una breve lista 
de recursos es como sigue: 
 Computacionales 
 Almacenamiento 
 Comunicaciones 
 Software y licencias 
 Equipo especial, arquitecturas, capacidades y políticas 
7.2.2 Conectividad: Comunicación fácil y segura 
La capa de conectividad define protocolos de comunicación y autenticación básicas 
requeridas para las transacciones de red a red específicos. Los protocolos de comunicación 
permiten el intercambio de datos entre los recursos de la capa de tela. Los protocolos de 
autenticación se basan en servicios de comunicación para proporcionar mecanismos 
criptográficamente seguros para verificar la identidad de usuarios y recursos. Los protocolos 
de comunicación requeridos pueden ser encontrados en la pila de protocolos TCP/IP son 
nombres (DNS), transporte (TCP, UDP) y enrutamiento (IP) y otros protocolos que se 
pueden encontrar en. 
En el problema de seguridad, como en el de comunicación, muchos estándares de 
seguridad desarrollados dentro del contexto del protocolo IP son aplicables. 
 Single sign-on: El usuario se debe autenticar sólo una vez y poder tener acceso a 
las herramientas presentes en el grid 
 Delegación: El usuario puede ejecutar una aplicación y delegarle sus permisos, de 
esta manera la aplicación tendrá acceso a los mismos recursos del usuario. 
 Integración con varias soluciones de seguridad locales: Debe permitir mapear las 
políticas y permisos en el grid y las asignadas por el sistema local. 
 Relaciones de confianza basada en el usuario: No se debe requerir la interacción 
entre sistemas para identificar si el usuario tiene los privilegios. Por ejemplo, si un 
usuario tiene derecho a utilizar los sitios A y B, el usuario debe ser capaz de utilizar 
los sitios A y B juntos sin necesidad de que los administradores de seguridad de A 
y B interactúan. 
7.2.3 Recurso 
Luego que se ha verificado la identidad del usuario es necesario proveer los mecanismos 
de acceso al recurso (Ian Foster & Kesselman, 2003). Son necesarios protocolos para 
negociación segura, iniciación, monitoreo, control, contabilidad y pago de compartir los 
recursos individuales. 
Encontramos dos clases de protocolos: 
 Protocolos de información se utilizan para obtener información acerca de la 
estructura y el estado de un recurso, por ejemplo, su configuración, la carga actual, 
y la política de uso. 
 Protocolos de administración se utilizan para negociar el acceso a un recurso 
compartido, especificando, por ejemplo, los requerimientos de recursos (incluyendo 
avanzado de reservas y la calidad de servicio) y la operación (s) a realizar, tales 
como la creación de procesos o de acceso a datos. 
7.2.4 Recursos, La capa colectiva coordinando múltiples recursos 
Es necesario proveer los mecanismos para interactuar con las colecciones de recursos (Ian 
Foster & Kesselman, 2003). Los servicios incluidos en esta capa no añaden requerimientos 
a los recursos individuales, algunos de ellos son: 
 Servicios de directorio: permiten a los participantes VO para descubrir la existencia 
y / o propiedades de los recursos VO. 
 Servicios de Co-asignación, programación e intermediación: permiten a los 
participantes de la VO solicitar la asignación de uno o más recursos para propósitos 
específicos y la programación de las tareas de los recursos apropiados. 
 Servicios de monitoreo y diagnóstico: apoyan el monitoreo de los recursos de la VO 
por fallos, ataque de hackers ("detección de intrusos"), sobrecarga, y así 
sucesivamente. 
 Servicios de réplica de datos: apoyan la gestión de los recursos de almacenamiento 
de la VO para maximizar el rendimiento de acceso a datos con respecto a los 
indicadores como el tiempo de respuesta, fiabilidad y coste. 
7.2.5 Aplicaciones 
Esta es la última capa de la arquitectura mostrada en (I Foster et al., 2001; Ian Foster & 
Kesselman, 2003), en esta capa se encuentran las aplicaciones que operan dentro del 
ambiente Grid. Las aplicaciones pueden usar protocolos, APIs o servicios de cualquier nivel 
inferior, como: administración de recursos, acceso a datos, búsqueda de servicios, entre 
otros. Aunque esta capa es llamada aplicaciones puede en la práctica contener algunos 
frameworks sofisticados. Estos frameworks pueden también definir los protocolos, servicios 
y / o APIs, por ejemplo, los frameworks de orquestación de servicios Web. 
7.3 COMPUTATIONAL GRID 
El recurso más utilizado son los ciclos de cómputo proporcionado por los procesadores de 
las máquinas en la red. Los procesadores pueden variar en velocidad, la arquitectura, la 
plataforma de software, y otros factores asociados, como la memoria, almacenamiento y 
conectividad. Hay tres formas principales para explotar los recursos de computación en un 
Grid (Berstis, 2002). La primera y más sencilla es utilizarlo para ejecutar una aplicación 
existente en una máquina disponible en la red en lugar de a nivel local. La segunda es 
utilizar una aplicación diseñada para dividir su labor de una manera tal que las partes 
separadaspueden ejecutar en paralelo en diferentes procesadores. El tercero es ejecutar 
una aplicación que necesita ser ejecutada muchas veces en muchas máquinas diferentes 
en la red. 
Computational Grid, también llamado compute grid (en español grid de cómputo) nos 
permiten realizar cálculos, un cálculo es tratado como una tarea que opcionalmente 
podemos dividirlos en varias subtareas, y ejecutarlas en diferentes nodos de la red en 
paralelo (“Compute Grids vs. Data Grids - DZone Java,” n.d.). El beneficio claro es que 
nuestro cálculo se realice más rápido, ya que ahora puede utilizar los recursos de los nodos 
de la red al tiempo. Uno de los patrones de diseño más comunes para la ejecución en 
paralelo es MapReduce. Sin embargo, los grids de cómputo son útiles incluso si no tenemos 
que dividir el cálculo, dado que nos ayudan a mejorar la escalabilidad global y la tolerancia 
a fallos del sistema mediante la descarga de los cálculos en la mayoría de los nodos 
disponibles. 
 
Figura 2 Planificación de tareas de una aplicación grid (Berstis, 2002). 
 
Algunas tareas pueden calcular algo, ejecutar uno o más comandos del sistema, mover o 
recoger datos, o manejar maquinaria. Una aplicación de grid organizada como un conjunto 
tareas es generalmente diseñada para que estas tareas se ejecuten en paralelo en 
diferentes máquinas en la red (Berstis, 2002). Los trabajos pueden tener dependencias 
específicas que pueden impedir que se ejecuten en paralelo en todos los casos. Por 
ejemplo, Algunas tareas pueden requerir la salida producida por otras tareas y no pueden 
ser ejecutadas hasta que esas tareas hayan terminado de ejecutarse. Este flujo de trabajo 
puede crear una jerarquía tareas y subtareas. Por último, los resultados de todas las tareas 
deben ser recogidos y debidamente ensamblados para producir la respuesta definitiva para 
la aplicación. 
7.4 DATA GRID 
El segundo recurso más común que se utiliza en un grid es el almacenamiento de datos. 
Un grid que proporciona una visión integrada de almacenamiento de datos a veces se llama 
una "data grid." Un Data Grid es una arquitectura particular de Grid enfocada en 
proporcionar servicios especializados para administrar gran cantidad de datos (Rahman et 
al., 2007). Esta arquitectura provee sistemas de archivos distribuidos en ambientes 
heterogéneos y geográficamente distribuidos. Cada nodo en el grid por lo general 
proporciona una cierta cantidad de almacenamiento para uso del grid, aunque temporal. El 
almacenamiento puede ser memoria o almacenamiento secundario usando discos duros u 
otro dispositivo de almacenamiento permanente. La memoria permite acceso rápido pero 
volátil, puede ser usada como caché de las aplicaciones que se están ejecutando. 
El almacenamiento secundario en un data grid debe aumentar espacio, desempeño, 
confiabilidad de los datos. Existen múltiples componentes en los niveles altos de una 
arquitectura de un Data Grid que permiten proveer estas características, tales como el 
manejo de réplicas. Uno de los retos importantes de investigación en data grids es la réplica 
de los datos. La replicación es la creación y administración de copias de archivos en el 
sistema de almacenamiento especificado (Brezany, Woehrer, & Tjoa, 2006). 
La meta de los sistemas de archivos para grid es proporcionar un desempeño razonable de 
operaciones de entrada y salida para aplicaciones data-intensive en área amplia. Estos 
sistemas usan los metadatos y los datos de los archivos en servicios separados, de esta 
manera permitir y explotar el acceso paralelo a los datos. La mayoría de sistemas de 
archivos modernos usan almacenamiento basado en objetos en lugar del basado en 
bloques, para reducir el costo de administración de metadatos y mejorar el desempeño del 
acceso a los datos (Tatebe, Hiraga, & Soda, 2010). 
Los principales componentes de un sistema de archivos para grid son: administrador de 
metadatos, servidores de datos y los clientes(Tatebe et al., 2010). En xtreemfs los 
componentes son: catálogo de réplicas y metadatos (MRC), servidor de almacenamiento 
de objetos (OSD), el servicio de directorio (DIR) y los clientes (Hupfeld et al., 2008). El 
componente de metadatos es el encargado de administrar los datos sobre el archivo, el 
número de inodos u objetos, entradas de directorio y ubicación de las réplicas. 
La réplica de datos es una excelente técnica para ubicar los datos más cerca de los clientes. 
La replicación es usada para disminuir la latencia de la red y el consumo del ancho de 
banda. También mejora la disponibilidad debido a las múltiples copias de los datos. La 
creación y la selección de réplicas son los retos más importantes en el desarrollo de un 
Data Grid. Algunos de los sistemas de archivos usados en Data Grid son: 
7.4.1 XtreemFS 
XtreemFS es un sistema de archivos distribuido y replicado para el uso en Cloud 
(XtreemFS, 2012). XtreemFS ha sido diseñado para el uso en redes de área amplia (WAN), 
permite autenticación y el uso de SSL. XtreemFS también permite la configuración para el 
particionamiento de los archivos (distribuido). Una desventaja de este sistema de archivos 
es que el sistema es administrado por un solo servidor, el cual puede ser un cuello de botella 
o un punto único de fallo (Hupfeld et al., 2008) . 
Al igual que otros sistemas de archivos basados en objetos, XtreemFS consiste de 
clientes, Dispositivos de Almacenamiento de Objetos (OSD) y servidores de metadatos 
llamado Catálogo de Metadatos y Replica (MRC). Adicionalmente a estos 3 componentes, 
un servicio de directorio actúa como registro para servidores y volúmenes del sistema de 
archivos (Hupfeld et al., 2008). 
Un XtreemFS MRC aloja múltiples volúmenes y actúa como un servidor de metadatos para 
los clientes que monten y accedan uno de sus volúmenes. Un MRC almacena toda la 
información acerca de los volúmenes alojados en una base de datos embebida, la cual tiene 
un mecanismo para replicar sus datos a otros hosts (Hupfeld et al., 2008). El servicio de 
directorio de XtreemFS conecta todos los componentes del sistema de archivos. El servicio 
de directorio permite a los clientes localizar los MRCs que son responsables por un cierto 
volumen, registra los servidores y les permite intercambiar información dinámica (Hupfeld 
et al., 2008). XtreemFS OSDs proporciona a los clientes con acceso rápido a los objetos 
que ellos almacenan. OSDs son responsables por el almacenamiento actual sobre sus 
discos. La lógica del OSD es dedicada a asegurar la consistencia de las réplicas de los 
archivos (Hupfeld et al., 2008). Xtreemfs permite la administración de la localización de las 
réplicas al usuario, el usuario decide donde ubicar sus réplicas y que tipo de réplica realizar. 
Permite usar dos tipos de réplicas de sólo lectura y de lectura y escritura. Las réplicas de 
sólo lectura son más fáciles de administrar, debido a su condición. XtreemFS también ha 
incorporado la posibilidad de usar un software de terceros, Vivaldi (XtreemFS, 2012) 
(Dabek, Cox, Kaashoek, & Morris, 2004), para administrar la selección de las réplicas. 
7.4.2 dCache 
dCache es un administrador de archivos jerárquicos diseñado para optimizar el uso 
del espacio en caché de disco para la carga que implica mover grandes cantidades de 
datos entre cintas y aplicaciones que se encuentran ejecutándose (Thain, 2004). dCache 
es un sistema que proporciona la distribuidor de espacios de nombres de archivo y un 
administrador de espacios de datos. dCache es hábil para coordinar una gran cantidad de 
nodos. Este sistema tiene la capacidad de ejecutarse sin un sistema de archivos, o con un 
número arbitrario de instancias y/o clases de sistemas de archivos. dCache provee un 
protocolo de acceso privado llamado dCap (Fuhrmann, 2004)(Ernst, Fuhrmann, Gasthuber, 
Mkrtchyan, & Waldman, 2001). Otra de sus características es que separa los datos de los 
metadatos,almacena los metadatos en una base de datos PostgreSQL. 
El sistema es capaz de detectar donde se encuentran los datos y, si es requerido, distribuir 
los conjuntos de datos más usados entre los múltiples nodos. Esta característica permite 
que la réplica de los archivos pueda estar en varios nodos. Uno de los aspectos claves en 
dcache es que la localización y número de réplicas en dCache., es determinado de forma 
autónoma por el sistema (Höfling, 2008). Este sistema de réplica es basada en el archivo 
de configuración, la carga del sistema y el espacio en disco. Un archivo puede estar 
replicado en al menos N nodos, pero no más de M. dCache implementa un administrador 
de pools, encargado de realizar las réplicas y evitar la sobrecarga de los pools(Fuhrmann, 
2004). 
7.4.3 Gfarm 
Gfarm es un sistema de archivos distribuido para compartir información y soportar la 
computación data-intensive distribuida. Gfarm usa los sistemas de archivos locales en un 
nodo de cómputo para maximizar el ancho de banda de E/S de un archivo 
distribuido, también permite almacenar varias réplicas de un archivo para disminuir el uso 
del ancho de banda. Gfarm es diseñado para compartir archivos entre múltiples dominios 
administrativos y soportar análisis de datos distribuidos en una WAN. No es simplemente 
compartir archivos, también es necesario proporcionar un desempeño aceptable para 
aplicaciones data-intensive (Tatebe et al., 2010). 
El sistema de archivos Gfarm consiste de un servidor de metadatos (MDS), servidores 
E/S (nodos del sistema de archivos) y clientes. El MDS administra los metadatos del 
sistema de archivos, el estado del archivo y de los nodos del sistema, la información de la 
membresía del grupo y cuentas de usuario globales. Los servidores de E/S proporcionan el 
acceso del archivo a un sistema de archivos locales. El cliente se conecta directamente al 
servidor E/S cuando está accediendo a los datos del archivo (Tatebe et al., 2010). 
7.5 BIBLIOGRAFIA 
Berstis, V. (2002). Fundamentals of grid computing. IBM Redbooks Paper, 1–28. Retrieved 
from 
http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:Fundamentals+of+Grid+
Computing#0 
Brezany, P., Woehrer, a., & Tjoa, a. M. (2006). The Grid: vision, technology development 
and applications. E & I Elektrotechnik Und Informationstechnik, 123(6), 251–258. 
http://doi.org/10.1007/s00502-006-0344-0 
Compute Grids vs. Data Grids - DZone Java. (n.d.). Retrieved September 18, 2015, from 
https://dzone.com/articles/compute-grids-vs-data-grids 
Dabek, F., Cox, R., Kaashoek, F., & Morris, R. (2004). Vivaldi: A decentralized network 
coordinate system. ACM SIGCOMM Computer …. Retrieved from 
http://dl.acm.org/citation.cfm?id=1015471 
Ernst, M., Fuhrmann, P., Gasthuber, M., Mkrtchyan, T., & Waldman, C. (2001). dCache, a 
distributed storage data caching system. Proceedings of Computing in High Energy 
Physics. 
Foster, I. (2002). What is the Grid ? A Three Point Checklist. GRID Today, 1, 32–36. 
http://doi.org/10.1103/PhysRevE.66.031916 
Foster, I., & Kesselman, C. (2003). Concepts and Architecture. In The Grid 2: Blueprint for 
a New Computing Infrastructure (pp. 37–63). 
Foster, I., Kesselman, C., & Tuecke, S. (2001). The anatomy of the grid: Enabling scalable 
virtual organizations. International Journal of High …. Retrieved from 
http://dl.acm.org/citation.cfm?id=1080667 
Fuhrmann, P. (2004). dCache, the Overview. White Paper, 1–6. Retrieved from 
http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:dCache+,+the+Overview
#0 
Höfling, M. (2008). On Data Placement Issues in Grid Computing Environments, 
(November). Retrieved from 
http://www8.cs.umu.se/education/examina/Rapporter/MichaelHoflingMT.pdf 
Hupfeld, F., Cortes, T., Focht, E., Hess, M., Malo, J., Marti, J., & Cesario, E. (2008). The 
XtreemFS architecture — a case for object-based file, (March), 2049–2060. 
http://doi.org/10.1002/cpe 
Tatebe, O., Hiraga, K., & Soda, N. (2010). Gfarm Grid File System. New Generation 
Computing, 28(3), 257–275. http://doi.org/10.1007/s00354-009-0089-5 
Thain, D. (2004). Coordinating Access to Computation and Data in Distributed Systems. 
University of Wiscosin - Madison. Retrieved from 
http://pages.cs.wisc.edu/~thain/library/thain-dissertation.pdf 
URL3. (2012). Computación Grid. Retrieved January 1, 2012, from 
http://es.wikipedia.org/wiki/Computación_grid 
XtreemFS. (2012). XtreemFS, a cloud filesystem. Retrieved from http://www.xtreemfs.org 
 
 
8 SIMULADORES DE AMBIENTES GRID 
8.1 INTRODUCCIÓN 
El diseño de sistemas que soporten la computación grid es una tarea compleja que involucra 
varios problemas, tales como: administración de recursos, desempeño de la red, seguridad, 
heterogeneidad, tolerancia a fallos, adaptabilidad, escalabilidad, concurrencia y 
transparencia. Realizar una investigación en un ambiente grid real es complejo, dado que 
inicialmente se requiere configurar y mantener dicho sistema y luego es necesario realizar 
las pruebas en múltiples ambientes grid (Dumitrescu & Foster, 2005). Además, en un 
ambiente real, evaluar un nuevo sistema es difícil por múltiples razones, inicialmente una 
evaluación en sistema real puede consumir demasiado tiempo; también los nodos y 
dispositivos son heterogéneos y existen múltiples variables no controladas dentro del 
sistema que impiden que un experimento sea repetible. Debido a esto, la mayoría de las 
investigaciones en sistemas distribuidos son realizadas usando herramientas de 
simulación. 
La simulación ha sido investigada y aplicada exitosamente en varios procesos, objetos y 
aplicaciones del mundo real. Proporciona la evaluación de múltiples problemas, tales como 
la factibilidad, el comportamiento y el desempeño sin la necesidad de construir un sistema 
real, de esta manera se puede ahorrar en tiempo y costos (Sulistio, Yeo, & Buyya, 2004). 
La creación de un modelo de simulación puede ser una tarea tan compleja como crear el 
sistema mismo, dado que los investigadores, muchas veces, no son expertos 
programadores, lo que les impide crear un nuevo programa que permita simular un 
ambiente para su proyecto. Sin embargo, existen diversas herramientas de simulación, 
estas herramientas permiten a los investigadores la posibilidad de evaluar sus teorías en 
múltiples ambientes y compararlas con otras teorías existentes. De esta manera, el 
investigador se enfoca en el diseño e implementación de la teoría escogida (Dumitrescu & 
Foster, 2005). Cada herramienta de simulación requiere un nivel de conocimiento menor 
que construir una aplicación que provea las características mencionadas. 
Como objetivo de esta tesis se planteó una taxonomía de las herramientas de simulación 
de ambientes grid, se realiza una revisión de algunas de ellas que son comúnmente 
utilizadas por la comunidad científica y se clasifican utilizando la taxonomía propuesta, para 
una mejor referencia revisar el anexo a este documento. En las siguientes secciones 
revisamos las herramientas con mayor cantidad de citas en artículos indexados, Microgrid 
(Xia, Dail, Casanova, & Chien, 2004), GridSim (Buyya & Murshed, 2002), SimGrid 
(Casanova, Legrand, & Quinson, 2008), OptorSim (D. Cameron & Millar, 2004; URL, 2013) 
y Gangsim(Dumitrescu & Foster, 2005) . 
8.2 MICROGRID 
Microgrid (Xia et al., 2004) provee un infraestructura grid virtual que permite la 
experimentación científica con técnicas de administración de recursos dinámicas y 
aplicaciones adaptativas para soportar experimentos controlados y repetitivos. Microgrid 
ha sido diseñado para emular grids Globus. Microgrid es diseñado para soportar ambientes 
de software grid reales (Quetier & Cappello, 2005). 
Microgrid permite a los investigadores ejecutar sus aplicaciones en un ambiente grid virtual. 
Este ambiente presenta a la aplicación una vista de servicios de información y recursos 
virtuales. Estos recursos se ejecutan sobre losrecursos físicos y MicroGrid puede explotar 
recursos heterogéneos u homogéneos (Figura 2). 
 
Figura 3 Arquitectura de Microgrid (Xia et al., 2004) 
8.3 GRIDSIM 
GridSim(Buyya & Murshed, 2002) (URL, 2015) permite el modelado y simulación de 
entidades, como usuarios del sistema, aplicaciones, recursos y planificadores, en 
computación en paralelo y distribuida, para el diseño y evaluación de algoritmos de 
planificación. Cada usuario se caracteriza por: tipo de trabajo (tiempo de ejecución, el 
número de la replicación paramétrico, etc.), la estrategia de optimización de la 
programación, la tasa de actividad, la zona horaria, fecha límite y presupuesto. Los recursos 
se describen con número de procesadores, el costo de procesamiento, rendimiento, política 
de planificación interna, carga de trabajo, la zona horaria. GridSim no diferencia entre tareas 
y datos. Gridsim está implementado en Java y usa SimJava como el framework base de la 
simulación. Se han agregado varias funcionalidades a la base inicialmente desarrollada. La 
arquitectura de GridSim tiene cinco niveles (Figura 4). 
 
Figura 4 Arquitectura de GridSim (Buyya & Murshed, 2002) 
8.4 SIMGRID 
SimGrid (Casanova et al., 2008)(URL, n.d.) es un framework de simulación cuya meta es 
proveer una herramienta de evaluación genérica para computación distribuida a gran 
escala. Sus componentes principales son dos: un API para investigadores que estudian 
algoritmos y necesitan rápidamente prototipos de simulación y un API para que los 
desarrolladores puedan implementar sus aplicaciones en el confort de un mundo simulado 
antes de subirlas al mundo real. SimGrid es disponible bajo licencia LGPL desde su página 
web y se puede ejecutar en Linux, Windows, Mac Os X y en AIX. SimGrid usa un kernel de 
simulación modular que permite la adición y el uso de nuevos modelos sin cambios en el 
código de usuario. 
 
Figura 5 Arquitectura de componentes Simgrid (URL, n.d.) 
8.5 OPTORSIM 
Optorsim (URL, 2013)(Bell & Cameron, 2003)(Xun-yi, Ru-chuan, & Qiang, 2010) está 
basado en la arquitectura del proyecto EU DataGrid, simula un ambiente de un grid de 
almacenamiento real para que los investigadores estudien la efectividad de los algoritmos 
de optimización. La estructura simulada asume varios sitios, un administrador de recursos 
(resource brooker). Cada sitio grid en Optorsim contiene varios elementos de cómputo, 
elementos de almacenamiento y un administrador de réplicas (Figura 6). Uno de los 
conceptos claves en los grids de almacenamiento es la réplica de los datos, involucrando 
la creación y administración de las réplicas. 
8.6 GANGSIM 
Gangsim(Dumitrescu & Foster, 2005) es un simulador de planificación, es derivado del 
Proyecto Ganglia, una herramienta de monitoreo de sistemas distribuidos. La novedad de 
Gangsim es que además del uso de sitios, involucra usuarios y planeadores de 
Organizaciones Virtuales (VO, por sus siglas en inglés) y su habilidad para modelar las 
políticas de uso al nivel de sitios y organizaciones virtuales. Esto permite evaluar como 
interfieren las políticas de uso de recursos, políticas de planeación y la carga de trabajo en 
el comportamiento de los planificadores de las organizaciones virtuales. Gangsim permite 
la ejecución en paralelo y puede combinar la simulación con la ejecución en ambientes 
reales (bancos de pruebas). Se encuentra inactiva y el código fuente no se encuentra 
disponible. 
 
 
Figura 6 Arquitectura de OptorSim (D. Cameron & Millar, 2004) 
8.7 MONARC 
MONARC (Models of Networked Analysis at Regional Centers for Large Hadron Collider 
Experiments) (Dobre & Stratan, 2011) es un framework de simulación diseñado e 
implementado para el proyecto que lleva su mismo nombre. El framework proporciona un 
conjunto completo de componentes básicos (nodos de procesamiento, servidores de datos, 
componentes de red) junto con unidades de decisión (módulos de replicación de datos o 
planificación). La segunda versión de MONARC, llamada MONARC II, incorpora el soporte 
para simular algoritmos para la réplica de datos y para la planificación de tareas. El 
simulador MONARC provee mecanismos para describir tráfico de red concurrente y evaluar 
diferentes estrategias en replicación de datos o en procedimientos de planificación de 
tareas. 
8.8 RESUMEN 
 
Actualmente existen múltiples simuladores que nos permiten realizar pruebas de las 
aproximaciones de algoritmos o sistemas de planificación para mejorar los tiempos de 
respuesta en el grid. Estos simuladores pueden acelerar el proceso de estas pruebas dado 
que en un sistema real las ejecuciones pueden tardar mucho tiempo y puede ser complejo 
desplegar una determinada configuración. En los sistemas reales también es complejo 
repetir una ejecución y por tanto no es fácil comparar la aptitud de cada técnica probada, 
pues los tiempos de conexión, latencias y cargas de procesamiento pueden ser diferentes. 
Podemos escoger una herramienta de simulación que se ajuste a nuestras necesidades, 
según la taxonomía propuesta en el anexo de este trabajo existen herramientas para 
simular como bancos de pruebas, emuladores y simuladores. 
Para este trabajo, hemos escogido a Optorsim como la herramienta de simulación que nos 
ayude a comparar entre las técnicas escogidas para la localización de réplicas en 
ambientes grid. Optorsim es un sistema de simulación que ha sido diseñado para la 
evaluación de optimización de almacenamiento. Aunque Optorsim también permite evaluar 
la planificación de tareas en un Compute Grid. Optorsim ha sido ampliamente utilizado para 
la evaluación de algoritmos de administración de réplicas en múltiples investigaciones 
(Belalem, 2009; D. G. Cameron et al., 2004; Jiang & Yang, 2007; Madi, Yusof, Hassan, & 
Almomani, 2011; Rasool, Li, Oreku, & Munir, 2007; Xun-yi et al., 2010). También es un 
simulador escrito en Java y de código abierto, que nos permite ejecutarlo en cualquier 
plataforma y además realizarle los ajustes necesarios. 
8.9 BIBLIOGRAFIA 
Belalem, G. (2009). Economic Model for Consistency Management of Replicas in 
Data Grids with OptorSim Simulator. Networks for Grid Applications, 121–
129. Retrieved from http://link.springer.com/chapter/10.1007/978-3-642-
02080-3_13 
Bell, W., & Cameron, D. (2003). Optorsim: A grid simulator for studying dynamic 
data replication strategies. … Journal of High …, 1–20. Retrieved from 
http://hpc.sagepub.com/content/17/4/403.short 
Buyya, R., & Murshed, M. (2002). Gridsim: A toolkit for the modeling and 
simulation of distributed resource management and scheduling for grid 
computing. Concurrency and Computation: Practice …, 1–37. 
Cameron, D. G., Millar, a. P., Nicholson, C., Carvajal-Schiaffino, R., Stockinger, 
K., & Zini, F. (2004). Analysis of Scheduling and Replica Optimisation 
Strategies for Data Grids Using OptorSim. Journal of Grid Computing, 2(1), 
57–69. http://doi.org/10.1007/s10723-004-6040-6 
Cameron, D., & Millar, A. (2004). Optorsim: a simulation tool for scheduling and 
replica optimisation in data grids. Computing in High Energy …. Retrieved 
from 
http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:OPTORS
IM+:+A+SIMULATION+TOOL+FOR+SCHEDULING+AND+REPLICA+OPTIM
ISATION+IN+DATA+GRIDS#0 
Casanova, H., Legrand, A., & Quinson, M. (2008). SimGrid: A generic framework 
for large-scale distributed experiments. Proceedings - UKSim 10th 
International Conference on Computer Modelling and Simulation, 
EUROSIM/UKSim2008, 126–131. http://doi.org/10.1109/UKSIM.2008.28 
Dobre, C., & Stratan, C. (2011). MONARC Simulation Framework. Proc. of the 
RoEduNet International Conference, 49(63), 35–42. Retrieved from 
http://arxiv.org/abs/1106.5158 
Dumitrescu, C. L., & Foster, I. (2005). GangSim: a simulator for grid scheduling 
studies. CCGrid 2005. IEEE International Symposium on Cluster Computing 
and the Grid, 2005., 1151–1158 Vol. 2. 
http://doi.org/10.1109/CCGRID.2005.1558689Jiang, J., & Yang, G. (2007). An optimal replication strategy for data grid 
systems. Frontiers of Computer Science in China, 1(3), 338–348. 
http://doi.org/10.1007/s11704-007-0033-0 
Madi, M., Yusof, Y., Hassan, S., & Almomani, O. (2011). A Novel Replica 
Replacement Strategy for Data Grid, 717–727. 
Quetier, B., & Cappello, F. (2005). A survey of Grid research tools: simulators, 
emulators and real life platforms. IMACS World Congress. Retrieved from 
http://scholar.google.com/scholar?hl=en&btnG=Search&q=intitle:A+surve
y+of+Grid+research+tools+:+simulators+,+emulators+and+real+life+pl
atforms#0 
Rasool, Q., Li, J., Oreku, G. S., & Munir, E. U. (2007). A Comparative Study of 
Replica Placement Strategies in Data Grids, 135–143. 
Sulistio, A., Yeo, C. S., & Buyya, R. (2004). A taxonomy of computer-based 
simulations and its mapping to parallel and distributed systems simulation 
tools. Software: Practice and Experience, 34(7), 653–673. 
http://doi.org/10.1002/spe.585 
URL. (n.d.). SimGrid: SimGrid Documentation. Retrieved August 17, 2015, from 
http://simgrid.gforge.inria.fr/simgrid/3.10/doc/ 
URL. (2013). Optorsim: data access grid simulator. Retrieved from http://edg-
wp2.web.cern.ch/edg-wp2/optimization/optorsim.html 
URL. (2015). The CLOUDS Lab: Flagship Projects - Gridbus and Cloudbus. 
Retrieved August 17, 2015, from http://www.cloudbus.org/gridsim/ 
Xia, H. X. H., Dail, H., Casanova, H., & Chien, a. a. (2004). The MicroGrid: using 
online simulation to predict application performance in diverse grid network 
environments. Proceedings of the Second International Workshop on 
Challenges of Large Applications in Distributed Environments, 2004. CLADE 
2004. http://doi.org/10.1109/CLADE.2004.1309092 
Xun-yi, R. E. N., Ru-chuan, W., & Qiang, K. (2010). Using optorsim to efficiently 
simulate replica placement strategies. The Journal of China Universities of 
Posts and Telecommunications, 17(1), 111–119. 
http://doi.org/10.1016/S1005-8885(09)60434-9 
 
 
 
 
 
9 INTELIGENCIA COMPUTACIONAL 
9.1 INTRODUCCIÓN 
El desarrollo de la inteligencia computacional nace de la necesidad de encontrar soluciones 
óptimas a problemas complejos computacionalmente, debido al espacio de soluciones 
posibles o la gran cantidad de datos a evaluar. Estas técnicas han sido especialmente 
desarrolladas en la actualidad, dada la posibilidad de obtener grandes volúmenes de datos 
y la necesidad de optimizar los recursos. La inteligencia computacional se inspiró en 
aspectos observables e imitables de la actividad inteligente del ser humano y de la 
naturaleza. La naturaleza cuando emprende acciones que requieran de inteligencia, 
procesa los datos y ajusta las acciones usando mecanismos de retroalimentación 
(Rutkowsku 2007), de esta manera funciona el sistema de aprendizaje de redes neuronales 
artificiales. Otro ejemplo son los algoritmos de optimización basados en procesos de 
selección natural, comportamiento de grupos o sistemas de lógica difusa que reflejan la 
aleatoriedad, imprecisión, subjetividad o relativismo de las evaluaciones de la naturaleza. 
La estructura de este capítulo es como sigue, en la segunda sección de este capítulo 
revisaremos el concepto de aprendizaje de máquinas y los tipos de aprendizaje. Después 
veremos algunas técnicas usadas en inteligencia computacional. Más adelante se revisará 
Inteligencia de Enjambres, la cual es una técnica muy interesante para el desarrollo del 
problema de réplicas en grid por sus características que facilitan su uso en sistemas 
distribuidos. Finalmente se presenta un resumen del capítulo. 
9.2 APRENDIZAJE 
Las teorías desarrolladas de inteligencia computacional fueron rápidamente aplicadas a 
muchos campos de la ingeniería, análisis de datos, pronóstico, biomedicina, bioinformática 
y otros. La idea central de la inteligencia computacional es el aprendizaje. El aprendizaje es 
la habilidad de un sistema para cambiar, o evolucionar, sus parámetros para mejorar la 
búsqueda de un objetivo. Aprendizaje dinámico es la habilidad para adaptarse “en línea”, 
en tiempo real en un ambiente cambiante (Cass & DePietro 1998). Existen tres tipos de 
aprendizaje o adaptación: 
Aprendizaje supervisado 
En el aprendizaje supervisado un “profesor” proporciona ejemplos relevantes de entrada y 
salida. El sistema emula los ejemplos de entrenamiento mientras adquiere la habilidad para 
generalizarlos. Un ejemplo de aprendizaje supervisado son las redes neuronales artificiales 
usando el algoritmo back-propagation. Los patrones de entrada para los cuales los 
patrones de salida son conocidos están presentes en la red. Alguna función de error en 
cada salida es usada para ajustar los parámetros del sistema. En este caso, los pesos de 
la red neuronal son ajustados en un intento por minimizar el error. 
Aprendizaje con refuerzo 
El aprendizaje con refuerzo de un sistema es dado usando un “crítico” el cual provee 
información heurística de refuerzo. La información variable de entrada a menudo incluye 
un rango dinámico de cada variable y quizá otra información que indique la precisión 
requerida. El crítico provee algo medida de aptitud basada en la meta. La aptitud no puede 
ser obtenida directamente, pero es una sugerencia de que tan buena es la solución con 
respecto a las otras soluciones. 
De los tipos de aprendizaje esta es más cercana a los sistemas biológicos, un ejemplo es 
que los animales tienden a evitar el comportamiento que les molesta y repetir con el que se 
sienten a gusto. El aprendizaje con refuerzo tiene sus raíces en la teoría de control de 
óptimos llamada programación dinámica. 
Aprendizaje no supervisado 
En el Aprendizaje no supervisado no se involucra un profesor o crítico. La interpretación del 
resultado del algoritmo no supervisado, que tan bueno es y si es apropiado o útil es 
realizada al finalizar el algoritmo. A menudo esta evaluación es realizada por un humano u 
otro sistema inteligente. 
Clustering agrega patrones de entradas similares en distintos subconjuntos mutualmente 
excluyentes llamados clústers. 
9.3 TÉCNICAS DE INTELIGENCIA COMPUTACIONAL 
La inteligencia computacional se ha convertido en una rama de investigación importante 
que se encarga de imitar o simular el comportamiento de aspectos importantes de la 
naturaleza a través de algoritmos matemáticos y sistemas para la búsqueda de soluciones 
a problemas complejos. Tales algoritmos se basan en la aplicación de las siguientes 
técnicas (Rutkowsku 2007): 
a. Redes Neuronales 
b. Lógica difusa 
c. Computación evolutiva 
d. Rough Sets 
e. Variables inciertas 
f. Métodos probabilísticos. 
g. Inteligencia de enjambres 
La inteligencia computacional no cubre únicamente las técnicas individuales sino también 
la combinación de varias técnicas. Estas técnicas son aplicadas comúnmente a problemas 
clásicos de inteligencia artificial. Como por ejemplo, procesar y hablar el lenguaje natural, 
construir sistemas expertos y robots, búsqueda de información y también para las 
necesidades de aprendizaje de las máquinas. 
Optimización es el corazón de muchos procesos naturales, incluyendo la evolución de 
Darwin y el comportamiento social de grupos. Las dos ramas principales de algoritmos que 
constituyen principalmente el campo de la optimización usando inteligencia computacional 
son los métodos de computación evolutiva, los algoritmos de inteligencia de enjambre y de 
búsqueda de alimento. Aunque ambas familias de algoritmos se dedican generalmente a la 
solución de búsqueda y optimización de problemas, ciertamente no son equivalentes, y 
cada uno tiene sus propias características distintivas. 
Debido a su naturaleza, la Inteligencia de Enjambres muestra unas características 
interesantes en el diseño de soluciones distribuidas a problemas, pues esta técnica está 
basada en el comportamiento observado de un conjunto que individuos que colaboran entre 
sí, demanera descentralizada y auto organizada, para la búsqueda de un objetivo 
(búsqueda de alimento, huir de depredadores, etcétera). Cada uno de los individuos de la 
población son autónomos y su comportamiento se transforma basado en sus vecinos y en 
la modificación del ambiente. 
9.4 INTELIGENCIA DE ENJAMBRES 
La inteligencia de enjambres está basada en los principios subyacentes del comportamiento 
natural de los sistemas que consiste de muchos agentes y explotar las comunicaciones 
locales y el control altamente distribuido. El método de inteligencia de enjambres constituye 
un modelo muy práctico y poderoso que simplifica el diseño de soluciones distribuidas a 
diferentes tipos de problemas(Ding et al. 2011). 
Los sistemas de inteligencia de enjambres están compuestos por una población de agentes 
con capacidades limitadas, que interactúan localmente entre ellos o con el ambiente y de 
esta manera son hábiles para resolver problemas complejos. Los enjambres utilizan formas 
de control descentralizado y auto-organización para llegar a sus metas (Sehrawat 2013). 
Investigadores en ciencias de la computación han desarrollado sistemas de inteligencia de 
enjambres en respuesta al éxito y eficiencia observada en los enjambres de la naturaleza 
para resolver problemas complejos. En estos enjambres biológicos los individuos 
(hormigas, pájaros, termitas, pescados o abejas) son simples criaturas con habilidades 
cognitivas y de comunicación limitadas que exhiben un comportamiento colectivo inteligente 
para proveer soluciones eficientes para problemas complejos como la evasión de 
depredadores y búsqueda de la ruta más corta (Sehrawat 2013). 
Los principios fundamentales del comportamiento colectivo de enjambres son (Ding et al. 
2011; Sehrawat 2013): 
a. Homogeneidad: cada individuo en el enjambre tiene el mismo comportamiento. El 
enjambre se mueve sin un líder, aunque líderes temporales aparezcan. 
b. Localidad: El movimiento de cada individuo es solamente influenciado por sus 
compañeros de enjambre más cercanos. 
c. Evitación de colisiones: Evitar con los compañeros de enjambre cercanos. 
d. Coincidencia de velocidad: Intentar coincidir con la velocidad de los compañeros de 
enjambre cercanos. 
e. Agrupamiento de enjambre: Mantenerse cerca a los compañeros de enjambre 
cercanos. 
Los sistemas basados en la inteligencia de enjambres tienen también las siguientes 
características: 
a. Autonomía: El sistema no requiere administración o mantenimiento externo. 
b. Adaptabilidad: Los individuos tienen la habilidad para detectar y generar cambios en 
el ambiente dinámicamente (comunicación indirecta). Ellos pueden de manera 
autónoma adaptar su nuevo comportamiento a estos cambios. 
c. Escalabilidad: Las habilidades del sistema pueden ser realizadas usando desde 
grupos pequeños hasta grupos de miles de individuos con la misma arquitectura. 
d. Flexibilidad: Los individuos no son esenciales, por tanto de manera dinámicamente 
pueden ser adicionados, removidos o reemplazados. 
e. Robustez: No hay un punto único de fallo debido a que no hay una coordinación 
central. Y al combinar escalabilidad y flexibilidad el sistema permite redundancia que 
es esencial para la robustez. 
f. Paralelo: El sistema es realmente paralelo y su funcionamiento es completamente 
distribuido. Las tareas realizadas por cada individuo dentro del grupo son las 
mismas. 
g. Auto-organización: La inteligencia exhibida en los sistemas de enjambres no está 
presente en los individuos, pero de alguna manera emerge del enjambre completo. 
h. Costo-efectivo: El sistema consiste de una colección finita de agentes homogéneos 
con capacidades limitadas. Además cada agente tiene las mismas capacidades y 
algoritmos de control. Esto simplifica claramente el diseño de la implementación de 
algoritmos y hardware paralelo. 
 A continuación revisaremos los dos algoritmos de inteligencia de enjambres más utilizados 
en investigación de optimización y búsqueda (Sehrawat 2013). 
9.4.1 Ant Colony Optimization (ACO) 
Es una metaheurística basada en población que puede ser usada para encontrar soluciones 
aproximadas a problemas de optimización complejos. ACO es inspirado en el 
comportamiento para la búsqueda de alimento de algunas especies de hormigas. Las 
hormigas marcan el camino favorable depositando feromonas en la tierra que serán 
seguidos por otros miembros de la colonia. ACO simula este procedimiento para resolver 
problemas de optimización (Dorigo & Birattari 2004; Wong 2011; Salami 2009). Este tipo 
particular de comunicación indirecta entre individuos es llamada estigmergía. Las dos 
principales características de la estigmergía que la diferencian de otro tipo de comunicación 
son las siguientes: 
- Estigmergía es una forma de comunicación indirecta y sin símbolos usando el 
ambiente: los insectos intercambian información por modificar su ambiente; y 
- La información de la estigmergía es local: sólo puede ser accesible por estos 
insectos que visiten el espacio en el cual fue liberado o su vecindario inmediato. 
Estigmertía puede ser observada en el comportamiento de las hormigas cuando van en 
busca de algún alimento. En la mayoría de especies de hormigas en su camino a la fuente 
de alimento ellas depositan en el suelo una sustancia llamada feromona. Esta feromona se 
va evaporando a medida que pasa el tiempo y las demás hormigas siguen la ruta en la cual 
la concentración de feromona es más alto. En la Figura 7 podemos ver este 
comportamiento, en la ruta más corta la hormiga llega más rápidamente al nido y por tanto 
la concentración feromona en el camino trazado es más alto que la ruta más larga. Cuando 
la hormiga llegue al nido esta concentración ha mermado. Finalmente la mayoría de las 
hormigas toman el sendero más corto, que contiene la mayor concentración de feromonas. 
 
Figura 7 Usando Feromonas para la selección de la mejor ruta (Sehrawat 2013) 
El pseudocódigo de ACO es como sigue: 
Configurar parámetros, 
inicializar los senderos de feromonas 
Mientras la condición de terminación no se cumpla do 
 ConstruirSolucionesHormigas 
 AplicarBúsquedaLocal (optional) 
 Actualizar Feromonas 
Fin mientras 
9.4.2 Particle Swarm Optimization (PSO) 
El algoritmo de optimización por enjambre de partículas viene siendo una técnica de 
computación evolutiva y un importante algoritmo heurístico en los últimos años. PSO Es un 
método basado en población, esta población es llamada enjambre. PSO está inspirado en 
el comportamiento social de los pájaros al momento de volar o buscar alimento en manada 
(Ding et al. 2011; Kennedy & Eberhart 1995; Sehrawat 2013; Bai 2010). Los pájaros y peces 
ajustan su movimiento físico para evitar depredadores, buscar alimento y compañeros, 
optimizar la temperatura entre otros. 
PSO comparte muchas características con las técnicas de computación evolutiva tales 
como Algoritmos Genéticos. El sistema es inicializado con una población de soluciones 
aleatorias y actualiza las generaciones para buscar óptimos. En PSO las soluciones 
potenciales, llamadas partículas, vuelan a través del espacio del problema siguiendo las 
partículas óptimas. Cada partícula tiene un valor de aptitud, que son evaluados por una 
función de aptitud a ser optimizada. Las partículas también tienen velocidades que 
controlan el vuelo de las partículas. Esta velocidad es inicialmente aleatoria y se ajusta de 
acuerdo a su experiencia de vuelo y a la experiencia de sus vecinos. Las partículas cambian 
su condición siguiendo 3 principios. 
 Para mantener la inercia 
 Cambiar la condición de acuerdo a su posición más optimista. (pbest) 
 Cambiar la condición de acuerdo a la posición más optimista del enjambre. (gbest) 
Usando estos dos valores cada partícula cambia su velocidad y posición usando las 
siguientes ecuaciones (Sehrawat 2013): 
𝑣𝑖𝑑(𝑡 + 1) = 𝑣𝑖𝑑(𝑡) + 𝑐1𝑟𝑎𝑛𝑑( )(𝑝𝑏𝑒𝑠𝑡 − 𝑥𝑖𝑑(𝑡))