Abstract
In this chapter we describe a mechanism to search for resources in unstructured peer-to- peer (P2P) networks using ant algorithms implemented through software agents. Traditional resource search algorithms in P2P networks use an uninformed or blind search among the various nodes of the network. In contrast, the resource search algorithm described in this chapter performs an informed search using the ant-based heuristic. In our algorithm, ants, implemented as software agents, are created in response to a user’s resource search query. An ant reinforces the route that yields a successful search for directing ants in the future towards nodes with higher probability of locating resources. We describe and compare different reinforcement strategies used by ants to perform efficient resource search in P2P networks.
Key Terms in this Chapter
Resource Discovery: The mechanism used by a node to search for resources among other nodes of the network. A user at a node provides a search query containing a set of keywords corresponding to the resource being searched for. A resource discovery protocol is then used to forward the search query to other nodes and search for the resource on those nodes. When a resource is located at a node, a success message is sent to the node that originated the search query.
Ant Algorithm: Essentially, a reinforcement learning algorithm. In an ant algorithm, points that are good candidates for a solution to a problem get reinforced over time. When the algorithm terminates, the points that have been reinforced the most are selected as the solution(s) to the problem.
Peer: A node in a P2P network. A peer can provide services to other peers and also receive services from other peers. Because it can behave both as a server and a client, a peer is also known as a servant.
Unstructured P2P Network: Networks that do not use a pre-determined topology and grow in an ad-hoc manner. A node in an unstructured P2P network makes the decision to accept another node as a neighbor based on the number of resources shared by the latter node.
Peer-to-peer Network: A network consisting of an overlay or logical network between nodes that are interconnected by an underlying physical network. Users are located on nodes of the P2P network. A user at a node can store resources such as data files on its node and can share these resources with other nodes, as well as acquire new resources from other nodes in the network.
Pheromone: The metric used in an ant algorithm to reinforce points in the solution space of a problem. Pheromone decays over time.
Anti-Pheromone: Unlike pheromone, anti-pheromone is used to provide negative reinforcement in an ant algorithm. Points in the solution space that are marked with anti-pheromone are usually bad solutions to the problem. The negative reinforcement provided by the anti-pheromone ensures that these points are not included in successive iterations of the ant algorithm.
Node Discovery: The mechanism used by a newly joining node in a P2P network to determine the IP addresses of existing nodes in the network and selectively choose them as neighbors.
Structured P2P Network: In such a network, the network growth follows a specific topology as a ring or a hypercube. Resources are placed on nodes using a distributed hash table (DHT)-based algorithm. In structured P2P networks, operations such as determining the location of a newly joining node within the network and searching for resources are performed using deterministic algorithms.