Busca Exaustiva em Redes P2P
Resumo
Apesar de inúmeros esforços nos últimos anos, buscas complexas em redes P2P de grande escala permanecem um problema em aberto e desafiador. Este trabalho propõe uma arquitetura híbrida para buscas complexas em redes P2P que utiliza uma leve estrutura, em uma rede predominantemente não estruturada, para evitar replicações desnecessárias e acelerar a propagação de mensagens de busca. Além da arquitetura, também é proposto um protocolo eficiente de busca que combina características de redes P2P estruturadas e não-estruturadas. Resultados extensivos de simulação, considerando cenários estáticos e dinâmicos, mostram que a arquitetura proposta, em conjunto com o protocolo de busca, possui desempenho superior à melhor solução até então conhecida em termos de número de mensagens, tempo de resposta, número de saltos em respostas positivas e taxa de sucesso. Além disso, o trabalho mostra analiticamente, utilizando resultados de árvores aleatórias, o limite superior teórico para o número máximo de pares que uma mensagem de busca deve percorrer para resolver uma consulta.
Referências
Devroye, L. (1998). Universal Limit Laws for Depths in Random Trees. SIAM Journal on Computing, 28(2):409–432.
Ferreira, R. A., Ramanathan, M. K., Awan, A., Grama, A., and Jagannathan, S. (2005). Search with Probabilistic Guarantees in Unstructured Peer-to-Peer Networks. In Proceedings of the 2005 IEEE P2P (P2P’05), pages 165–172, Konstanz, Alemanha.
Lopes, P. and Ferreira, R. A. (2010a). SplitQuest: Controlled and Exhaustive Search in Peer-to-Peer Networks. In Proceedings of the 2010 Usenix IPTPS (IPTPS’10), San Jose, CA.
Lopes, P. and Ferreira, R. A. (2010b). Uma Arquitetura Híbrida para Buscas Complexas em Redes P2P. In Anais do SBRC 2010, Gramado, RS.
Lopes, P. and Ferreira, R. A. (2011). Exhaustive Search in Peer-to-Peer Networks. Journal of Parallel and Distributed Computing (JPDC) submetido, em avaliação.
Mitzenmacher, M. (2001). The Power of Two Choices in Randomized Load Balancing. IEEE Trans. Parallel Distrib. Syst., 12(10):1094–1104.
Mohamed, H. and Robert, P. (2005). A Probabilistic Analysis of Some Tree Algorithms. The Annals of Applied Probability, 15(4):2445–2471.
Naor, M. and Wieder, U. (2007). Novel Architectures for P2P Applications: The Continuous-Discrete Approach. ACM Transactions on Algorithms (Eletronic Edition), 3(3).
Stoica, I., Morris, R., Karger, D., Kaashoek, F., and Balakrishnan, H. (2001). Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proceedings of the 2001 ACM SIGCOMM (SIGCOMM’01), pages 149–160, San Diego, CA.
Terpstra, W. W., Kangasharju, J., Leng, C., and Buchmann, A. P. (2007). BubbleStorm: Resilient, Probabilistic, and Exhaustive Peer-to-Peer Search. In Proceedings of the 2007 ACM SIGCOMM (SIGCOMM’07), pages 49–60, Tóquio, Japão.
