Repositorio Institucional de Documentos

Proyecto Final de Carrera Ingeniería Informática Curso 2010/2011 Memoria ESTRUCTURA DE ACELERACIÓN PARA RENDER 3D DISTRIBUIDA MEDIANTE COMUNICACIONES PEER TO PEER 1/3 Diego Ignacio Mallea Lobera Director: Juan Antonio Magallón Lacarta Grupo de Informática Gráfica Avanzada Departamento de Informática e Ingeniería de Sistemas Centro Politécnico Superior Universidad de Zaragoza Junio de 2011 A mis padres Jorge José y María Pilar Olga, y a mis hermanas Gabriela y Eugenia, por insistirme en que termine mis estudios. A mi novia Nadia, por no reclamar el tiempo empleado. A mis amigos de toda la vida, por secuestrarme e impedirme que me centre en acabar la carrera. Derechos de Autor Los derechos de la presente obra pertenecen a D. Diego Ignacio Mallea Lobera y al Dr. D. Juan Antonio Magallón Lacarta, del Departamento de Informática e Ingeniería de Sistemas del Centro Politécnico Superior de la Universidad de Zaragoza. Queda prohibida la reproducción total o parcial de esta obra, por cualquier medio, sin el permiso escrito de los autores. Ficha Técnica Proyecto fin de carrera Título: ESTRUCTURA DE ACELERACIÓN PARA RENDER 3D DISTRIBUIDA MEDIANTE COMUNICACIONES PEER TO PEER Autor: D. Diego Ignacio Mallea Lobera DNI: 72981973-Y Promoción: 2004/2011 Especialidad: Informática Director: Juan Antonio Magallón Lacarta Departamento: Informática e Ingeniería de Sistemas Centro: Centro Politécnico Superior Universidad: Universidad de Zaragoza Fecha Junio 2011 Resumen Hoy en día, se puede afirmar que el acceso a computadoras con una gran potencia de cálculo está al alcance en nuestros hogares o puestos de trabajo. Estas pequeñas estaciones, con las que consultamos el correo o las cuentas de nuestras redes sociales, están la mayoría del tiempo sin aprovechar al máximo su poder de cálculo. Hace tiempo que programas como el SETI, Folding o figthAids entre otros aprovechan estos tiempos de baja actividad de nuestras computadoras para procesar en horas grandes cantidades de datos, las cuales requerirían de supercomputadoras que requieren de costosas inversiones y un mantenimiento tan costoso que solo grandes gobiernos u organismos pueden hacer frente. Por otro lado tenemos que ámbitos tan dispares como el cine, los videojuegos, en la aeronáutica y un largo etcétera, se hace necesario el computar ingentes cantidades de datos con cálculos increíblemente complejos. Un ámbito en el cual se tiene una serie de cálculos que se pueden paralelizar y tiene una complejidad tan alta que requiere de más de un computado, es el mundo de la animación 3D. El presente proyecto busca evaluar los fundamentos básicos tras la producción de una animación 3D, en un sistema distribuido Peer to Peer. En primera instancia se decidió el evaluar las búsquedas en árboles kd mediante el empleo de dicha red, para ello se decidió el implementar una red de dichas características para poder distribuir el cálculo y los nodos de la red. Posteriormente se implemento una serie de algoritmos comúnmente empleados para la generación de dichas escenas animadas, búsquedas en kdtree, modificando estos para poder realizar los cálculos de una manera distribuida entre los componentes de la red. Según se avanzo en el estudio se hizo patente un hambre por evaluar e investigar las posibilidades de dicho sistema para nubes de volúmenes incurriendo en unas posibilidades de investigar las posibilidades de las mismas. Tras el desarrollo del PFC, se puede concluir que el uso de redes P2P abre un sinfín de posibilidades y mejoras. Además la ampliación de dichos algoritmos del procesado de nubes de puntos a nubes de volúmenes abre posibilidades que congenian con técnicas de colisiones. Tabla de Contenidos de la Memoria I CONTENIDOS Capítulo 1. Introducción ..................................................................................... 1 1.1. Preámbulo ................................................................................................ 1 1.2. Motivación ................................................................................................ 1 1.3. Objetivos .................................................................................................. 1 1.4. Estado del Arte ......................................................................................... 2 1.5. Estructura de la Memoria ......................................................................... 3 Capítulo 2. Planificación ..................................................................................... 5 2.1. Preámbulo ................................................................................................ 5 2.2. Ciclo de vida............................................................................................. 5 2.3. Análisis de Riesgos .................................................................................. 6 2.3.1. Alta complejidad en la implantación y comprensión ....................... 6 2.3.2. Lapsos de inactividad del proyecto ................................................. 6 2.3.3. Incertidumbre de no poder cumplir con la funcionalidad adecuada 6 2.4. Conclusiones............................................................................................ 6 Capítulo 3. Contexto Tecnológico ...................................................................... 7 Ingeniería Informática Proyecto Final de Carrera Capítulo: Planificación 5 Capítulo 2. PLANIFICACIÓN 2.1. Preámbulo En este capítulo se detalla la planificación llevada en el presente proyecto, las decisiones tomadas en dicha planificación, las rectificaciones, los riesgos y desviaciones observadas, así como las conclusiones de la misma. 2.2. Ciclo de vida En el desarrollo del proyecto se decidió el uso de un ciclo de vida en espiral. Para ello se planificó realizar tres ciclos completos con el fin de poder adaptarnos a los posibles contratiempos que pudiesen surgir. Las fases de cada ciclo elegidas fueron las siguientes: Fase Descripción Determinar objetivos En esta primera fase plantearemos las metas a concluir en el ciclo. Análisis de Riesgos En esta segunda fase, evaluaremos los contratiempos que pueden obstaculizar las metas marcadas. Desarrollar y probar Llevaremos a cabo las tareas necesarias para realizar las metas planteadas. Planificación Evaluaremos el trabajo realizado en las fases de este ciclo. Tabla 2 Fases elegidas en el ciclo de vida Las primeras estimaciones nos dejaron las siguientes estimaciones: Ilustración 1 Estimación inicial del proyecto Como no podría ser de otro modo los tiempos estimados en la planificación inicial se vieron alterados totalmente, sobrepasándolo los tiempos planificados inicialmente. Debido a condiciones laborales y personales el tiempo inicialmente planificado para las distintas tareas se alargó más de lo estimado. A ello hay que añadir que el primer prototipo fue un completo desastre. Finalmente según se fueron sucediendo los ciclos, estos fueron dando una proyección más ajustada a la realidad. Ingeniería Informática Proyecto Final de Carrera Capítulo: Planificación 6 2.3. Análisis de Riesgos En la realización del presente proyecto se pueden agrupar los riesgos evaluados durante las distintas etapas en estas tres temáticas Temáticas de Riesgos Alta complejidad en la implantación y comprensión. Lapsos de inactividad del proyecto. Incertidumbre de no poder cumplir con la funcionalidad adecuada. Tabla 3 Temáticas de riesgos 2.3.1. Alta complejidad en la implantación y comprensión Ciertos algoritmos del sistema requieren un estudio altamente costoso en tiempo y complejidad. Además en la elaboración de los mismos se puede incurrir en fallos difíciles de detectar. 2.3.2. Lapsos de inactividad del proyecto Debido a condiciones laborales y personales la dedicación total se hace imposible. Existe una clara posibilidad de incurrir en grandes periodos sin actividad. El reanudar después de los periodos de inactividad puede ser complejo y lento. 2.3.3. Incertidumbre de no poder cumplir con la funcionalidad adecuada Hubo una gran incertidumbre de si se podría realizar una implementación adecuada y óptima. 2.4. Conclusiones El ciclo de vida en espiral permitió realizar un mayor seguimiento del mismo permitiendo reevaluar el estado del proyecto dando una medida de progreso del mismo más real, ya que debido a las complejidades encontradas se hacía muy difícil una planificación más convencional. Como una mejora a tener en cuenta en futuros proyectos se hace patente el tener más en cuenta los tiempos de inactividad del proyecto como un riesgo mayor del estimado en primer momento, dificultando la viabilidad del proyecto. Para más detalles ver los anexos – Planificación Ingeniería Informática Proyecto Final de Carrera Capítulo: Contexto Tecnológico 7 Capítulo 3. CONTEXTO TECNOLÓGICO 3.1. Visión Global A la hora de computar grandes cantidades de nubes de puntos, estos se reparten en una estructura de árbol kd. Esta estructura tiene como objetivo el ordenar los puntos del espacio para una óptima búsqueda en él. Cuando nuestra nube de puntos tiene unas dimensiones aceptables estas pueden ser procesadas por un único computador. Aun así, la cantidad de datos a procesar hace de este proceso una tarea costosa. Cuando nuestra nube de puntos alberga una ingente cantidad de elementos, la tarea de procesarlo e incluso almacenarlos no puede ser llevada por una sola máquina, debido a que los recursos de la misma son limitados. Con este hecho se hace patente la necesidad de compartir el procesado y el almacenamiento de dicha nube. Lógicamente la distribución de los elementos nos resuelve esta limitación, pero a su vez nos implica una serie de retos a superar. 3.2. Software y motores de Render Actualmente existen reconocidas aplicaciones de modelado 3D y render populares, tales como 3ds MAX y V-Ray, que procesan en forma distribuida de manera sencilla y transparente para el usuario. Otro motor de render famoso es Mental Ray. La última generación de motores de render, además de distribuir el proceso final en varios equipos o nodos de render, permite utilizar esta misma potencia de procesamiento para hacer el render en pantalla, aplicando cambios en tiempo real. V-Ray RT es precisamente uno de estos tipos de software. Estas modificaciones sobre luces, cámaras, y posiciones de objetos, evita la necesidad de realizar múltiples renderizados previos de estudio, lo redunda en un ahorro muy significativo de tiempo. Ingeniería Informática Proyecto Final de Carrera Capítulo: Contexto Tecnológico 8 3.3. Limitaciones de los sistemas de render actuales 3.3.1. Granjas de render no especializadas: Principalmente hay dos limitaciones básicas: Limitación Consecuencia En disponibilidad Los ordenadores deben estar disponibles por tiempo indeterminado, es decir, lo necesario para completar el proceso global de render. En heterogeneidad La heterogeneidad entre los equipos, lo más usual, en un entorno de oficina, obliga a esperar a que concluya el render en el equipo más lento para disponer del render completo. Tabla 4 limitaciones básicas de las granjas de render 3.3.2. Granjas de render profesionales: Requieren de un entorno controlado, acondicionamiento de instalaciones para un alto rendimiento. Sus instalaciones requieren de una compleja cantidad de elementos. Nodos de render Switch de conectividad Switch de monitoreo Servidor de archivos UPS Servidor de backup Y un largo etcétera de otras cosas En conclusión requieren de una infraestructura específica y costosa. Muchas veces no asequibles por pequeñas organizaciones y sobre todo caras de mantener. Como alternativa existe la posibilidad de alquilar estos servicios. 3.4. Sistemas distribuidos de datos Actualmente existen diversas maneras de almacenar datos de manera distribuida. Tipos de Sistemas de almacenamiento distribuidos Bases de datos distribuidas. Tablas hash distribuidas. Sistemas de índice centralizados. Sistemas personalizados. Tabla 5 Tipos de Sistemas de almacenamiento distribuidos Ingeniería Informática Proyecto Final de Carrera Capítulo: Contexto Tecnológico 9 3.4.1. Bases de datos Distribuidas Las bases de datos distribuidas nos permiten almacenar los datos en varias máquinas y/o volúmenes. Ventajas de una base de datos distribuida: Ventaja Descripción Refleja una estructura organizacional Los fragmentos de la base de datos se ubican en los departamentos a los que tienen relación. Autonomía local Un departamento puede controlar los datos que le pertenecen. Disponibilidad Un fallo en una parte del sistema solo afectará a un fragmento, en lugar de a toda la base de datos. Rendimiento Los datos generalmente se ubican cerca del sitio con mayor demanda, también los sistemas trabajan en paralelo, lo cual permite balancear la carga en los servidores. Economía Es más barato crear una red de muchas computadoras pequeñas, que tener una sola computadora muy poderosa. Modularidad Se pueden modificar, agregar o quitar sistemas de la base de datos distribuida sin afectar a los demás sistemas (módulos). Tabla 6 Ventajas de una base de datos distribuida Desventajas de una base de datos distribuida Desventaja Descripción Complejidad Se debe asegurar que la base de datos sea transparente, se debe lidiar con varios sistemas diferentes que pueden presentar dificultades únicas. El diseño de la base de datos se tiene que trabajar tomando en cuenta su naturaleza distribuida, por lo cual no podemos pensar en hacer joins que afecten varios sistemas. Economía La complejidad y la infraestructura necesaria implica que se necesitará una mayor mano de obra. Seguridad Se debe trabajar en la seguridad de la infraestructura así como cada uno de los sistemas. Integridad Se vuelve difícil mantener la integridad, aplicar las reglas de integridad a través de la red puede ser muy caro en términos de transmisión de datos. Falta de experiencia Las bases de datos distribuidas son un campo poco común por lo cual no existe mucho personal con experiencia o conocimientos adecuados. Carencia de estándares Aún no existen herramientas o metodologías que ayuden a los usuarios a convertir un DBMS centralizado en un DBMS distribuido. Diseño de la base de datos se vuelve más complejo Además de las dificultades que generalmente se encuentran al diseñar una base de datos, el diseño de una base de datos distribuida debe considerar la fragmentación, replicación y ubicación de los fragmentos en sitios específicos. Diseño intrínseco Las bases de datos en general no están preparadas para la consulta de una estructura de árbol. Aunque existen diversas instrucciones SQL no estándar para trabajar con árboles, estas funcionan en base a costosos cálculos las cuales no las hacen óptimas para el uso por sistemas de render. Tabla 7 Desventajas de una base de datos distribuida Ingeniería Informática Proyecto Final de Carrera Capítulo: Contexto Tecnológico 10 3.4.2. Tablas hash Distribuidas Las tablas de hash distribuidas (DHTs), son una clase de sistemas distribuidos descentralizados que proveen un servicio de búsqueda similar al de las tablas de hash, donde pares (clave, valor) son almacenados en el DHT, y cualquier nodo participante puede recuperar de forma eficiente el valor asociado con una clave dada. La responsabilidad de mantener el mapeo de las claves a los valores está distribuida entre los nodos, de forma que un cambio en el conjunto de participantes causa una cantidad mínima de interrupción. Esto permite que las DHTs puedan escalar a cantidades de nodos extremadamente grandes, y que puedan manejar constantes errores, llegadas y caídas de nodos. 3.4.3. Sistemas de índice centralizados Consiste en sistemas donde el índice de donde están los datos está en uno o varios equipos dedicados. Implica una interacción muy férrea con el sistema encargado de indexar la información. Si estos sistemas de indexado caen, cae todo el sistema. Además existe un claro cuello de botella en los equipos indexadores. 3.4.4. Sistemas personalizados Implica la implementación de algoritmos de relación y un algoritmo de mantenimiento. La mayoría de las veces incurren en costosos tiempos de desarrollo, pudiendo caer en no abordar todas las posibles situaciones. 3.5. Estado de las técnica 3.5.1. Los algoritmos El campo de los algoritmos usados en los sistemas de render está muy estudiado. Hoy en día se sabe cuáles son los mejores algoritmos y optimizaciones para procesar una escena 3D. Técnica Fundamentos Físicos Sombreado de Gouraud Luz ambiente y difusa. Sombreado de Phong Luz ambiente, difusa y especular. Raytracing Simular luz como rayo, iluminación global. Mapeado de fotones Basado en Montecarlo, iluminación global. Radiosidad Equilibrio de energía. Tabla 8 Algoritmos usados en los sistemas de render En general el mundo de las imágenes sintéticas, cuando queremos sintetizar un fotograma de nuestra escena debemos mezclar distintos algoritmos con sus optimizaciones. Por ejemplo cuando se quiere simular una escena donde hay una niebla, se hacen los ajustes pertinentes para poder optimizar su procesamiento al máximo. Así es normal ver infinidad de publicaciones que mejoran la precisión y el realismo de un render bajo ciertas condiciones. Ingeniería Informática Proyecto Final de Carrera Capítulo: Contexto Tecnológico 11 3.5.2. Las redes de pares Alejándonos de las polémicas que salpican los medios de comunicación. Las redes de pares no se limitan a compartir archivos de dudosa legalidad. Estos sistemas se basan en la idea de compartir recursos directamente entre dos equipos de red. De este paradigma se han aprovechado proyectos para hacer posible la realización de tareas faraónicas en esta era digital. Ejemplo famosos de redes P2P Quitando los sistemas de compartición de datos, aquí nombro algunos de los proyectos reseñables. Proyecto Finalidad SETI@HOME Búsqueda de inteligencia extraterrestre. BOINC Proyecto para la compartición de los recursos con diversos fines científicos. Netsukuku Es el intento por levantar una red completamente distribuida sin puntos únicos de fallo. Tabla 9 Ejemplo famosos de redes P2P Características deseables en una red P2P Entre las características deseables en este tipo de redes destacamos: Característica Descripción Escalabilidad El sistema tiene que permitir escalar sin verse comprometida la eficiencia en general. Lo ideal es que cuanto mayor es el número de participantes más eficiente se vuelva el sistema. Robustez En estos sistemas se consigue la tolerancia a fallos mediante la redundancia de los recursos. Además en sistemas puros la necesidad de un sistema de índice queda solventada, no habiendo ningún punto singular de fallo. Descentralización Son sistemas descentralizados, todos los nodos son iguales. Por lo tanto no hay ningún nodo con una funcionalidad especial. Distribución de costes Los recursos individuales son compartidos por el sistema. Permitiendo su uso por cualquier nodo de la red. Anonimato Es una característica deseable en sistemas que sobrepasan el ámbito controlado de una organización. Seguridad Cuando el sistema escapa de los dominios de una organización. Se hace necesario el implementar en el sistema formas de evitar posibles nodos maliciosos, así como posibles espionajes o alteraciones de los datos de la red. Tabla 10 Características deseables en una red P2P Ingeniería Informática Proyecto Final de Carrera Capítulo: Contexto Tecnológico 12 Tipos de redes P2P Las redes P2P según el grado de centralización se pueden clasificar: Tipo Descripción Centralizadas Se rige bajo un único servidor, este servidor sirve de punto de enlace entre los distintos nodos. Todas las comunicaciones dependen del servidor. Híbridas, semicentralizadas o mixtas El servidor sirve de HUB y administrador de los recursos. Suelen permitir también trabajar en un funcionamiento de tipo puro. Puras Totalmente descentralizadas. Todos los nodos funcionan como cliente y servidor. Tabla 11 Tipos de redes P2P Ingeniería Informática Proyecto Final de Carrera Capítulo: Descripción del Sistema 13 Capítulo 4. DESCRIPCIÓN DEL SISTEMA 4.1. Preámbulo Nuestro sistema se va a encargar de evaluar una serie de algoritmos típicos del render permitiendo la distribución de los cálculos y los datos de una manera descentralizada. 4.2. Diagrama del sistema Descripción El sistema a nivel global, estaría compuesto de varias estaciones de render. Cada estación haría las veces de cliente y servidor. Dichas estaciones se conectarían unas a otras mediante redes internas y/o internet. A nivel lógico la conexión se haría punto a punto, es decir no habría intervención de terceros a la hora comunicarse, básicamente las estaciones trabajarían en el enrutamiento. Tabla 12 Diagrama del sistema Ilustración 2 Diagrama del sistema Ingeniería Informática Proyecto Final de Carrera Capítulo: Descripción del Sistema 20 Funcionalidades relacionadas con las estaciones de render Ilustración 9 Funcionalidades relacionadas con las estaciones de render Funcionalidad Añadir estaciones. Cargar estaciones. Configurar la redistribución de las estaciones conocidas en la red. Monitorizar el estado de las estaciones. Guardar las estaciones. Eliminar estaciones. Listar estaciones. Exportar estaciones. Importar estaciones. Propagar estaciones. Consultar estaciones remotas. Tabla 21 Funcionalidades relacionadas con las estaciones de render System Usuario p2p::gui p2p::controller añade estación carga estaciones configura estaciones elimina estación lista estaciones monitoriza estaciones salva estaciones añade estación carga módulo estaciones configura módulo estaciones elimina estación lista estación salva módulo estaciones consulta estaciones consulta estaciones remotas exporta estaciones importa estaciones Ingeniería Informática Proyecto Final de Carrera Capítulo: Descripción del Sistema 21 Funcionalidades relacionadas con las formas Ilustración 10 Funcionalidades relacionadas con las formas Funcionalidad Gestión de las formas Configurar la redistribución de las formas en la red Monitorizar las formas. Estadísticas de las formas. Añadir formas Eliminar formas Guardar formas Cargar formas Listar formas Exportar formas Importar formas Propagar formas Obtener formas remotas Tabla 22 Funcionalidades relacionadas con las formas System p2p::gui p2p::controller Usuario añade forma carga formas configura formas consulta formas elimina formas exporta formas importa formas salva formas representa formas añade forma carga módulo formas configura módulo formas consulta formas remotas elimina forma propaga formas salva formas propaga formas lista formas lista formas Ingeniería Informática Proyecto Final de Carrera Capítulo: Descripción del Sistema 22 Funcionalidades relacionadas con el árbol kd Ilustración 11 Funcionalidades relacionadas con el árbol kd Funcionalidad Gestión del árbol kd. Generación del árbol kd. Configuraciones relacionadas con el árbol. Estadísticas del árbol. Salva el árbol. Carga el árbol. Exporta el árbol. Importa el árbol. Propaga el árbol. Representa el árbol. Tabla 23 Funcionalidades relacionadas con el árbol kd System p2p::gui p2p::controller Usuario carga árbol importa árbol representa árbol salva árbol exporta árbol genera árbol configura árbol carga módulo árbol configura módulo árbol genera árbol recupera árbol salva módulo árbol Ingeniería Informática Proyecto Final de Carrera Capítulo: Descripción del Sistema 23 Funcionalidades de simulación Ilustración 12 Funcionalidades de simulación Funcionalidad Búsqueda local del punto más cercano. Búsqueda local contenidos en una esfera. Búsqueda local contenidos en un cubo. Búsqueda distribuida del punto más cercano. Búsqueda distribuida contenidos en una esfera. Búsqueda distribuida contenidos en un cubo. Configuración de la simulación. Tabla 24 Funcionalidades de simulación 4.3.8. El modelo Los datos que deben ser almacenados por las estaciones de render son: Datos Descripción De las estaciones de render En cada estación se almacena una cache de estaciones de render. Del listado de formas En cada estación se almacena una parte del modelo de formas. Del Árbol kd En cada estación se almacena una parte del árbol kd. De la configuración El estado de las automatizaciones y configuraciones realizadas en la estación. Tabla 25 El modelo System p2p::controllerp2p::gui Usuario búsqueda distribuida contenidos en cubo búsqueda distribuida contenidos en esfera búsqueda distribuida mas cercano búsqueda local contenidos en cubo búsqueda local contenidos en esfera búsqueda local mas cercano configura simulación búsqueda distribuida contenidos en cubo búsqueda distribuida contenidos en esfera búsqueda distribuida mas cercano búsqueda local contenidos en cubo búsqueda local contenidos en esfera búsqueda local mas cercano configura módulo simulación Ingeniería Informática Proyecto Final de Carrera Capítulo: Descripción del Sistema 24 Cache de estaciones de render Cada estación de la red para realizar simulaciones debe comunicarse con el resto de la red. Con el fin de agilizar las comunicaciones se almacena una pequeña cache con los datos de enrutamiento de las mismas. Esta cache contendrá no necesariamente el listado de todas las estaciones de la red. En caso de que el tamaño de la red sobrepase unas dimensiones considerables se hará uso de un enrutamiento mediante una red overlay. Listado de formas Nuestro modelo a simular generara un árbol kd mediante un listado con datos de las formas que están representadas en el espacio 3D. El tamaño de dichas formas puede ser lo suficientemente grande para no dar cabida en un solo computador. Por ello el almacenamiento de los datos ha de ser distribuido por las estaciones de render para su posterior procesado. Para dotar al sistema de mayor seguridad habrá redundancia de los datos. Ingeniería Informática Proyecto Final de Carrera Capítulo: Descripción del Sistema 25 El árbol kd Para la generación del árbol, podremos aplicar distintas técnicas de generación. Técnica Descripción Raíz común Todas las estaciones de la red tienen una raíz del árbol común, dicha raíz contiene ramas del árbol que están almacenadas en otras estaciones de la red. Árboles dependientes El árbol está fragmentado en pequeños subárboles incompletos, dichos subárboles tienen nodos que están almacenados en otras estaciones de la red. Árboles independientes Cada estación genera su propio árbol con el listado de formas locales. Tabla 26 Técnicas de generación y reparto del árbol kdtree Según la situación a simular puede ser interesante optar por uno o por otro. Se podría implementar un reparto del árbol en el cual cada estación se ocupe de un área del espacio, por tener esta mas interés en realizar búsquedas en su zona asignada. Por lo que sería interesante que el reparto no fuese aleatorio. En nuestro caso nos centraremos en la búsqueda mediante arboles independientes, ya que nos interesa evaluar las prestaciones de ciertos algoritmos que no tiene cabida este tipo de reparto. Ilustración 13 Técnicas de generación y reparto del árbol kdtree Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 27 Capítulo 5. SOLUCIÓN PROPUESTA 5.1. Preámbulo Vamos a evaluar la solución propuesta. Para ello analizaremos las diferentes tecnologías existentes en el mercado y las decisiones que nos han llevado a adoptar unas frente a otras. 5.2. Sistema de comunicación En las comunicaciones de red se quería un sistema que fuera lo más simple posible, obviándonos del duro trabajo de una implementación de cero, pero además que fuera lo suficientemente optimo para que dichas comunicaciones no representasen un problema elevado de rendimiento. Las opciones evaluadas fueron: Sistema de comunicación RMI WEBSERVERS SOCKETS RPC Tabla 27 Sistema de comunicación 5.2.1. Análisis de los sistemas de comunicación mediante Servicios Web El uso de Servicios Web no cumplen con la necesidad de realizar unas comunicaciones lo más optimas posibles al sobredimensionar en exceso las llamadas. 5.2.2. Análisis de los sistemas de comunicación mediante Sockets En el caso de los Sockets nos implica una implementación demasiado a bajo nivel. Aunque es bastante optima en cuanto a tamaño de datos. 5.2.3. Análisis de los sistemas de comunicación mediante RPC En el caso de RPC, los que utilizan el estándar IDL tienen una alta compatibilidad, pero su rendimiento depende en gran medida de la implementación realizada por cada uno de los actores en el juego. Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 28 5.2.4. Análisis de los sistemas de comunicación mediante RMI Teniendo como gran contra, el ser una comunicación cerrada al lenguaje Java, se opto por esta solución, al estar lo suficientemente madura y aportar una simplicidad a nuestras comunicaciones. El uso de RMI posibilita el envió de clases serializadas entre los actores. Como previsión se ha decidido el dar modularidad al núcleo de la aplicación, en previsión de poder en un futuro ampliar éste con la incorporación de distintos módulos que den soporte a otras formas de comunicación. 5.3. Interfaz de Usuario Entre las alternativas para interactuar en la aplicación tenemos las siguientes: Tipo de interfaz Línea de comandos. Entorno Web. Entorno de escritorio. Sistema empotrado. Tabla 28 Tipos de interfaz 5.3.1. Línea de comandos El uso de un entrono de línea de comandos se hace demasiado complicado para un usuario estándar. 5.3.2. Entorno Web Un entorno Web es muy interesante, en un principio se inicio su implantación. Pronto se hizo patente de que eleva la complejidad de nuestra aplicación a niveles demasiado elevados y entorpece su distribución al público en general, al tener que instalarse un servidor de aplicaciones Web. 5.3.3. Sistema empotrado Dados los medios materiales disponibles, se descarto esta posibilidad. 5.3.4. Entorno de Escritorio El uso de una solución de escritorio nos simplificó la implantación de la solución, permitiendo el uso de herramientas gráficas para presentar los datos al usuario con unos costes medios de tiempo, frente a su implementación en un entorno Web. Debido a las posibilidades del desarrollo futuro de un entorno Web para la supervisión de la aplicación se ha decidido implementar la estructura de la aplicación siguiendo el patrón de diseño MVC. Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 29 5.4. Formato de almacenamiento de los datos A la hora de utilizar una fuente de datos se nos presentan las siguientes alternativas: Formatos evaluados Utilizar una base de datos. Utilizar objetos con serialización estándar. Utilizar XML. Utilizar objetos con serialización personalizada. Tabla 29 Formatos de almacenamiento de los datos 5.4.1. Análisis del uso de una Base de datos El uso de una base de datos implicaría el uso de un gestor de BD, que aunque hay gestores incrustados en aplicaciones, no nos proporciona una estructura óptima para almacenar y acceder a un árbol kd. 5.4.2. Análisis del uso de XML Utilizar XML nos sobredimensiona el tamaño de los datos, ocupando demasiado la estructura del formato frente al elemento a almacenar. 5.4.3. Análisis del uso de Objetos con serialización El uso de una serialización estándar nos ocupa una memoria reducida pero esta puede ser mejorable. 5.4.4. Análisis del uso de Objetos con serialización personalizada El uso de una serialización personalizada nos permitiría un uso óptimo de los recursos. Finalmente se ha optado por una serialización personalizada con el fin de optimizar el uso de la memoria. Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 36 5.8. Modelado del Controlador Ilustración 19 Modelado del Controlador Descripción El controlador esta subdividido en varios módulos. Cada módulo proporciona una serie de funcionalidades básicas a la aplicación. La descripción de dichas funcionalidades básicas está descrita por módulos abstractos, con el fin de poder ampliar dicha funcionalidad, manteniendo la compatibilidad de las distintas versiones. Tabla 38 Modelado del Controlador p2p::controller controller::Controller +close() +getKdTree(): AbstractModuleModelKdTree +getMonitor(): AbstractModuleMonitor +getServices() +getShapes(): AbstractModuleModelShapes +getSimulation(): AbstractModuleSimulation +getStations(): AbstractModuleModelStations +getTasks(): AbstractModuleTasks controller::AbstractModule +PROP_NAME: String +addEventListener(eventName: String, listener: ActionListener) +addPropertyChangeListener(propertyName: String, listener: VeotableChangeListener) +addVetoableChangeListener(propertyName: String, listener: VetoableChangeListener) +close() +getName(): String +getPropertie(key: String): Object +getProperties(): Map<String,Object> +removeEventListener(eventName: String, listener: ActionListener) +removePropertyChangeListener(propertyName: String, listener: PropertyChangeListener) +removeVetoableChangeListener(propertyname: String, listener: VetoableChangeListener) +setPropertie(key: String, value: Object) controller::AbstractModuleModel +ACTION_LOAD: String +ACTION_SAVE: String +PROP_FILE_NAME: String +PROP_MODEL: String +generate(int size): T +getClassTypes(): Vector<Class> +getColumnsEditables(): Vector<Boolean> +getEncabezados(): Vector<String> +getFileName(): String +getListado(): Vector<Vector<Object>> +getModel(): T +load(fileName: String): boolean +load(): boolean +save(fileName: String): boolean +save(): boolean +setFileName(filename: String) controller::AbstractModuleModelKdTree controller::AbstractModuleModelShapes controller::AbstractModuleModelStations controller::AbstractModuleMonitor controller::AbstractModuleTasks controller::AbstractModuleSimulation Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 37 5.8.1. Modelado del módulo del controlador de servicios Ilustración 20 Modelado del módulo del controlador de servicios Descripción El módulo de servicios es el eje principal de la aplicación en el ámbito de las comunicaciones. Este módulo es el que se encarga de de dar soporte a las comunicaciones con otras estaciones de render. Tabla 39 Modelado del módulo del controlador de servicios controller::AbstractModule services services::ServicesRMI +addShapes(host: String, port: int, shapes: Collection<AbstractShape>): boolean +findEsferica(host: String, port: int, s: Sphere): List<AbstractShape> +findNear(host: String, port: int, po: coordinate): List<AbstractShape> +findOrtogonal(host: String, port: int, c: Cube): List<AbstractShape> +generateKdTree(host: String, port: int) +getshapesCount(host: String, port: int): int +isActived(host: String, port: int, nombre: String): boolean +isFree(host: String, host: int): boolean +mostrarServiciosCliente(host: String, port: int): String[] +mostrarServiciosServidor(host: String, port: int): String[] +ping(host: String, port: int): Date +propagateShapes(host: String, port: int): boolean +setKdTree(host: String, port: int, root: AbstractNode) +start(host: String, port: int, nombre: String): boolean +stop(host: String, port: int, nombre: String): boolean +updateShapes(host: String, port: int): List<AbstractShape> +updateStations(host: String, port: int): Set<AbstractStation> services::InterfaceServicesRMI controller::AbstractModuleServices +ACTION_CONSULT: String +ACTION_PING: String +ACTION_UPDATE_STATIONS: String +ACTION_UPDATE_SHAPES: String +ACTION_ADD_SHAPES: String +ACTION_GET_SHAPES_COUNT: String +ACTION_PROPAGATE_SHAPES: String +ACTION_GENERATE_KDTREE: String +ACTION_SET_KDTREE: String +ACTION_FIND_ORTOGONAL: String +ACTION_FIND_ESFERICA: String +ACTION_FIND_NEAR: String +ACTION_FROM_STATION: String +ACTION_TO_STATION: String +ACTION_FAILED_TO_STATION: String +ACTION_FAILED_FROM_STATION: String +PROP_MODULE: String +PROP_PORT: String +PROP_HOST: String +PROP_SERVICE: String +PROP_CONNECTED: String +PROP_TIMER_BETWEN_PING: String +PROP_TIMER_BETWEN_UPDATE_OF_STATIONS: String +addShapes(station: AbstractStation, shape: AbstractShape): boolean +addShapes(host: String, port: int, shape: AbstractShape): boolean +consult(station: AbstractStation): String[] +consult(host: String, port: int): String[] +findEsferica(host: String, port: int, s: Sphere): List<AbstractShape> +findEsferica(station: AbstractStation, s: Sphere): List<AbstractShape> +findNear(host: String, port: int, po: Coordinate): List<AbstractShape> +findNear(station: AbstractStation, po: Coordinate): List<AbstractShape> +findOrtogonal(host: String, port: int, c: Cube): List<AbstractShape> +findOrtogonal(station: AbstractStation, c: Cube): List<AbstractShape> +generateKdTree(host: String, int: Port) +generateKdTree(station: AbstractStation): boolean +getHost(): String +getInstance() +getLocalStation(): AbstractStation +getPort(): int +getServicio(): String +getShapesCount(station: AbstractStation): int +getShapesCount(host: String, int: Port): int +isActived(): boolean +ping(station: AbstractStation): boolean +ping(host: String, int: Port): Date +propagateShapes(station: AbstractStation): boolean +propagateShapes(host: String, int: Port): boolean +setHost(host: String) +setKdTree(host: String, int: Port, root: AbstractNode) +setKdTree(station: AbstractStation, root: AbstractNode): boolean +setPort(port: int) +start() +stop() +updateShapes(station: AbstractStation): boolean +updateShapes(host: String, int: Port): List<AbstractShape> +updateStations(station: AbstractStation): boolean +updateStations(host: String, int: Port): Set<AbstractStation> Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 38 5.8.2. Modelado del módulo del controlador del listado de estaciones de render Ilustración 21 Modelado del módulo del controlador del listado de estaciones de render Descripción El módulo del listado de estaciones es el encargado de gestionar localmente las estaciones de render que posteriormente serán utilizadas como cache local en las operaciones remotas. Tabla 40 Modelado del módulo del controlador del listado de estaciones de render 5.8.3. Modelado del módulo del controlador de formas Ilustración 22 Modelado del módulo del controlador de formas Descripción El modulo del listado de formas es el encargado de gestionar localmente las formas que posteriormente se almacenarán en el árbol. Tabla 41 Modelado del módulo del controlador de formas controller::AbstractModuleModelStations +ACTION_ADD_STATION: String +ACTION_GENERATE: String +ACTION_REMOVE_STATION: String +PROP_MODULE: String +addStation(station: AbstractStation): boolean +addStation(host: String, port: int): boolean +generateStation(host: String, port: int): AbstractStation +getInstance(): AbstractModuleModelStation +getStation(host: String, port: int): AbstractStation +removeStation(station: AbstractStation): boolean +removeStation(host: String, port: int): boolean controller::AbstractModuleModel controller::ModuleModelStations controller::AbstractModuleModel controller::AbstractModuleModelShapes +ACTION_ADD_SHAPE: String +ACTION_GENERATE: String +ACTION_REMOVE_SHAPE: String +PROP_MODULE: String +addShape(shape: AbstractShape) +getInstance(): AbstractModuleModelShapes +removeShape(shape: AbstractShape): boolean controller::ModuleModelShapes Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 39 5.8.4. Modelado del módulo del controlador de árbol kd Ilustración 23 Modelado del módulo del controlador de árbol kd Descripción El módulo del árbol kd nos permite gestionar y navegar por el árbol. Tabla 42 Modelado del módulo del controlador de árbol kd 5.8.5. Modelado del módulo del controlador de simulación Ilustración 24 Modelado del módulo del controlador de simulación Descripción El módulo de simulación nos servirá para procesar los distintos algoritmos a evaluar, tanto los de ámbito local como distribuido. Tabla 43 Modelado del módulo del controlador de simulación controller::AbstractModuleModel controller::AbstractModuleModelKdTree +ACTION_FAILED_GENERATE: String +ACTION_GENERATE: String +PROP_AUTOMATIC_GENERATE: String +PROP_COUNT_LEAFS: String +PROP_COUNT_LEVELS: String +PROP_COUNT_NODES: String +PROP_MODULE: String +PROP_TIME_BUILD: String +PROP_TIME_COUNT_LEAFS: String +PROR_TIME_COUNT_LEVELS: String +PROP_TIME_COUNT_NODES: String +generate() +generateNode(shape: AbstractShape, parent: AbstractNode, left: AbstractNode, rigth: AbstractNode): AbstractNode +generateNode(shape: AbstractShape, parent: AbstractNode): AbstractNode +generateNode(shape: AbstractShape): AbstractNode +getInstance(): AbstractModuleModelKdTree controller::ModuleModelKdTree controller::AbstractModule AbstractModuleSimulation +ACTION_FIND_AREA: String +PROP_AUTOMATIC_AREA: String +PROP_COUNT_PROPAGATE: String +PROP_FIND_SHAPES: String +PROP_LIST_SHAPES: String +PROP_LIST_FINDED_VALUES: String +PROP_MODULE: String +PROP_PROPAGATION_MODE: String +PROP_TIME_FIND_AREA: String +PROP_TIME_PROPAGATE: String +distribuitedFindEsferica(sphere: Sphere): List<AbstractShape> +distribuitedFindNear(po: Coordinate): List<AbstractShape> +distribuitedFindOrtogonal(Cube cube): List<AbstractShape> +getInstance(): AbstractModuleSimulation +localFindEsferica(sphere: Sphere): List<AbstractShape> +localFindNear(po: Coordinate): List<AbstractShape> +localFindOrtogonal(c: Cube): List<AbstractShape> +propagate() +propagateShapes() +refreshCount() controller::ModuleSimulation Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 40 5.8.6. Modelado del módulo del controlador de monitorización Ilustración 25 Modelado del módulo del controlador de monitorización Descripción El módulo de monitorización nos permite hacer un seguimiento del estado de los procesos, permitiendo mostrarnos un seguimiento selectivo de la aplicación. Tabla 44 Modelado del módulo del controlador de monitorización 5.8.7. Modelado del módulo del controlador de tareas Ilustración 26 Modelado del módulo del controlador de tareas Descripción El módulo de tareas es una implementación de un programador de tareas. Nos permite hacer ejecución paralela. En este caso implementamos el interfaz de java java.util.concurrent.ScheduledExecutorService para este cometido. Tabla 45 Modelado del módulo del controlador de tareas Para más detalles ver los anexos – Análisis controller::AbstractModule controller::AbstractModuleMonitor +PROP_MODULE: String +TRAZA_NAME: String +addError(o: Object, metodo: String, mensaje: String) +addError(c: Class, metodo: String, mensaje: String) +addException(o: Object, metodo: String, mensaje: String, e: exception) +addException(c: Class, metodo: String, mensaje: String, e: Exception) +addHandler(handler: Handler) +addInfo(o: Object, metodo: String, mensaje: String) +addInfo(c: Class, metodo: String, mensaje: String) +close() +getModule(): AbstractModuleMonitor +removeHandlers() controller::ModuleMonitor controller::AbstractModule controller::ModuleTasks AbstractModuleTasks +PROP_MODULE: String +getInstance(): AbstractModuleTasks ScheduledExecutorService Ingeniería Informática Proyecto Final de Carrera Capítulo: Solución propuesta 41 5.9. Modelado de la Vista Ilustración 27 Modelado de la Vista Descripción La vista estará compuesta por una serie de componentes que dispararan distintas funcionalidades del controlador. Tendremos una clase principal que servirá para ir posicionando los distintos componentes que serán accedidos mediante la barra de menú. Tabla 46 Modelado de la Vista Para más detalles ver los anexos – Análisis p2p::gui gui::DesktopView gui::DesktopApp gui::AbstractDesktop gui::components gui::menus menus::items components::AbstractTab components::SectionConsole components::SectionmonitorAplication components::SectionMonitorModules components::TabKdTreeDraw components::TabKdTreeTools components::TabServicesTools components::TabShapesList components::TabShapesDraw components::TabShapesTools components::TabSimulationDraw components::TabSimulationFindDistribuida components::TabSimulationFindLocal components::TabSimulationTools components::TabStationsDraw components::TabStationsListcomponents::TabStationsTools menus::MenuBarDefault menus::MenuKdTree menus::MenuServices menus::MenuShapes menus::MenuSimulation menus::MenuStations items::MenuItemKdTreeDownload items::MenuItemKdTreeDraw items::MenuItemKdTreeGenerate items::MenuItemKdTreeLoad items::MenuItemKdTreeSave items::MenuItemKdTreeTools items::MenuItemKdTreeUpload items::MenuItemServicesStart items::MenuItemServicesStop items::MenuItemServicesTools items::MenuItemShapesDownload items::MenuItemShapesDraw items::MenuItemShapesGenerate items::MenuItemShapesList items::MenuItemShapesLoad items::MenuItemShapesPropagate items::MenuItemShapesSave items::MenuItemShapesTools items::MenuItemShapesUpload items::MenuItemSimulationDraw items::MenuItemSimulationFindDistribuida items::MenuItemSimulationFindLocal items::MenuItemSimulationTools items::MenuItemStationsDownload items::MenuItemStationsDraw items::MenuItemStationsGenerate items::MenuItemStationsList items::MenuItemStationsLoad items::MenuItemStationsSave items::MenuItemStationsTools items::MenuItemStationsUpload Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 43 Capítulo 6. ESTUDIO DE LOS RESULTADOS 6.1. Preámbulo Para evaluar el sistema, habremos de calcular el sistema en diferentes situaciones. Aquí se resume el resultado de llevar a cabo dichos estudios. 6.2. Objeto de estudio El objeto de estudio es el rendimiento del sistema en un ámbito distribuido, para ello se realizaran los experimentos en un sistema sin distribuir para posteriormente realizar las mismas en un sistema distribuido. 6.3. Tipos de experimentos llevados a cabo Los experimentos llevados a cabo son: Tipos de Experimentos La búsqueda de elementos contenidos en un cubo ortogonal. La búsqueda de los elementos contenidos en una esfera. La búsqueda del elemento más cercano a una coordenada. Tabla 47 Tipos de Experimentos 6.4. Procedimiento llevado en los experimentos Con el fin de analizar el rendimiento medio de los experimentos, se procederá de la siguiente forma. Por cada experimento se evaluaran distintos tamaños de muestra. 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000 6500 7000 7500 8000 8500 9000 9500 10000 Tabla 48 tamaños de muestra El experimento se repetirá un total de 100 veces con muestras generadas aleatoriamente por cada una de las repeticiones. Así se realizaran 100 experimentos de búsqueda en una esfera con un tamaño de muestra de 500 elementos y cada uno de los experimentos se regenerara el espacio de muestras. Co los resultados de la experimentación con estos distintos tamaños de muestras obtendremos el comportamiento de los algoritmos. El uso de un tamaño de muestra nulo, nos permitirá calcular el tiempo base de las distintas configuraciones, permitiendo tener una apreciación de los tiempos perdidos en operaciones distintas del cálculo de los algoritmos de búsqueda. Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 44 6.5. Modo de generación de las muestras De los tres modos de generación después de unas pruebas iniciales calculando los tiempos base de las tres posibilidades de generación: El modo de generación elegido ha sido el de generar arboles independientes, esto es debido a que los tiempos de red son costosos. Si eligiéramos cualquiera de las otras dos opciones las operaciones de red se levarían a niveles que no justificarían la elección. El uso de las otras opciones tiene sentido si quisiéramos que cada nodo analizara un espacio concreto del espacio. Por ejemplo imaginemos un mundo virtual, cada ser de ese mundo es consciente solo de su alrededor de su mundo. A la hora de visualizar esa parte del mundo con sus datos podría generar la imagen de su mundo. Como mucho si tuviera que ver a la distancia pediría datos a un nodo de dicha área, que con probabilidad contendría los datos que necesitaría. Se podría decir que el árbol está repartido a las estaciones según su geolocalización dentro de ese mundo. Dado que lo que queremos evaluar es su rendimiento sobre ciertos algoritmos estos otros modos de reparto del árbol no tienen cabida. Ilustración 28 Opciones de generación Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 45 6.6. Entorno de pruebas En nuestro entorno de pruebas vamos a realizar las pruebas sobre dos estaciones en red, como distribuidor un ROUTER WIFI. ROUTER Cable Modem XDSL Wireless 802.11 b/g/Turbo G. Tabla 49 Router Estación A (LOCAL) Sistema operativo Windows Vista Home Premiun sp2 32 bits Memoria RAM 4 GB Procesador Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz 2.32GHz Adaptador de red D-Link DWL-G122 Adapter Wifi USB 54 Tabla 50 Maquina A (Local) Estación B (REMOTA) Sistema operativo Windows 7 32 bits Memoria RAM 4 GB Procesador AMD Turion (tm) 64 X2 Mobile Technology TL-64 2.20 GHz Adaptador de red Broadcom 4321AG 802.11a/b/g/draft-n Wi-Fi Adapter Tabla 51 Maquina B (Remota) La estación A será la que ejecute las pruebas, con lo que en las llamadas el enrutamiento para las pruebas distribuidas será a nivel de la propia maquina. La estación B sufrirá los retrasos de enrutamiento por el ROUTER. Estación A (LOCAL) Estación B (REMOTA) Ilustración 29 Entorno de pruebas Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 52 Análisis del cálculo del tiempo base de la estación A con uso de red en local y sin uso de red Ilustración 37 Tiempo base de la estación A con uso de red en local y sin uso de red Descripción Si comparamos los tiempos anteriores descubriremos que el tiempo perdido en protocolos de red es bastante elevado. −842919,3333 𝑛𝑠 1844,8333 𝑛𝑠 841074,499967 𝑛𝑠 Como podemos observar el tiempo perdido en los protocolos de red hace insignificante el tiempo perdido en otras operaciones, en la grafica casi se solapan al ser tan próximos. Tabla 56 Tiempo base de la estación A con uso de red en local y sin uso de red Búsqueda Ortogonal Búsqueda Esferica Búsqueda Cercano PROMEDIO Tiempo en ns con protocolos de red 954183 814643 759932 842919,3333 Tiempo en ns sin protocolos de red 1841 1938,5 1755 1844,833333 Tiempo en protocolos 952342 812704,5 758177 841074,5 0 200000 400000 600000 800000 1000000 1200000 Tiempo en nanosegundos Media acotada al 20% Tiempo Base (0 muestras) Estación A con uso de red y sin uso de red (ns) Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 53 Resultados del cálculo del tiempo base de la estación B con uso de protocolos de red en configuración remota Ilustración 38 Tiempo base de la estación B con uso de protocolos de red en configuración remota Descripción Aquí se pude ver cómo serían 100 simulaciones de 0 muestras. Esto nos da una idea del tiempo perdido en tareas que no son de cálculo para la estación A (con operaciones de red y enrutamiento por un enrutador). Los picos los achacamos a momentos de ocupación de CPU empleados por otros programas ajenos a la simulación y ocupación de la red por parte de otras estaciones ajenas a la experimentación. Tabla 57 Tiempo base de la estación B con uso de protocolos de red en configuración remota 0 50000000 100000000 150000000 200000000 250000000 300000000 350000000 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 Tiempo Base (0 muestras) Estación B con uso de red (ns) Búsqueda Ortogonal Búsqueda Esferica Búsqueda Cercano Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 54 Análisis del cálculo del tiempo base de la estación B con uso de protocolos de red en configuración remota Ilustración 39 Tiempo base de la estación B con uso de protocolos de red en configuración remota Descripción Para poder obtener el tiempo base lo que haremos es calcular la media acotada al 20%, con ello eliminamos los picos de CPU achacables a otros procesos externos a las pruebas y los picos de inicialización de los protocolos de red y mapeo de estaciones por parte del enrutador. Como podemos observar las tres búsquedas tienen una media acotada similar, alrededor de los 9956000 nanosegundos, esto es debido a que los tiempos aquí reflejados son debidos a operaciones no relacionadas con los algoritmos. Tabla 58 Tiempo base de la estación B con uso de protocolos de red en configuración remota Búsqueda Ortogonal Búsqueda Esferica Búsqueda Cercano PROMEDIO Tiempo en ns con protocolos de red Estación B 10056941 9403513 10410170,5 9956874,833 8800000 9000000 9200000 9400000 9600000 9800000 10000000 10200000 10400000 10600000 Tiempo en nanosegundos Media acotada al 20% Tiempo Base (0 muestras) Estación B con uso de red (ns) Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 55 Análisis del cálculo del tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto Ilustración 40 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto Descripción Si comparamos los tiempos anteriores descubriremos que el tiempo perdido en protocolos de red es bastante elevado. + 9956874,833 𝑛𝑠 − 842919,3333 𝑛𝑠 −1844,833333 𝑛𝑠 −1844,833333 𝑛𝑠 9110265,833 𝑛𝑠 Como podemos observar el tiempo perdido en enrutamiento de red hace insignificante el tiempo perdido en otras operaciones como en configuración de protocolos.. Tabla 59 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto Búsqueda Ortogonal Búsqueda Esferica Búsqueda Cercano PROMEDIO Tiempo en ns con protocolos de red Estación B 10056941 9403513 10410170,5 9956874,833 Tiempo en ns con protocolos de red Estación A 954183 814643 759932 842919,3333 Tiempo en ns sin protocolos de red Estación A 1841 1938,5 1755 1844,833333 Tiempo de enrutamiento 9099076 8584993 9646728,5 9110265,833 0 2000000 4000000 6000000 8000000 10000000 12000000 Tiempo en nanosegundos Media acotada al 20% Tiempo Base (0 muestras) Estación A con uso de red y sin uso de red (ns) Estación B con uso de red (ns) Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 56 Resultados del cálculo del tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada Ilustración 41 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada Descripción Aquí se pude ver cómo serían 100 simulaciones de 0 muestras. Esto nos da una idea del tiempo perdido en tareas que no son de cálculo para la estación A (con operaciones de red y enrutamiento por un enrutador). Los picos los achacamos a momentos de ocupación de CPU empleados por otros programas ajenos a la simulación y ocupación de la red por parte de otras estaciones ajenas a la experimentación. Tabla 60 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada 0 50000000 100000000 150000000 200000000 250000000 300000000 350000000 400000000 450000000 500000000 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 Tiempo Base (0 muestras) Estación A con uso de red (ns) Estacion B con uso de red (ns) Busqueda combinada Búsqueda Ortogonal Estación A LOCAL Búsqueda Esferica Estación A LOCAL Búsqueda Cercano Estación A LOCAL Búsqueda Ortogonal Estación B REMOTA Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 57 Análisis del cálculo del tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada Ilustración 42 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada Descripción Para poder obtener el tiempo base lo que haremos es calcular la media acotada al 20%, con ello eliminamos los picos de CPU achacables a otros procesos externos a las pruebas y los picos de inicialización de los protocolos de red y mapeo de estaciones por parte del enrutador. Como podemos observar las tres búsquedas tienen una media acotada similar, alrededor de los 10000000 nanosegundos, esto es debido a que los tiempos aquí reflejados son debidos a operaciones no relacionadas con los algoritmos. También he de explicar que el tiempo de búsqueda se limita a la estación más lenta. max 1558463 𝑛𝑠 10027806,83 𝑛𝑠 =10027806,83 𝑛𝑠 Tabla 61 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada Búsqueda Ortogonal Búsqueda Esferica Búsqueda Cercano PROMEDIO Tiempo en ns búsqueda combinada Estacion A en local 2311406 1258184 1105799 1558463 Tiempo en ns búsqueda combinada Estacion B en remoto 11685742 9763299,5 8634379 10027806,83 Tiempo en ns búsqueda combinada 11685742 9763299,5 8634379 10027806,83 0 2000000 4000000 6000000 8000000 10000000 12000000 14000000 Tiempo en nanosegundos Media acotada al 20% Tiempo Base (0 muestras) Estación B con uso de red (ns) Estacion A con uso de red (ns) Busqueda combinada Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 58 Análisis del cálculo del tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto y la búsqueda combinada Ilustración 43 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto y la búsqueda combinada Descripción Podemos observar que en la búsqueda combinado los resultados son similares a la operación de los mismos por separado. Por ejemplo el tiempo de búsqueda promedio de la estación A es similar en una búsqueda combinar al de la ejecución por separado, dada la escala manejada de tiempos: 1558463 𝑛𝑠 ≅ 842919,333 𝑛𝑠 (𝑣𝑒𝑟 𝑔𝑟𝑎𝑓𝑖𝑐𝑎 𝑝𝑎𝑟𝑎 𝑣𝑒𝑟 𝑠𝑖𝑚𝑖𝑙𝑖𝑡𝑢𝑑) Lo mismo pasa para la búsqueda de la estación B: 10027806,8 𝑛𝑠 ≅ 9956874,83 𝑛𝑠 (𝑣𝑒𝑟 𝑔𝑟𝑎𝑓𝑖𝑐𝑎 𝑝𝑎𝑟𝑎 𝑣𝑒𝑟 𝑠𝑖𝑚𝑖𝑙𝑖𝑡𝑢𝑑) Tabla 62 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto y la búsqueda combinada Tiempo en ns búsque da combin ada Estacion A en local Tiempo en ns búsque da combin ada Estacion B en remoto Tiempo en ns con protocol os de red Estación B Tiempo en ns con protocol os de red Estación A Tiempo en ns sin protocol os de red Estación A Tiempo en ns búsque da combin ada Búsqueda Ortogonal 2311406 11685742 10056941 954183 1841 11685742 Búsqueda Esferica 1258184 9763299,5 9403513 814643 1938,5 9763299,5 Búsqueda Cercano 1105799 8634379 10410170,5 759932 1755 8634379 PROMEDIO 1558463 10027806,8 9956874,83 842919,333 1844,83333 10027806,8 0 2000000 4000000 6000000 8000000 10000000 12000000 14000000 Tiempo en nanosegundos Media acotada al 20% Tiempo Base (0 muestras) Estación A con uso de red y sin uso de red (ns) Estación B con uso de red (ns) Busqueda combinada Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 59 Tiempo de procesamiento de los algoritmos Análisis del algoritmo del más cercano Ilustración 44 Análisis del algoritmo del más cercano Ilustración Tendencia de la simulación O(Log N) Descripción Se puede ver una clara tendencia a aumentar el tiempo de proceso en una escala O(Log N). Se puede observar que la media se dispara en ciertas partes de la gráfica. Esto es debido a momentos puntuales en que la CPU está ocupada por otras aplicaciones no relacionadas con la simulación. Sin embargo esto es así porque en la simulación se evaluaron tan solo puntos, si evaluamos volúmenes esto variara, siendo en el mejor de los casos de escala logarítmica y en el peor de los casos lineal. Tabla 63 Simulación local de la búsqueda del más cercano Máquina 1 0 20000 40000 60000 80000 100000 120000 Busqueda del mas cercano Estación A sin uso de protocolos de red Promedio (ns) Media acotada (20%) (ns) Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 60 Análisis del algoritmo de búsqueda ortogonal Ilustración 45 Análisis del algoritmo de búsqueda ortogonal Descripción Debido al algoritmo llevado en el recorrido del árbol, la tendencia variara de una búsqueda totalmente lineal a una búsqueda logarítmica. Esto es debido a que en ciertas partes las condiciones del algoritmo obligan a evaluar ambas ramas del árbol. Por lo tanto en el mejor de los casos el algoritmo tendrá una tendencia logarítmica y en el peor de los casos lineal. En este caso los puntos que sus proyecciones intersecciones con la esfera, obligaran a evaluar ambas ramas. Tabla 64 Análisis del algoritmo de búsqueda ortogonal 0 200000 400000 600000 800000 1000000 1200000 1400000 1600000 1800000 2000000 0 muestras 500 muestras 1000 muestras 1500 muestras 2000 muestras 2500 muestras 3000 muestras 3500 muestras 4000 muestras 4500 muestras 5000 muestras 5500 muestras 6000 muestras 6500 muestras 7000 muestras 7500 muestras 8000 muestras 8500 muestras 9000 muestras 9500 muestras 10000 muestras Busqueda ortogonal Estación A sin uso de protocolos de red Promedio (ns) Media acotada (20%) (ns) Ingeniería Informática Proyecto Final de Carrera Capítulo: Estudio de los Resultados 61 Análisis del algoritmo de búsqueda esférica Ilustración 46 Análisis del algoritmo de búsqueda esférica Descripción Debido al algoritmo llevado en el recorrido del árbol, la tendencia variara de una búsqueda totalmente lineal a una búsqueda logarítmica. Esto es debido a que en ciertas partes las condiciones del algoritmo obligan a evaluar ambas ramas del árbol. Por lo tanto en el mejor de los casos el algoritmo tendrá una tendencia logarítmica y en el peor de los casos lineal. Los picos observados en la grafica son debidos a momentos de ocupación de la CPU por procesos externos a la simulación. En este caso los puntos que sus proyecciones intersecciones con el cubo, obligaran a evaluar ambas ramas. Tabla 65 Análisis del algoritmo de búsqueda esférica 0 100000 200000 300000 400000 500000 600000 700000 0 muestras 500 muestras 1000 muestras 1500 muestras 2000 muestras 2500 muestras 3000 muestras 3500 muestras 4000 muestras 4500 muestras 5000 muestras 5500 muestras 6000 muestras 6500 muestras 7000 muestras 7500 muestras 8000 muestras 8500 muestras 9000 muestras 9500 muestras 10000 muestras Busqueda esférica Estación A sin uso de protocolos de red Promedio (ns) Media acotada (20%) (ns) Ingeniería Informática Proyecto Final de Carrera Capítulo: Bibliografía 68 8.2. Otros enlaces de interés Ilustración 47 Web de Wikipedia Ilustración 48 Web de Worldingo Ingeniería Informática Proyecto Final de Carrera Capítulo: Bibliografía 69 Ilustración 49 Web de CodePixel Ilustración 50 Web de Arrakis Ingeniería Informática Proyecto Final de Carrera Capítulo: Bibliografía 70 Ilustración 51 Web de Sargue Ilustración 52 Web de cfelde Ingeniería Informática Proyecto Final de Carrera Capítulo: Bibliografía 71 Ilustración 53 Web de cadstock Ilustración 54 Web de CodePixel Ingeniería Informática Proyecto Final de Carrera Capítulo: Bibliografía 72 Ilustración 55 Web de corej2eepatterns Tablas E Ilustraciones I TABLAS E ILUSTRACIONES Índice de Tablas Tabla 1 Estructura de la Memoria ................................................................................................................ 3 Tabla 2 Fases elegidas en el ciclo de vida ..................................................................................................... 5 Tabla 3 Temáticas de riesgos ....................................................................................................................... 6 Tabla 4 limitaciones básicas de las granjas de render.................................................................................. 8 Tabla 5 Tipos de Sistemas de almacenamiento distribuidos ........................................................................ 8 Tabla 6 Ventajas de una base de datos distribuida ...................................................................................... 9 Tabla 7 Desventajas de una base de datos distribuida ................................................................................ 9 Tabla 8 Algoritmos usados en los sistemas de render ................................................................................ 10 Tabla 9 Ejemplo famosos de redes P2P ...................................................................................................... 11 Tabla 10 Características deseables en una red P2P .................................................................................... 11 Tabla 11 Tipos de redes P2P ....................................................................................................................... 12 Tabla 12 Diagrama del sistema .................................................................................................................. 13 Tabla 13 Mantenimiento de la red ............................................................................................................. 14 Tabla 14 Modelo vista controlador ............................................................................................................ 15 Tabla 15 Características deseables para el interfaz de usuario .................................................................. 16 Tabla 16 El controlador .............................................................................................................................. 17 Tabla 17 Características deseables para los módulos del controlador ....................................................... 17 Tabla 18 Funcionalidades del controlador.................................................................................................. 18 Tabla 19 Funcionalidades de Sistema ......................................................................................................... 18 Tabla 20 Funcionalidades de Servicios de red ............................................................................................ 19 Tabla 21 Funcionalidades relacionadas con las estaciones de render ....................................................... 20 Tablas E Ilustraciones II Tabla 22 Funcionalidades relacionadas con las formas ............................................................................. 21 Tabla 23 Funcionalidades relacionadas con el árbol kd ............................................................................. 22 Tabla 24 Funcionalidades de simulación .................................................................................................... 23 Tabla 25 El modelo ..................................................................................................................................... 23 Tabla 26 Técnicas de generación y reparto del árbol kdtree ...................................................................... 25 Tabla 27 Sistema de comunicación ............................................................................................................ 27 Tabla 28 Tipos de interfaz .......................................................................................................................... 28 Tabla 29 Formatos de almacenamiento de los datos ................................................................................. 29 Tabla 30 Lenguajes de programación evaluados ....................................................................................... 30 Tabla 31 Puntos a favor de java ................................................................................................................. 30 Tabla 32 Puntos en contra de java ............................................................................................................. 30 Tabla 33 Modelado de los datos del modelo .............................................................................................. 32 Tabla 34 Modelado del modelo .................................................................................................................. 32 Tabla 35 Modelado del modelo de las estaciones de render...................................................................... 33 Tabla 36 Modelado del modelo del listado de formas ............................................................................... 34 Tabla 37 Modelado del Árbol kd................................................................................................................. 35 Tabla 38 Modelado del Controlador ........................................................................................................... 36 Tabla 39 Modelado del módulo del controlador de servicios ..................................................................... 37 Tabla 40 Modelado del módulo del controlador del listado de estaciones de render ................................ 38 Tabla 41 Modelado del módulo del controlador de formas ....................................................................... 38 Tabla 42 Modelado del módulo del controlador de árbol kd ..................................................................... 39 Tabla 43 Modelado del módulo del controlador de simulación ................................................................. 39 Tabla 44 Modelado del módulo del controlador de monitorización........................................................... 40 Tabla 45 Modelado del módulo del controlador de tareas ........................................................................ 40 Tabla 46 Modelado de la Vista ................................................................................................................... 41 Tabla 47 Tipos de Experimentos ................................................................................................................. 43 Tabla 48 tamaños de muestra .................................................................................................................... 43 Tabla 49 Router .......................................................................................................................................... 45 Tabla 50 Maquina A (Local) ........................................................................................................................ 45 Tabla 51 Maquina B (Remota).................................................................................................................... 45 Tabla 52 Tiempo Base Estación A sin uso de red ........................................................................................ 48 Tabla 53 Análisis del cálculo del tiempo base de la estación A sin uso de red ........................................... 49 Tabla 54 Tiempo base de la estación A con uso de red en local ................................................................. 50 Tabla 55 Tiempo base de la estación A con uso de red en local ................................................................. 51 Tabla 56 Tiempo base de la estación A con uso de red en local y sin uso de red ....................................... 52 Tabla 57 Tiempo base de la estación B con uso de protocolos de red en configuración remota ............... 53 Tabla 58 Tiempo base de la estación B con uso de protocolos de red en configuración remota ............... 54 Tabla 59 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto ............................................................................................................................................. 55 Tabla 60 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada ..................................... 56 Tabla 61 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada ..................................... 57 Tabla 62 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto y la búsqueda combinada ................................................................................................... 58 Tabla 63 Simulación local de la búsqueda del más cercano Máquina 1..................................................... 59 Tabla 64 Análisis del algoritmo de búsqueda ortogonal ............................................................................ 60 Tabla 65 Análisis del algoritmo de búsqueda esférica................................................................................ 61 Tabla 66 Tiempos base ............................................................................................................................... 64 Tabla 67 Trabajo Futuro ............................................................................................................................. 65 Tablas E Ilustraciones III Índice de Ilustraciones Ilustración 1 Estimación inicial del proyecto................................................................................................. 5 Ilustración 2 Diagrama del sistema ............................................................................................................ 13 Ilustración 3 Mantenimiento de la red ....................................................................................................... 14 Ilustración 4 Modelo vista controlador ....................................................................................................... 15 Ilustración 5 La vista ................................................................................................................................... 16 Ilustración 6 El controlador......................................................................................................................... 17 Ilustración 7 Funcionalidades de Sistema ................................................................................................... 18 Ilustración 8 Funcionalidades de Servicios de red....................................................................................... 19 Ilustración 9 Funcionalidades relacionadas con las estaciones de render .................................................. 20 Ilustración 10 Funcionalidades relacionadas con las formas ..................................................................... 21 Ilustración 11 Funcionalidades relacionadas con el árbol kd ..................................................................... 22 Ilustración 12 Funcionalidades de simulación ............................................................................................ 23 Ilustración 13 Técnicas de generación y reparto del árbol kdtree .............................................................. 25 Ilustración 14 Tres proyectos al más puro estilo MVC ................................................................................ 31 Ilustración 15 Modelado del modelo .......................................................................................................... 32 Ilustración 16 Modelado del modelo de las estaciones de render .............................................................. 33 Ilustración 17 Modelado del modelo del listado de formas ....................................................................... 34 Ilustración 18 Modelado del Árbol kd ......................................................................................................... 35 Ilustración 19 Modelado del Controlador ................................................................................................... 36 Ilustración 20 Modelado del módulo del controlador de servicios ............................................................. 37 Ilustración 21 Modelado del módulo del controlador del listado de estaciones de render ........................ 38 Ilustración 22 Modelado del módulo del controlador de formas ............................................................... 38 Ilustración 23 Modelado del módulo del controlador de árbol kd.............................................................. 39 Ilustración 24 Modelado del módulo del controlador de simulación ......................................................... 39 Ilustración 25 Modelado del módulo del controlador de monitorización ................................................... 40 Ilustración 26 Modelado del módulo del controlador de tareas ................................................................ 40 Ilustración 27 Modelado de la Vista ........................................................................................................... 41 Ilustración 28 Opciones de generación ....................................................................................................... 44 Ilustración 29 Entorno de pruebas .............................................................................................................. 45 Ilustración 30 Estación local ....................................................................................................................... 46 Ilustración 31 Estación A con uso de protocolos de red en configuración local ......................................... 46 Ilustración 32 Estación A con uso de protocolos de red en configuración local y la estación B con uso de protocolos de red en configuración remota ............................................................................................... 47 Ilustración 33 Tiempo Base Estación A sin uso de red ................................................................................ 48 Ilustración 34 Análisis del cálculo del tiempo base de la estación A sin uso de red ................................... 49 Ilustración 35 Tiempo base de la estación A con uso de red en local ......................................................... 50 Ilustración 36 Tiempo base de la estación A con uso de red en local ......................................................... 51 Ilustración 37 Tiempo base de la estación A con uso de red en local y sin uso de red ............................... 52 Ilustración 38 Tiempo base de la estación B con uso de protocolos de red en configuración remota ....... 53 Ilustración 39 Tiempo base de la estación B con uso de protocolos de red en configuración remota ....... 54 Ilustración 40 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto .................................................................................................................................. 55 Ilustración 41 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada .................... 56 Ilustración 42 Tiempo base de la estación B con uso de protocolos de red en configuración local y estación B con uso de protocolos de red en configuración remota en búsqueda combinada .................... 57 Tablas E Ilustraciones IV Ilustración 43 Tiempo base de la estación A con uso de red en local y sin uso de red y la estación B con uso de red en remoto y la búsqueda combinada ........................................................................................ 58 Ilustración 44 Análisis del algoritmo del más cercano ............................................................................... 59 Ilustración 45 Análisis del algoritmo de búsqueda ortogonal .................................................................... 60 Ilustración 46 Análisis del algoritmo de búsqueda esférica ........................................................................ 61 Ilustración 47 Web de Wikipedia ................................................................................................................ 68 Ilustración 48 Web de Worldingo ............................................................................................................... 68 Ilustración 49 Web de CodePixel ................................................................................................................ 69 Ilustración 50 Web de Arrakis ..................................................................................................................... 69 Ilustración 51 Web de Sargue ..................................................................................................................... 70 Ilustración 52 Web de cfelde ...................................................................................................................... 70 Ilustración 53 Web de cadstock .................................................................................................................. 71 Ilustración 54 Web de CodePixel ................................................................................................................ 71 Ilustración 55 Web de corej2eepatterns ..................................................................................................... 72