3.2.1.1 Cache

  • Article

To respond to LOOKUP messages when a neighbor is searching for a particular PNRP ID, a PNRP node is required to maintain a Route Entry Cache. A PNRP cloud has no scale limitation, and could consist of millions of registrations; because it would be prohibitively expensive, both in bandwidth and memory, for every node to cache every single registration in a cloud of this size, the selection of neighbors to cache is of critical importance to ensure a reasonable trade-off among search time, bandwidth, and memory consumption.

The specific cache organization is an implementation detail<5> but the following are requirements that MUST be met by a cache implementation:

  1. It MUST be such that a search for a single registration in the cloud can be implemented on the order of Log10(n) LOOKUP message operations, where n is the total number of registrations in the cloud. (For example, the cache structure specified in [PAST] has this property.)

  2. The cache MUST logically include all entries in each of the node's Leaf Sets.

    This constraint on the cache ensures that there is always a discoverable path to a registered PNRP ID. PNRP nodes, which are also Publishers, also use this constraint to detect and repair partitions in the cloud, as specified in section 3.2.6.2.1.

  3. A PNRP node MUST maintain a cache of at least 10 route entries (or all route entries in the cloud if there are fewer than 10), of the PNRP IDs of which are evenly distributed around the number space.

    This constraint ensures that when a neighbor is performing a bootstrap operation and solicits entries (using SOLICIT messages) for this node's cache, it is possible to advertise (using ADVERTISE messages) an even distribution of candidates.