re: [RRG] cache issues in LISP and CONS

[jnc@mercury.lcs.mit.edu (Noel Chiappa)]

    > From: Scott Brim <swb@employees.org>

    >> very efficient (in terms of overhead), and extremely effective (in
    >> terms of correctly identifying which mappings are widely used) system
    >> for deciding which entries to cache in the CDRs.

    > If it is just about request rate, then I see no reason for the aCAR to
    > inform its upstream nodes of anything. Its upstream nodes are already
    > quite aware of how many requests are being made for various prefixes
    > ...
    > I don't think it's good to design in interdependency when an individual
    > CDR has all the information the aCAR could give it .. A cache system
    > will cause frequently requested information to be present in the
    > intermediate nodes. It's simple and it doesn't depend on control
    > exchanges.

The issue is not who has what information, but rather the size of the cache
one would need in a CDR (particularly a top-level CDR) for that cache to be
effective.

This does assume that these caches are not intended to cache *everything*;
i.e. they'd have to have some sort of algorithm to decide what to cache, and
I'm assuming one would use some sort of LRU algorithm to do that. If you're
simply going to cache everything, than yeah, one doesn't need that 'advice
from the leaves up' algorithm - or, indeed, *any* algorithm to decide what to
keep, and what to discard. I don't know if a 'cache-everything' strategy is
viable - maybe it is, I just assumed it wasn't, but I haven't done any
back-of-the-envelope numbers to see if it would be.

But, if one has an incomplete cache, then one has the issue of how to decide
what to keep in it, and to do that, you have to keep some sort of history,
which is usually cache entries themselves. If the history/cache isn't big
enough, requests for entries which are not often repeated will flush the
entries which are (i.e. which ought to be cached). I tried for a while to
tackle that problem, of how big to make the caches, to ensure that they do
wind up holding the commonly-used bindings (which is a moving target anyway,
based on usage patters, the contents of the distributed database, etc). I
also tried more complex schemes (two-level caches, etc).

In the end, the scheme I mentioned above seemed better; it simply moves that
state out to the leaves, which have to have a copy of every entry anyway, so
it's just an extra entry in all those pre-existing database entries. It is
much easier to tune, and much less sensitive to changing usage patterns (which
could cause hit rates to fall drastically if they cause caches to get
flushed).

I dunno, maybe the whole concept of partial caches is a bad idea, and we
should just cache everything. Probably time to do some BOTE engineering...

	Noel

--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg