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

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Tue, 5 Jan 2010 12:16:50 -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?
> 

Thinking of this further I would suggest that all the overlapping
EID-prefixes returned in the map-reply should have the same TTL.

Later in this thread, you suggested only returning the more specific
matches, but would encourage the ETR to return all mappings, because the
presence of the covering aggregate in an ITR's map-cache will suppress
further queries to these (other) more specifics.

-Darrel

---

From: Luigi Iannone <[email-masked]>
Date: Wed, 6 Jan 2010 13:37:20 +0100

Hi Darrel,

> EID-prefixes returned in the map-reply should have the same TTL.

Is there a specific reason for this suggestion?

Wouldn't having different TTL values be an interesting feature?
For instance, a more specific can be used for a specific purpose that needs shorter TTL compared to the less specific that covers the whole site and is (most probably) more stable.

Luigi

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

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 06 Jan 2010 11:14:45 -0500

Wouldn't it be much simpler just to not use overlapping prefixes?  Then 
we don't have to figure out if there is a TTL relationship.  We don't 
have to figure out if  aresponse to one block should include other 
related blocks.  And we don't have to examine the result for failing 
corner-cases.

I would be interested to hear why we would want to allow overlapping 
prefixes, personally.

Yours,
Joel

Luigi Iannone wrote:
> For instance, a more specific can be used for a specific purpose that 
> needs shorter TTL compared to the less specific that covers the whole 
> site and is (most probably) more stable.
> 
> Luigi
> 
> 
>> [email-masked] <mailto:[email-masked]>
> ------------------------------------------------------------------------
>

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Wed, 6 Jan 2010 10:18:53 -0800

Luigi,
 
The main reason I can think of that you want consistent TTL is that if a
sub (more specific) prefix's TTL times out, the ITR will not know to
look for the more specific.   So while I agree that its intuitive for
the main prefix to have a longer TTL, I think it could have undesirable
side effects.
 
-Darrel

________________________________

	From: Luigi Iannone [mailto:[email-masked]] 
	Sent: Wednesday, January 06, 2010 4:37 AM
	To: Darrel Lewis (darlewis)
	Cc: Dino Farinacci (dino); [email-masked]
	Subject: Re: [lisp] Design discussion -06-(3) -> return all
overlapping prefixes

	Hi Darrel, 

		Thinking of this further I would suggest that all the
overlapping
		EID-prefixes returned in the map-reply should have the
same TTL.

	Wouldn't having different TTL values be an interesting feature?
	For instance, a more specific can be used for a specific purpose
that needs shorter TTL compared to the less specific that covers the
whole site and is (most probably) more stable.

	Luigi

		Later in this thread, you suggested only returning the
more specific
		matches, but would encourage the ETR to return all
mappings, because the
		presence of the covering aggregate in an ITR's map-cache
will suppress
		further queries to these (other) more specifics.
		
		-Darrel

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 6 Jan 2010 10:30:59 -0800

> Wouldn't it be much simpler just to not use overlapping prefixes?   
> Then we don't have to figure out if there is a TTL relationship.  We  
> don't have to figure out if  aresponse to one block should include  
> other related blocks.  And we don't have to examine the result for  
> failing corner-cases.

Joel, I too would prefer to go this route.

But could we specify in the spec that if this rare case happens, that  
what is returned is all more specifics?

> I would be interested to hear why we would want to allow overlapping  

There are policy reasons for returning more specifics with a different  
locator-set than the coarse prefix. That is if you wanted to  
regionalize your LISP site where the more-specifics are branches, with  
a locator-set for that region and the coarse prefix is for the main  
hub sites (with all locators included perhaps).

And for the LISP-MN case, we day the /32 EIDs for MNs don't come out  
of an EID-prefix that is used in the mapping system for another site.  
As you had mentioned in early email.

We need to drive consensus on this before making progress on the spec.  
Any suggestions?

Dino

>> that needs shorter TTL compared to the less specific that covers  
>> the whole site and is (most probably) more stable.
>> Luigi

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Wed, 6 Jan 2010 10:51:27 -0800

> I would be interested to hear why we would want to allow overlapping 

Hi Joel,

