Desenho e avaliação do algoritmo de filiação do projecto livefeeds

Abstract

O tema desta dissertação centra-se no projecto LiveFeeds, mais concretamente no seu algoritmo de filiação, que gere as entradas e saídas dos utilizadores do sistema. O LiveFeeds é um sistema editor/subscritor que pretende resolver o problema do crescente excesso de carga colocado nos servidores da World Wide Web pelos feeds RSS, problema este inerente ao modelo actual da WWW em que os utilizadores são forçados a inquirir um dado servidor para descobrir se existem alterações aos conteúdos em que estão interessados. O LiveFeeds está estruturado seguindo uma abordagem peer-to-peer, tendo sido escolhida como forma de encaminhamento um algoritmo de encaminhamento com um número constante de passos. Uma aproximação deste tipo leva a que seja necessário reflectir aprofundadamente no algoritmo de filiação utilizado. Para resolver o problema deste tipo de encaminhamento é necessário que haja uma replicação total ou parcial da informação de filiação dos utilizadores em todos os utilizadores do sistema. Esta problemática da replicação da informação está assim inseparavelmente ligada ao algoritmo de filiação do sistema. Dentro deste âmbito, esta dissertação proporciona diferentes contribuições. É desenvolvido um modelo que reflecte correctamente a dinâmica de entradas e saídas dos possíveis utilizadores do LiveFeeds que é utilizado para testar o algoritmo em condições próximas da sua execução real, em ambiente de simulação. Através de métodos analíticos e de simulação, é investigado se os custos de manutenção da replicação da filiação são suportáveis para que tal aproximação tenha viabilidade. É ainda sugerida uma alternativa ao algoritmo de filiação com visibilidade completa recorrendo a uma hierarquização do sistema baseada na noção de super-nós. Tal alternativa é estudada em profundidade sendo analisados os pontos centrais do desempenho do algoritmo, incluindo a análise de vários critérios que afectam o comportamento do mesmo. Do mesmo modo, são sugeridos alguns melhoramentos que poderão ser implementados no futuro.