Subject: [RRG] cache issues in LISP and CONS

From: Dan Jen <[email-masked]>
Date: Wed, 17 Oct 2007 18:26:59 -0700

The issue regarding packet drops with LISP and LISP-CONS has been
brought up a few times on the list.

Basically, packets are dropped for every ITR cache miss.  Since CONS
mapping requests may take a long time to be satisfied, this may result
in unacceptable service.

Suggestions have been made to route packets on the old topology in the
event of ITR cache misses. However, this leads to a major incremental
deployment issue -- since LISP adopters will still need to maintain
their routes in the old topology, there would be no reduction in the
size of the global routing table.  

I have not seen any other suggestions on how to handle this issue.
Could this be a fundamental problem with the design, or are there other
solutions? 

Thanks,

Dan

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 17 Oct 2007 23:01:37 -0400 (EDT)

> From: Dan Jen <[email-masked]>

    > Since CONS mapping requests may take a long time to be satisfied, this
    > may result in unacceptable service.

I have done a lot of thinking about optimizations in CONS, in an attempt to
produce a hierarchical distributed pull system with performance which is
close to that of a full-push system. These aren't reflected in the spec yet,
but I imagine some should be in the future.

There's a list of about 10, not all of which will be worth adding; since each
one adds complexity (some more than others), there's a complexity/performance
tradeoff to be considered for each one.

The two main ones (in terms of performance bang) are:

- Caching of EID->RLOC bindings in the CDR hierarchy, which both reduces
resolution delays, as well as decreasing load on aCAR's, for widely used
destinations. This is simple, and makes resolution of widely used
destinations about as fast as a push system.

- 'Piggybacking' the return EID->RLOC binding on the request for the forward
EID->RLOC binding. This one is not universally liked, because it adds a fair
amount of complexity (in part because you have to add authentication to
secure what are effectively unsolicited binding replies; in part because the
caching above means that not all requests actually get to the other end). On
the upside, doing this cuts out *all* of the resolution delay in the reverse
direction in *all* communication pairings, whether to widely used
sources/destinations, or not.

    > size of the global routing table.

Well, it's not just an incremental issue; either i) we always maintain the
backup routing (in which case we don't get the size reductions, as you point
out), or ii) we don't maintain them into the indefinite future, in which case
the speedup of using the backup routing would not be available in the future.

But since I think we can make the resolution adequately fast, I don't think
there's a problem here.

	Noel

---

From: Scott Brim <[email-masked]>
Date: Thu, 18 Oct 2007 08:24:59 -0500

> brought up a few times on the list.
...
> Could this be a fundamental problem with the design, or are there other

Well, to start with there's your default mapper :-).  It will have
some drops but perhaps not as many.  Noel mentions caching.  I believe
caching can help a lot, but we need to simulate it.  We also need to
investigate pushing information partway, and how it interacts with
cache.  Finally, there is the possibility -- related to default mapper
-- of sending initial packets on less than optimal routes while more
direct ones are found.

---

From: <[email-masked]>
Date: Thu, 18 Oct 2007 14:43:50 +0100

If I understood correctly (big assumption) I thought the intention was
somehow to have the mapping system partly responsible for multi-homing
(ID could map to multiple edge routers). Surely if we need to introduce
aggressive caching it would make multi-home failover slow? Also it would
make it hard for the mapping system to provide traffic engineering? 

Louise

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf 
> Of Scott Brim
> Sent: 18 October 2007 14:25
> To: Dan Jen
> Cc: [email-masked]
> Subject: Re: [RRG] cache issues in LISP and CONS
> 
> > Could this be a fundamental problem with the design, or are there 
> > other solutions?
> 
> Well, to start with there's your default mapper :-).  It will 
> have some drops but perhaps not as many.  Noel mentions 
> caching.  I believe caching can help a lot, but we need to 
> simulate it.  We also need to investigate pushing information 
> partway, and how it interacts with cache.  Finally, there is 
> the possibility -- related to default mapper
> -- of sending initial packets on less than optimal routes 
> while more direct ones are found.
> 
> 
> --

---

