Subject: [lisp] Design discussion -06-(3) -> return all overlapping prefixes

From: Dino Farinacci <[email-masked]>
Date: Mon, 21 Dec 2009 18:37:45 -0800

A description of the design issue:

(3) Add text in section 6.1.5 about returning all EID-prefixes in a
    Map-Reply sent by an ETR when there are overlapping EID-prefixes
    configure.

If a LISP site is configured with EID-prefixes that overlay, that is  
say it is configured with an EID-prefix of 10.1.0.0/16 and also  
10.1.0.0/24 we need better language in the spec to indicate how this  
is dealt with. Because if a Map-Request is sent for 10.1.1.1, and if  
the ETR only returns a Map-Reply for 10.1.0.0/16, then a Map-Request  
for 10.1.0.1 will use the locator-set from the 10.1.0.0/16 map-cache  
entry and not for the 10.1.0.0/24 entry which could have a different  
locator-set. So we want to write language in the spec to have an ETR  
return all EID-prefixes in the Map-Reply.

Any objections to this?

Thanks,
Dino/Darrel

---

From: Damien Saucez <[email-masked]>
Date: Tue, 22 Dec 2009 08:59:01 +0100

On 22 Dec 2009, at 03:37, Dino Farinacci wrote:

> If a LISP site is configured with EID-prefixes that overlay, that is say it is configured with an EID-prefix of 10.1.0.0/16 and also 10.1.0.0/24 we need better language in the spec to indicate how this is dealt with. Because if a Map-Request is sent for 10.1.1.1, and if the ETR only returns a Map-Reply for 10.1.0.0/16, then a Map-Request for 10.1.0.1 will use the locator-set from the 10.1.0.0/16 map-cache entry and not for the 10.1.0.0/24 entry which could have a different locator-set. So we want to write language in the spec to have an ETR return all EID-prefixes in the Map-Reply.
> 
ok, the Map-Reply MUST contain all the matching EID prefixes.

Damien Saucez
> Any objections to this?
> 
> Thanks,
> Dino/Darrel
> 
> _______________________________________________
> lisp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lisp

---

From: Florin Coras <[email-masked]>
Date: Tue, 22 Dec 2009 09:28:20 +0100

Hi,

> return all EID-prefixes in the Map-Reply.
I like this solution but I don't remember if the group has discussed the
scenario when a LISP site has many mobile nodes. If, for example, there
are 1000 mobile nodes they will all have individual (/32, /128[/64?] )
mappings and they sum up to a considerable amount of EID-prefixes to be
put in a Map-Reply. Do we have a solution for this or is this a
problem?  We don't care because mobility is out of scope?

Florin

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 22 Dec 2009 12:01:53 -0500

(speaking personally)
The problem below is why this approach makes me very nervous.

If we allow overlapping EID blocks, and if we ever allow mobile-LISP, 
then the number of EIDs in a prefix could be VERY large.  Returning all 
of them in response to any request for a non-mobile EID in the larger 
block is clearly the wrong answer.

My inclination, frankly, is to prohibit overlapping EID blocks in end 
allocations (delegations obvious are nested / overlapping, but you can 
never get an answer for a delegation, only for what is actually used.) 
A side may be allocate a single large block, and use part of it for 
fixed, and part of it for mobile.  But under this approach it can not 
use the whole block for the site, and use part of it for the mobile nodes.
Similarly, to avoid overlap, if an enterprise gets a block, and wants to 
use separate parts of the EID space for different locations, then it has 
to carve up the EID block to the locations.  (Heck, they are each 
distinct sites.)  (I have discussed in earlier messages how this can be 
done in a way that is compatible with having backup inter-location links 
as lower priority paths to various corporate locations.)

If we really want to allow nested resolvable blocks, I think we need to 
explain how this will avoid becoming intractable in response size.

Yours,
Joel

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 22 Dec 2009 16:53:33 -0800

>> If a LISP site is configured with EID-prefixes that overlay, that  
>> is say it is configured with an EID-prefix of 10.1.0.0/16 and also  
>> 10.1.0.0/24 we need better language in the spec to indicate how  
>> this is dealt with. Because if a Map-Request is sent for 10.1.1.1,  
>> and if the ETR only returns a Map-Reply for 10.1.0.0/16, then a Map- 
>> Request for 10.1.0.1 will use the locator-set from the 10.1.0.0/16  
>> map-cache entry and not for the 10.1.0.0/24 entry which could have  
>> a different locator-set. So we want to write language in the spec  
>> to have an ETR return all EID-prefixes in the Map-Reply.
>>

