Impacto de las topolog19 as Grid en el monitoreo y...

Impacto de las topologıas Grid en el monitoreoy descubrimiento automatico de recursos

David Gonzalez MarquezDirectores: Lic. Diego Fernandez Slezak, Dr. Esteban Mocskos, Lic. Pablo Turjanski

Jurados: Lic. Cristian Rosa (INRIA) y Ing. Alejandro Furfaro

10 de junio de 2010

Indice general

1. Introduccion 41.1. Grid Computing . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2. Globus Toolkit . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.1. Arquitectura y Componentes . . . . . . . . . . . . . . . 81.3. Grid Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.1. Limitaciones . . . . . . . . . . . . . . . . . . . . . . . . 12

2. Metodologıa 152.1. Generacion de redes . . . . . . . . . . . . . . . . . . . . . . . . 152.2. Polıticas de monitoreo y descubrimiento de recursos . . . . . . 18

2.2.1. Polıtica Jerarquica . . . . . . . . . . . . . . . . . . . . 192.2.2. Algoritmos Peer to Peer (P2P) . . . . . . . . . . . . . 202.2.3. Implementacion de polıticas en MDS . . . . . . . . . . 242.2.4. Parametros para las polıticas de distribucion de infor-

macion . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.5. Construccion de los mensajes de recursos . . . . . . . . 25

2.3. Metricas de la calidad de la informacion . . . . . . . . . . . . 25

3. Desarrollo de GridMatrix 2 273.1. GridMatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2. GridMatrix2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3. Generacion de redes . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.1. Interfaz grafica para la generacion de redes . . . . . . . 323.3.2. Topologıas de red . . . . . . . . . . . . . . . . . . . . . 343.3.3. Presentacion en pantalla . . . . . . . . . . . . . . . . . 353.3.4. Traduccion a SimGrid2 (platform file) . . . . . . . . . 36

3.4. Configuracion de simulaciones . . . . . . . . . . . . . . . . . . 373.4.1. Interfaz grafica de generacion de Deploy . . . . . . . . 373.4.2. Generacion de jerarquıas . . . . . . . . . . . . . . . . . 403.4.3. Identificacion de super-peers . . . . . . . . . . . . . . . 43

i

3.4.4. Configuraciones adicionales para la generacion de re-sultados . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4. Resultados 454.1. Topologıas basicas de red . . . . . . . . . . . . . . . . . . . . . 454.2. Impacto de la cantidad de niveles en la polıtica Jerarquica . . 534.3. Impacto de la cantidad de Super-Peers . . . . . . . . . . . . . 574.4. Super-Peer y su lımite en la capacidad de escalar . . . . . . . 594.5. Impacto de la relacion entre tiempo de expiracion y ciclo de

actualizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5. Conclusiones 65

6. Trabajo Futuro 686.1. Topicos a profundizar utilizando GridMatrix2 en su version

actual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.2. Caminos que se abren mediante la extension de GridMatrix2 . 69

ii

Indice de figuras

1.1. Organizacion jerarquica de GRIS . . . . . . . . . . . . . . . . 71.2. Esquema de componentes de GT4 . . . . . . . . . . . . . . . . 81.3. Interfaz grafica de GridMatrix . . . . . . . . . . . . . . . . . . 12

2.1. Ejemplo de diferentes topologıas de red . . . . . . . . . . . . . 182.2. Esquema de funcionamiento de la polıtica Jerarquica . . . . . 192.3. Esquema de una red P2P . . . . . . . . . . . . . . . . . . . . . 202.4. Esquema de funcionamiento de la polıtica Random . . . . . . 212.5. Esquema de funcionamiento de la polıtica Best-Neighbor . . . 222.6. Esquema de funcionamiento de la polıtica Super-Peer . . . . . 23

3.1. Esquema de interaccion entre archivos en GridMatrix . . . . . 283.2. Esquema de interaccion entre archivos en GridMatrix2. En

verde se muestran las nuevas prestaciones implementadas. . . 303.3. Ejemplo de la informacion almacenada en un archivo platform

de SimGrid2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.4. Ejemplo de la informacion almacenada en un archivo de Grid-

Matrix2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.5. Interfaz Grafica del Generador de Redes de GridMatrix2 . . . 333.6. Interfaz Grafica del Generador de Platform . . . . . . . . . . . 373.7. Interfaz Grafica del Generador de Deploy . . . . . . . . . . . . 383.8. Ejemplo de utilizacion del algoritmo de Dijkstra para la gene-

racion de una jerarquıa a partir de los nodos. . . . . . . . . . . 413.9. Ejemplo de particion de nodos en niveles de un arbol . . . . . 423.10. Ejemplo del resultado de una posible eleccion de padres para

cada uno de los nodos en la jerarquıa . . . . . . . . . . . . . . 423.11. Ejemplo de particion entre nodos de una red. . . . . . . . . . . 44

4.1. GIR en topologıa clique . . . . . . . . . . . . . . . . . . . . . 464.2. GIR en polıtica jerarquica: dos niveles y variacion en tiempo

de expiracion . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.3. GIR en topologıa lınea . . . . . . . . . . . . . . . . . . . . . . 50

iii

4.4. GIR en topologıa anillo . . . . . . . . . . . . . . . . . . . . . . 514.5. GIR en topologıa Estrella . . . . . . . . . . . . . . . . . . . . 524.6. GIR en varios niveles de jerarquıas con 100 nodos . . . . . . . 544.7. GIR en varios niveles de jerarquıas con 200 nodos . . . . . . . 554.8. GIR en niveles con 300 nodos . . . . . . . . . . . . . . . . . . 564.9. Impacto de la cantidad de super-peers . . . . . . . . . . . . . 584.10. GIR y LIR del root en un esquema centralizado . . . . . . . . 604.11. GIR en capa super-peer . . . . . . . . . . . . . . . . . . . . . 614.12. GIR variando el tiempo de expiracion . . . . . . . . . . . . . . 624.13. GIR variando el ciclo de actualizacion . . . . . . . . . . . . . . 634.14. GIR obtenido por distintas polıticas en funcion de la relacion

entre tiempo de expiracion y frecuencia de actualizacion (R). 64

6.1. GIR promedio y aproximacion exponencial para una polıticaSuper-Peer variando la cantidad de superpeers . . . . . . . . . 69

6.2. Arbol de opciones de GridMatrix2 . . . . . . . . . . . . . . . . 70

iv

Resumen

Las tecnologıas Grid afloran como un nuevo paradigma en la computacion dealto rendimiento, proveyendo la infraestructura para compartir recursos geografi-camente distribuidos de forma transparente. Para administrar eficientemente estosrecursos es necesario conocer su estado y disponibilidad. En estos escenarios, ladinamica de la informacion es muy compleja, y resulta practicamente imposiblede ser capturada por una jerarquıa estatica. En este trabajo se estudian algunosde los mecanismos por los cuales se obtiene y distribuye informacion de recursosen un Grid. GridMatrix, provee un entorno de ejecucion para emular polıticasde distribucion de informacion en entornos Grid, utilizando para esto el motorde simulacion SimGrid2. En esta tesis se extendio la aplicacion GridMatrix conherramientas para la generacion automatica de topologıas de red Grid y la genera-cion automatica de configuraciones, permitiendo la creacion de una amplia gamade combinaciones de parametros, tanto para la generacion de redes, como para laconfiguracion de las simulaciones. La configuracion de parametros para las simu-laciones se realiza de forma automatica para todas las polıticas implementadas:polıtica Jerarquica, Best-Neighbor, Super-Peer y Random.

Se realizo un estudio preliminar del comportamiento de las distintas polıticasen las topologıas basicas obteniendo interesantes resultados basados en las propiasrestricciones de las redes. Un elemento interesante, emergente de los resultadosanteriores, es estudiar el comportamiento de la polıtica Jerarquica teniendo encuenta la cantidad de niveles de jerarquıa. Los resultados mostraron la relacionque existe entre la cantidad de niveles y el tiempo de expiracion de la informacion.

La polıtica Super-Peer mostro resultados muy buenos y estables, en diversosescenarios. Se estudio el comportamiento de esta polıtica variando la cantidad denodos super-peer, mostrando un comportamiento de variacion suave a medida queaumenta la cantidad de super-peers, empezando de un comportamiento practica-mente centralizado, llegando finalmente a un comportamiento random. A partirde los resultados promisorios conseguidos, se estudio su escalabilidad, realizandoejecuciones que analizan redes del orden de 10000 nodos, con un comportamientomuy estable de la polıtica. Por ultimo, se realizo un experimento para determinarel valor optimo de tiempo de refresco de la informacion en funcion de tiempo deexpiracion de los recursos. Para redes de gran tamano, esta relacion debe ser toma-da con particular cuidado, pudiendo caer en configuraciones con muy bajos valoresde informacion en los nodos, o en ciclos de refresco mas seguido de lo necesario.

Los resultados obtenidos, aun preliminares, demuestran el poder de analisisdisponible, con una versatilidad tanto en el desarrollo de topologıas como en laconfiguracion de polıticas de propagacion de informacion.

1

Abstract

The proliferation of huge computer centers with thousands of processors avai-lable, summed up with the new computing paradigms as cloud computing, makedistributed environment a maze of new perspectives. In this scenario, Grid Com-puting requires knowledge of resources for the proper administration in distributedcomputing environments. Dynamics of resource information is increasing in com-plexity, and nowadays is almost impossible to be captured using a static hierarchy.Consequently, we focused on developing new tools to attack this new challenges.Grid-Matrix is a framework with an user-friendly GUI, based on the famous gridsimulator SimGrid. It is focused on the analysis of information propagation poli-cies, including automatic generation of very varied network topologies, and manydifferent policies scenarios.

In this thesis, GridMatrix was extended with tools for the automatic genera-tion of Grid topologies and automatic generation of configuration files describingthe policies and parameters implemented in each node, in particular for the Hie-rarchical, Best-Neighbor, Super-Peer and Random policies.

A preliminary study of the behavior of the different policies in the basic topolo-gies was performed, obtaining interesting results based on the restrictions imposedby the network topologies. An interesting emerging result was the behavior of thehierarchical policy depending on the number of levels of the hierarchy. The resultsshowed that the relation of number of levels and expiration time of informationmust be specially taken into account.

The Super-Peer policy showed very good and stable results in a variety ofscenarios. Behavior of policy was studied varying the number of super-peer nodes,showing a smooth variation as number increases, starting equal to a centralizedapproach and ending with a completely random behavior.

From this promisory results, the scalablity of the policy was analysed, executingsimulation on 10000-nodes networks, again with avery stable behavior. Finally, therelation between refresh time of resources and expiration time of information wasstudied. For big scale networks, this relation must be chosen with special care,as systems may fall in configuration where the amount of available information isextremely small in the nodes; or in the other hand, very small refresh time thatmight congest the network.

Results obtained, even though preliminary, show a very powerful tool for thiskind of analysis, with versatility in the generation of network topologies and inconfigration and testing of propagation of information policies.

2

Agradecimientos

A mis directores, Esteban Mocskos, Diego Fernandez Slezak y Pablo Tur-janski por el gran esfuerzo que pusieron en llevar adelante todo este trabajo.A mi familia por tolerar las horas de estudio. A mis companeros de toda lacarrera, Lucio Santi, Daniel Koile y German Kruszewski, sin ellos no hubierallegado aca. Y especialmente a Sil, por estar siempre.

3

Capıtulo 1

Introduccion

Durante las ultimas dos decadas se han producido cambios sustanciales enla forma en que percibimos y usamos los recursos y servicios computacionales.Dos decadas atras, era normal esperar que las necesidades de computo fueransatisfechas por la infraestructura tecnologica limitada a un centro de compu-tos. Esta situacion ha cambiado, y este cambio surge, fundamentalmente,por la creciente transformacion de las computadoras y los componentes dered, generando hardware cada vez mas rapido y software mas sofisticado.Como consecuencia de estos cambios se abrio la posibilidad de utilizar recur-sos distribuidos geograficamente de forma eficiente, para responder a ciertasnecesidades en campos de aplicaciones que ası lo requieren [1].

Grid Computing aflora como un nuevo paradigma, proveyendo la infra-estructura basica para compartir recursos de forma geograficamente distri-buida. El creciente desarrollo de las tecnologıas Grid y la gran cantidad derecursos existentes a nivel mundial, despiertan renovado interes en el estudiode las polıticas de descubrimiento y monitoreo de recursos.

En este contexto, se propone el estudio del impacto de las topologıas Griden el monitoreo y descubrimiento automatico de recursos. Para ello, se extien-de la herramienta GridMatrix [2], que ataca especıficamente la problematicade los servicios de informacion. Esta herramienta permite, mediante una mo-derna interfaz grafica y scripts implementados en Python, la simulacion dediferentes polıticas de distribucion de informacion, utilizando las funcionali-dades provistas por SimGrid2 [3, 4].

Para poder evaluar polıticas de distribucion de la informacion en distintasredes, es necesario poder contar con la especificacion de las mismas, estoincluye los recursos, los links entre nodos, los routers y las caracterısticastecnicas involucradas en cada uno de estos. En ese sentido, las extensionessobre GridMatrix radican principalmente en:

1. la generacion automatica de topologıas de red.

4

CAPITULO 1. INTRODUCCION

2. la generacion automatica de esquemas de propagacion de informacioncon parametros de entrada particulares para las diferentes polıticas ytopologıas disponibles.

Ambos desarrollos fueron integrados a GridMatrix, junto con un conjunto demodificaciones ligadas a la escalabilidad de la herramienta.

1.1. Grid Computing

Grid Computing [1,5–7] es un nuevo paradigma en la computacion de al-to rendimiento que provee la infraestructura basica para compartir recursos(desde computadoras de escritorio, cluster de computadoras, supercompu-tadoras, sistemas de almacenamiento o incluso sensores, aplicaciones o ins-trumentos cientıficos de cualquier ındole) de forma transparente y geografi-camente distribuida.

En este esquema distribuido, el concepto de usuario del sistema cambiaradicalmente. A diferencia de los sistemas de computacion de alto rendimien-to, o como se denominan en ingles High-performance computing (HPC), unusuario de un Grid no es un usuario local de ningun sistema, sino que esparte de una Organizacion Virtual (VO). Una VO es un conjunto de recursosy usuarios dentro de un Grid, que tienen en comun reglamentaciones y con-diciones para disponer de los recursos [8]. Para que un usuario pueda utilizarlos recursos de un Grid, este debe pertenecer a una VO que certifica su per-tenencia mediante un certificado. Dado que los recursos son administradospor diferentes instituciones, son muy importantes las cuestiones de seguridaden cuanto a la autenticacion de usuarios, emision de certificados, etc.

En este esquema general de computacion distribuida, aparecen distintassoluciones para la implementacion de Grids. Esta tecnologıa ha incursionadoen practicamente todos los centros de computos importantes del mundo sien-do, Globus Toolkit 4 (GT4) [9,10] una de las implementaciones mas utilizadaspara crear estos entornos sobre diferentes sistemas operativos y arquitecturasde computadoras.

GT4 consiste en un conjunto basico de servicios y aplicaciones para laadministracion de diferentes caracterısticas del Grid siguiendo un diseno decapas. Estos servicios estan orientados a la administracion y uso de los re-cursos disponibles en el Grid. Los diferentes recursos son caracterizados pormedio de atributos. Estos atributos pueden ser tanto estaticos (por ejem-plo en el caso de un nodo de procesamiento: version del sistema operativo,bibliotecas soportadas, arquitectura del procesador, etc.), como dinamicos(siguiendo el mismo ejemplo: cantidad de procesadores utiles en el sistema,

5


carga de los procesadores, memoria libre, disponibilidad de ancho de bandade red, etc.).

Una de las caracterısticas mas importantes en Grid Computing, es lanecesidad de mantener informacion actualizada referente a los recursos yservicios que el Grid provee [11].

El componente responsable de obtener, distribuir, indexar y almacenar lainformacion acerca de la configuracion y estado de los servicios y recursos esel Grid Resource Information Service (GRIS).

El enfoque estandar proporciona una organizacion centralizada para elGRIS, donde las consultas de recursos son enviadas a una maquina centraldistinguida, la cual provee el servicio de indexacion. Las actualizaciones deestado de los recursos tambien son enviadas por los proveedores a dichamaquina.

Este enfoque centralizado presenta algunos inconvenientes [12] como, porejemplo, es propenso a un unico punto de falla, carece de escalabilidad yposee altos costos de comunicacion en los enlaces que conducen informacional servidor. El uso de servidores centralizados puede convertirlos en cuellosde botella o puntos de falla.

Los sistemas de informacion centralizados son usados en R-GMA [13],Hawkeye [14,15], GMD [16], y MDS-1 [17].

La nueva generacion de sistemas de informacion, como Monitoring andDiscovery System (MDS) [18,19] y Ganglia [20], se basan en una organizacionjerarquica donde la informacion de los recursos es enviada entre los diferentesnodos siguiendo una jerarquıa.

En un futuro no muy lejano tendremos que estar preparados para tra-bajar en un escenario donde los recursos compartidos en la red alcanzaranun numero tal, que todo el planeta podrıa ser considerado una organizacionvirtual global. En tal entorno, la dinamica de la informacion de recursos nopuede ser capturada con una jerarquıa estatica [21]. Esta distribucion de lainformacion sufre de diversos inconvenientes desde el punto de vista de esca-labilidad. Por ejemplo, como se muestra en la figura 1.1, el tiempo en que lainformacion se distribuye crece a medida que el tamano del sistema aumenta,pudiendo provocar que, al llegar la informacion al destino deseado, la mismasea obsoleta. Por otra parte, tambien sufre de problemas similares a los delenfoque centralizado, como el de poseer un unico punto de falla, y la bajatasa de escalabilidad para un gran numero de usuarios y proveedores [22,23].

