Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01

From: Luigi Iannone <[email-masked]>
Date: Wed, 1 Apr 2015 15:40:06 +0200

Hi Ron,

> On 31 Mar 2015, at 19:48, Ronald Bonica <[email-masked]> wrote:
> 
> Damien,
> 
> In his email below, Joel asks:
> 
>>>> if we modified the section to say that we do not know
>>>> what the impact on cache size and control overhead will be, as the
>>>> studies that have been made have been disputed as to their relevance
>>>> to the core Internet case, would the document still meet the IESG
>>>> requirements for evaluating the impact
> 
> I support Joel's request, so long as the disclaimer is complete.

Agreed that we need to clarify (via a disclaimer) what are the assumptions of the studies, and that outsides these assumptions we have no information.

> If cache size and control overhead have impact, they must have impact upon something. Do we know what they will impact? If so, tell us. If not, tell us that.
> 

Let me try to understand here. What you are suggesting is that any discussion on the scalability of cache and control overhead should be dropped (they are in the papers anyway), and only the aspects that have an impact (and on what they have an impact) should be maintained.

Is my reading correct?

BTW, Deborah was also suggesting to simplify some sections which are cluttered with to much numbers. This seems to me inline with your suggestion (if I got it correctly).

ciao

Luigi

>                                                                                                                           Ron
> 
>> -----Original Message-----
>> From: Damien Saucez [mailto:[email-masked]]
>> Sent: Monday, March 30, 2015 7:19 PM
>> To: Ronald Bonica
>> Cc: Joel Halpern; Brian Haberman; BRUNGARD, DEBORAH A (ATTLABS); LISP
>> mailing list list
>> Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01
>> 
>> Ron,
>> 
>> As one of the authors I can say I am not frustrated :-)
>> 
>> We are looking on how to address in the best way the comments of this
>> thread.
>> 
>> Just that it is unrealistic to hope a new full study on the cache size from
>> research partners as such a study takes a lot of time and resources (to
>> produce the experimentation, then to get reviewed in a conference or
>> journal and finally get published) and would not change any conclusion with
>> regards to the analytical studies reference in the draft already and that draw
>> general conclusions.
>> 
>> The best solution could be to ask your customers to provide me the
>> necessary information so that I could evaluate the impact of LISP for their
>> needs. Without that, I am afraid that the only thing that we can reasonably
>> provide is theoretical/analytical studies.
>> 
>> The disclaimer you propose to add is just incorrect. It is not true that we
>> don't know the impact of cache size. Actually, in the draft, we already
>> reference the analytical study [CCD12] that demonstrates analytically that it is
>> possible to link cache size, traffic pattern, and miss rate.
>> 
>> Here is the paragraph present in the draft:
>> 
>> [CCD12]  generalizes the caching discussion and proposes an analytic
>>   model for the EID-to-RLOC cache size when prefix-level traffic has a
>>   stationary generating process.  The model shows that miss rate can be
>>   accurately predicted from the EID-to-RLOC cache size and a small set
>>   of easily measurable traffic parameters, meaning that operators can
>>   provision the EID-to-RLOC cache of their ITRs according to the miss
>>   rate they want to achieve for their given traffic.
>> 
>> That is clear enough for me and unless someone can prove the model wrong
>> I am perfectly fine with this observation that is supported by empirical data.
>> 
>> Cheers,
>> 
>> Damien Saucez
>> 
>> On 30 Mar 2015, at 17:17, Ronald Bonica <[email-masked]> wrote:
>> 
>>> Brian, Deborah,
>>> 
>>> I realize that the authors are frustrated. Maybe we can run with Joel's
>> proposal if we make the disclaimer complete.
>>> 
>>> Shouldn't the disclaimer read something like, "We do not know the impact
>> of cache size and control overhead on {x, y, z}", where x, y and z might be:
>>> 
>>> - LISP scaling
>>> - LISP security
>>> - LISP resiliency
>>> - other ???
>>> 
>>> Given that, might we draw some conclusions regarding LISP's applicability?
>>> 
>>>                           Ron
>>> 
>>>> -----Original Message-----
>>>> From: lisp [mailto:[email-masked]] On Behalf Of Joel M.
>>>> Halpern
>>>> Sent: Sunday, March 29, 2015 9:55 PM
>>>> To: Brian Haberman; BRUNGARD, DEBORAH A (ATTLABS)
>>>> Cc: LISP mailing list list
>>>> Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01
>>>> 
>>>> Brian, Deborah, if we modified the section to say that we do not know
>>>> what the impact on cache size and control overhead will be, as the
>>>> studies that have been made have been disputed as to their relevance
>>>> to the core Internet case, would the document still meet the IESG
>>>> requirements for evaluating the impact.  I don't want to ask the
>>>> authors if they can live with a certain change if that change will
>>>> cause other necessary reviewers to complain.
>>>> 
>>>> I do not see it as sensible to hold up the publication of this and
>>>> the other LISP work while researchers go off to see if they can calculate
>> better results.
>>>> Particularly not when publishing this document is required to do other
>> work.
>>>> 
>>>> Yours,
>>>> Joel
>>>> 
>>>> On 3/29/15 9:50 PM, Ross Callon wrote:
>>>>> I suppose that there are two options:
>>>>> 
>>>>> 1. Admit that we have no clue what the cache size or control
>>>>> overhead will be.
>>>>> 
>>>>> 2. Repeat the cited studies, but with a pessimistic (worse case)
>>>>> rather than optimistic (better than best case) assumption about
>>>>> cache granularity.
>>>>> 
>>>>> The second option would allow us to actually have some idea what
>>>>> would happen if LISP were deployed on an Internet-wide scale, but
>>>>> would of course take more time and more work.
>>>>> 
>>>>> Ross
>>>>> 
>>>>> PS: I will be offline at meetings all of this week, so I might be a
>>>>> bit slower to respond for the next few days.
>>>>> 
>>>>> -----Original Message----- From: Joel M. Halpern
>>>>> [mailto:[email-masked]] Sent: Sunday, March 29, 2015 9:36 PM
>> To:
>>>>> Ross Callon; Luigi Iannone; LISP mailing list list Cc:
>>>>> [email-masked] Subject: Re: [lisp] WG Last
>>>>> Call
>>>>> draft-ietf-lisp-impact-01
>>>>> 
>>>>> Putting aside the TBD (which of course needs to be fixed),  I have
>>>>> trouble figuring out what you want us to say about the main issue in
>>>>> your review.  On the one hand, this is the very issue that we have
>>>>> been asked to comment on, and on the other hand you say that we
>>>>> don't know. What do you think it is reasoanble to say?
>>>>> 
>>>>> Yours, Joel
>>>>> 
>>>>> On 3/29/15 9:03 PM, Ross Callon wrote:
>>>>>> Generally I think that this document needs more work before it will
>>>>>> be ready to submit for publication. Some comments on
>>>>>> draft-ietf-lisp-impact-01:
>>>>>> 
>>>>>> First of all, I assume that the TBD at the end of section 3 will be
>>>>>> fixed. This reads:
>>>>>> 
>>>>>> TBD: add a paragraph to explain the operational difference while
>>>>>> 
>>>>>> dealing with a pull model instead of a push.
>>>>>> 
>>>>>> Also in section 3, the third paragraph begins:
>>>>>> 
>>>>>> In addition, Iannone and Bonaventure [IB07] show that the number of
>>>>>> 
>>>>>> mapping entries that must be handled by an ITR of a campus network
>>>>>> 
>>>>>> with 10,000 users is limited to few tens of thousands, and does not
>>>>>> 
>>>>>> represent more than 3 to 4 Megabytes of memory.
>>>>>> 
>>>>>> Reference [IB07] is of course:
>>>>>> 
>>>>>> Iannone, L. and O. Bonaventure, "On the cost of caching locator/id
>>>>>> mappings", In
>>>>>> 
>>>>>> Proc. ACM CoNEXT 2007, December 2007.
>>>>>> 
>>>>>> This paper states:
>>>>>> 
>>>>>> In our analysis, we assume that the granularity of the
>>>>>> 
>>>>>> EID-to-RLOC mapping is the prefix blocks assigned by
>>>>>> 
>>>>>> RIRs. We call it /BGP granularity. In particular, we
>>>>>> 
>>>>>> used the list of prefixes made available by the iPlane
>>>>>> 
>>>>>> Project [15], containing around 240,000 entries. Using
>>>>>> 
>>>>>> /BGP granularity means that each EID is first mapped
>>>>>> 
>>>>>> on a /BGP prefix. The cache will thus contain /BGP
>>>>>> 
>>>>>> to RLOC mappings.2 This is a natural choice, since
>>>>>> 
>>>>>> routing locators are supposed to be border routers.
>>>>>> 
>>>>>> The authors should be aware that there is some aggregation /
>>>>>> summarization being done in the operation of BGP routing, and that
>>>>>> the granularity of routes which appear in the default-free BGP
>>>>>> routing tables is fundamentally different from the granularity of
>>>>>> enterprise network / ISP boundaries across which traffic is
>>>>>> exchanged.
>>>>>> 
>>>>>> The same paragraph cites Kim et al.  [KIF11], which is Kim, J.,
>>>>>> Iannone, L., and A. Feldmann, "Deep dive into the lisp cache and
>>>>>> what isps should know about it", In Proc.  IFIP Networking 2011, May
>> 2011.
>>>>>> From this document:
>>>>>> 
>>>>>> In addition, we use a local BGP prefixes
>>>>>> 
>>>>>> database, fed with the list of BGP prefixes published by the iPlane
>>>>>> Project [17].
>>>>>> 
>>>>>> The database is used to group EID-to-RLOCs mappings with the
>>>>>> granularity of
>>>>>> 
>>>>>> existing BGP prefixes, because, as for today, there is no
>>>>>> sufficient information
>>>>>> 
>>>>>> to predict what will be the granularity of mappings in a
>>>>>> LISP-enabled Internet.
>>>>>> 
>>>>>> I agree that "there is not sufficient information to predict what
>>>>>> will be the granularity of mappings in a LISP-enabled Internet".
>>>>>> However, not knowing what the mapping granularity will be does not
>>>>>> justify using an extremely optimistic guess, and then acting as if
>>>>>> the results are meaningful. These assumptions are clearly off by
>>>>>> some number of orders of magnitude, but how many orders of
>>>>>> magnitude is unknown. We will note that the current internet
>>>>>> default-free routing table includes a few hundred thousand entries
>>>>>> (roughly twice the
>>>>>> 240,000 entries that existed when this study was done).
>>>>>> 
>>>>>> For example, we might assume that the intended global deployment
>>>>>> model involves xTRs at the boundary between enterprise networks
>> and
>>>>>> service providers, and might note that there are several million
>>>>>> companies in the USA alone (most of these are relatively small
>>>>>> companies, of course). Thus there may be very roughly on the order
>>>>>> of a hundred million or so companies worldwide. If each one had a
>>>>>> separate entry in the mapping table, then the number of entries
>>>>>> will be nearly 1,000 times larger than BGP-prefix granularity.
>>>>>> 
>>>>>> Section 4 mentions as one possible use of LISP: "enable mobility of
>>>>>> subscriber end points". If individual end points are advertised
>>>>>> into LISP, then the granularity of the mapping table may be on the
>>>>>> order of individual systems. In this case the number of mapping
>>>>>> table entries that could exist globally might be on the same order
>>>>>> of magnitude as the number of people in the world, or very roughly
>>>>>> 7 Billion entries. This would suggest that the mapping table might
>>>>>> be roughly 30,000 times finer grained than was assumed in the
>>>>>> referenced studies.
>>>>>> 
>>>>>> I don't see how we can accurately predict the control plane load of
>>>>>> LISP without some sense for what the granularity of the mapping
>>>>>> table will be. It should however be possible to bound the control
>>>>>> plane load. The referenced studies give a lower bound on possible
>>>>>> control plane load (it won't be any less), but give neither an
>>>>>> accurate measurement nor an upper bound on the potential control
>>>>>> plane load. I don't think that the document can claim to explain
>>>>>> the impact of LISP without there being an attempt to measure an
>>>>>> upper bound on the control plane load.
>>>>>> 
>>>>>> Finally, perhaps I missed it but I didn't see any discussion of the
>>>>>> volume of overhead related to OAM traffic used for liveness
>>>>>> detection (the need for ITR's to determine the reachability of ETR's).
>>>>>> 
>>>>>> Thanks, Ross
>>>>>> 
>>>>>> *From:*lisp [mailto:[email-masked]] *On Behalf Of *Luigi
>>>>>> Iannone *Sent:* Monday, March 09, 2015 10:22 AM *To:* LISP mailing
>>>>>> list list *Cc:* [email-masked] *Subject:*
>>>>>> [lisp] WG Last Call draft-ietf-lisp-impact-01
>>>>>> 
>>>>>> Hi All,
>>>>>> 
>>>>>> the authors of the LISP Impact document
>>>>>> [https://tools.ietf.org/html/draft-ietf-lisp-impact-01] requested
>>>>>> the Work Group Last Call.
>>>>>> 
>>>>>> This email starts a WG Last Call, to end March 30th, 2015.
>>>>>> 
>>>>>> Because usually the pre-meeting period is already overloaded, the
>>>>>> LC duration is set to three weeks.
>>>>>> 
>>>>>> Please review this updated WG document and let the WG know if you
>>>>>> agree that it is ready for handing to the AD.
>>>>>> 
>>>>>> If you have objections, please state your reasons why, and explain
>>>>>> what it would take to address your concerns.
>>>>>> 
>>>>>> Any raised issue will be discussed during the WG meeting in Dallas.
>>>>>> 
>>>>>> Thanks
>>>>>> 
>>>>>> 
>>>>>> Luigi & Joel
>>>>>> 
>>>>>> 
>>>>>> 
>>>>>> _______________________________________________ lisp
>> mailing
>>>> list
>>>>>> [email-masked] https://www.ietf.org/mailman/listinfo/lisp
>>>>>> 
>>>>> 
>>>> 
>>>> _______________________________________________
>>>> lisp mailing list
>>>> [email-masked]
>>>> https://www.ietf.org/mailman/listinfo/lisp
>>> 
>>> _______________________________________________
>>> lisp mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/lisp
> 
> _______________________________________________
> lisp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lisp

---

From: Damien Saucez <[email-masked]>
Date: Thu, 2 Apr 2015 00:01:28 +0200

On 31 Mar 2015, at 19:48, Ronald Bonica <[email-masked]> wrote:

> I support Joel's request, so long as the disclaimer is complete. If cache size and control overhead have impact, they must have impact upon something.

I don’t see the point of an explicit disclaimer.  By definition when we give
hypothesis it means that results are limited to these hypotheses.  If we have
to put an explicit disclaimer in this document, it means that ALL IETF
documents based on experimentation/implementation should have such disclaimer,
but also any research document!

For me page 4 is explicit enough with the assumptions and I don’t see the point
to add a disclaimer.

The assumptions in these studies are:

o  contiguous addresses tend to be used similarly and EID prefixes
  follow the current BGP prefixes decomposition;

o  EIDs are used only at the stub ASes, not in the transit ASes;

o  the RLOCs of an EID prefix are deployed at the edge between the
  stubs owning the EID prefix and the providers, allocating the
  RLOCs in a Provider Aggregetable (PA) mode.

> Do we know what they will impact? If so, tell us. If not, tell us that.

This is the exact reason why [CCD12] is referenced. It shows that the impact
is on miss rate (see page 5). Also as it is a public analytical study, people can
adapt it relatively easily (as opposed to a traffic trace that is not available to
the community).

Damien Saucez

---

From: Damien Saucez <[email-masked]>
Date: Thu, 2 Apr 2015 09:15:34 +0200

On 30 Mar 2015, at 03:50, Ross Callon <[email-masked]> wrote:

> 1. Admit that we have no clue what the cache size or control overhead will be.
> 

See [CCD12], this document provides a generic model that works for
any desegregation assumption as long as the map-cache is implemented
with LRU.

Damien Saucez

> 2. Repeat the cited studies, but with a pessimistic (worse case) rather than optimistic (better than best case) assumption about cache granularity. 
> 
> The second option would allow us to actually have some idea what would happen if LISP were deployed on an Internet-wide scale, but would of course take more time and more work. 
> 
> Ross
> 
> PS: I will be offline at meetings all of this week, so I might be a bit slower to respond for the next few days.  
> 
> From: Joel M. Halpern [mailto:[email-masked]] 
> Sent: Sunday, March 29, 2015 9:36 PM
> To: Ross Callon; Luigi Iannone; LISP mailing list list
> Cc: [email-masked]
> your review.  On the one hand, this is the very issue that we have been 
> asked to comment on, and on the other hand you say that we don't know. 
> What do you think it is reasoanble to say?
> 
> Yours,
> Joel
> 
>> Generally I think that this document needs more work before it will be
>> ready to submit for publication. Some comments on draft-ietf-lisp-impact-01:
>> 
>>             Iannone, L. and O. Bonaventure, "On the cost of caching
>> locator/id mappings", In
>> 
>> summarization being done in the operation of BGP routing, and that the
>> granularity of routes which appear in the default-free BGP routing
>> tables is fundamentally different from the granularity of enterprise
>> network / ISP boundaries across which traffic is exchanged.
>> 
>> The same paragraph cites Kim et al.  [KIF11], which is Kim, J., Iannone,
>> L., and A. Feldmann, "Deep dive into the lisp cache and what isps should
>> know about it", In Proc.  IFIP Networking 2011, May 2011.  From this
>> document:
>> 
>> I agree that "there is not sufficient information to predict what will
>> be the granularity of mappings in a LISP-enabled Internet". However, not
>> knowing what the mapping granularity will be does not justify using an
>> extremely optimistic guess, and then acting as if the results are
>> meaningful. These assumptions are clearly off by some number of orders
>> of magnitude, but how many orders of magnitude is unknown. We will note
>> that the current internet default-free routing table includes a few
>> hundred thousand entries (roughly twice the 240,000 entries that existed
>> when this study was done).
>> 
>> For example, we might assume that the intended global deployment model
>> involves xTRs at the boundary between enterprise networks and service
>> providers, and might note that there are several million companies in
>> the USA alone (most of these are relatively small companies, of course).
>> Thus there may be very roughly on the order of a hundred million or so
>> companies worldwide. If each one had a separate entry in the mapping
>> table, then the number of entries will be nearly 1,000 times larger than
>> BGP-prefix granularity.
>> 
>> subscriber end points". If individual end points are advertised into
>> LISP, then the granularity of the mapping table may be on the order of
>> individual systems. In this case the number of mapping table entries
>> that could exist globally might be on the same order of magnitude as the
>> number of people in the world, or very roughly 7 Billion entries. This
>> would suggest that the mapping table might be roughly 30,000 times finer
>> grained than was assumed in the referenced studies.
>> 
>> I don't see how we can accurately predict the control plane load of LISP
>> without some sense for what the granularity of the mapping table will
>> be. It should however be possible to bound the control plane load. The
>> referenced studies give a lower bound on possible control plane load (it
>> won't be any less), but give neither an accurate measurement nor an
>> upper bound on the potential control plane load. I don't think that the
>> document can claim to explain the impact of LISP without there being an
>> attempt to measure an upper bound on the control plane load.
>> 
>> volume of overhead related to OAM traffic used for liveness detection
>> (the need for ITR's to determine the reachability of ETR's).
>> 
>> Thanks, Ross
>> 
>> *From:*lisp [mailto:[email-masked]] *On Behalf Of *Luigi Iannone
>> *Sent:* Monday, March 09, 2015 10:22 AM
>> *To:* LISP mailing list list
>> *Cc:* [email-masked]
>> *Subject:* [lisp] WG Last Call draft-ietf-lisp-impact-01
>> 
>> Hi All,
>> 
>> [https://tools.ietf.org/html/draft-ietf-lisp-impact-01] requested the
>> Work Group Last Call.
>> 
>> Because usually the pre-meeting period is already overloaded, the LC
>> duration is set to three weeks.
>> 
>> Please review this updated WG document and let the WG know if you agree
>> that it is ready for handing to the AD.
>> 
>> If you have objections, please state your reasons why, and explain what
>> it would take to address your concerns.
>>

---

From: Ross Callon <[email-masked]>
Date: Thu, 2 Apr 2015 14:57:58 +0000

> any desegregation assumption as long as the map-cache is implemented

I am at meetings all of this week (and of course last week was pretty busy for most of us). I have however pulled up a copy of this paper, and will read it through as soon as I get a chance. I will try to respond the first half of next week. 

Thanks, Ross

---

From: Damien Saucez <[email-masked]>
Date: Thu, 2 Apr 2015 17:03:54 +0200

> I am at meetings all of this week (and of course last week was pretty busy for most of us). I have however pulled up a copy of this paper, and will read it through as soon as I get a chance. I will…
great, thanks. 

Damien Saucez

---

From: Ronald Bonica <[email-masked]>
Date: Mon, 6 Apr 2015 10:53:58 +0000

Hi Luigi,

I am not suggesting that discussion of cache scaling and control overhead be dropped. This discussion is very helpful to the reader.

I suggest only that we run with Joel's proposal to add a disclaimer. The disclaimer should say something like:

>>>>>> we do not know what the
> >>>> impact on cache size and control overhead will be, as the studies
> >>>> that have been made have been disputed as to their relevance to the
> >>>> core Internet case

Furthermore, we should extend the disclaimer to say:

"We do not know what the  impact of cache size and control overhead will be upon {x, y, and z}".

                                                                                                   Ron

> From: Luigi Iannone [mailto:[email-masked]]
> Sent: Wednesday, April 01, 2015 9:40 AM
> To: Ronald Bonica
> Cc: Damien Saucez; LISP mailing list list; BRUNGARD, DEBORAH A (ATTLABS)
> >>>> if we modified the section to say that we do not know what the
> >>>> impact on cache size and control overhead will be, as the studies
> >>>> that have been made have been disputed as to their relevance to the
> >>>> core Internet case, would the document still meet the IESG
> Agreed that we need to clarify (via a disclaimer) what are the assumptions of
> the studies, and that outsides these assumptions we have no information.
> 
> 
> > If cache size and control overhead have impact, they must have impact
> upon something. Do we know what they will impact? If so, tell us. If not, tell
> us that.
> >
> 
> Let me try to understand here. What you are suggesting is that any
> discussion on the scalability of cache and control overhead should be
> dropped (they are in the papers anyway), and only the aspects that have an
> impact (and on what they have an impact) should be maintained.
> 
> Is my reading correct?
> 
> BTW, Deborah was also suggesting to simplify some sections which are
> cluttered with to much numbers. This seems to me inline with your
> suggestion (if I got it correctly).
> 
> ciao
> 
> Luigi
> 
> 
> >
> > Ron
> >
> >> Just that it is unrealistic to hope a new full study on the cache
> >> size from research partners as such a study takes a lot of time and
> >> resources (to produce the experimentation, then to get reviewed in a
> >> conference or journal and finally get published) and would not change
> >> any conclusion with regards to the analytical studies reference in
> >> the draft already and that draw general conclusions.
> >>
> >> necessary information so that I could evaluate the impact of LISP for
> >> their needs. Without that, I am afraid that the only thing that we
> >> can reasonably provide is theoretical/analytical studies.
> >>
> >> The disclaimer you propose to add is just incorrect. It is not true
> >> that we don't know the impact of cache size. Actually, in the draft,
> >> we already reference the analytical study [CCD12] that demonstrates
> >> analytically that it is possible to link cache size, traffic pattern, and miss
> rate.
> >>
> >> That is clear enough for me and unless someone can prove the model
> >> wrong I am perfectly fine with this observation that is supported by
> empirical data.
> >>
> >> Cheers,
> >>
> >> Damien Saucez
> >>
> >>>> Brian, Deborah, if we modified the section to say that we do not
> >>>> know what the impact on cache size and control overhead will be, as
> >>>> the studies that have been made have been disputed as to their
> >>>> relevance to the core Internet case, would the document still meet
> >>>> the IESG requirements for evaluating the impact.  I don't want to
> >>>> ask the authors if they can live with a certain change if that
> >>>> change will cause other necessary reviewers to complain.
> >>>>
> >>>>> PS: I will be offline at meetings all of this week, so I might be
> >>>>> a bit slower to respond for the next few days.
> >>>>>
> >>>>> trouble figuring out what you want us to say about the main issue
> >>>>> in your review.  On the one hand, this is the very issue that we
> >>>>> have been asked to comment on, and on the other hand you say that
> >>>>> we don't know. What do you think it is reasoanble to say?
> >>>>>
> >>>>> Yours, Joel
> >>>>>
> >>>>>> Generally I think that this document needs more work before it
> >>>>>> will be ready to submit for publication. Some comments on
> >>>>>> First of all, I assume that the TBD at the end of section 3 will
> >>>>>> be fixed. This reads:
> >>>>>>
> >>>>>> summarization being done in the operation of BGP routing, and
> >>>>>> that the granularity of routes which appear in the default-free
> >>>>>> BGP routing tables is fundamentally different from the
> >>>>>> granularity of enterprise network / ISP boundaries across which
> >>>>>> traffic is exchanged.
> >>>>>>
> >>>>>> database, fed with the list of BGP prefixes published by the
> >>>>>> iPlane Project [17].
> >>>>>>
> >>>>>> However, not knowing what the mapping granularity will be does
> >>>>>> not justify using an extremely optimistic guess, and then acting
> >>>>>> as if the results are meaningful. These assumptions are clearly
> >>>>>> off by some number of orders of magnitude, but how many orders
> of
> >>>>>> default-free routing table includes a few hundred thousand
> >>>>>> entries (roughly twice the
> >>>>>> companies, of course). Thus there may be very roughly on the
> >>>>>> order of a hundred million or so companies worldwide. If each one
> >>>>>> had a separate entry in the mapping table, then the number of
> >>>>>> entries will be nearly 1,000 times larger than BGP-prefix granularity.
> >>>>>>
> >>>>>> Section 4 mentions as one possible use of LISP: "enable mobility
> >>>>>> of subscriber end points". If individual end points are
> >>>>>> advertised into LISP, then the granularity of the mapping table
> >>>>>> may be on the order of individual systems. In this case the
> >>>>>> number of mapping table entries that could exist globally might
> >>>>>> be on the same order of magnitude as the number of people in the
> >>>>>> world, or very roughly
> >>>>>> 7 Billion entries. This would suggest that the mapping table
> >>>>>> might be roughly 30,000 times finer grained than was assumed in
> >>>>>> the referenced studies.
> >>>>>>
> >>>>>> I don't see how we can accurately predict the control plane load
> >>>>>> of LISP without some sense for what the granularity of the
> >>>>>> mapping table will be. It should however be possible to bound the
> >>>>>> control plane load. The referenced studies give a lower bound on
> >>>>>> possible control plane load (it won't be any less), but give
> >>>>>> neither an accurate measurement nor an upper bound on the
> >>>>>> potential control plane load. I don't think that the document can
> >>>>>> claim to explain the impact of LISP without there being an
> >>>>>> Finally, perhaps I missed it but I didn't see any discussion of
> >>>>>> the volume of overhead related to OAM traffic used for liveness
> >>>>>> Iannone *Sent:* Monday, March 09, 2015 10:22 AM *To:* LISP
> >>>>>> mailing list list *Cc:* [email-masked]
> >>>>>> If you have objections, please state your reasons why, and
> >>>>>> explain what it would take to address your concerns.
> >>>>>>

---

From: Luigi Iannone <[email-masked]>
Date: Wed, 8 Apr 2015 22:04:31 +0200

HI Ron,

> On 06 Apr 2015, at 12:53, Ronald Bonica <[email-masked]> wrote:
> 
> Hi Luigi,
> 

Thanks. We will try to streamline it a little bit, as suggested by Deborah.

> I suggest only that we run with Joel's proposal to add a disclaimer.

Agreed.
The final form of the disclaimer will depend on the updated content of the document (see previous point).

ciao

Luigi

> The disclaimer should say something like:
> 
> 
>>>>>>> we do not know what the

---

From: Ross Callon <[email-masked]>
Date: Thu, 9 Apr 2015 00:29:21 +0000

> any desegregation assumption as long as the map-cache is implemented

[CCD12] is of course: 

   Coras, F., Cabellos-Aparicio, A., and J. Domingo-Pascual, "An Analytical Model
   for the LISP Cache Size", In Proc. IFIP Networking 2012, May 2012.

I just finished reading this through. To me the analytic model looks mostly fine, except for one issue mentioned below, but the results (in terms of how large a cache is needed) depends upon the assumption about the granularity of the cache. 

Near the end of section 2 of this paper (the last paragraph before section 3) includes the text: 
   
   "... One can easily observe that the map-cache is most efficient in 
   situations when destination EIDs present high temporal and/or spatial 
   locality and that its size depends upon the diversity of the visited 
   destinations. As a result, a cache's performance depends entirely on 
   its provisioned size and on traffic characteristics."

Of course the desired size of the cache depends upon the likelihood, for a given cache size, that the next EID that comes along will match an entry which is already in the cache, which depends on the size of the entries in the cache. [As one absurd extreme example, if you had a single default route in the cache, every EID would match it and the cache could be of size 1. A less absurd but still slightly extreme example, if you could get away with nothing finer than a /8 in the cache, then 256 entries would be the largest possible cache size.]  Thus the text is true for any given granularity of entries in the cache. The paper might more accurately have said "As a result, a cache's performance depends entirely on its provisioned size, on traffic characteristics, and on the granularity of cache entries". 

In section 4.1, the second paragraph begins: 

   Both for the evaluation of the working set in section 3.3 and for
   the cache performance evaluation to be presented in section 4.3,
   IP addresses had to be mapped to their corresponding prefixes. We
   considered EID-prefixes to be of BGP-prefix granularity". 

Of course some assumption of the granularity of prefixes is needed. It is clear that what we assume for the granularity affects the result. I don't agree that BGP-prefix granularity is the right assumption. 

The other issue that I found with the paper refers to a later sentence in the same second paragraph of section 4.1:

   The only preprocessing we performed was to filter out more specific 
   prefixes. Generally such prefixes are used for traffic engineering 
   purposes. However, the LISP protocol provides mechanisms for a more
   efficient management of these functions that do not require EID-prefix
   de-aggregation. 

My understanding of this is that what some service providers do today is to announce some more specific prefixes (that match a PA prefix assigned to them) at some interconnection points and some different more specific prefixes at other interconnection points in order to draw in traffic where they want to draw it in. If with LISP you were to map all of these prefixes in one mapping table entry then you would be mapping them all to the same RLOC (or set of RLOCs). Ignoring the issue that any one large ISP could have thousands of PE routers (with thousands more CE routers attached to them), if all of these were mapped to one RLOC then you would not be able to do traffic engineering on a finer scale (unless you were to do deep packet inspection, which I believe is not the plan). Thus I understand how LISP might potentially prevent these more specific prefixes from being advertised into the global routing table, but they will still need to be in the mapping table.

Thanks, Ross

-----Original Message-----
From: Damien Saucez [mailto:[email-masked]] 
Sent: Thursday, April 02, 2015 3:16 AM
To: Ross Callon
Cc: Joel Halpern; Luigi Iannone; LISP mailing list list; [email-masked]
Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01

Damien Saucez

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Thu, 9 Apr 2015 17:51:36 +0000

On Apr 8, 2015, at 5:29 PM, Ross Callon <[email-masked]> wrote:

> My understanding of this is that what some service providers do today is to announce some more specific prefixes (that match a PA prefix assigned to them) at some interconnection points and some different more specific prefixes at other interconnection points in order to draw in traffic where they want to draw it in. If with LISP you were to map all of these prefixes in one mapping table entry then you would be mapping them all to the same RLOC (or set of RLOCs). 

This is not correct, there is no requirement for an ETR to provide the same answer to one requesting ITR as it does another.  Quite the opposite, replies can be customized depending on many possible variables.

-Darrel

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 9 Apr 2015 11:16:28 -0700

And to add to what Darrel said, the policy control can be provided at the LISP site or by the MSP (Mapping Service Provider). It depends who is jockeying for control or who wants features out-sourced.

Dino

> On Apr 9, 2015, at 10:51 AM, Darrel Lewis (darlewis) <[email-masked]> wrote:
> 
>

---

From: Ross Callon <[email-masked]>
Date: Fri, 10 Apr 2015 03:29:00 +0000

I understand that the ETR could send a different response to different ITRs. 

However, there is a reason that some more specific prefixes are advertised (in addition to a covering less specific prefix). One reason is that some service providers want incoming traffic delivered to them via different interconnects based on the destination. Even if you are doing traffic engineering with LISP, then this reason doesn't go away, and isn't solved by sending only the less specific prefix in the map reply. Of course there are other reasons to advertise more specific prefixes, and on the most part these don't go away either. I therefore feel that it was an error for the study discussed in [CCD12] to "... filter out more specific prefixes". 

Perhaps a more serious problem is that "BGP-prefix granularity" is not likely to be even remotely close to correct, with or without filtering out more specifics.  

Ross

-----Original Message-----
From: Dino Farinacci [mailto:[email-masked]] 
Sent: Thursday, April 09, 2015 2:16 PM
To: Darrel Lewis
Cc: Ross Callon; LISP mailing list list; [email-masked]
Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 9 Apr 2015 23:15:47 -0700

> However, there is a reason that some more specific prefixes are advertised (in addition to a covering less specific prefix). One reason is that some service providers want incoming traffic delivered to them via different interconnects based on the destination. Even if you are doing traffic

Right but if you want that with LISP you can return a coarse prefix in a Map-Reply with different priority values to different ITRs. It doesn't require for more-specifics. 

> engineering with LISP, then this reason doesn't go away, and isn't solved by sending only the less specific prefix in the map reply. Of course there are other

Yes it is solved. With a push protocol to instruct traffic to come one way or the other is only done with multiple prefixes where with LISP it can be done with the same prefix but is tailored on a per source or request basis. 

> reasons to advertise more specific prefixes, and on the most part these don't go away either. I therefore feel that it was an error for the study discussed in [CCD12] to "... filter out more specific prefixes".

It doesn't follow at all to me. 

Dino

---

From: Ross Callon <[email-masked]>
Date: Mon, 13 Apr 2015 18:04:11 +0000

Dino, I am not sure that you read my earlier email quite the way that I meant to explain the issue. One reason for more specifics being advertised is that some ISPs don't want incoming traffic split by source, but rather by destination. Probably to agree on how this would work with LISP we need to sit down in person and discuss this with white boards and pictures. 

To me it seems like there are two ways forward here: One option is to go with what Joel suggested earlier, and add to the document something along the lines that the scaling numbers are disputed and we don't actually know how it scales. The other option would be for at least the two of us to sit down in person as soon as we get a chance (no later than Prague, hopefully earlier if either of us gets a trip to the other's neck of the woods). I don't currently have any trips planned to California, but could let you know if I do and try to plan to stay an extra day to go over this. 

Thanks, Ross

-----Original Message-----
From: Dino Farinacci [mailto:[email-masked]] 
Sent: Friday, April 10, 2015 2:16 AM
To: Ross Callon
Cc: Darrel Lewis; LISP mailing list list; [email-masked]
Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01

Dino

---

From: Florin Coras <[email-masked]>
Date: Mon, 13 Apr 2015 11:52:20 -0700

Hi Ross,

Apologies for the belated reply, it was a busy week. First of all, 
thanks for taking the time to read the paper and for the good comments. 
More inline.

On 4/8/15 5:29 PM, Ross Callon wrote:
> I just finished reading this through. To me the analytic model looks 
> mostly fine, except for one issue mentioned below, but the results (in 
> terms of how large a cache is needed) depends upon the assumption 
> about the granularity of the cache.

I'm pretty sure you mean the granularity of the entries cached (the 
width of the EID-prefixes). And this is indeed so because in light of 
the fixed size of the 32-bit (or 128-bit) address space, granularity 
controls the number of prefixes and thereby the number of destinations 
traffic could have. But note that the relevant metric for a cache is the 
number of destinations rather than the granularity.
> Of course the desired size of the cache depends upon the likelihood, 
> for a given cache size, that the next EID that comes along will match 
> an entry which is already in the cache, which depends on the size of 
> the entries in the cache. [As one absurd extreme example, if you had a 
> single default route in the cache, every EID would match it and the 
> cache could be of size 1. A less absurd but still slightly extreme 
> example, if you could get away with nothing finer than a /8 in the 
> cache, then 256 entries would be the largest possible cache size.]  
> Thus the text is true for any given granularity of entries in the 
> cache. The paper might more accurately have said "As a result, a 
> cache's performance depends entirely on its provisioned size, on 
> traffic characteristics, and on the granularity of cache entries".

There are two things mixed in here: i) the parameters influencing cache 
performance and ii) assumptions to practically evaluate a cache's 
performance.

One of the traffic's characteristics is the number of destinations it 
has. As explained before, when dealing with EID-prefix caches, 
granularity influences the cardinality of the set of destinations, so 
its effect is indirectly considered. Therefore, I believe, our statement 
is general enough.

Regarding the second point, when setting up an experiment to evaluate 
map-cache performance, one has to consider the granularity of 
EID-prefixes. As you've noted, we've used BGP-prefix granularity to fix 
the number of destinations in our experiments. Understandably, this is 
debatable, but more on it lower.
> Of course some assumption of the granularity of prefixes is needed. It 
> is clear that what we assume for the granularity affects the result. I 
> don't agree that BGP-prefix granularity is the right assumption.

I've gleaned from your previous emails that you believe aggregation of 
PA assignments hides the actual size of the EID-prefix namespace. I 
guess this is why you disagree with our assumption. The goal our 
experiments was to understand the performance of LISP map-caches if edge 
networks already owning their address space (PI address owners) were to 
switch to LISP. Speculating if and how PA owning edge networks are to 
switch to LISP was outside the scope.

However, an important thing to consider is that cache performance is not 
primarily driven by the number of destinations but by the their 
popularity distribution. To give an absurd example: even if there are 
billions of destinations in the mapping system, if a site's users only 
visit google and facebook, the site's map-cache will only need 2 
entries. In fact, we've showed in [1] that the cache model can be 
entirely determined from the popularity distribution. Thereby, to 
understand a site's map-cache asymptotic scalability it is enough to 
characterize the popularity distribution of the EID-prefixes visited.

So, how does the popularity distribution look like? Since we cannot 
compute the popularity of EID-prefixes without any assumptions on 
granularity, we can instead look at web traffic as a good approximation. 
This has been shown to be power law, often referred to as Zipf-like (see 
[2]), i.e, most of the traffic goes to a small set of destinations while 
the majority of destinations are sent few or no packets at all. Note 
though that we obtained a similar law for our traces when considering 
EID-prefixes to be of BGP-prefix granularity and this law has been shown 
to hold in many other fields (see [1] and the references therein).

All this means that cache miss rates decrease very fast with cache size 
(see eq. (11) in [1]), but the exact 'speed' will depend on the 
characteristics of each site. In the worst case, if for some strange 
reason the popularity distribution becomes flat (i.e, all EID-prefixes 
are equally popular) then the map-cache size will have to be 
proportional to the number of EID-prefixes to ensure a reasonably good 
hit-rate.

[1] F. Coras, J. Domingo, A. Cabellos. "On the scalability of LISP 
mappings caches". Technical Report. URL: 
http://personals.ac.upc.edu/fcoras/publications/2015-fcoras-scalability.pdf
[2] Breslau, Lee, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. 
"Web caching and Zipf-like distributions: Evidence and implications." 
INFOCOM, in Proceedings. IEEE, vol. 1, pp. 126-134, 1999.

>
> The other issue that I found with the paper refers to a later sentence 
> in the same second paragraph of section 4.1:
>
> My understanding of this is that what some service providers do today 
> is to announce some more specific prefixes (that match a PA prefix 
> assigned to them) at some interconnection points and some different 
> more specific prefixes at other interconnection points in order to 
> draw in traffic where they want to draw it in.

If the more specifics are meant only for steering the traffic, then LISP 
offers better mechanisms for ingress TE (with only one mapping) by means 
of RLOC priority and weights. If instead you are suggesting those more 
specifics are advertised per *individual client* (which you seem to do 
lower) then we're back at the point above. That is, we might be 
underestimating the size of the EID-prefix namespace. Out of curiosity, 
do you happen to know any reference suggesting this is the norm rather 
than the exception?

> If with LISP you were to map all of these prefixes in one mapping 
> table entry then you would be mapping them all to the same RLOC (or 
> set of RLOCs). Ignoring the issue that any one large ISP could have 
> thousands of PE routers (with thousands more CE routers attached to 
> them), if all of these were mapped to one RLOC then you would not be 
> able to do traffic engineering on a finer scale (unless you were to do 
> deep packet inspection, which I believe is not the plan). Thus I 
> understand how LISP might potentially prevent these more specific 
> prefixes from being advertised into the global routing table, but they 
> will still need to be in the mapping table.
>
Here you seem to assume that all of the ISP's PA clients will turn on 
LISP on their CPEs (I really hope you're right ;-) ). If that happens, 
yes, all their prefixes will need to be registered in the mapping 
system. But again, what matters is popularity, not the absolute number 
of EID-prefixes. That is, there's nothing saying that a site sending 
traffic to the PA prefix will have to store all of the ISP's clients 
prefixes. Most probably it will cache just one.

Also, there's an alternative here. The ISP could turn LISP on its 
upstream ASBRs and their customers, since they're PA, would be 
unaffected. In this case, any site communicating with the ISP's clients 
would need to store just one mapping and the ISP would take care of 
routing the decapsulated packets to their intended destination. This is 
somewhat similar, to Instagram and Netflix being EIDs in Amazon's 
datacenters.

Thanks,
Florin
>> rather than optimistic (better than best case) assumption about cache 
>> granularity.
>>
>>> Iannone,
>>> LISP

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 13 Apr 2015 12:58:03 -0700

> Dino, I am not sure that you read my earlier email quite the way that I meant to explain the issue. One 

Well I read the words you wrote.  ;-)

> reason for more specifics being advertised is that some ISPs don't want incoming traffic split by source, but rather by destination. Probably to agree on how this would work with LISP we need to sit down in person and discuss this with white boards and pictures. 

What ISPs want more than anything else is balanced load. And if they have to vary from that point, they go more granular. And that usually means by source or 5-tuple hashing in the data-plane.

> To me it seems like there are two ways forward here: One option is to go with what Joel suggested earlier, and add to the document something along the lines that the scaling numbers are disputed and we don't actually know how it scales. The other option would be for at least the two of us to sit down in 

I agree. 

We don’t know how ANYTHING scales until it gets there. Where “there” is some point. Is BGP scaling? So this will always come down to subjective opinion and perspective from different points of view.

> person as soon as we get a chance (no later than Prague, hopefully earlier if either of us gets a trip to the other's neck of the woods). I don't currently have any trips planned to California, but could let you know if I do and try to plan to stay an extra day to go over this. 

We should do that in any case, but we shouldn’t block or slow down the process. We can do this in Prague but go with Joel’s suggestion for now.

Dino

---

From: Ross Callon <[email-masked]>
Date: Mon, 13 Apr 2015 21:04:48 +0000

> ...We should do that in any case, but we shouldn’t block or slow down the
> process. We can do this in Prague but go with Joel’s suggestion for now.

Makes sense. I think that Florin's email hints at a very small edit to Joel's suggestion, which I will mention in reply to his email. 

Ross

-----Original Message-----
From: Dino Farinacci [mailto:[email-masked]] 
Sent: Monday, April 13, 2015 3:58 PM
To: Ross Callon
Cc: Darrel Lewis; LISP mailing list list; [email-masked]
Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01

I agree. 

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 13 Apr 2015 14:06:07 -0700

> Makes sense. I think that Florin's email hints at a very small edit to Joel's suggestion, which I will mention in reply to his email. 

Ack Ross. Thanks.

Dino

---

From: Ross Callon <[email-masked]>
Date: Mon, 13 Apr 2015 21:15:46 +0000

> width of the EID-prefixes).

Yes. I have been summarizing this using the term "granularity of the cache" or "cache granularity", but of course I mean the granularity / "width" of the entries which are maintained in the cache. 

> The goal our experiments was to understand the
> performance of LISP map-caches if edge 

Yes, I think that this text gets to the point of my biggest issue. I am concerned that people may miss this assumption in the study and think that it pertains to a potential wider deployment of LISP. 

Perhaps the note that we need in the impact document would include something like: "[CCD12] analyzes the performance of the LISP map cache if only the current edge networks already owning their address space (PI address owners) were to switch to LISP. It is not known what the performance implications would be if LISP were more widely deployed, or if the availability of LISP or other factors were to cause a significant increase in the number of PI addresses." 

Thanks, Ross

-----Original Message-----
From: Florin Coras [mailto:[email-masked]] 
Sent: Monday, April 13, 2015 2:52 PM
To: Ross Callon; Damien Saucez
Cc: Joel Halpern; Luigi Iannone; LISP mailing list list; [email-masked]
Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01

Hi Ross,

Thanks,
Florin

---

From: Florin Coras <[email-masked]>
Date: Mon, 13 Apr 2015 15:55:31 -0700

Ross,

As explained in my previous email, the model is general, only the 
experimental validation makes assumptions with regards to the size of 
the EID-prefix namespace. See [1], and in particular eq. 11, to see how 
cache performance scales.

Thanks,
Florin

---

From: Ross Callon <[email-masked]>
Date: Tue, 14 Apr 2015 22:40:31 +0000

Dino;

One point from your first email yesterday that I think might be worth making (although this might be partially OBE by more recent emails). 

> What ISPs want more than anything else is balanced load. And if they
> have to vary from that point, they go more granular. And that usually
> means by source or 5-tuple hashing in the data-plane.

I agree that a very common approach for balancing load involves hashing on the well known 5-tuple (source and destination IP addresses, etc...) to allow load splitting across multiple paths (plus techniques for setting up the multiple paths). This is fairly well known. However, this does not require announcing "more specific" addresses into BGP (nor into the LISP cache). As such it doesn't relate to the issue of whether or not the more specific addresses that are currently advertised into BGP will need to also correspond to separate entries in a LISP cache. 

The reason that I was mentioning the less common, but still sometimes used approach of announcing more specific addresses into BGP in order to have traffic arrive at your network "closer" to the ultimate destination, is specifically because this *is* a reason for announcing more specific addresses in to BGP. I have heard this approach referred to as "cold potato" routing (since it tries to get the previous network operator along a path to hold onto the packet longer). 

Nonetheless, this is probably more easily discussed with a white board in front of us (and perhaps also a beer ;-).  

Ross

-----Original Message-----
From: Dino Farinacci [mailto:[email-masked]] 
Sent: Monday, April 13, 2015 3:58 PM
To: Ross Callon
Cc: Darrel Lewis; LISP mailing list list; [email-masked]
Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01

I agree. 

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 14 Apr 2015 15:47:07 -0700

> I agree that a very common approach for balancing load involves hashing on the well known 5-tuple (source and destination IP addresses, etc...) to allow load splitting across multiple paths (plus t…

Right, agree. I was referring to how ISPs load-split traffic. It is a combination of control-plane (the specifity of route advertisements) and data-plane (5-tuple hash to select one of many ECMP paths).

> The reason that I was mentioning the less common, but still sometimes used approach of announcing more specific addresses into BGP in order to have traffic arrive at your network "closer" to the ul…

Right. With LISP you can do cold or hot potato with the same length prefix given to ITRs in different source sites. That can’t be done with a push protocol unless you do (source, dest) routing which kinda blows up the size of the RIB.

> Nonetheless, this is probably more easily discussed with a white board in front of us (and perhaps also a beer ;-).  

Definitely. Count on it.

Dino