US 7,065,587 B2Granted

Peer-to-peer name resolution protocol (PNRP) and multilevel cache for use therewith

AssigneeMicrosoft Corporation

InventorsChristian Huitema, John L. Miller

Life of this patent

Estimating the term…

Loading patent…

Abstract

A serverless name resolution protocol ensures convergence despite the size of the network, without requiring an ever-increasing cache and with a reasonable numbers of hops. This convergence is ensured through a multi-level cache and a proactive cache initialization strategy. The multi-level cache is built based on a circular number space. Each level contains information from different levels of slivers of the circular space. A mechanism is included to add a level to the multi-level cache when the node determines that the last level is full. A peer-to-peer name resolution protocol (PNRP) includes a mechanism to allow resolution of names which are mapped onto the circular number space through a hash function. Further, the PNRP may also operate with the domain name system by providing each node with an identification consisting of a domain name service (DNS) component and a unique number.

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

receiving at a first node a request message from a requester node seeking address resolution of a second node having a unique number identifier, the request message including address information of the requester node;
populating a routing table of the first node with the address information of the requester node,
wherein the step of populating the routing table comprises the steps of:
determining if the address information of the requester node is already in the routing table,
refreshing the address information of the requester node if more recent than the address information of the requester node already stored in the routing table, else
computing a distance between the address information of the first node and the requester node,
determining from the distance a selected level into which to store the address information of the requester node,
wherein the selected level is a last level, and
storing the address information in the selected level;
analyzing the request message;
generating a response message to the requester node identifying address information of the first node as best matching for the request message when one of three conditions is met;
otherwise
determining a suitable next hop for the request;
forwarding the request message to the suitable next hop;
preparing a flooding message containing the address information of the first node with an empty list of already flooded nodes;
sending the flooding message to the requester node;
preparing a list of nodes in the routing table whose distance to the requester node is smaller than DMAX/(P(L−1))
removing from the list nodes that are marked as already flooded when the addition of the new entry is a result of a flooding message;
preparing a flooding message containing the address information of the requester node;
and
sending the flooding message to all nodes in the list.

18 more elements

Facts

Application

09/942,164Filed 29 Aug 2001 · us provisional application

Priority

2 Apr 2001

Published

US 2002/0143989 A13 Oct 2002

Granted

20 Jun 2006

Term ends

Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 61/4511
Using standardised directories; using standardised directory access protocols: using domain name system [DNS]
H04L 61/58
Network arrangements, protocols or services for addressing or naming: caching of addresses or names
H04L 67/104
In which an application is distributed across nodes in the network: peer-to-peer [P2P] networks
H04L 67/1065
Using node-based peer discovery mechanisms: discovery involving distributed pre-established resource-based relationships among peers, e.g. based…

Abstract

Claims2