A hierarchical framework for peer-to peer systems: design and optimizations
Marc Sánchez Artigas · TDX (Tesis Doctorals en Xarxa) · 2009
En los ultimos anos, las redes peer-to-peer (P2P) ha experimentado una fuerte expansion. Estos sustratos se constituyen en forma de redes overlay o de recubrimiento que interconectan usuarios de manera logica y desacoplada de la topologia fisica, y que proporcionan un servicio descentralizado de busqueda 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 tambien se denominan Tablas de Hash Distribuidas (DHTs). Basicamente, las DHTs proporcionan la misma funcionalidad de las tablas de hash tradicional, esto es, la interficie estandar 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 expectacion en los ultimos anos. Sin embargo, su adopcion como herramienta generalizada de comunicacion es aun lenta debido a un conjunto de inconvenientes. El primer inconveniente es que la estructura logica de las DHTs no se corresponde con la topologia fisica de Internet. En otras palabras, un usuario puede tener como vecinos a otros participantes que en realidad se encuentren muy alejados (en terminos de latencia) de el. Para aplicaciones en que la latencia extremo-a-extremo ha de ser necesariamente baja, esta falta de correspondencia supone un gran obstaculo. Por otro lado, muchos disenos asumen que la comunicacion es uniforme, mientras que en la practica los usuarios se comunican de manera mas 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 organizacion de los usuarios en dominios jerarquicos. Ejemplos tipicos de esta estrategia son el sistema DNS y los sistemas de distribucion y gestion de contenido multimedia de alta calidad.El problema basico es que la mayoria de DHTs se han disenado como estructuras llanas y por tanto, no pueden disfrutar de las ventajas de las jerarquias. En esta disertacion, hemos intentado solucionar este problema de la forma siguiente:Seducidos por la escalabilidad de los disenos jerarquicos, en la primera parte de esta tesis, describimos un framework o marco de trabajo jerarquico para DHTs. El objetivo principal de este framework es proporcionar una metodologia generica para transformar una DHT cualquiera en una DHT jerarquica constituida por grupos o clusters telescopicos, esto es, clusters de clusters de ... de clusters de usuarios. La idea basica consiste en explotar, si es posible, su estructura recursiva. En caso afirmativo, la construccion jerarquica hereda la homogeneidad en carga y funcionalidad del diseno original, pero con las ventajas adicionales derivadas de una estructura jerarquica. Para ilustrar la utilidad de nuestro framework, proporcionamos la version jerarquica 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 disenos. En la segunda parte de esta tesis, respondemos a una cuestion que uno deberia de tener en cuenta a fin de poder valorar objetivamente la utilidad de nuestro framework: En cuales aspectos nuestras construcciones jerarquicas son superiores a las existentes? Para dar una respuesta satisfactoria a esta pregunta, introducimos un modelo generico basado en costes. En general, nuestros disenos jerarquicos ofrecen un amplio abanico de posibilidades relacionadas con la explotacion de un sustrato con multiples dominios. Un ejemplo ilustrativo es la mejora del rendimiento. Si la comunicacion es frecuente entre usuarios de un mismo dominio, la adaptacion de los dominios a la red fisica permitira reducir el tiempo de busqueda medio del sistema. El problema basico es como organizar los usuarios en clusters de baja latencia, de manera descentralizada y escalable. Para solucionar este problema, la ultima parte de esta tesis introduce un nuevo algoritmo de clustering o de agrupamiento. La funcion de este algoritmo es organizar a los usuarios en multiples clusters de manera que los usuarios dentro de un cluster esten mutuamente mas cercanos (en terminos de latencia) que los usuarios pertenecientes a clusters distintos. Para juzgar la calidad de nuestra solucion, proponemos una nueva metrica denominada false clustering rate. Esta metrica mide la proporcion de usuarios falsamente agrupados dentro del sistema. Por usuarios falsamente agrupados nos referimos a usuarios lejanos que han estado erroneamente agrupados dentro de un mismo cluster. Finalmente, demostramos por medio de diversos experimentos como nuestro algoritmo permite obtener mejores significativas con respecto a las tecnicas existentes.