Subject: [lisp] Fwd: [rrg] [GROW] Operational experience with cache based mapping ID

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Nov 2008 11:50:42 -0800

I should have mentioned this during my talk. There *is* documentation  
on caching. Particularly relative to LISP.

Dino

Begin forwarded message:

> From: Eliot Lear <[email-masked]>
> Date: November 19, 2008 10:45:08 AM PST
> To: PAPADIMITRIOU Dimitri <[email-masked]>
> Cc: [email-masked], Routing Research Group Mailing List <[email-masked]>
> Subject: Re: [rrg] [GROW] Operational experience with cache based  
> mapping ID
>
> Dimitri,
>
> I've done some work in this space, but the best data I know of still  
> is the work done by Iannone & Bonaventure:
>
>
> Iannone, L., Bonaventure, O., “Locator/ID Separation: Study on the  
> cost of Mappings Caching and Mappings Lookups”,  Technical Report N.  
> 2007-04, Universite Catholique de Louvain, July 2007.
>
> This work is important.  It indicates that concerns about cache  
> sizes are considerably overblown.  Please have a look at the numbers  
> and methodology in that work.
>
> Of course more information is always welcome.
>
> Eliot
>
> On 11/19/08 6:10 PM, PAPADIMITRIOU Dimitri wrote:
>> i see value in such effort. ready to help.
>> -d.
>>
>>
>>> -----Original Message-----
>>> From: [email-masked] [mailto:[email-masked]] On
>>> Behalf Of William Herrin
>>> Sent: Wednesday, November 19, 2008 5:17 PM
>>> To: [email-masked]; Routing Research Group Mailing List
>>> Subject: [GROW] Operational experience with cache based mapping ID
>>>
>>> Hi folks,
>>>
>>> There was a suggestion at grow this morning that we produce a ID on
>>> operational experience with cache-based mapping systems. Systems  
>>> like
>>> the DNS have been very successful. On the other hand, I still  
>>> remember
>>> worms sending to random destinations on a 56k modem DOSing a Cisco
>>> 2500 because of the route cache. It would be very helpful to  
>>> determine
>>> what factors allow a caching strategy to be successful and what
>>> factors tend to lead to failure.
>>>
>>> I think this is very relevant to a number of the solution strategies
>>> under discussion on RRG, not just LISP. So, is anyone else  
>>> interested
>>> in organizing the effort? If not, I volunteer.
>>>
>>> Regards,
>>> Bill Herrin
>>>
>>>
>>> -- 
>>> William D. Herrin ................ [email-masked]  [email-masked]
>>> 3005 Crane Dr. ...................... Web:<http://bill.herrin.us/>
>>> Falls Church, VA 22042-3004
>>> _______________________________________________
>>> GROW mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/grow
>>>
>>>
>> _______________________________________________
>> rrg mailing list
>> [email-masked]
>> https://www.irtf.org/mailman/listinfo/rrg
>>
>>
>
> _______________________________________________
> rrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/rrg

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

---

From: "Tony Li" <[email-masked]>
Date: Wed, 19 Nov 2008 14:04:52 -0600

My recollection of this was that it was a good data point in demonstrating
that in a well-behaved situation, with a limited end-site, that caching was
sufficient and that the working set size was tractable.

I think it would be a major mistake to infer that (a) the working set is
tractable for ALL possible end-sites or (b) that there are no attack vectors
opened by this approach.  From other previous side discussions, I believe
that we're actually at a point where we agree that there are sites for which
the working-set is not tractable and thus those sites MUST have a full map.
We need to understand the break point between where caching is workable and
where we have to convert to a much more expensive complete mapping.

We definitely need to understand the threat environment.

Tony

