Multi-level cache architecture and cache management method for peer-to-peer name resolution protocol

A cache memory architecture for use in a peer having at least one locally registered peer ID within a peer name space, the peer name space having a first number of peer IDs instantiated therein, the first number of peer IDs being approximately evenly distributed throughout the peer name space and having an average spacing therebetween, comprising:

• a first memory region for storing peer IDs within a first range of +/−ten times the average spacing from the locally registered peer ID;
• a second memory region for storing peer IDs within a second range of +/−one hundred times the average spacing from the locally registered peer ID excluding the peer IDs within a range of +/−ten times the average spacing from the locally registered peer ID;
• and
• a third memory region for storing peer IDs within a third range of +/−one thousand times the average spacing from the locally registered peer ID excluding the peer IDs within a range of +/−one hundred times the average spacing from the locally registered peer ID.

A cache memory architecture for use in a peer having at least a first locally registered peer ID within a peer name space, the name space having an unknown number of peer IDs registered therein, comprising:

• a first cache memory segment for storing peer IDs instantiated anywhere in the peer name space, the first cache memory segment having a predetermined maximum number of peer IDs that may be stored therein;
• a second cache memory segment instantiated when the first cache memory segment exceeds the predetermined maximum number of peer IDs, the second cache memory segment spanning a range of one tenth the first cache memory segment centered at the first locally registered peer ID, the second cache memory segment forming an exclusion in the first cache memory segment, the second cache segment having a predetermined maximum number of peer IDs that may be stored therein;
• and
• a third cache memory segment instantiated when the second cache memory segment exceeds the predetermined maximum number of peer IDs, the third cache memory segment spanning a range of one tenth the second cache memory segment centered at the first locally registered peer ID, the third cache memory segment forming an exclusion in the second cache memory segment, the third cache memory segment having a predetermined maximum number of peer IDs that may be stored therein.

A method of cache memory management for a segmented cache architecture used in a peer-to-peer name resolution system in which peers may register IDs in a peer name space, the system including at least one locally registered peer ID, the method comprising the steps of:

• populating a first cache segment with a number of peer IDs discovered by the peer-to-peer name resolution system;
• instantiating a second cache segment covering a fraction of the first cache segment and centered at the locally registered peer ID upon receipt of an additional peer ID discovered by the peer-to-peer name resolution system after the number of peer IDs populated in the first cache segment reaches a predetermined maximum, the instantiation of the second cache segment resulting in an exclusion in the first cache segment;
• and
• instantiating a third cache segment covering a fraction of the second cache segment and centered at the locally registered peer ID upon receipt of an additional peer ID discovered by the peer-to-peer name resolution system after the number of peer IDs populated in the second cache segment reaches a predetermined maximum, the instantiation of the third cache segment resulting in an exclusion in the second cache segment.

A cache memory architecture for use in a peer having at least a first locally registered peer ID within a peer name space, the name space having an unknown number of peer IDs registered therein, comprising:

• a first cache memory segment for storing peer IDs instantiated anywhere in the peer name space, the first cache memory segment having a predetermined maximum number K of peer IDs that may be stored therein;
• a second cache memory segment instantiated when the first cache memory segment exceeds the predetermined maximum number of peer IDs, the second cache memory segment spanning a range of 1/(K/2) the first cache memory segment centered at the first locally registered peer ID, the second cache memory segment forming an exclusion in the first cache memory segment, the second cache segment having a predetermined maximum number K of peer IDs that may be stored therein;
• and
• a third cache memory segment instantiated when the second cache memory segment exceeds the predetermined maximum number of peer IDs, the third cache memory segment spanning a range of 1/(K/2) the second cache memory segment centered at the first locally registered peer ID, the third cache memory segment forming an exclusion in the second cache memory segment, the third cache memory segment having a predetermined maximum number K of peer IDs that may be stored therein.