Descubrimiento de servicios tolerante a fallos basado en hipercubos para sistemas distribuidos de gran escala

ADVERTIMENT . La consulta d’aquesta tesi queda condicionada a l’acceptació de les següents condicions d'ús: La difusió d’aquesta tesi per mitjà del servei TDX (www.tesisenxarxa.net) ha estat autoritzada pels titulars dels drets de propietat intel·lectual únicament per a usos privats emmarcats en activitats d’investigació i docència. No s’autoritza la seva reproducció amb finalitats de lucre ni la seva difusió i posada a disposició des d’un lloc aliè al servei TDX. No s’autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant al resum de presentació de la tesi com als seus continguts. En la utilització o cita de parts de la tesi és obligat indicar el nom de la persona autora. ADVERTENCIA. La consulta de esta tesis queda condicionada a la aceptación de las siguientes condiciones de uso: La difusión de esta tesis por medio del servicio TDR (www.tesisenred.net) ha sido autorizada por los titulares de los derechos de propiedad intelectual únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro ni su difusión y puesta a disposición desde un sitio ajeno al servicio TDR. No se autoriza la presentación de su contenido en una ventana o marco ajeno a TDR (framing). Esta reserva de derechos afecta tanto al resumen de presentación de la tesis como a sus contenidos. En la utilización o cita de partes de la tesis es obligado indicar el nombre de la persona autora. WARNING. On having consulted this thesis you’re accepting the following use conditions: Spreading this thesis by the TDX (www.tesisenxarxa.net) service has been authorized by the titular of the intellectual property rights only for private uses placed in investigation and teaching activities. Reproduction with lucrative aims is not authorized neither its spreading and availability from a site foreign to the TDX service. Introducing its content in a window or frame foreign to the TDX service is not authorized (framing). This rights affect to the presentation summary of the thesis as well as to its contents. In the using or citation of parts of the thesis it’s obliged to indicate the name of the author Qwertyuiopasdfghjklzxcvbnmqwertyu iopasdfghjklzxcvbnmqwertyuiopasdfg hjklzxcvbnmqwertyuiopasdfghjklzxcv bnmqwertyuiopasdfghjklzxcvbnmqwe rtyuiopasdfghjklzxcvbnmqwertyuiopa sdfghjklzxcvbnmqwertyuiopasdfghjklz xcvbnmqwertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmqwertyuio pasdfghjklzxcvbnmqwertyuiopasdfghj klzxcvbnmqwertyuiopasdfghjklzxcvbn mqwertyuiopasdfghjklzxcvbnmqwerty uiopasdfghjklzxcvbnmqwertyuiopasdf ghjklzxcvbnmqwertyuiopasdfghjklzxc vbnmqwertyuiopasdfghjklzxcvbnmrty uiopasdfghjklzxcvbnmqwertyuiopasdf ghjklzxcvbnmqwertyuiopasdf ghjklzxcvbnmqwertyuiopasdfghjklzxc DESCUBRIMIENTO DE SERVICIOS TOLERANTE A FALLOS BASADO EN HIPERCUBOS PARA SISTEMAS DISTRIBUIDOS DE GRAN ESCALA ANTONIA GALLARDO GÓMEZ Ingeniera Técnico Superior en Telecomunicaciones DIRECTOR Dr. LUIS M. DÍAZ DE CERIO RIPALDA Memoria presentada en cumplimiento parcial de los requisitos para el grado de Doctor en el Departamento de Arquitectura de Computadores de la Universitat Politècnica de Catalunya (UPC) – BarcelonaTech Julio 2013 DESCUBRIMIENTO DE SERVICIOS TOLERANTE A FALLOS BASADO EN HIPERCUBOS PARA SISTEMAS DISTRIBUIDOS DE GRAN ESCALA ANTONIA GALLARDO GOMEZ Memoria presentada en cumplimiento parcial de los requisitos para el grado de Doctor en el Departamento de Arquitectura de Computadores de la Universitat Politècnica de Catalunya (UPC) – BarcelonaTech Julio 2013 Dedicada a mi hijo David y a mi madre. vii ÍNDICE ÍNDICE ..................................................................................................................... vii LISTA DE FIGURAS ................................................................................................. ix LISTA DE TABLAS ................................................................................................. xiii LISTA DE PUBLICACIONES ................................................................................ xvii AGRADECIMIENTOS ............................................................................................. xix ABSTRACT .............................................................................................................. xxi I. INTRODUCCIÓN .............................................................................................. 1 1.1 Resumen de la tesis..................................................................................... 1 1.2 Contribuciones de la tesis ........................................................................... 4 1.3 Esquema de la tesis ..................................................................................... 5 II. ESTADO DEL ARTE ......................................................................................... 7 2.1 Estándares ................................................................................................... 7 2.2 Servicios de descubrimiento ..................................................................... 10 2.3 Hipercubo ................................................................................................. 15 2.4 Síntesis ...................................................................................................... 17 III. HIPERCUBO .................................................................................................... 19 3.1 Definición de hipercubo ........................................................................... 19 3.2 Mantenimiento de un hipercubo ............................................................... 20 3.3 Búsquedas en un hipercubo ...................................................................... 28 IV. DESCUBRIMIENTO DE SERVICIOS ........................................................... 33 4.1 Arquitectura del servicio .......................................................................... 33 4.2 Búsqueda en el servicio ............................................................................ 34 V. EVALUACIONES ............................................................................................ 53 5.1 Herramientas utilizadas ............................................................................ 53 5.2 Evaluación de escalabilidad ...................................................................... 55 5.3 Flexibilidad estática en hipercubos completos ......................................... 59 5.4 Flexibilidad estática en hipercubos incompletos ...................................... 65 viii 5.5 Tiempos de búsqueda por simulación ...................................................... 71 5.6 Tiempos de búsqueda en PlanetLab ......................................................... 74 VI. CONCLUSIONES Y TRABAJO FUTURO .................................................... 83 BIBLIOGRAFÍA ....................................................................................................... 87 ANEXOS ................................................................................................................... 93 ANEXO A: EVALUACIÓN DE ESCALABILIDAD .............................................. 95 ANEXO B: EVALUACIÓN EN HIPERCUBOS COMPLETOS ........................... 101 ANEXO C: EVALUACIÓN EN HIPERCUBOS INCOMPLETOS ...................... 103 ANEXO D: TIEMPOS DE BÚSQUEDA POR SIMULACIÓN............................. 109 ANEXO E: LISTA DE NODOS DE PLANETLAB UTILIZADOS ...................... 111 ANEXO F: TIEMPOS DE BÚSQUEDA EN PLANETLAB ................................. 115 xv Tabla 40: Porcentaje de veces que se encuentra un servicio buscado en PlanetLab. ............. 116 xvii LISTA DE PUBLICACIONES Se listan las publicaciones dividiéndolas en artículos en revistas y presentados en congresos y en orden cronológico inverso. I. ARTÍCULOS EN REVISTAS Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Roc Messeguer Pallarès; Andrreu P. Isern Deyà; Kana Sanjeevan. GRID Resource Searching on the GridSim Simulator. Lecture Notes in Computer Science. 5544,pp. 357366. Springer-Verlag, 05/2009 . ISSN 0302-9743. Fuente de impacto: SCOPUS (SJR) – Índice de impacto: 0.572 Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan. HGRID: A Selfconfiguring Grid Resource Discovery. Journal of Computing and Information Technology. 16 - 4, pp. 333 - 338. University Computing Centre of Zagreb, 12/2008. ISSN 1330-1136. Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan.Self-configuring Resource Discovery on a Hypercube Grid Overlay. Lecture Notes in Computer Science. 5165,pp. 510 - 519.Springer-Verlag, 08/2008. ISSN 0302-9743. Fuente de impacto: SCOPUS (SJR) – Índice de impacto: 0.493 xviii II. ARTÍCULOS PRESENTADOS EN CONGRESOS Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Roc Messeguer Pallarès; Andreu P. Isern Deyà; Kana Sanjeevan. GRID Resource Searching on the GridSim Simulator. 9th International Conference on Computational Science (mayo del 2009), pp. 357 - 366. ISBN 978-3-642-01969-2. Fuente de impacto: ERA 2010 – Rango de impacto: A Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan. HGRID: Fault Tolerant, Log2N Resource Management for Grids. 5th International Conference on Networking and Services (abril 2009), pp. 511 - 517. ISBN 978-0-7695-3586-9. Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan. Self-configuring Resource Discovery on a Hypercube Grid Overlay. 14th International Euro-Par Conference (agosto 2008), pp. 510 - 519. ISBN 978-3-540-85450-0. Fuente de impacto: ERA 2010 – Rango de impacto: A Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan. HGRID: A Selfconfiguring Grid Resource Discovery. 30th International Conference on Information Technology Interfaces (junio 2008), pp. 833 - 838. ISBN 978-953-7138-12-7. Fuente de impacto: ERA 2010 – Rango de impacto: C Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan. HGRID: An Adaptive Grid Resource Discovery. 2nd International Conference on Complex, Intelligent and Software Intensive Systems (marzo 2008), pp. 411 - 416. ISBN 978-0-7695-3109-0. Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan; Luis C. E. Bona. Scalable Self-Configuring Resource Discovery for Grids, V Brazilian Workshop on Grid Computing and Applications (junio 2007), pp. 13 - 22. ISBN 85-766-9118-3. Antonia Gallardo Gómez; Luis Díaz de Cerio Ripalda; Kana Sanjeevan. A Fault Tolerant, Log2N Resource Management Scheme for Grids. XIV Jornadas de Concurrencia y Sistemas Distribuidos (junio 2006), pp. 145 - 155.ISBN 84-689-9292-5 xix AGRADECIMIENTOS En estas líneas quiero agradecer a mi director Luis, a mi compañero de despacho y amigo Sanji y a mi ponente Leandro, su ayuda y su paciencia durante todo el tiempo que ha durado esta tesis. También quiero agradecer a Miguel, a Cristina, a Esther y a Angélica que me recordaran que tenía este trabajo pendiente (tengo tendencia a dispersarme). Muchas gracias. No quiero olvidar tampoco a Roc ya que con él empecé un trabajo final de carrera que sin su ayuda no hubiera finalizado y al que hago referencia en este documento. También quiero recordar a mis padres que siempre trabajaron para que yo llegara hasta aquí y que aguantaron mi mal humor cuando no lograba mis objetivos. Mi hermana también estuvo ahí. Finalmente, agradezco a la persona más importante de mi vida, a mi hijo David, su ayuda y todas las horas que no ha podido jugar conmigo en el último año (mientras yo acababa este trabajo), y al que quiero muchísimo. xxi ABSTRACT Current distributed systems that are capable of sharing resources in a distributed manner are experiencing an increase in their use and scope. This increased use in various application areas is largely due to the low cost of deployment and maintenance of a distributed environment, when compared to architectures like supercomputers. A supercomputer consists of thousands of processing units (CPUs) and thousands of gigabytes (GBs) of RAM, which work together to process complex operations and / or expensive simulations of physics, medical research, weather, etc. Supercomputers are located in a single room, where all processors and memories are linked by high speed networks and are within walking distance. This clearly differentiates them from distributed systems that are geographically distributed environments linked (typically) by the Internet. Many research efforts today are focused on providing solutions for distributed systems. These include for example the work of European Grid Infrastructure (EGI) [1] which aims to create an e-Science infrastructure that makes use of a variety of distributed computing technologies and will strengthen Europe's position in the area of distributed computing infrastructures. It is essential that the solutions proposed allow for the sharing of a very large number of resources. This is a complex challenge to tackle since we do not want the solution to degrade as the number of system resources increase. It is also imperative that the solutions proposed, adapt to failures that occur both in the network and in the hardware and / or software that form the distributed system. This does not imply that the components should be universally available, but that the solution should be able to adapt to obtain the highest possible performance from all the components available at a given time. This is a more complex challenge. This thesis proposes a Resource Discovery Service (of services or resources) for largescale distributed systems that are able to adapt to failures that occur in the system. By large scale systems, we mean systems that may be made up of hundreds, thousands or millions of machines. Failures refer to components that are not accessible through the network, components that are not working, or are overloaded, etc. It should be mentioned that in this work we found that in a real environment of geographically distributed resources, it is essential for service discovery to be fault tolerant. In one of the evaluations of our proposed discovery service, we chose 150 machines distributed geographically throughout Europe at random, without knowing if they were in a state of failure or not. We found that 24'67% of them were unavailable because they were in a failed state or because they failed during the evaluation of our service discovery. Examples of distributed systems where you can apply the discovery service that is presented in this thesis are Grid environments. A Grid environment [2] integrates communication networks and machines to provide a virtual platform for computing and data management to users. A user accesses the Grid and utilizes its resources (individual computers, data files, etc.). Grid environments allow users to interact with the resources in a uniform way, providing a xxii powerful platform. Another way to define a Grid is to compare it with the electrical grid [3]. For example, when you submit a job to the Grid environment or store data in it, it is not known exactly which resource in the Grid is used - just as when an electrical device is connected, we do not know from where the energy consumed is generated. A user of a Grid only needs an access device and a network connection while an electrical network user only needs a plug that is connected to the mains. Thus, Grid environments are transforming society, considerably increasing computing power and distributed storage by combining individual resources that by themselves have no significant power or storage capacity. An efficient resource discovery service becomes essential in such environments. Other examples of distributed systems where the Resource Discovery Service presented in this thesis can be applied are Cloud environments [4], since such environments are large-scale distributed systems. Companies like Amazon, Google or Microsoft that own innumerable number of machines are provisioning commercial Cloud environments and offering computing (Amazon EC2), data storage (Amazon S3), web applications hosting (Google App Engine) , collaboration through online versions of office applications (Microsoft Office 365), etc.. In these environments too, service discovery is critical. In this thesis, the proposed discovery service is based on an overlay that has a hypercube topology that interconnects nodes / intermediaries (brokers). The term overlay is used to describe a virtual network constructed at the application layer, above the level of TCP / IP. It acts as an intermediary component that mediates between service consumers (or clients) and service providers (or servers). Service discovery can be seen as a process that consists of 4 phases: bootstrapping, where customers and service providers establish the first contact with the system; service announcement, where a service provider publishes information about the services provided; search, where a client seeks one or more specific services; and selection, the last phase of service discovery where the service to be utilized by the user is selected from those available. This thesis focuses on the search phase. An example could be a client trying to locate clusters with 8 CPUs, 1 GB of memory with CPU usage below 50%; where the clusters must have given software installed, such ATLAS-6.0.4; and is connected to a database containing the data of a particular experiment. Once the clusters that meet the above requirements are localized, the last phase of resource discovery is the selection of the cluster that is to be used by the client. The difficulties of this type of search lies, among others, in that resource discovery systems based on centralized topologies that are not fault tolerant degrade when the number of shared resources increase. Hence, if a server fails, the search fails and the customer cannot use the service. For these reasons, the discovery service presented is not based on a centralized topology. Furthermore, there is no component of the system that has information about the entirety of shared resources within which a client could locate a needed resource. This poses the complex challenge of ensuring that if the resource searched in a system is available, then the client must be able to locate it. Like other authors [5], we distinguish between three aspects of fault tolerance in an overlay. An overlay is a virtual network that connects nodes. The first aspect is data replication, a xxiii technique of having multiple copies of the same data in different nodes. The data will be lost only if the nodes fail simultaneously. The second aspect is the maintenance of the overlay. This requires the application of some technique or techniques to reconfigure the overlay, removing from it the failed nodes. Since the reconfiguration of the overlay is not immediate, the system must continue to serve the demands of their customers while reconfiguring the overlay, the third aspect has to do with the static resilience of the algorithm that runs on the overlay. Static resilience is the ability of the algorithm running on the overlay to continue serving customers before failover algorithms run. Of the three aspects above, this paper will not focus on data replication or maintenance of the overlay. The main contribution of this thesis will focus on presenting a search algorithm with high static flexibility. In order to evaluate static flexibility, we consider static nodes identified to be in a failed state in the overlay and assume that the reconfiguration techniques for the overlay have still not been executed – i.e., the nodes in a failed state still belong to the overlay. Searches are performed on this static scenario and evaluated to see if resources (services) can be located efficiently under these conditions. The results obtained for static flexibility are very encouraging. For example, in a distributed system consisting of about 1,000,000 nodes, if we consider that the required resources present in the overlay are uniformly distributed and that 30% of the nodes fail in a uniformly distributed manner, the algorithm presented in this thesis is able to locate about 94% of them. This is in contrast to the algorithm proposed by HaoRen et al. [6] (described later in this thesis) that locates only 4% of the available resources. Furthermore, if we apply the algorithm in HyperD [7] to the example shown in their article [8] (also described later in this thesis) and compare it to the results from applying the algorithm presented in this thesis, we are able to locate 100% of the resources present compared to 55.5% in their case. The algorithms that have been compared with the one proposed in this thesis are algorithms for large-scale distributed systems that are structured as hypercube overlay topologies. Specific to the case of HaoRen et al., after the review of a publication, it has been necessary to assert that comparatively, the algorithm proposed in this paper is not the same as the algorithm proposed by them. Furthermore, our proposal has significantly enhanced static resilience. It is important to emphasize that a resource discovery system formed by an overlay along with a search algorithm that has less static resilience than another, should be able to reconfigure itself faster in order to be able to be equivalently fault tolerant. The high values of static resilience that have been realized in this thesis make the costly process of immediate reconfiguration of failed nodes in a hypercube unnecessary for the correct functioning of the resource discovery process. The reason is that although the hypercube has not been reconfigured, the resource discovery system continues to serve the requests of customers efficiently. To conclude this section, the quality of the algorithm proposed in this thesis is first evaluated by measuring whether when applied to large-scale distributed systems it significantly degrades it, and secondly by measuring its static resilience and comparing the results obtained with algorithms proposed by other authors and thirdly by evaluating in terms of search times. xxiv Also, search times are obtained by emulation of systems formed by about a thousand nodes. As a final evaluation, we implemented a system consisting of 150 machines distributed geographically throughout Europe that were running user processes that were beyond our control. Thus we were able run experiments (searches) under real traffic conditions. The machines were chosen randomly without knowing if they were in a faulty state or not. Of the chosen machines, 24'67% of them was found to be in a failed state - because they were in error or because they failed during searches. This clearly shows that the algorithms to be used in large-scale distributed systems must be fault tolerant. The main contributions of this thesis are: A decentralized architecture that has partial information of system failures, named HOverlay that can efficiently search for services in large-scale distributed systems (orders of magnitude of hundreds, thousands and millions of machines). Two search algorithms (prior to the final proposal), called Algorithm-vd and Algorithm-va for large-scale systems that adapt to failures that inevitably occur in any system. A search algorithm (the final proposal) called Algorithm-taux, also for large-scale systems that adapts to the inevitable failure of any system and one that learns from previous searches. This enables future searches to better adapt to failures with Algorithm-va and Algorithm-vd, for example when there is a network partition, i.e., when all the network connections between two groups of systems fail simultaneously. In order to evaluate Algorithm-taux and compare it to other algorithms we have implemented: A simulator that can evaluate a distributed system with static resilience and distributed algorithms that run on the system based on a hypercube topology that can have up to millions of nodes. This high number of nodes has required simulations with large cost in time. Using this prototype, when the system malfunctions, Algorithm-taux adapts even to 90% more. A simulator that allows us to emulate a distributed system, measuring search times and effectiveness. Using this prototype to simulate 30% of evenly distributed failed nodes and the scarcity of services sought and present in the system, Algorithm-taux was able to find at least one service that satisfied its search criteria in 100% of the simulations performed. A prototype to measure search times and effectiveness in a real system that is geographically distributed and based on a hypercube topology. The prototype has been tested on a set of 150 machines distributed throughout Europe. II. ESTADO DEL ARTE En este capítulo se describen trabajos relacionados con la propuesta presentada dividiendo el capítulo en 4 apartados. El primer apartado se dedica a estándares y cómo aplicarlos a la propuesta presentada más adelante en el documento. El segundo apartado se centra en describir brevemente servicios de descubrimiento de servicios propuestos. En el tercer apartado de este capítulo se presentan para la topología en hipercubo propuestas donde la topología se genera con interconexiones físicas y donde la topología se genera con interconexiones lógicas En el cuarto y último apartado del capítulo se concluye con una síntesis de todos apartados anteriores. 2.1 Estándares Tal y como se ha comentado anteriormente ejemplos de sistemas distribuidos donde puede aplicarse la propuesta de esta tesis son los entornos de Grid. Al igual que un portátil comprado para una universidad catalana no podrá recargar su batería directamente enchufando a la corriente en la habitación de un hotel de Luisiana (Estados Unidos), la solución desarrollada para un entorno de Grid particular no siempre funcionará para otro. Si los entornos de Grid llegaron para ser ampliamente adoptados – si están para ofrecer soluciones reales, con riesgos aceptables, para la industria y la e-Ciencia – entonces deben ser interoperables, lo que implica el desarrollo de estándares. También se ha comentado que otros ejemplos de sistemas distribuidos donde puede aplicarse la propuesta de este documento son los entornos de Cloud, pero a día de hoy estos entornos no han desarrollado estándares para ser interoperables y habitualmente pertenecen a una única organización. Así este apartado se centra en estándares para entornos de Grid y cómo aplicarlos a la propuesta de esta tesis, ya que es necesario que una solución para sistemas distribuidos de gran escala sea interoperable como debe serlo una solución para Grid. 2.1.1 Grid Monitoring Architecture Grid Monitoring Architecture (GMA) fue propuesto por Tierney et al. [9], y ha sido aceptado como estándar (en la categoría de información), para sistemas de monitorización de Grid por el Open Grid Forum [10] (o Global Grid Forum, como se llama ahora). Se trata de una arquitectura simple compuesta por tres componentes: Productor: una fuente de datos en el Grid, por ejemplo, un sensor. Consumidor: un usuario de los datos disponibles en el Grid. Servicio de Directorio: un almacén de datos que guarda detalles de los productores y consumidores. La figura 1 muestra la arquitectura de GMA. Un productor registra una descripción de su servicio ofrecido en el Servicio de Directorio. Un consumidor contacta con el Servicio de Directorio para localizar proveedores que dispongan del servicio que busca. Una comunicación directa entre el consumidor y cada uno de los productores seleccionados es establecida entonces. Los consumidores pueden registrarse también en el Servicio de Directorio para ser notificados si nuevos productores que dispongan del servicio buscado se registran en el Servicio de Directorio. 8 Directory Service Consumer Producer Register Consumer / find Producers Consumer details Producers details Register Producer / find Consumers events suscribe Data flow Control messages Figura 1: Arquitectura de GMA1 La arquitectura presentada en esta tesis puede seguir la misma arquitectura que el GMA, añadiendo una forma de interconectar los Servicios de Directorio presentes en el Grid entre sí. 2.1.2 Globus Toolkit Globus Toolkit (GT) [12] es un software de código abierto cuyo objetivo es ser un estándar de facto apara desarrollar sistemas distribuidos que compartan servicios. Es ampliamente utilizado en la ciencia y, recientemente, en aplicaciones comerciales. Está siendo desarrollado por la Globus Alliance y otros colaboradores en todo el mundo. GT está formado por un conjunto de componentes. Por ejemplo, Grid Resource Allocation & Management (GRAM), para el envío de trabajos a una máquina determinada. El componente usado para el descubrimiento de servicios es MDS, (Metacomputing Directory Service, Monitoring and Discovery Service o Monitoring and Discovery System, dependiendo de la versión del GT). MDS define e implementa mecanismos para descubrimiento de recursos/servicios y para monitorización en sistemas distribuidos. Dependiendo de la version de GT el servicio de descubrimiento de MDS varía. MDS1 (Metacomputing Directory Service), liberado en GT 1.1.2 y anteriores, está basado en una base de datos centralizada LDAP [13]. MDS2 (Monitoring and Discovery Service), liberado en GT 1.1.3 y GT2.x, está basado en bases de datos LDAP distribuidas. MDS3 (Monitory and Discovery System), liberado con GT 3.x, está basado en servicios distribuidos siguiendo el estándar OGSI [14]. MDS4 (Monitoring and Discovery System), liberado con GT4.x, está basado en Web Services [15] descentralizados. La figura 2 muestra conceptualmente la arquitectura de MDS2, MDS3 y MDS4 dentro de una organización. Está formada por Resources y Aggregators. Resources son los recursos que ofrece una organización al sistema distribuido, y Aggregators son índices que almacenan información de los Resources. Los Aggregators pueden registrarse en otros Aggregators. En la figura 2 el Aggregator superior contiene información de 6 Resources. A medida que subimos en 1 fuente: [11]. 9 la jerarquía, tenemos información de más Resources, pero la información generalmente está menos actualizada. Los clientes pueden buscar servicios conectándose a los Resources (la información será más reciente pero es necesario que el cliente conozca Resources que existen en el sistema para poderse conectar a ellos) o pueden buscar servicios conectándose a los Aggregators (aquí no es necesario conocer Resources que hay en el sistema pero la información está menos actualizada). A AA R R R R R R Client Figura 2: Arquitectura de MDS2, MDS3 y MDS4. Centrándonos en la última versión del MDS, MDS4 [16], se han implementado dos Aggregators: Index Service y Trigger Service. Un Index Service monitoriza información de los servicios del sistema y la publica en un único lugar. Generalmente, se espera que una organización implemente uno o más Index Services, que almacenen información de todos los recursos disponibles en la organización. El Index Service de MDS4 guarda, no sólo información de la localización del servicio, sino también una versión cacheada del servicio, y mantiene la copia cacheada actualizada, utilizando mecanismos de tiempo de vida. En general, los Index Services pueden organizarse en jerarquías, pero no hay un índice global que disponga de información de todos los recursos del sistema. El Aggregator del Trigger Service guarda información de los servicios y ejecuta alguna acción en función de esa información (por ejemplo, enviar un e-mail a los administradores, cuando se alcanza cierto valor de carga del sistema o cuando el espacio en disco disponible está por debajo de algún valor, con el objetivo de identificar posibles anomalías en el sistema). 10 La propuesta de esta tesis puede implementarse utilizando MDS4. Esto implicaría interconectar los Index Services que consideren cada una de las organizaciones que forman el sistema distribuido siguiendo la topología presentada en esta tesis y que los clientes se conecten a cualquiera de los Index Service. 2.2 Servicios de descubrimiento Se han publicado bastantes servicios de descubrimiento en el contexto de sistemas distribuidos de gran escala, aunque no todavía suficientes. Este apartado describe el servicio de descubrimiento de Secure Service Discovery Service (SDS), Intentional Naming System (INS), arquitecturas Peer-to-Peer (P2P), TeraGrid, Uniform Interface to Computing Resources (UNICORE), Advanced Resource Connector y Resource Selection Service. Los 3 primeros se consideran tolerantes a fallos de todos los comparados en [17]. El resto son relevantes en Grid. 2.2.1 Secure Service Discovery Service La arquitectura de SDS [18] se compone de servidores SDS organizados siguiendo una topología en árbol jerárquica. Ejemplos de jerarquías en árbol que pueden utilizarse son las basadas en dominios administrativos (compañías, gobiernos, organizaciones, etc.), las basadas en la topología de la red (saltos de red), las basadas en medidas de métricas de red (ancho de banda, latencia, etc.) y las basadas en localización geográfica. Cada servidor SDS puede participar en una o más jerarquías, manteniendo punteros separados a los servidores SDS padres e hijos de cada una de las jerarquías a las que pertenecen. Cada servidor SDS es responsable de un conjunto de dominios. Una vez un servidor SDS ha establecido su conjunto de dominios, almacena las descripciones de servicios de los dominios de los que es responsable y, las descripciones de servicios de los dominios de sus hijos en la jerarquía SDS a la que pertenece; cachea estas descripciones y propaga un resumen de esta información a su servidor SDS padre. La figura 3 muestra la arquitectura de SDS. El servidor SDS C contiene descripciones de servicios de los dominios C, A y B, ya que los servidores SDS A y B son nodos hijos del servidor C en la jerarquía del ejemplo, propagando un resumen de estas descripciones al servidor SDS D que es su servidor SDS padre. 11 C BA D A | B | C BA SDS server Figura 3: Arquitectura de SDS. La función principal de un servidor SDS es localizar servicios que le piden los clientes. Cuando un cliente busca un determinado servicio, el cliente se conecta a un servidor SDS y envía su petición. El servidor SDS busca en su base de datos local y devuelve al cliente todas las descripciones de servicios que cumplen los requisitos de la petición de éste. En caso de que el servidor SDS no disponga de ninguna descripción de servicio que cumpla las necesidades del cliente, el servidor SDS reenvía la petición recibida a su servidor SDS padre. Un servidor SDS puede utilizar uno o varios servidores de respaldo que comparten las descripciones de servicios de éste. Si el servidor SDS deja de funcionar, uno de los servidores SDS de respaldo toma su relevo de forma transparente al cliente. 2.2.2 Intentional Naming System El sistema de descubrimiento INS está formado por una overlay de intermediarios que se llaman Intentional Name Resolvers (INRs) [19]. Los INS se agrupan por dominios y se propone que cada dominio tenga un “resolvedor de espacio de dominio” (DSR) que contiene la lista de INRs de su dominio. La información de los servicios que ofrece un dominio se replica en todos los INRs. Esta información replicada se almacena, dentro de cada INR, en una estructura en árbol llamada name-tree. Cuando un INR recibe una búsqueda de servicios por parte de un cliente, el INR busca servicios que satisfagan la petición dentro de su name-tree. Cabe destacar que este servicio de descubrimiento se considera distribuido porque hay un conjunto de INRs y de gran escala porque en las evaluaciones realizadas escala para varios miles de servicios, pero los mismos autores reconocen dejan como trabajo futuro la adaptación de INS a redes de área extensa que utilicen Internet. 12 2.2.3 Peer-To-Peer A grandes rasgos la arquitectura Peer-To-Peer (P2P) puede dividirse en P2P no estructurado y estructurado (sobretodo Distributed Hash Tables o DHTs). Se utilizará el término nodo para referirse a lo que hasta ahora se ha llamado intermediarios (entidad que media entre el consumidor y el proveedor de servicios) o servidores. Adriana Iamnitchi e Ian Foster [20] sugieren una arquitectura distribuida P2P no estructurada para entornos de Grid. Sin embargo, este tipo de P2P no garantiza que un dato buscado y presente en el sistema se encuentre, incluso aunque el sistema carezca de fallos, ya que las búsquedas pueden no consultar el nodo que tiene el dato buscado. En P2P estructurado basado en DHTs cada nodo mantiene información de enrutado de O(log N) nodos, donde N es el total de nodos presentes en la overlay. Los datos y los nodos se mapean en la overlay dependiendo de un identificador. A cada nodo se le asigna la responsabilidad de gestionar una fracción del total de datos. Cuando un nodo de la overlay recibe una petición de búsqueda, las DHTs (en general) son capaces de encontrar un dato presente en la overlay en un número limitado, O(log N), de saltos entre nodos. 2.2.4 TeraGrid TeraGrid se inició en 2001 como encargo de la National Science Foundation (NSF) [21]. NSF es una agencia de gobierno de U.S.A que apoya la investigación y la educación en todos los campos no médicos de la ciencia y de la ingeniería. El encargo consistía en crear un centro de investigación único Teraflop/s, the Distributed Terascale Facility o DTF [22]. DFT estaría constituido por cuatro nodos, una arquitectura del sistema común, una red de ancho de banda amplia y por aplicaciones de software distribuidas. El proyecto finalizó en 2011, como un entorno de Grid que combinaba 11 asociaciones. En la actualidad, el proyecto continúa como Extreme Science and Engineering Digital Environment (XSEDE) [23]. TeraGrid fue coordinado a través del Grid Infrastructure Group (GIG), de la Universidad de Chicago, que trabajaba junto con asociaciones de U.S.A que proveían servicios al entorno de Grid. Los usuarios de TeraGrid provienen principalmente de universidades de U.S.A, llegando a ser unos 4.000 usuarios de más de 200 universidades diferentes. TeraGrid integra computadores de altas prestaciones, recursos de datos, herramientas e instalaciones experimentales. En total, TeraGrid dispone de más de un petaflop de capacidad computacional y de más de 30 petabytes de datos, accesibles vía redes de altas prestaciones. Los usuarios también pueden acceder a más de 100 bases de datos específicas por áreas. El proyecto TeraGrid implementó un servicio de descubrimiento de servicios llamado Integrated Information Service (IIS) para cubrir sus necesidades de localización de servicios [24]. La arquitectura de IIS tiene dos componentes, uno local y otro global. Cada proveedor de servicios que pertenece al entorno de Grid trabaja con un servicio de información local donde publica los servicios que ofrece. Un servicio de información global indexa, agrega y republica la información obtenida de los servicios de información local. 13 El servicio de información global es tolerante a fallos utilizando técnicas de replicación, y por tanto, replicando el servicio de información global en varios servidores simultáneamente ubicados en distintos lugares. La figura 4 muestra la arquitectura de IIS. En la izquierda hay múltiples servicios de información local, cada uno de los cuales publica su contenido en los servidores del servicio de información global. Todos los servicios de información global son redundantes. En la derecha están los clientes, cada uno de los cuales accede al servicio de información global utilizando un servicio de nombres dinámico (info.teragrid.org) que, de forma transparente, direcciona a los clientes a uno de los servidores de información global. Utilizando el servidor de nombres dinámico del dominio “dyn.teragrid.org”, IIS puede direccionar el nombre info.teragrid.org de un servidor de servicios de información global a otro en unos 15 minutos (el tiempo necesario para actualizar todas las cachés en Internet). OSGCC 2008 Globus Primer: An Introduction to Globus Software 63 … info.dyn.teragrid.org info.teragrid.org TeraGrid Dynamic DNS Dynamically direct clients to one or more servers Set by Information Services administrators Changes propagate globally fast (TTL = 15 minutes) Clients Dynamically Changes Doesn’t Change RP/partner services TG wide servers (Patrick Dorn & NCSA NetEng) Figura 4: Arquitectura de IIS2. 2 Fuente:(Presentation slides) http://www.mcs.anl.gov/~liming/primer/ 14 2.2.5 Uniform Interface to Computing Resources Uniform Interface to Computing Resources [25] (UNICORE) ofrece software de cliente y de servidor para Grid. UNICORE es un middleware de código abierto bajo licencia BSD. La arquitectura de UNICORE 6 se compone de tres capas, una capa cliente, una capa de servicios y una capa de sistema. La figura 5 muestra un ejemplo de arquitectura de UNICORE 6 con dos nodos y todos los servicios centrales agrupados bajo un gateway. El gateway actúa como punto de entrada a un nodo UNICORE y se encarga de la autentificación de todos los mensajes que lleguen. En la capa de servicios, para operar como una infraestructura distribuida UNICORE, es necesario un servicio global de registro, donde los diferentes servicios, una vez puestos en marcha, se registran. Este servicio de registro es contactado por los clientes para localizar servicios. Por tanto, el servicio de registro es el servicio central de un Grid UNICORE 6. El resto de componentes mostrados en la figura 5 están relacionados con servicios distintos del servicio de descubrimiento. Figura 5: Arquitectura de UNICORE 63 3 Fuente: http://www.unicore.eu/unicore/architecture.php 15 2.2.6 Advanced Resource Connector Advanced Resource Connector (ARC) [26] es un middleware de código abierto usado en varias infraestructuras Grid, como el multidisciplinario Nordic Data Grid [27], el Estonian Grid [28], Swegrid [29] y otros. The NorduGrid Collaboration [30] coordina el desarrollo de ARC. Esta colaboración fue originalmente establecida por varias instituciones académicas nórdicas y por centros de investigación, pero estuvo siempre abierta a la incorporación de nuevos miembros. El nuevo contrato de colaboración, firmado en 2011, tiene 11 colaboradores de 10 países. ARC define el Grid como un conjunto de recursos que se registran en un sistema de información común. El sistema de información común sirve como eje central del Grid y consiste en tres componentes: Local Information Services (LIS), Index Services (IS) y Registration Processes (RP). Los Local Information Services son responsables de la descripción y caracterización de recursos. Los Index Services se utilizan para mantener listas dinámicas de recursos disponibles, conteniendo la información de contacto de los proveedores de los recursos. Un proveedor de recursos puede ser un LIS u otro IS. El contenido del Index Service es publicado por los proveedores vía el Registration Process y es periódicamente borrado por el Index Service. De esta forma se mantiene una lista dinámica de proveedores y recursos disponibles. Los Index Services son básicamente listas planas de URLs de contacto de otros IS y LIS. Los Local Information Services y los Index Services de ARC están organizados en una jerarquía en árbol mutinivel que utiliza el Registration Process. Los LIS representan el nivel más bajo de la jerarquía en árbol. Los recursos se registran en el primer nivel de Index Services, que se registra en el segundo nivel de Index Services, y así sucesivamente. El registro finaliza en el Top Level Indice, que representa el root del árbol jerárquico. Para evitar que el sistema tenga un único punto de fallo, ARC sugiere un árbol con múltiples roots. 2.2.7 Resource Selection Service Resource Selection Service (ReSS) [31] es una infraestructura para seleccionar recursos en los que se van a ejecutar trabajos. El sistema ReSS se ha implementado en dos importantes infraestructuras Grid: Open Science Grid (OSG) [32] y FermiGrid [33], el Grid del campus de Fermilab. OSG es un consorcio de laboratorios nacionales y universidades de U.S.A que proporciona un Grid para satisfacer las necesidades computacionales de comunidades científicas. OSG pone a disposición de sus colaboradores cientos de recursos computacionales y de datos. El sistema ReSS está compuesto por dos componentes: un proveedor de información desplegado en los recursos y un repositorio de información central donde buscar recursos. ReSS publica la información de los recursos en el repositorio de información central. 2.3 Hipercubo La tesis presentada propone un servicio de descubrimiento con una arquitectura descentralizada que permite la búsqueda de servicios distribuidos. Se basa en una overlay con topología hipercubo. Sobre la overlay se propone un algoritmo que localiza eficientemente servicios en presencia de fallos antes de que los algoritmos de recuperación ante fallos actúen y reconfiguren la overlay, es decir, se proponen algoritmos con elevada flexibilidad estática. 16 Para obtener en el servicio de descubrimiento elevada flexibilidad estática es necesario escoger una topología adecuada y las propiedades del hipercubo [34] la convierten en una buena candidata. Esta afirmación se constata, por ejemplo, en [5] para sistemas basados en DHTs que utilizan algoritmos de enrutamiento. En dicho trabajo además, se evalúa la flexibilidad estática de algoritmos de enrutamiento muy conocidos que aprovechan las propiedades de la topología sobre la que se ejecutan. Las topologías evaluadas son árbol, hipercubo, butterfly, anillo y una topología híbrida que combina árbol y anillo. Los resultados obtenidos muestran que el enrutamiento en el hipercubo tiene la mejor flexibilidad estática cuando el porcentaje de nodos no-vivos es no mayor que el 30% del total de nodos presentes en la overlay (por ejemplo, un Grid). Los algoritmos propuestos en esta tesis no utilizan enrutado pero utilizan caminos alternativos que evitan los nodos en fallo aprovechando las propiedades de la topología en hipercubo tal y como hace el algoritmo de enrutamiento en el hipercubo. En el área de multiprocesadores se han propuesto múltiples algoritmos en los que los procesadores se interconectan en hipercubo. De estos algoritmos los que tienen más afinidad con el presentado en esta tesis son los algoritmos denominados de broadcast en presencia de fallos. Un algoritmo de este tipo intenta enviar el mismo mensaje al máximo número de procesadores teniendo en cuenta que esos procesadores pueden estar en fallo. Algunos de esos algoritmos para hipercubo en multiprocesadores proponen algoritmos en los que es necesario conocer información global. Por ejemplo, en [35] se necesita conocer el número total de procesadores en fallo. Este tipo de algoritmos no se pueden aplicar a sistemas distribuidos de gran escala ya que en un sistema distribuido no se conoce a priori información global del sistema como es el número total de fallos. Otros de esos algoritmos para hipercubo en multiprocesadores envían múltiples copias del mismo mensaje a cada procesador usando caminos diferentes [36] [37] [38]. Este tipo de algoritmos aplicados a sistemas distribuidos de gran escala generan elevado overhead, ya que al enviar múltiples copias para aumentar la probabilidad de que se reciba el mensaje se consume un alto ancho de banda. En cualquier caso las interconexiones del hipercubo sobre el que se ejecuta el algoritmo propuesto en esta tesis son interconexiones lógicas, lo que nos permite generar interconexiones nuevas si el algoritmo lo requiere como hace el Algoritmo-taux. Esto no es posible en un multiprocesador ya que las redes de interconexión son físicas y por tanto no se pueden modificar. En los últimos años el hipercubo se está proponiendo en sistemas distribuidos como en SCAFFOLD [39], HyperCUP [40], Edutella [41], HyperD y en el sistema propuesto por HaoRen et al. Con respecto a las arquitecturas de los anteriores sistemas distribuidos la arquitectura de la presente propuesta añade información parcial de fallos del sistema. Esta información permitirá que la búsqueda en sistemas distribuidos de gran escala (de órdenes de magnitud de cientos, millares y millones) se adapte a los fallos que se producen irremediablemente en el sistema. SCAFFOLD utiliza el hipercubo como estructura para guardar datos en un nodo pero no especifica algoritmo alguno de búsqueda entre los nodos que guardan estos datos. HyperCUP, Edutella y HyperD utilizan una overlay con topología en hipercubo y el algoritmo de búsqueda entre los nodos que forman un hipercubo es el mismo. 23 New A node that wants to join the hypercube will send a beacon message announcing its presence 110 010 000 001 011 110 010 000 001 011 New The HRoot receives the beacon and responds with a ping, containing the new logical address 110 010 000 001 011 111 The joining node takes on the logical address given to it and adds “110” as its neighbor 110 010 000 001 011 111 The new node is now the new HRoot, and so it will beacon 110 010 000 001 011 111 Upon receiving the beacon, some nodes realize that they have a new neighbor and ping in response ping 110 010 000 001 011 111 The new node responds to a ping from each new neighbor ping ping a) b) d) f) c) e) Figura 9: HyperCast - un nodo se incorpora5 5 Fuente: (Talk on Hypercube Protocol, 2000) http://www.comm.utoronto.ca/hypercast/papers.html 24 110 010 000 001 011 111 A node may fail unexpectedly 110 010 000 011 111 ! !Holes in the hypercube fabric are discovered via lack of response to pings ping ping ping ping ping ping ping ping ping 110 010 000 011 111 The HRoot and nodes which are missing neighbors send beacons 110 010 000 011 111 Nodes which are missing neighbors can move the HRoot to a new (lower) logical address with a ping message ping (as 001) 110 010 000 011 111 The HRoot sends leave messages as it leaves the 111 logical address leave leave 110 010 000 011 001 The HRoot takes on the new logical address and pings back 110 010 000 011 001 The “old” 111 is now node 001, and takes its place in the cube 110 010 000 001 011 The new HRoot and the nodes which are missing neighbors will beacon 110 010 000 001 011 Upon receiving the beacons, the neighboring nodes ping each other to finish the repair operation ping ping Figura 10: HyperCast - uno nodo falla6 6 Fuente: (Talk on Hypercube Protocol, 2000) http://www.comm.utoronto.ca/hypercast/papers.html 25 El trabajo que detalla el protocolo de HyperCast centra sus experimentos en determinar si el protocolo es escalable para un gran número de nodos. Dado que no les fue posible simular millones de nodos los experimentos simularon miles de nodos y se asumió que si los datos obtenidos para miles de nodos mostraban que HyperCast era escalable, era razonable asumir que sería escalable también para un número mayor de nodos. Las medidas analizadas fueron el número de paquetes transmitidos, el número de bytes transmitidos y el tiempo necesario para devolver al hipercubo a un estado estable. Estas medidas analizan dos comportamientos del protocolo. Primero, el tráfico de control transmitido debe ser escalable con el tamaño del grupo multicast que forma el hipercubo. Si el control de tráfico se incrementa linealmente con el tamaño del grupo, entonces el protocolo no sería capaz de soportar un gran número de nodos. Segundo, se quería mostrar que el tiempo necesario para devolver al hipercubo a un estado estable no es dependiente del tamaño del hipercubo. Este tiempo muestra cómo de rápido el protocolo de HyperCast puede incorporar cambios dinámicos en el hipercubo. Se diseñaron tres experimentos sobre el testbed descrito anteriormente para evaluar con respecto al tamaño del hipercubo el efecto del número de nodos que se unen al hipercubo, el efecto del número de nodos que fallan inesperadamente y el efecto de la pérdida de paquetes. En el experimento del efecto del número de nodos que se unen al hipercubo con respecto al tamaño del hipercubo se concluyó que HyperCast es escalable. En el experimento del efecto de nodos que fallan inesperadamente con respecto al tamaño del hipercubo se concluyó que a medida que el número de nodos aumenta el tiempo necesario para reparar un nodo en fallo no aumenta. Esto permitía mostrar que el protocolo de HyperCast escala bien para hipercubos con un elevado número de nodos. En el experimento del efecto de la pérdida de paquetes con respecto al tamaño del hipercubo se vio que el tráfico multicast crecía rápidamente a medida que aumentaba la pérdida de paquetes. La solución propuesta a esta problemática fue que era necesario ajustar el valor de ttimeout en función de la pérdida de paquetes. Recordemos que ttimeout es el tiempo máximo que espera un nodo las respuestas a los mensajes ping de sus vecinos y que pasado ese tiempo sin obtener respuesta de un nodo vecino empieza a enviar periódicamente mensajes tipo beacon para indicar que ha detectado un vecino en fallo. 3.2.2 Propuesta de HaoRen et al. En la propuesta de HaoRen et al. se obtiene el identificador lógico de un nodo siguiendo un código Gray como en HyperCast. En la tabla 1 (ya presentada anteriormente) se muestra el orden de los identificadores siguiendo un código binario y siguiendo un código Gray. En esta propuesta se describe cuando un nodo se incorpora y cuando un nodo sale, considerando en este último caso que la overlay ya no va a contener más a ese nodo. Cuando un nodo sale, ese nodo se convierte en un espacio libre (free space) y otro nodo presente en el hipercubo asume su lugar. El nodo que asume su lugar es el nodo vecino en la dimensión más pequeña que tiene el nodo. Como los autores, para hacer referencia a la dimensión más pequeña que tiene un nodo se utilizará el término Lmin. En la figura 11 se muestra un ejemplo 26 en un hipercubo 3-dimensional formado por 6 nodos (figura 11.a) donde el nodo G(i=3)=010 (Lmin=0) sale del hipercubo (figura11.b). Así el nodo que asume el lugar de G(i=3)=010 es G(i=2)=011. a) b) 001 011 000 010 111 110 Dim. 1 Dim. 0 Dim. 2 001 011 000 free space 111 110 Figura 11: HaoRen et al. – un nodo sale. Cuando un nodo se incorpora si hay espacios libres en el hipercubo, el nodo que se incorpora es el nodo con valor i menor siguiendo el orden de códigos de Gray. En caso contrario, el nodo que se incorpora es el nodo con identificador siguiente siguiendo el orden de códigos de Gray. Cabe notar que para aplicar la técnica que describen los autores en su propuesta es necesario que el nodo que se incorpora obtenga de alguna forma como mínimo cómo contactar con los nodos que han asumido el lugar de otro y el valor i mayor del hipercubo. Por ejemplo, en la figura 11 cómo contactar con el nodo G(i=2)=011 y que i=5. 3.2.3 HyperD A diferencia de la propuesta de HaoRen et al. y de HyperCast donde cada nodo de la overlay tiene asociado un único identificador lógico, en HyperD cada nodo de la overlay tiene asociada una dirección física y como mínimo un identificador lógico, pudiendo tener más de uno. Los identificadores lógicos son siempre los identificadores de un hipercubo n-dimensional completo, por lo que en HyperD se distingue entre hipercubo lleno (todos los nodos tienen un único identificador lógico) e hipercubo parcial (algún o algunos nodos tienen más de un identificador lógico), siendo el caso más habitual a medida que aumenta el número de nodos de la overlay el de tener un hipercubo parcial. En la figura 12 se muestra un ejemplo de un 1dimensional lleno HyperD (H1) con 2 nodos, de un 2-dimensional parcial HyperD (H2) con 3 nodos y de un 2-dimensional lleno con 4 nodos respectivamente. 27 0 1 10 11 00 01 H2 (3 nodes)H1 (2 nodes) 10 11 11 00 01 10 11 00 01 H2 (4 nodes) Figura 12: HyperD con 2, 3 y 4 nodos. En HyperD cada nodo almacena la dirección física y lo o los identificadores lógicos de cada uno de sus vecinos. Periódicamente se actualiza esta información contactando con sus vecinos. Cuando un nodo presente en HyperD deja de formar parte de HyperD, bien porque así lo anuncia o porque falla, el nodo aún presente en HyperD que tiene el identificador lógico adyacente al identificador lógico mayor (en decimal) del nodo que deja de formar parte de HyperD añade a sus identificadores lógicos los identificadores lógicos del nodo que ya no forma parte de HyperD. En la figura 13 se ilustra el proceso que se sigue cuando un nodo deja de formar parte de HyperD. El nodo que deja de formar parte de HyperD es el nodo con los identificadores lógicos 011 y 111 (figura 13.a), por tanto, el identificador lógico mayor de ese nodo es 111. Así, el nodo con identificador lógico adyacente a 111 (nodo con identificador 110) pasa a tener los identificadores lógicos que tenía y los nuevos (011 y 111) (figura 13.b) Dim. 1 Dim. 0 Dim. 2 a) b) 001 101 011 111 000 010 100 110 001 101 000 010 100 110 011 111 Figura 13: HyperD – un nodo deja de formar parte. Cuando un nuevo nodo se incorpora contacta con un nodo presente en HyperD y se inicia un procedimiento de asignación de identificador/es lógico/s del hipercubo n-dimensional completo que forma HyperD para el nuevo nodo. Si el hipercubo es un hipercubo n-dimensional lleno todos los nodos doblan sus identificadores lógicos, pasando el hipercubo a ser un hipercubo (n+1)-dimensional y el nuevo nodo toma el identificador lógico de valor i mayor siguiendo el orden del código de Gray, conectándose además con todos los vecinos del nodo con identificador lógico G(i=0) siguiendo el orden del código de Gray. Si el hipercubo es un hipercubo n- 28 dimensional parcial el nuevo nodo toma algún/os identificadores lógicos de otro nodo ya presente en el hipercubo, dejando ese nodo ya presente de tener esos identificadores. En la figura 14 se muestra el ejemplo de un 2-dimensional lleno (figura 14.a) que pasa a ser un hipercubo 3dimensional parcial (figura 14.b) y en la figura 15 se muestra un ejemplo de un 3-dimensional parcial con 5 nodos (figura 15.a) donde el nuevo nodo obtiene después del proceso de asignación los identificadores lógicos 011 y 111 (figura 15b) a) b) 01 11 00 10 Dim. 1 Dim. 0 Dim. 2 001 101 011 111 000 100 010 110 100 Figura 14: HyperD – un nodo se incorpora (hipercubo lleno). a) b) 001 101 000 010 100 110 011 111 Dim. 1 Dim. 0 Dim. 2 001 101 000 010 011 111 100 110 011 111 Figura 15: HyperD – un nodo se incorpora (hipercubo parcial). 3.3 Búsquedas en un hipercubo En este apartado se describen 2 algoritmos para búsquedas en un hipercubo que no pueden resolverse utilizando enrutamiento. Estas propuestas son propuestas de otros autores ya que la propuesta de esta tesis se presenta en un apartado del siguiente capítulo. 3.3.1 Búsqueda propuesta por HaoRen et al. Para un entorno de Grid, HaoRen et al. propone un algoritmo de transposición de los nodos basado en datos obtenidos a través de una búsqueda. La overlay puede ser un hipercubo ndimensional completo o incompleto. Los identificadores lógicos de los nodos van de G(0) a G(M- 29 1), donde M es el número de nodos del hipercubo y G(i) es el código de Gray de índice i (ver Tabla 1). Cada nodo del hipercubo tiene un único identificador lógico. Para representar la evolución de la búsqueda que realiza el algoritmo se utiliza una representación en árbol. Los nodos del árbol representan nodos del hipercubo. Cuando un nodo envía la búsqueda a uno de sus nodos vecinos lo indicamos con una flecha que va del nodo emisor al nodo receptor. El algoritmo se ejecuta en varios pasos, siendo el número de flechas que hay hasta el nodo inicial el número de pasos en el que el nodo es accedido. La figura 16 muestra un ejemplo de búsqueda desde el nodo 010 (nodo inicial) en un hipercubo 3-dimensional completo. Como podemos ver, no todos los nodos deben propagar la petición a todos sus vecinos. De hecho, el nodo inicial es el único nodo que propaga la petición a todos sus vecinos. Para el resto de nodos que no propagan a todos sus vecinos, si el nodo recibe la petición por su vecino en dimensión i solo envía la petición a sus vecinos en dimensiones mayores que la dimensión i. 010 011 000 110 001 111 100 101 0 1 2 1 2 2 2 000 001 010 100 011 101 110 111 start node start node Figura 16: HaoRen et al. - ejemplo de búsqueda (hipercubo completo). La figura 17 muestra un ejemplo de búsqueda en un hipercubo 3-dimensional incompleto desde el nodo 010 (figura 17.a) (nodo inicial) y desde el nodo 101 (figura 17.b) (nodo inicial). Como podemos ver, no todos los nodos deben propagar la petición a todos sus vecinos. De hecho, si el nodo inicial tiene vecino en la dimensión 0 (como en la figura 17.a), el nodo inicial es el único nodo que propaga la petición a todos sus vecinos y si el nodo inicial no tiene vecino en la dimensión 0 (como en la figura 17.b) es un nodo vecino del nodo inicial el que propaga la petición a todos sus vecinos. Para el resto de nodos que no propagan a todos sus vecinos, si el nodo recibe la petición por su vecino en dimensión i solo envía la petición a sus vecinos en dimensiones mayores que la dimensión i. 30 010 011 000 110 001 111 0 1 2 1 2 000 001 010 011 110 111 start node start node a) 101 001 010 111 000 011 2 1 2 0 1 000 001 010 011 101 110 111 start node start node b) broadcast 110 2 broadcast Figura 17: HaoRen et al. - ejemplo de búsqueda (hipercubo incompleto). 3.3.2 Búsqueda en HyperD En HyperD la overlay siempre es un hipercubo n-dimensional completo que puede ser lleno (cuando todos los nodos tienen un único identificador lógico) o parcial (si algún nodo tiene más de un identificador lógico). Para representar la evolución de la búsqueda que realiza el algoritmo se utiliza una representación en árbol. Los nodos del árbol representan nodos del hipercubo. Cuando un nodo envía la búsqueda a uno de sus nodos vecinos lo indicamos con una flecha que va del nodo emisor al nodo receptor. El algoritmo se ejecuta en varios pasos, siendo el número de flechas que hay hasta el nodo inicial el número de pasos en el que el nodo es accedido. La figura 18 muestra un ejemplo de búsqueda desde el nodo inicial marcado como (3) cuyos identificadores lógicos son 0010 y 1010 en un hipercubo 4-dimensional parcial. Como podemos ver, no todos los nodos deben propagar la petición a todos sus vecinos. De hecho, el nodo inicial es el único nodo que propaga la petición a todos sus vecinos. Para el resto de nodos que no propagan a todos sus vecinos, si el nodo recibe la petición por su vecino en dimensión i solo envía la petición a sus vecinos en dimensiones mayores que la dimensión i. 31 0010 1010 0110 1110 0000 1000 0011 1011 1111 0100 1100 1101 0101 HyperD (H4 -10 nodes) dim0 dim2 dim3 dim1 START NODE (7) (0) (12) (8) (6) (10) 0111 (9) 1001 (11) 0001 (1) VN xxxx virtual node (non-existent) (3) (6) (7) (9) (0) (1) (12) (8) VN (3) VN (6) VN (7) (10) VN (0) (11) VN (12) VN (12) (3) START NODE xxxx node 2 1 0 2 2 1 33 3 2 Figura 18: HyperD - ejemplo de búsqueda. 39 El Algoritmo-va se basa en la misma idea base que el Algoritmo-vd mostrada de nuevo en la figura 22.a y 22.b pero además añade una nueva idea ilustrada por la figura 22.c. Las figuras 22.a y 22.b han sido explicadas en el apartado 3.3.3.1.1. En la figura 22.c se muestra un ejemplo donde el nodo inicial tiene dos vecinos no-vivos: el vecino en la dimensión 1 (010) y el vecino en la dimensión 2 (100). Dada esta situación, el Algoritmo-va consulta al nodo 110 a través del nodo 111 en el cuarto paso. Cabe notar que el nodo 110 no es consultado en el segundo paso ya que el nodo 010 es un nodo no-vivo. 000 001 010 100 011 101 110 111 0 1 2 1 2 2 2 000 001 010 100 011 101 110 111 start node start node 000 001 100 010 101 011 110 111 0 2 1 2 1 1 1 start node 000 001 010 100 011 101 110 111 start node a) b) Vd={0,1,2) Vd={0,2,1) 000 001 010 100 011 101 110 111 0 1 2 1 2 2 2 000 001 010 100 011 101 110 111 start node start node c) Vd={0,1,2) 110 Va={0) 0 Figura 22: Representación en árbol del Algoritmo-va. En el Algoritmo-va cada nodo trabaja con dos vectores, llamados vd y va, Estos vectores son establecidos por el nodo padre de la propagación. La lista vd se reordena como en el Algoritmo-vd para reducir el efecto de los nodos no-vivos en la propagación de la petición de recursos del cliente en el hipercubo. La lista va se utiliza para consultar nodos hijos de vecinos no-vivos utilizando un camino alternativo. Este nuevo camino utiliza sólo nodos del hipercubo no consultados antes. Así los nodos son consultados como máximo una vez y no se requieren mensajes adicionales. 4.2.2.2 Algoritmo-va: un ejemplo completo Este apartado presenta un ejemplo de búsqueda de recursos utilizando el Algoritmo-va. La figura 23 muestra la overlay en hipercubo y la representación en árbol del proceso de búsqueda. 40 La overlay en este caso está formada por un hipercubo 4-dimensional incompleto que contiene 12 nodos. Los nodos grises representan nodos vivos, los nodos rayados representan nodos existentes que se encuentran en estado no-vivo y los nodos blancos con línea discontinua representan nodos que no existen en el sistema porque el hipercubo es incompleto y por tanto no contiene todos los nodos. El algoritmo propuesto no distingue entre nodos no-vivos y nodos no-presentes en el hipercubo, por lo que ambos tipos de nodos se marcan como nodos no-vivos. 0000 0100 1000 dim2 vd={3,0,1}-> vd={0,1,3} va={} dim3 vd={0,1} va={3} NONALIVE 0001 dim0 vd={1} va={} NONALIVE 0010 dim1 vd={} va={} 0011 dim1 vd={} va={} 1010 dim1 vd={} va={3} 1001 dim0 vd={1} va={3} NONALIVE 1100 dim3 vd={} va={} 0110 dim1 vd={3} va={} 0101 dim0 vd={1,3} va={} NONALIVE 1101 dim3 vd={} va={} 0111 dim1 vd={3} va={} NONALIVE 1111 dim3 vd={} va={} NONALIVE 1110 dim3 vd={} va={} 1011 dim1 vd={} va={3} nonalive 0010 0011 0110 0111 0000 nonalive 0001 0100 0101 1010 1011 nonalive 1110 nonalive 1111 1000 1001 nonalive 1100 nonalive 1101 0011 dim3 vd={} va={} NONALIVE 0010 dim3 vd={} va={} NONALIVE 0001 dim3 vd={} va={} xxxx xxxx NONALIVE xxxx reached node alive node not reached non-alive node (existent) START NODE 1st STEP 2nd STEP 3rd STEP 4th STEP NONALIVE xxxx non-alive node (non-existent) dim0 dim2 dim3 dim1 vd={0,1,2,3} -> vd={2,3,0,1} Figura 23: Ejemplo del Algoritmo-va en un hipercubo 4-dimensional incompleto. Una petición de servicio o servicios P se inicia en el nodo 0000 de un hipercubo 4dimensional. En el primer paso de este ejemplo, el valor del vector vd en el nodo inicial es {0, 1, 2, 3} y después de que el nodo inicial chequee el estado de sus vecinos, el vector vd se reordena como {2, 3, 0, 1}. En este caso, 0 y 1 se colocan en las dos últimas posiciones de vd porque en el ejemplo asumimos que los nodos vecinos en las dimensiones 0 (0001) y 1 (0010) son nodos novivos. La petición se propagará a través de los nodos vivos del nodo inicial pero antes un nuevo vector vd se genera para cada uno de éstos nodos vecinos vivos. El nuevo vector vd se crea eliminado la dimensión usada en la propagación y aquellas dimensiones de las posiciones previas a la dimensión usada en la propagación. Por ejemplo, para el nodo vecino del nodo inicial (0000) en la dimensión 3 (1000) se genera el vector vd = {0, 1} ya que vd = {2, 3, 0, 1}. 41 El nodo inicial tiene dos vecinos no-vivos y por tanto uno de ellos tiene un hijo en el árbol de propagación (0011). Para consultar al nodo 0011 el algoritmo intenta encontrar un camino alternativo a través del último nodo vivo del vector; el vecino en la dimensión 3 (1000) en este caso. Por este motivo, la dimensión 3 se añade al vector va del nodo 1000 (inicialmente el vector va es un vector vacío). Los vectores generados para cada uno de los nodos vivos del nodo inicial, vd y va, se envían junto con la petición a cada uno de estos nodos (0100 y 1000) en el primer paso. En los siguientes pasos, cada nodo recibe la petición, vd y va de su nodo padre y realiza el mismo procedimiento que el nodo inicial, es decir, reordena vd y añade nuevas dimensiones a va dependiendo del estado de los vecinos a los que debe propagar la petición del cliente. En el ejemplo, el nodo 0100 recibe vd = {3, 0, 1} y reordena como vd = {0, 1, 3} ya que su vecino en la dimensión 3 (1100) es un nodo no-vivo. Cada nodo envía la petición a sus vecinos en las dimensiones de vd después de generar sus vectores vd y va. Además, si un nodo recibe un vector va no vacío, el nodo reenvía la petición a cada uno de sus vecinos en las dimensiones que indica va sólo si el vecino en esa dimensión no es su nodo padre. Recordemos que su nodo padre es el nodo que le ha enviado el mensaje de petición de recursos. En el ejemplo, el nodo 1000 recibe va = {3} de su vecino en la dimensión 3 y éste nodo es su nodo padre (0000). Cuando la propagación se realiza a vecinos en las dimensiones marcadas por va, la petición se envía junto con vectores vd y va vacíos ya que esos nodos no deben realizar ninguna propagación más. Las flechas en la figura 23 indican cómo se realiza la propagación de la petición a través del hipercubo y líneas (sin flecha) indican que la propagación no puede realizarse en esa dimensión. Las líneas con trazado continuo indican que esa propagación se realiza con la información del vector vd y la líneas con trazado discontinuo significan que esa propagación se realiza con la información del vector va. En cinco pasos todos los nodos vivos del ejemplo son consultados una única vez. Cabe notar que si el nodo 0001 no hubiera estado en estado no-vivo (nodo con relleno rayado), el nodo 0011 (nodo con relleno en blanco) se habría consultado en el segundo paso del algoritmo a través del vecino en la dimensión 1 del nodo 0001 utilizando el vector vd, pero el algoritmo es capaz de consultar a este nodo en el cuarto paso utilizando el vector va a través del vecino en la dimensión 3 del nodo 1011. 4.2.2.3 Algoritmo-va: procedimiento de búsqueda El procedimiento de búsqueda se inicia cuando un cliente conecta con uno de los nodos del sistema y solicita un recurso (o recursos). Si el nodo inicial contactado por el cliente no dispone del recurso solicitado inicia una búsqueda que propaga un mensaje de petición de recursos por el hipercubo. Un mensaje de petición de recursos se compone de la petición que realiza el cliente (message.request) y dos vectores (message.vd y message.va). Cada nodo del hipercubo es consultado una única vez. Si el nodo consultado dispone del recurso solicitado ese nodo ya no propaga la petición del cliente ya que se ha encontrado al menos un recurso que satisface la solicitud del cliente. Por el contrario, si el nodo consultado no dispone del recurso solicitado, al 42 no poder asegurar el nodo consultado si en el sistema ya se ha encontrado dicho recurso, el nodo consultado propaga la petición. La figura 24 muestra el diagrama de flujo que se ejecuta en un nodo del hipercubo cuando llega una petición de recurso. startNode ? vd=message.vd va=message.va vd={0,1,..,n-1} va={} vd, nNonAlive, dAlive = statusNeighbors(vd) nNonAlive > 1 ? va2=addToList(va,dAlive) true false for(j=0;j<va.size();j++) message.vd={} message.va={} sendToNeighbor(va[j],message) va[j] is not parent node ? true false true for(k=0;k<vd.size()-nNonAlive;k++) message.vd=createList(k,vd) message.va=va2message.va=va vd[k] == dAlive && nNonAlive > 1 ? truefalse sendToNeighbor(vd[k],message) satisfyRequest ? true satisfyRequest = processRequest(message.request) sendResult(this.node) false Figura 24: Diagrama de flujo del Algoritmo-va. Subrayados aparecen resaltados los cambios con respecto al diagrama de flujo del Algoritmo-vd. 1) Cuando un nodo recibe un mensaje de petición de recurso (o recursos) se ejecuta la función processRequest(message.request). Si la petición no puede ser satisfecha por el nodo el valor de satisfyRequest se establece a false. En otro caso, el valor de satisfyRequest se establece a true y la función sendResult(this.node) se ejecuta para informar al cliente de que la petición puede satisfacerse en este nodo. 2) Si satisfyRequest es false y el nodo que procesa la petición es el nodo inicial contactado por el cliente (startNode es true), el vector vd se inicializa como vd = {0, 1, …, n-1} (el conjunto de dimensiones del hipercubo) y va se inicializa como va = {} (un vector vacío). En otro caso (startNode is false) vd y va se inicializan respectivamente con los vectores recibidos en el mensaje de petición de recursos. 43 3) El nodo ejecuta la función statusNeighbors(vd) y reordena el vector vd de tal forma que las dimensiones correspondientes a los nodos vecinos no-vivos se colocan en las últimas posiciones del vector. Por ejemplo, si vd = {0, 1, 2, 3} y el vecino en la dimensión 1 es no-vivo entonces vd se reordena como {0, 2, 3, 1}. La función statusNeighbors(vd) también retorna dos valores enteros nNonAlive y dAlive. El valor entero de nNonAlive es el valor del número de nodos no-vivos del vector reordenado vd. El valor entero de dAlive contiene la dimensión del último vecino vivo almacenada en vd. Por ejemplo, si vd = {2, 1, 0, 3} y los vecinos del nodo en las dimensiones 0 y 3 son nodos no-vivos, nNonAlive = 2 y dAlive = 1. El valor de nNonAlive se utilizará para enviar mensajes de petición de recursos sólo a los nodos vecinos vivos de un nodo y el valor de dAlive se utilizará para consultar nodos que se consultarían si no hubiera nodos no-vivos en la overlay. 4) Si el número de vecinos no-vivos (nNonAlive) es mayor que uno, el nodo ejecuta la función addToList(va, dAlive). Esta función añade dAlive al final del vector va y retorna un nuevo vector (va2) que se utilizará, si es necesario, más adelante en lugar de va. 5) Para cada posición k en el vector vd que representa un nodo vecino vivo, se ejecuta la función createList(k, vd) que crea un nuevo vector compuesto de todas las dimensiones que se encuentran después de la posición k en el vector ordenado vd y se actualiza vd con este nuevo vector. En otras palabras, si el número de elementos en vd (vd.size()) es q la función retorna {vd[k+1], ..., vd[q-1]}. Por ejemplo, si vd = {0, 2, 3, 1} y k = 1, la llamada a createList(k, vd) devuelve {3, 1}. Para todos los nodos vecinos vivos, excepto para el último vecino vivo, el vector va toma el valor del vector va recibido en el mensaje de petición de recursos. Para el último nodo vecino vivo (vd[k] = dAlive) y si el número de nodos vecinos no vivos es mayor que 1, el vector va toma el valor del vector va2 generado en el paso anterior. La petición de recursos que realizó el cliente, el vector vd y el vector va se envían al nodo vecino correspondiente en la dimensión vd[k] a través de la función sendToNeigbor(vd[k], message). 6) Finalmente, el nodo también propaga la petición a cada uno de sus vecinos en las dimensiones marcadas por va ejecutando la función sendToNeigbor(va[j], message) sólo si el vecino en la dimensión va[j] no es su nodo padre. Recordamos que su nodo padre es el nodo que le ha enviado el mensaje de petición de recursos. Los vectoress vd y va, incluidos en este mensaje son vectores vacíos ya que los nodos que recibirán este mensaje de petición de recursos no propagan el mensaje a ninguno de sus nodos vecinos. 4.2.3 Algoritmo-taux Para presentar el algoritmo final que se propone en este documento primero se introduce la idea base del algoritmo, después se detalla un ejemplo completo del algoritmo y finalmente se presenta el diagrama de flujo. En los dos primeros sub-apartados se ha supuesto que ninguno de los nodos tiene el recurso o recursos solicitados para ilustrar mejor la propagación de la búsqueda en el hipercubo. Si algún nodo consultado tuviera el recurso solicitado ese nodo ya no propagaría 44 la petición del cliente. El nombre de Algoritmo-taux viene dado porque además de los vectores vd (vector de dimensiones) y va (vector añadido) que usa Algoritmo-va se utiliza también una tabla llamada taux (tabla auxiliar). 4.2.3.1 Algoritmo-taux: representación en árbol Como en los algoritmos anteriores, Algoritmo-vd y Algoritmo-va, una representación en árbol se utiliza para mostrar el proceso de búsqueda del Algoritmo-taux. Los nodos del árbol representan nodos del hipercubo. Cuando un nodo envía el mensaje de petición de recursos a uno de sus nodos vecinos se indica con una flecha que va del nodo emisor al nodo receptor. Cuando un nodo no puede ser accedido por encontrarse su nodo padre en estado no-vivo se indica con una línea discontinua. El algoritmo se ejecuta en varios pasos, siendo el número de flechas que hay hasta el nodo inicial el número de paso en el que el nodo es accedido. El Algoritmo-taux se basa en las ideas base de Algoritmo-vd (mostradas de nuevo en las figuras 25.a y 25.b) y de Algoritmo-va (mostrada de nuevo en la figura 25.c) pero además añade una nueva idea ilustrada por la figura 25.d. Las figuras 25.a y 25.b han sido explicadas en el apartado 3.3.3.1.1. La figura 25.c ha sido explicada en el apartado 3.3.3.2.1. En la figura 25.d se muestra un ejemplo donde el nodo inicial debe enviar el mensaje de petición de recursos a tres vecinos no-vivos: el vecino en la dimensión 0 (001), el vecino en la dimensión 1 (010) y el vecino en la dimensión 2 (100). Dada esta situación, el nodo inicial (000) envía el mensaje de petición al último nodo al que se accedería si sus vecinos no estuvieran no-vivos (111). En la figura puede verse cómo a través de este nodo (111) se consultan los mismos nodos que a través del nodo inicial (000). 45 000 001 010 100 011 101 110 111 0 1 2 1 2 2 2 000 001 010 100 011 101 110 111 start node start node 000 001 100 010 101 011 110 111 0 2 1 2 1 1 1 start node 000 001 010 100 011 101 110 111 start node a) b) Vd={0,1,2) Vd={0,2,1) 000 001 010 100 011 101 110 111 0 1 2 1 2 2 2 000 001 010 100 011 101 110 111 start node start node c) Vd={0,1,2) 110 Va={0) 0 000 001 010 100 011 101 110 111 0 1 2 1 2 2 2 Vd={0,1,2) 111 110 101 011 100 010 001 000 0 1 2 1 2 2 2 Vd={0,1,2) Reached Before 000 001 010 100 011 101 110 111 start node start node d) Figura 25: Representación en árbol del Algoritmo-taux. En el Algoritmo-taux cada nodo además de la tabla de vecinos dispone de una tabla llamada taux que contiene información de nodos que no son vecinos. La forma en que se rellena taux se mostrará más adelante. El Algoritmo-taux trabaja con tres vectores, llamados vd, va y wl. Los vectores vd y va funcionan como en el Algoritmo-va. El vector wl se utiliza para rellenar las tablas taux que tienen los nodos y en los siguientes sub-apartados se muestra cómo se usa. Los vectores son establecidos por el nodo padre. El vector vd se reordena como en el Algoritmo-vd para reducir el efecto de los nodos no-vivos en la propagación del mensaje de petición de recursos del cliente en el hipercubo. El vector va se utiliza como en el Algoritmo-va para consultar nodos utilizando un camino alternativo. La tabla taux se utiliza sólo cuando todos los nodos vecinos por los que se debe propagar el mensaje están en estado no-vivo. Este nuevo camino utiliza sólo nodos del hipercubo no consultados antes. Así los nodos son consultados como máximo una vez. 4.2.3.2 Algoritmo-taux: un ejemplo completo Este apartado presenta un ejemplo de búsqueda de recursos utilizando el Algoritmo-taux. La figura 26 muestra la overlay en hipercubo, la representación en árbol del proceso de búsqueda y 46 cómo se añade la información de un nodo a una tabla taux. La overlay en este caso está formada por un hipercubo 4-dimensional incompleto que contiene 12 nodos. Los nodos grises representan nodos vivos consultados, los nodos rayados representan nodos existentes que se encuentran en estado no-vivo y los nodos blancos con línea discontinua representan nodos que no existen en el sistema porque el hipercubo es incompleto y por tanto no contiene todos los nodos. El algoritmo propuesto no distingue entre nodos no-vivos y nodos que no existen en el hipercubo, por lo que ambos tipos de nodos se marcan como nodos no-vivos. 0000 0100 1000 dim2 vd={3,0,1}-> vd={0,1,3} va={} wl={} dim3 vd={0,1} va={3} wl={loc(0000), 0011} NONALIVE 0001 dim0 vd={1} va={} wl={} NONALIVE 0010 dim1 vd={} va={} wl={} 0011 dim1 vd={} va={} wl={} 1010 dim1 vd={} va={3} wl={loc(0000), 0011} 1001 dim0 vd={1} va={3} wl={loc(0000), 0011} NONALIVE 1100 dim3 vd={} va={} wl={} 0110 dim1 vd={3} va={} wl={} 0101 dim0 vd={1,3} va={} wl={} NONALIVE 1101 dim3 vd={} va={} wl={} 0111 dim1 vd={3} va={} wl={} NONALIVE 1111 dim3 vd={} va={} wl={} NONALIVE 1110 dim3 vd={} va={} wl={} 1011 dim1 vd={} va={3} wl={loc(0000), 0011} nonalive 0010 0011 0110 0111 0000 nonalive 0001 0100 0101 HOverlay (H4 -12 nodes) 1010 1011 nonalive 1110 nonalive 1111 1000 1001 nonalive 1100 nonalive 1101 0011 dim3 vd={} va={} wl={loc(0000), 0011} NONALIVE 0010 dim3 vd={} va={} wl={loc(0000), 0011} NONALIVE 0001 dim3 vd={} va={} wl={loc(0000), 0011} xxxx xxxx NONALIVE xxxx reached node alive node not reached non-alive node (existent) START NODE 1st STEP 2nd STEP 3rd STEP 4th STEP NONALIVE xxxx non-alive node (non-existent) dim0 dim2 dim3 dim1 vd={0,1,2,3} -> vd={2,3,0,1} va={} wl={} messageUpdate Figura 26: Ejemplo del Algoritmo-taux en un hipercubo 4-dimensional incompleto. Una petición de recurso o recursos P se inicia en el nodo 0000 de un hipercubo 4dimensional. En el primer paso de este ejemplo, el valor del vector vd en el nodo inicial es {0, 1, 2, 3} y después de que el nodo inicial chequee el estado de sus vecinos, el vector vd se reordena como {2, 3, 0, 1}. En este caso, 0 y 1 se colocan en las dos últimas posiciones de vd porque en el ejemplo asumimos que los nodos vecinos en las dimensiones 0 (0001) y 1 (0010) son nodos novivos. La petición se propaga a través de los nodos vivos del nodo inicial pero antes un vector vd se genera para cada uno de éstos nodos vecinos vivos. Estos vectores vd se crean eliminado la dimensión usada en la propagación y aquellas dimensiones de las posiciones previas a la 47 dimensión usada en la propagación. Por ejemplo, para el nodo vecino del nodo inicial (0000) en la dimensión 3 (1000) se genera la lista vd = {0, 1} ya que vd = {2, 3, 0, 1}. El nodo inicial tiene dos vecinos no-vivos y por tanto uno de ellos tiene un hijo en el árbol de propagación (0011). Para consultar al nodo 0011 el algoritmo intenta encontrar un camino alternativo a través del último nodo vivo del vector; el vecino en la dimensión 3 (1000) en este caso. Por este motivo, la dimensión 3 se añade al vector va del nodo 1000 (inicialmente va es un vector vacío). Como el nodo inicial tiene dos vecinos no-vivos, la información de un nodo debería añadirse a la tabla taux del nodo inicial (si es posible). Por este motivo, el nodo inicial calcula cuál es el último nodo en el árbol de propagación al que se accede a través de va (0011) y añade al vector wl del nodo 1000 su localización y el identificador calculado (wl = {loc(0000), 0011}). La localización del nodo 0000 (loc(0000)) es una IP y un puerto donde el nodo está escuchando mensajes que le pueden llegar. Inicialmente el vector wl es un vector vacío. Los vectores generados para cada uno de los nodos vivos del nodo inicial, vd, va y wl se envían junto con la petición a cada uno de estos nodos (0100 y 1000) en el primer paso. Los valores wl = {loc(0000), 0011} hacen que si el mensaje de petición de recursos llega hasta el nodo 0011, éste nodo envíe su localización al nodo 0000, a través de un mensaje que en la figura 26 se llama messageUpdate. Cuando el nodo 0000 reciba este mensaje añadirá la localización del nodo 0011 en su tabla taux. Así una tabla taux de un nodo contiene el identificador de un nodo del hipercubo que no es vecino suyo y cómo contactar con ese nodo (la IP del nodo con ese identificador y un puerto donde está escuchando). Las flechas en la figura 26 indican cómo se realiza la propagación de la petición a través del hipercubo y líneas (sin flecha) indican que la propagación no puede realizarse en esa dimensión. Las líneas con trazado continuo indican que esa propagación se realiza con la información del vector vd y la líneas con trazado discontinuo significan que esa propagación se realiza con la información del vector va. Como ya hemos dicho anteriormente la tabla taux sólo se utiliza cuando todos los vecinos por los que hay que propagar están en estado no-vivo. Así, Algoritmo-taux permite continuar la búsqueda cuando el hipercubo se segmenta. Cabe notar que cuando esta situación se produce en los primeros pasos de la búsqueda, gran parte del hipercubo no es consultado si se usan los algoritmos previos a Algoritmo-taux. Como ejemplo de uso de la tabla taux, la figura 27 muestra el caso de mensaje de una petición de recursos iniciada en el nodo 1000, que llega al nodo 0000 y que debe propagarse a través de tres vecinos no-vivos en un hipercubo 4-dimensional. 48 0000 0111 NONALIVE 0001 vd={0,1,2}-> vd={1,2,0} va={} wl={} dim0 vd={1,2} va={} wl={} NONALIVE 0010 dim1 vd={2} va={} wl={} NONALIVE 0100 dim2 vd={} va={} wl={} NONALIVE 0110 dim2 vd={} va={} wl={} 0101 dim2 vd={} va={} wl={} 0011 dim1 vd={2} va={} wl={} NONALIVE 0110 dim0 vd={} va={} wl={} 0011 dim2 vd={0} va={} wl={} 0101 dim1 vd={2,0} va={} wl={} NONALIVE 0100 dim0 vd={} va={} wl={} NONALIVE 0001 dim2 vd={0} va={} wl={} NONALIVE 0000 dim0 vd={} va={} wl={} NONALIVE 0010 dim0 vd={} va={} wl={} 0111 dim2 vd={} va={} wl={} nonalive 0010 0011 nonalive 0110 0111 0000 nonalive 0001 nonalive 0100 0101 HOverlay (H4) xxxx xxxx NONALIVE xxxx reached node alive node not reached non-alive node (existent) 3rd STEP 4th STEP 5th STEP dim0 dim2 dim3 dim1 dim3 vd={0,1,2} -> vd={0,1,2} va={} wl={} 1st STEP never will be reached because the previous nodes are non-alive nonalive 0010 0011 nonalive 0110 0111 0000 nonalive 0001 nonalive 0100 0101 2nd STEP 1000 1000 1000 START NODE Figura 27: Ejemplo de uso de la tabla taux en el Algoritmo-taux. Una petición de recurso o recursos P llega al nodo 0000 con los valores vd = {0, 1, 2}, va = {} y wl = {}. Como los vecinos en las dimensiones 0 (0001), 1 (0010) y 2 (0100) del nodo están en estado no-vivo, se calcula el último nodo al que se accedería utilizando vd (vecino en la dimensión 2 del vecino en la dimensión 1 del vecino en la dimensión 0 del nodo 0000, es decir, el nodo 0111) y se mira en la tabla taux si tenemos información de la localización del nodo calculado (0111). En el ejemplo suponemos que sí, por lo que se envía al nodo calculado los valores de vd, va y wl recibidos. El proceso de búsqueda en este nodo (0111) se trata como cualquier otro mensaje de petición de recursos. Por ejemplo, el nodo 0111 reordena el vector vd = {0, 1, 2} recibido a vd = {1, 2, 0} ya que su vecino en la dimensión 0 (0110) está en estado no-vivo. Cabe notar que la figura 27 no muestra la búsqueda completa en el hipercubo. Para el ejemplo mostrado en la figura, la búsqueda se inicia en el nodo 1000 y sólo se muestra la propagación de P por su vecino 0000. Algoritmo-taux, en estas condiciones, permite consultar 4 nodos más que sus algoritmos previos en un hipercubo formado por 16 nodos. Cabe notar también que, en la misma figura, el ejemplo muestra el uso de la tabla taux en el primer paso de la búsqueda, pero que puede producirse en cualquiera de los pasos de Algoritmotaux. 55 El entorno de desarrollo generado con GridSim forma parte de un proyecto final de carrera de l’Escola d’Enginyeria de Telecomunicació i Aeroespacial de Castelldefels (Universitat Politècnica de Catalunya – BarcelonaTech), realizado por Andreu Pere Isern Deyà. En el proyecto anteriormente referenciado GridSim presentó algunas complicaciones. La deficiencia más importante es su baja escalabilidad, que no permite realizar simulaciones del orden de nodos que se requieren en la presente tesis (cientos, miles o millones), ya que a medida que el número de nodos de la simulación aumenta, la memoria RAM consumida crece exponencialmente. Así, esta herramienta no ha podido ser utilizada en la mayoría de las evaluaciones de la presente tesis y sólo ha podido ser utilizada para verificar el funcionamiento de los algoritmos en ejemplos concretos con muy pocos nodos. 5.1.2 Aplicaciones propias Una vez desestimado el uso de GridSim como simulador por no permitir realizar simulaciones de entornos distribuidos de gran escala, entendiendo por gran escala, como ya se ha dicho anteriormente, sistemas formados por cientos, miles o millones de máquinas, se opta por generar aplicaciones propias que permitan minimizar el uso de recursos de la máquina donde se ejecutan las simulaciones. El elevado número de nodos ha requerido algunas simulaciones costosas en tiempo, por ejemplo del orden de semanas. La elección del lenguaje de programación de tales aplicaciones se basa en que sea un lenguaje multiplataforma que permita ejecutar las simulaciones en cualquier máquina. Así, el lenguaje utilizado para las aplicaciones propias de esta tesis ha sido Java. Las aplicaciones propias generadas han sido un simulador que permite evaluar en un sistema distribuido simulado métricas de flexibilidad estática de algoritmos que se ejecuten sobre una overlay con topología en hipercubo y un simulador que permite en un sistema emulado distribuido con topología en hipercubo medir tiempos de búsqueda y efectividad. 5.1.3 PlanetLab PlanetLab es una red de investigación global que permite desarrollar nuevos servicios. Desde sus inicios en 2003, más de 1000 investigadores de las principales instituciones académicas y laboratorios industriales de investigación han utilizado PlanetLab para desarrollar nuevas tecnologías para el almacenamiento distribuido, mapeo de red, sistemas P2P, DHTs, y el procesamiento de consultas. En la presente tesis se ha utilizado PlanetLab como infraestructura que simula un entorno distribuido formado por máquinas geográficamente dispersas y sobre las cuales se han desplegado aplicaciones propias de la presente tesis. 5.2 Evaluación de escalabilidad En sistemas distribuidos de gran escala la escalabilidad es una propiedad necesaria ya que cuando un sistema distribuido tiene esta propiedad, al aumentar de tamaño no se degrada considerablemente su funcionamiento y calidad habituales. En este apartado se describe la simulación realizada para evaluar la escalabilidad del los algoritmos presentados en esta tesis También en este capítulo se muestran y discuten los resultados. 56 5.2.1 Descripción del experimento En esta simulación se ha evaluado la escalabilidad de los algoritmos vd, va y taux. Las HOverlays consideradas han estado formadas entre 153 nodos y 29.491 nodos. Para ello, se han generado hipercubos n-dimensionales incompletos de dimensión 8 a 15, ocupados en un 60%, 70%, 80% y 90%. No se han considerado ocupaciones iguales o menores al 50% porque un hipercubo n-dimensional incompleto ocupado en un 50% o menos es un hipercubo (n-1)- dimensional incompleto. En la simulación se ha evaluado cada HOverlay con una probabilidad de fallo (Pf) del 30% y con una probabilidad de satisfacer el recurso en los nodos (Psr) del 25%, 50% y 75%. Pf puede interpretarse como el porcentaje de nodos no-vivos que pueden encontrarse en la overlay. Psr puede interpretarse como el porcentaje de nodos vivos que disponen del servicio que el cliente solicita. Se han establecido estos valores considerando condiciones para las búsquedas con alta probabilidad de fallo y recursos “poco presentes”, “bastante presentes” y “muy presentes” en el sistema distribuido. Con Pf a 30%, para cada dimensión, para cada % de ocupación y para cada Psr, se han ordenado aleatoriamente todos los nodos vivos del hipercubo n-dimensional incompleto y se ha ejecutado una búsqueda de servicio desde cada uno de estos nodos siguiendo ese orden para cada uno de los algoritmos evaluados. Después de esta primera iteración por cada uno de los nodos vivos, se ha ejecutado una segunda iteración de una búsqueda de servicio desde cada uno de esos nodos vivos siguiendo el mismo orden que en la primera iteración para cada uno de los algoritmos evaluados. Finalmente, para cada algoritmo evaluado, se ha calculado el porcentaje de la media de nodos vivos consultados respecto el total de nodos vivos. También se ha calculado el porcentaje de éxito para cada uno de los algoritmos, es decir, en cuantas búsquedas desde nodos vivos de HOverlay se ha encontrado el servicio solicitado. Cabe notar que calcular los porcentajes anteriores en la primera iteración o en la segunda iteración para los algoritmos vd y va es indistinto, se obtienen los mismos resultados y que en el objetivo de la primera iteración de búsquedas en el experimento sólo ha sido asegurar que las tablas taux de Algoritmo-taux no se encuentren vacías o prácticamente vacías en las búsquedas desde los primeros nodos vivos de la iteración, ya que en ese caso Algoritmo-taux es equivalente a Algoritmo-va. Cabe notar también que en Algoritmo-taux la mejora en el porcentaje de la media de nodos vivos consultados respecto el total de nodos vivos con una única iteración o con dos es muy pequeña. Por ejemplo, en el experimento realizado se ha obtenido para el caso concreto del hipercubo n-dimensional incompleto de dimensión 15 ocupado en un 60%, un porcentaje del 85,97% con una iteración y un porcentaje del 85,95% con dos iteraciones. Finalmente para Algoritmo-taux no hay ninguna mejora en el porcentaje de éxito ya que es un 100% con una única iteración y con dos iteraciones. 5.2.2 Datos e interpretación del experimento La figura 30 muestra la media de nodos vivos consultados en % respecto al total de nodos vivos en función de Psr y del % de ocupación. El % de ocupación del hipercubo n-dimensional 57 incompleto (% occupp.) mostrado es 60%, 70%, 80% y 90% (filas) y el Psr es 25%, 50% y 75% (columnas). Para cada una de las gráficas mostradas, la unidad en el eje ordenadas es %. El eje de abscisas indica la dimensión del hipercubo incompleto. Los valores exactos obtenidos se encuentran en el Anexo A. 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=25%, 70% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=25%, 80% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=25%, 90% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=50%, 80% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=50%, 70% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=50%, 90% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=75%, 70% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=75%, 80% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=75%, 90% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=75%, 60% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=50%, 60% ocupp.) 0,0 10,0 20,0 30,0 40,0 8 9 10 11 12 13 14 15 Average of queried nodes (%) Hypercube Dimension (Psr=25%, 60% ocupp.) Algorithm-vd Algorithm-va Algorithm-taux Figura 30: Escalabilidad-Porcentaje de la media de nodos vivos consultados (Pf=30%). Fijado un % de ocupación (una fila), vemos que al aumentar Psr disminuye el % de nodos consultados. La explicación de este resultado se encuentra en que, al aumentar Psr, aumenta el número de nodos vivos que satisfacen la petición del cliente y, por tanto, se encuentra el nodo 58 que satisface esta petición antes, con lo que la búsqueda deja de propagarse por el hipercubo ndimensional incompleto antes para una Psr mayor. Estableciendo una Psr (una columna), no se ve ninguna relación con la ocupación del hipercubo n-dimensional incompleto. Para cada gráfica de la figura 30, no se aprecian casi nunca diferencias para los tres algoritmos evaluados, pero en el Anexo A sí se observa menor % de nodos vivos consultados para vd, después le sigue va y, finalmente, el % es igual al anterior o algo mayor para taux (aunque los valores difieren poco expresados en %). Por ejemplo, en la dimensión 15, para Psr=25% y 70% es 12,85% para vd, 13,48% para va y 13,62% para taux y en la misma dimensión 15, para Psr=50% y 70% es 1,71% para vd, 1,75% para va y 1,75% para taux. Para la mayoría de las gráficas vemos que al aumentar la dimensión del hipercubo disminuye el % de nodos vivos consultados. La explicación de este resultado se encuentra en el hecho de que, al aumentar la dimensión, manteniendo el % y Psr, aumenta el número total de nodos vivos que satisfacen el servicio que solicita el cliente y, por tanto, es más probable encontrar un nodo que satisfaga la petición, dejándose de propagar la búsqueda por el hipercubo incompleto antes para dimensiones mayores. Para las pocas ocasiones en que lo anterior no se cumple, hay que tener en cuenta que la ubicación de los nodos que satisfacen el servicio que solicita el cliente es aleatoria y por tanto, puede darse el caso de que haya que consultar bastantes nodos para encontrar uno que satisfaga la búsqueda del cliente. En la figura 31 se muestra el % de veces (efectividad) que un servicio se encontró para las búsquedas realizadas desde nodos vivos. Para todas las gráficas la efectividad es del 100%, es decir, siempre se encuentra el servicio solicitado por el cliente. Como conclusión obtenemos que el Algoritmo-taux es escalable, ya que fijada una Psr, al aumentar la dimensión del hipercubo disminuye el porcentaje de nodos vivos consultados. Además, el algoritmo propuesto es escalable en términos de almacenamiento de datos, ya que un nodo sólo mantiene información de sus vecinos y no hay ningún nodo en el sistema que tenga información de todos los nodos. También, las búsquedas pueden iniciarse desde cualquier nodo del sistema distribuido y como mínimo para las Psr superiores al 25% siempre se encuentra el servicio buscado aunque fallen el 30% de los nodos del sistema. 59 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=25%, 60% ocupp.) Algorithm-vd Algorithm-va Algorithm-taux 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=25%, 70% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=25%, 80% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=25%, 90% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=50%, 60% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=50%, 70% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=50%, 80% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=50%, 90% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=75%, 60% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=75%, 70% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=75%, 80% ocupp.) 0,0 20,0 40,0 60,0 80,0 100,0 120,0 8 9 10 11 12 13 14 15 effectiveness (%) Hypercube Dimension (Pf=30%, Psr=75%, 90% ocupp.) Figura 31: Escalabilidad-Porcentaje de veces que se encuentra un recurso (Pf=30%). 5.3 Flexibilidad estática en hipercubos completos En este apartado se explica el método utilizado para evaluar cómo se comportan el algoritmo utilizado en HyperD, el utilizado por HaoRen et al. y Algoritmo-taux (propuesto en esta documento) bajo condiciones de fallo y, si son capaces o no, de localizar servicios eficientemente antes de que los algoritmos de recuperación ante fallos se ejecuten. Recordemos que se utiliza el término flexibilidad estática (static resilience) para referirnos a esta localización. En esta evaluación los hipercubos son hipercubos completos, es decir, hipercubos formados por N = 2n 60 nodos (donde N es el número de nodos del hipercubo y n es la dimensión del hipercubo). También en este apartado se muestran los resultados obtenidos y se discuten éstos. 5.3.1 Comparativa con búsqueda en HyperD En HyperD los hipercubos siempre son n-dimensionales completos. Cuando algún nodo tiene más de un único identificador lógico el hipercubo es parcial mientras que cuando todos los nodos tienen un único identificador lógico es un hipercubo n-dimensional completo lleno. En la comparativa de este apartado se utiliza un hipercubo parcial, que es el escenario más habitual. La comparativa cuando HyperD es un hipercubo n-dimensional completo lleno puede verse en el siguiente apartado a este ya que la búsqueda en HyperD es equivalente a la búsqueda con el algoritmo utilizado por HaoRen et al. 0010 1010 0110 1110 0000 1000 NONALIVE 0011 1011 1111 0100 1100 1101 0101 HyperD (H4 -10 nodes) dim0 dim2 dim3 dim1 START NODE (7) (0) (12) (8) (6) (10) 0111 (9) 1001 (11) 0001 (1) NONALIVE xxxx non-alive node (existent) VN xxxx virtual node (non-existent) (3) NONALIVE (6) (7) (9) (0) (1) (12) (8) VN (3) VN (6) VN (7) (10) VN (0) (11) VN (12) VN (12) (3) START NODE xxxx xxxx reached node alive node not reached 2 1 0 2 2 1 33 3 2 Figura 32: Ejemplo de búsqueda en HyperD con un nodo no-vivo. Para realizar la comparativa se ha asumido que el sistema no dispone del servicio solicitado por el cliente, se ha iniciado una búsqueda desde un nodo vivo y se ha contabilizado cuantos nodos vivos no se han consultado. En la comparativa de este apartado se ha utilizado como hipercubo el ejemplo extraído de la figura 3 del artículo de los autores de HyperD [8]. Dicho ejemplo es un hipercubo 4-dimensional completo parcial formado por 10 nodos. Para representar 61 la evolución de la búsqueda que realiza el algoritmo se utiliza una representación en árbol. Los nodos del árbol representan nodos del hipercubo. Cuando un nodo envía la búsqueda a uno de sus nodos vecinos lo indicamos con una flecha que va del nodo emisor al nodo receptor. El algoritmo se ejecuta en varios pasos siendo el número de flechas que hay hasta el nodo inicial el número de pasos en el que el nodo es accedido. La figura 32 muestra la búsqueda iniciada desde el nodo vivo marcado como (3) con identificadores lógicos 0010/1010 donde el nodo marcado como (6) con identificadores lógicos 0011/1011 es no-vivo. En esas condiciones se consultan con el algoritmo de búsqueda en HyperD 5 de 9 nodos vivos. Los nodos no consultados son los nodos marcados como (11), (10), (1) y (9). Para la búsqueda utilizando el algoritmo propuesto en este documento se ha considerado el caso peor, es decir, que la tabla auxiliar taux está vacía para todos los nodos. La figura 33 muestra la misma búsqueda que la figura 32 utilizando el Algoritmo-taux. Cabe notar que en este caso particular, Algoritmo-taux sólo reordena el vector vd ya que no necesita usar el vector va ni las tablas taux. En esas condiciones con Algoritmo-taux se consultan 9 de 9 nodos vivos. 0010 1010 0000 1000 0110 1110 NONALIVE 0011 1011 1111 0100 1100 1101 0101 HyperD (H4 -10 nodes) dim0 dim2 dim3 dim1 START NODE vd={2,0,3}->vd={2,0,3} va={} wl={} (7) 0111 1001 (11) 0001 (1) NONALIVE xxxx non-alive node (existent) VN xxxx virtual node (non-existent) (3) NONALIVE (6) (7) (9) (0) (1) (12) (8) VN (3) VN (6) VN (7) (10) VN (0) (11) VN (12) VN (12) (3) START NODE xxxx xxxx reached node alive node not reached (0) (12) (8) (6) (9) (10) vd={0,3}->vd={3,0} va={} wl={} vd={0} va={} wl={} vd={0,3}->vd={0,3} va={2} wl={} vd={3} va={2} wl={} vd={} va={2} wl={} vd={3} va={} wl={} vd={} va={} wl={} Figura 33: Ejemplo de búsqueda de Algoritmo-taux con un nodo no-vivo. 62 En las condiciones de la comparativa realizada, la flexibilidad estática de Algoritmo-taux es mucho mayor ya que ofrece una garantía total de localización, consultando si es necesario a todos los nodos vivos (el servicio solicitado por el cliente no se encuentra). La mejora es de 44,44% con respecto al algoritmo de búsqueda de HyperD en ese hipercubo 4-dimensional parcial. 5.3.2 Comparativa con búsqueda propuesta por HaoRen et al. Para realizar la comparativa se han evaluado los algoritmos vd, va, taux y el algoritmo utilizado por HaoRen et al. en hipercubos completos de dimensiones 14, 17 y 20, lo que nos permite compararlos en sistemas distribuidos formados por 16.384, 131.072 y 1.048.576 nodos. Cabe decir que para los casos en que los nodos de HyperD tienen uno y sólo un identificador lógico el hipercubo n-dimensional utilizado por HaoRen et al. es igual al hipercubo n-dimensional completo y que además en esos casos ambos algoritmos de búsqueda son iguales. Así, sólo para esos casos, esta comparativa también aplica a la búsqueda en HyperD. La probabilidad de este escenario en HyperD es baja (aproximadamente 1/2n donde n es la dimensión del hipercubo) y decrece a medida que aumenta la dimensión (redes de gran escala). 5.3.2.1 Descripción del experimento Para que la localización del servicio no influya en los resultados del experimento, se ha asumido que el sistema no dispone del servicio solicitado por el cliente y a todos los nodos del hipercubo se les ha asignado una probabilidad de fallo Pf. Pf puede interpretarse como el porcentaje de nodos no-vivos presentes en la HOverlay. Se ha ejecutado la simulación para valores de Pf entre 0 y 50%. Dada una Pf, se ha ejecutado una búsqueda de servicio P desde un nodo vivo y se ha contabilizado cuantos nodos vivos no se han consultado (failed paths) para cada uno de los algoritmos comparados. Posteriormente se ha escogido otro nodo vivo, lo que es equivalente a variar la distribución de nodos no-vivos utilizando una distribución random uniforme, y se ha vuelto a ejecutar la búsqueda de servicio P. Se han ejecutado un total de 20 búsquedas. Después de esta primera iteración de 20 búsquedas, se ha ejecutado una segunda iteración de las mismas 20 búsquedas de servicio desde cada uno de los nodos vivos de la primera iteración para cada uno de los algoritmos evaluados. Finalmente, para cada algoritmo evaluado, se ha calculado el porcentaje de la media de failed paths respecto al total de nodos vivos. Cabe notar que calcular los porcentajes anteriores en la primera iteración o en la segunda iteración para los algoritmos de HaoRen, vd y va es indistinto, se obtienen los mismos resultados y que en el objetivo de la primera iteración de búsquedas en el experimento sólo ha sido asegurar que las tablas taux de Algoritmo-taux no se encuentren vacías o prácticamente vacías, ya que en ese caso Algoritmo-taux es equivalente a Algoritmo-va. Cabe notar también que en Algoritmo-taux la mejora en el porcentaje calculado con una única iteración o con dos es muy pequeña. Por ejemplo, en el experimento realizado se ha obtenido para el caso concreto del hipercubo n-dimensional completo de dimensión 20 con probabilidad de fallo Pf = 10%, un porcentaje del 0,23 % con una iteración y un porcentaje del 0,21 % con dos iteraciones. A diferencia del Algoritmo-va, el Algoritmo de HaoRen et al. no reordena el vector vd y no utiliza el vector va. El Algoritmo-vd reordena el vector vd pero no usa el vector va. Finalmente el 63 Algoritmo-taux continúa en algunos casos la búsqueda cuando los demás algoritmos no pueden (utilizando una tabla auxiliar). Cómo se generan y utilizan los vectores y la tabla se ha explicado anteriormente. 5.3.2.2 Datos e interpretación del experimento En la figura 34 se muestra gráficamente al variar Pf el porcentaje de la media de nodos vivos no consultados (failed paths). La unidad del eje de ordenadas es % y la del eje de abscisas indica la probabilidad de fallo. Dado que la gráfica muestra el porcentaje de nodos no consultados, el algoritmo con porcentaje más alto será el peor y el algoritmo con porcentaje más bajo el mejor de los evaluados. Visualmente las gráficas de la figura 34 se agrupan en 3 grupos. De arriba a abajo, el primer grupo, formado por las 3 gráficas superiores corresponden al algoritmo de búsqueda utilizado por HaoRen et al., el segundo grupo, formado por 3 gráficas que se solapan visualmente en una sola línea corresponden al Algoritmo-vd y el tercer grupo, formado por 6 gráficas, que se solapan visualmente en una sola línea, corresponden a los algoritmos va y taux. Los valores exactos obtenidos en el experimento se detallan en el anexo B. Así, la gráfica de la figura 34 muestra que los algoritmos vd, va y taux ofrecen sustancialmente mejor flexibilidad estática que el Algoritmo utilizado por HaoRen et al. Los algoritmos taux y va son además mejores que vd. Gráficamente no se aprecia que taux sea mejor que va, pero en los valores exactos mostrados en el anexo B puede verse una mejora de taux con respecto a va. Cabe esperar también, que esa mejora aumente a medida que se realicen más búsquedas en HOverlay (en esta simulación se han realizado sólo 20), ya que la tabla auxiliar que utiliza taux para continuar las búsquedas cuando va no puede, contendrá más nodos y será más probable continuar la propagación si es necesario. De los resultados se observa que al algoritmo utilizado por HaoRen et al. es el único que le afecta la dimensión del hipercubo. Como en esta simulación sólo se realizan 20 búsquedas desde nodos vivos escogidos aleatoriamente y el estado de todos los nodos es aleatorio, no podemos determinar con exactitud cuál es el comportamiento al aumentar la dimensión del hipercubo (más adelante confirmaremos que a este algoritmo le afecta la dimensión del hipercubo). 64 0,0 20,0 40,0 60,0 80,0 100,0 0 10 20 30 40 50 Average of failed paths (%) Pf: probability of failure (%) HaoRen (Dim 20) HaoRen (Dim 17) HaoRen (Dim 14) Algorithm-vd (Dim 20) Algorithm-vd (Dim 17) Algorithm-vd (Dim 14) Algorithm-va (Dim 20) Algorithm-va (Dim 17) Algorithm-va (Dim 14) Algorithm-taux (Dim 20) Algorithm-taux (Dim 17) Algorithm-taux (Dim 14) Figura 34: Porcentaje de la media de failed paths en hipercubos completos. A todos los algoritmos les afecta Pf, pero al algoritmo utilizado por HaoRen et al. le afecta mucho más. Por ejemplo, al incrementar el valor de Pf de un 10% a un 20% en el hipercubo 20dimensional completo de la simulación, se produce un incremento en el porcentaje de la media de failed paths del 25,44% para el Algoritmo propuesto por HaoRen et al., del 3,88% para vd, del 1,48% para va y del 1,37% para taux. Este hecho también se observa en la tabla 2 que muestra la media y la varianza de los datos de la gráfica de la figura 34. Algorithm (hypercube's dimension) Average Variance HaoRen (Dim. 14) 68,56 1343,77 HaoRen (Dim. 17) 67,08 1481,23 HaoRen (Dim. 20) 73,83 1497,35 Algorithm-vd (Dim. 14) 14,01 268,64 Algorithm-vd (Dim. 17) 13,98 259,87 Algorithm-vd (Dim. 20) 14,26 269,48 Algorithm-va (Dim. 14) 8,69 142,10 Algorithm-va (Dim. 17) 8,67 136,13 Algorithm-va (Dim. 20) 8,86 142,06 Algorithm-taux (Dim. 14) 8,41 137,86 Algorithm-taux (Dim. 17) 8,42 133,75 Algorithm-taux (Dim. 20) 8,69 140,05 Tabla 2: Media y varianza del porcentaje de la media de failed paths de la figura 34. 71 la Pf no sea extremadamente alta, ya que ofrecen garantías de localización elevadas consultando si es necesario (el servicio solicitado por el cliente no se encuentra) a casi todos los nodos del sistema distribuido independientemente del número de nodos que tenga el sistema. De todos los algoritmos evaluados, taux es el que presenta mejores prestaciones al aumentar la Pf. 5.5 Tiempos de búsqueda por simulación En este apartado se describe la simulación realizada para medir el tiempo de búsqueda de servicios en HOverlay. La simulación se ha realizando utilizando tiempos de transferencia entre máquinas obtenidos del proyecto Reliable Service Infrastructure in Donation-based Grid Environments (RIDGE) [48]. En este proyecto se obtuvieron tiempos de transferencia de datos durante un periodo de tiempo de 10 meses, de julio de 2007 a abril de 2008, en PlanetLab. Como ya se ha dicho, PlanetLab es una red de investigación global. Puede verse como un conjunto de máquinas distribuidas a lo largo del planeta, sobre las que se pueden instalar y ejecutar aplicaciones distribuidas en condiciones reales. Actualmente, PlanetLab dispone de 1078 máquinas que pertenecen a 530 instituciones diferentes. Los resultados del proyecto RIDGE se encuentran disponibles a través de un fichero de texto en su página web. 5.5.1 Descripción del experimento En esta simulación se ha evaluado el tiempo de búsqueda de servicios en HOverlay para los algoritmos vd, va, taux y el algoritmo utilizado por HaoRen et al. Las HOverlays consideradas han estado formadas por 614, 768 y 921 nodos. Para ello, se han generado hipercubos 10dimensionales incompletos ocupados en un 60%, 75% y 90 %. No se han considerado ocupaciones iguales o menores al 50% porque un hipercubo n-dimensional ocupado en un 50% o menos es un hipercubo (n-1)-dimensional. En la simulación se ha evaluado cada HOverlay con una probabilidad de fallo (Pf) en los nodos del 30% y con una probabilidad de satisfacer la petición (Psr) en los nodos del 1%. Pf puede interpretarse como el porcentaje de nodos no-vivos que pueden encontrarse en la overlay. Psr puede interpretarse como el porcentaje de nodos vivos que dispone del servicio que el cliente busca. Se han establecido estos valores considerando condiciones extremas para las búsquedas de servicios, alta probabilidad de fallo de los nodos y muy pocos nodos que dispongan del servicio buscado. A cada nodo presente en la overlay se le ha asignado un tiempo del fichero disponible en el proyecto RIDGE. La asignación de tiempos ha sido aleatoria, de forma que, para al nodo con identificador 0 de la overlay se le ha asignado el tiempo del fichero almacenado en una posición aleatoria, al nodo con identificador 1 se le ha asignado el siguiente tiempo después de esta posición aleatoria y así sucesivamente. Como los datos almacenados en el fichero no están ordenados, la asignación ha sido aleatoria. Este tiempo se ha interpretado como el tiempo que tarda el mensaje de búsqueda en llegar a este nodo desde otro nodo más el tiempo que necesita este nodo para ejecutar el algoritmo evaluado. Una vez generado el hipercubo 10-dimensional incompleto (con una Pf de 30% y una Psr de 1%, en cada nodo), para cada % de ocupación, se han ordenado aleatoriamente los nodos vivos del hipercubo incompleto, se ha ejecutado una búsqueda desde cada uno de los nodos vivos 72 siguiendo ese orden para cada uno de los algoritmos evaluados. Para cada búsqueda se ha almacenado el tiempo menor que ha tardado la búsqueda en encontrar un nodo que satisface el servicio que solicita el cliente. Este tiempo puede verse como el tiempo menor que transcurre desde que el cliente envía el mensaje de búsqueda hasta que se encuentra un nodo en HOverlay que satisface la búsqueda. También se ha calculado el porcentaje de éxito para cada uno de los algoritmos, es decir, en cuantas búsquedas desde el cliente se ha encontrado el servicio. 5.5.2 Datos e interpretación del experimento Para representar los datos se utiliza el percentil. Un percentil, y% = v significa que en y% de las búsquedas de servicio, el tiempo de búsqueda obtenido está por debajo del tiempo v. Así, un percentil del 50% muestra el tiempo de búsqueda suficiente para encontrar el servicio en el 50% de las búsquedas realizadas y un percentil del 100% muestra el tiempo de búsqueda máximo obtenido. La figura 37 muestra el tiempo de las búsquedas de las que se ha obtenido respuesta en función del % de ocupación y del percentil. Los percentiles mostrados son 25%, 50%, 75% y 100% (filas) y el % de ocupación del hipercubo 10-dimensional (% occupp.) es 60%, 75% y 90% (columnas). Para cada una de las gráficas mostradas, la unidad de tiempo en el eje de ordenadas es el milisegundo. El eje de abscisas indica cada uno de los 4 algoritmos evaluados: algoritmo utilizado por HaoRen et al., vd, va y taux. Dado que las gráficas muestran el tiempo de búsqueda, el o los algoritmos con tiempos menores son los mejores de los que se evalúan. Los valores exactos obtenidos se encuentran en el anexo D. Como ejemplo, el primer valor de la primera gráfica (337,5 msecs.) significa que del total de respuestas recibidas (servicios encontrados) para el algoritmo utilizado por HaoRen et al., el 25% de las respuestas obtenidas no tardaron más de 337,5 msecs. Estableciendo un % de ocupación (columna) vemos que al incrementar el percentil, incrementa el tiempo obtenido. La explicación de ello es que aumentando el percentil estamos añadiendo casos en los que el tiempo de búsqueda es cada vez mayor. De las gráficas obtenidas se observa que el algoritmo utilizado por HaoRen et al. no siempre es peor que los algoritmos propuestos vd, va y taux. Debe tenerse en cuenta que la comparación del algoritmo de HaoRen et al. con el resto de algoritmos evaluados no puede realizarse utilizando las gráficas mostradas en la figura 37. La razón se encuentra en que estas gráficas muestran el tiempo de las búsquedas de las que se ha obtenido respuesta y, en el caso del algoritmo de HaoRen et al., no siempre se encuentra el servicio buscado. La figura 38 muestra el porcentaje de veces que se encuentra un servicio para las búsquedas realizadas desde nodos vivos (efectividad). Los valores exactos obtenidos se encuentran en el anexo D. 73 0,0 50,0 100,0 150,0 200,0 250,0 300,0 350,0 400,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (60 % occupp.) PERCENTILE (25%) 0,0 50,0 100,0 150,0 200,0 250,0 300,0 350,0 400,0 450,0 500,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (60 % occupp.) PERCENTILE (50%) 0,0 100,0 200,0 300,0 400,0 500,0 600,0 700,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (60 % occupp.) PERCENTILE (75%) 0,0 200,0 400,0 600,0 800,0 1000,0 1200,0 1400,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (60 % occupp.) PERCENTILE (100%) 0,0 50,0 100,0 150,0 200,0 250,0 300,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (75% occupp.) PERCENTILE (25%) 0,0 50,0 100,0 150,0 200,0 250,0 300,0 350,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (75% occupp.) PERCENTILE (50%) 0,0 50,0 100,0 150,0 200,0 250,0 300,0 350,0 400,0 450,0 500,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (75% occupp.) PERCENTILE (75%) 0,0 100,0 200,0 300,0 400,0 500,0 600,0 700,0 800,0 900,0 1000,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (75% occupp.) PERCENTILE (100%) 0,0 50,0 100,0 150,0 200,0 250,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (90% occupp.) PERCENTILE (25%) 0,0 50,0 100,0 150,0 200,0 250,0 300,0 350,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (90% occupp.) PERCENTILE (50%) 0,0 50,0 100,0 150,0 200,0 250,0 300,0 350,0 400,0 450,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (90% occupp.) PERCENTILE (75%) 0,0 200,0 400,0 600,0 800,0 1000,0 1200,0 1400,0 HaoRen Alg.Vd Alg.Va Alg.Taux Response Time (msec) Algorithm (90% occupp.) PERCENTILE (100%) Figura 37: Tiempo de búsqueda (Pf=30%)(Psr=1%). 74 0,0 10,0 20,0 30,0 40,0 50,0 60,0 70,0 80,0 90,0 100,0 HaoRen Alg.Vd Alg.Va Alg.Taux effectiveness (%) Algorithm (60% occupp.) 0,0 10,0 20,0 30,0 40,0 50,0 60,0 70,0 80,0 90,0 100,0 HaoRen Alg.Vd Alg.Va Alg.Taux effectiveness (%) Algorithm (75% occupp.) 0,0 10,0 20,0 30,0 40,0 50,0 60,0 70,0 80,0 90,0 100,0 HaoRen Alg.Vd Alg.Va Alg.Taux effectiveness (%) Algorithm (90% occupp.) Figura 38: Porcentaje de veces que se encuentra un servicio buscado (Pf=30%)(Psr=1%). Si observamos el porcentaje de veces que se encuentra un servicio buscado en la figura 38, vemos que la efectividad del algoritmo utilizado por HaoRen et al. es claramente inferior al resto de los algoritmos. Para los algoritmos vd, va y taux se encuentra en un 100% de los casos el servicio buscado mientras que para el Algoritmo utilizado por HaoRen et al. esto no sucede. Concluimos de esta simulación que el algoritmo utilizado por HaoRen et al. no asegura que se encuentre un servicio en HOverlay, aunque dicho servicio esté presente, al menos para las condiciones de la simulación realizada: una Pf = 30% y una Psr = 1% en un hipercubo 10dimensional incompleto con % de ocupación del 60%, 75% y 90%. En cambio, los algoritmos vd, va y taux encuentran el servicio en estas condiciones en un 100% de los casos. 5.6 Tiempos de búsqueda en PlanetLab En este apartado se presenta el sistema distribuido real implementado para el servicio de descubrimiento descrito en esta tesis y el experimento realizado en él. El sistema distribuido utiliza PlanetLab como infraestructura. Como ya se ha dicho, PlanetLab es una red de investigación global que permite desarrollar nuevos servicios. Desde sus inicios en 2003, más de 1000 investigadores de las principales instituciones académicas y laboratorios industriales de investigación, han utilizado PlanetLab para desarrollar nuevas tecnologías para el almacenamiento distribuido, mapeo de red, sistemas P2P, DHTs, etc. PlanetLab actualmente dispone de 1093 nodos en 533 lugares. De los nodos disponibles se eligieron 150 nodos distribuidos a lo largo de Europa para crear HOverlay. Así se obtuvo un hipercubo 8-dimensional incompleto con una ocupación del 59%. Tal y como hemos comentado anteriormente, cada nodo (o BIS) en HOverlay tiene un identificador. El identificador de cada BIS fue la posición en la que la máquina aparecía en la lista de nodos de PlanetLab en el momento en que se creó la overlay (noviembre 2011). Dado que dicha lista de nodos no sigue ningún orden aparente y que 2 identificadores en decimal seguidos en HOverlay no son necesariamente vecinos (por ejemplo el nodo con identificador 7(0111) y nodo con identificador 8(1000) no son vecinos en HOverlay), la overlay creada fue aleatoria sin tener en cuenta ningún criterio geográfico que permitiera (a priori) optimizar el tiempo de búsqueda. La lista de nodos utilizados con el identificador de cada uno de ellos se encuentra en el anexo E. 75 En HOverlay cada nodo almacena el estado de sus vecinos. El estado de un vecino se actualizó cada 10 segundos enviando un mensaje al nodo vecino. Si el nodo vecino contestaba al mensaje, su estado se actualizaba como vivo. En otro caso, el estado del vecino se consideraba no-vivo. Entre los nodos escogidos no fue posible desplegar el servicio de descubrimiento en 37 de ellos; obteniendo una tasa inicial de fallo del 24,67%. Durante el experimento, no se obtuvo ninguna respuesta de un total de 7 nodos; 3 de ellos interrumpieron su ejecución y el resto parece que generaban timeouts en las respuestas. Así, el total de nodos no-vivos fue de 44 y la tasa final de nodos en estado no-vivo en el momento del experimento del 29,33%. Una vez puesto en marcha HOverlay, si un nodo recibía un mensaje de búsqueda, el Algoritmo-va se ejecutaba. HOverlay y el Algoritmo-va se implementaron utilizando el protocolo de transporte TCP. Pruebas utilizando UDP en vez de TCP, mostraron que las pérdidas de paquetes eran tan altas que los clientes en pocas ocasiones recibían respuestas de sus búsquedas. 5.6.1 Descripción del experimento En este apartado se describe el experimento realizado sobre el sistema distribuido implementado en PlanetLab. Un cliente se conecta a cada uno de los nodos de HOverlay y envía una búsqueda de servicio con una probabilidad x de ser satisfecha en los nodos de la overlay. Esto significa que aproximadamente un x% de los nodos de HOverlay tienen el servicio solicitado y, por tanto, pueden satisfacer la búsqueda. Los nodos que satisfacen la búsqueda fueron escogidos aleatoria y uniformemente. Las probabilidades de satisfacer la búsqueda o petición (Psr) utilizadas en la evaluación fueron 1%, 5% y 10%. Para cada una de las búsquedas realizadas (una por nodo de la overlay), se calculó el tiempo transcurrido en el cliente entre el envío de la búsqueda y la primera respuesta recibida y se guardaron los datos. Cuando un nodo de la overlay recibía una búsqueda y el servicio solicitado estaba disponible en el nodo, éste enviaba una respuesta directa al cliente que le indicaba la disponibilidad del servicio. Para las búsquedas de las que no se recibió ninguna respuesta no se pudieron almacenar datos. El experimento anterior se realizó el mismo día, 5 veces en 3 slots de tiempo diferentes. Uno fue a las 08:00 a.m. CET, otro a las 13:00 p.m. CET y un tercero a las 21:00 p.m. CET. Así, se ejecutaron un total de 2250 búsquedas desde nodos distribuidos geográficamente por Europa. 5.6.2 Datos e interpretación del experimento Para representar los datos se utiliza el percentil. Un percentil, y% = v significa que en y% de las búsquedas de servicio, el tiempo de búsqueda obtenido está por debajo del tiempo v. Así, un percentil del 50% muestra el tiempo de búsqueda suficiente para encontrar el servicio en el 50% de las búsquedas realizadas y un percentil del 100% muestra el tiempo de búsqueda máximo. La figura 39 muestra el tiempo de las búsquedas de las que se ha obtenido respuesta, en función de la probabilidad de satisfacer la búsqueda (Psr) y del percentil. Los percentiles mostrados son 25%, 50%, 75% y 100% (filas) y la probabilidad de satisfacer la búsqueda (Psr) en los nodos es 1%, 5% y 10% (columnas). Para todas las gráficas, la unidad de tiempo en el eje de 76 ordenadas es el milisegundo. El eje de abscisas indica el número del experimento ejecutado (1 a 5 son los 5 experimentos para el primer slot de tiempo, 6 a 10 los 5 experimentos del segundo slot de tiempo, y 11 a 15 los 5 experimentos para el tercer slot de tiempo). Dado que las gráficas muestran tiempo de búsqueda, un tiempo bajo es mejor que uno alto. Los valores exactos obtenidos se encuentran en el anexo F. 0,0 100,0 200,0 300,0 400,0 500,0 600,0 700,0 800,0 900,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=1%) PERCENTILE (25%) 0,0 200,0 400,0 600,0 800,0 1000,0 1200,0 1400,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=1%) PERCENTILE (50%) 0,0 500,0 1000,0 1500,0 2000,0 2500,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=1%) PERCENTILE (75%) 0,0 5000,0 10000,0 15000,0 20000,0 25000,0 30000,0 35000,0 40000,0 45000,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=1%) PERCENTILE (100%) 0,0 100,0 200,0 300,0 400,0 500,0 600,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=10%) PERCENTILE (25%) 0,0 100,0 200,0 300,0 400,0 500,0 600,0 700,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=10%) PERCENTILE (50%) 0,0 100,0 200,0 300,0 400,0 500,0 600,0 700,0 800,0 900,0 1000,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=10%) PERCENTILE (75%) 0,0 10000,0 20000,0 30000,0 40000,0 50000,0 60000,0 70000,0 80000,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experimentt (Psr=10%) PERCENTILE (100%) 0,0 100,0 200,0 300,0 400,0 500,0 600,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=5%) PERCENTILE (25%) 0,0 100,0 200,0 300,0 400,0 500,0 600,0 700,0 800,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=5%) PERCENTILE (50%) 0,0 200,0 400,0 600,0 800,0 1000,0 1200,0 1400,0 1600,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=5%) PERCENTILE (75%) 0,0 5000,0 10000,0 15000,0 20000,0 25000,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Response Time (msec) Experiment (Psr=5%) PERCENTILE (100%) Figura 39: Tiempo de búsqueda en PlanetLab. 77 Como ejemplo, el primer valor de la primera gráfica (612 milisegundos), significa que del total de las respuestas recibidas de las búsquedas del primer experimento de los 5 del slot de tiempo de las 08:00 a.m. CET, el 25% de las búsquedas no tardaron más de 612 milisegundos. Fijando un percentil (una fila), vemos que a medida que Psr se incrementa, el tiempo de búsqueda mostrado desciende en la mayoría de los casos. La explicación de este resultado se encuentra en que para una búsqueda con un Psr mayor es más probable que un nodo que satisfaga la búsqueda y, por tanto, es más probable encontrar un nodo antes. Estableciendo una Psr (columna) vemos que al incrementar el percentil incrementa el tiempo obtenido para la mayoría de las muestras. La explicación de ello es que aumentando el percentil estamos añadiendo casos en los que el tiempo de búsqueda es cada vez mayor. Para algunas gráficas vemos que se obtienen valores de tiempo bastante dispares en diferentes experimentos. Con respecto a este punto, debe tenerse en cuenta el hecho de que estamos ejecutando las búsquedas en nodos de PlanetLab que ejecutan también procesos de otros usuarios que no se controlan. Así, el tiempo de búsqueda puede verse afectado por otros procesos que se ejecutan en los nodos. También, el tiempo de búsqueda se ve afectado por las condiciones de la red en el momento en el que se realizan los experimentos y estas condiciones son impredecibles. Por otro lado vemos que para el percentil 100% es para el que se obtienen las mayores diferencias entre los valores obtenidos para distintos experimentos. La explicación de esto radica en el hecho de que en este caso estamos considerando todos los tiempos de búsqueda de las búsquedas de las que se ha obtenido respuesta. Así, sólo con que un nodo esté sobrecargado, o la comunicación entre dos nodos o entre un nodo y el cliente sea lenta, el tiempo mostrado se ve incrementado considerablemente. En las figuras 40, 41 y 42 se muestran los tiempos de búsqueda en PlanetLab utilizando funciones de distribución acumulada para Psr = 1%, 5% y 10% respectivamente. Para cada una de las figuras, la primera gráfica son las funciones de distribución acumulada de los experimentos 1 a 5 que son los 5 experimentos para el primer slot de tiempo, la segunda gráfica son las funciones de distribución acumulada de los experimentos 6 a 10 que son los 5 experimentos del segundo slot de tiempo y la tercera gráfica son las funciones de distribución de los experimentos 11 a 15 que son los 5 experimentos para el tercer slot de tiempo. El eje de abscisas indica el tiempo de búsqueda expresado en segundos y el eje de ordenadas indica la probabilidad (en tanto por uno). Por ejemplo, si para 1 segundo en el eje de abscisas el eje de ordenadas toma el valor 0,8, significa que en el 80% de los casos la búsqueda no tardó más de 1 segundo. 78 0,00 0,10 0,20 0,30 0,40 0,50 0,60 0,70 0,80 0,90 1,00 0,001 0,01 0,1 1 10 100 Response Time (seconds) (Psr=1%) Number of experiment = 1 Number of experiment = 2 Number of experiment = 3 Number of experiment = 4 Number of experiment = 5 Number of experiment = 6 Number of experiment = 7 Number of experiment = 8 Number of experiment = 9 Number of experiment = 10 Number of experiment = 11 Number of experiment = 12 Number of experiment = 13 Number of experiment = 14 Number of experiment = 15 Figura 40: Funciones de distribución acumulada del tiempo de búsqueda (Psr = 1%). 79 0,00 0,10 0,20 0,30 0,40 0,50 0,60 0,70 0,80 0,90 1,00 0,001 0,01 0,1 1 10 100 Response Time (seconds) (Psr=5%) Number of experiment = 1 Number of experiment = 2 Number of experiment = 3 Number of experiment = 4 Number of experiment = 5 Number of experiment = 6 Number of experiment = 7 Number of experiment = 8 Number of experiment = 9 Number of experiment = 10 Number of experiment = 11 Number of experiment = 12 Number of experiment = 13 Number of experiment = 14 Number of experiment = 15 Figura 41: Funciones de distribución acumulada del tiempo de búsqueda (Psr = 5%). 80 0,00 0,10 0,20 0,30 0,40 0,50 0,60 0,70 0,80 0,90 1,00 0,001 0,01 0,1 1 10 100 Response Time (seconds) (Psr=10%) Number of experiment = 1 Number of experiment = 2 Number of experiment = 3 Number of experiment = 4 Number of experiment = 5 Number of experiment = 6 Number of experiment = 7 Number of experiment = 8 Number of experiment = 9 Number of experiment = 10 Number of experiment = 11 Number of experiment = 12 Number of experiment = 13 Number of experiment = 14 Number of experiment = 15 Figura 42: Funciones de distribución acumulada del tiempo de búsqueda (Psr = 10%). BIBLIOGRAFÍA [1] The European Grid Infrastructure home page, http://www.egi.eu/ [2] Berman, F., Hey, A.J. and Fox, G.C. 2003. GRID Computing, John Wiley & Sons Ltd, Chichester, England. [3] Ian Foster, Carl Kesselman, and Steven Tuecke. 2001. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. Int. J. High Perform. Comput. Appl. 15, 3 (August 2001), 200-222. DOI=10.1177/109434200101500302 http://dx.doi.org/10.1177/109434200101500302 [4] Ian Foster, Yong Zhao, Ioan Raicu Shiyong Lu. “Cloud Computing and Grid Computing 360-Degree Compared” [5] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica. 2003. The impact of DHT routing geometry on resilience and proximity. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM '03). ACM, New York, NY, USA, 381-394. DOI=10.1145/863955.863998 http://doi.acm.org/10.1145/863955.863998 [6] Hao Ren, Zhiying Wang, and Zhong Liu. 2006. A Hyper-cube based P2P Information Service for Data Grid. In Proceedings of the Fifth International Conference on Grid and Cooperative Computing (GCC '06). IEEE Computer Society, Washington, DC, USA, 508513. DOI=10.1109/GCC.2006.9 http://dx.doi.org/10.1109/GCC.2006.9 [7] Andi Toce, Abbe Mowshowitz, Paul Stone, Patrick Dantressangle and Graham Bent. September 2011. HyperD: A Hypercube Topology for Dynamic Distributed Federated Databases. ACITA 2011. [8] Andi Toce, Abbe Mowshowitz, Akira Kawaguchi, Paul Stone, Patrick Dantressangle and Graham Bent. September 18, 2012. HyperD: Analysis and Performance Evaluation of a Distributed Hypercube Database. ACITA 2012. [9] B. Tierney, R. Aydt, D. Gunter, W. Smith, M. Swany, V. Taylor and R. Wolski. March 2000. Revised January 2002. A Grid monitoring architecture. Global Grid Forum Performance Working Group. [10] B. Tierney, R. Aydt, D. Gunter, W. Smith, M. Swany, V. Taylor and R. Wolski. 2002. A Grid Monitoring Architecture. Open Grid Forum. GFD.7. INFO. [11] A. W. Cooke, A. J. G. Gray, W. Nutt, J. Magowan, M. Oevers, P. Taylor, R. Cordenonsi, R. Byrom, L. Cornwall, A. Djaoui, L. Field, S. M. Fisher, S. Hicks, J. Leake, R. Middleton, A. Wilson, X. Zhu, N. Podhorszki, B. Coghlan, S. Kenny and J. Ryan. 2004. The relational grid monitoring architecture: Mediating information about the grid. Journal of Grid Computing (2004) 2: 323–339 88 [12] Ian Foster. 2005. Globus toolkit version 4: software for service-oriented systems. In Proceedings of the 2005 IFIP international conference on Network and Parallel Computing (NPC'05), Hai Jin, Daniel Reed, and Wenbin Jiang (Eds.). Springer-Verlag, Berlin, Heidelberg, 2-13. DOI=10.1007/11577188_2 http://dx.doi.org/10.1007/11577188_2 [13] LDAP, http://en.wikipedia.org/wiki/LDAP [14] Open Grid Services Infrastructure (OGSI) standard version 1.0. 2003. Global Grid Forum. draft-ggf-ogsi-gridservice-33_2003-06-27.pdf [15] Booth D, Hass H, McCabe F et al. 2003. Web Services Architecture, W3C, Working Draft, Retrieved from http://www.w3.org/TR/2003/WD-ws-arch-20030808/ [16] Schopf J M, Raicu I, Pearlman L et al. 2006. Monitoring and Discovery in a Web Services Framework: Functionality and Performance of Globus Toolkit MDS4. Technical Report, Mathematics and Computer Science Division, Argonne National Laboratory. [17]R. Ahmed, N. Limam, J. Xiao, Y. Iraqi, and R. Boutaba. 2007. Resource and service discovery in large-scale multi-domain networks. Commun. Surveys Tuts. 9, 4 (October 2007), 2-30.DOI=10.1109/COMST.2007.4444748 http://dx.doi.org/10.1109/COMST.2007.4444748 [18] Steven E. Czerwinski, Ben Y. Zhao, Todd D. Hodes, Anthony D. Joseph, and Randy H. Katz. 1999. An architecture for a secure service discovery service. In Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking (MobiCom '99). ACM, New York, NY, USA, 24-35. DOI=10.1145/313451.313462 http://doi.acm.org/10.1145/313451.313462 [19] William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, and Jeremy Lilley. 2000. The design and implementation of an intentional naming system. SIGOPS Oper. Syst. Rev. 34, 2 (April 2000), 22-. DOI=10.1145/346152.346192 http://doi.acm.org/10.1145/346152.346192 [20] Adriana Iamnitchi and Ian T. Foster. 2001. On Fully Decentralized Resource Discovery in Grid Environments. In Proceedings of the Second International Workshop on Grid Computing (GRID '01), Craig A. Lee (Ed.). Springer-Verlag, London, UK, UK, 51-62. [21] Catlett, C. and others. 2008. TeraGrid: Analysis of Organization, System Architecture, and Middleware Enabling New Types of Applications, Advances in Parallel Computing; Volume 16, 2008; High Performance Computing and Grids in Action [22] The National Science Fundation (NSF) Program Synopsis, http://www.nsf.gov/funding/pgm_summ.jsp?pims_id=5456 [23] Extreme Science and Engineering Digital Environment (XSEDE) https://www.xsede.org/home 89 [24] Lee Liming, John-Paul Navarro, Eric Blau, Jason Brechin, Charlie Catlett, Maytal Dahan, Diana Diehl, Rion Dooley, Michael Dwyer, Kate Ericson, Ian Foster, Ed Hanna, David L. Hart, Chris Jordan, Rob Light, Stuart Martin, John McGee, Laura Pearlman, Jason Reilly, Tom Scavo, Michael Shapiro, Shava Smallen, Warren Smith, and Nancy Wilkins-Diehr. 2009. TeraGrid's integrated information service. In Proceedings of the 5th Grid Computing Environments Workshop (GCE '09). ACM, New York, NY, USA, , Article 8 , 10 pages. DOI=10.1145/1658260.1658271 http://doi.acm.org/10.1145/1658260.1658271 [25] Uniform Interface to Computing Resources (UNICORE), http://www.unicore.eu/index.php [26]M. Ellert, M. Grønager, A. Konstantinov, B. Kónya, J. Lindemann, I. Livenson, J. L. Nielsen, M. Niinimäki, O. Smirnova, and A. Wäänänen. 2007. Advanced resource connector middleware for lightweight computational Grids. Future Gener. Comput. Syst. 23, 2 (February 2007), 219-240. DOI=10.1016/j.cam.2006.05.008 http://dx.doi.org/10.1016/j.cam.2006.05.008 [27]F. Ould-Saada, The NorduGrid collaboration, SWITCH Journal 1 (2004) 23–24. [28]The Estonian Grid home page, http://grid.eenet.ee [29]The Swedish Grid testbed (SWEGRID) home page, http://www.swegrid.se. [30]The NorduGrid Collaboration home page, http://www.nordugrid.org/ [31]Gabriele Garzoglio, Tanya Levshina, Parag Mhashilkar and Steve Timm. 2009. ReSS: A Resource Selection Service for the Open Science Grid. Grid Computing (2009), Part III, 8998, DOI: 10.1007/978-0-387-78417-5_8 [32]The Open Science Grid home page, http://www.opensciencegrid.org/ [33]The FermiGrid home page, http://fermigrid.fnal.gov/ [34]Youcef Saad and Martin H. Schultz. 1988. Topological Properties of Hypercubes. IEEE Trans. Comput. 37, 7 (July 1988), 867-872. DOI=10.1109/12.2234 http://dx.doi.org/10.1109/12.2234 [35] Dong Xiang, Member, IEEE, Ai Chen, and Jie Wu, Senior Member, IEEE. 2003. Reliable Broadcasting in Wormhole-Routed Hypercube-Connected Networks Using Local Safety Information. IEEE transactions on reliability. Vol. 52, no. 2 (June 2003) [36] M. Y. Chan and S. J. Lee. 1993. Fault-Tolerant Embedding of Complete Binary Trees in Hypercubes. IEEE Trans. Parallel Distrib. Syst. 4, 3 (March 1993), 277-288. DOI=10.1109/71.210811 http://dx.doi.org/10.1109/71.210811 90 [37] Jai Eun Jang. 1990. An optimal fault-tolerant broadcasting algorithm for a hypercube multiprocessor. In Proceedings of the 1990 ACM annual conference on Cooperation (CSC '90). ACM, New York, NY, USA, 96-102. DOI=10.1145/100348.100363 http://doi.acm.org/10.1145/100348.100363 [38]Chang, Y. 1993. Fault tolerant broadcasting in SIMD hypercubes. In Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, 1-4 Dec 1993. 348-351. DOI: 10.1109/SPDP.1993.395512 [39]Gangadhar, D.K.;SCAFFOLD - self configuring overlays using metadata hypercubes, Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2010 International Congress on Digital Object Identifier: 10.1109/ICUMT.2010.5676475 Publication Year: 2010, Pages: 875 - 880 [40] Mario Schlosser, Michael Sintek, Stefan Decker, and Wolfgang Nejdl. 2002. HyperCuP: hypercubes, ontologies, and efficient search on peer-to-peer networks. In Proceedings of the 1st international conference on Agents and peer-to-peer computing (AP2PC'02), Gianluca Moro and Manolis Koubarakis (Eds.). Springer-Verlag, Berlin, Heidelberg, 112-124. [41] Wolfgang Nejdl, Martin Wolpers, Wolf Siberski, Christoph Schmitz, Mario Schlosser, Ingo Brunkhorst, and Alexander Löser. 2003. Super-peer-based routing and clustering strategies for RDF-based peer-to-peer networks. In Proceedings of the 12th international conference on World Wide Web (WWW '03). ACM, New York, NY, USA, 536-543. DOI=10.1145/775152.775229 http://doi.acm.org/10.1145/775152.775229 [42] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. 2001. Chord: A scalable peer-to-peer lookup service for internet applications. SIGCOMM Comput. Commun. Rev. 31, 4 (August 2001), 149-160. DOI=10.1145/964723.383071 http://doi.acm.org/10.1145/964723.383071 [43]Muhamed Sukkar. (2010). Design and Implementation of a Service Discovery and Recommendation Architecture. (Doctoral dissertation). Retrieved from http://hdl.handle.net/10012/5526. [44] Jörg Liebeherr and Tyler K. Beam. 1999. HyperCast: A Protocol for Maintaining Multicast Group Members in a Logical Hypercube Topology. In Proceedings of the First International COST264 Workshop on Networked Group Communication (NGC '99), Luigi Rizzo and Serge Fdida (Eds.). Springer-Verlag, London, UK, UK, 72-89. [45]Buyya, R. i Murshed, M., “GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for GRID Computing”, Monash University, Melbourne, Australia, 1-37. [46]The GridSim home page, http://www.gridbus.org/gridsim/ 91 [47]The Simjava home page, http://www.dcs.ed.ac.uk/home/hase/simjava/ [48]RIDGE - Reliable Service Infrastructure in Donation-based Grid Environments (http://ridge.cs.umn.edu/pltraces.html) ANEXOS 95 ANEXO A: EVALUACIÓN DE ESCALABILIDAD Dim. Algorithm-vd Algorithm-va Algorithm-taux 836,36 37,72 37,95 925,18 26,25 26,33 10 25,05 26,21 26,30 11 22,11 23,15 23,25 12 18,37 19,14 19,23 13 17,44 18,29 18,40 14 16,28 17,04 17,16 15 13,33 13,95 14,05 Average of queried nodes (%) Tabla 6: Porcentaje de la media de nodos vivos consultados (Psr=25%) (60% ocupación). Dim. Algorithm-vd Algorithm-va Algorithm-taux 832,81 34,16 34,29 930,39 31,22 31,33 10 26,48 27,78 27,91 11 21,54 22,49 22,70 12 21,42 22,51 22,71 13 17,82 18,63 18,81 14 15,63 16,40 16,58 15 12,85 13,48 13,62 Average of queried nodes (%) Tabla 7: Porcentaje de la media de nodos vivos consultados (Psr=25%) (70% ocupación). 96 Dim. Algorithm-vd Algorithm-va Algorithm-taux 837,19 38,87 39,16 931,37 32,61 32,78 10 23,16 24,23 24,42 11 21,14 22,10 22,33 12 20,09 21,02 21,27 13 17,60 18,42 18,61 14 13,98 14,66 14,84 15 13,43 14,06 14,25 Average of queried nodes (%) Tabla 8: Porcentaje de la media de nodos vivos consultados (Psr=25%) (80% ocupación). Dim. Algorithm-vd Algorithm-va Algorithm-taux 828,60 29,14 29,23 930,33 31,43 31,63 10 22,84 23,70 23,89 11 22,31 23,23 23,41 12 19,11 19,96 20,18 13 17,53 18,41 18,64 14 14,08 14,76 14,95 15 12,99 13,60 13,78 Average of queried nodes (%) Tabla 9: Porcentaje de la media de nodos vivos consultados (Psr=25%) (90% ocupación). 103 ANEXO C: EVALUACIÓN EN HIPERCUBOS INCOMPLETOS Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 833,49 3,36 1,57 0,70 943,18 5,52 2,86 1,81 10 35,34 1,38 0,56 0,38 11 41,53 2,58 1,17 0,85 12 43,87 2,05 0,80 0,50 13 49,04 2,43 1,03 0,61 14 49,61 1,95 0,74 0,44 15 53,09 2,02 0,75 0,45 16 54,82 2,09 0,81 0,46 Average of failed paths (%) Pf = 10 %, 60 % occup. Tabla 21: Porcentaje de la media de failed paths (Pf=10%, 60% ocupación). Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 832,39 1,77 0,70 0,47 935,24 2,80 1,05 0,41 10 40,32 2,38 0,92 0,56 11 44,20 2,67 1,08 0,66 12 43,98 1,94 0,72 0,42 13 49,61 2,41 0,90 0,44 14 52,86 2,33 0,82 0,40 15 54,10 2,03 0,71 0,37 16 56,92 2,07 0,73 0,37 Average of failed paths (%) Pf = 10 %, 70 % occup. Tabla 22: Porcentaje de la media de failed paths (Pf =10%, 70% ocupación). 104 Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 833,93 1,60 0,66 0,18 938,19 2,48 1,05 0,59 10 38,68 1,76 0,60 0,28 11 44,37 2,02 0,66 0,36 12 47,57 2,39 0,87 0,39 13 48,08 2,10 0,76 0,33 14 52,42 2,24 0,78 0,34 15 54,39 2,05 0,69 0,31 16 57,02 2,00 0,66 0,28 Pf = 10 %, 80 % occup. Average of failed paths (%) Tabla 23: Porcentaje de la media de failed paths (Pf =10%, 80% ocupación). Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 829,66 1,68 0,36 0,19 932,63 1,49 0,39 0,16 10 40,56 1,84 0,65 0,28 11 40,76 1,82 0,56 0,23 12 46,94 2,02 0,64 0,29 13 48,05 1,96 0,60 0,24 14 51,86 1,90 0,58 0,24 15 52,38 1,71 0,50 0,20 16 55,48 1,71 0,50 0,20 Pf = 10 %, 90 % occup. Average of failed paths (%) Tabla 24: Porcentaje de la media de failed paths (Pf =10%, 90% ocupación). 105 Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 851,08 8,51 4,77 3,22 950,36 5,03 2,15 1,76 10 56,16 6,65 3,12 2,33 11 61,06 6,50 3,07 2,27 12 65,39 6,14 2,81 2,15 13 68,45 6,48 2,93 2,12 14 73,72 7,16 3,33 2,43 15 75,76 6,87 3,06 2,23 16 78,53 6,70 2,94 2,14 Average of failed paths (%) Pf = 20 %, 60 % occup. Tabla 25: Porcentaje de la media de failed paths (Pf =20%, 60% ocupación). Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 843,35 5,66 2,97 2,24 954,11 8,12 4,38 2,55 10 54,96 5,26 2,39 1,50 11 64,37 7,03 3,21 2,02 12 67,29 7,29 3,37 2,12 13 72,59 8,01 3,68 2,48 14 73,68 6,99 3,05 1,91 15 76,66 6,78 2,92 1,89 16 78,99 6,46 2,70 1,76 Average of failed paths (%) Pf = 20 %, 70 % occup. Tabla 26: Porcentaje de la media de failed paths (Pf =20%, 70% ocupación). 106 Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 849,77 7,81 3,93 2,25 952,63 6,31 2,72 1,66 10 56,66 5,46 2,23 1,28 11 62,91 7,14 3,22 2,00 12 67,55 6,85 3,00 1,83 13 72,69 7,20 3,12 1,88 14 74,10 6,76 2,92 1,74 15 76,68 6,48 2,70 1,62 16 78,90 6,44 2,67 1,59 Pf = 20 %, 80 % occup. Average of failed paths (%) Tabla 27: Porcentaje de la media de failed paths (Pf =20%, 80% ocupación). Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 851,41 7,28 3,16 1,73 952,14 5,46 2,23 1,31 10 61,97 7,53 3,22 2,10 11 66,11 7,40 3,25 2,15 12 68,79 6,90 2,86 1,70 13 71,23 6,53 2,61 1,50 14 73,72 6,09 2,44 1,39 15 76,44 6,04 2,39 1,37 16 79,12 6,23 2,48 1,41 Pf = 20 %, 90 % occup. Average of failed paths (%) Tabla 28: Porcentaje de la media de failed paths (Pf =20%, 90% ocupación). 107 Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 859,64 10,65 5,27 4,96 965,20 11,36 5,91 5,19 10 70,62 15,20 9,15 7,28 11 74,60 16,31 9,90 8,27 12 78,50 14,39 8,00 6,36 13 82,46 14,79 8,06 6,65 14 85,13 14,43 7,72 6,43 15 87,44 14,96 8,10 6,58 16 89,55 14,89 7,95 6,40 Average of failed paths (%) Pf = 20 %, 60 % occup. Tabla 29: Porcentaje de la media de failed paths (Pf =30%, 60% ocupación). Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 863,22 12,22 5,98 5,20 966,25 15,82 10,05 8,12 10 69,48 11,93 6,63 5,26 11 76,96 16,57 9,68 7,44 12 80,89 15,42 8,58 6,72 13 83,49 14,46 7,71 6,02 14 86,03 14,81 7,85 5,93 15 88,00 14,75 7,82 5,86 16 89,80 14,60 7,65 5,71 Average of failed paths (%) Pf = 20 %, 70 % occup. Tabla 30: Porcentaje de la media de failed paths (Pf =30%, 70% ocupación). 108 Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 862,31 10,77 5,13 4,00 970,26 15,71 8,54 6,57 10 74,20 14,52 7,59 5,62 11 77,76 15,39 8,40 6,07 12 79,25 13,42 7,02 4,96 13 82,51 13,65 7,13 5,09 14 85,86 14,25 7,44 5,31 15 88,65 14,79 7,69 5,42 16 90,29 14,73 7,66 5,39 Pf = 20 %, 80 % occup. Average of failed paths (%) Tabla 31: Porcentaje de la media de failed paths (Pf =30%, 80% ocupación). Dim. HaoRen et al.'s Algorithm-vd Algorithm-va Algorithm-taux 859,36 9,93 4,77 3,40 970,44 15,05 8,00 6,04 10 71,72 12,46 6,34 4,66 11 77,86 14,57 7,64 5,45 12 79,94 13,04 6,50 4,53 13 83,31 13,52 6,77 4,62 14 85,91 13,80 6,98 4,73 15 88,02 13,69 6,88 4,64 16 90,12 14,01 7,04 4,76 Pf = 20 %, 90 % occup. Average of failed paths (%) Tabla 32: Porcentaje de la media de failed paths (Pf =30%, 90% ocupación). 109 ANEXO D: TIEMPOS DE BÚSQUEDA POR SIMULACIÓN Algorithm PERCENTILE (25%) PERCENTILE (50%) PERCENTILE (75%) PERCENTILE (100%) HaoRen 337,50 463,00 589,50 1139,00 Alg.Vd 353,75 462,00 578,00 1151,00 Alg.Va 353,50 462,00 576,50 1151,00 Alg.Taux 353,50 461,00 574,00 1151,00 Time (msecs.) Tabla 33: Tiempo de búsqueda (Psr= 1%) (Pf=30%) (60% ocupación). Algorithm PERCENTILE (25%) PERCENTILE (50%) PERCENTILE (75%) PERCENTILE (100%) HaoRen 241,00 319,00 436,00 896,00 Alg.Vd 211,75 288,00 378,00 589,00 Alg.Va 210,50 285,50 376,25 589,00 Alg.Taux 210,50 285,50 376,25 589,00 Time (msecs.) Tabla 34: Tiempo de búsqueda (Psr= 1%) (Pf=30%) (75% ocupación). Algorithm PERCENTILE (25%) PERCENTILE (50%) PERCENTILE (75%) PERCENTILE (100%) HaoRen 210,00 295,00 394,00 1147,00 Alg.Vd 198,75 267,00 346,50 693,00 Alg.Va 197,50 266,00 346,50 693,00 Alg.Taux 197,50 265,50 344,50 693,00 Time (msecs.) Tabla 35: Tiempo de búsqueda (Psr= 1%) (Pf=30%) (90% ocupación). Algorithm 60% occupp. 75% occupp. 90% occupp. HaoRen 50 80 89 Alg.Vd 99 100 100 Alg.Va 100 100 100 Alg.Taux 100 100 100 Effectiveness (%) Tabla 36: Porcentaje de veces que se encuentra un servicio buscado (Psr= 1%) (Pf=30%). 111 ANEXO E: LISTA DE NODOS DE PLANETLAB UTILIZADOS Lista de nodos de Noviembre 2011 Node identifier Hostname 0 ple4.ipv6.lip6.fr 1 ple3.ipv6.lip6.fr 2 onelab-1.fhi-fokus.de 3 planetlab2.ionio.gr 4 host147-82-static.93-94-b.business.telecomitalia.it 5 planetlab1.urv.cat 6 planetlabpc1.upf.edu 7 planetlab1.tau.ac.il 8 planetlab1.thlab.net 9 uoepl1.essex.ac.uk 10 planetlab-2.imag.fr 11 ple01.fc.univie.ac.at 12 planetlab2.urv.cat 13 planetlab3.xeno.cl.cam.ac.uk 14 planetlab2.upc.es 15 planetlab01.tkn.tu-berlin.de 16 planetlab01.dis.unina.it 17 onelab6.iet.unipi.it 18 planetlabpc2.upf.edu 19 planetlab2.csg.uzh.ch 20 planetlab2.dit.upm.es 21 planetlab-1.cs.ucy.ac.cy 22 planetlab-3.imperial.ac.uk 23 planetlab1.informatik.uni-wuerzburg.de 24 plab1-itec.uni-klu.ac.at 25 uoepl2.essex.ac.uk 26 planetlab1.dit.upm.es 27 planetlab1.ci.pwr.wroc.pl 28 dplanet1.uoc.edu 29 planetlab1.csg.uzh.ch 30 planetlab-1.imperial.ac.uk 31 planetlab1.fct.ualg.pt 32 planetlab-1.iscte.pt 33 planet1.l3s.uni-hannover.de 34 openlab02.pl.sophia.inria.fr 35 planet2.itc.auth.gr 36 planetlab2.informatik.uni-wuerzburg.de 37 planetlab2.informatik.uni-goettingen.de 38 ops.ii.uam.es 39 planetlab2.tau.ac.il 112 Node identifier Hostname 40 planetlab-2.di.fc.ul.pt 41 planetlab1.montefiore.ulg.ac.be 42 planetlab1.sics.se 43 planetlab-node-02.ucd.ie 44 ple02.fc.univie.ac.at 45 planetlab2.fri.uni-lj.si 46 planetlab2.tmit.bme.hu 47 planetlab1.upm.ro 48 planetlab-node-01.ucd.ie 49 planetlab-2.iscte.pt 50 planetlab04.cnds.unibe.ch 51 planetlab1.di.fct.unl.pt 52 planetlab-node3.it-sudparis.eu 53 peeramidion.irisa.fr 54 planetlab2.fem.tu-ilmenau.de 55 planetlab1.s3.kth.se 56 planetlab-4.dis.uniroma1.it 57 planetlab2.ifi.uio.no 58 thalescom-48-41.cnt.nerim.net 59 onelab7.iet.unipi.it 60 planetlab1.cs.aueb.gr 61 planetlab1.rd.tut.fi 62 lsirextpc02.epfl.ch 63 planetlab2.xeno.cl.cam.ac.uk 64 planetlab1.ionio.gr 65 planetlab3.di.unito.it 66 planetlab-um00.di.uminho.pt 67 planetlab2.wiwi.hu-berlin.de 68 planetlab1.research.nicta.com.au 69 planetlab2.eurecom.fr 70 planetlab-2.research.netlab.hut.fi 71 planetlab1.fri.uni-lj.si 72 iraplab2.iralab.uni-karlsruhe.de 73 planet2.unipr.it 74 onelab2.info.ucl.ac.be 75 ple2.tu.koszalin.pl 76 planetlab3.cs.st-andrews.ac.uk 77 planet3.prakinf.tu-ilmenau.de 78 planetlab3.informatik.uni-erlangen.de 79 onelab3.info.ucl.ac.be 80 plab2.ple.silweb.pl 81 planetlab2.di.fct.unl.pt 82 planet2.l3s.uni-hannover.de 83 planetlab4.hiit.fi