Improving the scalability of search in networks through multiple random walks

Abstract

We explore the use of multiple RWs for content search in a network where a failure occurs with very low probability and can be answered by a query to an external third party that always either has the content or knows where the content is located. We address the following fundamental questions: (i) How does the number of RWs affect search time as the system scales in size? (ii) What is the communications over-head incurred through the use of multiple RWs? (iii) Can the probability of a search failure be made sufficiently small? (iv) If a failed query is routed to a third party server, can the load placed on this server be made to scale? Our goal is to understand how different system and work-load parameters affect answers to the above questions. For example, it is necessary to attach a TTL to each RW in order to limit their communications overhead. Moreover, performance is sensitive to the demand pattern for content and to the level of content replication.