Exhaustive Search in P2P Networks
Abstract
Despite numerous efforts in the past few years, efficient complex queries in large-scale P2P networks remain an open and challenging problem. This work presents a hybrid architecture for complex queries in P2P networks that relies on a lightweight network structure, in a predominantly non-structured network, to avoid unnecessary query replication and to speed up query propagation in unstructured P2P networks. In addition to this architecture, this work presents a controlled and exhaustive search protocol that combines structured and non-structured P2P networks features. Extensive simulation results, considering static and dynamic scenarios, show that the proposed architecture, in conjunction with a search protocol, outperforms the best known solution in number of messages, response time, number of hops, and success rate for query resolution. Furthermore, this work shows, analytically, using random trees results, an upper bound on query routing.
References
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.
