Subject: [lisp] EID-to-RLOC Cache Integrity

From: Ronald Bonica <[email-masked]>
Date: Fri, 24 Jun 2011 17:00:50 -0400

Dino, 

A few weeks ago, we went round and round over the question of cache integrity and talked past one another. I think that I can formulate the question a little better now.

In order for an ITR to function properly, the EID-to-RLOC cache must conform to some integrity rules. These integrity rules are never stated explicitly in the base document. The reader is left to infer them from selected LISP behaviors. For example, you say that when the EID-to-RLOC database contains several more specific prefixes (e.g., 10.1.1.0/24) and a single overlapping less specific interface and the ITR sends a Map Request whose response is the less specific:

- the ETR must respond with the less specific and all of the more specifics
- the less specific must expire before the more specifics

This leads me to infer that if the ITR is to behave correctly and its cache contains the less specific, it must also contain all of the more specifics. But you never say this explicitly. I must infer it.

This integrity rule is important because it drives the answer to many other questions. For example:

- If the ITR uses the less specific and updates its expiration time,  must it update the expiration time of all of the more specifics, also?
- If the EID-to-RLOC cache thrashes, and I am forced to delete unexpired entries, must I delete the less specific before the more specifics?

Also, I am left to wonder if there are any other cache integrity rules that I have not gleaned from the text.

It would be good if you could add a section that explicitly states cache integrity rules.

                                                                       Ron

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 27 Jun 2011 09:34:42 -0700

> Dino,
>
> A few weeks ago, we went round and round over the question of cache  
> integrity and talked past one another. I think that I can formulate  
> the question a little better now.
>
> In order for an ITR to function properly, the EID-to-RLOC cache must  
> conform to some integrity rules. These integrity rules are never  
> stated explicitly in the base document. The reader is left to infer  
> them from selected LISP behaviors. For example, you say that when  
> the EID-to-RLOC database contains several more specific prefixes  
> (e.g., 10.1.1.0/24) and a single overlapping less specific interface  
> and the ITR sends a Map Request whose response is the less specific:

Sorry, I cannot parse your "For example" sentence. What is a "less  
specific interface"?

> This leads me to infer that if the ITR is to behave correctly and  
> its cache contains the less specific, it must also contain all of  
> the more specifics. But you never say this explicitly. I must infer  
> it.

Yes.

> - If the ITR uses the less specific and updates its expiration  
> time,  must it update the expiration time of all of the more  
> specifics, also?

The update of the expiration time is based on receiving a Map-Reply  
and in section 6.1.5, it is documented how to send and process Map- 
Replies when overlapping EID-prefixes are in use.

> - If the EID-to-RLOC cache thrashes, and I am forced to delete  
> unexpired entries, must I delete the less specific before the more  
> specifics?

You could. But you could also use an LRU algorithm on EID-prefixes  
which are not overlapping.

> Also, I am left to wonder if there are any other cache integrity  
> rules that I have not gleaned from the text.
>

We have been over this a number of times. The chairs believe the text  
that is already in the spec is sufficient and leaves opportunities  
open to experiment.

Dino

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

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 27 Jun 2011 12:44:12 -0400

There appear to be two related technical issues here.

The first one is on refreshing entries.  A refresh of a less-specific 
with overlapping more-specifics will inherently provide refresh of the 
more-specifics.  Even if an implementor does not realize that, he will 
do the right thing.  We can live with the text asa is on that.

The second one deals with a different issue.  In performing local 
maintenance of a cache with overlapping entries, one could easily get 
into a situation where the less-specific is being used (its use time 
would be updated), but the more-specifics are not being used.  An 
LRU-based cache maintenance algorithm could, according to what is 
written in the spec, remove these relatively-unused entries in teh event 
of cache exhaustion.
HOWEVER, such removal would actually be wrong.  It would break the 
coherence requirement.
As far as I know, nothing in the spec says taht.
Yes, a sufficiently attentive reader could realize that one set of 
protocol behavior could impact another.  But we do NOT normally expect 
readers to perform that level of inference.  Specs are to be 
implementable by folks who are not protocol designers.

Is there some place in the space where it says this?  If not, could we 
add a sentence or two in the text on local cache management.

Yours,
Joel

On 6/27/2011 12:34 PM, Dino Farinacci wrote:
>> - If the ITR uses the less specific and updates its expiration time,
>> must it update the expiration time of all of the more specifics, also?
>
> The update of the expiration time is based on receiving a Map-Reply and
> in section 6.1.5, it is documented how to send and process Map-Replies
> when overlapping EID-prefixes are in use.
>
> You could. But you could also use an LRU algorithm on EID-prefixes which
> are not overlapping.

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 27 Jun 2011 19:01:43 -0700

> The first one is on refreshing entries.  A refresh of a less- 
> specific with overlapping more-specifics will inherently provide  
> refresh of the more-specifics.  Even if an implementor does not  
> realize that, he will do the right thing.  We can live with the text  
> asa is on that.
>
> maintenance of a cache with overlapping entries, one could easily  
> get into a situation where the less-specific is being used (its use  
> time would be updated), but the more-specifics are not being used.   
> An LRU-based cache maintenance algorithm could, according to what is  
> written in the spec, remove these relatively-unused entries in teh  
> event of cache exhaustion.
> protocol behavior could impact another.  But we do NOT normally  
> expect readers to perform that level of inference.  Specs are to be  
> Is there some place in the space where it says this?  If not, could  
> we add a sentence or two in the text on local cache management.

Yes, I will make sure I mention how to time out entries when there are  
overlapping EID-prefixes. Thanks a lot for clarifying things Joel.

Dino

>>> This integrity rule is important because it drives the answer to  
>>> many
>>> other questions. For example:
>>>
>> and