An example use case I have in mind is on-demand pushback:

Lets say you are an enterprise with the eid 240.1.0.0/24 as an EID.  You
have a server, 240.1.1.100/32 that comes under a DDoS attack.  This DDoS
attack is filling your access link's bandwidth.

Now as the site's operator you can add a more specific mapping for
240.1.1.100/32 with the action of Drop.

Remote cache's then (once they are updated, with this cache coherency
(Dave Meyer's term) issue being a separate topic) traffic to this /32
will be dropped at the ITR (or Proxy ITR)!!!  Now your access bandwidth
is freed up and the DDoS attack is being dropped by the source of the
attack.

IMO this is a fundamental change to the security capabilities of your
site, and something that could really be a deployment incentive for
LISP.  While it does add some complexity to the design, I think it is
worth it.  There are obviously other use cases for TE, but this one I
think deserves special consideration.

-Darrel

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 06 Jan 2010 14:39:29 -0500

Does this assume use of a header bit in the data packet to trigger 
control revalidation?  (Without that, I just can't see how this case 
would work, even if we allowed it.)

Yours,
Joel

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Wed, 6 Jan 2010 11:43:41 -0800

> would work, even if we allowed it.)

I don't follow, you mean, the action bit of drop for the /32 below?
This case seems straightforward to me.

Let me know how if I need to explain it in more detail.

-Darrel

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Wed, 6 Jan 2010 12:53:50 -0800

> > would work, even if we allowed it.)

Joel and I had an off list conversation where we got sorted, so here is
the results.  In my first message, I tried to keep the cache-coherency
issue separate from the sub-prefixes issue.  But they are inter-related,
and I will try to give a detailed example that includes them.  So I'll
rewrite the example below with more detail on how caches get updated.
Comments welcome.

More Specific Pefixes used as a DoS Pushback:
--------------------

Lets say you are an enterprise with the eid 240.1.0.0/24 as an EID.  You
have a server, 240.1.1.100/32 that comes under a DDoS attack.  This DDoS
attack is filling your access link's bandwidth.  Also, lets consider
what happens if your /24 mapping has a 24 hour TTL when the DDoS attack
starts.  Obviously you don't want to wait 24 hours to push back/drop the
attack traffic.

Now as the site's operator you can add a more specific mapping for
240.1.1.100/32 with the action of Drop, and changes both the /24 and the
/32 TTL to 10 minutes.

The site's xTR will now set SMR bit in data packets it sends to other
sites, letting them know that the mapping for the /24  has changed.
ITRs you are not sending data to currently will learn this new mapping
by probing (probing is all Proxy ITRs can do) and learning that the
mapping has changed. 

So over a period of time (likely several minutes due to the probe
interval), remote ITR's (and Proxy ITRs) caches will be updated.  

Your site's access bandwidth is freed up and the DDoS attack is being
dropped by the source of the
attack.

-Darrel

---

From: Patrick Frejborg <[email-masked]>
Date: Thu, 7 Jan 2010 09:03:33 +0200

Joel,

it would be interesting to have a look on how much overlapping
prefixes there is today in the DFZ and if that needs to be purged into
non-overlapping prefixes what would then be the amount of prefixes in
DFZ?
Or perhaps a uni-class caching approach might be interesting, as
discussed in section 2.1 at
http://www.cs.princeton.edu/~chkim/papers/routecaching_pam09.pdf

-- patte
On Wed, Jan 6, 2010 at 6:14 PM, Joel M. Halpern <[email-masked]> wrote:
> Wouldn't it be much simpler just to not use overlapping prefixes?  Then we
> don't have to figure out if there is a TTL relationship.  We don't have to
> figure out if  aresponse to one block should include other related blocks.
>  And we don't have to examine the result for failing corner-cases.
>
>> needs shorter TTL compared to the less specific that covers the whole site
>> and is (most probably) more stable.
>>
>> Luigi
>>
>>

---

From: Terry Manderson <[email-masked]>
Date: Wed, 6 Jan 2010 23:26:46 -0800

co-chair hat off.

Patrick,

What I see from the ICANN ASN is summarized here:

http://stats.research.icann.org/bgp/

