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

• US 20030196060A1
• Filed: 04/15/2002
• Published: 10/16/2003
• Est. Priority Date: 04/15/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John L.
• Granted Patent: US 6,912,622 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• 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 69/329 in the application layer [OSI layer 7]

Abstract

A peer-to-peer cache architecture stores peer address certificates in different cache segments according to the number of IDs being stored and their relative distance in the peer name space. The cache instantiates regions of decreased range and increased granularity as additional information from close peers is learned. In a large peer cloud where the number of instantiated IDs is not known, each succeeding cache region covers one tenth of the preceding cache region. For peers with multiple IDs registered locally, the segmented cache of the present invention combines overlapping segments of the same granularity to eliminate the duplication of information that would otherwise occur. A cache tree, an instantiated segment tree, and an uninstantiated segment tree are arranged in red-black trees to simplify the search and proper placement and instantiation of information.

Claims

1. 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 having an average spacing therebetween, comprising:

a second number N of memory regions for storing peer IDs, each memory region from 1 . . . N storing peer IDs within a range of +/−

10^{1 . . . N} times the average spacing from the at least one locally registered peer ID, each of the memory regions 2 . . . N excluding the peer IDs stored in preceding memory regions 1 . . . N−

1; and

wherein the number N of memory regions is determined as the log of the first number of peer IDs instantiated in the name space.

2. The cache memory architecture of claim 1, wherein each of the N memory regions has a capacity to store a third number of peer IDs therein, the third number for each memory region being equal to the range divided by the average spacing.

3. The cache memory architecture of claim 2, wherein the third number for each memory region from 2 . . . N is equal to the range of its associated memory region less the range of the preceding regions 1 . . . N−

1.

4. The cache memory architecture of claim 1, wherein each memory region from 1 . . . N stores peer IDs having a granularity of 10^{0 . . . N−}

1 times the average spacing.

5. The cache memory architecture of claim 1, wherein the peer has at least two locally registered peer IDs, wherein at least one of the second number of memory regions for each of the two locally registered peer IDs covers at least a common portion of the name space;

and wherein the at least one of the second number of memory regions for each of the two locally registered peer IDs that covers at least a common portion of the name space is combined into a single memory region to eliminate duplication of peer IDs stored therein.

6. The cache memory architecture of claim 1, wherein each of the memory regions N−

1 . . . 1 is instantiated only after a next higher memory region N . . . 2 becomes full.

7. 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.

8. The architecture of claim 7, wherein the first memory region has a capacity to store a second number of peer IDs therein, the second number being equal to the first range divided by the average spacing, wherein the second memory region has a capacity to store a third number of peer IDs therein, the third number being equal to the second range minus the first range divided by the average spacing, and wherein the third memory region has a capacity to store a fourth number of peer IDs therein, the fourth number being equal to the third range minus the second range divided by the average spacing.

9. The cache memory architecture of claim 7, wherein the first memory region stores peer IDs having a granularity of the average spacing, wherein the second memory region stores peer IDs having a granularity of 10 times the average spacing, and wherein the second memory region stores peer IDs having a granularity of 100 times the average spacing.

10. The cache memory architecture of claim 7, wherein the peer has at least two locally registered peer IDs, wherein at least one of the memory regions for each of the two locally registered peer IDs covers at least a common portion of the name space;

and wherein the at least one of the memory regions for each of the two locally registered peer IDs that covers at least a common portion of the name space is combined into a single memory region to eliminate duplication of peer IDs stored therein.

11. 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.

12. The cache memory architecture of claim 11, further comprising a fourth cache memory segment instantiated when the third cache memory segment exceeds the predetermined maximum number of peer IDs, the fourth cache memory segment spanning a range of one tenth the third cache memory segment centered at the first locally registered peer ID, the fourth cache memory segment forming an exclusion in the third cache memory segment.

13. The cache memory architecture of claim 11, wherein the peer includes at least the first and a second locally registered peer IDs, further comprising a fifth cache memory segment instantiated when the first cache memory segment exceeds the predetermined maximum number of peer IDs, the fifth cache memory segment spanning a range of one tenth the first cache memory segment centered at the second locally registered peer ID, the fifth cache memory segment forming an exclusion in the first cache memory segment, the fifth cache segment having a predetermined maximum number of peer IDs that may be stored therein.