From: Xu Xiaohu <[email-masked]>
Date: Thu, 18 Oct 2007 16:20:05 +0200

> -----邮件原件-----
> 发件人: [email-masked] [mailto:[email-masked]] 代表 Noel Chiappa
> 发送时间: 2007年10月18日 5:02
> 收件人: [email-masked]
> 抄送: [email-masked]
> 主题: Re: [RRG] cache issues in LISP and CONS
> 
How to determine the widely used destination when taking the P2P traffic,
which consumes more than 60~70% of the total bandwidth, into account?

Once caching is deployed in the CDR hierarchy, does the ITR still need to
use cache mechanism?

Xiaohu Xu

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 18 Oct 2007 11:11:18 -0400 (EDT)

> From: Xu Xiaohu <[email-masked]>

    > How to determine the widely used destination

I spent a lot of time thinking about that, and finally came up with what I
think is a very efficient (in terms of overhead), and extremely effective (in
terms of correctly identifying which mappings are widely used) system for
deciding which entries to cache in the CDRs.

Basically, it works by starting with the actual mappings in the aCARs; those
entries have to always exist anyway, so it is just an extra field in those
entries, which gets incremented any time the mapping is requested. When the
aCARs notice a lot of requests for a particular mapping, they suggest to their
parent CDR(s) that they cache that mapping. The same process then repeats at
each CDR level.

We will have to tune it a bit, and adjust the constants (i.e. how many
requests are enough to trigger the upward cache) but the basic mechanism
is very good.

    > when taking the P2P traffic, which consumes more than 60~70% of the
    > total bandwidth, into account?

Bandwidth is not necessarily the same as number of connections, and the need
for a mapping only exists when a connection is opened. Since my understanding
is that most P2P traffic is for large media files, I suspect that they account
for a smaller percentage of connection openings. Also, since they are for
large files, if they take a few extra tens/hundreds of milliseconds to start,
I think that is probably acceptable.

Also, the second optimization I mentioned (having the EID->RLOC mapping for
the source carried along with the request for the EID->RLOC mapping for the
destination) will help P2P connections too (since it helps *every*
connection).

Of course, if we were designing the entire network from scratch, we would
probably have the mapping system return both the EID and RLOC, or something
like that; it doesn't make sense to have two separate resolution cycles.
However, we have to live with what it already out there, which means this
resolution step has to be a separate system.

    > Once caching is deployed in the CDR hierarchy, does the ITR still need
    > to use cache mechanism?

I would say yes, but remember, a cache is just a way to increase performance.
So, if you can get 'good enough' performace without the cache, you don't have
to have it.

What would be the benefit to not having the ITR cache entries? Making them
simpler? The disadvantage is that every connection would be slower to open
(the ITR would have to talk to the rCAR).

	Noel

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 18 Oct 2007 12:01:55 -0400 (EDT)

> From: Scott Brim <[email-masked]>

    > Well, to start with there's your default mapper :-).

That's a interesting idea. Has the default mapper stuff been worked out in
detail?

    > I believe caching can help a lot, but we need to simulate it.

I am a bit dubious about simulations; CDR caching is simply enough it's
probably easier to just add it, and see how it performs in actual usage.

    > From: Robin Whittle <[email-masked]>

    > You could probably create a complex combination of caching and genuine
    > push of update messages to make the CAR-CDR network faster.
    > The question is whether it would be easier to create a complex and
    > souped up CAR-CDR system than to establish a clean - although ambitious
    > - system to distribute mapping data globally,

Well, that's the $64,000 question. There's no question that a pure push
system will have better performance (in terms of resolution delays) than even
an optimized pull system. How much better depends on a lot of factors, but
there will always be some cases where pure push outperforms any pull system.
However, a pure push system awill also have a *lot* more overhead. Is "a
*lot*" too much? I don't know.