of most interest might be the origin maps, which puts all prefixes
underneath their least specific in terms of sub-allocated (more specific
announced by a different ASN) and deaggregated (more specific announced by a
different ASN).

Cheers
Terry

---

From: Damien Saucez <[email-masked]>
Date: Thu, 7 Jan 2010 09:18:09 +0100

Darrel,

Tell me if I am wrong: when a DDoS attack is detected, you create a more-specific entry for the destination under attack with a short TTL and a special (set of) RLOC(s). You thus need to inform the sources of traffic that their is a change in the mapping and then use the SMR bit. The sources will then send Map-Requests and receive the new mappings.

If I understood correctly, this counter-measure can be used to generate even bigger DDoS! Indeed, every time you see this kind of attack, you generate a more-specific mapping to isolate the attacked server. This mapping has a short TTL and every body needs to know the mapping. So when the new mapping is generated, every body will ask for the new mapping, and this will be done every 10min in your example, meaning that we effectively reduce the traffic to the destination but we increase the load on the mapping system. Basically, instead of having sometime a query, we have queries all the time (especially if we set the same TTL , e.g., 10 min, to all the mappings as you recommended in a previous mail). Additionally, if we just drop the packet, how to know that the DDoS is finished? We do not receive traffic anymore! Finally, if you move all the traffic to a black-hole, you also drop the correct traffic, making the attack more efficient than without the protection.

Finally, if an attacker knows how the system will behave (add a more specific entry with small TTL), he can perform 3 kinds of DDoS at the same time. First, the original DDoS (no traffic to the target as the mapping redirect traffic to a black-hole). Second, a DDoS on the mapping system, if you attack a lot of targets the system generates a lot of short-lives mappings and thus a lot of traffic on the mapping system, globally. Third, if you know that the map cache size at the sites you are attacking from, then you can calculate the number of targets you need to fill the cache and drop some completely unrelated traffic. 

IMO, to make this counter-measure a bit better, we need:
1. Detect the origin of the attack
2. Push the more-specific mapping only to the origin of the attack (do not change mappings for the other sources of traffic)

But even with these changes, the counter-measure can have very bad side effects. And if you combine this attack with a spoof attack, you can isolate a perfectly innocent site.

Regards,

Damien Saucez

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 07 Jan 2010 07:45:13 -0500

[For clarity, this is all personal.  As chair, I just have to wait and 
see what folks think..]

We are talking about overlapping EIDs, not overlapping locators.
There are LOTs of overlapping addresses in the current tables.
There are multiple reasons for these.
It is not clear to me that any of them apply to EIDs.
Patrick, you seem to see a parallel I am missing.  Can you elucidate?

Darrel has raised an interesting idea for how one might use overlapping 
EIDs if they are allowed.  That usage clearly has value.  Is that value 
more than the complexity required for allowing overlapping EIDs? 
Particularly if, as appears to be the case, we would need to indicate 
that any request for a block that has nested EIDs needs to return all 
those nested EID mappings as well?  I don't know what the right tradeoff is.

I would be interested in hearing from other folks who have looked at 
this as to where the value is.

Thanks,
Joel

---

From: Patrick Frejborg <[email-masked]>
Date: Thu, 7 Jan 2010 19:39:02 +0200

Joel,

I think you can drop my previous questions....my head had a slow start
this morning, probably due to the holidays, cold and snow...

Only situation when a cache-hiding could occur is if an ETR-1
advertise an aggregate e.g. /20 and an ETR-2 advertise a /24 from the
the same space. An ITR setting up a connection first to ETR-1 can not
setup a "longest match" connection to ETR-2 until the cache entry /20
has expired on the affected ITR. But this can be avoided as long there
is no aggregate behind the ETR, the cache-hiding situation shouldn't
occur. And there should be no reason to aggregate EIDs...thus my
previous concerns are not valid, drop that.

"No-aggeragtes-behind-ETR" have some implications for the ETR though -
cache entries at ETR are no longer aggregated as today the FIB of a
multi-homed ASBR is. Then for how many cache entries should an ETR be
designed for?
Especially if the ETR is in front of a popular site, the current DFZ
aggregated entries gets de-aggregated in the ETR cache - could the
needed size of the cache become larger than the current FIB in the
DFZ?
Think it depends on the popularity of the site...but a site might
become suddenly popular due to some event, e.g. natural catastrophe,
accidents etc...