6


AggregatorService

AggregatorService

AggregatorService

AggregatorService

Recurso Recurso Recurso Recurso Recurso

Recurso Recurso

Recurso

tiempo de vida dela información

Figura 1.1: Organizacion jerarquica de GRIS, los Aggregator Services son losencargados de recopilar la informacion de los Recursos y enviarla a su superioren la jerarquıa. A medida que se asciende en la jerarquıa, la informacioncontenida en los Aggregator Services puede haber sido obtenida desde elrecurso hace mas tiempo.

1.2. Globus Toolkit

Globus Toolkit [10] (GT) es un conjunto de componentes de softwa-re disenados para solucionar los problemas mas comunes en ambientes decomputacion distribuida. Siendo desarrollado desde 1990, se ha convertidoen una de las herramientas mas utilizadas en la implementacion de tecno-logıas Grid [24]. Actualmente Globus Toolkit es desarrollado por GlobusAlliance [10], que es un grupo de organizaciones y personas individuales.

Los componentes de GT solucionan cuestiones relativas a la seguridad,administracion y movimiento de datos, ademas del acceso, administraciony descubrimiento de recursos. Para implementar estas funcionalidades GTofrece numerosas herramientas, desde componentes basicos responsables delaccionar mas elemental, hasta complejas funcionalidades a nivel de aplicacion[24]. Cabe destacar que muchos componentes de GT pueden ser usados comobase para implementar un entorno Grid. Esto no implica que GT sea unasolucion completa para la implementacion de un Grid, sino que proporcionalas herramientas y facilidades para hacer frente a los requerimientos de estastecnologıas.

La version mas reciente de Globus Toolkit es la version 5 (GT5), para lacual se enumeran varios cambios con respecto a su antecesor. En particular,en octubre de 2009, se presento una nota con los cambios incorporados en estaversion1; en la cual se enumeran una serie de reimplementaciones y cambios

1La nota mencionada del 10/22/2009 puede encontrarse en http://globus.org/

7

http://globus.org/alliance/news.html



de diseno.Entre estos se expresa que en la practica MDS es utilizado para tareas

de descubrimiento, pero su uso para monitoreo es limitado. Para la futuraversion de este componente (llamada Crux ), se requerira un gran esfuerzo dedesarrollo ya que integrara diferentes herramientas open source de monitoreocomo Nagios [25]. Si bien GT5 es la ultima version de esta herramienta, seencuentra en pleno desarrollo y aun no posee todos los servicios implemen-tados, como por ejemplo MDS o su sucesor. Por este motivo, en lo que restadel trabajo nos basaremos en la herramienta MDS-4 incluida en GT4.

A continuacion se expondra un breve resumen de los componentes y ca-racterısticas principales de los paquetes de software que componen GlobusToolkit 4.

1.2.1. Arquitectura y Componentes

Globus Toolkit 4 es un framework Open Source que consiste en una co-leccion de componentes; muchos de ellos basados en estandares existentes,mientras que otros son el resultado del desarrollo especıfico.

Figura 1.2: Esquema de componentes de GT4 clasificados segun la categorıade funcionalidad a la que corresponden.

A modo ilustrativo, en la figura 1.2 se muestran los principales compo-nentes incluidos en este paquete. Estos componentes estan clasificados en lassiguientes categorıas:

Common runtime components: Serie de bibliotecas y aplicaciones queforman, como su nombre lo indica, la base necesaria para el resto delos componentes.

alliance/news.html bajo el tıtulo de “Important information on Globus events andplans”

8


























Security: Incluye un conjunto de componentes que arbitran cuestionesrelacionadas con la seguridad de las comunicaciones y autenticacion deusuarios.

Data management: Integra diversas herramientas que permiten la ges-tion de datos en un entorno Grid. Las mismas permiten transferir, mo-ver y borrar archivos, ademas de diversos componentes para mantenerreplicas y consistencia de archivos.

Execution management: Incluye herramientas para la gestion de la eje-cucion en un entorno Grid. Permite ejecutar remotamente trabajos yrealizar el seguimiento de los mismos.

Information services: Un conjunto de servicios encargados principal-mente de la recoleccion, almacenamiento y procesamiento de cualquierinformacion sobre el estado de los recursos y servicios en un Grid. Per-mite descubrir y monitorear los recursos, ademas de poder tomar de-terminaciones dependiendo de su estado.

El ultimo punto, Information services, es objeto de estudio en este traba-jo. Por esta razon, se detallan a continuacion sus principales componentes,como ası tambien los principios que rigen su funcionalidad.

Information services

Este componente, implementado en GT4 como MDS se ocupa de la reco-leccion, distribucion, indexacion, almacenamiento, y posterior procesamientode la informacion relacionada al estado de los diversos recursos, servicios yconfiguraciones en el Grid [26].

El objetivo de MDS es brindar una herramienta para encontrar recursosdentro de una organizacion virtual y contar con la posibilidad de monitorearsu estado en todo momento. Para cumplir este objetivo debe recopilar infor-macion de diferentes areas dentro del grid. Se denomina Aggregator Frame-work al marco de trabajo que describe el comportamiento general de serviciosorientados a la recopilacion, indexacion y procesamiento de informacion delgrid.

Dentro este marco, MDS cuenta con dos servicios, agrupados bajo el nom-bre de Aggregator Services. El primero, Index Service, posee un catalogo deinformacion sobre los recursos. Para acceder al mismo provee interfaces deconsulta (poll) o para la suscripcion (push), esta ultima se puede realizarsobre cualquier tipo de fuente de informacion de recursos. Por otro lado, elsegundo servicio de MDS, Trigger Service permite configurar acciones que

9


seran disparadas a partir de eventos (sobre condiciones acerca de la informa-cion almacenada en el catalogo).

En las distintas versiones de Globus, el conjunto de estas herramientasfueron implementadas tanto como Web Services (WS), como no-WS. En GT4se migro la mayorıa de los servicios a WS, en un intento por acrecentar lainteroperatividad de GT4. Por esta razon, se pueden encontrar referenciasen la bibliografıa a servicios orientados tanto a WS como a Pre-WS [27]. Enalgunos casos, estos ultimos existen por compatibilidad, y en otros porqueaun no existe la implementacion en WS. En este trabajo, nos concentraremosen la implementacion en GT4, donde MDS4 consta de dos servicios de altonivel, el Index service y el Trigger service, implementados como WS.

Entrando en mas detalle en los servicios descriptos:

Index service:

En la bibliografıa, a los componentes encargados de proveer la informa-cion a los ındices, se los puede encontrar con el nombre de aggregatorsource. Estos ultimos toman la informacion de un information provider,que se encarga de la interfaz con el recurso y la posterior generacion dela informacion.

Los aggregator source utilizan los mecanismos mencionados anterior-mente para proveer la informacion a los Index services. En particular,un Index service puede actuar como un aggregator source enviando in-formacion a otros Index services. Este procedimiento es de fundamentalimportancia para este trabajo y es ilustrado en la figura 1.1 de la pagina7.

Como fue mencionado en la seccion 1.1, la configuracion estandar delInformation service es la configuracion que forma una organizacion detipo jerarquica. En este caso, la conexion para los mecanismos de poll ypush, entre los diferentes Index services, sigue la estructura de un arbol.

La informacion entre los diferentes Index services es enviada cada undeterminado lapso de tiempo, que no necesariamente es igual para todoslos Index Services, lo cual trae aparejado una serie de inconvenientes.Por un lado, la presencia de informacion sobre un determinado recursono da ninguna garantıa acerca de la disponibilidad del mismo. Se debea que la autoridad de administracion puede dar de baja el recurso y lainformacion contenida en el Index Service aun no haber sido actualiza-da. Por otro lado, la informacion publicada en un Index Service se debeconsiderar como reciente, pero no como la ultima. El monitoreo de los

10


recursos no se realiza en tiempo real, sino que se actualiza cada lap-sos de tiempo fijos, determinando un posible retardo de actualizaciono incluso la perdida de informacion por un menor tiempo de refresco.El ultimo punto a considerar es que, si la informacion dentro de unIndex Service no es actualizada periodicamente, esta quedara obsoleta.Por esta razon todos los datos almacenados en un Index Service tienenun determinado tiempo de vida. Pasado este tiempo, la informaciones eliminada. Cabe destacar que este mecanismo, que permite borrarinformacion desactualizada, es de vital importancia para mantener lacoherencia en los datos almacenados.

Trigger service: Este servicio permite declarar eventos. Por un ladose define la accion a realizar y por el otro la condicion que la desencade-nara. En particular, la condicion es una expresion sobre la informacionalmacenada en el Information service. Si esta condicion se cumple, serealizara una accion definida por medio de un script.

El estudio preliminar de la propagacion de informacion fue desarrolladopor Pablo Yabo en su tesis de licenciatura [2], enfocada en el desarrollo dela aplicacion GridMatrix. Esta aplicacion permite simular el comportamien-to de diferentes polıticas de distribucion de informacion reproduciendo losmecanismos provistos por MDS.

1.3. Grid Matrix

El estudio en el campo de las arquitecturas Grid puede ser inabordableutilizando recursos reales, ya que requerirıa la puesta en marcha de un desme-surado numero de equipamiento. Por esta razon existen varios simuladores deprocesos distribuidos orientados a arquitecturas Grid. Sin embargo ningunode ellos ha sido orientado para estudiar polıticas de monitoreo y descubri-miento de recursos. GridMatrix es una aplicacion que tiene como objetivocubrir el vacıo existente en este sentido.

Para el desarrollo de GridMatrix se opto por implementar las funcionali-dades necesarias para el estudio de polıticas de monitoreo y descubrimientode recursos, sobre un motor de simulacion ya existente. En ese momento, laopcion mas adecuada fue la de utilizar SimGrid2 [4] debido a sus caracterısti-cas y ventajas. Para mas informacion al respecto, remitirse a Yabo [2] dondese describen en detalle las opciones estudiadas.

SimGrid2 es una herramienta que proporciona funcionalidades para lasimulacion de aplicaciones distribuidas en entornos heterogeneos. Facilita laprogramacion de aplicaciones en plataformas que van desde simples redes de

11


computadoras a complejas arquitecturas grid. En este ultimo punto, es dondese sustenta la decision de utilizarlo como motor para GridMatrix.

La aplicacion GridMatrix cuenta con una avanzada interfaz grafica (figura1.3) que permite la creacion de complejas topologıas de red en un entornofacil de utilizar.

Figura 1.3: Interfaz grafica de GridMatrix

El comportamiento de los nodos es programado mediante el uso de unainterfaz de scripting en Python, dando acceso a un entorno muy potentey completo de funcionalidades. Esta interfaz permite, de manera sencilla,implementar diferentes polıticas de propagacion de informacion, incluyendola capacidad de visualizar el progreso de la ejecucion.

Sin embargo, GridMatrix posee un conjunto de limitaciones en relacion alos requerimientos necesarios para el estudio de polıticas de distribucion deinformacion.

1.3.1. Limitaciones

Las limitaciones de GridMatrix se pueden categorizar de la siguiente for-ma:

12


Recursos

La principal limitacion de GridMatrix es la referida a la utilizacion derecursos. La topologıa de red se debe describir por medio de un archi-vo que se utiliza como entrada de SimGrid2, conocido como archivoplatform, en formato Extensible Markup Language (XML). Dado queGridMatrix utiliza SimGrid2 como motor de simulacion, es importanterealizar adecuadamente la generacion de este archivo. En este archivo,se requiere describir todas las posibles rutas viables entre los nodosde la red. Por lo tanto, para redes lo suficientemente grandes, esteproceso puede no escalar debido a la cantidad de rutas posibles. Lasimplementaciones de bibliotecas estandar para serializacion de archivosXML resultan limitadas, ya que mantienen gran cantidad de datos enmemoria.

Asociado a esta limitacion SimGrid2, por cuestiones de diseno, requie-re un ruteo estatico de toda la red como entrada en el archivo de red(platform). Esta decision limita su capacidad de escalar por requeriruna gran cantidad de recursos. Para resolver este problema, los creado-res de SimGrid2 desarrollaron un nuevo formato de archivos platform.Desafortunadamente, GridMatrix es incompatible con este nuevo for-mato.

Funcionalidades

Como describimos anteriormente, uno de los objetivos de GridMatrix esel estudio de las distintas polıticas de distribucion de informacion a lolargo de la red, con distintas topologıas. Estas polıticas de distribucionson configuradas a traves de un archivo XML, llamado archivo deploy.GridMatrix no provee ninguna funcionalidad para generar automatica-mente la configuracion de las polıticas (archivos deploy). En tal caso esnecesario editar manualmente un archivo indicando las caracterısticasparticulares de cada escenario a simular. Este proceso, como cualquieramanual, es propenso a errores y en redes de mayor tamano se vuelveuna solucion impracticable.

Caracterizacion de Topologıas de Red

Para poder estudiar el comportamiento de diferentes topologıas de red,es imprescindible caracterizarlas a fin de poder compararlas; como porejemplo calcular la cantidad de nodos o determinar si cumple con unaley de potencia o power-law. GridMatrix no posee ninguna forma derealizar este analisis. Tampoco es posible exportar la red generada aun formado adecuado para hacerlo.

13


Intefaz

La interfaz grafica de GridMatrix lo hace una herramienta unica en sutipo, pero a la hora de trabajar con grandes redes aparecen dificultadesinherentes a la visualizacion de los datos. Esta herramienta no proveeuna forma de reorganizar sus elementos graficos ni su reduccion entamano.

En esta tesis se propone abordar el estudio de polıticas de propagacion deinformacion en una variedad de topologıas de red. En base a las limitacionesexpuestas, se extiende la herramienta GridMatrix en los siguientes puntos:

1. Solucionar problemas de escalabilidad en GridMatrix.

2. Mejorar la interfaz grafica a fin de permitir una mejor visualizacion delas red.

3. Mejorar la compatibilidad con SimGrid2.

4. Implementar la generacion automatica de topologıas de redes.

5. Implementar la generacion automatica de esquemas de propagacion deinformacion con parametros de entrada particulares para las diferentespolıticas y topologıas disponibles.

6. Implementar la medicion de parametros de las redes generadas.

En el capıtulo 2, se expone la metodologıa utilizada en esta tesis paraincorporar las propuestas enumeradas. En el capıtulo 3 se hace foco en laimplementacion de estos puntos, mientras que en el 4 se detallan y analizanlos casos de estudio realizados para los distintos escenarios planteados. Porultimo, en los capıtulos 5 y 6 se evaluan y discuten los resultados obtenidos,proponiendo nuevas lıneas de investigacion que se abren a partir de estetrabajo.

14

Capıtulo 2

Metodologıa

Para profundizar en el estudio sobre el problema de monitoreo y descu-brimiento automatico de recursos, que inicialmente se propone en la tesisde Pablo Yabo [2], se opto por extender las funcionalidades de GridMatrixhaciendo foco en la generacion de redes de forma automatica. Existen dife-rentes tipos de generadores de redes utilizados por la comunidad cientıfica.Como primer paso se estudiaron generadores de redes evaluando que puedie-ran generar redes con caracterısticas similares a las de una red grid real. Eneste capıtulo se detalla el estudio de los distintos generadores, indicando lascaracterısticas principales de cada uno.

Finalmente, se introducen las polıticas de distribucion de informacionimplementadas en GridMatrix y cuales son los parametros a explorar en lassimulaciones.

2.1. Generacion de redes

Uno de los aspectos mas importantes en este trabajo es la generacionautomatica de topologıas de red. Para encarar este problema se examinaronsoluciones preexistentes utilizadas por la comunidad cientıfica.

BRITE [28]: De su sigla en ingles Boston University Representative In-ternet Topology Generator, es un proyecto de la Universidad de Boston quefue implementado en java y C++ a fin de favorecer la portabilidad. Poseeuna interfaz grafica para parametrizar y visualizar la generacion. Esta orien-tado a analizar diferentes estrategias para la generacion de topologıas dered de alcance global. La principal caracterıstica es que utiliza modelos decrecimiento incremental y preferencial sobre la conectividad. Usando estosprocedimientos se logra gran correlacion de las power-law en las topologıas

15

CAPITULO 2. METODOLOGIA

que genera [28,29]. Actualmente no es mantenido por sus autores.

Inet [30]: Genera topologıas similares a Internet a nivel de conectividadde Sistemas Autonomos (AS). Inicialmente asigna grados a los nodos de lared, respetando power-law, luego procede a interconectarlos [30, 31]. Estametodologıa es comunmente utilizada para representar las caracterısticas deInternet y generar una red libre de escala. Inet se encuentra implementadoen C.

Tiers [32]: Es un generador jerarquico multicapa. Puede definirse el gra-do de los nodos en funcion de la redundancia [29]. Esta orientado a imitar laestructura de niveles existente en Internet, basado en generar una jerarquıade tres niveles separadas en WANs, MANs y LANs [31]. Genera una red quees solo una jerarquıa entre nodos, en la cual no se respeta power-law. Laimplementacion se encuentra realizada en C.

GridG [33]: Es un generador de topologıas de red orientado a topologıasGrid. La mecanica de funcionamiento se caracteriza por realizar transforma-ciones a partir de una red generada inicialmente. Para generar tal red utilizaTiers que, como fue mencionado anteriormente, genera una estructura detres niveles. Con la finalidad de respetar parametros basados en power laws,agrega redundancia entre los routers de la red generada. Por ultimo proveeun mecanismo para agregar informacion adicional a la red, a nivel de routers,links y hosts. Fue implementado como una secuencia de trasformaciones detexto plano escritas en Perl.

