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

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.

1 . 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;    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; and    forwarding the request message to the suitable next hop.    
   
   
       2 . The protocol of  claim 1 , wherein the step of analyzing the request message comprises the step of comparing the unique number identifier to the address information of the first node, and wherein the step of 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 comprises the step of generating a response message to the requester node identifying address information of the first node as best matching for the request message when the unique number identifier is identical to the address information of the first node.  
   
   
       3 . The protocol of  claim 1 , wherein the request message contains a maximum hop count value and a list of node that have processed the request message, and wherein the step of analyzing the request message comprises the step of determining if a number of nodes which have previously processed the request message exceeds the maximum hop count, and wherein the step of 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 comprises the step of generating a response message to the requester node identifying address information of the first node as best matching for the request message when the number of nodes which have previously processed the request message exceeds the maximum hop count.  
   
   
       4 . The protocol of  claim 1 , wherein the request message contains a list of nodes that have processed the request message, and wherein the step of analyzing the request message comprises the step of determining if the address information of the first node is in the list of nodes that have processed the request message, and wherein the step of 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 comprises the step of generating a response message to the requester node identifying address information of the first node as best matching for the request message when the address information of the first node is in the list of nodes that have processed the request message.  
   
   
       5 . The protocol of  claim 1 , wherein the request message includes a certificate of origin, further comprising the steps of checking the certificate of origin to determine its validity, and refusing the request message when the certificate of origin is invalid.  
   
   
       6 . The protocol of  claim 1 , 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 the 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; and    storing the address information in the selected level.    
   
   
       7 . The protocol of  claim 6 , wherein the selected level is a last level having K entries stored therein, and wherein the step of determining the selected level comprises the steps of determining that an entry should be replaced, and replacing the entry with the address information of the requester node.  
   
   
       8 . The protocol of  claim 6 , wherein the selected level is a last level, further comprising the steps of preparing a flooding message containing the address information of the first node with an empty list of already flooded nodes, and sending the flooding message to the requester node.  
   
   
       9 . The protocol of  claim 1 , further comprising the steps of checking a date of validity for address information in the routing table, and removing address information for which the date of validity has passed.  
   
   
       10 . The protocol of  claim 1 , wherein the step of determining a suitable next hop for the request comprises the steps of finding a subset of routing table entries whose address is not already listed in the request message, returning an indication of failure when the subset is empty, returning a particular entry when the particular entry is the only entry in the subset.  
   
   
       11 . The protocol of  claim 10 , further comprising the steps of finding two entries whose identifiers are closest to the second node, randomly pick one of the two entries, and return the randomly picked entry.  
   
   
       12 . The protocol of  claim 1 , further comprising the steps of: 
 receiving a response message including address information of the second node and address information of a best match node;    comparing the address information of the second node and the address information of the best match node;    replacing the address information of the best match node with the address information of the first node when the address information of the best match node is not equal to the address information of the second node and the address information of the first node is closer to the address information of the second node than the address information of the best match node; and    relaying the response message to the requester node when the requester node is not the first node.    
   
   
       13 . The protocol of  claim 1 , further comprising the step of forming the unique number identifier of the second node by computing a hash of a unique name of the second node.  
   
   
       14 . The protocol of  claim 13 , wherein the step of forming the unique number identifier further comprises the step of associating a unique number with the hash of the unique name to form the unique number identifier in the form <hash>.<unique number>.  
   
   
       15 . The protocol of  claim 1 , further comprising the step of extracting the unique number identifier of the second node from a unique name processed through a DNS query to a peer to peer server, the unique name taking the form <peer to peer identifier>.<DNS server address>.  
   
   
       16 . The protocol of  claim 15 , wherein the <peer to peer identifier> is a unique name, further comprising the step of forming the unique number identifier of the second node by computing a hash of a unique name of the second node.  
   
   
       17 . The protocol of  claim 16 , wherein the step of forming the unique number identifier further comprises the step of associating a unique number with the hash of the unique name to form the unique number identifier in the form <hash>.<unique number>.