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

• US 7,054,867 B2
• Filed: 09/18/2002
• Issued: 05/30/2006
• Est. Priority Date: 09/18/2001
• Status: Expired due to Fees

• Current Assignee: Skype Limited (Microsoft Corporation)
• Original Assignee: Skyris Networks, Inc.
• Inventors: Wilken, Benjamin B., Bosley, Carleton J., Srivastava, Gitika
• Primary Examiner(s): Wassum, Luke S
• Application Number:
  US10/246,793
• Publication Number:
  US 20030126122A1
• Time in Patent Office: 1,350 Days
• Field of Search: 707 1- 5, 707/10, 709220-222
• 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 of the direct contacts with a minimum frequency, to determine whether or not that direct contact is still a member of the network;

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;

the 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

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

2. A node as in claim 1 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.

3. A node as in claim 2 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.

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