SIMULACRUM (SIMUlated pLAtform CReation and User Modifica-tion) [34,35]: Es una herramienta construida por los desarrolladores de Sim-Grid, pero independiente de este proyecto. Recordemos que SimGrid es unsimulador de aplicaciones distribuidas en entornos heterogeneos utilizado co-mo motor de GridMatrix. Este generador permite armar redes respetandodistintas topologıas, Clique, Line, Ring, Star, Uniform, Exponential, Wax-man [36], Zegura [37] y Barabasi [38]. Su implementacion fue realizada enJAVA.

Tanto BRITE, Inet, Tiers y GridG estan orientados a generar redes queimitan, en algunos aspectos, las relaciones de conectividad de internet. Por elcontrario, Simulacrum permite el armado de distintas topologıas conocidas,incluyendo basadas en internet y topologıas basicas. Por este motivo, se de-cidio tomar Simulacrum como base para la generacion automatica de redesen GridMatrix2.

16


Sin embargo, esta herramienta presentaba algunos problemas a resolver.En primer lugar, se encuentra implementada en JAVA y el desarrollo deGridMatrix en C++/Python. En segundo lugar, esta desarrollada como he-rramienta de SimGrid2 y por lo tanto la red que genera es almacenada con elformato utilizado en los archivos platform, inadecuado para medir parametroso caracterizar redes. Mas adelante, en la seccion 3.3, se detallan las razonesque impiden la caracterizacion de parametros sobre redes en este formato y sepropone un nuevo formato para el almacenamiento de la topologıa de la redfısica. Finalmente, se opto por tomar de Simulacrum e incluir sus algoritmosde generacion dentro de GridMatrix2.

Los algoritmos incluidos son los siguientes:

Clique: Existe un link entre cualquier par de routers (figura 2.1a).

Line: Existe un solo camino que interconecta todos los routers (figura2.1b).

Ring : Los routers se encuentran interconectados por un solo ciclo (figura2.1c).

Star : Se identifica un router como central y los restantes se conectancon este (figura 2.1d).

Uniform: Se interconectan routers en funcion de una probabilidad uni-forme.

Exponential : Se crea una red donde la probabilidad de que dos nodosesten conectados sigue la ley de potencia. El numero de conexionescrece en funcion de un cierto parametro alpha (correspondiente al ex-ponente).

Waxman: Se crea una red siguiendo el modelo de Waxman [36]. Elnumero de ejes crece con respecto a un cierto parametro alpha y unparametro beta que indica la heterogeneidad de la longitud de las co-nexiones.

Zegura: Se crea una red siguiendo el modelo de Zegura [37], el cualse basa en los parametros alpha (probabilidad de conexion entre ejescortos), beta (probabilidad de conexion entre ejes largos) y r (valorentre 0 y

√2, que indica el lımite entre ejes largos y cortos).

Barabasi : Se crea una red de acuerdo al algoritmo de Barabassi-Albert(el cual respeta ley de potencia) [38].

17


(a) Clique (b) Line

(c) Ring (d) Star

Figura 2.1: Ejemplo de diferentes topologıas de red

2.2. Polıticas de monitoreo y descubrimiento

de recursos

El monitoreo y descubrimiento de recursos es fundamental en un sistemadistribuido, permitiendo el diagnostico y la deteccion de nuevas incorporacio-nes de recursos. Ambas tareas requieren la recoleccion de datos desde multi-ples fuentes de informacion distribuidas a lo largo de la red. Estas fuentes,representadas por nodos en la red, incluyen toda la informacion relacionadaal recurso.

Los diferentes nodos estan interconectados por medio de una red fısicaa traves de canales de comunicacion logicos (rutas) entre los routers. La es-tructura de comunicacion entre nodos es lo que denominamos polıtica dedistribucion de informacion. La relacion entre los canales de comunicacionimplementados por las polıticas y la red fısica subyacente puede afectar se-riamente el desempeno de la propagacion de la informacion.

Por otro lado, la comunicacion entre nodos puede ser en cualquiera de losdos sentidos; es valida tanto la solicitud como el envıo de informacion a otrosnodos. La eleccion de cual es el nodo destino, tambien depende de la polıticade distribucion de la informacion.

18


En GridMatrix se implementa un conjunto de polıticas, basadas en eltrabajo de Mastroiani [39]. En las secciones siguientes se describe cada unade ellas, comenzando por la polıtica Jerarquica, para luego continuar con laspolıticas basadas en redes Peer to peer (P2P).

2.2.1. Polıtica Jerarquica

Esta polıtica se basa en la estructuracion de una jerarquıa estatica, esta-blecida a priori, entre los nodos de la red. Cada nodo es asignado en algunnivel de la jerarquıa, conociendo quien es su padre (nivel superior) y quienessus hijos (nivel inferior). De esta forma, el intercambio de informacion serealiza entre los nodos padre e hijos, fluyendo entre niveles. En la figura 2.2se puede observar un esquema de esta polıtica. Es importante mencionar queesta organizacion entre los nodos no necesariamente debe respetar la red fısi-ca subyacente que los conecta, pudiendo dos nodos padre e hijo estar a variospasos de distancia o hops en la red fısica.

11.1

1.2

1.2.1

1.2.2

1.2.3

1.2.3.1

1.1.1

1.1.2

Figura 2.2: Esquema de funcionamiento de la polıtica Jerarquica sobre unared. Las flechas indican la relacion padre/hijo.

Si bien esta polıtica posee un muy buen desempeno para una amplia ga-ma de casos, se debe tener en cuenta algunas desventajas. En primer lugar,la baja tolerancia a fallas debido a que si un nodo sale de servicio, toda larama formada por este y los que se encuentran en niveles inferiores pierdenel acceso a la informacion del resto del grid. Por otro lado, la configuracionde la jerarquıa debe realizarse de forma manual y requiere de un manteni-miento indispensable para poder sobrellevar los cambios en la red, tanto de

19


interconexion, como de prestacion de servicio.La polıtica jerarquica es la que actualmente utiliza MDS para la propa-

gacion de informacion [18].

2.2.2. Algoritmos Peer to Peer (P2P)

Las siguientes polıticas se engloban como algoritmos P2P. Las redes P2Pson redes logicas entre nodos, como se ilustra en la figura 2.3, que se basanen el intercambio de informacion entre nodos vecinos que no necesariamentese encuentran cercanos fısicamente. En una red P2P, cada nodo conoce a unconjunto de nodos vecinos con los cuales puede interactuar. Las polıticas quese mencionan a continuacion utilizan este esquema de operacion, donde losvecinos asignados pueden ser cualquier otro nodo de la red.

Figura 2.3: Esquema de una red P2P. Las lıneas azules representan la redlogica P2P y las lıneas de color gris identifican las conexiones fısicas entre losnodos y routers.

Polıtica Random

Esta polıtica carece de todo tipo de estructura, cada nodo elige un ve-cino al azar al cual enviar o solicitar informacion. Una de las ventajas masimportante es que no se requiere almacenar informacion acerca de los nodosvecinos con los que se comunica ya que se escogen siguiendo una distribucionuniforme [40]. En la figura 2.4 se ilustra este comportamiento. Por lo general,este algoritmo no se comporta adecuadamente para grandes redes [40].

La enorme ventaja es la simplicidad del algoritmo, muy facil de imple-mentar, que requiere poca capacidad de computo y almacenamiento. Sinembargo, para realizar consultas es necesario tener conocimiento previo delos nodos a consultar, lo cual constituye una tarea muy compleja. Por este

20


Figura 2.4: Esquema de funcionamiento de la polıtica Random sobre una red.Las flechas indican algunas de las interacciones posibles entre vecinos.

motivo, normalmente el vecindario utilizado para la seleccion random no in-cluye todos los nodos sino solo un subconjunto. En redes muy grandes convecindarios extensos, la eleccion al azar de nodos puede ser muy deficiente,llevando a un aumento en la latencia de los mensajes, o incluso creando unacongestion innecesaria en la red [40].

Polıtica Best-Neighbor

Esta polıtica intenta resolver el problema fundamental de la polıtica Ran-dom de vecindarios extensos con nodos muy lejanos. Para resolver este in-conveniente, se analiza la informacion de los nodos a los que se consulta, yse asigna un puntaje estableciendo una prioridad a los mejores nodos.

En el comienzo, este metodo opera igual que random, eligiendo al azarlos nodos a los cuales consultar o enviar informacion. A medida que reco-lecta informacion, la eleccion sobre con cual nodo comunicarse deja de sercompletamente al azar. En base a la calidad de informacion recopilada decada nodo, aumenta o disminuye la probabilidad de seleccionar a un vecinodeterminado.

A diferencia de la polıtica random, los nodos requieren almacenar infor-macion acerca de sus vecinos. Cuanta mas informacion posea de los nodoscon los que se comunica, mejor sera la eleccion del vecino y la calidad de losdatos que logre obtener en sus proximas consultas. En la figura 2.5 se ilus-tra esta idea. En nuestra implementacion, el algoritmo comienza eligiendoaleatoriamente el nodo al cual consultar. Luego, la probabilidad de elegir un

21


vecino cualquiera se reduce proporcionalmente a la cantidad de informaciondisponible del resto de los vecinos [40]. Aun cuando un nodo tenga infor-macion total de la red, se mantiene una pequena probabilidad de elegir unnodo vecino de forma aleatoria, manteniendo un grado de adaptabilidad alos cambios producidos en el sistema.

Figura 2.5: Esquema de funcionamiento de la polıtica Best-Neighbor sobreuna red. Las flechas indican algunas de las interacciones posibles entre losvecinos de cada nodo. El tamano de la flecha representa la calidad de lainformacion brindada por el vecino.

Si bien esta polıtica tiene las mismas ventajas y desventajas que la polıticaRandom, se diferencia de esta ultima en que, con escenarios heterogeneos,se comporta mejor. Esto se debe a la eleccion no aleatoria de los nodos,que permite librarse de elegir nodos pobres en informacion. Por otro lado,en redes grandes, esta ventaja sobre random puede notarse a largo plazo,cuando la cantidad de informacion recopilada sobre la red es suficiente.

Polıtica Super-Peer

Una red P2P pura utiliza parte del ancho de banda en funciones quepodrıan ser realizadas por una cache local, ahorrando trafico de red. Es poresto que surgieron, por ejemplo, las redes Super-Peer como punto intermedioentre sistemas totalmente distribuidos y servicios basados en cache [23]. Estasredes requieren identificar a un conjunto de nodos como super-peers, entre loscuales se dispondra la interaccion usando una polıtica P2P pura. El resto delos nodos actuara de forma diferente; como clientes, ya que tendran asignado

22


un Super-Peer al cual realizarle consultas, es decir una distribucion jerarquicade un nivel. En este esquema, cada super-peer forma un cluster con susclientes. Una observacion interesante, es notar que una red P2P pura esigual a una red Super-Peer, donde el tamano de todos los clusters de clienteses igual a uno [41]. En la implementacion de GridMatrix, los super-peersdistribuyen la informacion entre sı utilizando la polıtica Random.

Figura 2.6: Polıtica Super-Peer sobre una red. En el grafico se identificanlos super-peers con un ıcono diferente con la sigla SP. Las areas pintadasengloban los nodos asignados al unico super-peer dentro del area, las flechasindican las interacciones, ya sea entre super-peers o entre super-peers y nodos.

Esta polıtica busca tomar las ventajas, tanto de la polıtica jerarquica co-mo de la polıtica random. En primer lugar, la polıtica jerarquica requiereconstruir una jerarquıa entre los nodos de la red, tomando a un nodo distin-guido como root. Este ultimo es el cuello de botella para la red, ademas de serun grave punto de falla. En la polıtica Super-Peer no existe un solo root, sinoque cada super-peer es un root de una pequena jerarquıa de un solo nivel.Esto permite que las jerarquıas sean mantenibles y no exista un solo puntode falla para todo el grid. En segundo lugar, la polıtica random no se com-porta bien para redes muy grandes, una mala eleccion del vecino con el cualcomunicarse generara congestion en la red, obteniendo ademas informacionpobre. Por otro lado, se requiere tener conocimiento de toda la red, que resul-ta impracticable para redes grandes. En la polıtica Super-Peers se cuenta conpocos nodos, en relacion con el total de la red, que son super-peers. Por lotanto se puede tener entre estos buenos canales de comunicacion ademas de

23


tener conocimiento de todos. De esta forma, se obtienen las mejores ventajasde la polıtica random para la distribucion de la informacion.

2.2.3. Implementacion de polıticas en MDS

Teniendo en cuenta el funcionamiento de MDS en GT4 detallado en laintroduccion, en esta seccion se busca explicar la implementacion general delas polıticas de distribucion de informacion en MDS.

Los servicios asociados a MDS, como se explico en detalle en la seccion1.2.1, pueden solicitar informacion acerca de los recursos desde cualquiernodo de la red que disponga de este servicio. En la implementacion estandarde MDS se construye, de manera estatica, un esquema jerarquico entre losnodos. Las consultas se realizan respetando esta jerarquıa, es decir que losnodos pueden recibir informacion de su superior en la jerarquıa y envıa estainformacion a sus hijos en la jerarquıa.

En el esquema propuesto para utilizar polıticas P2P de distribucion deinformacion, se busca que todos los nodos puedan hacer o recibir consultas decualquier nodo. Dado que los servicios de MDS utilizan las tecnicas de Push(suscripcion) y Poll (consulta) para operar la informacion almacenada en susındices, es muy simple implementar cualquier otro esquema que presuma alos nodos como pares que distribuyen informacion.

La informacion recibida luego de una consulta, contiene datos acerca deltiempo de expiracion, pasado el cual esta informacion deja de ser valida. Estees el mecanismo por el cual se limpian los registros de informacion obsoleta.Utilizando este dato acerca del tiempo de expiracion, junto con el tiempo deretardo en recibir la informacion desde un determinado nodo, se puede darcuenta de la calidad de la informacion proporcionada por un determinadovecino en la red P2P.

2.2.4. Parametros para las polıticas de distribucion deinformacion

Las polıticas estudiadas en el presente trabajo requieren de un conjuntode parametros de configuracion, tanto compartidos por todas las polıticascomo exclusivos de cada una en particular.

Cada nodo de la red tendra informacion propia con un cierto tiempode expiracion. Esta informacion es transferida a otro nodo, de acuerdo a lapolıtica establecida, indicando su expiration time y resource count, siendoel primero el tiempo de vida que tiene la informacion de los recursos, y elsegundo la cantidad de recursos a la que hace referencia la informacion de un

24


nodo. Este pasaje de informacion se realiza en intervalos regulares de tiempodefinidos por los parametros push y poll que indican cada cuanto tiempo serealizara cada una de las acciones.

2.2.5. Construccion de los mensajes de recursos

Una decision importante acerca de la implementacion de las polıticas es eldiseno de los mensajes entre los nodos. Los mensajes contienen un valor queindica el tiempo de vida, mencionado como expiration time de los recursos.El tamano de cada mensaje consta de dos partes, la primera es de tamanofijo representando el encabezado del mensaje. La segunda parte es de tamanovariable, proporcional a la cantidad de recursos que se envıa (constante paracada recurso).

2.3. Metricas de la calidad de la informacion

Para poder dar cuenta del rendimiento de las polıticas de distribucion deinformacion se debe poder medir la calidad y cantidad de la informacion pro-porcionada por cada una. Esta metrica debe estar enfocada a cuantificar lainformacion, tanto de forma global en toda la red, como de forma particularen un solo nodo en la red. Para realizar esta tarea se plantean principalmentedos ındices. Estos sirven para comparar las diferentes polıticas. A continua-cion se describe cada uno de ellos.

Local Information Rate (LIR): Este coeficiente esta comprendido entre0 y 1. Captura la cantidad de informacion que un nodo particular tienede toda la red completa en un solo momento, ponderando el tiempode expiracion de esta informacion. El valor 1, significarıa que el nodoconoce cada fragmento de informacion sobre la red entera, y esta es tannueva como pueda serlo. La definicion de LIR para el nodo k es:

LIRk =

∑Nh=1

(expirationh−ageh)expirationh

· resourceCounthtotalResourceCount

(2.1)

Donde N es el numero de nodos en todo el sistema, expirationh es eltiempo de expiracion de los recursos del nodo h en el nodo k, ageh es eltiempo desde que la informacion fue obtenida por ese nodo, resourceCounthes la cantidad de recursos en el nodo h y totalResourceCount es el totalde recursos en toda la red. La expresion expirationh − ageh es similaral parametro conocido como time-to-live en el protocolo IP. Es impor-tante aclarar que ageh puede valer como maximo expirationh.

25


Global Information Rate (GIR): Este coeficiente tambien es un valorentre 0 y 1. Captura la cantidad de informacion que toda la red conocesobre sı misma. Es calculado como el promedio de los valores LIR detodos los nodos.

Global Information Variability (GIV): Este coeficiente es el desvıo estandardel valor GIR. Mide la variabilidad sobre GIR.

El calculo de estos ındices fue integrado a GridMatrix. Como resultado deuna simulacion se permite generar estos ındices, tanto de forma global, comoindicando particularmente los nodos sobre los cuales se desean generaran lasmetricas.

26

Capıtulo 3

Desarrollo de GridMatrix 2

El objetivo principal del presente trabajo consiste en estudiar el com-portamiento de las polıticas de distribucion de informacion sobre diferentestopologıas de red. Para abordar este problema, se extendio la herramienta condos caracterısticas de manera independiente: por un lado, (1) la generacionautomatica de topologıas de red, y por el otro, (2) la generacion de esquemasde propagacion de informacion con parametros de entrada particulares paralas diferentes polıticas disponibles.

