Hybridflood algorithms minimizing redundant messages and maximizing efficiency of search in unstructured P2P networks - Barjini, Hassan (2012)
Unstructured peer-to-peer (P2P) networks, aggregate the slack resources on each peer, which may include bandwidth, storage space, and computing power. As a peer joins this P2P network, the total demand and total capacity of the system simultaneously increase. However, in a typical client-server network, as a client joins the network it only shares its demands, not its resources. Thus as more clients join the client-server network fewer resources are available to serve each client. Besides, the decentralized structure of a P2P network increases its robustness because it removes the single point of failure that can be inherent in a client-server based system. Therefore the unstructured model of the P2P network has attracted the greatest attention from both users and the researcher communities. Searching is an essential and basic activity for all P2P applications. Thus, there are a large number of research works have focused on unstructured P2P search facilities. There are two main reasons driving the research interest in this arFirst, the upward trend of digital information production, such as HTML, music and image files, requires a scalable information infrastructure that is capable of indexing and searching. Recent studies have shown that more than 97% of information produced worldwide is in a digital form. The amount of digital information is expected to grow exponentially. There are many challenges posed by such a huge amount of information for existing search systems. Second, compared to traditional centralized networks, unstructured P2P networks are particularly attractive and promising due to their scalability, availability, low cost, easy deployment, and data freshness. Meanwhile the fundamental property of existing and scalable unstructured P2P networks is the high heterogeneity of the peers that participate in the network. The heterogeneity of peers in unstructured P2Ps introduces both challenges and opportunities when designing a P2P network. Flooding is a basic file search procedure in unstructured P2P file-sharing systems. In fooding a peer initiates the file search operation by broadcasting a query to its neighbors, who continue to propagate it to their neighbors. Flooding has no knowledge about network topology nor files or resources distribution, so it ofers an attractive method for file discovery in dynamic and developing networks. In the meantime, fooding produces exponentially redundant messages at each hop. Consequently, the growth of redundant messages limits the system's scalability and causes unnecessary trafic in networks. In this thesis, we combine two search techniques to tackle this issue and improve P2P search performance in terms of search efficiency and the quality of the search results. We proposed two novel search algorithms named QuickFlood and HybridFlood. QuickFlood combines two food-based searches; fooding and teeming. QuickFlood is performed in two steps, in a first step the algorithm performs fooding in a limited number of hops. In the second step the algorithm follows a teeming search. QuickFlood compared with blocking expanding ring search decreased redundant messages by 70%, increased two-time success rate and decreased latency by 30%. Therefore, the algorithm enhanced unstructured P2P search by increasing scalability, efficiency and reliability of search. HybridFlood is also performed in two steps. The first step performs fooding with a limited number of hops. In the second step, nosey nodes are selected in each searching horizon. The nosey nodes are nodes which have the most links to other nodes. These nodes maintain the data index of all client nodes. HybridFlood in comparison to the blocking expanding ring search decreased redundant messages by 80%, increased the success rate by 2.5, and decreased of latency by 80%. In the other word the algorithm improved unstructured P2P search's scalability, efficiency and reliability. We provided analytical studies for fooding, QuickFlood and HybridFlood. The analytical results provided the best hop threshold point for the optimum growth rate coverage and redundant messages from the three systems. It also proved that in HybridFlood, broadcasting messages are reduced by at least an order of magnitude. Thus, the proposed algorithms enhance the performance of the search by reducing redundant messages, increasing the success rate and decreasing latency. The simulation experiments validated the analytical results.