Zone indexing: Optimizing the balance between searching and indexing in a loosely structured overlay
While structured peer-to-peer systems are efficient in terms of overhead, they still lack the unstructured system's flexibility and ability to support a wide range of complex queries. This paper examines systems supporting complex queries, deterministic operation, and a fair load distribution between nodes. The aim is to minimize the bandwidth and node load using an optimal level of indexing. The paper first theoretically examines the optimal balance of search and index messages using a search/index space model. This balance is fundamentally determined by the frequency of search requests and index updates. Based on this study, the paper proposes a novel loosely structured peer-to-peer system, Zone indexing, that can balance between index update traffic and search traffic in order to minimize the bandwidth overhead. Nodes are organized into a ring structure. The ring is divided into overlapping zones, within which index updates are distributed. We present an overlay maintenance algorithm with low-cost join and leave operations and a high churn resistance. We further propose a method to dynamically adjust the zone size in order to maintain optimal performance when the network size or user behavior changes. Additionally, we propose a method to limit the search delay by introducing parallel searching. The proposed solutions are evaluated mathematically and the analysis is verified with simulation.