|-----Original Message-----
|From: [email-masked] [mailto:[email-masked]] On 
|Behalf Of Dino Farinacci
|Sent: Wednesday, November 19, 2008 1:51 PM
|To: [email-masked]
|Subject: [lisp] Fwd: [rrg] [GROW] Operational experience with 
|cache basedmapping ID
|
|I should have mentioned this during my talk. There *is* documentation  
|on caching. Particularly relative to LISP.
|
|Dino
|
|Begin forwarded message:
|
|> From: Eliot Lear <[email-masked]>
|> Date: November 19, 2008 10:45:08 AM PST
|> To: PAPADIMITRIOU Dimitri <[email-masked]>
|> Cc: [email-masked], Routing Research Group Mailing List <[email-masked]>
|> Subject: Re: [rrg] [GROW] Operational experience with cache based  
|> mapping ID
|>
|> Dimitri,
|>
|> I've done some work in this space, but the best data I know 
|of still  
|> is the work done by Iannone & Bonaventure:
|>
|>
|> Iannone, L., Bonaventure, O., "Locator/ID Separation: Study on the  
|> cost of Mappings Caching and Mappings Lookups",  Technical 
|Report N.  
|> 2007-04, Universite Catholique de Louvain, July 2007.
|>
|> This work is important.  It indicates that concerns about cache  
|> sizes are considerably overblown.  Please have a look at the 
|numbers  
|> and methodology in that work.
|>
|> Of course more information is always welcome.
|>
|> Eliot
|>
|> On 11/19/08 6:10 PM, PAPADIMITRIOU Dimitri wrote:
|>> i see value in such effort. ready to help.
|>> -d.
|>>
|>>
|>>> -----Original Message-----
|>>> From: [email-masked] [mailto:[email-masked]] On
|>>> Behalf Of William Herrin
|>>> Sent: Wednesday, November 19, 2008 5:17 PM
|>>> To: [email-masked]; Routing Research Group Mailing List
|>>> Subject: [GROW] Operational experience with cache based mapping ID
|>>>
|>>> Hi folks,
|>>>
|>>> There was a suggestion at grow this morning that we produce a ID on
|>>> operational experience with cache-based mapping systems. Systems  
|>>> like
|>>> the DNS have been very successful. On the other hand, I still  
|>>> remember
|>>> worms sending to random destinations on a 56k modem DOSing a Cisco
|>>> 2500 because of the route cache. It would be very helpful to  
|>>> determine
|>>> what factors allow a caching strategy to be successful and what
|>>> factors tend to lead to failure.
|>>>
|>>> I think this is very relevant to a number of the solution 
|strategies
|>>> under discussion on RRG, not just LISP. So, is anyone else  
|>>> interested
|>>> in organizing the effort? If not, I volunteer.
|>>>
|>>> Regards,
|>>> Bill Herrin
|>>>
|>>>
|>>> -- 
|>>> William D. Herrin ................ [email-masked]  
[email-masked]
|>>> 3005 Crane Dr. ...................... Web:<http://bill.herrin.us/>
|>>> Falls Church, VA 22042-3004
|>>> _______________________________________________
|>>> GROW mailing list
|>>> [email-masked]
|>>> https://www.ietf.org/mailman/listinfo/grow
|>>>
|>>>
|>> _______________________________________________
|>> rrg mailing list
|>> [email-masked]
|>> https://www.irtf.org/mailman/listinfo/rrg
|>>
|>>
|>
|> _______________________________________________
|> rrg mailing list
|> [email-masked]
|> https://www.irtf.org/mailman/listinfo/rrg
|
|_______________________________________________
|lisp mailing list
[email-masked]
|https://www.ietf.org/mailman/listinfo/lisp
|

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Nov 2008 12:36:33 -0800

When the working set exceeds the capacity, you install a single course  
entry and use network diameter and network hierarchy to scale "the  
system wide cache". Choose your tradeoff of cache size versus data- 
path stretch. We might have to choose both in different parts of the  
network.

Rather than anyone saying what is wrong with caching, present an  
alternative which is better.

Dino

On Nov 19, 2008, at 12:04 PM, Tony Li wrote:

> |> Cc: [email-masked], Routing Research Group Mailing List <[email-masked] 
> >

---

From: "Tony Li" <[email-masked]>
Date: Wed, 19 Nov 2008 14:43:37 -0600

|When the working set exceeds the capacity, you install a 
|single course  
|entry and use network diameter and network hierarchy to scale "the  
|system wide cache". 

In other words, punt to the next level of cache, which then has an even
larger working set.  How does that help?  It degenerates into a centralized
full map, which clearly doesn't work.

|Choose your tradeoff of cache size versus data- 
|path stretch. We might have to choose both in different parts of the  
|network.
|
|Rather than anyone saying what is wrong with caching, present an  
|alternative which is better.

First, we have to be free to say what is wrong.  Bringing up bugs in a free
and open way is necessarily part of the process.

Second, there have been numerous alternatives discussed: full map, DHT, and
hybrids.  

We still don't seem to have consensus on a direction.

Tony

---

From: Eliot Lear <[email-masked]>
Date: Wed, 19 Nov 2008 22:08:52 +0100

Hi Tony,

> sufficient and that the working set size was tractable.

The data set in question comes from a campus network with 10,000 active 
users.  The estimated cache size with a five hour timeout is 
approximately 3MB.  The full paper is available at 
http://inl.info.ucl.ac.be/system/files/Conext-2007-CRV-UCL-v2-Clean.pdf.

Eliot

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Nov 2008 13:13:40 -0800

> full map, which clearly doesn't work.

Tony, you know how hierarchy works. You follow coarse prefixes as you  
go up and more specifics as you go down. See draft-meyer-lisp- 
cons-04.txt for details. And refer to the VA stuff Paul is working on.

> and open way is necessarily part of the process.

Right, and we don't want that to stop. But would like some  
alternatives as well.

> Second, there have been numerous alternatives discussed: full map,  

Right, and I think many of these are misunderstood because they are  
not brought to the level of detail to find the bugs.

Dino

---

From: "Tony Li" <[email-masked]>
Date: Wed, 19 Nov 2008 16:04:49 -0600