Adicionalmente, mediante el uso de las herramientas desarrolladas es po-sible caracterizar los parametros de redes existentes, posibilitando la genera-cion de escenarios sinteticos con caracterısticas similares a redes reales.

En primer lugar se abordara la descripcion del estado actual de GridMa-trix.

3.1. GridMatrix

Como se menciono en la introduccion, GridMatrix es una aplicacion desa-rrollada para el estudio de las polıticas de propagacion de informacion enarquitecturas grid. Para el desarrollo de GridMatrix se utilizo SimGrid2 co-mo motor de simulacion, el cual posee diferentes interfaces de alto nivel. Detodas ellas, GridMatrix utiliza MSG (Simple programming environment).

MSG fue originalmente desarrollada para el estudio de algoritmos descheduling, que luego, gracias a posteriores actualizaciones, se convirtio enuna de las API mas utilizadas de SimGrid2. Esta API permite la creacionde aplicaciones distribuidas, a traves de un prototipado de funciones que seejecutan como procesos en los diferentes nodos de una red.

Una aplicacion consiste en procesos que pueden ser creados, suspendidos oabortados dinamicamente. Estos procesos pueden ser sincronizados mediante

27

CAPITULO 3. DESARROLLO DE GRIDMATRIX 2

el intercambio de mensajes. Para este intercambio de mensajes entre procesos,SimGrid2 tiene en cuenta una estructura de red y por lo tanto los mensajesson sincronizados en base a los retardos de los diferentes links dentro de lared.

Para ejecutar una simulacion en SimGrid2 se requiere de dos archivosde configuracion XML. El primero de ellos representa la red (platform file),conteniendo una descripcion de la distribucion e interconexion de los dife-rentes equipos, en terminos de nodos y links. El segundo archivo describeque procesos seran ejecutados en cada nodo (deploy file).

Una vez que ambos archivos XML son definidos, se deben implementarlos programas que correran en cada nodo. Estos programas son registradosen SimGrid2 como funciones. En el archivo deploy file se indicara a cadanodo que funcion registrada sera la que ejecute, desencadenando un procesoasociado a dicha funcion. La registracion de funciones en SimGrid2 es unpunto clave a tener en cuenta. En vistas a la implementacion de GridMatrix,esta cuestion sera explicada en detalle mas adelante.

Una vez configurados estos archivos se puede proceder a la ejecucion de lasimulacion. En la figura 3.1 se ilustra el esquema de interaccion entre archi-vos en GridMatrix. Notar que el platform file es generado automaticamentepor la aplicacion GridMatrix a partir de un archivo de descripcion de la red(.net). Este ultimo posee la descripcion de toda la red junto con caracterısti-cas adicionales que el platform file no posee, por ejemplo la posicion de loselementos dentro de la interfaz grafica.

Figura 3.1: Esquema de interaccion entre archivos en GridMatrix

GridMatrix interactua con SimGrid2 de forma de proveer una interfaz pa-ra asistir en la configuracion de la red. Como se menciono en la introduccion,el comportamiento de los nodos es programado mediante el uso de scriptsen Python. Este detalle es fundamental, ya que el uso de Python abre ungran abanico de posibilidades. Ademas de la sencillez en el uso y la facilidad

28


para la modificacion del comportamiento programado. Es posible construiruna polıtica o realizar un cambio a una polıtica existente en poco tiempo.Incluso, calcular parametros en la simulacion sin tener que construir ninguntipo de codigo adicional relevante.

Para poder correr simulaciones utilizando codigo Python, fue desarrolla-do un conjunto de bindings que hacen posible el intercambio de datos entrela interfaz grafica en C++ y el codigo Python que implementa las polıticas.Desde un punto de vista practico, en el codigo Python se incluye una bi-blioteca que provee la forma de acceder a las funcionalidades de la interfazgrafica.

SimGrid2 necesita tener registradas las funciones que ejecutara en ca-da nodo. Las mismas estan escritas en Python, y es un requerimiento queSimGrid2 ejecute este codigo. Pero esto ultimo no es posible porque pararegistrar una funcion en SimGrid2, esta debe estar programada en C. Parasolucionar dicho problema, se opto por generar una unica funcion en codigoC, encargada de ejecutar una funcion en Python distinguida. Con este meca-nismo, SimGrid2 ejecuta un solo proceso correspondiente a la funcion config,encargada de ejecutar en todos los nodos las tareas configuradas desde el ar-chivo deploy. En el archivo deploy se describe un solo proceso que ejecuta lafuncion config. Los parametros pasados a esta funcion son los que conformanla configuracion para cada uno de los nodos.

Otro punto importante a mencionar corresponde a una decision de disenoque sera modificada en la segunda version de GridMatrix. Cuando se eje-cuta una simulacion, como primera fase de la misma, es generado de formaautomatica el archivo platform. El archivo se construye temporalmente parala actual simulacion. El perıodo de tiempo invertido en la costosa tarea degenerar este archivo es inutil para posteriores simulaciones, ya que no puedeser almacenado ni reutilizado. Para redes del orden de 500 nodos, esta tareapuede llevar un tiempo considerable (del orden de minutos en las pruebasrealizadas).

3.2. GridMatrix2

Como fue explicado en la introduccion, principalmente se busca imple-mentar la generacion automatica de topologıas de red y la configuracionautomatica de escenarios de simulacion. Para estas dos tareas fue necesa-rio implementar tres modulos. El primero, encargado de la generacion deredes, construyendo a partir de una determinada configuracion un archivode descripcion de red (.net). El segundo, el generador de archivos platform,encargado de transformar el archivo de descripcion de red (.net) a un archi-

29


vo platform, necesario como entrada de SimGrid2. En secciones posterioresse describe este proceso y la relacion entre ambos archivos. El tercer y ulti-mo modulo se encarga de generar archivos deploy, los cuales describen laconfiguracion de una simulacion. Esta tarea no resulta para nada trivial, yaque requiere un extenso conjunto de entradas para cada una de las polıticasde distribucion de informacion. En la seccion 3.4 se explica en detalle estafuncionalidad.

En la figura 3.2 se ilustra la interaccion entre los archivos y las nuevasprestaciones de GridMatrix2. Es especialmente interesante la comparacioncon la figura 3.1 que muestra el funcionamiento de la version anterior deGridMatrix.

archivoplatform (.xml)

archivo dedeploy (.xml)

código pythonde las

políticas (.py)

GridMatrix2

SimGrid2Intérprete

Python

archivo dedescripciónde red (.net)

Generador de redes

Generador dearchivos Platform

Generador dearchivos deploy

Figura 3.2: Esquema de interaccion entre archivos en GridMatrix2. En verdese muestran las nuevas prestaciones implementadas.

3.3. Generacion de redes

Previo a abordar el problema de la generacion de redes, se analizaranlas cuestiones referentes al almacenamiento de estas por parte de SimGrid2.El proceso de generacion de redes terminara construyendo un archivo dedescripcion de red (.net).

30


Como fue mencionado con anterioridad, este archivo posee un formatodiferente al utilizado por SimGrid2 (archivo platform). Por esta razon se rea-liza un proceso posterior correspondiente a la generacion del archivo platform.Para comprender los fundamentos de esta transformacion y la inherente ne-cesidad de su existencia, debemos interiorizarnos en como se almacena lainformacion en los archivos platform.

SimGrid2 almacena tres elementos en sus archivos de descripcion de red.

Nodos: Elementos de computo de la red.

Links: Conexiones entre elementos de la red, sean nodos o routers.

Rutas: Camino de Links entre dos Nodos. Estan conformados por dosnodos (fuente y destino), y una lista de Links intermedios.

Las rutas poseen solo informacion acerca de los links que las conforman.No tienen ninguna informacion acerca de los routers que conectan estos links.Un ejemplo de este concepto se ilustra en la figura 3.3.

A

B

C

1 2

3

4

56

7

a) Representación de la red

A B CNodos:

A B1 2 3

A C1 5 6 7

BBCC

AC

BA

3 1

3 2 5 6 7

7 6 5 1

7 6 4 3

Rutas:

1 2 3 4 5 6 7Links:

b) Información almacenada

4 5

Figura 3.3: Ejemplo de la informacion almacenada en un archivo platform deSimGrid2, en terminos de nodos, links y rutas.

En base a esta representacion, se puede observar que la topologıa alma-cenada no es la topologıa real de la red, sino que es un posible conjuntode rutas entre todos los nodos. Si se parte de este conjunto de rutas solosera posible reconstruir una fraccion de la red original, ya que si ningunaruta pasa por un determinado link, este link no sera almacenado. Por otrolado, las rutas se construyen a partir de los links, no dando cuenta de losrouters que interconectan estos links. Puede observarse que a partir de estarepresentacion se puede reconstruir, en terminos de grafos, solo una fracciondel grafo de lıneas que se induce de la red original. Siguiendo el resultadoclasico de teorıa de grafos, no siempre se puede reconstruir el grafo original a

31


partir de un grafo de lıneas, por ende tampoco la red original. Esto es debidoexclusivamente a que se almacena las rutas en terminos de aristas en vez dehacerlo en terminos de vertices, es decir, en funcion de links en vez de routersrespectivamente.

Dado que Simgrid2, no guarda informacion total acerca de la red fısicasubyacente en el archivo platform, se decidio utilizar otro formato de archivopara el almacenamiento de la misma. En este contexto surge la necesidad decontar con un archivo de descripcion de red propio de GridMatrix (archivode extension .net), que guarda la descripcion de la red fısica. A partir deeste archivo es posible generar de manera automatica el archivo platform(necesario para la ejecucion de una simulacion en Simgrid2).

El archivo de descripcion de red (.net) almacena nodos, routers y cone-xiones entre ellos. En terminos de grafos, los nodos y routers corresponden avertices, y las conexiones corresponden a aristas entre vertices. En la figura3.4 se ilustra un ejemplo de la forma en que es almacenada esta informacionen GridMatrix2.

I

II III

VI

I II III VI

B IA II

C VI

I III IIIII IIIIII VI

A

B

C

a) Representación de la red

A B CNodos:

Ejes:

Routers:

b) Información almacenada

Figura 3.4: Ejemplo de la informacion almacenada en un archivo de GridMa-trix2 en terminos de nodos, routers y conexiones entre ellos.

En la seccion 3.3.4 se explican los detalles de diseno relacionados con latraduccion del archivo .net al archivo platform.

A continuacion se detallan los aspectos mas relevantes de la generacionde redes.

3.3.1. Interfaz grafica para la generacion de redes

A fin de integrar la funcionalidad de generacion automatica de redes enGridMatrix2, se diseno una interfaz grafica que se ilustra en la figura 3.5.

Las opciones disponibles pueden ser clasificadas en tres grupos. En pri-mer lugar (a) las opciones referentes a las caracterısticas de la topologıa de

32


Figura 3.5: Interfaz Grafica del Generador de Redes de GridMatrix2

red (Network Options). En segundo lugar (b) la informacion referente a lascaracterısticas de los elementos propios de la red (SimGrid Options). Porultimo, (c) opciones de caracter general.

(a) Dentro de las opciones de red, se debe indicar un nombre, que sera tantoel nombre de la red, como el nombre del archivo a generar. A continuacionse debe seleccionar el tipo de topologıa de la red.

Una vez configurada la topologıa y el nombre de la red, se debera indicarel tamano de la misma. Este ultimo punto es medido en terminos decantidad de nodos y routers. Adicionalmente, es posible generar una seriede redes variando el tamano automaticamente. Para esto, se puede optarpor la opcion more. En este caso se debera indicar los valores lımite y elintervalo, tanto para routers como para nodos.

Finalmente, si para generar alguna topologıa es necesario ingresar algunparametro especıfico, se provee la lista de ellos con la posibilidad deeditarlos desde la interfaz. Por ejemplo, en el caso de la topologıa Expo-nencial, posee un parametro propio: el exponente de la red.

(b) Dentro del bloque de opciones referentes a SimGrid, se puede observartres grupos. El primero permite indicar los nombres que tendran losnodos, indicando para esto un prefijo y un sufijo. Los nombres de losnodos se forman a partir de estos valores y numeros correlativos. El

33


segundo grupo configura las caracterısticas de los elementos de la red,tanto links como nodos. Proporcionando valores uniformes para anchode banda, latencia y capacidad de computo. La capacidad de computo(power) se mantiene por cuestiones de compatibilidad, ya que solo esutilizada para construir el archivo platform para SimGrid2. Por ultimo,se encuentra la opcion de ruteo. Como fue explicado con anterioridad, elruteo en SimGrid2 es estatico. A partir de esto, se decidio generar dosclases de ruteos: el primero generando solo los caminos mınimos entretodos los nodos; el segundo, listando todos los caminos posibles entre losnodos.

(c) Dentro de las opciones de caracter general, en el extremo inferior de lapantalla, se cuenta con cuatro items que permiten indicar el formato enque se desea generar la red. Las opciones posibles son, GridMatrix, Sim-Grid, Igraph y Metis. Las primeras dos opciones corresponden a archivosen formato XML, utilizados como entrada para GridMatrix2 (.net) y co-mo archivo platform para SimGrid2 respectivamente. Las dos opcionesrestantes corresponden a archivos en texto plano que pueden ser utiliza-dos como entradas para Igraph [42] y Metis [43]. Ambos formatos puedenser utlizados para exportar las redes generadas y permitir utilizarlas enotros programas, por ejemplo, con el fin de caracterizarlas.

Ademas, se puede apreciar un campo de texto. En dicho campo es obliga-torio ingresar el directorio donde se guardaran las redes generadas. A suderecha se presenta la opcion detailed name, que permite al momento deguardar el resultado de la generacion, adicionar en el nombre del archivolos parametros de cantidad de routers y cantidad de nodos con los quecuenta la red generada.

En la siguiente seccion se detalla todo lo referente a la generacion de lasdistintas topologıas de red.

3.3.2. Topologıas de red

En terminos generales, la polıtica para la generacion se basa en construiruna red entre los routers de forma adecuada, respetando la topologıa y losparametros especificados. Una vez construida dicha red, se procede a agregarlos nodos a la misma.

La adicion de nodos a la red se puede realizar ordenadamente o de formaaleatoria. En el primer caso, se ordenan todos los routers y se agrega a cadauno, en orden, todos los nodos de la red. De esta manera pueden darse tressituaciones: a) si la cantidad de routers es menor que la cantidad de nodos,

34


entonces habra routers que tengan mas nodos que otros; b) si la cantidad derouters es mayor que la cantidad de nodos, existiran routers que no tenganningun nodo asignado; y c) si la cantidad de routers es la misma que la denodos, cada router tendra un solo nodo asociado.

La otra forma en la que pueden ser agregados nodos a una red, es deforma aleatoria. En este caso, por cada nodo se selecciona uniformemente unrouter a cual asociarlo.

Las topologıas soportadas en esta implementacion son Clique, Line, Ring,Star, Uniform, Exponential, Waxman, Zegura y Barabasi. En el capıtulo ante-rior fueron descriptas las caracterısticas de cada una de ellas. A continuacionresta algunos detalles referentes al desarrollo.

Para las topologıas basicas, Clique, Line, Ring y Star se opto por, unavez generadas, los nodos sean agregados de forma ordenada. Esta decisionse debe a que este tipo de topologıas se utilizan de forma teorica y se deseapoder conocer exactamente cual es el resultado de la generacion de la red.Para las restantes topologıas implementadas, la opcion fue que los nodossean agregados de forma aleatoria a la red. Adicionalmente se provee unmecanismo para alterar las redes basicas, asignando un porcentaje de linksque seran agregados o borrados.

Por otro lado, se busca que la red generada sea conexa, es decir queexista un camino entre todo par de nodos de la red. Los algoritmos Uniform,Exponential, Waxman, Zegura y Barabasi no garantizan este punto. Por estarazon se decidio iterar una cantidad finita de veces hasta encontrar una redconexa; solucion que se comparte con el generador de redes Simulacrum. Anivel de interfaz, en el caso de no encontrar una red adecuada, se le indicaal usuario que se itero una cantidad determinada de veces y que aun ası nose pudo encontrar una red satisfactoria. Ademas, en el mismo mensaje, se leindica que los parametros para la generacion no son seguros.

La generacion de la red se podrıa dar por terminada, si no fuera porque lamisma debe ser presentada en una interfaz grafica. Para analizar este puntose invita a leer la siguiente seccion.

3.3.3. Presentacion en pantalla

Con una red generada de la forma descripta anteriormente, no tenemoslos valores de posicion de los nodos y routers. Si bien es un punto que podrıacaracterizarse como menor, no resulta trivial su solucion. Para esto fue nece-sario utilizar bibliotecas adicionales que proveen funcionalidades para graficargrafos

Existen varias opciones para operar con grafos, ya sea utilizando Oc-tave [44], Matlab [45] o R-project [46]. En particular durante la etapa de

35


investigacion previa al desarrollo, fue utilizada la biblioteca Igraph [42] des-de R-project para cuantificar y graficar redes. En base a esta experiencia ycontando con que Igraph se encuentra desarrollado en C, no fue complejoutilizarla para la tarea en cuestion. De todas formas se debio portar la red aun formato en terminos de grafos y luego generar los valores de posicion enla pantalla.

Esta utilidad puede ser usada en la aplicacion desde el menu view�updatelayout.

Una vez generada la red en terminos de nodos y routers, y quizas tam-bien redibujada para su mejor visualizacion, se procede a la transformacionde formato, de manera que pueda ser utilizado por SimGrid2. El siguienteapartado explica detalles al respecto.

3.3.4. Traduccion a SimGrid2 (platform file)

