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

From: "lisp issue tracker" <[email-masked]>
Date: Wed, 16 Mar 2011 09:42:12 -0000

#46: Cache Thrashing (review by Y. Rekhter)

Changes (by luigi@…):

  * status:  new => resolved
  * resolution:  => fixed

Comment:

 Authors replied on the mailinglist that in their opinion there is no need
 to make any change to the draft. Neither the original person that raised
 the issue nor the mailinglist stated a different opinion.

-- 
-------------------------------+--------------------------------------------
Reporter:  wmhaddad@…          |        Owner:                 
    Type:  technical           |       Status:  resolved       
Priority:  major               |    Component:  draft-ietf-lisp
Severity:  -                   |   Resolution:  fixed          
Keywords:                      |  
-------------------------------+--------------------------------------------

Ticket URL: <http://trac.tools.ietf.org/wg/lisp/trac/ticket/46#comment:2>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: "lisp issue tracker" <[email-masked]>
Date: Wed, 16 Mar 2011 09:42:30 -0000

Changes (by luigi@…):

  * status:  resolved => closed

    Type:  technical           |       Status:  closed         

Ticket URL: <http://trac.tools.ietf.org/wg/lisp/trac/ticket/46#comment:3>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: "lisp issue tracker" <[email-masked]>
Date: Wed, 16 Mar 2011 19:34:15 -0000

Changes (by yakov@…):

  * status:  closed => reopened
  * resolution:  fixed =>

Comment:

 The issue raised in this ticket has to be addresses. Until it is
 addressed, the ticket should stay open.

-- 
-------------------------------+--------------------------------------------
Reporter:  wmhaddad@…          |        Owner:                 
    Type:  technical           |       Status:  reopened       
Priority:  major               |    Component:  draft-ietf-lisp
Severity:  -                   |   Resolution:                 
Keywords:                      |  
-------------------------------+--------------------------------------------

Ticket URL: <https://wiki.tools.ietf.org/wg/lisp/trac/ticket/46#comment:4>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: "lisp issue tracker" <[email-masked]>
Date: Thu, 17 Mar 2011 16:48:25 -0000

Comment(by yakov@…):

 From the response to the ticket:

   Thank you for your contribution to draft-ietf-lisp-06.txt. The draft
 authors
   have reviewed your comments but do not feel that changes to the document
 are
   warranted at this time. We feel that existing text adequately describes
 cache
   management behavior.

 The response is insufficient, as it fails to point out to the specific
 section(s) of the existing text that according to the authors "adequately
 describes cache management behavior". In order to determine whether the
 existing text is adequate, the first thing the authors need to do is to
 point out to such text.

Ticket URL: <http://trac.tools.ietf.org/wg/lisp/trac/ticket/46#comment:5>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: "lisp issue tracker" <[email-masked]>
Date: Tue, 29 Mar 2011 16:26:10 -0000

Changes (by jmh@…):

  * status:  reopened => resolved
  * resolution:  => fixed

Comment:

 Text has been added to the -11 revision of teh specification noting that
 cache thrashing happens, that implementors should think about it, and that
 the experiment may tell us more about whether this is an issue needing
 further attention.

Ticket URL: <https://wiki.tools.ietf.org/wg/lisp/trac/ticket/46#comment:6>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 29 Mar 2011 10:14:18 -0700

Hi,

>  the experiment may tell us more about whether this is an issue needing

Here is the text that has been added:

   Given that the ITR/PTR maintains a cache of EID-to-RLOC mappings,
   cache sizing and maintenance is an issue to be kept in mind during
   implementation.  It is a good idea to have instrumentation in place  
   to detect thrashing of the cache.  Implementation experimentation  
   will be used to determine which cache management strategies work
   best.

The above text failed to mention that cache sizing is an issue not
just "during implementation", but during deployment as well.

Moreover, the above text failed to mention that in the context of
LISP, thrashing of the cache on a given ITR/PTR has non-local
implications, as it could result in excessive volume of LISP control
traffic, which in turn would further deteriorate the situation.

Finally, the above failed to mention that being able to
detect thrasing is necessary, but not sufficient - an implementation
must be able to suppress thrasing.

