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

From: Peter Schoenmaker <[email-masked]>
Date: Thu, 18 Dec 2008 15:46:33 -0800

Hi,

It seems there is interest in this topic.  But to move forward we need  
volunteer(s) to act as the editor.

We already have one study <http://inl.info.ucl.ac.be/publications/cost-caching-locatorid-mappings 
 > specifically on LISP.  There is a request for a study of existing  
deployed protocols that use caching, and their operational impacts.

Do we have more specifics about the protocols to be studied, and what  
the paper would contain?

peter

On Nov 24, 2008, at 11:59 AM, Ron Bonica wrote:

> Hi Bill,
>
> Since we are discussing operational experience, I would like to see  
> the
> conversation continue on the GROW list.
>
> GROW chairs,
>
> There seems to be interest in this topic. Could you guys appoint a
> document editor?
>
>                                 Ron
>
>
> William Herrin wrote:
>> Thanks folks. The question was asked in GROW but it seems like its
>> most directly relevant to the research being done in RRG. I suggest  
>> we
>> move the discussion to one list or the other and periodically give an
>> update to both. Does anyone have a preference for which list?
>>
>> Regards,
>> Bill
>>
>>
>> On Wed, Nov 19, 2008 at 11:10 AM, PAPADIMITRIOU Dimitri
>> <[email-masked]> 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
>>>>
>>
>>
>>
> _______________________________________________
> GROW mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/grow

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

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Fri, 19 Dec 2008 00:56:59 +0100

Peter,

the below is what I proposed to Bill that launched the thread: 

---
Section 1: Introduction

Section 2: Motivations and Roles

Section 3: Caching Techniques

Section 3.1: Metrics
- Hit rate
- Hit time/Latency
- Others

Section 3.2: Cache Replacement Algorithms 
- Least Recently Used (LRU)
- Least Recently Replaced (LRR)
- Least Frequently Used (LFU)

-> Associativity (Direct mapping, Fully/N-Way/Skewed)

Section 3.4: Acquisition Techniques 
- Push: e.g. BGP
- Pull: e.g. DNS
- Hybrid Push-Pull 

Section 4: Operational experience

- Structure to be refined per input

Section 5: Conclusions

---

comments are welcome.

thanks,
-dimitri.

> Behalf Of Peter Schoenmaker
> Sent: Friday, December 19, 2008 12:47 AM
> To: Ron Bonica
> Cc: [email-masked]; Routing Research Group Mailing List
> Subject: Re: [GROW] Operational experience with cache based mapping ID
> 
> Hi,
> 
> We already have one study 
> <http://inl.info.ucl.ac.be/publications/cost-caching-locatorid
-mappings

---

From: "William Herrin" <[email-masked]>
Date: Thu, 18 Dec 2008 22:26:29 -0500

On Thu, Dec 18, 2008 at 6:46 PM, Peter Schoenmaker <[email-masked]> wrote:
> Do we have more specifics about the protocols to be studied, and what the
> paper would contain?

Hi Peter,

Apologies for my delinquency on this.

First, based on the feedback I've heard, I suggest keeping the
discussion about operational experience with pull-cache mapping
systems on GROW. GROW's traffic is pretty light right now. RRG has
gotten active as of late and I suspect there are a number of folks on
GROW who are interested in this subject but don't want to wade through
all the RRG messages.

Folks on RRG who want to subscribe to GROW to follow and participate
in this discussion can do so at:
https://www1.ietf.org/mailman/listinfo/grow . I will cut the RRG list
from future messages on this topic.

For the document, I was thinking along the lines of:

1. Introduction: We're looking to learn the difference between
successful and unsuccessful pull-cache mapping systems so that as we
consider using pull-cache for Internet routing we can avoid proposals
with the characteristics of an unsuccessful pull-cache map.

2. Interesting pull-cache systems seen in operations (brief summaries)

2a. At least two successful pull-cache systems. DNS and CPU ram cache perhaps?

2b. At least four superseded (unsuccessful) pull-cache systems. Cisco
fast switching (cache single IP address destinations in a hash table).
What else?

3. Metrics for each system

3a. Estimated upper bound of entries in the system (DNS has billions
of entries. A CPU cache can handle millions of ram pages).

3b. Estimated upper bound of active entries in typical cache. (a few
hundred thousand names at once in a DNS cache. Around hundred thousand
pages in a CPU ram cache).

3c. Typical entries served per second (a few thousand with DNS. A
couple billion with the CPU cache)

3d. Typical delays on a cache miss (a couple hundred ns with the CPU
cache. 50 to 2000 ms with the DNS)

3e. Replacement algorithm

3f. Etc.

4. Commonalities

4a. Characteristics common to both successful and unsuccessful
pull-cache systems

4b. Characteristics observed primarily in unsuccessful pull-cache systems

4c. Characteristics observed primarily in successful pull-cache systems

5. Conclusions: what to look for and what to avoid in proposed
pull-cache systems for routing.

Thoughts? Any suggestions for what interesting but failed pull-cache
information systems we can glean insight from?

Regards,
Bill Herrin

p.s. Dimitri, did you receive my 12/2 response to your 11/29 email?
Wondering if we have a rogue spam filter somewhere between us.

