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

From: Michael Meisel <[email-masked]>
Date: Sun, 30 Nov 2008 19:28:29 -0800

Luigi Iannone wrote:
> If that experience is useful I am ready to help
> 
> Luigi

Sorry to be so late coming into this, but we did some work on caching
effectiveness at PEs, see section 5 of our technical report:

http://fmdb.cs.ucla.edu/Treports/080004.pdf

-Michael

> Eliot Lear wrote:
>> 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
> _______________________________________________
> rrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/rrg
_______________________________________________
GROW mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/grow

---

From: Havard Eidnes <[email-masked]>
Date: Tue, 02 Dec 2008 20:31:27 +0100 (CET)

> http://fmdb.cs.ucla.edu/Treports/080004.pdf

There is some terminology used in section 5 that I'm not in tune with,
but I still think I got the gist of it.  If I read it correctly, the
simulations tried to use "typical" traffic patterns to validate the
behaviour, with a relatively limited population being served by the
network at the sampling points.

There are two potential problems with this when one look at it on a
wider scale:

1) From an operational perspective, one is much more interested in
   robust behaviour under *any* circumstances.  So, in addition to
   looking at "typical" traffic traces, one should also study the
   worst-case behaviour.

2) My guess is that if one tries to employ caching solutions when one
   serve ever larger populations (as in the current Internet, when
   e.g. performing service in large ISPs networks), caching solutions
   will come under significantly more strain, since my expectation is
   that the forwarding will encounter ever more entropy/randomness,
   decreasing the utility of caching solutions.

I'm old enough to remember the first-generation "route cache" used on
Cisco AGS+ routers, and the initial design's reliance on "typical
traffic patterns" -- if I recall correctly it inserted host entries in
the destination forwarding cache.  It performed reasonably well under
normal circumstances, but fell over when the first user in rather
quick succession tried to sequentially "ping" all the addresses on the
Internet...  That lead (via several intermediate steps) down the path
to the current situation where Internet routing gear typically does
not operate with forwarding caches, but instead with fully populated
FIBs for use by the forwarding logic.

Regards,

- Håvard

---

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:
>>>> 3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>

---

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 
> >>>> operational experience with cache-based mapping systems. 
> Systems  
> >>>> like

---

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: Ron Bonica <[email-masked]>
Date: Fri, 19 Dec 2008 11:25:54 -0500

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. The security consideration section should also talk about DoS
attacks and mitigations.

                              Ron

---

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
> 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: "William Herrin" <[email-masked]>
Date: Sun, 21 Dec 2008 03:21:17 -0500

Hi Dimitri,

BGP is not a cache acquisition technique. BGP is a database
distribution mechanism. The very essence of a cache is that it
contains only a small working set carved from the full database.

Caches can pull from local databases and remote databases. They can
pull from central and distributed databases. But without fail, they
are populated when requests for data pull it in from the larger
database.

To the extent information is pushed to a cache, it generally falls
into two categories: extra information included in response to a pull
and speculative information that an external system has some reason to
believe the cache will need.

The "additional" section of a DNS response is an example of extra
information. Gratuitous ARP is an example of a speculative push.

Regards,
Bill Herrin

---

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

Bill, 

I meant that the working set is extracted/derived from the BGP routing
database. 

To remove the confusion, I suggest to consider i) pull from local
database (e.g. BGP RIB) - one could refer to local pull, ii) pull from
remote databases (e.g. DNS) - one could refer to remote pull, and as I
stated in my previous post iii) "hybrid pull-push" to cover the case of
proactive cases.

Would that work for you ?
-dimitri.

> From: [email-masked] [mailto:[email-masked]] On Behalf 
> Of William Herrin
> Sent: Sunday, December 21, 2008 9:21 AM
> Cc: [email-masked]

---

From: "William Herrin" <[email-masked]>
Date: Sun, 21 Dec 2008 09:30:56 -0500

