Subject: [lisp] FIB compression as a possible solution

From: Dino Farinacci <[email-masked]>
Date: Thu, 21 Jul 2011 02:13:11 -0700

It has been stated that if the granularity of prefixes in negative Map- 
Replies are too specific, we can fill up a cache. There are two ways  
to deal with this:

(1) Use some form of aggregation or table compression.
(2) Don't store negative prefixes.

Jeff mentioned for (1) to have the mapping system return a coarse  
negative prefix with positive ones which punch holes in negative map- 
replies. This will be quite hard since the sender of the negative Map- 
Reply may not know all positive entries (since they are spread around  
and stored in other map-servers). But the map-server could infer based  
on looking at the ALT to find positive entries. So some research can  
be done on this idea to see if is tractable.

Another way to tackle (1) is to have the ITR look at the more-specific  
negative prefixes to see if they can be combined into a fewer number  
of more coarse prefixes using localized prefix compression. If exact  
compression can be done, then do it (meaning their are no positive  
holes in the compressed aggregate). If there are holes created, they  
*could be mitigated* if you already have a positive cache entry stored  
because you previously have encapsulated to the site. But you can't  
always depend on this ordering to make it reliable.

As for (2), we could say, we'll make a tradeoff by saving the cache at  
the expense of more load on the mapping system. Well the mapping  
system (like DNS) has to be provisioned and capacity planned to handle  
load for scaling reasons. So it should also be able to handle DoS load  
too. And if it can't, then the DoS load gets dropped (that is the good  
news). But with every DoS load that gets dropped there is good load  
that loses too. So take this with a grain of salt.

But if the ITRs only stored positive cache entries, one might think we  
would not know when to forward natively to non-LISP sites. Well when  
an ITR gets a cache miss, it could send the packet natively as well as  
send a rate-limited Map-Request. We do implement very short-lived data- 
caches so we can do aggressive rate-limiting. If a Map-Reply is  
returned, you know the destination is a LISP site and you cache the  
positive entry. If nothing comes back, you continue to forward  
natively. As I said, this puts more Map-Request load on the mapping  
system.

Or maybe a combination can be used. You store negative entries to a  
threshold and when you need to store a positive, it is the negative  
ones that are evicted first to make room for the positive ones. And  
which negative ones you choose to evict can the most specific prefixes  
because they represent a smaller set of destinations and the  
probability of sending a Map-Request for them to find out if they are  
LISP destinations or not is less likely then with larger blocks.

Note, it is easier to compress negative map-cache entries since their  
locator-set is the same. That is it is empty with an action of "native- 
forward" where as for positive map-cache entries you cannot compress  
consecutive power-of-2 blocks if the locator-set is different (meaning  
the EID-prefixes belong to different sites). Now, there is always the  
option to take the compressed value and use a new locator, perhaps a  
re-encapsulating router in the core, that can hold more prefixes. This  
is related to my other email where a PETR can be used where it  
decapsulates from the ITR and re-encapsulates directly to the site.  
This will be at the expense of possible added data-plane stretch.

Dino

---

From: Jeff Wheeler <[email-masked]>
Date: Thu, 21 Jul 2011 06:12:15 -0400

On Thu, Jul 21, 2011 at 5:13 AM, Dino Farinacci <[email-masked]> wrote:

> Jeff mentioned for (1) to have the mapping system return a coarse negative
> prefix with positive ones which punch holes in negative map-replies. This
> will be quite hard since the sender of the negative Map-Reply may not know
> all positive entries (since they are spread around and stored in other
> map-servers). But the map-server could infer based on looking at the ALT to
> find positive entries. So some research can be done on this idea to see if
> is tractable.
>

It would be possible to install shorter negative plus one or more longer
positives that are not complete mappings, but "next-hop ms-resolve," which
would discard packets to the shorter negative but still be able to punt and
do MS query for the possibly-positive part of the address space.

If I was the implementer, I would probably then keep count in my Trie to
know when a particular branch of the address space cache contains mostly
negative entries, which would indicate opportunities for on-demand
"compression."

> negative prefixes to see if they can be combined into a fewer number of more
> coarse prefixes using localized prefix compression. If exact compression can
> be done, then do it (meaning their are no positive holes in the compressed
> aggregate). If there are holes created, they *could be mitigated* if you
> already have a positive cache entry stored because you previously have
> encapsulated to the site. But you can't always depend on this ordering to
> make it reliable.
>

I do not understand how this can be beneficial if the MS currently sends
negative replies that are the shortest possible prefixes which do not
overlap any possible positive mapping.  Keep in mind that my understanding
of the control-plane remains limited, specifically I am not familiar with
how much state is available from the local MS vs what must be retrieved from
distant MS.  I need to do some homework in this area.

