Range and cover queries in overlay networks

• US 7,516,116 B2
• Filed: 04/07/2006
• Issued: 04/07/2009
• Est. Priority Date: 04/07/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zheng, Changxi, Li, Shipeng, Shen, Guo Bin
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Quader; Fazlul
• Application Number:
  US11/279,003
• Publication Number:
  US 20070239759A1
• Time in Patent Office: 1,096 Days
• Field of Search: 707/1, 707/2, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

System and methods for range and cover queries in overlay networks are described. In one aspect, respective node intervals [s, t] of multiple node intervals are allocated to corresponding nodes in a segment tree. Each integer s and t corresponding to an index to a sorted array of possible endpoints of the node intervals. Each node in the segment tree corresponds to a particular computing device (peer) of multiple computing devices in an overlay network. A node interval [s, t] is assigned to a particular peer associated with a key. This assignment provides a connection between node interval structural information of the segment tree and an underlying structure-less routing substrate in the overlay network. The segment tree is distributed across the peers for query operations over DHT.

Claims

1. A computer implemented method, the method comprising:

generating a segment tree on multiple participating computing devices (peers) comprising one or more memory units storing computer-executable instructions executable on one or more processors, the generated segment tree comprising multiple nodes, each node of the multiple nodes having a respective node interval [s, t] of multiple node intervals, s and t being indexes to a sorted array of possible endpoints of the node intervals, each node corresponding to a particular computing device of multiple participating computing devices (peers) in an overlay network, each node interval being assigned to a peer of the peers to provide a connection between node interval structural information of the segment tree and an underlying structure-less routing substrate associated with the overlay network; and

distributing the segment tree across the peers for query operations using a Distributed Hash Table (DHT) interface, wherein the query operations comprise cover query operations to locate each range of multiple ranges currently in the network that cover a given key and further wherein the query operations comprise range query operations with an associated range of [s, t] to find each key of multiple keys in a certain range over the network, and wherein the method further comprises;

splitting the range with a range splitting algorithm such that the range is split into a union of minimum node intervals associated with the segment tree; and

retrieving one or more keys maintained by corresponding peers in the network using the union of minimum node intervals a DHT get operation; and

wherein a final query result is a union of the one or more keys returned.

2. The method of claim 1, wherein the query operations further comprise one or more of:

range query operations to find each key of multiple keys in a certain range over the network; and

cover query for a range.

3. The method of claim 1, wherein the query operations comprise queries of sub-ranges that are executed in parallel.

4. The method of claim 1, wherein generating further comprises:

for each node of the multiple nodes, allocating a respective node interval [s, t] of the node intervals to the node; and

for each node interval, assigning the node interval to a peer of the peers.

5. The method of claim 1, wherein the method further comprises balancing load on nodes in the segment tree across levels using a downward load stripping mechanism that reduces redundancy embedded in the segment tree.

6. The method of claim 1, wherein the method further comprises:

inserting a given key to a specific leaf node in the segment tree;

inserting the given key to all ancestors of the leaf node; and

wherein the leaf node is identified using DHT lookup operations.

7. The method of claim 1, wherein the method further comprises:

removing a key from a leaf node and all ancestors of the leaf node, the segment tree comprising the leaf node and the ancestors, the leaf node being identified based on DHT; and

responsive to the removing, if a node transitions from saturation to un-saturation;

attempting to recruit an additional key from any child nodes to the node; and

if no additional key is recruited, marking the node as unsaturated.

8. The method of claim 1, wherein the method further comprises:

supporting one or more of multi-attribute range and cover queries by extending the range splitting algorithm to multi-dimensional scenarios such that a 2N branch segment tree is utilized to maintain N-D structural information.

9. The method of claim 1, wherein the query operations are cover query operations, and wherein the method further comprises one or more of inserting and removing segments associated with the segment tree from one or more corresponding peers.

10. The method of claim 9, further comprising:

decomposing a segment of the segments into a union of minimum node intervals using a range splitting algorithm; and

implementing one or more of the inserting and removing the segments with a respective interval belonging to the union of minimum node intervals.

11. A computer-readable memory unit comprising computer-program instructions that when executed by a processor perform acts comprising:

receiving a segment tree range and a delegated interval from a peer computing device of multiple peer computing devices in an overlay network, each peer computing device comprising one or more memory units storing computer-executable instructions executable on one or more processors, the delegated interval having been assigned in view of a particular key, the delegated interval providing a connection between node interval structural information of the segment tree and an underlying structure-less network routing substrate, wherein the segment tree supports query operation comprising cover query operations to locate each range of multiple ranges currently in the network that cover a given key; and

responsive to receiving the segment tree range and the delegated interval reconstructing a segment tree with multiple nodes, each node representing a respective node interval [s, t] of multiple node intervals, each integer s and t corresponding to an index to a sorted array of possible endpoints of the node intervals, the segment tree also having been constructed by the peer computing device, wherein the query operations comprise range query operations with an associated range of [s, t] to find each key of multiple keys in a certain range over the network, and wherein the computer-program instructions further comprise instructions for;

splitting the range with a range splitting algorithm such that the range is split into a union of minimum node intervals associated with the segment tree;

retrieving one or more kegs maintained by corresponding peers in the network using the union of minimum node intervals a DHT get operation; and

wherein a final query result is a union of the one or more keys returned.

12. The computer-readable memory unit of claim 11, wherein the segment tree supports query operations further comprising:

range query operations to find each key of multiple keys in a certain range over the network; and

cover query for a range.

13. The computer-readable memory unit of claim 11, wherein the query operations comprise queries of sub-ranges that are executed in parallel.

14. The computer-readable memory unit of claim 11, wherein the computer-program instructions further comprise instructions for balancing load on nodes in the segment tree by reducing redundancy across levels of the segment tree.

15. The computer-readable memory unit of claim 11, wherein the computer-program instructions further comprise instructions for:

inserting the key to a specific leaf node in the segment tree;

inserting the key to all ancestors of the leaf node; and

wherein the leaf node is identified using DHT lookup operations.

16. The computer-readable memory unit of claim 11, wherein the query operations are cover query operations, and wherein the computer-program instructions further comprise instructions for one or more of inserting and removing segments associated with the segment tree from one or more corresponding peers.

17. A computing device comprising:

one or more memory units storing computer-executable instructions executed on one or more orocessors;

query support means, executable on the one or more processors, to support cover queries over a DHT network, wherein query support means includes cover query operations to locate each range of multiple ranges currently in the DHT network that cover a given key; and

segment tree maintenance means, executable on the one or more processors, to implement one or more of insert and remove key operations in a segment tree that supports cover query,

wherein query operations comprise range query operations with an associated range of [s, t] to find each key of multiple keys in a certain range over the network, and wherein the computing device further comprises;

splitting the range with a range splitting algorithm such that the range is split into a union of minimum node intervals associated with the segment tree;

retrieving one or more keys maintained by corresponding peers in the network using the union of minimum node intervals a DHT get operation; and

wherein a final query result is a union of the one or more keys returned.

18. The computing device of claim 17, wherein the query support means also comprises means to support range queries over the DHT network, and wherein the segment tree maintenance means aiso comprises means to implement one or more of insert and remove key operations in a segment tree that supports range query.