Subject: [lisp] Mapping Service negative cache replies

From: Jeff Wheeler <[email-masked]>
Date: Thu, 28 Apr 2011 01:31:49 -0400

Dear List,

I've had several off-list discussions with some vendor folks, and
otherwise, working hard on LISP.  I see that the issue of cache
thrashing is currently left entirely up to the implementor to handle.
I may be unaware of some body of work on this topic, however, I
believe the current language in draft-ietf-lisp-ms-07, below,
eliminates a needed means of reducing negative mapping cache size on
an ITR.

>From section 4.4 Map-Resolver Processing:
To minimize the number of negative cache entries needed by an ITR, the
Map-Resolver should return the least-specific prefix which both
matches the original query and does not match any EID-prefix known to
exist in the LISP-capable infrastructure.

This is a good approach in most circumstances, where there are few
packets to unknown destinations (few "punts" to the control-plane.)
It breaks down, however, in the event the ITR needs to process a large
amount of packets to unknown destinations, such as:
* a deliberate DoS attack on the ITR from within
* reply packets to an external DoS attack with false, random source addresses
* a malicious worm searching for hosts to infect
* etc.

All of the above contribute to FIB churn.  They may also cause a large
number of negative mapping cache entries to be populated on the ITR.
To demonstrate how the mechanism in draft-ietf-lisp-ms-07 is not ideal
in this situation, all you must do is emulate the existing IPv6
routing table, which contains numerous, costly-to-express holes.  For
example, current ARIN IPv6 allocations to ISPs are /32 in size but are
aligned on /23 boundaries.  These holes between "adjacent" (minus
holes) /32 ISP allocations allow a malicious person to cause an ITR to
learn nine (9) negative mapping cache entries between each two /32
allocations, if one was utilizing LISP on Internet-scale, and LISP
were widely-deployed.

The draft language does not leave room for alternatives, but it
probably should.  A different mechanism works better in this
situation, allowing the ITR to learn about all feasible prefix
mappings within a given supernet.  This may allow the ITR to reduce
its number of negative cache entries dramatically by installing a far
smaller number of positive mappings (to control-plane cache for
possible use, or to FIB.)

This is of more importance than is immediately obvious, because one
must consider the cost of "punts" to the control-plane in order to
drive the learning process.  These punts must be policed somehow, and
surely, they will be by vendor implementations with a "hardware FIB"
and a "software negative cache."  However, when faced with a large
volume of punts (packets to unknown destinations, causing a negative
cache hit or a new Mapping Service inquiry), an implementation might
choose to actually install negative mappings into his FIB, preventing
these known-bad punts from reaching the control-plane *and* preventing
them from contenting for policer conformance with other punts which
are needed to learn new mappings for legitimate traffic.  This means
the cost of pushing some negative cache entries into the FIB should be
considered, and the cost of doing so should be able to be minimized by
the implementation.

I suggest the Mapping Service specification leave room for an ITR that
wishes to request all mappings within a given subset of the feasible
routing table.  This gives the implementor additional options for
dealing with malicious traffic which may drive its negative mapping
cache to a large size, and perhaps consume precious FIB resources as
well.

Darrel Lewis tells me there was a similar capability in a router with
"on-demand FIB compression."  While the application differs in this
case, the principle is the same.

-- 
Jeff S Wheeler <[email-masked]>
Sr Network Operator  /  Innovative Network Concepts