> As for (2), we could say, we'll make a tradeoff by saving the cache at the
> expense of more load on the mapping system. Well the mapping system (like
> DNS) has to be provisioned and capacity planned to handle load for scaling
> reasons. So it should also be able to handle DoS load too. And if it can't,
> then the DoS load gets dropped (that is the good news). But with every DoS
> load that gets dropped there is good load that loses too. So take this with
> a grain of salt.
>
> would not know when to forward natively to non-LISP sites. Well when an ITR
> gets a cache miss, it could send the packet natively as well as send a
> rate-limited Map-Request. We do implement very short-lived data-caches so we
> can do aggressive rate-limiting. If a Map-Reply is returned, you know the
> destination is a LISP site and you cache the positive entry. If nothing
> comes back, you continue to forward natively. As I said, this puts more
> Map-Request load on the mapping system.
>

I do not understand how this can be effective.  If the ITR does not have a
native Locator address for the payload address family, and the site is
relying upon LISP, there won't be a way for packets to even reach the
"native Internet" for some alternate forwarding to the destination.

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

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 21 Jul 2011 18:08:48 -0700

> replies. This will be quite hard since the sender of the negative  
> Map-Reply may not know all positive entries (since they are spread  
> around and stored in other map-servers). But the map-server could  
> infer based on looking at the ALT to find positive entries. So some  
> research can be done on this idea to see if is tractable.
>
> It would be possible to install shorter negative plus one or more  
> longer positives that are not complete mappings, but "next-hop ms- 
> resolve," which would discard packets to the shorter negative but  
> still be able to punt and do MS query for the possibly-positive part  
> of the address space.

Yes, that could be done but again, we could create more entries then  
we wanted to.

> If I was the implementer, I would probably then keep count in my  
> Trie to know when a particular branch of the address space cache  
> contains mostly negative entries, which would indicate opportunities  
> for on-demand "compression."

Yes, we can do that as well.

> Another way to tackle (1) is to have the ITR look at the more- 
> specific negative prefixes to see if they can be combined into a  
> fewer number of more coarse prefixes using localized prefix  
> compression. If exact compression can be done, then do it (meaning  
> their are no positive holes in the compressed aggregate). If there  
> are holes created, they *could be mitigated* if you already have a  
> positive cache entry stored because you previously have encapsulated  
> to the site. But you can't always depend on this ordering to make it  
> reliable.
>
> I do not understand how this can be beneficial if the MS currently  
> sends negative replies that are the shortest possible prefixes which  
> do not overlap any possible positive mapping.  Keep in mind that my  
> understanding of the control-plane remains limited, specifically I  
> am not familiar with how much state is available from the local MS  
> vs what must be retrieved from distant MS.  I need to do some  
> homework in this area.

This is exactly what you suggested above. There are cases where a map- 
server returns a negative map-reply for a configured EID-prefix but  
has not been registered by the site.

> As for (2), we could say, we'll make a tradeoff by saving the cache  
> at the expense of more load on the mapping system. Well the mapping  
> system (like DNS) has to be provisioned and capacity planned to  
> handle load for scaling reasons. So it should also be able to handle  
> DoS load too. And if it can't, then the DoS load gets dropped (that  
> is the good news). But with every DoS load that gets dropped there  
> is good load that loses too. So take this with a grain of salt.
>
> But if the ITRs only stored positive cache entries, one might think  
> we would not know when to forward natively to non-LISP sites. Well  
> when an ITR gets a cache miss, it could send the packet natively as  
> well as send a rate-limited Map-Request. We do implement very short- 
> lived data-caches so we can do aggressive rate-limiting. If a Map- 
> Reply is returned, you know the destination is a LISP site and you  
> cache the positive entry. If nothing comes back, you continue to  
> forward natively. As I said, this puts more Map-Request load on the  
> mapping system.
>
> I do not understand how this can be effective.  If the ITR does not  
> have a native Locator address for the payload address family, and  
> the site is relying upon LISP, there won't be a way for packets to  
> even reach the "native Internet" for some alternate forwarding to  
> the destination.

A "native locator" as you termed it is just a FIB route with a next- 
hop. If the destination is non-LISP, the packet flows natively to the  
site as it does today. If the destination is a LISP site (and the ITR  
does not have a Map-Reply returned yet so it cannot encapsulate), the  
ITR will forward towards a PITR which will encapsulate to the site.

Dino

> _______________________________________________
> lisp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lisp