Dino,

|Tony, you know how hierarchy works. You follow coarse prefixes as you  
|go up and more specifics as you go down. See draft-meyer-lisp- 
|cons-04.txt for details. And refer to the VA stuff Paul is working on.

I do indeed know how hierarchy works.  I know that a caching element in a
hierarchy that overruns its working set is going to thrash.  I know that you
can only scale if you distribute the work (in this case caching) down the
hierarchy towards the leaves.  I know that redirecting those requests
upwards is simply going to cause the collapse of higher layers. 

I also know that it's trivial to attack caches through a random walk of the
namespace.  I also know that it's trivial to trigger that remotely if there
is any way to get a response to a random incoming source.  

I know that any proposal needs to address these issues, not duck them.

|> Second, there have been numerous alternatives discussed: full map,  
|> DHT, and
|> hybrids.
|
|Right, and I think many of these are misunderstood because they are  
|not brought to the level of detail to find the bugs.

I think that many people are not willing to have the architectural
discussions necessary because they find it more fun to jump into the
architecturally irrelevant details.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Nov 2008 14:12:36 -0800

> is any way to get a response to a random incoming source.

Tell me why a BGP routing table is not a cache? And does not suffer  
the same problems you state above?

Both cases are data structures, malloc() is done in both cases, and  
capacity problems happen in both cases. The only difference is *when*  
the data structure is populated.

Dino

---

From: "Tony Li" <[email-masked]>
Date: Wed, 19 Nov 2008 16:31:53 -0600

|Tell me why a BGP routing table is not a cache? And does not suffer  
|the same problems you state above?

Interesting.  Please see http://en.wikipedia.org/wiki/Cache.

BGP pushes around a set of data (paths).  There is no fetch of remote
information triggered by usage.  There is no LRU removal of unused data.
There is no temporal fluctuation in the state space used due to the requests
seen.

In short, BGP is a partial map distribution mechanism.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Nov 2008 14:58:43 -0800

> In short, BGP is a partial map distribution mechanism.

Would you say NERD is similar to BGP then?

Like George Michaelson mentioned today, any mapping distribution  
scheme can be used with the LISP data plane. Meaning LISP can work  
without a cache. And if we put in a push map distribution scheme or a  
partial map distribution mechanism like BGP, would you say LISP  
doesn't use a cache?

Dino

---

From: "Tony Li" <[email-masked]>
Date: Wed, 19 Nov 2008 17:17:17 -0600

|Would you say NERD is similar to BGP then?

There are certain similarities, yes.

|Like George Michaelson mentioned today, any mapping distribution  
|scheme can be used with the LISP data plane. Meaning LISP can work  
|without a cache. And if we put in a push map distribution scheme or a  
|partial map distribution mechanism like BGP, would you say LISP  
|doesn't use a cache?

Even more generally, the mapping problem can and should be decoupled from
the 'data plane' problem throughout RRG.  The confounding of multiple
problems and the resulting cross product of solutions is making the
situation much more complex than it has any right to be.  If folks could
simply walk away from their various specific proposals and stick to
architectural directions, we might make it to consensus much more rapidly.

Tony

P.s.  Yes, I recognize that not every mapping mechanism is going to play
well with every data plane mechanism.  That's ok.  Architecture is the
process of breaking down the large problem into a number of smaller problems
and deciding how to proceed on each of those smaller problems.

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 19 Nov 2008 15:21:58 -0800

> architectural directions, we might make it to consensus much more  

At the end of the day, you have to make a decision. And it's been 25  
months since the IAB workshop.

Dino

---

From: "Tony Li" <[email-masked]>
Date: Wed, 19 Nov 2008 22:52:12 -0600

|At the end of the day, you have to make a decision. 

s/you/we/

Again, we need consensus to do anything meaningful.  We need the support of
the entire IETF and the entire industry to have any impact.  

Tony

---

From: Scott Brim <[email-masked]>
Date: Wed, 19 Nov 2008 17:50:46 -0600

This is an RRG issue.  I'll respond over there.

Excerpts from Tony Li on Wed, Nov 19, 2008 05:17:17PM -0600:
> |without a cache. And if we put in a push map distribution scheme or
> a  |partial map distribution mechanism like BGP, would you say LISP
> |doesn't use a cache?
> 
> Even more generally, the mapping problem can and should be decoupled
> from the 'data plane' problem throughout RRG.  The confounding of
> multiple problems and the resulting cross product of solutions is
> making the situation much more complex than it has any right to be.
> If folks could simply walk away from their various specific
> proposals and stick to architectural directions, we might make it to
> consensus much more rapidly.
> 
> Tony
> 
> P.s.  Yes, I recognize that not every mapping mechanism is going to
> play well with every data plane mechanism.  That's ok.  Architecture
> is the process of breaking down the large problem into a number of
> smaller problems and deciding how to proceed on each of those
> smaller problems.