I actually stated it wrong. It should contain all "more specific"  
matches. Here is what we were thinking in terms of text:

    When an ETR is configured with overlapping EID-prefixes, a Map-
    Request with an EID that longest matches any EID-prefix must be
    returned in a single Map-Reply message.  For instance, if an ETR had
    database mapping entries for EID-prefixes 10.0.0.0/8, 10.1.0.0/16,
    10.1.1.0/24 and 10.1.2.0/24, and a Map-Request was for EID 10.1.5.5,
    then a Map-Reply with a record count of 2 is returned with mapping
    records for EID-prefixes 10.0.0.0/8 and 10.1.0.0/16.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 22 Dec 2009 16:58:17 -0800

> problem?  We don't care because mobility is out of scope?

If the site had EID-prefix 10.1.0.0/16 and a LISP-MN was sitting in  
the site with address 10.1.1.1/32, there  is no need for returning  
both EID-prefixes here because the 10.1.1.1/32 locator-set wouldn't be  
used directly by remote ITRs. They would first encapsulate to the ETR  
based on locators for 10.1.0.0/16 and then the ETR would decap and  
reencap to the LISP-MN.

This is a case where the LISP-MN *roams back* to the topology where  
its EID-prefix resides.

However, if the remote ITR knew about the the /32, it only responds  
with 10.1.0.0/16 and 10.1.1.1/32 (and not all the other MNs /32s).

Sorry how I could have created confusion with my initial email.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 22 Dec 2009 17:00:55 -0800

> My inclination, frankly, is to prohibit overlapping EID blocks in  
> end allocations (delegations obvious are nested / overlapping, but  
> you can never get an answer for a delegation, only for what is  
> actually used.) A

I would same the same Joel.

In most cases there will be either a single EID-prefix for a site. Or  
when exceeding allocation capacity another one which is not  
overlapping (but perhaps in a contiguous power-of-2 block).

I also think with one allocation of say /24, a site might want to  
regionalize where one /25 is using locators A and A' in the US and  
another /25 using locators B and B' in Europe.

But these are not overlapping cases.

> side may be allocate a single large block, and use part of it for  
> fixed, and part of it for mobile.  But under this approach it can  
> not use the whole block for the site, and use part of it for the  
> mobile nodes.
> Similarly, to avoid overlap, if an enterprise gets a block, and  
> wants to use separate parts of the EID space for different  
> locations, then it has to carve up the EID block to the locations.   
> (Heck, they are each distinct sites.)  (I have discussed in earlier  
> messages how this can be done in a way that is compatible with  
> having backup inter-location links as lower priority paths to  
> various corporate locations.)

Right.

Dino

---

From: Xu Xiaohu <[email-masked]>
Date: Tue, 29 Dec 2009 15:41:52 +0800

> -----邮件原件-----
> 发件人: [email-masked] [mailto:[email-masked]] 代表 Dino
> Farinacci
> 发送时间: 2009年12月22日 10:38
> 收件人: [email-masked]
> 主题: [lisp] Design discussion -06-(3) -> return all overlapping prefixes
> 

In fact, I had proposed the same approach to the EID prefix overlapping
issue two years before. That is "...There are some approaches to avoid this:
one is avoiding the EID prefixes in mapping database overlapped, the other
is replying with all the specific EID-prefixes’ mapping covered by the
matching EID-prefix. The former will result in non-aggregation, ...<skip>...
The latter approach will result in some useless states in the ITR cache...."
For more details, see http://www.ops.ietf.org/lists/rrg/2007/msg00429.html

However, at that time, some people who are engaged in LISP-CONS didn’t
reach a consensus on that topic. See 
http://www.ops.ietf.org/lists/rrg/2007/msg00448.html and 
http://www.ops.ietf.org/lists/rrg/2007/msg00447.html

Now (two years latter since then) I'm glad to see the above issue and its
corresponding solution are covered in LISP design :)

Xiaohu

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 29 Dec 2009 09:01:15 -0800

> For more details, see http://www.ops.ietf.org/lists/rrg/2007/msg00429.html

Let's make it very clear we are talking about the map-cache here and  
not the mapping delivery system. In LISP-CONS and LISP-ALT, we still  
maintain good aggregation because all these systems need to do is  
route the Map-Request to *any* ETR at the destination site.

The reason the site may have more specific mapping entries is because  
the locator-set may be different.

An ITR could store the more-specific mappings if it has flows matching  
the entry. And when it doesn't it could just use the coarse mapping  
and set a small amount of *exception state* when it would need to send  
Map-Requests for the more specifics mappings it decided to *not* store  
when the ETR returned more than one mapping in the Map-Reply.

Dino

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 30 Dec 2009 09:30:35 +0800

