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

• US 20030126122A1
• Filed: 09/18/2002
• Published: 07/03/2003
• Est. Priority Date: 09/18/2001
• Status: Active Grant

• Current Assignee: Skype Limited (Microsoft Corporation)
• Original Assignee: Stirling Bridge, Inc.
• Inventors: B. Wilken, Benjamin, Bosley, Carleton J., Srivastava, Gitika
• Granted Patent: US 7,054,867 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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. NODE IN DISTRIBUTED INDEXING SCHEME WHERE EACH NODE MAINTAINS ROUTING CONTACT LIST, MINORITY OF CONTACTS ARE DIRECT CONTACTS WHICH IT REPEATEDLY CHECK STATUS OF AND REPLACES IF THEY HAVE GONE INACTIVE, AND NODE RESPONDS TO SEARCH REQUEST BY USING CONTACT CLOSEST TO REQUESTED ADDRESS, WHETHER IT IS DIRECT OR INDIRECT CONTACT A node in a distributed indexing network (Define 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 instruction s 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 contacts 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. LEARNS ABOUT INDEX AND NETWORK ADDRESS OF EACH INDIRECT CONTACT FROM A GIVEN DIRECT CONTACT, AND LEARNS ABOUT CHANGES IN STATUS OF INDIRECT CONTACT FROM THE SAME DIRECT CONTACT A node as in claim X 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. NODE RESPONDS TO A CONTACT REQUEST FROM ANOTHER NODE BY SENDING OTHER NODE A SUBSET OF ITS CONTACTS, AND WHEN NODE DETERMINES THAT ONE OF ITS DIRECT CONTACTS IS NOT FUNCTIONING IT FINDS A NEW DIRECT CONTACT TO REPLACE IT AND SENDS INDEX ADDRESS AND NETWORK ADDRESS OF REPLACEMENT CONTACT TO ANY NODES IT HAD PREVIOUSLY GIVEN REPLACED CONTACT TO A node as in claim X 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. IF NODE RECEIVES INDICATION FROM ANOTHER NODE THAT ONE OF ITS INDIRECT CONTACTS HAS BEEN REPLACED, IT RELAYS INFORMATION ABOUT THE REPLACEMENT TO ANY OTHER NODE IT HAS PREVIOUSLY SUPPLIED THAT CONTACT TO. A node as in claim X 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. DOES NOT DIRECTLY CHECK STATUS OF INDIRECT CONTACTS AT ANY MINIMAL FREQUENCY GREATER THAN {fraction (1/10)}^TH THAT USED WITH DIRECT CONTACTS, AND LEARNS OF THEIR STATUS THROUGH DIRECT CONTACTS_ A node as in claim X 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. DISTRIBUTED INDEXING NETWORK WHERE MULTIPLE NODES INDEX OVERLAPPING PORTIONS OF INDEX SPACE 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. WHEN NEW INFORMATION TO BE INDEXED ENTERS NETWORK A SEARCH IS PERFORMED TO FIND A NODE ASSOCIATED WITH A SUBSET OF THE INDEX SPACE INTO WHICH THE INDEXED INFORMATION FALLS, NEW INFORMATION IS STORED AT THAT NODE, NODES OF NETWORKS WITH OVERLAPPING SUBSETS OF THE INDEX SPACE COMMUNICATE WITH EACH OTHER SO AS TO TRANSFER TO A NODE INDEXING A GIVEN PORTION OF INDEX SPACE INFORMATION INDEXED UNDER THAT PORTION THAT IT DOES NOT YET CONTAIN A node as in claim X 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. NODES HAVE CAPABILITY OF DETERMINING HOW MANY OTHER NODES SHARE ASSOCIATION WITH GIVEN PORTION OF INDEX SPACE AND FOR INCREASING THE NUMBER OF SUCH NODES IF THEY FALL BELOW A GIVEN LOWER LIMIT A node as in claim X 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. LOGICAL NODES—

NODE DEFINES A SUBSET OF NETWORK NODES THAT, WITH IT, DEFINE A LOGICAL NODE, ALL OF WHICH ARE ASSOCIATED WITH SAME SUBSET OF INDEX SPACE, IT COMMUNICATES WITH OTHER NODES IN LOGICAL NODE TO OBTAIN NEW INFORMATION THAT HAS AN INDEX VALUE IN LOGICAL NODE'"'"'S SUBSET OF INDEX SPACE, AND STORES COPY OF SUCH NEW INFORMATION 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; and

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. NODE HAS PROGRAMMING FOR ESTIMATING POPULATION OF ITS LOGICAL NODE AND EITHER FOR SPLITTING IF POPULATION IS TOO HIGH, OR MERGING IF IT IS TOO LOW A node as in claim X 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. HAS PROGRAMMING FOR BOTH SPLITTING AND MERGING A node as in claim X wherein the node'"'"'s memory stores instructions for performing both said functions to split and to merge.

12. NODES OF LOGICAL NODE SHARE VALUES FOR A SET OF ADDRESS BITS A node as in claim X 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 most significant bits of the index address space that are shared by the nodes of the node'"'"'s logical node.

13. NODE IN UNDER POPULATED LOGICAL NODE CAN REQUEST NODE FROM OTHER LOGICAL NODE TO JOIN ITS LOGICAL NODE A node as in claim X 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. RUMOR BASED COMMUNICATION A node as in claim X 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. NEW NODE IS ADDED TO NETWORK BY PICKING A PLURALITY OF POSSIBLE INDEX ADDRESS VALUE FOR IT, SEARCHING FOR A NODE IN LOGICAL NODE HANDLING INDEX EACH SUCH INDEX ADDRESS, SELECTING AS NODE'"'"'S INDEX ADDRESS THAT ASSOCAITED WITH NODE HAVING LOWEST POPULATION A node as in claim X 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. NODE OF LOGICAL NODE SHARE VALUES FOR A SET OF ADDRESS BITS A node as in claim X 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. SHARE VALUES FOR SET OF HIGH ORDER ADDRESS BITS A node as in claim X wherein said shared bits are a sequence of the most significant bits in said index address bits.

18. NODE IN DISTRIBUTED INDEXING SCHEME THAT INDEXES KEYWORD ENTRIES 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. —

KEYWORD'"'"'S INDEX VALUE IS A HASH OF THE KEYWORD A node as in claim X wherein said index value associated with a keyword is a hash of the keyword.

20. KEYWORD ENTRY CONTAINS LISTS OF ONE OR MORE FILES ASSOCIATED WITH KEYWORD A node as in claim x wherein a keyword entry associated with a given keyword contains a lists of one or more files associated with the given keyword.

21. KEYWORD ENTRY INCLUDES INDEX VALUE ASSOCIATED WITH EACH FILE IN LIST, AND NODE STORES FILE ENTRIES WITH INDEX VALUES CORRESPONDING TO ITS INDEX ADDRESS A node as in claim X 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. FILE ENTRY INCLUDES SET OF NETWORK ADDRESSES OF ONE OR MORE NODES WHERE FILE IS STORED A node as in claim X 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. NODE IN DISTRIBUTED INDEXING SCHEME THAT INDEXES FILE ENTRIES STORING LIST OF LOCATION(S) FILE IS STORED—

WHERE NODE REQUESTS A FILE BY INDEX VALUE FROM THE NETWORK;

NODE RESPONDS TO SUCH A REQUEST BY SENDING INFORMATION ON A SET OF ONE OR MORE FILES IN A REQUESTED FILE'"'"'S ENTRY, THE FILE REQUEST INCLUDES AN INDICATION OF LOCATION OF THE REQUESTING NODE ON THE NETWORK, AND THE FILE REQUEST RESPONSE INCLUDES SELECTION OF FILE LOCATIONS MOST APPROPRIATE FOR REQUESTOR'"'"'S LOCATION 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 storied 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.