Welcome to the UPF Digital Repository

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

Show simple item record

dc.contributor.author Sánchez Artigas, Marc
dc.contributor.other Oliver Riera, Miquel
dc.contributor.other García López, Pedro
dc.contributor.other Universitat Pompeu Fabra. Departament de Tecnologia
dc.date.accessioned 2024-03-16T02:34:28Z
dc.date.available 2024-03-16T02:34:28Z
dc.date.issued 2011-04-12T16:36:23Z
dc.date.issued 2009-02-27
dc.date.issued 2009-01-12
dc.date.issued 2009-02-27
dc.identifier 9788469234723
dc.identifier http://www.tdx.cat/TDX-0227109-144129
dc.identifier http://hdl.handle.net/10803/7551
dc.identifier B.12898-2009
dc.identifier.uri http://hdl.handle.net/10230/11846
dc.description.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.
dc.description.abstract Programa de doctorat en Tecnologies de la Informació i les Comunicacions
dc.format application/pdf
dc.format application/pdf
dc.language.iso eng
dc.publisher Universitat Pompeu Fabra
dc.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.
dc.rights info:eu-repo/semantics/openAccess
dc.source TDX (Tesis Doctorals en Xarxa)
dc.title A hierarchical framework for peer-to peer systems: design and optimizations
dc.type info:eu-repo/semantics/doctoralThesis
dc.type info:eu-repo/semantics/publishedVersion
dc.date.modified 2024-03-15T10:58:05Z
dc.subject.keyword hierarchical designs
dc.subject.keyword distributed systems
dc.subject.keyword peer to peer overlay networks
dc.subject.keyword distributed Hash tables
dc.subject.keyword clustering por proximidad
dc.subject.keyword dise no Jerarquico
dc.subject.keyword tablas de Hash distribuidas
dc.subject.keyword sistemas de igual a igual
dc.subject.keyword redes overlay de igual a igual
dc.subject.keyword disseny jerarquic
dc.subject.keyword clustering per proximitat
dc.subject.keyword sistemas distribuidos
dc.subject.keyword distribuides
dc.subject.keyword taules de Hash
dc.subject.keyword sistemes d'igual a igual
dc.subject.keyword xarxes overlay d'igual a igual
dc.subject.keyword sistemes distribuits
dc.subject.keyword proximity clustering
dc.subject.keyword 004


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Statistics

In collaboration with Compliant to Partaking