On Sun, Dec 21, 2008 at 4:36 AM, Eliot Lear <[email-masked]> wrote:
> 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.

Hi Eliot,

I think we have a disconnect here. Is the gentleman who asked the
original question around? Would you mind clarifying your question?

What kind of operational experience are you interested in?

Do you want to know what early-stage proposals have encountered in
their experimental settings?

As Eliot points out, most of the ideas from RRG are in the
pre-engineering research phase. In many cases there is no protocol,
let alone operational data about it. As you might expect for the IRTF,
the RRG task is determining the universe of possible solutions and
sorting out which of the ideas are promising enough to merit deploying
engineering resources in IETF working groups.

Or do you want to know what behavior we've observed in major, deployed
pull-cache systems in the past?

We should be able to offer reliable answers to this question, but
they'll be less directly relevant to the routing domain. To my
knowledge, the routing domain has not previously seen the successful
deployment and use of a pull-cache system.

Regards,
Bill Herrin

---

From: "William Herrin" <[email-masked]>
Date: Sun, 21 Dec 2008 10:16:13 -0500

Hi Dimitri,

Not really, no.

Are you aware of any examples of a cache coupled with a BGP RIB?
Generally we see a full database conversion to produce the local FIB
and we see direct queries for diagnostics such as a looking glass. On
occasion we also see defined database subsets propagated towards a
peering-only router. None of these activities exhibit the
characteristics commonly understood to be a cache.

If no such system exists, we can hardly report on its operational properties.

The key elements of the matrix seem to be:

* Pull, pull with extra, speculative push.

All caching systems exhibit pull, pull with extra or both. Some also
have speculative push.

Example of pull: ARP request and response.
Example of pull with extra: DNS request and response with "additional" section.
Example of speculative push: cache page invalidation due to a write to
another CPU's cache in a multi-CPU system.

* Local database, remote database.

The major difference between a local database and a remote database is
that lookups to a local database are expected to succeed with a high
enough probability of success that it can be considered a
critical-stop failure when they don't succeed.

Example of a local database: DRAM on a computer.
Example of a remote database: DNS.

* Central database, distributed database.

Example of a central database: A SQL server.
Example of a distributed database: Virtual memory: multiple swap files
on different hard disks.

Note that some virtual memory architectures treat DRAM as a cache for
virtual memory while others treat DRAM as one element in a distributed
database.

For the former, the swap must be at least as large as the DRAM and the
swap page is allocated at the same time as the DRAM page. In the
latter, space in the swap file is not allocated until you want to
remove a page from DRAM.

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

Can you offer examples of associativity outside of CPU caches? The
ones you've mentioned here are all very specific to issues that arise
when trying to deal with mapping CPU cache pages to DRAM pages.

Regards,
Bill Herrin

---

From: "John G. Scudder" <[email-masked]>
Date: Sun, 21 Dec 2008 10:20:42 -0500

> Are you aware of any examples of a cache coupled with a BGP RIB?

Pre-CEF cisco routers.  (Not that they're the only ones to have  
shipped a router like this, just the most well-known case.)

--John

---

From: "William Herrin" <[email-masked]>
Date: Sun, 21 Dec 2008 10:26:09 -0500

On Sun, Dec 21, 2008 at 10:20 AM, John G. Scudder <[email-masked]> wrote:
> Pre-CEF cisco routers.  (Not that they're the only ones to have shipped a
> router like this, just the most well-known case.)

Hi John,

Not so. Cisco fast switching implemented a cache coupled with the
router's FIB. The FIB was constructed in part from the BGP RIB, but it
was its own full database.

Regards,
Bill Herrin

---

From: "John G. Scudder" <[email-masked]>
Date: Sun, 21 Dec 2008 10:29:07 -0500

> was its own full database.

Seems like an unimportant difference in terms of system dynamics but  
maybe I'm missing your point.

--John

