Publication
Search Strategies in Unstructured Overlays
| dc.contributor.advisor | Miranda, Hugo | por |
| dc.contributor.author | Fonseca, Pedro Marques | por |
| dc.date.accessioned | 2009-11-25T09:55:55Z | por |
| dc.date.accessioned | 2014-11-14T16:22:06Z | |
| dc.date.available | 2009-11-25T09:55:55Z | por |
| dc.date.available | 2014-11-14T16:22:06Z | |
| dc.date.issued | 2008 | por |
| dc.description.abstract | Os sistemas peer-to-peer, como aplicações de partilha e distribuição de conteúdos ou voz-sobre-IP, são construídos sobre redes sobrepostas. Redes sobrepostas são redes virtuais que existem sobre uma rede subjacente, em que a topologia da rede sobreposta não tem de ter uma correspondência com a topologia da rede subjacente. Ao contrário das suas congéneres estruturadas, as redes sobrepostas não estru- turadas não restringem a localização dos seus participantes, ou seja, não limitam a escolha de vizinhos de um dado nó, o que torna a sua manutenção mais simples. O baixo custo de manutenção das redes sobrepostas não-estruturadas torna estas especialmente adequadas para a construção de sistemas peer-to-peer capazes de tolerar o comportamento dinâmico dos seus participantes, uma vez que estas redes são permanentemente afectadas pela entrada e saída de nós na rede, um fenómeno conhecido como churn. O algoritmo de pesquisa mais comum em redes sobrepostas não-estruturadas consiste em inundar a rede, o que origina uma grande quantidade de mensagens duplicadas por cada pesquisa. A escalabilidade destes algoritmos é limitada porque consomem demasiados recursos da rede em sistemas com muitos participantes. Para reduzir o n´umero de mensagens, as redes sobrepostas não-estruturadas podem ser organizadas em topologias hierárquicas. Nestas topologias alguns nós da rede, chamados super nós, assumem um papel mais importante, responsabilizando-se pela localização de objectos. A utilização de super nós cria novos problemas, como a sua selecção e a dependência da rede de uma pequena percentagem dos nós. Esta dissertação apresenta um novo algoritmo de pesquisa, chamado FASE, criado para operar sobre redes sobrepostas não estruturadas com topologias não- hierárquicas. Este algoritmo combina uma política de replicação com uma técnica de divisão do espaço de procura para resolver pesquisas ao alcance de um número reduzido de saltos com o menor custo possível. Adicionalmente, o algoritmo procura nivelar a contribuição dos participantes, já que todos contribuem de uma forma semelhante para o desempenho da pesquisa. A estratégia seguida pelo algo- ritmo consiste em dividir tanto os nós da rede como as chaves dos seus conteúdos por diferentes “frequências” e replicar chaves nas respectivas frequências, sem, no entanto, limitar a localização de um nó ou impor uma estrutura à rede ou mesmo aplicar uma definição rígida de chave. Com o objectivo de mitigar o problema do churn, é apresentado um algoritmo de monitorização distribuído para as réplicas originadas pelo FASE. Os algoritmos propostos são avaliados através de simulações, que validam a eficiência do FASE quando comparado com outros algoritmos de pesquisa em redes sobrepostas não-estruturadas. É também demonstrado que o FASE mantém o seu desempenho em redes sob o efeito do churn quando combinado com o algoritmo de monitorização. | por |
| dc.identifier.uri | http://hdl.handle.net/10451/13936 | por |
| dc.identifier.uri | http://repositorio.ul.pt/handle/10455/3246 | por |
| dc.language.iso | por | por |
| dc.subject | não-estruturadas | por |
| dc.subject | churn | por |
| dc.subject | redes sobrepostas | por |
| dc.subject | pesquisa eficiente | por |
| dc.subject | Peer-to-peer | por |
| dc.title | Search Strategies in Unstructured Overlays | por |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | por |
| rcaap.type | masterThesis | por |