Alhussein Abouzeid Research:
Systems: Communication Networks; Wireless Ad Hoc and Sensor Networks; Peer-to-Peer Networks.
Applied Theory: Stochastic Processes; Algorithm and Protocol Complexity; Multi-layer Optimization; Information Theory; Queuing Theory.
Project "Randomized": Randomized Algorithms for Overlay and Disconnected Networks
Locating a resource/ service or a peer efficiently is one of the most important issues related to unstructured decentralized networks. The objective of a search mechanism is to successfully locate resources while incurring low overhead and low delay. In order to fulfill this objective, several random walk based search algorithms have been proposed. However, no analytical model has been proposed to quantify the effect of parameters of random walk, such as the number and time to live (TTL) of random walkers, on the performance of search algorithms.
In this work we develop a mathematical model for random walk search in a peer-to-peer network. Using the model we derive analytical expressions for the performance metrics, such as delay, overhead and success rate, of the search in terms of the popularity of the resource being searched for and the parameters of random walk. We propose an algorithm that uses the analytical expressions in order to adaptively set the parameters of random walk so that it maintains a certain minimum level of performance. The algorithm is called Equation Based Adaptive Search (EBAS). We also propose a method for maintaining popularity estimates of the resources in the network. The work is based on an important recent observation regarding the relationship between random walk and uniform sampling. The work is currently being extended to utilize location information. This extension is specifically useful for delay tolerant networks (DTNs).
N. Bisnik and A.A. Abouzeid, “” Computer Networks, in press, available online (ScienceDirect) 18 September 2006. (Conference version in HoTP2P 2005).