TY - GEN
T1 - Heuristics for uninformed search algorithms in unstructured P2P networks inspired by self-organizing social insect models
AU - Dasgupta, Prithviraj
AU - Antonson, Erik
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Peer-to-peer networks
KW - Resource searching
KW - Software agents
KW - Swarm intelligence
UR - http://www.scopus.com/inward/record.url?scp=47849122549&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=47849122549&partnerID=8YFLogxK
U2 - 10.1007/978-0-387-09655-1_3
DO - 10.1007/978-0-387-09655-1_3
M3 - Conference contribution
AN - SCOPUS:47849122549
SN - 9780387096544
T3 - IFIP International Federation for Information Processing
SP - 19
EP - 32
BT - Biologically-Inspired Collaborative Computing
A2 - Hinchey, Mike
A2 - Pagnoni, Anastasia
A2 - Rammig, Franz
A2 - Schmeck, Hartmut
ER -