Como fue mencionado anteriormente, SimGrid2 requiere la descripcionde la red de forma particular. La construccion del archivo platform (.xml)comienza listando los nodos que seran parte de la red. Luego se listan loslinks y por ultimo las rutas. Este orden es estricto, ya que no se puedenregistrar links luego de registrar rutas.

Las rutas son caminos entre los dos nodos, pero descriptos por las aristaso conexiones por las que pasa (figura 3.3). La restriccion de crear estas rutasimplica la necesidad de plantear un ruteo estatico, necesario para operar conSimGrid2. En esta tesis se implementaron dos tipos de ruteos, el primerodonde se listan todas las rutas posibles entre los nodos (All Paths), y el se-gundo en que se enumeran los mejores caminos para llegar de un nodo a otro(Hops Best Path).

Otro aspecto importante a considerar se refiere a los links. En el formatosoportado por GridMatrix2 solo se cuenta con routers, por lo tanto estamosobligados a guardar la informacion de las caracterısticas de los links comorouters. Esta cuestion se resolvio tomando las siguientes decisiones:

El nombre de un link estara compuesto por los nombres de los routersque conecte. En el caso que el link conecte un nodo a un router, estetendra los dos nombres, tanto el del router como el del nodo.

La latencia se considero como la mayor entre ambos routers.

El ancho de banda, se considero como el menor entre los dos routers.

36


Cabe destacar que una vez generada una red de forma automatica, estapuede ser modificada por medio de la interfaz. La modificacion puede alterarla red, cambiando las caracterısticas de los nodos o routers, o tambien modi-ficando la interconexion entre los mismos. Cualquiera sea el caso, se requiereregenerar el archivo platform. Para esto se diseno la interfaz de la figura 3.6que permite regenerar dicho archivo, incluso, es posible regenerar los valoresde los routers y nodos.

Figura 3.6: Interfaz Grafica del Generador de Platform

Una vez finalizada esta cuestion se debe atacar la problematica de ge-nerar parametros adecuados para las polıticas mencionadas en el capitulo2.2. A este procedimiento lo denominaremos configuracion de simulaciones ogeneracion de deploy file.

3.4. Configuracion de simulaciones

El segundo archivo requerido para SimGrid2 es el archivo deploy cuyafuncion principal es la de definir los procesos que seran ejecutados en cadanodo, los resultados que deberan ser generados y el tiempo total de ejecucion.

3.4.1. Interfaz grafica de generacion de Deploy

A fin de integrar la funcionalidad de generacion automatica de archivosde deploy en GridMatrix2, se desarrollo la interfaz grafica que puede verseen la figura 3.7.

En el grafico se observan varias pantallas, las cuales se encuentran in-tegradas en la pantalla general de generacion de archivos de deploy. Cadauna de estas se corresponde con un conjunto de opciones relacionadas a laspolıticas implementadas de distribucion de informacion. Seleccionando cual-quiera de las cuatro opciones posibles en el extremo inferior de cada una de

37


(a) General (b) Hierarchical

(c) Super-Peer (d) Best Neighbor

Figura 3.7: Interfaz Grafica del Generador de Deploy. Se omite la pantalladestinada a la polıtica random dado que la misma es equivalente a la que semuestra en la polıtica best-neighbor

las pantallas (Hierarchical, Super Peer, Best Neighbor y Random), se definefinalmente cuales seran los archivos a generar. En el cuadro de texto “StorePath” se debe indicar, de manera obligatoria, cual sera el directorio dondese almacenaran los resultados.

En la primer pantalla, denominada General (figura 3.7a), se encuentran

38


los parametros generales para todas las polıticas. Se debe completar el tiempode duracion de la corrida y el nombre del nodo que sera asignado para ejecutarla configuracion inicial. Cabe recordar, tal como se detallara en la primerseccion del presente capıtulo, que en GridMatrix2 existe un solo proceso quese encarga de configurar la polıtica de distribucion de informacion en todoslos nodos. Ademas se deben completar dos parametros: resource count yexpiration time. Ambos son intervalos a partir de los cuales se determinanlos valores, de manera uniforme, del parametro a utilizar en la polıtica depropagacion. Para el caso de resource count, solo se aplica a un porcentajede nodos, determinado mediante el parametro rich nodes percentage. El restode los nodos seran configurados con la mınima cantidad de recursos posible.

Cabe destacar que tanto el parametro resource count como expirationtime, son definidos de forma independiente y por unica vez. Esto permitegenerar un conjunto de instancias de archivos de deploy con exactamente losmismos valores para cada nodo, siempre y cuando no sean regenerados dichosvalores.

El resto de las pantallas permiten seleccionar parametros especıficos decada una de las polıticas. Si bien hay parametros que figuran simultaneamenteen todas, pueden ser configurados de forma diferente. Un ejemplo de esto esel prefijo (name prefix ) y sufijo del nombre de salida de los archivo (namesufix ).

Las polıticas Jerarquica y Super-Peer son las que requieren especial aten-cion, ya que necesitan informacion adicional ligada a la topologıa de red.

Para la polıtica Jerarquica se requiere crear una jerarquıa entre los nodos.Este trabajo no es para nada trivial y sera explicado en detalle mas adelante.Dentro de la pantalla de la figura 3.7b puede visualizarse un campo queindica la manera en que sera creada la jerarquıa y cual sera el nodo utilizadocomo raız de la misma. La interfaz permite solo dos opciones para crearla jerarquıa: a) libre (es el caso de Dijkstra) o limitada (el caso de strict).En el caso que sea limitada, se deben completar dos parametros: altura yconectividad lımite. La altura se refiere a la cantidad de niveles totales quetendra el arbol de la jerarquıa. A modo de ejemplo, si el nodo mas lejano seencuentra a 5 niveles del nodo raız, y el lımite seleccionado es 4, entoncestodos los nodos pertenecientes al nivel 5 no seran configurados en la jerarquıa,sino que figuraran como nodos que no corren ningun proceso. En el casodel parametro conectividad lımite, a un padre no se le podra asociar en lajerarquıa mas de la cantidad de hijos que sea indicado como lımite.

Dentro de esta pantalla, tambien debera configurase los valores de pushy poll para cada uno de los nodos. En el caso de la polıtica jerarquica, poderconfigurar de forma diferente estos valores para cada uno de los niveles de lajerarquıa, es algo casi indispensable. Por esta razon se cuenta con una tabla

39


donde se enumeran cada uno de los niveles de la jerarquıa. Para generarla esnecesario hacer clic sobre el boton Calculate Levels. La generacion se realizateniendo en cuenta el nodo seleccionado como Master Node; en el caso decambiar la eleccion de dicho nodo, se debera regenerar. Esta decision fuetomada en base a que calcular la cantidad de niveles que tendra una jerarquıaes muy costoso para redes de gran tamano.

La pantalla correspondiente a la polıtica Super-Peer se puede observar enla figura 3.7c. Los valores de push y poll son configurados de forma genericapara todos los nodos de la red. A traves del parametro SuperPeer se define elrango a partir del cual se hara una distribucion uniforme y se asignara a cadasuper-peer el tiempo de intercambio de informacion entre ellos. La seleccionde cuales nodos son designados como super-peers se configura a traves de lasopciones clustering method. Figurando tres opciones: a) arbol de tres niveles(3 level tree), b) metis y c) scotch. La primer opcion aplica un algoritmo quesera descripto mas adelante; el mismo se encarga de armar un arbol jerarqui-co y tomar los primeros nodos de esa jerarquıa como super-peers. Las dosopciones restantes del menu permiten indicar el programa que sera utilizadocomo particionador. Los detalles referentes a este mecanismo seran descriptosmas adelante.

Las configuraciones para las polıticas random y best-neighbor son muysimilares. Solo se deben configurar los valores de push y poll. Un punto a des-tacar sobre todas las polıticas, es que la configuracion de los valores de pushy poll puede ser o no habilitadas, de forma que una polıtica solo responda auno de los dos eventos. Adicionalmente, puede configurarse que los valores depush y poll tengan el mismo valor, mediante la opcion same value. La opcionadd Poll permite sumar un valor constante al valor asignado a Poll. Todasestas opciones abren un abanico de posibilidades para la configuracion de losvalores en que se generaran para los eventos de push y poll.

A continuacion se detallan los procedimientos utilizados para la genera-cion de jerarquıas e identificacion de super-peers, junto con las problematicasasociadas.

3.4.2. Generacion de jerarquıas

La jerarquıa que se intenta construir debe utilizar solo los nodos de la redy no los routers como elementos constitutivos. Por lo tanto, como se vera acontinuacion, es importante analizar la red de forma tal que la jerarquıagenerada tenga caracterısticas lo mas realistas posible.

De aquı en adelante se utilizara la terminologıa de grafos. Cuando se hagaalusion a vertices, refiere tanto a nodos grid como routers; en el caso de ejeso aristas refiere a links de la red.

40


Un primer enfoque para la construccion de una jerarquıa entre los nodos,podrıa ser la utilizacion del algoritmo de Dijkstra para obtener los caminosmınimos a todos los vertices. En la figura 3.8 puede verse un ejemplo.

0 - Raiz

12

3

4

5

2

3

3

4

5

Figura 3.8: Ejemplo de utilizacion del algoritmo de Dijkstra para la genera-cion de una jerarquıa a partir de los nodos.

Como se puede observar en la figura, esta solucion no es posible ya que lajerarquıa se construye sobre todos los elementos de la red, tanto nodos comorouters, y no es lo buscado (construir una jerarquıa solo entre los nodos dela red).

Para solucionar este problema se opto por modificar el algoritmo. La ideadel nuevo algoritmo se divide en dos partes: a) se identifican los niveles dela jerarquıa como particiones de los nodos; b) se procede a indicarle a cadanodo cual sera su padre.

A modo de dato de entrada, el algoritmo necesita conocer el nodo desig-nado como raız de la jerarquıa. Esta dato debe es ingresado desde la interfaz,como ya se ha explicado en la seccion 3.4.1. El objetivo es que los nodosde mayor jerarquıa esten mas cerca de la raız, mientras que los de menorjerarquıa sean las hojas del arbol.

El primer paso del algoritmo es generar, a partir de la raız, un arbolde distancias mınimas a todos los vertices. La distancia mınima es medidaen funcion de la cantidad de hops. Luego, a partir de este arbol, se parti-cionan los nodos en terminos de distancia a la raız. Por lo tanto, un nodopertenecera solo a uno de estos conjuntos a los que llamaremos niveles.

La restriccion fundamental para el siguiente paso del algoritmo es que,dado un nodo, el padre del mismo debe pertenecer al nivel inmediatamentesuperior. Esto puede observarse en el ejemplo presentado en la figura 3.9.Una vez concluido, se esta en condiciones de individualizar el padre de cadauno de los nodos.

41


Nivel 2

Nivel 0

Nivel 3

Nivel 1

Figura 3.9: Ejemplo de particion de nodos en niveles de un arbol

La tarea de individualizar los padres de cada uno de los nodos no essimple. Se opto por encontrar el nodo del nivel superior a distancia mınimadel nodo en cuestion, y que simultaneamente tenga la menor cantidad dehijos ya asignados. En la figura 3.10 se muestra un ejemplo de una jerarquıagenerada de esta manera.

Figura 3.10: Ejemplo del resultado de una posible eleccion de padres paracada uno de los nodos en la jerarquıa

En el algoritmo 1 se puede observar el pseudocodigo completo del proce-dimiento de generacion de jerarquıas mencionado.

Otro punto importante a discutir es la identificacion de los super-peers yla construccion de las particiones de nodos. En la proxima seccion se abor-dara este tema.

42


Algoritmo 1 Pseudocodigo del algoritmo de generacion de jerarquıas

Entrada: nodo MasterNode.1: distance ← calcular usando floyd la distancia mınima en hops, entre

todo par de nodos o routers2: levels ← particion en niveles de todos los nodos, desde MasterNode

en funcion de distance

3: para todo nivel l en levels hacer4: para todo nodo i en el nivel l de levels hacer5: father[i] ← nodo en la particion l− 1 a menor distancia del nodo

i, que tenga menos hijos asignados.6: fin para7: fin para8: devolver father

3.4.3. Identificacion de super-peers

La polıtica Super-Peer requiere particionar los nodos de forma que a cadauno de estos le sea asignado un solo super-peers1. Para este punto, como yafue mencionado, se plantean tres estrategias posibles.

Las dos primeras estrategias suponen utilizar el particionador de grafosMetis y el particionador Scotch. Cualquiera sea el caso, una vez obtenidaslas particiones, se procede a determinar cual sera el super-peer. Para esto seidentifica al nodo a distancia menor en promedio a todos los restantes de laparticion. En la figura 3.11 se ilustra una posible particion entre nodos deuna red para el caso de tres subconjuntos. Alguno de los nodos de la particionsera el seleccionado como super-peer, en el caso de la particion de la derecha,en el ejemplo, podrıa ser cualquiera entre el 3, 4 o 5, ya que son los nodos amenor distancia promedio entre todos.

La ultima estrategia utiliza un algoritmo ingenuo para particionar. Estese plantea como solucion alternativa, restringida por la topologıa de la red.La idea fundamental del algoritmo es tomar los primeros nodos a distanciamınima de un nodo dado y asignar a estos como Super-Peers. Por otro la-do, los nodos que esten a menor distancia de cada uno de los Super-Peersseleccionados seran asignados como sus hijos respectivamente.

A diferencia de la polıtica Jerarquica y Super-Peer, tanto Random comoBest-Neighbor no requieren de informacion adicional de configuracion, por lotanto no fue necesario crear ningun algoritmo accesorio.

1Se limita la cantidad de super-peers a uno por cuestiones de simplicidad. Tener masde un super-peer queda fuera del alcance propuesto para esta tesis

43


Figura 3.11: Ejemplo de particion entre nodos de una red.

Dejando claro como se generan los parametros para cada una de las polıti-cas, se continua a explicar lo referente a la generacion de resultados.

3.4.4. Configuraciones adicionales para la generacionde resultados

El archivo deploy no solo consta de lo mencionado en las secciones an-teriores, sino que tambien se deben contener la configuracion referente a losresultados que seran generados por GridMatrix2.

Si bien GridMatrix2 permite elegir que resultados seran almacenados du-rante la ejecucion de una simulacion, se tomo como determinacion generarel archivo deploy indicando que sean almacenados todos los resultados detodos los nodos. En la seccion 2.3 se explica detalladamente cuales son losparametros resultantes de una simulacion y como estos son calculados.

En el caso que se requiera un tipo de configuracion especial para algunnodo determinado, se puede generar el archivo deploy y alterar tal archivode forma manual.

44

Capıtulo 4

Resultados

En este capıtulo se muestran algunos resultados obtenidos usando lasnuevas caracterısticas implementadas en GridMatrix2 para estudiar ciertosaspectos de la relacion y el impacto que hay entre la red fısica subyacen-te en una infraestructura Grid y la organizacion logica que se elije para lacomunicacion de la informacion de monitoreo y descubrimiento de recursos.

4.1. Topologıas basicas de red

Como primer enfoque en el estudio del impacto de las topologıas de red seanalizo el comportamiento de algunas topologıas de red basicas. Para todoslos casos de prueba, se genero una red de 50 routers y una cantidad denodos variable (100, 200 y 300 nodos). El objetivo es mantener la estructurasubyacente de la red, pero aumentar su tamano por medio del incremento denodos.

En lo que sigue de esta seccion, se analizara el desempeno de las dife-rentes polıticas de distribucion de la informacion en distintas topologıas deorganizacion de la red.

Clique

En esta topologıa todos los routers se encuentran conectados entre sı, losnodos se conectan de forma balanceada, es decir, todos los routers tienenconectados aproximadamente la misma cantidad de nodos.

La figura 4.1 muestra el comportamiento a nivel global de cada una delas polıticas en escenarios en los cuales se va aumentando gradualmente lacantidad de nodos del sistema entre 100 y 300 nodos.

En este tipo de topologıa el camino mas largo entre dos nodos es de doshops y el mas corto de tan solo uno, por lo tanto serıa esperable que cualquier

45

CAPITULO 4. RESULTADOS

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)

JerárquicaSuper−Peer

Random

(a) 100 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(b) 200 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(c) 300 nodos

Figura 4.1: Topologıa clique: GIR para las diferentes polıticas. Se usan 50routers y se varıa la cantidad de nodos utilizando un tiempo de expiraciondistribuido uniformemente entre 200 y 300 segundos. Super-Peer presenta elresultado mas estable en todos los casos, mientras que jerarquico con tresniveles solo la supera en los sistemas de 100 nodos. Random pierde rapida-mente eficiencia con el aumento del tamano del sistema, pero no deja de seruna opcion interesante dado que el GIR cae solo un 50 % cuando el sistemacrece un 300 % en cantidad de nodos.

polıtica se comporte relativamente bien.La polıtica Random muestra una caıda gradual del rendimiento a medida

que aumenta el tamano del sistema. Esto se debe a que, al aumentar lacantidad de nodos y la cantidad de recursos existentes, la polıtica Randomse muestra menos eficiente para recolectar la informacion. De todos modos,constituye una alternativa no tan mala dado que un aumento de 300 % en lacantidad de nodos del sistema repercute en una caıda de aproximadamente50 % en el GIR.

46


En los escenarios considerados, la polıtica Super-Peer se comporto deuna manera muy estable y con buen rendimiento a pesar del aumento en eltamano del sistema. Los alcances de esta polıtica en relacion con el tamanodel sistema, se estudia con detalle en la seccion 4.4.

La polıtica Jerarquica presenta resultados interesantes, ya que si bien sucomportamiento para 100 nodos supera al del resto de las polıticas evaluadas(figura 4.1a), para los sistemas de mayor tamano aparece una caıda en elrendimiento que lo empareja a Super-Peer. La jerarquıa que se contruye sobreel grafo clique tiene tres niveles:

