Systems, methods and programming for routing and indexing globally addressable objects and associated business models

• US 20060218167A1
• Filed: 05/26/2006
• Published: 09/28/2006
• Est. Priority Date: 09/18/2001
• Status: Abandoned Application

• Current Assignee: Benjamin B. Wilken, Carleton J. Bosley, Gitika Srivastava
• Original Assignee: Benjamin B. Wilken, Carleton J. Bosley, Gitika Srivastava
• Inventors: Wilken, Benjamin B., Bosley, Carleton J., Srivastava, Gitika
• Application Number:
  US11/441,862
• Publication Number:
  US 20060218167A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms

Abstract

Methods, apparatus, and programming recorded in machine readable memory are provided for the index, search and retrieval of objects on a global network. This inventive system embeds a distributed index in a routing layer to enable fast search. The method provides dynamic insertion, lookup, retrieval, and deletion of participating nodes, objects and associated metadata in a completely decentralized fashion. Nodes can dynamically join and leave the network. This infrastructure can be applied to content networks for publishing, searching, downloading, and streaming.

Claims

1. A node in a distributed indexing network in which each node has an address in an index address space and in a separate network address space, said node comprising:

machine readable memory for storing program instructions and data structures;

one or more processors for executing program instructions stored in said memory;

program instructions stored in said memory for;

associating a subset of the index address space with the node;

maintaining a contact list, which stores the index space and network address for each of a plurality of contacts, each of which is another node in said indexing network;

treating a minority of said contact list as direct contacts and the rest of said contacts as indirect contacts;

attempting to communicate with each direct contact with a minimum frequency, to determine whether or not that direct contact is still a member of the network; and

responding to a determination that a given direct contact is no longer functioning as a member of the network by finding a new direct contact to replace that given contact and replacing the replaced direct contact in the node'"'"'s contact list with the index and network address of the replacement contact;

wherein the node responds to a search request for a given index address that does not fall in the subset of the index address space associated with the node by using, as the next node to send such a search request to, the address on its contact list that is closest to the given address, whether that address is a direct or indirect address.

2. A node as in claim 1 wherein:

said node learns the index address and network address of each of the node'"'"'s indirect contacts from an associated one of the node'"'"'s direct contacts; and

said node learns about changes in the state of a given indirect contact from the same direct contact from which it learned the indirect contact'"'"'s index and network address.

3. A node as in claim 2 wherein:

said program instructions include instructions for responding to a request from another node for a set of contacts by sending the requesting node a subset of the node'"'"'s contacts and storing a record that the node has sent said subset of contacts to the other, requesting, node; and

wherein said node responding to a request determines that a given direct contact is no longer functioning as a member of the network also includes sending to any other node to which the node has previously sent the given direct contact in response to a contact request a message that the given contact has been replaced, including the index address and network address of the replacement contact.

4. A node as in claim 3 wherein said program instructions include instructions for responding to a message from another node indicating that a given indirect contact supplied to the node by said other node has been replaced by a new indirect contact having a given index and network address by:

replacing the given indirect contact in the node'"'"'s contact list with the index and network address of the replacement node; and

sending to any other node to which the node has previously sent the replaced indirect contact in response to a contact request a message indicating that the previous communicated contact has been replaced, including the index and network address of the replacement contact.

5. A node as in claim 1 wherein said node does not directly communicate with indirect contacts at a frequency greater than one tenth the minimal frequency with which it communicates with direct contacts for the purpose of determining whether or not that indirect contact is still a member of the network, and learns about changes in status of such indirect contacts through communications with direct contacts.

6. A distributed indexing network in which each node has an address in an index address space and in an independent network address space, said network comprising:

a plurality of nodes each of which includes;

machine readable memory for storing program instructions and data structures;

one or more processors for executing program instructions stored in said memory;

program instructions stored in said memory for;

associating a subset of the index address space with the node;

storing on said node indexed information having an associated index address value within the node'"'"'s associated subset of the index address space; and

responding to a request for information associated with a given index value by accessing information, if any, that has been stored on the node in association with that index value;

wherein all or a portion of the subset of the index address space associated with each of a plurality of nodes overlaps, so that each node in said plurality of nodes stores indexed information for a similar set of index address values.

7. A node as in claim 6 wherein said nodes contain program instructions for:

responding to the entry of new information to be indexed with a given index value by performing a search to find a node associated with a subset of the index space that includes said given indexed value;

storing the new information on the node found by the search in association with the given index value;

communicating between nodes associated with a given portion of the index space information that has been indexed under an index value that falls within said given index space portion on one such node; and

responding on a given node to such communication by storing a copy of such information in association with said index value.

8. A node as in claim 6 wherein said nodes contain programming instructions for:

enabling a node to determine the number of nodes that index a given portion of the index address space; and

responding to a determination that the number of nodes that index said given portion of the index address space is below a given lower limit, by sending messages to one or more other nodes not currently indexing said given portion of the index space requesting that said other nodes start to index said given index space portion;

responding to such a request by changing the portion of the index address space a given node indexes to include said requested portion of the index address space.

9. A node in a distributed indexing network in which each node has an address in an index address space and in a separate network address space, said node comprising:

machine readable memory for storing program instructions and data structures;

one or more processors for executing program instructions stored in said memory;

program instructions stored in said memory for;

associating a subset of the index address space with the node;

storing on said node indexed information having an associated index address value within the node'"'"'s associated subset of the index address space;

responding to a request for information associated with a given index value by accessing information, if any, that has been stored on the node in association with the given index value;