---

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
> 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.

Thanks for the offer !

> 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,

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 
> 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.

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. 

> 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?

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.

---

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

Hi Bill,

> Sent: Sunday, December 21, 2008 4:16 PM

Cisco Express Forwarding (CEF) to give one of the best known example. 

> another CPU's cache in a multi-CPU system.

No difference here with the initial segmentation proposed, you can add a
pull with metadata but there is no fundamental difference. 
 
> Example of a remote database: DNS.

So, basically we have local and remote databases. Something different
from the above proposal ?
This said local dabases do not resume to DRAM any Local Information Base
can be considered (the case with cache entries derived BGP routing
entries is a good example). 

> latter, space in the swap file is not allocated until you want to

I fail to see why we would have to consider non-colocated central
databases for a networking system that is by definition distributed -
afaik the document does not intend to cover (e.g. file) caching for
centralized IT systems.

> when trying to deal with mapping CPU cache pages to DRAM pages.

A routing cache differs from a DRAM because the former only requires
Read from the Forwarding engine while the latter supports R/W from the
CPU. The application (routing) makes also the system specific wrt to the
dynamics of the routing table compared to the DRAM-CPU system. 

Other than this DRAM-CPU and routing cache-RIB system are both driven by
associativity, replacement and pre-load/pre-fetch

Regards,
-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: "William Herrin" <[email-masked]>
Date: Sun, 21 Dec 2008 12:53:08 -0500

On Sun, Dec 21, 2008 at 10:29 AM, John G. Scudder <[email-masked]> wrote:
> Seems like an unimportant difference in terms of system dynamics but maybe
> I'm missing your point.

Hi John,

The point is that the methodology is incorrect. They're not coupled.
The BGP RIB-level activity implies nothing about the fast switching
cache-level activity and vice versa. If you want to understand the
operational characteristics of caching, you'd be looking in the wrong
place.

Looking at cache to RIB, best case you glean no useful information.
Worst case you find correlations that imply a false causation matrix,
contaminating any decisions you make with the information.

Think of it like a boxcar on a railroad. If you want to understand the
behavior of the boxcar, you don't look at its relationship to the
engine. You look at its relationship to the car in front, the car
behind and track below.

> Cisco Express Forwarding (CEF) to give one of the best known example.

No, CEF is an example of a full FIB database. Don't expand the
definition of a cache to the point where it is indistinguishable from
the database to which it is subservient. You would render any
conclusions you reach into gibberish and we'd be right back where we
started with no way to evaluate the efficacy of LISP's route caching
proposal.

> pull with metadata but there is no fundamental difference.

Would you argue that when I request the route for a particular
destination IP address, there would be no operational difference
between a caching system that returns the next hop for the requested
IP address and a caching system that returns the next hop for the
prefix containing that IP address?

Meaning no disrespect, I think you've placed a conclusion ahead of the
research here.

> entries is a good example).

Yes, there is something different. With a local database, there is
little or no error recovery between the cache and the database. As a
result, error recovery is not a factor in evaluating the cache's
behavior. With a remote database, the impact of error recovery is a
huge factor.

> afaik the document does not intend to cover (e.g. file) caching for

Elements of some of the proposed solutions on RRG place a supposed
cache at the top level of the database distribution hierarchy. In
reality, the top of the hierarchy ends up functioning as a remote
central database of routes from which each encoder caches a working
set.

When evaluating those proposals, you will want to understand the
implications of a central versus distributed database. You'll also
want to be able to recognize when part of what the author has proposed
is not functionally a cache at all, even though he describes it that
way.

> dynamics of the routing table compared to the DRAM-CPU system.

Maybe I didn't explain myself well. Let me try again:

With routing algorithms, we use netmasks instead of specifying a
generic range of IP addresses with arbitrary starts and ends. We do
this because the hardware logic to implement netmasks is much simpler.