14. The cache memory architecture of claim 13, wherein a portion of the second and the fifth cache memory segments cover a common area of the name space, and wherein the second and the fifth cache memory segments are combined into a sixth cache memory segment to prevent duplication of information.

15. The cache memory architecture of claim 14, further comprising a seventh cache memory segment instantiated when the sixth cache memory segment exceeds the predetermined maximum number, the seventh cache memory segment spanning a range of one tenth the second cache memory segment centered at the second locally registered peer ID.

16. 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.

17. The method of claim 16, further comprising the steps of:

forming a first binary tree containing all of the peer IDs discovered by the peer-to-peer name resolution system;

forming a second binary tree containing starting addresses in the peer name space to all of the instantiated cache segments; and

forming a third binary tree containing uninstantiated cache segments that relate to an immediately preceding instantiated cache segment.

18. The method of claim 17, further comprising the steps of:

receiving a new peer ID discovered by the peer-to-peer name resolution system;

searching the second binary tree to determine in which instantiated segment the new peer ID belongs;

determining that the predetermined maximum for the instantiated segment in which the new peer ID belongs has not been reached; and

adding the new peer ID to the instantiated segment in which the new peer ID belongs when the predetermined maximum has not yet been reached.

19. The method of claim 17, further comprising the steps of:

receiving a new peer ID discovered by the peer-to-peer name resolution system;

searching the second binary tree to determine in which instantiated segment the new peer ID belongs;

determining that the predetermined maximum for the instantiated segment in which the new peer ID belongs has been reached;

searching the third binary tree to determine if there is an uninstantiated segment that overlaps the instantiated segment in which the new peer ID belongs when the predetermined maximum has been reached; and

instantiating a new cache segment when the step of searching the third binary tree identifies the uninstantiated segment that overlaps the instantiated segment in which the new peer ID belongs.

20. The method of claim 17, further comprising the steps of:

receiving a new peer ID discovered by the peer-to-peer name resolution system;

searching the second binary tree to determine in which instantiated segment the new peer ID belongs;

determining that the predetermined maximum for the instantiated segment in which the new peer ID belongs has been reached;

searching the third binary tree to determine if there is an uninstantiated segment that overlaps the instantiated segment in which the new peer ID belongs; and

randomly replacing a peer ID in the instantiated segment in which the new peer ID belongs when the step of searching the third binary tree does not identify any uninstantiated segment that overlaps the instantiated segment in which the new peer ID belongs.

21. The method of claim 16, wherein the system includes at least a second locally registered peer IDs, further comprising the step of instantiating a fourth cache segment covering a fraction of the first cache segment and centered at the second 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 fourth cache segment resulting in an exclusion in the first cache segment.

22. The method of claim 21, wherein the second and the fourth cache segments overlap to an extent, further comprising the step of combining the second and the fourth cache segments into a single cache segment to eliminate duplication of information in the second and the fourth cache segments.

23. The method of claim 21, wherein the second locally registered peer ID is unregistered by the peer-to-peer name resolution system, further comprising the steps of uninstantiating the fourth cache segment.

24. The method of claim 16, wherein the step of instantiating the second cache segment covering a fraction of the first cache segment comprises the step of instantiating the second cache segment covering one-tenth of the first cache segment, and wherein the step of instantiating the third cache segment covering a fraction of the second cache segment comprises the step of instantiating the third cache segment covering one-tenth of the second cache segment.

25. A computer-readable medium having computer-executable instructions for performing the steps of claim 16.

26. 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.

27. The cache memory architecture of claim 26, further comprising a fourth cache memory segment instantiated when the third cache memory segment exceeds the predetermined maximum number of peer IDs, the fourth cache memory segment spanning a range of 1/(K/2) the third cache memory segment centered at the first locally registered peer ID, the fourth cache memory segment forming an exclusion in the third cache memory segment.

28. 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 having an average spacing therebetween, comprising:

a second number N of memory regions for storing peer IDs, each memory region from 1 . . . N storing peer IDs within a range of +/K^{1 . . . N} times the average spacing from the at least one locally registered peer ID, wherein K is a positive integer greater than 1, each of the memory regions 2 . . . N excluding the peer IDs stored in preceding memory regions 1 . . . N−

1; and

wherein the number N of memory regions is determined as the log base K of the first number of peer IDs instantiated in the name space.