With all this in mind I would like to propose replacing the text
quoted above with the following:

   Given that the ITR/PTR maintains a cache of EID-to-RLOC mappings,
   cache sizing and maintenance is an issue to be kept in mind
   during both implementation and deployment. In the context of
   LISP, cache thrasing on the ITR/PTR could result in the ITR/PTR
   dropping data, thus negatively affecting connectivity. Moreover,
   it could also result in excessive volume of LISP control traffic,
   which could spread the detrimental effects of thrasing beyond
   the ITR/PTR and all the hosts that communicate through this
   ITR/PTR. Therefore, an implementation MUST provide instrumentation
   in place to detect thrashing of the cache, and MUST provide
   mechanism(s) to suppress thrasing.  Specifications of such
   mechanisms are outside the scope of this document.  Implementation
   experimentation will be used to determine which cache management
   strategies work best.

Yakov.

---

From: Eliot Lear <[email-masked]>
Date: Tue, 29 Mar 2011 22:51:26 +0200

Hi Yakov,

> just "during implementation", but during deployment as well.

I agree with this point.  I believe actually the change for the above
text is to change "Implementation experimentation" simply to
"Experimentation" or "Deployment experience".

> traffic, which in turn would further deteriorate the situation.

I agree with this concern.  The degenerative case one could imagine is a
cache of 1 entry, in which case packets to every separate site would
generate queries, presumably through the ALT.  However...
> must be able to suppress thrasing.

I agree with this point.  However, I would suggest a different set of text:

   Given that the ITR/PTR maintains a cache of EID-to-RLOC mappings,
   and that undersized caches could cause excessive control traffic,
   implementations MUST have some form of cache management in place.
   The specific management mechanisms are beyond the scope of this
   specification.

Regards,

Eliot

---

From: "lisp issue tracker" <[email-masked]>
Date: Wed, 30 Mar 2011 14:28:34 -0000

Comment(by yakov@…):

Ticket URL: <http://trac.tools.ietf.org/wg/lisp/trac/ticket/46#comment:7>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: Yakov Rekhter <[email-masked]>
Date: Wed, 30 Mar 2011 07:51:22 -0700

Eliot,

>    The specific management mechanisms are beyond the scope of this

The text you proposed above is insufficient as (a) it failed to
mention that undersized caches could lead to cache thrashing,
(b) cache thrashing, in addition to excessive control traffic, 
could also result in dropping data (thus negatively affecting
connectivity), and (c) the detrimental effects of excessive 
control traffic due to thrashing could spread beyond the ITR/PTR
that experiences thrashing.

Moreover, saying that an implementation must has "some form
of cache management in place" is insufficinet, as what is needed
is not just "some form" of cache management, but a mechanism
that would allow to suppress thrashing.

With all this in mind I would propose to augment the text you
proposed above with the missing points. Here is the revised text:

    Given that the ITR/PTR maintains a cache of EID-to-RLOC mappings,
    undersized caches could cause cache thrasing. Cache thrasing
    could result in the ITR/PTR dropping data, thus negatively
    affecting connectivity for all the hosts that communicate through
    this ITR/PTR. Moreover, cache thrasing could cause excessive
    control traffic, which could spread the detrimental effects of
    thrasing beyond the ITR/PTR that experiences the thrasing.
    Therefore, an implementation MUST have some form of cache
    management in place that would provide suppression of cache
    thrasing. The specific management mechanisms are beyond the 
    scope of this specification. Experimentation and deployment 
    experience will be used to determine which cache management 
    strategies work best.

If folks think that "MUST" in the above should be replaced with
"SHOULD" or "RECOMMENDED", it would be fine with me.

Yakov.

---

From: Eliot Lear <[email-masked]>
Date: Wed, 30 Mar 2011 18:02:38 +0200

Hi Yakov,

> mention that undersized caches could lead to cache thrashing,
Rather than use the term "cache thrashing", I chose instead to describe
the effects of undersized caches, which is another way of saying...
cache thrashing.  And it's a bit more descriptive.  I would also argue
that it is important to be concise.
> connectivity),
I think the above text captures this as well.
>  and (c) the detrimental effects of excessive 
Control traffic has to go somewhere, right?

> that would allow to suppress thrashing.
Fair enough. 

How about the following then:

   Given that the ITR/PTR maintains a cache of EID-to-RLOC mappings,
   and that undersized caches could cause excessive control traffic,
   implementations MUST have some form of cache management in place
   that prevents excessive network control traffic.  The specific
   management mechanisms are beyond the scope of this specification.

This also keeps things concise.  I also understand that others may be
uncomfortable about a normative MUST.  I understand those concerns and
have thrashed (cough) both ways about that myself.

Eliot