CPU caches face a similar problem keeping track of which range of
memory a particular cache page represents and which range of memory a
nearby cache page should represent. This is called the associativity
issue. Fully, n-way and skewed are examples of constraints on the map
between CPU cache and DRAM which simplify the hardware logic that
implements the cache.

I propose that this associativity issue is unique to the PC memory
management domain. Issues which appear in only one caching problem are
a property of that problem domain, not a general property of caching
systems. Because we don't want to confuse the issue with irrelevant
information, we should not consider associativity as part of the
report on caching systems.

I ask you to falsify this proposal by offering a concrete example of
one associativity issue in a well known caching problem domain other
than PC memory management.

> ongoing at RRG (or even at other groups) based on experience.

Refer to http://bill.herrin.us/network/rrgarchitectures.html for a
grid of current activity on RRG. Note that this document does not
address operational experience at all; it just describes the
architectures that have been proposed.

Regards,
Bill Herrin

p.s. Dimitri, I sent you another copy of my 12/3 message. If you
didn't receive it, please check your spam folder and/or your server
rejection logs.

---

From: "John G. Scudder" <[email-masked]>
Date: Sun, 21 Dec 2008 13:09:11 -0500

> The point is that the methodology is incorrect. They're not coupled.

Practically speaking, this is not correct, all the more so in an  
architecture where there is a highly notional separation between the  
different data structures in question.

> operational characteristics of caching, you'd be looking in the wrong

We have real-world operational experience that says otherwise.

> engine. You look at its relationship to the car in front, the car

To extend the analogy, do you mean to assert that the engine has no  
relevance to the behavior of the boxcar?

--John

---

From: "John G. Scudder" <[email-masked]>
Date: Sun, 21 Dec 2008 14:01:07 -0500

> We have real-world operational experience that says otherwise.

To expand on this comment slightly, I don't mean to assert correlation  
between BGP activity and cache activity [*].  What I do mean to say is  
that experience with fast switching (and similar) is very relevant to  
thinking about any other cache-based forwarding scheme, whether the  
"engine" (to use your analogy) is BGP or some other map distribution  
scheme.

--John

[*] Though I'll note in passing and only as a curiosity that non- 
correlation, while intuitively obvious, has not actually been proven  
AFAIK.
_______________________________________________
GROW mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/grow

---

From: "William Herrin" <[email-masked]>
Date: Sun, 21 Dec 2008 15:36:18 -0500

> We have real-world operational experience that says otherwise.

John,

Maybe. The past two years of research on RRG suggest that conclusion
is in error, that you have in fact missed something. If we test with
the proper methodology, one possible outcome is that you're right and
RRG needs to exclude a whole set of solutions that are currently on
the table. If instead we make intuitive leaps in our methodology, only
one outcome is likely: garbage in, garbage out.

The fast switching route cache talks to the FIB and the FIB talks to
the protocol RIBs. Those are the system boundaries. If you want to
examine the behavior of the cache, the function of the RIBs is out of
scope, hidden behind the behavior of the FIB.

> relevance to the behavior of the boxcar?

The boxcar is not pulled on the vector the engine travels. Instead,
the boxcar is pulled on the vector the car in front is traveling. Pay
attention to the engine and you'll incorrectly expect the boxcar to
derail at the first turn.

Pay attention to the BGP RIB in caching systems that don't directly
interact with it and you'll deduce caching behavior in proposed
protocols which is not a credible result of those protocols'
operation.

> between BGP activity and cache activity.  What I do mean to say is that
> experience with fast switching (and similar) is very relevant to thinking
> about any other cache-based forwarding scheme, whether the "engine" (to use
> your analogy) is BGP or some other map distribution scheme.

Our experience with how the fast switching cache interacted with the
router's FIB is indeed very much on point. It is one of the very few
examples of pull-cache that is directly related to routing. But it
isn't related to BGP or Interdomain routing.

