Decentralized algorithms for search and routing in large-scale networks.

摘要

During the past decade, advances in technology and science have led to many large-scale distributed systems which can be characterized as networks. Some examples include the World Wide Web, the Internet, the power grid, wireless sensor networks, and military (net-centric) logistics. The scale of the size of these networks is substantially different from the networks considered in traditional graph theory. Further, these networks do not have any pre-specified structure/order or any design principles. Hence, the problems posed in such networks are very novel. Recent years has witnessed an explosion of interest across different disciplines, in understanding and characterizing such large-scale networks, which led to development of a new field called "Network science". This activity was mainly triggered by significant findings in real-world networks which led to a revival of network modeling and gave rise to many path breaking results. Until now, a major part of this research was focused on modeling and characterizing the behavior of the networks. However, the ultimate goal of modeling these networks is to understand and optimize the dynamical processes taking place in the network.; Search and routing is one of the most important and prevalent process in many real-world networks. Many times one needs to transport raw material/computer files/messages from one node to another using the edges of the network. In traditional graph theory, there do exist abundant number of algorithms that can compute the optimal paths in the network. However, these algorithms assume that global information of the network is available, i.e. how each and every node is connected in the network is known. But in some scenarios, it is not possible to have access to global information of the network and we need to have decentralized algorithms that can navigate through the network by using only local information. In this dissertation, we address an important process of search and routing in large-scale networks. This forms the core problem of this thesis. Examples include routing of sensor data in wireless sensor networks, locating data files in peer-to-peer networks, connecting relief workers in a disaster scenario, and finding information in distributed databases. Decentralized search and routing in networks is broadly classified into two types of networks, namely, non-spatial networks and spatial networks.; In non-spatial networks, we study trade-offs presented by local search algorithms in networks which are heterogeneous in edge weights and node degree. We demonstrate that search based on a network measure, local betweenness centrality (LBC), utilizes the heterogeneity of both node degrees and edge weights to perform the best in scale-free weighted networks. We show that the performance of LBC search is similar to BC search, which utilizes the maximum information about a neighbor. Further, we demonstrate that the search based on LBC is universal and performs well in a large class of complex networks. We also test the algorithms on the peer-to-peer network, Gnutella, and discuss the results obtained.; In spatial networks, we consider a family of parameterized spatial network models that are heterogenous in node degree. We investigate several algorithms and illustrate that some of these algorithms exploit the heterogeneity in the network to find short paths by using only local information. In addition, we demonstrate that the spatial network model belongs to a class of searchable networks for a wide range of parameter space. Further, we test these algorithms on the U.S. airline network which belongs to this class of networks and demonstrate that searchability is a generic property of the U.S. airline network. These results provide insights on designing the structure of distributed networks that need effective decentralized search algorithms.