Method and apparatus for distributed indexing

• US 20070079004A1
• Filed: 09/30/2005
• Published: 04/05/2007
• Est. Priority Date: 09/30/2005
• Status: Abandoned Application

• Current Assignee: NEC Laboratories America Inc (NEC Corporation)
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Chen, Liping, Tatemura, Junichi, Candan, Kasim, Cavendish, Dirceu, Agrawal, Divyakant
• Application Number:
  US11/240,068
• Publication Number:
  US 20070079004A1
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: G06F 9/5044 considering hardware capabilities

Abstract

Disclosed is a method and apparatus for providing range based queries over distributed network nodes. Each of a plurality of distributed network nodes stores at least a portion of a logical index tree. The nodes of the logical index tree are mapped to the network nodes based on a hash function. Load balancing is addressed by replicating the logical index tree nodes in the distributed physical nodes in the network. In one embodiment the logical index tree comprises a plurality of logical nodes for indexing available resources in a grid computing system. The distributed network nodes are broker nodes for assigning grid computing resources to requesting users. Each of the distributed broker nodes stores at least a portion of the logical index tree.

Claims

1. A system comprising:

a plurality of distributed network nodes;

each of said network nodes storing at least a portion of a logical index tree;

said logical index tree comprising a plurality of logical nodes;

wherein said logical nodes are mapped to said network nodes based on a hash function.

2. The system of claim 1 wherein each of said logical nodes is stored at least in the network node to which it is mapped.

3. The system of claim 1 wherein at least one of said network nodes stores all nodes of the logical index tree.

4. The system of claim 1 wherein each of said network nodes stores 1) a logical node which maps to the network node and 2) the logical nodes on a path from said logical node to a root node.

5. The system of claim 1 wherein:

said logical index tree further comprises replicated logical nodes; and

each of said network nodes stores the logical nodes which map to the network node.

6. The system of claim 1 wherein said logical nodes of said logical index tree map keys to values.

7. The system of claim 6 wherein said keys comprise a plurality of resource attributes and said values represent addresses of resources.

8. A method comprising:

maintaining a logical index tree comprising a plurality of logical nodes;

storing at least a portion of said logical index tree in a plurality of distributed network nodes; and

mapping said logical nodes to said network nodes based on a hash function.

9. The method of claim 8 further comprising the step of:

storing logical nodes in at least the network nodes to which they map.

10. The method of claim 8 wherein said step of storing comprises storing the entire logical index tree in at least one of said network nodes.

11. The method of claim 8 wherein said step of storing comprises the steps of:

storing a logical node in the network node to which said logical node maps; and

storing the logical nodes on a path from said logical node to a root node in said network node.

12. The method of claim 8 wherein:

said step of maintaining a logical index tree comprises replicating logical nodes; and

said step of storing comprises storing the logical nodes of said logical index tree in the network nodes to which said logical nodes map.

13. A grid computing resource discovery system comprising:

a logical index tree comprising a plurality of logical nodes for indexing available resources in said grid computing system,

a network of distributed broker nodes for assigning grid computing resources to requesting users, each of said distributed broker nodes storing at least a portion of said logical index tree;

wherein said logical nodes are mapped to said broker nodes based on a distributed hash function.

14. The system of claim 13 herein each of said logical nodes is stored at least in the broker node to which it maps.

15. The system of claim 13 wherein at least one of said broker nodes stores all of said logical nodes.

16. The system of claim 13 wherein each of said broker nodes stores:

1) logical leaf nodes which map to the broker node and

     2) logical nodes on paths from said logical leaf nodes to a root node.

17. The system of claim 13 wherein:

said logical index tree further comprises replicated logical nodes; and

each of said broker nodes stores the logical nodes which map to the broker node.

18. The system of claim 13 wherein said logical nodes map keys to values.

19. The system of claim 18 wherein said keys comprise a plurality of grid computing resource attributes and said values represent network addresses of grid computing resources.