Random Walk Based Node Sampling in Self-Organizing Networks
Ming Zhong and Kai Shen
Department of Computer Science, University of Rochester
Random walk is a means of network node sampling that requires little index
maintenance and can function on almost all connected network topologies. With
careful guidance, node samples following a desired probability distribution can
be generated with the only requirement that the sampling probabilities of each
visited node and its direct neighbors are known at each walk step. This paper
describes a broad range of network applications that can benefit from such guided
random walks in dynamic and decentralized settings. This paper also examines
several key issues for implementing random walks in self-organizing networks,
including the convergence time of random walks, impact of dynamic network changes
and particularly resulted walker losses, and the difficulty of pacing walk steps
without synchronized clocks between network nodes. Our result suggests that with
proper management, these issues do not cause significant problems under many
realistic network environments.