Fast switching failed in much smaller configurations too. As we seek
to understand why, we should avoid confusing the issue with irrelevant
information.

I object to treating BGP as a source database which pushes information
into a cache unless an example of such a system in fact exists. Fast
switching is not such a system. It pulls, not pushes information from
the router FIB, and it interacts with the FIB, not the BGP RIB.

Accordingly, Dimitri's section 3.4 push acquisition of cache data from
the BGP RIB is invalid. No such system ever existed, so any
description of it's operational properties would be false.

What did exist was a destination address to next hop cache pulled from
the local-central FIB database. I think it's very important that we
learn why that failed when it's sister system, the DNS, has performed
so well. I think we'll find clues to that answer by examining other
successful and more importantly, unsuccessful pull-cache systems that
aren't necessarily related to the Internet.

My theory, by the way, is that the DNS did encounter the same problem
as fast switching around the same time. Because DNS caches operate
near the edge where cache miss loads aren't impossibly high and
because the DNS runs on general purpose hardware instead of
purpose-built appliances, the software developers were able to
quantify rogue behavior in a way that was efficiently detectable.
Rogue behavior was simply too many cache misses per second from the
same source. They implemented detection and blocking code, and the
problem went away almost before it began.

We'll see if my theory pans out.

Regards,
Bill Herrin

---

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

Bill, 

> Sent: Sunday, December 21, 2008 6:53 PM
> To: John G. Scudder
> Cc: PAPADIMITRIOU Dimitri; [email-masked]

I do not understand anymore where the objection is in your arguments:

- is it the issue of whether CEF or alike itself is not associated to a
caching system ? in my view a system that "routes the first packet and
switches the next packet of a given data flow" relies on a mechanism
where there is an intermediate entity storing a subset of the
information and that can be accessed faster than from its initial
location. As a matter of comparison in LISP: if the first packet arrives
at the ITR but no local mapping entry in the mapping cache, lookup is
performed to populate the mapping cache. 

- is it the issue of data traffic/packet-driven vs
routing/control-driven replacement ? in my view the kernel of the
problem of such system is the correlation between incomin traffic
destination prefixes (that issues read operations) and reachability
information dynamics (that performs write operations) and that problem
is common to CEF or other similar systems that RRG is currently
investigating.

... or is it the issue that we do not have any system coupled with
routing information base ?

> Meaning no disrespect, I think you've placed a conclusion ahead of the

I don't mean this. I simply refer that the addition of metadata can be
of importance it remains a pull operation. Dependency on the cache entry
themselves may be analysed for sure. 

> behavior. With a remote database, the impact of error recovery is a

So I think you agree with the point made: there are local and remote
databases.

> is not functionally a cache at all, even though he describes it that

I view this as a particular structure of a distributed set of remote
databases (in the form of distributed hierarchy). By central database
one usually refer to a single repository.

> between CPU cache and DRAM which simplify the hardware logic that

The associativity (or equivalently the placement and location tracking
of a cache entry) is a common trade-off in any caching system: on one
end of the spectrum full associativity on the other end of the spectrum
direct mapping.  

> than PC memory management.

Associative caches for IP routing is one example here among others.

> architectures that have been proposed.

I have read this document. It may serve as basis for such analysis.

Regards,
-dimitri.
> didn't receive it, please check your spam folder and/or your server

PS: i got it and will take a look at it.

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Sun, 21 Dec 2008 22:31:24 +0100

Bill,

> description of it's operational properties would be false.

This is not what I suggest (referring to my previous post):

"...the working set is extracted/derived from the BGP routing
database. 

To remove the confusion, I suggest to consider i) pull from 
local database (e.g. BGP RIB) - one could refer to local pull,"

Reason: the RIB is the source of information for where cache entries are
derived whereas the pull operations are traffic driven from these
"derived" entries. 

> the local-central FIB database. 