If the cache gets much larger, will the ETR node become more expensive
than the current DFZ FIB node?
Are there any studies around ETR in front of popular sites and the
expected cache size of the ETR?

Perhaps I haven't yet recovered from the holidays and missing something obvious?

-- patte

On Thu, Jan 7, 2010 at 2:45 PM, Joel M. Halpern <[email-masked]> wrote:
> [For clarity, this is all personal.  As chair, I just have to wait and see
> what folks think..]
>
> Darrel has raised an interesting idea for how one might use overlapping EIDs
> if they are allowed.  That usage clearly has value.  Is that value more than
> the complexity required for allowing overlapping EIDs? Particularly if, as
> appears to be the case, we would need to indicate that any request for a
> block that has nested EIDs needs to return all those nested EID mappings as
> well?  I don't know what the right tradeoff is.
>
> I would be interested in hearing from other folks who have looked at this as
> to where the value is.
>
> Thanks,
> Joel
>
> Patrick Frejborg wrote:
>>
>> Joel,
>>
>>> we

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Thu, 7 Jan 2010 09:54:23 -0800

> -----Original Message-----
> From: Damien Saucez [mailto:[email-masked]] 
> Sent: Thursday, January 07, 2010 12:18 AM
> Cc: Joel M. Halpern; [email-masked]
> Subject: Re: [lisp] Design discussion -06-(3) -> 
> returnalloverlapping prefixes
> 
> Darrel,
> 
> Tell me if I am wrong: when a DDoS attack is detected, you 
> create a more-specific entry for the destination under attack 
> with a short TTL and a special (set of) RLOC(s). You thus 
> need to inform the sources of traffic that their is a change 
> in the mapping and then use the SMR bit. The sources will 
> then send Map-Requests and receive the new mappings.
> 

Blackholing is not a solution to DDoS, but it's a tool for a site's
toolbox to sacrifice one host in order to keep the site up.  But lets
not make this a discussion about DDoS, since that's a wider topic that
isn't LISP specific.  But it's a hobby of mine for the last 10 years or
so and I'd love to talk off-list about it.  (for further reading, check
out flowspec and remote triggered black holing in bgp)

I personally don't consider a site performing mapping updates to be a
DoS.  And the ALT must have the capcity to handle sites who use any
valid TTL.

-Darrel

---

From: Luigi Iannone <[email-masked]>
Date: Thu, 7 Jan 2010 20:14:31 +0100

Darrel,

On Jan 6, 2010, at 19:18 , Darrel Lewis (darlewis) wrote:

> Luigi,
>  
> The main reason I can think of that you want consistent TTL is that if a sub (more specific) prefix's TTL times out, the ITR will not know to look for the more specific.   

Thanks, I got your point. 

Nevertheless, I think this is exactly the main  problem that overlapping EID-prefixess have: How does an ITR having a less specific become aware that a new more-specific mapping exists?
In this case map-versioning can help (here it goes again ;-) ), but I am sure there are still corner cases that we are not aware of.  

Generally speaking I think that overlapping EID-prefixes has potential, but of course it adds complexity (TANSTAAFL).

 Luigi

> So while I agree that its intuitive for the main prefix to have a longer TTL, I think it could have undesirable side effects.
>  
> -Darrel
>  
> 
> Subject: Re: [lisp] Design discussion -06-(3) -> return all overlapping prefixes
> 
> Hi Darrel,
>

---

From: John Zwiebel <[email-masked]>
Date: Fri, 8 Jan 2010 10:35:45 -1000

On Jan 7, 2010, at 9:14 AM, Luigi Iannone wrote:

>
> Nevertheless, I think this is exactly the main  problem that  
> overlapping EID-prefixess have: How does an ITR having a less  
> specific become aware that a new more-specific mapping exists?
> In this case map-versioning can help (here it goes again ;-) ), but  
> I am sure there are still corner cases that we are not aware of.
>

