WWW 2007 / Poster Paper

Topic: Search

SRing: A Structured Non DHT P2P Overlay Supporting String Range Queries
Xiaoping Sun
China Knowledge Grid Research Group Institute of Computing Technology Graduate School of Chinese Academy of Sciences, China

Xue Chen
China Knowledge Grid Research Group Institute of Computing Technology Graduate School of Chinese Academy of Sciences, China

sunxp@kg.ict.ac.cn ABSTRACT
This paper presents SRing, a structured non DHT P2P overlay that efficiently supports exact and range queries on multiple attribute values. In SRing, all attribute values are interpreted as strings formed by a base alphabet and are published in the lexicographical order. Two virtual rings are built: N-ring is built in a skip-list way for range partition and queries; D-ring is built in a small-world way for the construction of N-ring. A leave-and-join based load balancing method is used to balance range overload in the network with heterogeneous nodes.

chenxue@kg.ict.ac.cn
of length m as their name IDs from the string space S formed by E. n nodes are sorted in increasing order of their name IDs, nid1 S nid1 S ... S nidn, and form a ring called N-ring. Node nidk is responsible for all strings falling in range (nidk-1, nidk] in S. Ntable is built to support range queries in N-ring. For building Nring, node nidk is also assigned a random digital string ID didk of length m drawn from S, initially the same as its random name ID. Digital IDs are also sorted in increasing order to form a ring called D-ring. D-table is built to support query on digital IDs in D-ring. N-ring is constructed based on common prefixes of digital IDs of nodes in a skip-list way [3] to support efficient range queries on attribute strings. Those nodes with digital IDs that share a common prefix of length l form a sub-ring at level l where nodes are sorted in increasing order of their name IDs, for l = 0, 1, 2, ..., and m (Figure 1 (a)). Level 0 is the underlying N-ring. Each node connects to its predecessor and b = log L successors in the each sub-ring (L = |E|) (Figure 1 (b)). Randomness of digital IDs ensures the efficiency of N-tables in any distribution of name IDs. When a node joins N-ring, first it locates its digital ID in D-ring and joins D-ring. From its predecessor and successor in D-ring, the node chooses the one sharing with it longer common prefix of digital ID as the bootstrap node. Then it lookups its name ID in Nring from that bootstrap node. Query is forwarded along the link closest to the target. When jumping into a different sub-ring, the node inserts itself into that sub-ring. When forwarding a range query, query messages are forwarded to the closest one to the target range. It can achieve O(log n) hops.

Categories and Subject Descriptors
H.3.4 [Information Storage AND Retrieval]: Systems and Software-Distributed systems, Information networks.

General Terms
Algorithms, Design, Experimentation.

Keywords
P2P, multi-attribute, range queries, load balancing.

1. INTRODUCTION
Distributed Hash Table (DHT) overlays have high scalability of exact query routing in large-scale P2P systems [1]. However, it is difficult to implement range queries in DHT overlays. One way is to build index on DHT overlays to support range queries [4]. Another natural way is to let nodes partition the original keyword space to preserve their original order. Two key issues must be addressed, efficient query routing and balanced load distribution. This paper introduces a structured non DHT P2P overlay SRing that efficiently supports exact and range queries on multiple attribute value strings of data objects. Range overload can be quickly smoothed in heterogeneous environments without global knowledge of load distribution.

2. SYSTEM ARCHITECTURE
In SRing, data objects are identified by a set of attribute values. All attribute values are interpreted as strings consisting of characters of a base alphabet E = {e1, e2, ..., eL} (L = |E|). We assume that such interpretation can preserve the original order of attribute values. Many data types such as numeric values, date, and text have this property. All strings are sorted by the lexicographical order S based on E. Nodes randomly draw strings
Copyright is held by the author/owner(s). WWW 2007, May 8­12, 2007, Banff, Alberta, Canada. ACM 978-1-59593-654-7/07/0005.

Figure 1. Architecture of SRing, N-table and D-table. When joining D-ring, the node lookups its digital ID in D-ring and inserts into the overlay at the node currently holds its digital ID. D-table is built in a small-world way without requiring the estimate of network size. In node nk with digital ID string didk = a1a2...am (ai  E), D-table contains m rows with each having b = log2 L long links (Figure 1(c)). In the ith row, a long link ri,j is produced by a seed ID string rsi,j = a1a2,...biai+1...am. rsi,j differs

1193