el primer nivel esta compuesto unicamente por el nodo root.

en el segundo nivel aparecen todos los nodos que estan conectados almismo router que el nodo root, es decir, que el camino para llegar alroot es de un hop.

en el nivel tres quedan todos los nodos restantes de la red.

Esta forma de organizacion no aprovecha las caracterısticas de la topo-logıa clique. Tener tres niveles significa que, para intercambiar informacionentre dos nodos hoja (pertenecientes al tercer nivel), es posible que el caminoa seguir sea mucho mas largo que si directamente fuera enviada entre ellos.

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)

2 niveles, 100 nodos2 niveles, 200 nodos2 niveles, 300 nodos3 niveles, 100 nodos3 niveles, 200 nodos3 niveles, 300 nodos

(a) Jerarquıas de dos y tres niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)

100 nodos, 200 expiration time100 nodos, 300 expiration time100 nodos, 400 expiration time300 nodos, 200 expiration time300 nodos, 300 expiration time300 nodos, 400 expiration time

(b) Variacion en el tiempo de expiracion

Figura 4.2: GIR en polıtica jerarquica: en la figura (a) una jerarquıa restrin-gida a dos niveles se desempena mejor frente a una de tres en los sistemasde 200 y 300 nodos, mientras que en el sistema con 100 nodos, ambas secomportan de manera similar. En la (b) se aumenta gradualmente el tiempode expiracion utilizando 100 y 300 nodos en una jerarquıa de tres niveles,mostrando un impacto notable en el desempeno a medida que la informaciontarda mas en expirar.

47


A fin de validar esta hipotesis, se presenta la figura 4.2, en la cual selimita la cantidad de niveles generados y se varıa el tiempo de expiracion dela informacion intercambiada entre los nodos.

Para la figura 4.2a se construyo un escenario donde se busca analizar elrendimiento para una jerarquıa de solo dos niveles, es decir, un nodo root yel resto conectados a el (representando un esquema centralizado). Se puedeobservar que para sistemas de 100 nodos, ambas jerarquıas presentan uncomportamiento similar, pero en sistemas de mayor tamano la jerarquıa dedos niveles se comporta mejor que la de tres. Esto la hace muy adecuadapara escenarios fuertemente conectados, aunque de todos modos no haga unuso intensivo de la estructura de red subyacente en lo que respecta al usode la cantidad de caminos alternativos entre cada par de nodos. La relacionentre la cantidad de niveles y el comportamiento de la polıtica jerarquica seprofundiza en la seccion 4.2.

Por otro lado, se analizo la influencia de un aumento en el tiempo deexpiracion de la informacion. Como se menciono anteriormente, definir unajerarquıa de tres niveles implica que la informacion debera atravesar seisniveles para viajar de un extremo al otro (tres niveles desde el nodo al rooty otros tres desde el root al nodo destino). En este aspecto, el aumento deltiempo de expiracion causara que la informacion sea valida durante mastiempo, posibilitando que sea distribuida sin que expire mientras atraviesala jerarquıa.

En los resultados presentados en la figura 4.1, el tiempo de expiracionutilizado para los nodos varıa uniformemente entre 200 y 300 segundos1 uti-lizando una jerarquıa de tres niveles. En la figura 4.2b el tiempo de expiracionde los recursos fue fijado en 200, 300 y 400 segundos utilizando la misma can-tidad de niveles en la jerarquıa.

La figura 4.2b muestran de una manera clara el impacto que produceel aumento en el tiempo de expiracion, siendo especialmente notable parael sistema de 300 nodos: a mayor tiempo de expiracion, mejor es el desem-peno global del sistema. Para un sistema de 100 nodos, se repite el mismofenomeno. Un aumento superior a 400 segundos no tuvo mayor impacto enlos tamanos de sistema estudiados, pudiendo concluir que para estos casosesta cantidad es lo suficientemente alta como para que la informacion puedaatravesar los seis niveles y mantener actualizado a todo el sistema. Dado loimportante que resulta este tema, se lo trata nuevamente en la seccion 4.5.

1En general, la eleccion de la unidad de tiempo no tiene mayor impacto en la generalidadde la discusion de este tipo de resultados

48


Lınea

En esta topologıa los routers estan conectados entre sı uno a continua-cion de otro, con aproximadamente la misma cantidad de nodos conectadosa ellos. El camino mas largo entre un par de nodos en esta topologıa esta di-rectamente relacionada con la cantidad de routers.

Intuitivamente, esta topologıa no parece ser propicia para el intercambiode informacion entre nodos. Si la comunicacion entre nodos superara el anchode banda disponible en alguno de los links, se observarıa congestion y porende una disminucion en la eficiencia de los ındices de informacion. Esteinconveniente, es de particular relevancia en la polıtica Jerarquica ya que laeleccion del nodo root y la jerarquıa utilizada puede provocar la congestion siesta se armara incorrectamente. El resto de las polıticas, si bien podrıan sufrirel mismo sıntoma, poseen una porcion aleatoria que distribuye (al menos, enparte) la congestion.

Por este motivo, se eligieron redes con abundante ancho de banda, y segeneraron las jerarquıas tomando distintos nodos root para corroborar queno se produjera este fenomeno. Se ejecutaron las diferentes polıticas variandola cantidad de nodos en la red, manteniendo fija la cantidad de routers. Losresultados de estos escenarios se presentan en la figura 4.3.

De manera muy similar a la topologıa clique, la polıtica Random mues-tra una caıda en el desempeno a medida que aumenta el tamano del siste-ma, mientras que las polıticas Jerarquica y Super-Peer mantienen estable sudesempeno en todos los tamanos de sistema estudiados. La polıtica Jerarqui-ca es la que presenta mejores resultados, mientras que, levemente por debajo,Super-Peer sigue representando una buena alternativa en estos tamanos desistema.

Anillo

Los routers y nodos se encuentran organizados de manera similar a latopologıa lınea, con la diferencia de que se agrega una conexion entre losrouters de los extremos. De esta forma la red se vuelve simetrica, y el caminomas largo entre un par de nodos esta relacionada con la mitad de la cantidadde routers.

En la figura 4.4 se muestra el comportamiento de las tres polıticas estu-diadas en sistemas con las mismas caracterısticas que las utilizadas en lastopologıas lınea y anillo.

Es interesante notar que, a pesar de disminuir la longitud del camino maslargo en la red, la polıtica Random se comporta de manera muy similar a lastopologıas anteriores. Esto indica que la respuesta obtenida con esta polıtica

49


0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(a) 100 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(b) 200 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(c) 300 nodos

Figura 4.3: Topologıa lınea: GIR para las diferentes polıticas. Se usan 50 rou-ters y se varıa la cantidad de nodos utilizando un tiempo de expiracion distri-buido uniformemente entre 200 y 300 segundos. Tanto la polıtica Jerarquicacomo la Super-Peer se comportan de manera muy estable en todos los casosestudiados, siendo la Jerarquica la que mejor desempeno presenta.

esta relacionada directamente con el tamano del sistema y no con la formaen que la infraestructura de red la interconecta.

Nuevamente, la polıtica Jerarquica con tres niveles y Super-peer presentanvalores muy estables de GIR, siendo la primera la que mejor se comporta.

Estrella

En esta topologıa se identifica un router como central y el resto se conec-tan a este. Los nodos se agregan de manera balanceada a todos los routersexceptuando al nodo central, al que se le agrega un unico nodo. Entonces,el camino mas largo entre un par de nodos es de tres hops, mantiendose

50


0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(a) 100 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(b) 200 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(c) 300 nodos

Figura 4.4: Topologıa Anillo: GIR para las diferentes polıticas. Se usan 50routers y se varıa la cantidad de nodos utilizando un tiempo de expiraciondistribuido uniformemente entre 200 y 300 segundos. Los resultados son si-milares a los obtenidos con la topologıa lınea: la polıtica Jerarquica es laque mejor desempeno presenta seguida muy establemente por Super-Peer.La polıtica Random presenta la misma degradacion en el desempeno que conlas topologıas lınea y anillo.

invariante con el aumento de tamano del sistema.La figura 4.5 muestra los resultados para las polıticas siguiendo las mis-

mas condiciones que en las secciones anteriores con una salvedad: dada latopologıa de la red, en este caso la jerarquıa que queda definida tiene solodos niveles, es decir, corresponde a un esquema centralizado. Como se vio an-teriormente (y se vera en mayor detalle en la siguiente seccion), esto tiene unimpacto mayor en el desempeno de la polıtica Jerarquica.

Nuevamente la polıtica Random sigue mostrandose invariante respecto ala topologıa de la red y solo sensible al tamano del sistema. Los valores de

51


0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(a) 100 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(b) 200 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(c) 300 nodos

Figura 4.5: Topologıa Estrella: GIR para las diferentes polıticas. Se usan 50routers y se varıa la cantidad de nodos utilizando un tiempo de expiraciondistribuido uniformemente entre 200 y 300 segundos. La jerarquıa posee solodos niveles debido a la topologıa utilizada y presenta un desempeno muybueno y estable. Las polıticas Super-peer y Random conservan el comporta-miento mostrado en los tres casos anteriores.

GIR son muy similares a los obtenidos en los tres casos anteriores. La polıticaSuper-peer tambien presenta valores de GIR similares a los casos anteriores:muy estables en el rango de sistemas estudiados y siempre por encima deRandom. La polıtica Jerarquica es la que muestra mayores cambios, convalores de GIR muy altos y estables, sobrepasando notablemente a los delas otras polıticas en todos los tamanos de sistemas. Esto se debe a que lajerarquıa construida posee un nivel menos que en los otros casos. Este efecto,se estudia en profundidad en la proxima seccion.

52


4.2. Impacto de la cantidad de niveles en la

polıtica Jerarquica

En este escenario se busca analizar el desempeno de la polıtica Jerarquicaen funcion de la cantidad de niveles definidos. Como se menciono en la seccion4.1, la cantidad de niveles juega un factor preponderante en el desempenode esta polıtica. Esto se relaciona directamente con el tiempo de expiracionde la informacion intercambiada; en los casos mas dramaticos puede llegar aque la informacion de estado de un extremo de la jerarquıa expire mientrasatraviesa la red, produciendo una disminucion en la cantidad de informacioncon que cuentan los nodos.

La topologıa de red utilizada para este escenario corresponde a una redtipo internet, es decir una topologıa con distribucion exponencial de conecti-vidad con un exponente α = 0,286 [47]. Las redes fueron generadas con unacantidad fija de routers (50 routers), y con una cantidad variable de nodos:100, 200 y 300 nodos. En este sentido, todas las jerarquıas se construyeronsobre redes similares en estructura, pero con un aumento en la cantidad denodos.

Las jerarquıas fueron construidas utilizando la heurıstica explicada en laseccion 3.4.2 en la pagina 40, con 2, 3, 4 y 5 niveles. El caso de dos nivelescorresponde a un esquema centralizado que posee un nodo como root y losnodos restantes son hijos de este.

El comportamiento de la polıtica podrıa verse modificado a partir de laeleccion del nodo root. Para asegurarse que la eleccion del nodo root elegidopara generar la organizacion no influye significativamente en el comporta-miento de la polıtica, se realizaron ejecuciones partiendo de distintos nodosroot. En los graficos que se presentan mas adelante, solo se incluyen los resul-tados de un unico nodo root dado que en todos los casos analizados, variarla eleccion de este nodo no implico un cambio significativo en el comporta-miento observado. En el caso de jerarquıa de 5 niveles con esta cantidad denodos de la red, se observo una variacion mayor que en el resto de los casos.Esta variacion se debe a que la cantidad de nodos no es suficiente para poblaradecuadamente todos los niveles, observandose que el nivel mas bajo quedamuy despoblado, lo que provoca que la eleccion del nodo root sea de mayorimportancia para evaluar el comportamiento. Para este caso se tomo un casopromedio, coherente con el comportamiento en el resto de los niveles.

En cada una de las pruebas realizadas (correspondientes a las figuras 4.6a 4.8), se incluyeron los resultados obtenidos con las polıticas Super-Peery Random que sirven para complementar el analisis del comportamiento eincluyen el desempeno de jerarquıas que utilizan una cantidad creciente de

53


niveles.

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(a) 2 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(b) 3 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(c) 4 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(d) 5 niveles

Figura 4.6: GIR con polıticas Super-Peer, Random y Jerarquica en un sistemacon 100 nodos y 50 routers variando la cantidad de niveles utilizado en lajerarquıa. Con este tamano de sistema, el esquema de dos niveles es el quemejor desempeno presenta. Una jerarquıa con tres niveles

La figura 4.6 muestra el comportamiento de la polıtica Jerarquica en unsistema de 100 nodos y 50 routers. En la figura 4.6a la polıtica Jerarquicaque utiliza dos niveles presenta unos niveles de GIR muy altos, sobrepasandoa Super-Peer y Random. Cuando la jeraquıa esta organizada en tres niveles(figura 4.6b), su desempeno cae hasta emparejarse con Super-Peer, mientrasque Random sigue aun por debajo de ambas. Cuando la jerarquıa tiene cuatroy cinco niveles (figuras 4.6c y 4.6c), el desempeno de la polıtica Jerarquicacae aun mas, quedando por debajo de Super-Peer y emparejado con Randomen ambos casos.

Como se anticipo, la polıtica Jerarquica decrementa su valor de GIR alaumentar la cantidad de niveles, debido a que la informacion debe atravesar

54


un paso intermedio adicional, provocando una retardo que afecta el tiempode vida de la informacion recibida. Es trivialmente predecible que el casode dos niveles (escenario centralizado) sea el de mayor valor de GIR, yaque la informacion de todos los nodos es compartida a traves de un unicopunto. El inconveniente radica en el punto de falla centralizado; es decir,que la informacion queda comprometida en este unico nodo, promoviendo lacongestion en la red o en el nodo central (que debe procesar la informacion)a medida que aumenta la cantidad de nodos. Al aumentar los niveles, estacongestion se distribuye, pudiendo escalar a un mayor numero de nodos. Sinembargo, en este caso el valor de GIR es practicamente indistinguible con elde Super-Peer. Siendo este ultimo mas tolerante a fallas, podrıamos concluirque la polıtica mas conveniente a elegir, en este caso, serıa Super-Peer.

A continuacion se estudiaron las direfentes polıticas en las mismas con-diciones, en un escenario de 200 nodos (50 routers), figura 4.7.

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(a) 2 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(b) 3 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(c) 4 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(d) 5 niveles

Figura 4.7: GIR de las polıticas super-peer, random y jerarquica en un sistemacon 200 nodos y 50 routers variando la cantidad de niveles.

55


La creciente cantidad de nodos en comparacion con el caso anterior afectaa la polıtica Random, disminuyendo su valor de GIR. Sorprendemente, lapolıtica jerarquica conserva los valores de GIR obtenidos con el escenarioanterior (100 nodos), al igual que Super-Peer. Debido a la disminucion de lapolıtica Random, en este caso la polıtica jerarquica de 4 niveles se muestrasuperior que la mencionada. Nuevamente, en el caso de 5 niveles no muestramejorıa con respecto a Random.

Por ultimo, se presenta el caso con 300 nodos y 50 routers, figura 4.8.

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(a) 2 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(b) 3 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(c) 4 niveles

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)


Random

(d) 5 niveles

Figura 4.8: GIR de las polıticas super-peer, random y jerarquica en un sistemacon 300 nodos y 50 routers variando la cantidad de niveles.

Nuevamente, en esta experiencia se ven aumentadas las observaciones delos casos anteriores. La polıtica Random disminuye aun mas que en el casoanterior, a raız del aumento en la cantidad de nodos. Por otro lado, Jerarquicoy Super-Peer mantienen los mismos valores de GIR. Debido al decrementode Random, en este ultimo escenario la jerarquıa de cinco niveles resulta masconveniente que el caso aleatorio.

56


Es interesante notar, que en todos los casos las polıticas Jerarquica ySuper-Peer mantuvieron los valores de GIR; siendo similares el caso de jerarqui-co de 3 niveles con Super-Peer. La respuesta obtenida de ambas polıticas enestos escenarios resulta razonable ya que Super-Peer esta compuesto por clus-ters jerarquicos de dos niveles, interconectados entre ellos de forma P2P pura.Si la cantidad de nodos P2P fuera relativamente pequena, es esperable que secomporte aproximadamente igual que una jerarquıa de dos niveles, obtenien-do un comportamiento global similar a una polıtica estrictamente jerarquicade tres niveles. Por lo tanto, en este tipo de redes resulta conveniente utilizarpolıticas Super-Peer ya que carece de punto unico de falla y no promueve lacongestion de nodos centrales o la red.

4.3. Impacto de la cantidad de Super-Peers

Dada una topologıa de red, la seleccion de cuantos y cuales nodos actuarancomo super-peers es de mucha importancia. Las distintas opciones disponiblesy el procedimiento de seleccion estan descriptos en la seccion 3.4.3 en lapagina 43. En esta seccion se estudia la influencia de la cantidad de super-peers en el comportamiento de esta polıtica.

Es importante destacar, que la polıtica Super-Peer presenta dos casosextremos que son interesantes de remarcar: por un lado si todos los nodosde la red fueran super-peers sin nodos asociados, se estarıa en presencia deuna polıtica Random pura. Por otro lado, si en esta forma de organizacionse eligiese un unico super-peer para toda la red, es decir, si todos los nodosestuvieran asociados a un unico super-peer, se estarıa en presencia de unapolıtica Jerarquica con dos niveles o esquema centralizado.

