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

[Ross Callon <[e-mail]>]

> 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

[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:[e-mail]] 
Sent: Thursday, April 02, 2015 3:16 AM
To: Ross Callon
Cc: Joel Halpern; Luigi Iannone; LISP mailing list list; [e-mail]
Subject: Re: [lisp] WG Last Call draft-ietf-lisp-impact-01


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

> I suppose that there are two options:
> 
> 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.  
> 
> -----Original Message-----
> From: Joel M. Halpern [mailto:[e-mail]] 
> Sent: Sunday, March 29, 2015 9:36 PM
> To: Ross Callon; Luigi Iannone; LISP mailing list list
> Cc: [e-mail]
> 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:[e-mail]] *On Behalf Of *Luigi Iannone
>> *Sent:* Monday, March 09, 2015 10:22 AM
>> *To:* LISP mailing list list
>> *Cc:* [e-mail]
>> *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
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/lisp
>> 
> 
> _______________________________________________
> lisp mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/lisp