Range and Cover Queries in Overlay Networks

• US 20070239759A1
• Filed: 04/07/2006
• Published: 10/11/2007
• Est. Priority Date: 04/07/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Shipeng, Zheng, Changxi, Shen, Guo
• Granted Patent: US 7,516,116 B2
• Time in Patent Office: Days
• 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 method at least partially implemented by a computer, the method comprising:

generating a 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.

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

cover query operations to locate each range of multiple ranges currently in the network that cover a given key;

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 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;

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.

9. The method of claim 8, 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 2^N branch segment tree is utilized to maintain N-D structural information.

10. 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.

11. The method of claim 10, 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.

12. A computer-readable storage medium 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, 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; 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;

13. The computer-readable storage medium of claim 12, wherein the segment tree supports query operations comprising:

cover query operations to locate each range of multiple ranges currently in the network that cover a given key;

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

cover query for a range.

14. The computer-readable storage medium of claim 12 wherein the query operations comprise queries of sub-ranges that are executed in parallel.

15. The computer-readable storage medium of claim 12, 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.

16. The computer-readable storage medium of claim 12, 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.

17. The computer-readable storage medium of claim 12, 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 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 computer-readable storage medium of claim 12 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.

19. A computing device comprising:

query support means to support cover queries over a DHT network; and

segment tree maintenance means to implement one or more of insert and remove key operations in a segment tree that supports cover query.

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