This would lead to an incomplete anaysis: by limiting caching system
analysis to forwarding cache entries wrt traffic dynamics (e.g.
exploration effects) one misses the impact resulting from routing
topology changes for ongoing traffic flows.  

The latter point is exactly one of the issues that have been extensively
discussed during last GROW meeting (another is the exploration effect).

Thanks,
-d.
> Sent: Sunday, December 21, 2008 9:36 PM
> To: John G. Scudder

---

From: "William Herrin" <[email-masked]>
Date: Sun, 21 Dec 2008 18:21:36 -0500

Hi Dimitri,

My objection is that you've expressed a misunderstanding of the
difference between a cache and a database. CEF creates an
authoritative database. When a packet is routed, the lookup occurs
directly on that database; no cache is involved.

By comparison, LISP and several of the other map-encap proposals have
a small cache which contains a working set of destinations presently
in use. When no cached entry matches a packet's destination, lisp
queries the database to find the destination and then adds the result
to its cache.

One is caching. One is not. You described both as caching, hence my objection.

Here's the problem: you've described a cache in a way that is
identical to the database on which the cache operates. You're
conclusions will be constrained by that definition. Because you've
made the terms equivalent, you won't be able to draw meaningful
distinctions between them.

> one usually refer to a single repository.

This is a subtle but very important point. If the top of the hierarchy
has a full database then it isn't a cache. And if the top of the
hierarchy is the only set of nodes with a full database then it isn't
a distributed database, it's a central database and the other levels
of the hierarchy are caches.

> Associative caches for IP routing is one example here among others.

Concrete example please. Is there an XYZ cache in IOS 12.9? Does JunOS
have a competing cache that works differently?

> derived whereas the pull operations are traffic driven from these

If you replace 3.4 push/pull/hybrid with 3.4 pull local-central, pull
local-distributed, pull remote-central and pull remote-distributed,
you'll be closer.

However, the BGP RIB still isn't an example of a database supplying a
local-central pull cache.

In Cisco fast switching, the cache is pulled from the router FIB,
*not* the BGP RIB. Nor is the FIB a direct derivative of the BGP RIB.
The router FIB is constructed from *multiple* protocol RIBs including
the connected RIB, the static RIB, the OSPF RIB, etc.

I am aware of no caching mechanisms which refer directly to the BGP
RIB. If you cite one that doesn't confuse the difference between a
cache and a database, I'll withdraw my objection.

Incidently, it's possible to build a small FIB cache instead of a
complete FIB. On a cache miss, you'd consult each of the RIBs
including the BGP RIB in order to compute a next hop to insert into
the cache. That would be an example of local-distributed-pull. The
problem is, no such system exists so we can't very well offer
observations about our operational experience with it.

If BGP is not a red herring here, I want you to demonstrate that with the data.

Regards,
Bill Herrin

---

From: "John G. Scudder" <[email-masked]>
Date: Sun, 21 Dec 2008 20:43:22 -0500

> the connected RIB, the static RIB, the OSPF RIB, etc.

While technically true this neglects the point that in real networks,  
the BGP-derived subset of the FIB tends to dominate (for large values  
of "dominate").

--John

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Mon, 22 Dec 2008 10:00:08 +0100

Bill

> difference between a cache and a database. 

My point is to prevent from hiding the fundamental issues of caching
behind system-/implementation specifics without looking at the broad
picture. 

Leaving outside the problem of comparison with CEF for a moment (because
I think it resulted in adding more confusion than add any
clarification), I think we are in disagreement on the description of a
cache: once a subset of entries from a full set is (re-)placed such that
it can be accessed faster than the initial set (the requestor benefits
from speed-up access/transfer of these entries), one speaks about a
cache-based system. the cache implementation itself is not actually
relevant at this level of description (it can be a set of records in a
table, memory entries, etc.) 