defining a set of the network'"'"'s nodes, including the node, that form a logical node, comprised of nodes that are all associated with the same subset of the index address space and store substantially the same indexed information;

communicating with other nodes in said logical node to obtain any new information that such other nodes have stored that is not yet stored on the node and that has an associated index address value within the logical node'"'"'s associated subset of the index address space; and

storing a copy of said new information on the node, so that the node, if it stays in the network long enough will obtain a copy of substantially all such information that has been stored by other nodes in the logical node over a given period of time.

10. A node as in claim 9 wherein:

said memory stores instructions for forming an estimate of the number of nodes in the node'"'"'s logical node; and

said memory stores instructions for at least one of the following;

responding to such an estimate indicating that the number of nodes in the logical node is above a certain size by performing one or more functions to split the logical node into two or more new separate logical nodes each associated with a separate portion of the subset of the index address space associated with the logical node;

or

responding to such an estimate indicating that the number of nodes in the logical node is below a certain size by performing one or more functions to merge the node'"'"'s current logical node with a second, different current logical node to form one new logical node having an associated subset of the index address space that includes the subsets of the index address space associated with both the node'"'"'s current logical node and the second current logical node.

11. A node as in claim 10 wherein the node'"'"'s memory stores instructions for performing both said functions to split and to merge.

12. A node as in claim 11 wherein:

said program instructions represent the index address space by a set of possible values that can be represented by a set of address bits; and

the nodes that form a given logical node all share a common set of bit values for a given sequence of the most significant bits of said sequence of address bits; and

said splitting and/or merging of logical nodes involve changing the length of the sequence of the most significant bits of the index address space that are shared by the nodes of the node'"'"'s logical node.

13. A node as in claim 9 wherein said memory stores instructions for:

forming an estimate of the number of nodes in the node'"'"'s logical node; and

responding to such an estimate indicating that the number of nodes in the logical node is below a certain size by requesting other nodes in the network to join the node'"'"'s logical node by changing their index address value to one falling within the subset of the index address space associated with the node'"'"'s logical node.

14. A node as in claim 9 wherein said communicating with other nodes in said logical node includes communicating at some minimal frequency with different nodes in its logical node, in which at least one given side in each such communication:

receives a list of information updates stored by the other side in the communication, where each such update indicates the node on which it originated, and an indication of the relative time of update'"'"'s origin; and

obtains from the other side, and stores a copy of, any updates that the given side does not already have a copy of.

15. A node as in claim 9 wherein said instructions include instructions for:

obtaining, when the node is entering the distributed indexing network, at least two index address values for use as potential index address values for the node;

for each of said potential index address values;

performing a search on the network for another node belonging a logical node associated with a subset of the index address space that includes that potential address value; and

querying each such other node as to the population of its associated logical node;

selecting that one of the potential index address value having the associated logical node with the smallest population as the node'"'"'s new index address value; and

then commencing said communication with other nodes in the logical node associated with the node'"'"'s new index address value.

16. A node as in claim 9 wherein:

said program instructions represent the index address space by a set of possible values that can be represented by a set of index address bits; and

the nodes that form a given logical node all share a common set of bit values for a common subset of said index address bits.

17. A node as in claim 16 wherein said shared bits are a sequence of the most significant bits in said index address bits.

18. A node in a distributed indexing network in which each node has an address in an index address space and in a separate network address space, said node comprising:

machine readable memory for storing program instructions and data structures;

one or more processors for executing program instructions stored in said memory;

program instructions stored in said memory for;

associating a subset of the index address space with the node;

storing on said node a keyword entry for each of one or more keywords having an index value corresponding to the node'"'"'s associated subset of the index address space, where each such keyword entry associated with a given keyword stores information relating to one or more objects associated with the given keyword; and

responding to a request for information associated with a keyword index value for which the node stores a corresponding keyword entry by accessing information stored on the node in that keyword entry.

19. A node as in claim 18 wherein said index value associated with a keyword is a hash of the keyword.

20. A node as in claim 20 wherein a keyword entry associated with a given keyword contains lists of one or more files associated with the given keyword.

21. A node as in claim 20 wherein:

a keyword entry includes an index value associated with each file in said list of one or more files; and

said memory also stores program instructions for storing on said node a file entry for each of one or more files having index values that are within the subset of the index address space associated with the node.

22. A node as in claim 21 wherein each of said file entries includes information on each of a set of one or more copies of all or a portion of the entry'"'"'s associated file stored on one or more different nodes of said network, including the network addresses of the node on which each such copy is stored.

23. A node in a distributed indexing network in which each node has an address in an index address space and in a separate network address space, said node comprising:

machine readable memory for storing program instructions and data structures;

one or more processors for executing program instructions stored in said memory;

program instructions stored in said memory for;

associating a subset of the index address space with the node;

storing on said node a file entry for each of one or more file'"'"'s having an index corresponding to the node'"'"'s associated subset of the index address space, where each such file entry stores information relating its associated file and information on each of a set of one or more copies of all or a portion of the entry'"'"'s associated file, which copies can be stored on one or more different nodes of said network, including the network addresses of the node on which each such copy is stored; and

receiving a request for information associated with a file having a given index value, which includes an indication of the network location of the node that has generated such a request;

responding to such a file-by-index request, if the index value of the requested file falls within the subset of the index address space associated with the node, by sending to the node that sent the request information on a set of one or more copies of all or part of the file listed in the requested file'"'"'s entry, including the network address of node'"'"'s storing those copies;

wherein said selecting on which file copies to send information to the requesting node includes making said selections as a function of the apparent appropriateness of the network location at which a given file copy is stored given the network location of the requesting node.