I tried to do some back-of-the-envelope math, and I decided that depending on
what assumptions you made about how often bindings changed (I seem to get a
new IP address at home every couple of months as my ISP reorganizes), how
small address blocks became (i.e. will we go below /24's), etc you could get
answers ranging from easy to do (a couple of updates per second) to
unreasonable (a thousand per second). 

I do have a few things I can say for sure. For one, I don't think it's
feasible to do significant amounts of mobility with a pure push system; it
will raise the update rate too much. Doing mobility will greatly increase the
size of the table (since individual hosts will be mobile) as well as the
update rate, making push doubly infeasible.

For another, a lot of the table (and the updates to it) will be unused in
basically every box; as the Internet increasingly splits into
language-specific regions (I doubt a lot of people in South America are
looking at pages in Mandarin). Most hosts on the Internet rarely, if ever,
communicate with large portions of the rest of it, and this tendency for
differentiated communication patterns becomes more prominent as one gets
toward the leaves (which is where pure push has to send mappings, if you want
to get rid of *all* mapping delays).

In general, I think that push is architecturally brittle, in that one can't
do a lot with it. It either works, or it doesn't (like the DFZ today).

Yes, optimized pull systems are more complex. It's TANSTAAFL: you don't get a
system with almost as good speed characteristics, and a lot less operational
overhead, and also have minimal complexity. It's like the old "fast, cheap,
good" axiom, only this version is "speed, overhead, complexity: pick any two".

	Noel

---

From: Xu Xiaohu <[email-masked]>
Date: Thu, 18 Oct 2007 18:25:00 +0200

> -----邮件原件-----
> 发件人: Noel Chiappa [mailto:[email-masked]]
> 发送时间: 2007年10月18日 17:11
> 收件人: [email-masked]
> 主题: re: [RRG] cache issues in LISP and CONS
> 
Great idea! It looks like BGP damping mechanism, isn't it? 
How to keep the cached mapping, especially those in ITR in real-time? Use
small TTL? This will result in frequent query/reply which is acceptable for
host but not acceptable for router. If the mapping server is a host, is that
practical for forwarding the initial traffic with caching miss? If the
mapping server is a router, can it bear for frequent request/reply pressure?
> I think that is probably acceptable.
I agree with your opinion.
> (the ITR would have to talk to the rCAR).
Not just simple, but also no need to consider how to keep the cached mapping
in real-time and no loss of the initial packets with caching miss. Of
course, it depends on a distributed mapping and forwarding mechanism.

Xiaohu XU

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 18 Oct 2007 12:47:04 -0400 (EDT)

> From: <[email-masked]>

    > I thought the intention was somehow to have the mapping system partly
    > responsible for multi-homing (ID could map to multiple edge routers).
    > Surely if we need to introduce aggressive caching it would make
    > multi-home failover slow?

Ow. Good question! This margin is definitely too small to fully explore this!
But I think the answer is no, generally.

First, you have to distinguish between a couple of cases; ongoing
communications which were already in progress when the failure happens, and
new communications.

Caching will not have much impact on the ongoing communications cases - not
if the cached entries include mappings from EID's to RLOC sets, and not just
individual RLOC's.

I mean, whether there is caching or not, in either case there is an entity X
has is reachable via a number of RLOC's, and when one stops working, other
entities Y1...YN which are communicating with X need to find that out, so
they can switch to other RLOC's. Whether the Ys got those RLOC sets by
communicating directly with X's aCAR, or those RLOC sets were cached, there's
no difference.

Of course, then on has to decide whether each Ym is supposed to figure it out
on their own, or whether some other agent Q does it on their behalf, and then
notifies all the Ym, and if you do that how does Q know where all the Ym are,
yadda, yadda.

(See:

  http://ana-3.lcs.mit.edu/~jnc/tech/nsrg/multihoming_points.txt
  http://ana-3.lcs.mit.edu/~jnc/tech/nsrg/multihoming_more.txt

for a bit more thinking about what has to happen, and how to minimize
the overhead, in all that 'recovering from a failure' stuff.)

Caching might have an impact on the new communication cases - but only if one
assumes that on a temporary failure, the aCAR entries will be updated to
remove the 'broken' RLOC. If not, caching clearly has no effect.

I'm unsure that we will update the mapping database, any more than we update
the DNS in such cases now. Although I suppose we are talking about doing
mobility with this mapping system, so I suppose it's possible.

Also, if we do support multihoming failover for ongoing communication (above)
those mechanisms will also work in this case, to find out that there's a
non-working RLOC, and stop using it, so if we solve that one, we've
automatically solved this one (although we'll still have a performance hit,
as we'll have to go through the 'discover RLOC Rx1 isn't working' cycle).

This is just scratching the surface of a complex topic; I don't know if
anyone has analyzed in detail how we will support the various kinds of
multi-homing, and yes, that's something that should be done 'soon'. Again,
there are complex questions of performance versus complexity versus
overhead...

    > Also it would make it hard for the mapping system to provide traffic
    > engineering?

It depends on whether (and if so, how often) doing traffic engineering would
require changing the EID->RLOC binding(s). If so, I can imagine e.g. putting
smaller lifetimes on binding entries as a way to do this. Yes, that will
increase the overhead of operating the system, but TANSTAAFL.

Note, however, that in this case it's probably not the end of the world if
someone keeps using an old EID->RLOC binding, unlike the 'busted link' case
above. There, keep using the old binding -> no communication. Here, keep
using the old binding -> traffic using that old binding for a while (until it
times out) takes a path other than the desired one.

<Repeat previous closing comment...>

	Noel

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 18 Oct 2007 18:12:35 -0700

> make it hard for the mapping system to provide traffic engineering?

According to the LISP design, locator reachability is not part of the  
mapping database. See draft-farinacci-lisp-04.txt for details on how  
locator reachability is done in the data-plane.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 18 Oct 2007 22:38:33 -0700

> brought up a few times on the list.

Ah know, everyone tends to focus on corner cases. But please remember  
this is only for the first source in the source-site sending to the  
first destination in the destination-site.

We have lived with this problem with ARP and ND for years. I know  
it's a bit different and localized to a LAN but server-based switch  
networks are really large with 10s of thousands of end-hosts  
attached, so this problem occurs more often than people would think  
and we have lived with it (because it isn't much of an issue IMO).

If we become too pedantic about solving this, it could lead to a very  
complicated design which will prohibit deployment as well.

So we have to carefully choose our poison.

> mapping requests may take a long time to be satisfied, this may result

If people think this is a show-stopper, we could recommend  
implementations queue small amounts of packets. But that causes  
unnecessary resource utilization in the implementation. Most IPv4/ARP  
(if not all) drop packets but the IPv6-ND test suites required to  
queue exactly one packet (and different Tahi tests indicated to queue  
either the first one or the last one). So how does queuing exactly  
one packet actually solve the problem.

Therefore, we have to watch what we ask for from a design.

> size of the global routing table.

The routes in the old topology are aggregatable RLOCs that map to  
topology. The routes (EID-prefixes) used in the new topology are  
highly aggregatable because it is based on allocation hierarchy. So  
the PI prefixes that were in the old topology can be a smaller set  
that are in the new topology.

We are very close to testing this alternate topology idea. We are  
close to testing it because it requires really no new code  
development to make it happen.

> other

The problem is not in the design. The problem is just a hard problem  
to solve.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 18 Oct 2007 22:41:53 -0700

> That's a interesting idea. Has the default mapper stuff been worked  

We have text in draft-farinacci-lisp-04.txt (been there since -00) on  
"re-encapsulating tunnel routers". The deployment would be like this:

o All ITRs would be configured with a default mapping of an EID- 
prefix of 0.0.0.0/0
   with one or more locators pointing to the default mapper.

o The default mapper would decap the packet, interrogate the inner DA  
EID and assuming
   it had more specific mappings, would either encapsulate to the  
next mapper along the
   way to the destination or directly to the ETR at the destination  
site.

o Then policy could decide if the ETR sends a Map-Reply back to the  
ITR so a direct
   path can be taken for subsequent packets, or continue to use the  
default-mapper path.

dino

---

From: <[email-masked]>
Date: Fri, 19 Oct 2007 11:38:35 +0300

Have you looked at the Behive replication framework? The authors have
demonstartrated it's use as DNS replacement (CoDoNS). It does proactive
popularity based replication, and allows you to meet arbitrary average
lookup latencies (O(1)). Based on the CoDoNS paper
(http://www.cs.cornell.edu/people/egs/beehive/codons-sigcomm04/index.htm
l) the system outperforms DNS on all metrics.

The Behive overview is on the same paper:

http://www.cs.cornell.edu/people/egs/beehive/codons-sigcomm04/node12.htm
l

I have't tried to apply this to the mapping problem between EIDs and
RLOCs, but since Behive is prefix based, so there might be a beautiful
application of it to EID that have some hierarchy in them (=prefix).

Further I believe the mapping system should be such that it stays within
the core, i.e. all the mappings are resolvable within the BGP routable
core, so that resolving the mappings does not depend on any such
mappings itself!

	Jarno  

>Of ext Noel Chiappa
>Sent: 18 October, 2007 18:11
>To: [email-masked]
>Cc: [email-masked]
>Subject: re: [RRG] cache issues in LISP and CONS
>
>I spent a lot of time thinking about that, and finally came up 
>with what I think is a very efficient (in terms of overhead), 
>and extremely effective (in terms of correctly identifying 
>which mappings are widely used) system for deciding which 
>entries to cache in the CDRs.
>
>Basically, it works by starting with the actual mappings in 
>the aCARs; those entries have to always exist anyway, so it is 
>just an extra field in those entries, which gets incremented 
>any time the mapping is requested. When the aCARs notice a lot 
>of requests for a particular mapping, they suggest to their 
>parent CDR(s) that they cache that mapping. The same process 
>then repeats at each CDR level.
>
>We will have to tune it a bit, and adjust the constants (i.e. 
>how many requests are enough to trigger the upward cache) but 
>the basic mechanism is very good.
>
>
>Bandwidth is not necessarily the same as number of 
>connections, and the need for a mapping only exists when a 
>connection is opened. Since my understanding is that most P2P 
>traffic is for large media files, I suspect that they account 
>for a smaller percentage of connection openings. Also, since 
>they are for large files, if they take a few extra 
>tens/hundreds of milliseconds to start, I think that is 
>probably acceptable.
>
>Also, the second optimization I mentioned (having the 
>EID->RLOC mapping for the source carried along with the 
>request for the EID->RLOC mapping for the
>destination) will help P2P connections too (since it helps 
>*every* connection).
>
>Of course, if we were designing the entire network from 
>scratch, we would probably have the mapping system return both 
>the EID and RLOC, or something like that; it doesn't make 
>sense to have two separate resolution cycles.
>However, we have to live with what it already out there, which 
>means this resolution step has to be a separate system.
>
>
>So, if you can get 'good enough' performace without the cache, 
>you don't have to have it.
>
>What would be the benefit to not having the ITR cache entries? 
>Making them simpler? The disadvantage is that every connection 
>would be slower to open (the ITR would have to talk to the rCAR).
>
>	Noel
>
>--

---

From: Scott Brim <[email-masked]>
Date: Mon, 22 Oct 2007 09:54:57 -0400

On 18 Oct 2007 at 11:11 -0400, Noel Chiappa allegedly wrote:
> Basically, it works by starting with the actual mappings in the
> aCARs; those entries have to always exist anyway, so it is just an
> extra field in those entries, which gets incremented any time the
> mapping is requested. When the aCARs notice a lot of requests for a
> particular mapping, they suggest to their parent CDR(s) that they
> cache that mapping. The same process then repeats at each CDR level.

If it is just about request rate, then I see no reason for the aCAR to
inform its upstream nodes of anything.  Its upstream nodes are already
quite aware of how many requests are being made for various prefixes,
and the aCAR is not aware of conditions under which the CDR is
operating.  I don't think it's good to design in interdependency when
an individual CDR has all the information the aCAR could give it, plus
more that the aCAR does not know about.  A cache system will cause
frequently requested information to be present in the intermediate
nodes.  It's simple and it doesn't depend on control exchanges.  

On the other hand, Vince pointed out that communication between an
aCAR and its immediate upstream CDR could be used to communicate "high
load experienced", and affect which aCARs the CDR [cluster] sends
requests to. 

Scott

---

From: [email-masked] (Noel Chiappa)
Date: Mon, 22 Oct 2007 10:36:37 -0400 (EDT)

>> very efficient (in terms of overhead), and extremely effective (in
    >> terms of correctly identifying which mappings are widely used) system
    >> for deciding which entries to cache in the CDRs.

    > quite aware of how many requests are being made for various prefixes
    > ...
    > I don't think it's good to design in interdependency when an individual
    > CDR has all the information the aCAR could give it .. A cache system
    > will cause frequently requested information to be present in the
    > intermediate nodes. It's simple and it doesn't depend on control
    > exchanges.

The issue is not who has what information, but rather the size of the cache
one would need in a CDR (particularly a top-level CDR) for that cache to be
effective.

This does assume that these caches are not intended to cache *everything*;
i.e. they'd have to have some sort of algorithm to decide what to cache, and
I'm assuming one would use some sort of LRU algorithm to do that. If you're
simply going to cache everything, than yeah, one doesn't need that 'advice
from the leaves up' algorithm - or, indeed, *any* algorithm to decide what to
keep, and what to discard. I don't know if a 'cache-everything' strategy is
viable - maybe it is, I just assumed it wasn't, but I haven't done any
back-of-the-envelope numbers to see if it would be.

But, if one has an incomplete cache, then one has the issue of how to decide
what to keep in it, and to do that, you have to keep some sort of history,
which is usually cache entries themselves. If the history/cache isn't big
enough, requests for entries which are not often repeated will flush the
entries which are (i.e. which ought to be cached). I tried for a while to
tackle that problem, of how big to make the caches, to ensure that they do
wind up holding the commonly-used bindings (which is a moving target anyway,
based on usage patters, the contents of the distributed database, etc). I
also tried more complex schemes (two-level caches, etc).

In the end, the scheme I mentioned above seemed better; it simply moves that
state out to the leaves, which have to have a copy of every entry anyway, so
it's just an extra entry in all those pre-existing database entries. It is
much easier to tune, and much less sensitive to changing usage patterns (which
could cause hit rates to fall drastically if they cause caches to get
flushed).

I dunno, maybe the whole concept of partial caches is a bad idea, and we
should just cache everything. Probably time to do some BOTE engineering...

	Noel

---

From: Scott Brim <[email-masked]>
Date: Mon, 22 Oct 2007 11:18:23 -0400

On 22 Oct 2007 at 10:36 -0400, Noel Chiappa allegedly wrote:
> The issue is not who has what information, but rather the size of
> the cache one would need in a CDR (particularly a top-level CDR) for
> that cache to be effective.

I agree with your goal of not requiring a full cache, but the main
problem is that the aCAR has no idea what a CDR's operating
environment is, so how can the aCAR predict when "it would be good to
cache this"?  All the aCAR can tell the CDR is what *it* is
experiencing.  Telling the CDR when to cache will certainly be either
too early or too late -- unless of course you built knowlege of CDR
performance into the aCAR, which sounds like a horrible idea.

Let's go with your assumption that the CDR has too many "chaff"
queries, i.e. there are so many one-off mapping requests that the
"occasional" ones (not rare, but not frequent either) are pushed out
of the cache.  I guess I would accept something in the map-reply that
wouldn't "advise" the CDR on what to do, but might indicate the aCAR's
experienced rate of queries ... but caching by CDRs *other* than the
one in question will reduce that rate to be the same as the "rare"
rate.  At a system level, an aCAR reports how the behavior of *all*
CDRs is affecting it, and a *single* CDR tries to figure out how to
behave in response?

So again, I agree with the goal, but I don't like the mechanism.

This would be a good thing to simulate.

swb

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Mon, 22 Oct 2007 19:13:38 +0200

> Could this be a fundamental problem with the design, or are there  

What I'd like to see here is a two-pronged system: a standard issue  
ITR/ETR system that handles most of the traffic, and an increased  
stretch overlay network that can handle the packets that run into  
cache misses.

Let me explain how I envision the overlay network. Suppose  
100.0.0.0/6 is used for PI address space in this scheme, where each  
user has a /24 = 256k PI users. That would be too much to add to our  
existing routing table or to flat route in an overlay network. But  
flat routing 16k is doable so we make 16 rendezvous points that each  
handle a /10 out of that 100.0.0.0/6 block. So user 102.34.56.0/24  
registers with the rendezvous points that hand 102.0.0.0/10. These  
rendezvous points inject their prefixes into regular BGP so the users  
are reachable by routing the traffic to the closest rendezvous point  
where it is tunneled back to the user.

Obviously such a path is not exactly efficient, but since it's only  
needed for cache misses, this isn't much of an issue. However, this  
infrastructure does allow us to make a good caching mechanism without  
imposing unreasonable performance requirements upon it. Also, it  
would be possible to defer a mapping lookup for a short time until  
it's clear that the communication is at least somewhat long-lived.

It would even be possible to encapsulate the data packet into a  
mapping request for additional efficiency...

I believe such a system can easily be created in a Frankensteinian  
manner from the proposals currently on the table.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 23 Oct 2007 15:33:38 +0200

> stretch overlay network that can handle the packets that run into  

Replying to myself - always cool.

I just realized that such an architecture could have some nice  
security benefits. The access to the overlay network could be rate  
limited, and direct communication using the ITR/ETR system could be  
subject to negotiation of credentials. This could potentially help  
against denial of service attacks.

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Wed, 24 Oct 2007 03:36:39 -0700

> From: [email-masked] [mailto:[email-masked]] On Behalf 
<snip>
> I just realized that such an architecture could have some 
> nice security benefits. The access to the overlay network 
> could be rate limited, and direct communication using the 
> ITR/ETR system could be subject to negotiation of 
> credentials. This could potentially help against denial of 
> service attacks.

I think we need to do some more thinking about whether with the overlay
network it is better to send the data packets themselves, or just Map
Request packets. 

The rate limiting of data to the overlay network could itself become a
vector for DoS attacks.  If I flood a site with random sourced syns, the
site will start accessing the overlay network to discover mapping
information for all the various syn-ack packets.  If this resultant
flood of requests is rate limited, then I could starve legitimate
requests for mapping from that site.  

The whole overlay system, especially if it shares fate with other
network elements, could have some interesting vulnerabilities.

LISP itself has a light form of authentication in the form of return
routability checks with a nonce.

I think you do describe one of the key benefits of a map/encap scheme
like LISP however:  Having persistent EIDs that are visible in the
inner-header that a network element can classify and apply policy on.

-Darrel

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 25 Oct 2007 00:24:10 +0200

> network it is better to send the data packets themselves, or just Map

Agree.

> requests for mapping from that site.

That would depend on the design. First of all, I think I'd defer the  
mapping request until the third packet in the three-way handshake to  
avoid mapping floods caused by SYN floods.

And if there are enough rendezvous points it becomes hard to make the  
path from each towards the target destination choke. Then again, only  
doing that for a few may be enough of a nuisance. However, each ITR  
should rate limit packets it injects into the overlay network and  
mapping requests that it generates. That means that DoS attacks are  
felt close to the source rather than at the target, which is good  
because close to the target it's easier to deal with them.

If the overlay network doesn't let a useful amount of traffic  
through, it should still be possible to obtain mappings and the  
traffic will start to flow after an initial delay. If the ETR detects  
too much or abusive traffic from a particular ITR, it can then tell  
that ITR to stop sending traffic. We may want to have the option to  
require a certain nonce in each packet to make sure that ITRs only  
get to send traffic after being authorized to do so by the ETR.

There are no magic bullets in (D)DoS mitigation, but I think useful  
results can be gained here.

> network elements, could have some interesting vulnerabilities.

It's important to consider all eventualities, because that's exactly  
what the attackers are going to do.

> routability checks with a nonce.

The big problem today is that people can inject large amounts of  
abusive traffic and can hide in large numbers or by spoofing their  
source addresses. Obtaining mappings means revealing a working source  
address, and after that, any non-conformant behavior, such as failing  
to rate limit properly, can easily be spotted and dealt with though  
offline methods.