---

From: Luigi Iannone <[email-masked]>
Date: Fri, 19 Dec 2008 10:49:51 +0100

Hi,

the paper http://inl.info.ucl.ac.be/publications/cost-caching-locatorid
shows some basic stats specific to the LISP cache.

If you are interested we can propose other measurements using the 
metrics that Dimitri is listing below (section 3 of the proposed toc).

I think this will be useful to deepen the understanding of the cache 
behavior in LISP, but also more generally on map-and-encaps solutions.

Cheers

Luigi

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Fri, 19 Dec 2008 15:19:24 +0100

bill, all,

a couple of comments here below

- on the scope: one may to limit to pull systems but the acquisition
techniques should also imho consider hybrid push-pull system

- on the structure/content:

  . section 2: i agree that a section should be included that provides
for an overview of the pull-system(s) and this before detailing
operational experience. but section 2 and 3 shall be reverted as metrics
are common (a section 3.1 on the metrics i detailed should be
considered)

  . section 2: segmentation of successful/unsuccessful is a matter of
choice but i would not qualify them as successful/unsuccessful at that
stage but keep analytical evaluation in section 4 

  . section 4: deals with characteristics and observations from the
field but there is a need to tackle the actual performance of these
systems. it is also worthwhile detailing performance wrt to the
different replacement algorithms (LRU,LFU,LRR)

thanks,
-dimitri.
ps: i missed your e-mail you sent on Dec.3rd

> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of William Herrin
> Sent: Friday, December 19, 2008 4:26 AM
> To: Peter Schoenmaker
> Subject: Re: [rrg] [GROW] Operational experience with cache 
> based mapping ID
>

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Sun, 21 Dec 2008 00:52:11 +0100

Hi Ron, 

> From: Ron Bonica [mailto:[email-masked]] 
> Sent: Friday, December 19, 2008 5:26 PM
> To: PAPADIMITRIOU Dimitri
> Cc: Peter Schoenmaker; [email-masked]; Routing Research Group 
> Mailing List
> Hi Dimitri,
> I think that this is a very good outline.
> 
> Someplace in the document, you might want to address failure 
> modes that
> are associated with each cache replacement algorithm and acquisition
> technique. 

Failure modes and their impact certainly deserve a dedicated 
section in the document indeed.

> The security consideration section should also talk about DoS
> attacks and mitigations.

The exploration problem is indeed a real issue. The security 
considerations will be addressed accordingly.

Thanks,
-dimitri.

---

From: Eliot Lear <[email-masked]>
Date: Sun, 21 Dec 2008 10:36:27 +0100

Dimitri,

I've written quite a bunch on this already, and you are free to borrow 
from any of the NERD versions you would like to snip from.

HOWEVER...

The title of the draft explicitly states "operational experience with 
cache based mapping".  Can you please help me with that?  I would think 
that as far as such mappings are concerned there are really only two 
groups of people who have any: LISPers and HIPsters.

If we are just going to talk about previous uses of caching, that's okay 
too, but I would suggest that the impact of a cache miss is HIGHLY 
variable based on application, and the actual occurrence of a cache miss 
is highly variable not only based on application, but based on 
configuration as well.

As a case in point, I used netnews to distribute the precursor of the 
Human Genome Project (GenBank) throughout the net to scientists' systems 
who would then suck the thing into an RDB.  Consistent distribution was 
important, and so a cache miss would stall an update.  But once the file 
had been loaded, any further misses were irrelevant.  There are a lot of 
netnews design examples out there from the server side.

It's been said that we've done caching before on routers, and this is 
true.  And so my point is simply this: the question must be asked, what 
are the similarities and differences between the systems in use and what 
was done previously?

Eliot

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Sun, 21 Dec 2008 16:49:10 +0100

Eliot, 

> From: Eliot Lear [mailto:[email-masked]] 
> Sent: Sunday, December 21, 2008 10:36 AM
> Cc: Ron Bonica; [email-masked]; Routing Research Group Mailing List

Thanks for the offer !

> If we are just going to talk about previous uses of caching, 
> that's okay too,

This is indeed the purpose i.e. "Lessons Learned with Caching" and such
lessons can be learned from both successful and unsuccessful
experiences. 

> but I would suggest that the impact of a cache miss is HIGHLY 

The question on how far the similarity holds with ongoing applications
listed here above is to be interpreted as follows: caching mechanisms
share a core set of common principles - so except if any of these new
application relies on a new caching mechanism there is no reason to
believe we will be left without useful material as outcome of this
exercise.  

Now i think there is another question in your statement - nature of the
cached information - as you seem to infer that mapping caches in the
networking space are specific to the two applications of LISP ad HIP:
the same answer applies here. 

> are the similarities and differences between the systems in 
> use and what was done previously?

Imho such document can provide for an analysis grid of what is currently
ongoing at RRG (or even at other groups) based on experience.
Nevertheless, the term "operational experience" MAY induce a certain
confusion in that it assumes currently deployed routing system makes
de-facto use of caching - this is why i would prefer the title "Lessons
Learned with Caching" so as to prevent any pre-assumption on any usage
or positive/negative experience.

Thanks,
-d.