DHT overlay schemes for scalable p-range resource discovery

The information service is a critical component of a grid infrastructure for resource discovery. Although P2P computing paradigm could address some of the scalability issues that plagued grid resource discovery, most existing distributed hash table (DHT) based P2P overlays have difficulty in treating attribute range queries that are common in resource discovery lookups due to the inherent randomness of hash functions. Recently, there have been various attempts to solve the range search problem over DHT networks [Aberer, et al. (2003), Gao and Steenkiste (2004), Ratnasamy, et al. (2003), and Tanin, et al. (2005)]. Central to all of these is a mapping scheme which maps the tree-structured logical index space to some DHT-based physical node space. In this paper, we propose a general framework to put all these under the same umbrella based on how mapping of the tree-structured index that identifies a physical node responsible of a particular range is done through replication. We identify three schemes which should cover the spectrum of all meaningful replication schemes: the tree replication scheme (TRS) replicates the entire tree; the path caching scheme (PCS) replicates paths from root to leaves; and the node replication scheme (NRS) replicates individual logical nodes.