Applying random walks in structured and self-organizing networks: Evaluation by transient analysis

摘要

Dynamic overlay networks on the Internet and especially ad hoc networking scenarios often rely on self-organizing schemes for distributed communication and for construction and modification of the topology. When there are no central management facilities and search indices available, flooding is a standard method to collect knowledge about the network structure and the content on the nodes. In recent time, random walks have attracted attention as an alternative search method whose efficiency has been demonstrated by simulation studies. In this paper we use transient analysis as a simple and scalable approach to examine the properties of random walks. The convergence to steady state and the coverage of the network in the course of the random work are main characteristics of interest. In our evaluations we consider randomly build networks in comparison to structured networks of different type and size. In addition to basic random walks, an improvement by avoiding a direct return to the previous node is included.