Subject: Re: [lisp] #46: Cache Thrashing (review by Y. Rekhter)

From: [email-masked] (Noel Chiappa)
Date: Tue, 29 Mar 2011 17:33:49 -0400 (EDT)

> From: Yakov Rekhter <[email-masked]>

    > being able to detect thrasing is necessary, but not sufficient - an
    > implementation must be able to suppress thrasing.

I'm interested in the engineering aspects of this, not just what to say in
this particular document.

The only way I've ever heard of to really 'fix' (AKA prevent) cache thrashing
problems (going all the way back to the days of page replacement algorithms on
big time-sharing machines, back when machines had relatively small main
memories) is to either i) change the access pattern (perhaps by reducing
offered load), or ii) increase the size of the cache.

(Yes, yes, I know that in very limited-size caches, and to make the cache
hardware 'relatively' simple, you get things like N-way associative caches.  I
don't think those apply here, because our caches will of necessity be much
larger - since the cost of a miss is so large, we have to minimize miss count
- and implemented very differently.)

Since i) isn't really feasible for us , and ii) is 'relatively' easy now that
memory is so cheap, is there any reason not to say something to the effect of
'we recommend that to prevent any possibility of cache thrashing, the ITR
MUST be able to cache all the mappings it receives, only discarding mappings
which have not been used in a considerable time (e.g. 1 hour)'.

(Also, I think there is some data from one of the simulations done by the
guys in Europe which shows how large caches have to be - or had to be at the
time the simulations were done - to provide low levels of cache miss for
previously seen destinations. I seem to recall that there was enough info
there to work out how long you had to be able to hold mappings in the cache
to keep refill overhead, etc, down to a reasonable level. Perhaps we should
refer to that for setting the recommended hold time, above?)

	Noel

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 29 Mar 2011 17:44:13 -0400

While I like the theory you advance, I don't know how to build it in 
practice.  What size memory, short of the full LISP table, should I 
build in my device to meet the MUST?  Whatever size I build, someone can 
easily build a test case for which it fails.

Personally, I am actually curious to see, in an enterprise edge 
deployment, how well this works.  I presume there is already some data. 
  The experiment will tell us more.
I wonder about the interaction of caching with all sorts of other cases, 
but I do not see that the document needs to spell out all of the history 
of our problems, or the difficulties in addressing this, in order to 
conduct the experiment.

Yours,
Joel

On 3/29/2011 5:33 PM, Noel Chiappa wrote:
>      >  From: Yakov Rekhter<[email-masked]>
>
> _______________________________________________
> lisp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lisp
>

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 29 Mar 2011 14:46:07 -0700

> build in my device to meet the MUST?  Whatever size I build, someone  
> can easily build a test case for which it fails.

This is true for all tables, and the analysis to deploy a new box  
always takes this in consideration.

Dino

> deployment, how well this works.  I presume there is already some  
> data.  The experiment will tell us more.
> I wonder about the interaction of caching with all sorts of other  
> cases, but I do not see that the document needs to spell out all of  
> the history of our problems, or the difficulties in addressing this,  
> in order to conduct the experiment.
>
> Yours,
> Joel
>

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 30 Mar 2011 03:23:13 -0400

How about adding a second sentence to the paragraph in -11 that 
currently addresses this saying:
Cache sizing has deployment and control plane implications.

While one can get tempted into a long discussion of those implications, 
I do not think that is needed, whereas it is useful to remind 
implementors that those implications are present.

Thank you,
Joel

On 3/29/2011 5:46 PM, Dino Farinacci wrote:
> This is true for all tables, and the analysis to deploy a new box always
> takes this in consideration.
>
> Dino
>