FWIW:
Isn't a given EID prefix under the control of a single administrator?
So it is up to that administrator to determine how he wants to  
allocate more specific prefixes
Every ITR under his control should have configuration for all the  
other ITRs for the same prefix

---

From: Luigi Iannone <[email-masked]>
Date: Mon, 11 Jan 2010 11:13:14 +0100

> Isn't a given EID prefix under the control of a single administrator?

Yes.

> So it is up to that administrator to determine how he wants to allocate more specific prefixes
> Every ITR under his control should have configuration for all the other ITRs for the same prefix
> 

No, the ITR will request the mapping through the mapping system and the ETR will provide such a mapping.

The scenario here is assume that your ITR is encapsulating traffic with destination 1.2.3.4 using a mapping with EID prefix 1.2/16. At some point the administrator of the prefix setup a new more specific mapping 1.2.3/24. How does you ITR knows that the new mapping is available?

Hope I clarified the scenario.

Luigi

---

From: Sam Hartman <[email-masked]>
Date: Mon, 11 Jan 2010 18:32:10 -0500

>>>>> "Joel" == Joel M Halpern <[email-masked]> writes:

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

    Joel> If we allow overlapping EID blocks, and if we ever allow
    Joel> mobile-LISP, then the number of EIDs in a prefix could be VERY
    Joel> large.  Returning all of them in response to any request for a
    Joel> non-mobile EID in the larger block is clearly the wrong
    Joel> answer.
Joel, I think  that my gut inclination is to support overlapping
    Joel> prefixes, although I don't have a strong argument for doing it
    Joel> and
if the WG has or does reach the decision that we don't want overlapping
    Joel> prefixes I'm OK ith that.

It seems that you have a couple of options when your reply set would be
too large (and I believe a MNblock is one case where you get a large
reply set):

1) return a more specific mapping than you otherwise could.

2) Return less specific mappings with the MN prefix/the prefix that has
a lot of specific entries covered by a negative record saying that no
information is returned.

Remember that there are a number of negative record types.  One of them
is to discard packets.  However I think there is at least one record
type that basically says "I don't have an answer for you now."  I.E ask
again.  Such a record could cover parts of a prefix that are high-churn
or that have too much data.

--Sam

---

From: Sam Hartman <[email-masked]>
Date: Mon, 11 Jan 2010 18:33:47 -0500

>>>>> "Darrel" == Darrel Lewis (darlewis) <[email-masked]> writes:

Thinking of this further I would suggest that all the overlapping
    Darrel> EID-prefixes returned in the map-reply should have the same
    Darrel> TTL.

Why is this?
Won't you want lover TTLs for your MN entries than fixed node entries?

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 11 Jan 2010 21:54:16 -0500

Can you elucidate the advantages that lead you to want to support 
overlapping (nested, generally) EID prefixes?

Your point about the "ask later" (ACT code 2) answer is a good way to 
cope with excess sub-blocks, if they are organized reasonably.  Should 
we say that in the document?  (If so, where?  Once we get past "the 
protocol does / does not permit nested EID prefixes", this starts to get 
into recommended policy, which is not protocol.)

Yours,
Joel

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 12 Jan 2010 14:31:24 -0800

Here is proposed text to deal with this issue. Darrel will be posting  
posting to the list an entire diff file as well as the ID shortly.

Thanks,
Dino and Darrel

On Dec 21, 2009, at 6:37 PM, Dino Farinacci wrote:

> Dino/Darrel

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Thu, 14 Jan 2010 21:44:37 -0800

> Won't you want lover TTLs for your MN entries than fixed node entries?

MN entries are not 'overlapping' in the sense that they are their own
EID block (a /32 or /128).  Rather than nested inside another EID block.

-Darrel

---

From: Sam Hartman <[email-masked]>
Date: Fri, 15 Jan 2010 11:28:55 -0500

Depending on topology and how likely it is that MNs would be away from
the site, I actually think you might well want to nest them.
However another note you sent to the list explained why that introduces
problems when the shorter TTL entries expire.

Obviously, for the MN case, there are solutions we could adopt--the site
could route the packets using some sort of triangle routing like a HA
does and send you a SMR for that longer prefix, but that's a *lot* of
complexity.  Your solution of using the TTL is far simpler.