WWW 2007 / Poster Paper from didk at the ith character. Let v(ai) denote the position of character ai in E. Let d = L / 2p and p is a real number uniformly generated in range [0, log2L]. Then, (v(ai) + d) mod L is the position of character bi in E. The distance d between bi and ai in E follows the harmonic probability distribution in range (0, L]. In each row of D-table, we generate b = log2 L seed IDs using the same harmonic probabilistic distribution. Total m log2 L seed IDs are produced. It approximates Kleinberg's small-world network [2] in one-dimensional ring, without the estimate of network size. After generating all seed IDs, nk locates remote nodes that hold these seed IDs in D-ring and setups long links to them. In a query process in D-ring, each hop chooses the link closest to the target string for the next jump. Since many seed IDs correspond to the same node, D-table contains O(log n) distinct remote links and the routing hops is O(log n) in an overlay with n nodes. Like structured P2P overlays with ring geometries, D-table has more resilience in neighbor selection and route selection than tree geometries that support prefix-based routing [1], including the numeric routing table of SkipNet [3].

Topic: Search overlays with equal capacity (Unf-cap) (Figure 3 (b)). In each round one request is sent out. In all cases, the variance of the utilizations of nodes drops quickly. The average move times of buckets grows very slowly with the increasing initial variance.

Figure 2. Query hops and routing table size.

3. LOAD BALANCING IN SRING
In the local storage of a node, strings are partitioned into a number of buckets, each with a predefined number of strings. The load of ni is measured by a utilization factor ui = li / ci,, where li is the number of buckets in ni and capacity ci is the maximum number of buckets ni can hold. Load balancing process is periodically executed in each node to reduce the variance of ui in the overlay. During the load balancing, ni concurrently sends out at most K  1 random requesting messages that contain nidi, didi, li, ci and a random digital ID dids. Only when requests get responses or time out, can node ni send more. Each requesting message is routed in D-ring to the node nr that holds dids and is recorded in the incoming list of nr. ni also keeps the load information li + 1 and ci + 1 of its successor ni+1 in N-ring. Then, ni draws messages from its incoming request list for making load balancing decision. For a request from nk with lk load and ck capacity, the utilization gain is gk = uk - ui. If the largest gain gm < 0, ni rejects all requestors. If gm > 0, we consider the increased load in the successor ni+1 of ni. Let l l  m = m - m and  i +1 = li +1 + li - li +1 . If m > i+1, it means that cm ci + cm ci +1 ci +1 the utilization increased in ni+1 is smaller than the utilization decreased in nm. Then, ni is moved to share mb = lmci / (cm + ci) number of buckets of nm. If mb < 1, ni rejects all requestors and waits for the next round of load balancing. When moving, ni transfers all buckets to ni+1 and quits. Then it sets its name ID to the largest string among those moved buckets from nm and joins N-ring again. It takes O(log n) messages. Digital IDs and D-tables of all involved nodes need not to be changed. Figure 3. Load balancing effects and costs.

5. CONCLUSION
SRing can efficiently support range queries on multiple attribute value strings and can effectively smooth range overload in heterogeneous environments. SRing has potentials in supporting semantics-rich queries in large-scale distributed networks.

6. ACKNOWLEDGEMENTS
This work was supported by the National Basic Research Program (973 project no. 2003CB317000) and the National Science Foundation of China (No. 60503047)

7. REFERENCES
[1] K. Gummadi, R. Gummadiy, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica, "The Impact of DHT Routing Geometry on Resilience and Proximity", In Proceeding of SIGCOMM 2003. pp. 381-394, 2003. [2] J. Kleinberg, "The Small-World Phenomenon: An Algorithmic Perspective", in Proceeding of 32nd ACM STOC, pp. 163-170, 2000. [3] N. Harvey, M. Jones, S. Saroiu, M. Theimer, and A. Wolman, "SkipNet: A Scalable Overlay Network with Practical Locality Properties", In Proceeding of USITS 2003, pp. 113­ 126, Mar. 2003. [4] H. Zhuge, X. Sun, J. Liu, E. Yao and X. Chen, "A Scalable P2P Platform for the Knowledge Grid", IEEE Transactions on Knowledge and Data Engineering, Vol. 17, No.12, pp. 17211736, 2005.

4. EXPERIMENTS
Figure 2 (a) shows that query hops is not affected by L in both Nring and D-ring. Query hops and routing table size of N-ring and D-ring grow logarithmically with increasing n (Figure 2(b)). We test the load balancing method with Zipfian distribution of capacities (Zipf-cap) and uniform distribution (Unf-bucket) of bucket loads (Figure 3. (a)). Hotspot distributions (Hot-bucket) with all B buckets of strings located in h nodes are also tested in

1194