A hierarchical framework for peer-to peer systems: design and optimizations

Abstract

En los últimos años, las redes peer-to-peer (P2P) ha experimentado una fuerte expansión. Estos sustratos se constituyen en forma de redes overlay o de recubrimiento que interconectan usuarios de manera lógica y desacoplada de la topología física, y que proporcionan un servicio descentralizado de búsqueda de recursos. Existen dos grandes familias de redes P2P descentralizadas: las redes P2P desestructuradas y las redes P2P estructuradas. Desde el punto de vista funcional, las redes estructuradas también se denominan Tablas de Hash Distribuidas (DHTs). Básicamente, las DHTs proporcionan la misma funcionalidad de las tablas de hash tradicional, esto es, la interficie estándar Put(clave, valor) y Get(clave), pero asociando los pares clave-valor con usuarios de la DHT.Debido a su excelente escalabilidad, las DHT han suscitado una gran expectación en los últimos años. Sin embargo, su adopción como herramienta generalizada de comunicación es aún lenta debido a un conjunto de inconvenientes. El primer inconveniente es que la estructura lógica de las DHTs no se corresponde con la topología física de Internet. En otras palabras, un usuario puede tener como vecinos a otros participantes que en realidad se encuentren muy alejados (en términos de latencia) de él. Para aplicaciones en que la latencia extremo-a-extremo ha de ser necesariamente baja, esta falta de correspondencia supone un gran obstáculo. Por otro lado, muchos diseños asumen que la comunicación es uniforme, mientras que en la práctica los usuarios se comunican de manera más frecuente con los usuarios que pertenecen al mismo dominio administrativo, comparten los mismos intereses etc.Para resolver estas deficiencias, tradicionalmente se ha recurrido a la organización de los usuarios en dominios jerárquicos. Ejemplos típicos de esta estrategia son el sistema DNS y los sistemas de distribución y gestión de contenido multimedia de alta calidad.El problema básico es que la mayoría de DHTs se han diseñado como estructuras llanas y por tanto, no pueden disfrutar de las ventajas de las jerarquías. En esta disertación, hemos intentado solucionar este problema de la forma siguiente:Seducidos por la escalabilidad de los diseños jerárquicos, en la primera parte de esta tesis, describimos un framework o marco de trabajo jerárquico para DHTs. El objetivo principal de este framework es proporcionar una metodología genérica para transformar una DHT cualquiera en una DHT jerárquica constituida por grupos o clusters telescópicos, esto es, clusters de clusters de ... de clusters de usuarios. La idea básica consiste en explotar, si es posible, su estructura recursiva. En caso afirmativo, la construcción jerárquica hereda la homogeneidad en carga y funcionalidad del diseño original, pero con las ventajas adicionales derivadas de una estructura jerárquica. Para ilustrar la utilidad de nuestro framework, proporcionamos la versión jerárquica de Chord y un conjunto de indicaciones para poder transformar seis DHTs de manera sencilla. Cerramos esta parte con el estudio de la mejora potencial en el rendimiento de nuestros diseños. En la segunda parte de esta tesis, respondemos a una cuestión que uno debería de tener en cuenta a fin de poder valorar objetivamente la utilidad de nuestro framework: En cuáles aspectos nuestras construcciones jerárquicas son superiores a las existentes? Para dar una respuesta satisfactoria a esta pregunta, introducimos un modelo genérico basado en costes. En general, nuestros diseños jerárquicos ofrecen un amplio abanico de posibilidades relacionadas con la explotación de un sustrato con múltiples dominios. Un ejemplo ilustrativo es la mejora del rendimiento. Si la comunicación es frecuente entre usuarios de un mismo dominio, la adaptación de los dominios a la red física permitirá reducir el tiempo de búsqueda medio del sistema. El problema básico es como organizar los usuarios en clusters de baja latencia, de manera descentralizada y escalable. Para solucionar este problema, la última parte de esta tesis introduce un nuevo algoritmo de clustering o de agrupamiento. La función de este algoritmo es organizar a los usuarios en múltiples clusters de manera que los usuarios dentro de un cluster estén mutuamente más cercanos (en términos de latencia) que los usuarios pertenecientes a clusters distintos. Para juzgar la calidad de nuestra solución, proponemos una nueva métrica denominada false clustering rate. Esta métrica mide la proporción de usuarios falsamente agrupados dentro del sistema. Por usuarios falsamente agrupados nos referimos a usuarios lejanos que han estado erróneamente agrupados dentro de un mismo cluster. Finalmente, demostramos por medio de diversos experimentos como nuestro algoritmo permite obtener mejores significativas con respecto a las técnicas existentes.Programa de doctorat en Tecnologies de la Informació i les Comunicacions