> You're conclusions will be constrained by that definition. Because 
> you've made the terms equivalent, 
>
> you won't be able to draw meaningful distinctions between them.
> 
> >> want to be able to recognize when part of what the author 
> >> has proposed is not functionally a cache at all, even though he 
> >> describes it that way.
> >
> > databases (in the form of distributed hierarchy). By 
> > central database one usually refer to a single repository.
> 

We have a different definition of a centralized database and distributed
database i think. A distributed database that includes temporarily or
not the full information set does not result in a centralized system.
So, I would leave people to comment here.  

> >> one associativity issue in a well known caching problem 
> >> domain other than PC memory management.
> >

There are past and ongoing experiments with such associative caches -
does that make the case more real ? or is the reality limited to Cisco
IOS or other commercial OS ? 

> local-distributed, pull remote-central and pull remote-distributed,

As said above pull local/remote from the forwarding point of view copes
with the read operation. what about the operation needed in case of
routing information change pushed downward onto the FIB (not triggered
by a change in dest. addresses but routing topology) ? 

I would have better covered cases where the database either local or
remote has an complete or an incomplete set (being a superset of the
working set but smaller than the full set) rather than speak about
central and distributed databases. 

> the connected RIB, the static RIB, the OSPF RIB, etc.

The point is known (forwarding cache entries are pulled from the FIB
derived from RIB/s) and i don't think we disagree. Note: initially my
assumption was to speak about mapping distribution independently on how
they are used to build the working set e.g from FIB via one or multiple
levels of indirection from RIB->FIB. By BGP it was meant they are known
locally by DNS they are queried if unknown locally. We have been mixing
the networking-level vs system-level description. 

So, I will use a system-level description to prevent us diverging from
the real issues in cache-based systems. Indeed, once we agree on this
description, we are left with the fundamental problems of caching: 

1) impact of the variability of the information source itself (FIB). So,
what is the dynamics of placement/replacement of the cache entries in
addition to the traffic spatial distribution.

2) impact of the granularity of the entries that results in trade-offs
between higher replacement rate vs working set size (and so cache size).

3) which strategy to populate an alternate cache (in case of failure of
the primary cache): proactive (pre-fetch and keep re/placement as for
the primary cache) or reactive (after failure and progressively
populated).

Thanks,
-dimitri.

---

From: "William Herrin" <[email-masked]>
Date: Mon, 22 Dec 2008 13:09:10 -0500

On Mon, Dec 22, 2008 at 4:00 AM, PAPADIMITRIOU Dimitri
<[email-masked]> wrote:
> I think we are in disagreement on the description of a cache:

You're right, we disagree. You held up a Golden Delicious apple, a
McIntosh apple and a Bartlett pear and said, "These are apples." The
pear isn't an apple. It may grow on a tree and it may have a similar
texture but a pear isn't shaped like an apple, it doesn't taste like
an apple and the bottom line is: it's not an apple.

Precomputing a FIB from a set of RIBs is not caching. It isn't even
memoization.

If you investigate starting with a faulty taxonomy, the "pear" will
serve as a false counter-example to many statements about apples which
are, in fact, true. You won't learn what you hope to learn, about
apples or caches.

> IOS or other commercial OS ?

I'll settle for a published research paper in which more than one type
of "associativity" is discussed in the context of caches excluding PC
memory caching.

I expect you to demonstrate that associativity is a caching issue in
more than one problem domain, hence an issue for caching in general
rather than an issue unique to PC memory caching. I'm not trying to be
dogmatic about this. You've claimed that associativity is a general
property of caches. I just want to see that claim supported.

> by a change in dest. addresses but routing topology) ?

I'm going to break off this branch of the conversation. We're starting
to delve into caching theory here. That's wonderfully interesting
stuff, I could go on about it all day, but it isn't on point. We're
supposed to be grounding the topic by discussing operational
experience with caches. For that, we should select a representative
sample of operational caching systems and then restrain the scope of
our discussion.

Regards,
Bill Herrin