El escenario de pruebas consta de un sistema en el que se mantiene cons-tante la cantidad de nodos, pero se aumenta gradualmente la cantidad desuper-peers y de routers. El aumento de routers impacta directamente en lalongitud de los caminos entre nodos que quedan definidos en la red. Nue-vamente, las redes contruidas son similares a internet, siguiendo la ley depotencias, con 500 nodos y utilizando 100 y 300 routers. Las simulacionesfueron realizadas con configuraciones de 10, 30 y 50 super-peers.

Es importante notar que el numero promedio de hijos de los nodos super-peer dependera la cantidad de super-peers utilizados en la simulacion. Porejemplo, para 20 super-peers correspondera que cada uno tenga 500/20 = 25hijos. Al aumentar la cantidad de nodos super-peers, menor sera la cantidadde hijos que tenga.

En la figura 4.9 se presentan los resultados de esta simulacion. Para po-der comparar el comportamiento de Super-Peer, se incluyen en la figura los

57


graficos de las polıticas Random y Jerarquica de dos niveles (esquema cen-tralizado).

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)

JerárquicaRandom

10 super−peers30 super−peers50 super−peers

(a) 100 routers

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000G

IR

tiempo (segundos)

JerárquicaRandom

10 super−peers30 super−peers50 super−peers

(b) 300 routers

Figura 4.9: GIR de las polıticas Random, Jerarquica de dos niveles y super-peer en un sistema con 500 nodos, con 100 routers (panel izquierdo) y 300routers (panel derecho), variando la cantidad de super-peers seleccionados.

En las figuras 4.9a y 4.9b se observan las dos polıticas para comparar(Random y Jerarquica de dos niveles) en los dos extremos de valor de GIR.De forma consistente con los resultados de las secciones anteriores, la polıticaJerarquica presenta valores de GIR cercanos a 0,8, mientras que Random semantiene alrededor de 0,2. Es interesante observar que Random no disminuyesu valor con el aumento de routers, sino que esto depende particularmentedel aumento en la cantidad de nodos, en este caso constante.

Como era predecible, el valor de GIR de Super-Peer se encuentra entrelos valores de las dos polıticas de control y al aumentar la cantidad de nodossuper-peer, el valor de GIR disminuye, acercandose cada vez mas a los valoresobtenidos por Random.

Es esperable que el comportamiento en promedio de esta polıtica se com-porte de forma que nunca caiga por debajo del desempeno de la polıticaRandom y ademas no supere el valor dado por la polıtica Jerarquica de dosniveles.

Vale la pena aclarar que, como se dijo en la seccion anterior, el comporta-miento de la polıtica estudiada con pocos nodos super-peer (en comparacioncon la cantidad total de nodos) es practicamente igual al visto en la polıticaJerarquica de tres niveles (no graficado por claridad). Sin embargo, Super-Peer presenta varias ventajas por sobre la polıtica Jerarquica. Por un lado,la subdivision de nodos a lo largo de la red se puede realizar de forma inde-pendiente, pudiendo separar por entidad de administracion independientes.

58


Luego, la interconexion de estas entidades se realiza por una polıtica P2P pu-ra (aleatoria), lo que requiere muy poco esfuerzo de implementacion. Ademas,no posee punto unico de falla; al menos, no de forma global.

4.4. Super-Peer y su lımite en la capacidad

de escalar

Dados los buenos resultados obtenidos por la polıtica Super-Peer en lassecciones anteriores, una pregunta que surge es cual es el lımite en la capaci-dad de escalar que posee esta organizacion. El estado actual de desarrollo deGridMatrix2 no permite hacer simulaciones con una mayor cantidad de no-dos a los mostrados anteriormente debido al consumo de recursos necesariospara la simulacion; y, como vimos hasta ahora con los sistemas estudiados,no se llego a un valor crıtico en el que el desempeno de esta polıtica empeorecon la cantidad de nodos. Por este motivo, se desarrollo una metodologıa quepermite explorar estos lımites utilizando la capacidad actual de GridMatrix2.

Como se describio en la seccion 2.2.2 en la pagina 22, la polıtica Super-peer define dos niveles: un nivel superior formado por los super-peers que secomunican entre sı usando una polıtica P2P (en nuestro caso directamenteRandom) y un nivel inferior en la que los nodos utilizan un superpeer co-mo nodo central en un esquema centralizado o jerarquico de dos niveles. Esposible, entonces, aprovechar esta organizacion hıbrida para disenar la me-todologıa que nos puede permitir llegar a simulaciones que superen el valorcrıtico de nodos de un sistema que utiliza esta polıtica.

La propuesta es modelar el mecanismo de intercambio de informacion anivel de superpeers, pero sin simular el detalle de la comunicacion con losnodos asociados. El procedimiento es, entonces, hacer una simulacion en laque se reemplazan al super-peer con todos sus nodos asociados por un uniconodo que los represente. Para hacerlo, este nodo debe poseer la informacionde recursos que el super-peer va obteniendo de sus nodos asociados duranteel periodo estudiado. Es decir, la cantidad de recursos que el nodo tendrıa,deberıa variar con el tiempo de una manera similar a como varıa la informa-cion de recursos del super-peer que reemplaza. Dado que GridMatrix2 solopermite configurar una cantidad estatica de recursos antes de comenzar lasimulacion, el unico camino a seguir es utilizar el promedio de la cantidad derecursos que tiene el super-peer como valor representativo.

Para que este reemplazo posea validez y los resultados obtenidos tenganvalor, es necesario estudiar la variacion de la informacion de un super-peerindividual. Esto se puede hacer mediante el analisis del LIR en el root en

59


esquema centralizado, lo cual corresponderıa a realizar un acercamiento a loque ocurre en el nivel “inferior” de una polıtica Super-Peer. La figura 4.10muestra los resultados del LIR del root en dos sistemas con 15 y 30 nodos.

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

/LIR

tiempo (segundos)

GIRLIR root

(a) 15 nodos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

/LIR

tiempo (segundos)

GIRLIR root

(b) 30 nodos

Figura 4.10: GIR y LIR del root en un esquema centralizado en dos sistemascon diferente cantidad de nodos. En ambos casos la variacion del LIR en elroot es baja, aunque disminuye aun mas con el aumento en la cantidad de no-dos del sistema. Se incluye el GIR para tener una medida de comportamientoglobal y asegurarse que los resultados son validos.

En ambos casos, se puede notar una baja variacion del LIR, levementeinferior en el caso presentado en la figura 4.10b. Esto permite suponer queserıan validos los resultados de la aproximacion que surge a partir del re-emplazo del super-peer y todos sus nodos asociados por un unico nodo conuna cantidad de informacion correspondiente al promedio de lo que tendrıael super-peer durante la simulacion.

El siguiente paso es estudiar como cambia la distribucion de informacionen la capa de super-peers con el tamano del sistema. Para esto se realizansimulaciones en la que se fija un sistema que utiliza la polıtica Random.Los nodos utilizados tendran recursos propios estaticos que representan asuper-peers con una cantidad de nodos asociados que varıa entre 30 y 50.

En la figura 4.11 se presentan los resultados de esta experiencia en la quese estan representando sistemas de entre 1500 y 2500 nodos (correspondienteal caso de 50 nodos en los graficos), y de 6000 a 10000 nodos (para el caso de200 nodos), aunque solo enfocando en la capa de super-peers. Se tomo comolımite para determinar cuando un sistema no distribuye suficientemente bienla informacion un valor de GIR por debajo de 0,4 que corresponde a unsistema en que los nodos no tienen una buena intercomunicacion entre ellos.

Entonces, en la figura 4.11a se muestra el desempeno de un sistema en

60


0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)

50 nodos100 nodos150 nodos200 nodos

(a) Expiracion entre 200 y 300 segundos

0

0.2

0.4

0.6

0.8

1

0 500 1000 1500 2000 2500 3000

GIR

tiempo (segundos)

50 nodos100 nodos150 nodos200 nodos

(b) Expiracion entre 300 y 400 segundos

Figura 4.11: GIR a nivel de super-peers para una cantidad de nodos entre 50y 200, con distintos tiempos de expiracion.

el que la informacion expira entre los 200 y 300 segundos. En este caso, soloel sistema mas pequeno supera la cota de buen funcionamiento de 0,4 en elGIR, mientras que el de 100 nodos se encuentra en el lımite. Esto significaque si la informacion tiene un tiempo de expiracion de 200 a 300 segundos,el maximo tamano de sistema con un buen desempeno estarıa entre los 3000y 5000 nodos.

Por otro lado, en la figura 4.11b se incluyen los resultados para un tiempode expiracion entre 300 y 400 segundos. El impacto del aumento del tiempo esnotable, ya que permite que todos los tamanos de sistemas incluidos superenla cota impuesta de 0,4 en el GIR. Es decir, que permitirıa tener sistema conbuena transferencia de informacion de recursos con una tamano de 6000 a10000 nodos. Esta relacion que se presenta entre la mejora en el desempenode una polıtica y el tiempo de expiracion de la informacion se trata con mayorprofundidad en la siguiente seccion.

4.5. Impacto de la relacion entre tiempo de

expiracion y ciclo de actualizacion

En esta seccion se busca profundizar el estudio de la relacion entre eltiempo de expiracion de la informacion y el ciclo de actualizacion entre losnodos.

Las figuras 4.12 y 4.13 muestran el GIR promedio de una corrida completaen las distintas polıticas pero descartando los instantes iniciales. En esteperiodo todas las polıticas presentan un tiempo durante el cual la informacion

61


0

0.2

0.4

0.6

0.8

1

50 100 150 200 250 300 350 400 450 500 550

GIR

pro

med

io

tiempo de exp. (segundos)

20406080

100120140

(a) hierarchical

0

0.2

0.4

0.6

0.8

1

50 100 150 200 250 300 350 400 450 500 550

GIR

pro

med

io


20406080

100120140

(b) super-peer

0

0.2

0.4

0.6

0.8

1

50 100 150 200 250 300 350 400 450 500 550

GIR

pro

med

io


10203040506070

(c) random

Figura 4.12: GIR promedio de las distintas polıticas para distintos valores detiempo de expiracion y tiempo de push-poll fijo

empieza a fluir hasta que se estabiliza, por lo que no aporta demasiado a findel analisis que se desea realizar.

En todos los casos, una dismunicion en el ciclo de actualizacion (es decir,aumento de la frecuencia con que los nodos se comunican entre sı) y unaumento en el tiempo de expiracion producen mejores resultados sin importarla polıtica que se analice.

En las figuras 4.12 y 4.13 se ataca la relacion entre el ciclo de actualizaciony el tiempo de refresco, pero en ambos casos, fue necesario dejar uno de losdos fijo y realizar la variacion del otro. A pesar de la valiosa informacionque muestran estos graficos, para analizar con mayor profundidad en el quese comparen las distintas polıticas entre sı, es necesario definir un nuevoparametro R:

R =tiempo expiracion

ciclo actualizacion

62


0

0.2

0.4

0.6

0.8

1

0 20 40 60 80 100 120 140 160

GIR

pro

med

io

tiempo push−poll (segundos)

tiempo de exp. 100tiempo de exp. 200tiempo de exp. 300tiempo de exp. 400tiempo de exp. 500

(a) hierarchical

0

0.2

0.4

0.6

0.8

1

0 20 40 60 80 100 120 140 160

GIR

pro

med

io



(b) super-peer

0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50 60 70 80

GIR

pro

med

io



(c) random

Figura 4.13: GIR promedio en las distintas polıticas para distintos valores detiempo de actualizacion dejando fijo el tiempo de expiracion de la informa-cion. En todos los valores de ciclo de actualizacion, el GIR promedio obtenidoaumenta con el tiempo de expiracion. Esto ocurre para todas las polıticas.

De acuerdo a esta definicion, cuando R se acerque a 1, el tiempo deexpiracion de la informacion y el ciclo de refresco seran muy parecidos entresı. Esto significa que la informacion expirara rapidamente y no dara tiempoa los nodos a comunicar informacion valida al resto del sistema. En estecaso extremo, estarıamos ante una situacion en la cual todos los nodos solocontarıan con la informacion de sus propios recursos o, a lo sumo, con la desus vecinos directos.

Por otro lado, el crecimiento de R significa que la informacion que hayen el sistema tarda muchos ciclos de actualizacion en expirar, lo que puedepermitir que viaje trayectos muy largos y aumente fuertemente la cantidadde informacion valida con que cuentan los nodos del sistema.

Como base para la ejecucion de las simulaciones cuyos resultados se re-

63


0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50

GIR

pro

med

io

R


Random

Figura 4.14: GIR obtenido por distintas polıticas en funcion de la relacionentre tiempo de expiracion y frecuencia de actualizacion (R).

sumen en la figura 4.14 se usa un escenario con un sistema que cuenta con100 nodos y 100 routers. En los lımites de los valores de R analizados, to-das las polıticas suelen tener un comportamiento bastante parejo: cerca de0, todas tienen valores muy bajos de GIR, mientras que al alejarse hacia losvalores altos, todas presentan una pendiente suave de mejora que las terminaacercando entre sı.

La polıtica Jerarquica (esquema centralizado) es la que mejor resulta-dos muestra en los rangos intermedios. Por otro lado, la polıtica Super-peercomporta un poco mas pobre que la Jerarquica, aunque con un buen com-portamiento general en todo el rango de R estudiado. Finalmente y como erade esperar, la polıtica Random presenta el peor desempeno inclusive en losvalores altos de R.

64

Capıtulo 5

Conclusiones

En las ultimas dos decadas se han producido cambios sustanciales en laforma en que percibimos y usamos los recursos y servicios computaciona-les. En este nuevo contexto, Grid Computing aflora como nuevo paradigma,proveyendo la infraestructura basica necesaria para compartir recursos deforma geograficamente distribuida. Una de las caracterısticas mas importan-tes en Grid Computing, es la necesidad de mantener informacion actualizadareferente a los recursos y servicios que el Grid provee.

Actualmente, Globus Toolkit es la plataforma Grid mas utilizada. GTincluye un servicio llamado MDS que se ocupa de la recoleccion, distribucion,indexacion, almacenamiento, y posterior procesamiento de la informacionrelacionada al estado de los diversos recursos, servicios y configuraciones enel Grid.

El estudio de eficacia de las polıticas de propagacion de informacion enel campo de las arquitecturas Grid puede ser inabordable utilizando recursosreales, ya que requeriere la puesta en marcha de un desmesurado numerode equipamiento. Por esta razon se implementaron distintos simuladores deprocesos distribuidos orientados a arquitecturas Grid, entre ellos GridMatrix.

La principal limitacion de GridMatrix es la referida a la utilizacion derecursos, no permitiendo la simulacion de escenarios de gran tamano. Por otrolado, las polıticas de distribucion de informacion son configuradas a manoa traves de un archivo XML y no se provee ninguna funcionalidad para sugeneraracion automatica. De la misma forma, no se provee una herramientade generacion automatica de topologıas de red.

En esta tesis se abordaron los estudios de polıticas de propagacion de in-formacion en una variedad de topologıas de red, extendiendo la herramientaGridMatrix para subsanar las limitaciones mencionadas. Para ello se utiliza-ron los ındices GIR, LIR y GIV que miden la informacion disponible tantoglobal como local (en cada nodo).

65

CAPITULO 5. CONCLUSIONES

Para la generacion automatica de redes se estudiaron soluciones existen-tes, y se tomo como base para el desarrollo SIMULACRUM. Las topologıasimplementadas fueron Clique, Line, Ring, Star, Uniform, Exponential, Wax-man, Zegura y Barabasi. Las polıticas previamente incluidas en GridMatrixson Jerarquica, Random, Super-Peer y Best-Neighbor.

La implementacion de la nueva version de GridMatrix consistio en im-plementar dos modulos. El primero, encargado de la generacion de redes,construye a partir de una determinada configuracion un archivo de descrip-cion de red y su traduccion para el simulador. El segundo, el generador dearchivos, describe la configuracion de una simulacion particular, es decir laspolıticas a utilizar en cada uno de los nodos.

A partir de este desarrollo se pudo estudiar el comportamiento de lasdistintas polıticas de propagacion de informacion en diferentes topologıas dered. En primer lugar, se analizo el comportamiento en las topologıas masbasicas. Como era de esperar, el esquema jerarquico de dos niveles (esquemacentralizado) mostro los valores mas altos de eficiencia. En segundo lugar,Super-Peer y Jerarquico de tres niveles mostraron comportamientos similares,con la ventaja del primero de no poseer punto unico de falla y mas faciladministracion.

A partir de los datos recabados, se decidio ahondar en el analisis de lapolıtica Super-Peer ya que en los ensayos mostro una excelente relacion en-tre eficiencia y costo de mantenimiento. Se estudio esta polıtica en algunosescenarios predefinidos, en los cuales se realizo un barrido de la cantidad desuper-peers. Se obtuvieron resultados alentadores, promoviendo a esta polıti-ca como una excelente alternativa, presentando resultados similares (incluso,mejores) que aquellos obtenidos por la polıtica jerarquica de tres niveles. Pa-ra obtener estos resultados se calculo el lımite de nodos super-peer en la redpara el mejor funcionamiento, manteniendo un alto valor de GIR y ciertotamano de cluster de nodos que facilite el mantenimiento y sea tolerante afallas.

Por su naturaleza de diseno, un aspecto muy interesante es la escalabili-dad de Super-Peer. GridMatrix2, si bien ha aumentado las posibilidades dela version anterior, aun no puede realizar ejecuciones en escenarios lo sufi-cientemente grandes para realizar este estudio. Sin embargo, tomando valorespromedios del comportamiento de los nodos super-peer se realizaron ejecu-ciones tomando a los clusters de recursos como un unico nodo, y se estudio laescalabilidad en ese contexto. En estos escenarios se obtuvieron los lımitesdel tamano de red para esta polıtica (en funcion de los tiempos de vida delos recursos), por encima de los cuales los valores de eficiencia se encuentranpor debajo de lo aceptable.

