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

• US 7,962,651 B2
• Filed: 06/13/2005
• Issued: 06/14/2011
• Est. Priority Date: 04/02/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John L., Huitema, Christina
• Primary Examiner(s): Avellino; Joseph E
• Assistant Examiner(s): MCLEOD, MARSHALL M
• Application Number:
  US11/152,587
• Publication Number:
  US 20050267992A1
• Time in Patent Office: 2,192 Days
• Field of Search: 709/217, 709/238, 709/243, 709/245
• US Class Current: 709/245
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/58 Caching of addresses or names
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

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.

Claims

1. A multilevel cache of a computing device for use in a peer to peer name resolution protocol, the multilevel cache comprising a set of L levels, each level sized to hold K entries, and the computing device configured to, in response to an attempt to add a K+1 entry to the multilevel cache'"'"'s L^th level that is occupied by K entries, add a L+1^th level to the multilevel cache and divide the K entries between the L^th level and the L+1^th level and replace a randomly selected entry in the multilevel cache'"'"'s L^th level with the K+1 entry.

2. A method of dynamically maintaining a multilevel cache for use in a peer to peer name resolution protocol, comprising the steps of:

receiving a new entry to be entered into the multilevel cache of a computing device;

determining in which level the new entry is to be stored;

determining if the level into which the new entry is to be stored is full;

storing the new entry in the level when the level is not full;

randomly replacing another entry with the new entry when the level is full and when the level is not a last level of the multilevel cache; and

adding a new level when the level is full and when the level is the last level of the multilevel cache, sorting entries from the last level between the last level and the new level, and storing the new entry, the method performed by the computing device.

3. The method of claim 2, wherein the step of determining in which level the entry is to be stored comprises the step of determining if the entry already exists in the multilevel cache, and replacing an address certificate for the entry when the address certificate is more recent than the address certificate of the entry stored in the multilevel cache.

4. The method of claim 2, wherein the step of determining in which level the new entry is to be stored comprises the step of computing a distance between a local identifier and an entry identifier.

5. A computer-readable storage media excluding signals and carrier waves comprising computer-executable instructions that, when executed by a computing device, cause the computing device to perform a method comprising:

receiving a new entry;

determining a level of a cache in which to add the new entry, wherein the cache comprises L levels with each level configured to hold K entries;

determining that the level is occupied by K entries;

selecting, in response to the determining that the level is occupied by K entries, a random entry in the level of the cache; and

replacing the selected entry with the new entry.

6. The computer-readable storage media excluding signals and carrier waves of claim 5, further comprising:

preparing a message comprising an address certificate; and

sending the message to an address associated with the new entry.

7. The computer-readable storage media excluding signals and carrier waves of claim 5, further comprising:

determining that the level is the L^th level of the multilevel cache; and

adding, in response to the determining that the level is the L^th level of the multilevel cache, a L+1^th level to the multilevel cache.

8. The computer-readable storage media excluding signals and carrier waves of claim 7, further comprising:

dividing the K entries between the L^th level and the L+1^th level.

9. The computer-readable storage media excluding signals and carrier waves of claim 8, wherein the dividing is based on a distance between a local identifier and an identifier of one of the K entries.