Re: [RRG] Re: [RAM] How to avoid black-hole in LISP-CONS with aggregation mechanism?

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

    > From: Xu Xiaohu <xuxh@huawei.com>

    > .. it may result in inefficient lookup.
    > ...
    > As long as the aggregation does not exceed its authoritative address
    > space, it's OK.

Again, this is a topic that has been discussed fairly extensively, but it's
not completely resolved yet, in part because I don't think there is a perfect
answer.

In general, if the advertisments upward only cover what a CDR is actually
authoritative for, and that recurses upward, that does result in optimal
'routing' of requests down the CDR 'pseudo-hierarchy'. (I call is a
'pseudo-hierarchy' since it is basically hierarchical in form, but the
existence of cross-links among siblings mean it's not a pure hierarchy).

The problem with doing that is that you may not get much reduction in the
amount of information passed upward, so that in the higher levels of the
pseudo-hierarchy the tables could get quite large. (How much aggregation you
actually get depends on how the EID name-space is allocated, etc - e.g. if a
node has childrem which are authoritative for say, 128.52.0/17 and
128.52.128/17, then it can aggregate that to a single entry to advertise
upward, i.e. 128.52/16. However, if it only has a large number of entries of
the form 128.52.X/24, with gaps, then it may not be able to aggregate them
all into a single entry.)

This is of course very similar to the tradeoff in normal hierarchical
routing, where you have a tradeoff between routing overhead, and path
optimality. (We don't have a single perfect solution there, either!)

In CONS, as it stands, a request could (in the worst case) take an extra
'sideways' hop at each level. One can think of a number of possible
optimizations, e.g. simple heuristics for limiting the upward advertisements
(e.g. to one level above the parent of the node that originates an
advertisment) which can reduce this a lot, but attention has been focused
elsewhere recently, for a variety of reasons. (For one, we won't know how bad
the aggregation is until we look at some actual data.)


I have been thinking hard about possible optimizations for CONS, and have
come up with a long list of things we could possibly do. Of course, not all
of them will be cost-effective, so only the ones that make sense will
eventually be added.

Of those, I have been thinking about the ones that seem to have the most
payoff in some detail, e.g. caching 'popular' EID->RLOC bindings in the CDR
hierarchy (so that requsts for the mapping for major content providers don't
have to go all the way through the pseudo-hierarchy, to the CAR which holds
that mapping).

Eventually we will get back to this issue of optimizing the request descent
path through the CDR pseudo-hierarchy, and try and work out some good
heuristics for optimizing it. If anyone has any good ideas, they would
certainly be welcome!

	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