Por ultimo, se profundizo en el estudio del comportamiento de las polıticas

66

CAPITULO 5. CONCLUSIONES

en funcion de tiempo de vida de la informacion de recursos. Para ello sedefinio un nuevo ındice que relaciona el tiempo de expiracion de los recursos,con el tiempo del ciclo de actualizacion entre nodos. La polıtica Jerarquicacon dos niveles (esquema centralizado) mostro los mejores resultados en losrangos intermedios. Por el contrario, es muy interesante que la polıtica Super-peer se comporto consistemente mejor que la Jerarquica de tres niveles entodos el rango de R estudiado.

La herramienta desarrollada en esta tesis permitio un primer estudio delcomportamiento de distintas polıticas en una diversidad de topologıas de red.Los resultados, aunque preliminares, demuestran un poder de analisis dispo-nible muy grande, con una versatilidad tanto en el desarrollo de topologıascomo en la configuracion de polıticas de propagacion de informacion.

67

Capıtulo 6

Trabajo Futuro

Las extensiones implementadas en GridMatrix2 proponen un gigantescocampo de posibilidades sobre las cuales experimentar. En el presente trabajose tratan algunas, dejando fuera del alcance del mismo una gran cantidad decaminos sin recorrer. Por esta razon, este capıtulo se divide en dos grandesareas, en la primera se mencionan aquellas lıneas de trabajo que no involucrandesarrollos en GridMatrix2, mientras que en la segunda se detallan algunasde las posibilidades que implican aumentar sus capacidades.

6.1. Topicos a profundizar utilizando Grid-

Matrix2 en su version actual

Dentro de este punto se pueden mencionar dos aspectos. Los relacionadoscon la red y los relacionados con las polıticas de distribucion de la informa-cion. En el contexto de la red, solo han sido estudiadas las topologıas basicas(Clique, Lınea, Anillo y Exponencial), quedando fuera del analisis las redestipo Barabasi, Waxman y Zegura. Tambien ha quedado pendiente el estudiode varaciones de las topologıas basicas. Las mismas pueden ser modificadastanto de manera automatica (a traves de las diversas opciones que presentaGridMatrix2), como de forma manual. Otro aspecto considerado, pero noabordado en detalle, es el analisis de la distribucion de conectividad en lared, es decir, la modificacion de los valores de latencia y ancho de banda.

En el contexto de las polıticas de distribucion de informacion existenmuchos parametros que pueden ser estudiados, entre los cuales se puedenmencionar: los intervalos de consulta y suscripcion de las polıticas, el tiempode expiracion, la cantidad de recursos y la duracion de los experimentos.Estos parametros tambien pueden ser combinados con la estructura de lajerarquıa en la polıtica Jerarquica, o la formula de valoracion de los vecinos

68

CAPITULO 6. TRABAJO FUTURO

en la polıtica Best-Neighbor, entre otros.La modificacion de los algoritmos de distribucion de informacion o la im-

plementacion de nuevas polıticas puede resultar muy simples de implementardebido al uso de scripts en Python. Esto abre las puertas al estudio de nuevaspolıticas de distribucion o de profundizar en ciertos detalles de las existentes,como por ejemplo el descubrimiento de vecinos en las polıticas Super-Peer.

Un ultimo punto a mencionar es que, como se vio en la seccion 4.3, elestudio de la cantidad de super-peers en una polıtica Super-Peer en relacioncon las polıticas Jerarquica y Random abre la puerta a analizar cual es la can-tidad de super-peers que debe tener un sistema para operar de forma optima.Esta tarea plantea un interrogante muy interesante y requiere profundizar eneste tema. La idea fundamental es encontrar la curva que relaciona la canti-dad de superpeers con el GIR resultante para una red o topologıa particular.Como puede verse en el figura 6.1, en un estudio preliminar se grafico el GIRpromedio para diferentes cantidades de super-peers, y se aproximo este valorcon una exponencial negativa.

0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50

GIR

pro

med

io

Cantidad de superpeers

relación entre cantidad de superpeers

Figura 6.1: GIR promedio y aproximacion exponencial para una polıticaSuper-Peer para 1, 10, 20, 30, 40 y 50 super-peers.

6.2. Caminos que se abren mediante la ex-

tension de GridMatrix2

La interfaz de GridMatrix2 resulta limitada en algunos aspectos cuan-do se trata de redes grandes o con caracterısticas especiales. La misma no

69


Configuración

Red

Best-NeighborRandom

Super-Peer Jerárquico

Otras políticas(Python)

modificación de los algoritmosde las políticas (Python)

Agregado deparámetrosde medición

políticas

jerarquíalibre

estrictalibre en conexiones

libre en niveles

elección del topede la jerarquía

ejecución

duracción

cantidad derecursos

tiempo deexpiración

algoritmo deasignación devalores (c++)

valores dePush y Poll

Parámetros

Tamaño

Políticade ruteo

todas las rutas

mejores rutas

generación automáticade múltiples redes

de distintos tamaños

cantidadde nodos

cantidadde routers

latenciade loslinks

ancho debanda delos links

Topología

exportación y mediciónde parámetros

básicas

CliquéLínea

AnilloEstrella

alteracionesautomáticas

formula de cuantificación de mejorvecino para Best-Neighbor (Python)

alteraciones manuales

algoritmo de generación de jerarquía (c++)

algoritmo de asignaciónde niveles (c++)

método de selecciónde super-peer

Metis

3Level(head)

tiempo y seteo de Push

tiempo y seteo de Poll

valores iguales

constante adicional

otras (c++)

Zegura

Exponential

Waxman

Barabasi

r babaexp

algoritmo de ruteo (c++)

algoritmo de asignaciónde nodos a routers (c++)

algoritmo de asignaciónde valores (c++)

Figura 6.2: Esquema de posibles trabajos futuros utilizando GridMatrix2. Enel centro de la figura se observan las dos areas fundamentales de configuracionde parametros, tanto para la configuracion de la simulacion, como para ladescripcion de la red. En algunos recuadros se indica si se requiere del usode codigo C++ o Python.

permite visualizar fracciones de una red o generar clusters como elementosde la red. Estos dos puntos resultan fundamentales para explotar todas lascaracterısticas de SimGrid2.

Actualmente GridMatrix2 maneja los recursos como unidades de infor-macion de tamano constante en todos los nodos. Estos valores no puedenser tipificados de forma que cada nodo posea diferentes tipos de recursos. Elestudio de las polıticas de distribucion de informacion, teniendo en cuentaeste aspecto, abre otra rama de posibles experimentos para GridMatrix2.

Si bien la generacion automatica de redes permite construir un conjuntode redes en funcion de parametros para una topologıa particular, GridMatrix2no permite construir una red utilizando otros programas, o por medio descripts programados por el usuario.

Otro aspecto que se engloba dentro de las modificaciones a las polıticas,es el estudio de la tolerancia a fallas, es decir, analizar el comportamiento delas diferentes polıticas ante la caıda de un nodo, un link o un conjunto deellos.

En la figura 6.2 se puede observar un esquema de los trabajos futuros

70


mencionados en esta seccion. En el centro de la figura se observan las dos areasfundamentales de configuracion de parametros, tanto para la configuracionde la simulacion, como para la descripcion de la red. En algunos recuadrosse indica si se requiere del uso de codigo C++ o Python.

71


Acronimos

AS Sistemas Autonomos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

GT4 Globus Toolkit 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

GRIS Grid Resource Information Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

HPC High-performance computing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

MDS Monitoring and Discovery System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

P2P Peer to peer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

VO Organizacion Virtual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

WS Web Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

XML Extensible Markup Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

72

Bibliografıa

[1] D. De Roure, M.A. Baker, N.R. Jennings, and N.R. Shadbolt. Grid com-puting - making the global infrastructure a reality, chapter The evolutionof the Grid, pages 65–100. John Wiley & Sons Ltd, 2003.

[2] Pablo Yabo. Grid matrix: una extension a un simulador de grid pa-ra enfocar en la propagacion de informacion de recursos y monitoreo.Master’s thesis, Facultad de Ciencias Exactas y Naturales, UBA, 2008.

[3] H. Casanova. Simgrid: A toolkit for the simulation of application sche-duling. In CCGRID ’01: Proceedings of the 1st International Symposiumon Cluster Computing and the Grid, page 430, Los Alamitos, CA, USA,2001. IEEE Computer Society.

[4] Henri Casanova, Arnaud Legrand, and Martin Quinson. Simgrid: Ageneric framework for large-scale distributed experiments. In UKSIM’08: Proceedings of the Tenth International Conference on ComputerModeling and Simulation, pages 126–131, Los Alamitos, CA, USA, 2008.IEEE Computer Society.

[5] A. Abbas. Grid Computing: A Practical Guide to Technology and Ap-plications. Charles River Media, Hingham, MA, 2003.

[6] I. Foster, C. Kesselman, J.Nick, and Tuecke S. The physiology of thegrid: An open grid services architecture for distributed systems integra-tion. Technical report, Open Grid Service Infrastructure WG, GlobalGrid Forum, 2002.

[7] Ian Foster and Carl Kesselman. The Grid 2: Blueprint for a New Com-puting Infrastructure. The Morgan Kaufmann Series in Computer Archi-tecture and Design. Morgan Kaufmann Publishers Inc., San Francisco,CA, USA, November 2003.

73

BIBLIOGRAFIA

[8] Ian Foster, Carl Kesselman, and Steven Tuecke. The anatomy of the grid:Enabling scalable virtual organizations. Int. J. High Perform. Comput.Appl., 15(3):200–222, August 2001.

[9] Ian Foster. Globus Toolkit Version 4: Software for Service-OrientedSystems. In H. Jin, D. Reed, and W. Jiang, editors, IFIP Internatio-nal Conference on Network and Parallel Computing 2005, volume 3779of Lecture Notes in Computer Science, pages 2–13. Springer Berlin /Heidelberg, 2005.

[10] Globus Alliance web page. last visited on 03/20/2010.

[11] Giovanni Aloisio, Massimo Cafaro, Italo Epicoco, Sandro Fiore, DanieleLezzi, Maria Mirto, and Silvia Mocavero. Resource and service disco-very in the igrid information service. In Computational Science and ItsApplications - ICCSA, pages 1–9, 2005.

[12] R. Ranjan, A. Harwood, and R. Buyya. Peer-to-peer-based resource dis-covery in global grids: a tutorial. Communications Surveys & Tutorials,IEEE, 10(2):6–33, 2008.

[13] X. Zhang, J. L. Freschl, and J. M. Schopf. A performance study ofmonitoring and information services for distributed systems. In Proc.12th Int’l Conf. High Performance Distrib. Computing, pages 270–281.IEEE Computer Society, Jun 2003.

[14] Serafeim Zanikolas and Rizos Sakellariou. A taxonomy of grid moni-toring systems. Future Gener. Comput. Syst., 21(1):163–188, January2005.

[15] Hawkeye. a monitoring and management tool for distributed systems.Last visited on 07/09/2009.

[16] Jia Yu, Srikumar Venugopal, and Rajkumar Buyya. A market-orientedgrid directory service for publication and discovery of grid service pro-viders and their services. J. Supercomput., 36(1):17–31, 2006.

[17] Gregor von Laszewski, Warren Smith, Steven Tuecke, Steven Fitzge-rald, Ian Foster, and Carl Kesselman. A directory service for configuringhigh-performance distributed computations. In HPDC ’97: Proceedingsof the 6th IEEE International Symposium on High Performance Distri-buted Computing, pages 365–375, Los Alamitos, CA, USA, 1997. IEEEComputer Society.

74

BIBLIOGRAFIA

[18] MDS in Globus Alliance. last visited on 03/20/2010.

[19] K. Czajkowski, S. Fitzgerald, I. Foster, and C. Kesselman. Grid informa-tion services for distributed resource sharing. In HPDC ’01: Proceedingsof the 10th IEEE International Symposium on High Performance Dis-tributed Computing, pages 181–194, Washington, DC, USA, 2001. IEEEComputer Society.

[20] Federico D. Sacerdoti, Mason J. Katz, Matthew L. Massie, and David E.Culler. Wide area cluster monitoring with ganglia. In Proceedings of theIEEE International Conference on Cluster Computing, pages 289–298.IEEE Computer Society, December 2003.

[21] P. Trunfio, D. Talia, C. Papadakis, P. Fragopoulou, M. Mordacchini,M. Pennanen, K. Popov, V. Vlassov, and S. Haridi. Peer-to-Peer resour-ce discovery in Grids: Models and systems. Future Generation ComputerSystems, 23(7):864–878, August 2007.

[22] B. Plale, C. Jacobs, S. Jensen, Ying Liu, C. Moad, R. Parab, and P. Vaid-ya. Understanding grid resource information management through asynthetic database benchmark/workload. In CCGRID ’04: Proceedingsof the 2004 IEEE International Symposium on Cluster Computing andthe Grid, pages 277–284, Washington, DC, USA, April 2004. IEEE Com-puter Society.

[23] Diego Puppin, Stefano Moncelli, Ranieri Baraglia, Nicola Tonellotto,and Fabrizio Silvestri. A grid information service based on peer-to-peer. In Jose C. Cunha and Pedro D. Medeiros, editors, Euro-Par 2005Parallel Processing, volume 3648 of Lecture Notes in Computer Science,pages 454–464. Springer, 2005.

[24] A globus primer, describing globus toolkit version 4. last visited on03/20/2010.

[25] W. Barth. Nagios: System and network monitoring. No Starch PressSan Francisco, CA, USA, 2008.

[26] Key concepts for information services. last visited on 03/20/2010.

[27] B. Jacob, L. Ferreira, N. Bieberstein, C. Gilzean, J.Y. Girard, R. Stra-chowski, and S. Yu. Enabling applications for grid computing with Glo-bus. IBM, 2003.

75

BIBLIOGRAFIA

[28] Alberto Medina, Anukool Lakhina, Ibrahim Matta, and John Byers.Brite: Universal topology generation from a user’s perspective. Technicalreport, Boston, MA, USA, 2001.

[29] Giuseppe Lo Presti Giuseppe Lo Re Giuseppe Di Fatta. Computer net-work topologies: Models and generation tools. Technical Report 5/2001,University of Palermo, Italy, July 2001.

[30] C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator.Technical Report CSE-TR443 -00, Department of EECS, University ofMichigan, 2000.

[31] Algirdas Pakstas Frank Zhigang Wang Muhammad Azizur Rahman.Network topology generation and discovery tools. In The 7th AnnualPostGraduate Symposium on The Convergence of Telecommunications,Networking and Broadcasting, 2006.

[32] M. Doar. A better model for generating test networks. In Proceedings ofGLOBECOM’96. Global Telecommunications Conference, pages 86–93.IEEE, Nov 1996.

[33] Dong Lu and Peter A. Dinda. Gridg: Generating realistic computationalgrids. ACM Sigmetrics Performance Evaluation Review, 30:33–40, 2003.

[34] PDA, the Platform Description Archive. Last visited on 02/24/2010.

[35] Marc-Eduard Frincu, Martin Quinson, and Frederic Suter. HandlingVery Large Platforms with the New SimGrid Platform Description For-malism. Technical Report RT-0348, INRIA, 2008.

[36] Bernard M. Waxman. Routing of multipoint connections. IEEE Journalon Selected Areas in Communications, 6(9):1617–1622, December 1988.

[37] Kenneth L. Calvert, Matthew B. Doar, and Ellen W. Zegura. ModelingInternet Topology. IEEE Communications Magazine, 35(6):160–163,June 1997.

[38] Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in ran-dom networks. Science, 286(5439):509–512, October 1999.

[39] Carlo Mastroianni, Domenico Talia, and Oreste Verta. Designing aninformation system for grids: Comparing hierarchical, decentralized P2Pand super-peer models. Parallel Computing, 34(10):593–611, 2008.

76

BIBLIOGRAFIA

[40] A. Iamnitchi, I. Foster, and D.Nurmi. A peer-to-peer approach to re-source discovery in grid environments. In Proceedings of the 11 th IEEEInternational Symposium on High Performance Distributed ComputingHPDC-11 (HPDC’02), page 419, Edinbourgh, UK, Jul 2002. IEEE.

[41] B. Yang and H. Garcia-Molina. Designing a Super-Peer Network. InProceedings of 19th International Conference on Data Engineering (IC-DE’03), page 49, Los Alamitos, CA, USA, 2003. IEEE Computer So-ciety.

[42] Igraph. http://igraph.sourceforge.net/. Last visited on02/25/2010.

[43] Metis. http://glaros.dtc.umn.edu/gkhome/views/metis. Last visi-ted on 02/25/2010.

[44] Octave. http://www.gnu.org/software/octave/. Last visited on03/20/2010.

[45] Matlab. http://www.mathworks.com/. Last visited on 03/20/2010.

[46] R-project. http://www.r-project.org/. Last visited on 03/20/2010.

[47] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. In SIGCOMM ’99: Procee-dings of the conference on Applications, technologies, architectures, andprotocols for computer communication, pages 251–262, New York, NY,USA, 1999. ACM.

77

http://igraph.sourceforge.net/

http://glaros.dtc.umn.edu/gkhome/views/metis

http://www.gnu.org/software/octave/

http://www.mathworks.com/

http://www.r-project.org/

Impacto de las topolog19 as Grid en el monitoreo y...

Documents

Transcript of Impacto de las topolog19 as Grid en el monitoreo y...