> -----邮件原件-----
> 发件人: Dino Farinacci [mailto:[email-masked]]
> 发送时间: 2009年12月30日 1:01
> 收件人: Xu Xiaohu
> 抄送: [email-masked]
> 主题: Re: [lisp] Design discussion -06-(3) -> return all overlapping
prefixes
> > For more details, see
http://www.ops.ietf.org/lists/rrg/2007/msg00429.html
> not the mapping delivery system. 

Yes, I'm talking about the map-cache here, too. 

The following is Noel's response to my email mentioned before, which may be
helpful for you.
http://www.ops.ietf.org/lists/rrg/2007/msg00437.html

> In LISP-CONS and LISP-ALT, we still

I'm not suspecting this.

> when the ETR returned more than one mapping in the Map-Reply.

I'm a bit confused. Do you mean: the additional specific mappings returned
in the map-reply (due to being covered by the matched coarse mapping) are
stored in the cache. However they are not used for forwarding packets
directly since they may become stale. Hence they are marked with a special
flag to indicate that if a received packet matches any of those entries, a
new map-request should be sent in order to get the latest mapping for that
packet.

If the above understanding is not correct, could you please say more with an
example? 

Xiaohu

---

From: Charrie Sun <[email-masked]>
Date: Wed, 30 Dec 2009 10:01:03 +0800

2009/12/30 Xu Xiaohu <[email-masked]>

> new map-request should be sent in order to get the latest mapping for that
I suspect what Dino means is that when ITR receives all coarse and specific
mappings replies it only stores the corse ones, while marks the specific
EIDs as 'exceptional state'. (Perhaps this doesn't wholely related to the
data validity but to the storage demand of ITR.) When ITR wants to forward
packets to those specific EIDs, it launches another request (instead of
using the coarse mapping). Is it right, Dino?

---

From: Charrie Sun <[email-masked]>
Date: Wed, 30 Dec 2009 10:23:30 +0800

2009/12/23 Joel M. Halpern <[email-masked]>

> If we allow overlapping EID blocks, and if we ever allow mobile-LISP, then
> the number of EIDs in a prefix could be VERY large.  Returning all of them
> in response to any request for a non-mobile EID in the larger block is
> clearly the wrong answer.

> allocations (delegations obvious are nested / overlapping, but you can never
> get an answer for a delegation, only for what is actually used.) A side may
> be allocate a single large block, and use part of it for fixed, and part of
> it for mobile.  But under this approach it can not use the whole block for
> the site, and use part of it for the mobile nodes.
> use separate parts of the EID space for different locations, then it has to
> carve up the EID block to the locations.  (Heck, they are each distinct
> sites.)  (I have discussed in earlier messages how this can be done in a way
> that is compatible with having backup inter-location links as lower priority
> paths to various corporate locations.)
>
>
I fully aggree. I think we should differenciate the cases between
multihoming and mobility. In multihoming we could have different mappings
for one EID prefix (the coarse prefix) with different preferences; in
mobility we might need to store and reply mapping for each EID separately,
which is indeed very large. Perhaps we could take advantage of that a mobile
host wouldn't leave a site too soon. While in either case (multihoming and
mobility), EID blocks shouldn't be overlapped. If a site want to use
different locations, separate EIDs and equipped with preferences.

---

From: Xu Xiaohu <[email-masked]>
Date: Wed, 30 Dec 2009 12:20:21 +0800

_____  

发件人: Charrie Sun [mailto:[email-masked]] 
发送时间: 2009年12月30日 10:01
收件人: Xu Xiaohu
抄送: Dino Farinacci; [email-masked]
主题: Re: [lisp] Design discussion -06-(3) -> return all overlapping
prefixes

prefixes

I'm not suspecting this.

I suspect what Dino means is that when ITR receives all coarse and specific
mappings replies it only stores the corse ones, while marks the specific
EIDs as 'exceptional state'. 

[Xiaohu]: then where should the specific EID prefixes be stored?

Xiaohu

(Perhaps this doesn't wholely related to the data validity but to the
storage demand of ITR.) When ITR wants to forward packets to those specific
EIDs, it launches another request (instead of using the coarse mapping). Is
it right, Dino? 

Xiaohu

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 31 Dec 2009 11:42:31 -0800

> stored in the cache. However they are not used for forwarding packets

Yes. But I wouldn't phrase it that way. I would say to store them  
"efficiently". Which means not as a map-cache entry but as another  
data structure used as an exception to coarse map-cache entry. Just  
suggesting an implementation trick.

> new map-request should be sent in order to get the latest mapping  

Yes.

> If the above understanding is not correct, could you please say more  

You got it.

Dino