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

Author

Sánchez Artigas, Marc

Director

Oliver Riera, Miquel

García López, Pedro

Date of defense

2009-01-12

ISBN

9788469234723

Legal Deposit

B.12898-2009



Department/Institute

Universitat Pompeu Fabra. Departament de Tecnologia

Doctorate programs

Programa de doctorat en Tecnologies de la Informació i les Comunicacions

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.

Keywords

hierarchical designs; distributed systems; peer to peer overlay networks; distributed Hash tables; clustering por proximidad; dise no Jerarquico; tablas de Hash distribuidas; sistemas de igual a igual; redes overlay de igual a igual; disseny jerarquic; clustering per proximitat; sistemas distribuidos; distribuides; taules de Hash; sistemes d'igual a igual; xarxes overlay d'igual a igual; sistemes distribuits; proximity clustering

Subjects

004 - Computer science and technology. Computing. Data processing

Documents

tmsa.pdf.pdf

1.675Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)