© Photo by Gonçalo João

| Home | Curriculum | Research | Publications | Students |

João Leitão's Homepage : Publications : Abstract

Thicket: Construção e Manutenção de Múltiplas Árvores numa Rede entre Pares
M. Ferreira, J. Leitão, and L. Rodrigues

Selected sections of this report were published in the Proceedings of the second Portuguese Symposium on Informatics, Braga, Portugal, Sep, 2010.

Portuguese Abstract

As árvores de disseminação permitem a distribuição eficiente de contéudos em redes sobrepostas mas impõem uma carga aos nós interiores muito superior à dos nós folha. Uma forma de contornar este problema passa pela utilização de múltiplas árvores em que cada nó é apenas interior num pequeno subconjunto de todas as árvores, e folha nas restantes. As múltiplas árvores permitem a distribuição da carga e o envio de informação redundante para a recuperação de falhas. Neste trabalho propomos o Thicket, um algoritmo para a construção e manutenção de múltiplas árvores, de forma totalmente descentralizada, sobre uma rede não estruturada. O algoritmo foi implementado e avaliado através de simulações, utilizando uma rede composta por 10.000 nós.

English Abstract

Spanning tree structures allow efficient resource usage when broadcasting data on overlays networks but they impose a much higher load to the interior nodes than the leafs. One way of overcoming this issue is to employ multiple spanning trees where a node is interior in just a few of them and a leaf in the remaining. This configuration enhances load distribution and provides a mechanism for introducing redundancy required for fault-tolerance. This work presents Thicket, a protocol for building and maintaining multiple spanning trees, with fully decentralized algorithms, in an unstructured overlay. The protocol was implemented and evaluated, using simulations, in a network composed of 10.000 nodes.

[BibTeX][Abstract][PDF]