Heuristics for uninformed search algorithms in unstructured P2P networks inspired by self-organizing social insect models

Prithviraj Dasgupta, Erik Antonson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We consider the problem of rapidly searching for resources or files in a distributed, unstructured, peer-to-peer file sharing network. Unstructured p2p network protocols such as Gnutella use a flooding-based mechanism for resource searching that generates considerable traffic in the network for each search query. When the searching activity by users in a p2p network is high, the traffic generated from the search requests could ensue congestion and result in increased search latency and poor performance in the entire network. To address this problem, we describe a resource search algorithm for p2p networks inspired by the stigmergetic behavior of ants while searching for food. Ants are used to encapsulate a search query initiated by a user in the p2p network. To search for the resource corresponding to their search query among the nodes of the network, each ant associates a certain amount of virtual pheromone with the nodes it visits. Later on, ants searching for resources use the amount and type of pheromone associated by previous ants with each node along their search path to direct the search query towards nodes that have a higher probability of resulting in the success for the search. We have tested our algorithm extensively within a simulated p2p network. Our simulation results show that our ant-based heuristics perform better than a completely uninformed or blind search that requires similar message overhead for each search query. When compared to a flooding-based mechanism, although the ant based search heuristic performs less efficiently under certain circumstances, it is capable of reducing the message overhead per search query by an exponential amount with respect to the flooding-based mechanism.

Original languageEnglish (US)
Title of host publicationBiologically-Inspired Collaborative Computing
Subtitle of host publicationIFIP 20th World Computer Congress, Second IFIP TC 10 International Conference on Biologically-Inspired Collaborative Computing
EditorsMike Hinchey, Anastasia Pagnoni, Franz Rammig, Hartmut Schmeck
Pages19-32
Number of pages14
DOIs
StatePublished - 2008

Publication series

NameIFIP International Federation for Information Processing
Volume268
ISSN (Print)1571-5736

Keywords

  • Peer-to-peer networks
  • Resource searching
  • Software agents
  • Swarm intelligence

ASJC Scopus subject areas

  • Information Systems and Management

Fingerprint Dive into the research topics of 'Heuristics for uninformed search algorithms in unstructured P2P networks inspired by self-organizing social insect models'. Together they form a unique fingerprint.

  • Cite this

    Dasgupta, P., & Antonson, E. (2008). Heuristics for uninformed search algorithms in unstructured P2P networks inspired by self-organizing social insect models. In M. Hinchey, A. Pagnoni, F. Rammig, & H. Schmeck (Eds.), Biologically-Inspired Collaborative Computing: IFIP 20th World Computer Congress, Second IFIP TC 10 International Conference on Biologically-Inspired Collaborative Computing (pp. 19-32). (IFIP International Federation for Information Processing; Vol. 268). https://doi.org/10.1007/978-0-387-09655-1_3