Algorithmic performance of large-scale distributed networks: A spectral method approach

Abstract

Complex networks like the Internet, peer-to-peer systems, and emerging sensor and ad-hoc networks are large distributed decentralized communication systems arising repeatedly in today's technology. In such networks it is critical to characterize network performance as the size of the network scales. The focus of my work is to relate basic network performance metrics to structural characteristics of underlying network topologies, and to develop protocols that reinforce and exploit desired structural characteristics. For the case of the Internet at the Autonomous System level, we relate the graph theoretic notions of conductance and spectrum to network clustering and network congestion. In particular, we show how spectral analysis can identify clusters, and how the presence of clusters affects congestion. This is important for network prediction and network simulation. For the case of peer-to-peer networks we relate conductance and spectral gap to the fundamental questions of searching and topology maintenance. We propose new protocols for maintaining peer-to-peer networks with good conductance and low network overhead. We compare the performance of the traditional method of search by flooding to searching by random walks. We isolate cases of practical interest, such as clustered and dynamic network topologies, where the latter have superior performance. The improvement in the performance can be directly quantified in terms of the conductance of the underlying topology. We introduce further hybrid search schemes, of which flooding and random walks are special instances, which aim to improve the performance of searching by using locally maintained information about the network topology.