Flower-petal resolutions for PNRP

• US 20060239197A1
• Filed: 04/22/2005
• Published: 10/26/2006
• Est. Priority Date: 04/22/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horton, Noah, Lieuallen, Brian R.
• Granted Patent: US 7,817,647 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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/107 with limitation or expansion of the discovery scope

Abstract

The claimed process and system provides a resolution process for a multi-level cache resolution protocol that involves a lookup procedure whereby the initiating node contacts each intermediate node directly using a communication link separate from any previous intermediate node. The resolution process may involve caching information from each contacted intermediate node during the resolution process to request leads on the target node in the form of a list of closer nodes known to the intermediary node.

Claims

1. A serverless name resolution protocol through which unique numbers are resolved to addresses, comprising the steps of:

creating and initializing a node state object at an initiating node that keeps track of the state of a resolution process of the initiating node;

creating a lookup message at the initiating node and sending the lookup message to an intermediate node;

receiving at the intermediate node a lookup message from the initiating node and determining whether the intermediate node contains information on a closer node to the target node than a node specified by the lookup message;

creating an answer message object at the intermediate node containing information on the closer node and sending the answer message to the initiating node in response to the lookup message object;

determining at the initiating node whether the closer node of the answer message matches a resolve criteria of the initiating node.

2. The resolution protocol of claim 1, wherein the state object comprises information on a target node, a best match node, a next hop node, a path list and further wherein the state object comprises a stack object.

3. The resolution protocol of claim 1, wherein the lookup message comprises information on a target node, an intermediate node ID, and a best match node.

4. The resolution protocol of claim 1, further comprising determining at the intermediate node whether the intermediate node ID contained in the lookup message matches the intermediate node ID and including in an answer message an invalid indicator when the unique number identifier contained in the lookup message does not match.

5. The resolution protocol of claim 4, further comprising determining at the initiating node whether an answer message contains an invalid indicator and removing node information corresponding to the intermediate node ID from the initiating node.

6. The resolution protocol of claim 1, wherein sending the lookup message object to an intermediate node comprises sending the lookup message object to an intermediate node closer to the target node than the initiating node.

7. The resolution protocol of claim 1, wherein closer comprises a closer numerical difference between node IDs in a circular number system.

8. The resolution protocol of claim 1, wherein sending the lookup message object to an intermediate node comprises sending the lookup message object to an intermediate node having an address corresponding to the intermediate node ID contained in the lookup message, and further comprising determining whether an answer message was received at the initiating node and removing node information corresponding to the intermediate node ID from the initiating node when no answer message is received.

9. The resolution protocol of claim 2, wherein determining whether the intermediate node contains information on a node closer to the target node than the initiating node comprises comparing a unique number identifier of the target node to a set of unique number identifiers stored at the intermediate node, and wherein creating an answer message object comprises providing address information of an intermediate node closer to the target node than the best match node of the lookup message.

10. The resolution protocol of claim 1, further comprising sending an inquire message to the closer node if the closer node matches the resolve criteria and providing an indication if the inquire message verifies the existence of the closer node.

11. The resolution protocol of claim 2, further comprising changing the best match node to correspond to the intermediate node from which an answer message was received, adding the intermediate node from which an answer message was received on to the stack object, and adding the next hop node contained in the answer message to the stack object, when the answer message does not satisfy the resolve criteria.

12. The resolution protocol of claim 1, wherein the resolve criteria comprises whether the closer node of the answer message the target node.

13. A computer mesh network comprising:

an initiating node attempting to resolve a unique number identifier to an address of a target node, wherein the initiating node contains a cache of local nodes and comprises a state object that keeps track of the state of a resolution process of the initiating node;

a first intermediate node that is listed in the cache of the initiating node and is closer to the target node than the initiating node, wherein the initiating node contains a cache of local nodes;

wherein the initiating node sends a first lookup message to the first intermediate node when the initiating node does not have the target node address in its cache, and wherein the intermediate node receives a lookup message from the initiating node and returns an answer message to the initiating node with the address of a second intermediate node closer to the target node than the first intermediate node.

14. The computer mesh network of claim 13, wherein closer comprises a numerical difference between node IDs in a circular number system.

15. The computer mesh network of claim 13, wherein the intermediate node finds a plurality of entries in its cache with identifiers that are closest to the target node, randomly picks one of the plurality of entries, and returns the randomly picked entry in the answer message.

16. The computer mesh network of claim 14, wherein the initiating node will send a second lookup message to the address of the second intermediate node contained in the answer message.

17. The computer mesh network of claim 16, wherein the state object maintains a list of nodes traversed during the resolution process and further wherein the initiating node will send a third lookup message to the first intermediate node if the second intermediate node does not contain the address of a node closer to the target node.

18. The computer mesh network of claim 13, wherein the lookup message includes a certificate of origin, and further comprises checking the certificate of origin to determine its validity, and refusing the lookup message when the certificate of origin is invalid.

19. The computer mesh network of claim 13, wherein the initiating node sends an inquire message to the closer node address contained in the answer message if the closer node address corresponds to the target node ID.

20. The computer mesh network of claim 13, wherein the initiating node sends the intermediate node an ID corresponding to the intermediate node in the lookup message and further wherein the intermediate node returns an answer message with an invalid indicator if the intermediate node ID of the lookup message does not match its ID.