Subject: [RRG] Tunnel fragmentation/reassembly for RRG map-and-encaps architectures

From: "Templin, Fred L" <[email-masked]>
Date: Thu, 20 Dec 2007 10:52:26 -0800

Just to have disclosure for the current understanding
of this out on the list, the full proposal is given
below. LISP is used as the example RRG map-and-encaps
architecture, but the same approach can be applied to
any such scheme: 

1) Add two flag bits plus an ID field to the LISP
header. The "Frag" flag is 0/1 if the packet is
unfragmented/fragmented, and the "Seg" flag is 0/1
if this packet is the A or B Segment of the original
packet. The ID field can be a 16-bit extension to
the IPv4 id, or a 32-bit ID that is independent of
the IPv4 id (FFS). To save encapsulation overhead,
the two flag bits could share the same word/longword
as the LISP ID field to give a 14+2 [ID/flags] field
or a 30+2 [ID/flags] field and still leave enough ID
bits to avoid reassembly misassociations.

2) Before the ITR knows whether the ITR->ETR tunnel
pathMTU can handle original packets up to 1500 bytes,
it sends 1500- original packets into the tunnel as
either 1-fragment or 2-fragment packets of no more
than (750+ENCAPS) bytes each. The assumption is that
packets of this size will NEVER be dropped due to an
MTU restriction in the ITR->ETR tunnel, which may
have implications for the placement of the ITR and
ETR in the network. (To the best of my knowledge,
the 750 byte fragment suggestion is attributed to
Iljitsch van Beijnum, however RFC1812 does suggest
that sending equal-sized fragments is a legitimate
fragmentation strategy.)

3) The ITR creates 2-fragment packets by splitting
the original packet into A and B segments. Both
segments set the "Frag" flag. The A segment sets
"Seg=0" and the B segment sets "Seg=1". Both segments
set corresponding values in the LISP ID field. (The
A and B segments should set different values in the
IPv4 ID, since the two packets might otherwise appear
as duplicates.)

4) While sending 2-fragment packets, the ITR sends
1500 byte sprite-mtu probes to the ETR. If it gets
probe replies back, it can stop sending 2-fragment
packets and begin sending 1-fragment packets. If the
ITR subsequently gets a packet-too-big, it can resume
sending 2-fragment packets and try probing again later.

5) The ITR admits 1501+ packets into the tunnel without
fragmenting them. FFS, the ITR either admits the packets
(if they are no larger than the outgoing IPv4 interface)
and sends NO PTB feedback back to the original source
(stateless), or admits the packet and also sends back a
PTB. In the latter case, the ITR also sends sprite-mtu
probes to determine the maximum packet size that the
ITR->ETR path can accommodate. When a maximum size is
determined, the ITR then has an accurate path MTU value
that it can use to determine when to send a PTB back to
the original source. But, this requires extra state in
the ITR. In both cases, the assumption is that original
sources that send 1501+ packets are also doing something
like RFC4821. This should appear in a BCP document.

6) The ETR must reassemble any 2-fragment packets. It
does so through simple concatenation of the A and B
parts of the 2-fragment packet. The ETR can greatly
reduce the memory required for reassembly buffers by
actively discarding any reassemblies that appear to
have no chance of completion. This assumes that any
packet reordering on the ITR->ETR path will be on the
order of a small number of positions (~100 or less),
and that any gross reordering will be short-lived
in nature. (In fact, if the ETR does this it might
be possible to drop back to using plain-old IPv4
fragmentation and reassembly instead of adding new
encapsulation overhead to LISP. But then, there would
still only be a 16-bit IPv4 ip_id which some have
argued is a problem. This is FFS.) In both cases,
the ETR must configure a reassembly buffer size of
at least 2KB to accommodate reassembly for 1500-
original packets plus any outer layers of encapsulation
including the LISP/UDP/IPv4 encapsulation and any
additional encapsulations such as IPsec/ESP, L2TP,
etc. To the best of my knowledge, the 2KB reassembly
requirement idea is attributed to a list posting from
Dan Romascanu (however I had heard it mentioned at
least once previously in private conversation) and
should also appear in a BCP document. 

7) The idea of a 2-fragment maximum for fragmentation
is something that many of us have talked about over
the years in on- and off-list discussions and has also
appeared in some drafts. I believe Robin Whittle has
more recently been talking about this idea with specific
reference to the RRG problem space, but the idea itself
is not new.

8) Again, the above can apply equally to *any*
map-and-encaps tunnel-oriented proposal for RRG,
and not just LISP. 

Fred
[email-masked]

PS: If I have mis-attributed any of the ideas, or failed
    to attribute others, please let me know. I recognize
    that it can be very difficult to keep track of who
    thought of what first...

> -----Original Message-----
> From: Templin, Fred L 
> Sent: Tuesday, December 18, 2007 2:25 PM
> To: Routing Research Group list
> Subject: [RRG] LISP Fragmentation and Reassembly
> 
> "sprite-mtu" identifies conditions under which the ITR
> must fragment outer packets which the ETR must reassemble.
> (And, from the list discussions, we seem to be reaching
> consensus that any reassembly at the ETR must be limited
> to 1500 byte or smaller original packets.) But, sprite-mtu
> further defines a "dance" that needs to be orchestrated
> between the ITR and ETR when IPv4 fragmentation and
> reassembly are occurring, which may be too onerous for
> some deployments.
> 
> The reason for the dance is that the 16-bit ip_id needs
> to be carefully monitored when IPv4 fragmentation is
> occurring such that any reassembly misassociations are
> detected. But, if we disable IPv4 fragmentation and instead
> define a LISP-specific fragmentation and reassembly at
> the LISP shim layer immediately above UDP, then we can
> have the shim layer insert a 32-bit id which would avoid
> the RFC4963 issues and eliminate the need for close
> coordination with the ETR.
> 
> I have already specified such a mechanism for DHCP:
> 
> http://www.ietf.org/internet-drafts/draft-templin-dhcpmtu-00.txt
> 
> and a similar specification for LISP would be nearly identical.
> The penalty is extra LISP encapsulation overhead, but the
> benefit of avoiding the need for synchronization between the
> ITR and ETR is substantial. (In fact, it may be essential to
> the successful deployment of LISP.) Also, when the path MTU is
> large enough to accommodate all 1500 byte and smaller packets
> without fragmentation, the extra encapsulation overhead can
> be eliminated.
> 
> So, I am inclined to write this up as a draft but probably
> won't be able to get to it until after the 1st of the year.
> It could either go as part of the sprite-mtu draft, or as
> an independent draft like the DHCP one. But better yet
> would probably be to just put it directly into the LISP
> specification itself. What does anyone think?
> 
> Thanks - Fred
> [email-masked] 
> 
> --
> 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
> 

--
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: Iljitsch van Beijnum <[email-masked]>
Date: Fri, 21 Dec 2007 21:21:56 +0100

On 20 dec 2007, at 19:52, Templin, Fred L wrote:

> below.

I think this is a good way to make the fragmentation issue as painless  
as possible IF we choose to accept it, with one important and a minor  
caveat.

So at some point we should try to get consensus about whether we want  
to allow fragmentation or not. We may as well do that now...

The important caveat is: when do you send back a too big message to  
the original source? This is clearly what needs to happen if the  
original source performs path MTU discovery properly, which is  
fortunately still what most (right?) hosts do. The problem is that you  
can't simply send too bigs for all packets that are too big, because  
that way you would be performing a denial-of-service attack on hosts  
that don't honor these messages. And, more imporantly, you'd probably  
be wasting local CPU cycles unless you have silicon for ICMP  
generation. Would simply rate limiting too bigs be a workable  
approach? I guess it would be if you don't drop the packet but  
fragment it, although that behavior wouldn't be expected by the source  
host (but hey, stranger things have happened in the name of the  
unreliable datagram). If you drop the packet, you'd probably do that  
for several in a row so TCP would be taking a nap for a while when  
that happens.

> than (750+ENCAPS) bytes each.

This can probably be further optimized to be aligned with memory  
buffers.

We could even generalize this to: =< 1024 or > 2048 are never  
fragmented, 1024 - 2047 byte packets are split into a packet with the  
first 1024 bytes of the original packet and a second packet with the  
remaining bytes.

(Making the packets roughly equal size minimizes the chances of  
subsequent fragmentation and making the first no smaller than the  
second avoids the first one from arriving first when the two fragments  
travel over parallel paths, both issues that I don't think are all  
that important here.)

> In both cases, the assumption is that original

If we use a few bits in the encapsulation header to ask the  
decapsulator to send ACKs for selected packets (see my message to Dino  
earlier this week, and probably one later today) then the encapsulator  
could do its own RFC 4821 based on the data packets. I think that  
would be extremely useful.

---

From: Brian E Carpenter <[email-masked]>
Date: Sat, 22 Dec 2007 13:47:31 +1300

I'm still not sure that I get the point of any of this.

The Internet architecture says that end-systems are
responsible for e2e issues, and PMTU sure seems like
an e2e issue. It's a blot on the architecture that
IPv4 permits fragmentation en route; imagine a world
in which DF is set in every IPv4 packet - hosts would
end up discovering (or configuring) a suitable MTU.
That's also how IPv6 works.

I think it's another blot on the architecture for
a map-and-encap solution to even touch this problem -
except for a SHOULD statement about the MTU to be provided
by every tunnel, which should obviously be a bit bigger
than the required IPv6 Internet MTU.

    Brian

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 21 Dec 2007 17:08:35 -0800

> architecture, but the same approach can be applied to

See comments inline. For full disclosure, I don't endorse this proposal.

> either 1-fragment or 2-fragment packets of no more

So we are going to double the packets sent everywhere until we find  
out? This doesn't sound like a good idea to me.

> sending 2-fragment packets and try probing again later.

This requires the ITR to keep state for each ETR. It doesn't do this  
now. This is a huge requirement on the ITR which I object to.

> 6) The ETR must reassemble any 2-fragment packets. It

This is a non-starter in router products unless you *force* software  
switching. And even if you *force* software switching, it's a great  
DOS attack against the buffer system of the router. Leave malicious  
out of the way. If a Google ETR is recieving from 100K places, you  
think the router can store 100K 1500-byte sized packet for any length  
of time (1-2 seconds).

> have no chance of completion. This assumes that any

And how does the ETR determine there is no chance of completion?  
Please don't answer.

Dino

---

From: Tony Li <[email-masked]>
Date: Fri, 21 Dec 2007 17:51:03 -0800

Hi Brian,

> I'm still not sure that I get the point of any of this.

Well, let's try to fix that.

> an e2e issue.

Except that it's not.  For PMTUD discovery to operate, the network  
MUST respond with ICMP messages and those messages MUST make it  
through to the source.  Now, theoretically, the host would simply  
back down its MTU if there is a packet loss, but pragmatically, not  
enough implementations do that correctly for this to be a truly  
adequate solution.  [Aside: if you feel that we should move that  
direction, we should deprecate the ICMP messages.]

Thus, it's not an e2e issue, it has the network involved in it, up to  
the elbows.

> It's a blot on the architecture that

Correction: doesn't work.

Even with correctly implemented hosts and routers, there are two  
major problems:

Problem 1) ICMP filtering
Thanks to the prevalence of DoS attacks, many end-sites filter out  
ICMP messages.  While most static filters are capable of being  
configured to pass ICMP PTB messages, most site administrators have  
not been so careful as to be that specific and instead simply drop  
all inbound ICMP.  This effectively breaks PMTUD.  Even if  
administrators did pass PTB messages, they'd simply get DoSed that  
way too, or MTU'ed down to 576.  [Aside: In an insecure environment,  
the network CANNOT effectively signal to the host.  This is a major  
architectural issue.]

Problem 2) Tunneling
If a packet is tunneled, then the source address on the tunneled  
packet is that of the router that performed the encapsulation, NOT  
the original source host.  Thus, if there is an MTU issue in the  
middle of the tunnel span, the PTB message is sent to the  
encapsulating router that cannot effectively do anything about the  
issue.  This  problem is aggravated because the tunnel itself  
detracts from the MTU as seen by the source.

> than the required IPv6 Internet MTU.

The blot on the architecture is that PMTUD doesn't work and folks  
seem to continue to be in denial about it.  We need to fix it,  
completely independently of RRG issues.  Further, if we want to want  
to use any kind of tunneling in our solution, we need to address this  
problem head on.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Sat, 22 Dec 2007 17:08:34 +1300

I guess I wasn't blunt enough.

PMTUD has been broken and unreliable for years, and that
hasn't stopped the Internet from working. The reason is
that hosts and applications have found methods of working
successfully that don't depend on PMTUD. Let's not even
debate what those methods are; it doesn't matter for
this discussion.

I don't see why the (virtual) links that are created by
a map-and-encap solution should be held to a higher standard
than any other link-layer technology.

     Brian

On 2007-12-22 14:51, Tony Li wrote:
> Except that it's not.  For PMTUD discovery to operate, the network MUST 
> respond with ICMP messages and those messages MUST make it through to 
> the source.  Now, theoretically, the host would simply back down its MTU 
> if there is a packet loss, but pragmatically, not enough implementations 
> do that correctly for this to be a truly adequate solution.  [Aside: if 
> you feel that we should move that direction, we should deprecate the 
> ICMP messages.]
> 
> Even with correctly implemented hosts and routers, there are two major 
> problems:
> 
> Thanks to the prevalence of DoS attacks, many end-sites filter out ICMP 
> messages.  While most static filters are capable of being configured to 
> pass ICMP PTB messages, most site administrators have not been so 
> careful as to be that specific and instead simply drop all inbound 
> ICMP.  This effectively breaks PMTUD.  Even if administrators did pass 
> PTB messages, they'd simply get DoSed that way too, or MTU'ed down to 
> 576.  [Aside: In an insecure environment, the network CANNOT effectively 
> signal to the host.  This is a major architectural issue.]
> 
> Problem 2) Tunneling
> If a packet is tunneled, then the source address on the tunneled packet 
> is that of the router that performed the encapsulation, NOT the original 
> source host.  Thus, if there is an MTU issue in the middle of the tunnel 
> span, the PTB message is sent to the encapsulating router that cannot 
> effectively do anything about the issue.  This  problem is aggravated 
> because the tunnel itself detracts from the MTU as seen by the source.
> 
> 
> The blot on the architecture is that PMTUD doesn't work and folks seem 
> to continue to be in denial about it.  We need to fix it, completely 
> independently of RRG issues.  Further, if we want to want to use any 
> kind of tunneling in our solution, we need to address this problem head on.
> 
> Tony
>

---

From: Tony Li <[email-masked]>
Date: Fri, 21 Dec 2007 21:48:26 -0800

> debate what those methods are; it doesn't matter for

In fact, it very much does.  The way that folks have worked around it  
for years is to go around and manually turn down MTUs on end hosts,  
leaving the Internet in a continual state of debugging and manual  
reconfiguration.

> than any other link-layer technology.

Other link-layer technologies are not creating this problem.   
Tunneling is.

And as long as we're going to make significant architectural changes,  
we should be making things cleaner than when we got here.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Sun, 23 Dec 2007 15:59:13 +1300

> leaving the Internet in a continual state of debugging and manual 

There's some of that, but there are also apps that tune down their
application PDU size until things work. I guess my instinct is that
this problem can only be generically solved at transport level
and above, as RFC 4821 begins to recognize.
> Other link-layer technologies are not creating this problem.  Tunneling is.

But it wouldn't, if we simply placed a (recursive) requirement on tunnels
to deliver adequate MTU at the innermost level. Which is of course
an operational, not a protocol, solution.
> 
> And as long as we're going to make significant architectural changes, we 
> should be making things cleaner than when we got here.

I can't disagree with the principle. But to my taste, we're headed towards
complexity instead of simplicity.

Also - isn't this issue applicable to all the VPNish things being
developed these days, i.e. signiicantly broader than RRG?

     Brian

---

From: Tony Li <[email-masked]>
Date: Sat, 22 Dec 2007 19:24:53 -0800

> and above, as RFC 4821 begins to recognize.

Agreed.  If we knew that 4821 was going to make it into a  
predominance of hosts, this wouldn't be nearly the issue that it is...

> an operational, not a protocol, solution.

True, but it's not a reasonable operational requirement due to the  
large deployed base of 1500B MTU media.

>> And as long as we're going to make significant architectural  
>> changes, we should be making things cleaner than when we got here.
>

Agreed.  I hope that we can do better.

> developed these days, i.e. signiicantly broader than RRG?

In some ways, yes.  It has been an issue since we started tunneling  
over IP and it's not going to go away soon.  The big difference, the  
reason why RRG has to solve this if we want to tunnel, is that we're  
making tunneling a first class part of the architecture.  If LISP  
were to be deployed ubiquitously, for example, we'd end up with  
something like 99.99% of all Internet core traffic being tunneled and  
being susceptible to the PMTUD problems that we've discussed.  This  
would include tunneling a large percentage of the folks without their  
knowledge and consent.  This is very different than inflicting pain  
on a small subset of sophisticated folks who are using a specialized  
application.

Tony

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 23 Dec 2007 09:49:08 -0500

I keep reading the debates about tunnel MTU, and wondering about two
practical observations.

Firstly, while there are many concerns about the way Mobile-IP works,
folks don't complain about applications not working over MIP, even MIPv4
(which requires tunnels.)

Secondly, there are a lot of VPNs.  Many of them provided by
middleboxes.  They seem to use tunnels exactly the way the proposals on
the table do.  And they seem to work.  With a wide range of applications.

So while the theory clearly says that there is a problem with tunnel
mTU, the practice seems to suggest that it works.

Is there some other dimension here that explains the mismatch?

Thank you,
Joel M. Halpern

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Sun, 23 Dec 2007 17:07:15 +0100

> Is there some other dimension here that explains the mismatch?

There aren't any problems when the least capable point in the path is  
at one of the ends. In that case, the host in question obviously won't  
be sending packets that are larger than the path can support, and the  
TCP MSS option makes sure that the other end doesn't either. (In  
theory you could have trouble with non-TCP protocols but most non-TCP  
traffic uses small packets anyway, the apps that don't tend to use a  
somewhat conservative packet size and often the DF bit isn't set.)

The problematic situation is the one where the point with the smallest  
MTU is somewhere in the middle of the path. This happens when users  
have an ethernet LAN and a CPE that terminates PPP over ethernet, for  
instance. To avoid support calls, those CPEs intercept TCP SYN packets  
and modify the TCP MSS option to reflect the MTU of the PPPoE link  
(1492). I'm sure this is what happens in a lot of VPN gear, too.

Note that the support calls I mentioned aren't theoretical: from  
experience, I can tell you those WILL happen if you don't do this (or  
clear the DF bit so that fragmentation can happen anyway).

---

From: Tony Li <[email-masked]>
Date: Sun, 23 Dec 2007 09:22:56 -0800

> (which requires tunnels.)

Can I ask, how broadly are people using MIP?  I don't know of anyone  
using it today.

> Is there some other dimension here that explains the mismatch?

How many of those VPNs are based on MPLS?

I think I can tell you without violating too many corporate secrets  
that anytime Cisco sees a customer deploying an L3 tunneling solution  
that the MTU is an issue, usually resolved by a manual workaround.

Tony

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 23 Dec 2007 12:44:44 -0500

With regard to Mobile-IP, it is not being used much as originally
envisioned.  However, it is beign used quite heavily by a number of
technologies with mobility needs.

While there are provider based VPNs, some (maybe even many) of which use
MPLS, there are also lots of CE based VPNs which use other technologies
(IPSec for one example, but there are many others.)
It has been years since I had to deploy those, so I do not know what
hacks people are using to make the applications work.  But most
customers do assume that the apps work.  And they seem to be correct.

Yours,
Joel

Tony Li wrote:
> I think I can tell you without violating too many corporate secrets that
> anytime Cisco sees a customer deploying an L3 tunneling solution that
> the MTU is an issue, usually resolved by a manual workaround.
> 
> Tony
>

---

From: Robert Raszuk <[email-masked]>
Date: Sun, 23 Dec 2007 13:57:34 -0800

Joel,

 > hacks people are using to make the applications work.

The hacks usually are:

* Setting manually the right MTU on the host. Pain like hell as you are 
never sure what to set to be optimal.

* Setting MTU on CE and fragment there in case of IPSec VPNs

* Setting mpls MTU on PEs and fragment there. To add there are knobs to 
overwrite DF bit if set pretty much blindly.

But just to add the MTU issue is not only related to tunneling. We 
pretty much have the same issue to run over DSL transport. And AFAIK 
there is no automation to fix it. The manual labor to set it correctly 
is not trival .. Example: http://www.dslreports.com/faq/5793 And this is 
only on the DSL single p2p link.

The above procedure for sure will not work on the Internet wide 
tunneling as the links given tunnel takes may be changing dynamically.

Cheers,
R.

---

From: "Templin, Fred L" <[email-masked]>
Date: Wed, 2 Jan 2008 09:48:14 -0800

Back from the holidays, I guess I'll begin the new year by
answering the only item I was explicitly asked *not* to: 

> From: Dino Farinacci [mailto:[email-masked]] 
> Sent: Friday, December 21, 2007 5:09 PM
> To: Templin, Fred L
> Cc: Routing Research Group list
> Subject: Re: [RRG] Tunnel fragmentation/reassembly for RRG 
> map-and-encaps architectures
... 
> And how does the ETR determine there is no chance of completion?  

Recent Linux 2.6.x kernel versions do exactly this; pull
a recent kernel distribution, edit net/ipv4/ip_fragment.c,
and search for "ip_frag_too_far". (This was pointed out by
Matt Mathis in an off-list discussion.)

Thanks - Fred

---

From: Brian Dickson <[email-masked]>
Date: Wed, 02 Jan 2008 13:38:39 -0500

Tony Li wrote:
>> I guess my instinct is that
> Agreed.  If we knew that 4821 was going to make it into a predominance 
> of hosts, this wouldn't be nearly the issue that it is...
>> to deliver adequate MTU at the innermost level. 
>
> The big difference, the reason why RRG has to solve this if we want to 
> tunnel, is that we're making tunneling a first class part of the 
> architecture.  If LISP were to be deployed ubiquitously, for example, 
> we'd end up with something like 99.99% of all Internet core traffic 
> being tunneled and being susceptible to the PMTUD problems that we've 
> discussed.  This would include tunneling a large percentage of the 
> folks without their knowledge and consent.  This is very different 
> than inflicting pain on a small subset of sophisticated folks who are 
> using a specialized application.
Between the PMTUD problem, and the "elephant in the room" (state 
signaling that needs to be handled *somewhere*), I am coming to a rather 
uncomfortable conclusion:

With or without LISP itself, the real problems that need to be solved, 
are intrinsically "transport"-ish.
Which means: if we want to have a "better than we got here" solution, 
which scales, works well, and has longevity (even across subsequent 
generations of network protocols), the place to tackle the problems is 
at the transport layer. (ugh.)

The "elephant in the room":
While LISP et al appear to solve some problems, when you look at it just 
the right way, the real problem is - how do you multihome, and detect, 
handle, and respond to failures on one of many paths available (i.e. 
"route around" the outage), in a scalable fashion?
In BGP with PI, i.e. using BGP for multihoming, the state is carried via 
BGP.
In LISP, the presumption is that the mapping stuff handles the state - 
but does that differ much from the BGP solution, other than moving the 
problem somewhere else? The state is still needed, and needs to be 
propogated in a timely fashion.

Is it (socially/politically/procedurally) possible for RRG to 
collectively say, we want the problem to be fixed, we are willing to 
work on fixing it, but it's not a routing problem?

(Consider the can of worms opened. Sorry.)

Brian Dickson

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 2 Jan 2008 10:43:32 -0800

> While LISP et al appear to solve some problems, when you look at it  
> just the right way, the real problem is - how do you multihome, and  
> detect, handle, and respond to failures on one of many paths  
> available (i.e. "route around" the outage), in a scalable fashion?
> In BGP with PI, i.e. using BGP for multihoming, the state is carried  
> via BGP.
> In LISP, the presumption is that the mapping stuff handles the state  
> - but does that differ much from the BGP solution, other than moving  
> the problem somewhere else? The state is still needed, and needs to  
> be propogated in a timely fashion.

Locator reachability and routing around failures is not in the mapping  
database. Please read draft-farinacci-lisp-05.txt section 6.3 for the  
locator reachability mechanism.

Dino

---

From: Tony Li <[email-masked]>
Date: Wed, 2 Jan 2008 10:50:46 -0800

On Jan 2, 2008, at 10:38 AM, Brian Dickson wrote:

> collectively say, we want the problem to be fixed, we are willing  
> to work on fixing it, but it's not a routing problem?

I know of no reason why we couldn't do that.  However, actually doing  
the work would probably require a different venue.

I suspect that it would take some time and effort to convince others  
that this is the right course of action.

Tony

---

From: Brian Dickson <[email-masked]>
Date: Wed, 02 Jan 2008 14:47:01 -0500

> locator reachability mechanism.
Hi, Dino,

My "elephant" wasn't directed at any specific locator/ID proposal in 
particular, but is common to them all.

That said, even if the reachability isn't in the database, it *is* 
kept/signaled between ITR/ETR tuples. The problem doesn't go away, it 
just gets pushed to the ITRs and ETRs.

Brian

P.S. Since the ITR/ETR use caches, and reactively populate the caches, 
IMHO, it's a step backwards, from CEF to pre-CEF bad-old-days. (Sorry. 
Old wounds still ache from time to time :-). Not so old if you include 
MSFC's...)

P.P.S. And not to harp on this, but the absence of active reachability 
awareness on the ITR/ETR nodes, other than for the immediate local info 
(default and CE/PE stuff), means lots of failure modes on the selected 
RLOC path take longer to notice, or even can't be detected or handled.

Things like black holes, routing loops, frame/packet smashing, errored 
links, etc., can cause data loss in one direction, without the ITR 
knowing or the ETR seeing the encapsulated packets.
This is acknowledge in the comment about there being a dependency on 
Host Unreachable ICMP messages, but that looks like a bit of an Achile's 
Heel.

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 2 Jan 2008 12:07:30 -0800

> particular, but is common to them all.

Right, I was commenting solely on your locator reachability comment.

> kept/signaled between ITR/ETR tuples. The problem doesn't go away,  
> it just gets pushed to the ITRs and ETRs.

Right, in the data-plane, with no extra messages other than the data  
itself.

> P.S. Since the ITR/ETR use caches, and reactively populate the  
> caches, IMHO, it's a step backwards, from CEF to pre-CEF bad-old- 
> days. (Sorry. Old wounds still ache from time to time :-). Not so  
> old if you include MSFC's...)

We are not talking about the same scale. I can sell you a 10 million  
entry cache, but you probably won't buy it.  ;-)

> Things like black holes, routing loops, frame/packet smashing,  
> errored links, etc., can cause data loss in one direction, without  
> the ITR knowing or the ETR seeing the encapsulated packets.

> Host Unreachable ICMP messages, but that looks like a bit of an  
> Achile's Heel.

So, one could also add something on top of the data-plane mechanism,  
but we strongly hesitate. Want to scale or want to solve every  
reachability problem?

Does the routing system today fix block holes, routing loops, etc...  
or do they contribute to it?

Dino

---

From: Brian Dickson <[email-masked]>
Date: Wed, 02 Jan 2008 15:31:26 -0500

Dino Farinacci wrote:
>> caches, IMHO, it's a step backwards, from CEF to pre-CEF 
>> bad-old-days. (Sorry. Old wounds still ache from time to time :-). 
>> Not so old if you include MSFC's...)
>
MacBook w/2GB running quagga - already have one, thanks. :-) :-)
> but we strongly hesitate. Want to scale or want to solve every 
Ideally, both. :-)
I'm not saying for sure it's possible, but it would be a laudable goal, yes?

If I think of something along those lines, I'll share. :-)

If there is a solution-space which would work equally well for IPv4 and 
IPv6, but which would only be really feasible (for address consideration 
reasons) in IPv6, would that be "good enough"?
> or do they contribute to it?
If an RLOC prefix is withdrawn from the DFZ, it would be better if the 
xTRs knew that rather than relying on ICMP. I'm just saying...

Brian

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 2 Jan 2008 12:37:28 -0800

>> We are not talking about the same scale. I can sell you a 10  
>> million entry cache, but you probably won't buy it.  ;-)
>>

We are not talking about the same sort of products either.  ;-) If  
this needs to go fast, the MacBook memory won't run at 40-100G.

>> So, one could also add something on top of the data-plane  
>> mechanism, but we strongly hesitate. Want to scale or want to solve  
>> every reachability problem?
> Ideally, both. :-)

We chose to start with something simple rather than put a lot of  
mechanism in up front.

> If there is a solution-space which would work equally well for IPv4  
> and IPv6, but which would only be really feasible (for address  
> consideration reasons) in IPv6, would that be "good enough"?

Well, the LISP proposal thinks we can.

>> Does the routing system today fix block holes, routing loops,  
>> etc... or do they contribute to it?
> If an RLOC prefix is withdrawn from the DFZ, it would be better if  
> the xTRs knew that rather than relying on ICMP. I'm just saying...

Sure, but there is aggregation, so you can't depend on it. That is,  
you can't depend on a lot of mechanism that is in the net. That is the  
hard part, that is the reasons we all need to make hard decisions,  
then just throwing more mechanism. Each new mechanism you add will add  
issues and barrier to deployment.

Dino

---

From: "Templin, Fred L" <[email-masked]>
Date: Thu, 3 Jan 2008 15:43:05 -0800

Iljitsch,

Please see below for some follow up on this one from
a couple of weeks back: 

> From: Iljitsch van Beijnum [mailto:[email-masked]] 
> Sent: Friday, December 21, 2007 12:22 PM
> To: Templin, Fred L

> for several in a row so TCP would be taking a nap for a while when  

If we can set a BCP threshold for DF=1 packets above which
the original source is expected to implement RFC4821, then
another possibility is to never have the ITR send back a
PTB under any circumstances. This means that we may have to
do some work to get medium-sized packets through the tunnel,
but admit the large and small ones unfragmented w/o ever
sending any PTBs.

I firmly believe we should establish a BCP that says
that original sources that send DF=1 packets of 1501+
bytes are strongly recommended to use RFC4821 (and may
get unpredictable results if they don't). 
 
> This can probably be further optimized to be aligned with memory  

I don't see much value in the ITR trying to guess at a
memory alignment that might be favorable to all ETRs. That
is precisely why trailers are now historical; there were
only ever a small class of (now-obsolete) devices for
which they provided any real benefit. 

> first 1024 bytes of the original packet and a second packet with the  

This brings up an unspoken assumption - that the interdomain
core is comprised wholly of links that configure MTUs that
are significantly larger than 1KB. Personally, I don't find
that to be an unreasonable assumption; BCP documents like
RFC3819 only talk about setting small MTUs on slow links,
and I don't think we would find many (any?) of those in the
interdomain core. So, can it be reasonably assumed that the
interdomain core is made up of links with significantly
larger than 1KB MTUs (e.g., ~1500 bytes or larger)? I sure
hope so...

Back to the numbers you've mentioned above, I think I like
them and here is why. ITR->ETR tunnels are in-the-network
tunnels and as such there may be many hops between the
original source and the ITR. Within those hops, there may
be additional encapsulations (IPSec tunnels, L2TP, etc.)
such that a 1500 byte packet sent by the original source
might grow to something like ~1750 by the time it reaches
the ITR. So, the 1-2KB fragmentation region allows for up
to ~500 bytes of additional encapsulation overhead between
the original source and the ITR. Similarly, there may be
many hops between the ITR and ETR and possibly additional
encapsulations on the path between the two. So, the 1KB
maximum fragment size allows ~500 bytes of additional
encapsulation between the ITR and ETR in case there might
be a "degenerate" 1500 MTU Ethernet on the path.

So, we could:

  - admit 1KB- packets into the tunnel unfragmented
    and trust that they will make it through due to
    the ubiquitous deployment of Ethernet or larger
    sized MTUs
  - fragment (1KB+, 2KB-) packets into 2-fragment
    outer packets until such time that probing has
    determined that they can be sent as 1-fragment
    outer packets
  - admit 2KB+ packets into the tunnel unfragmented
    and let them sink or swim on their own

This means that, in order to probe our way out of the
(1KB+, 2KB-) pain region we really need for the links
in the core to support significantly larger MTUs than
just a small delta above 1500. So, why not just go
straight to Gig-E and enable jumboframes on all links
in the core? ("Baby-jumbos" of 4KB or larger are
probably OK, too.)   

> travel over parallel paths, both issues that I don't think are all  

I like the idea of making the two fragments roughly
equal sized. I'm not sure I get the point about making
the first fragment larger than the second?

> would be extremely useful.

This is something I have considered many times and have
always come to the conclusion that the benefits are not
necessarily as obvious or significant as they might seem.
First, you need extra bits in the encapsulation header
that go with every packet. Second, you need to have a
nonce such that the ITR can tell that the ACK is legitimate.
(Something like an MD5 digest of the original packet returned
in the ACK might be OK.) But furthermore, you may not always
have a large data packet lying around when you need one.

In that case, there needs to be an explicit probe packet
type that is not a data packet. RFC4821 suggests using an
adjunct protocol (e.g., ICMP echo/request, traceroute,
sprite-mtu) for the purpose of probing. But as you say,
tunnling proposals that use UDP encapsulation could include
a probe packet type inline as part of the UDP protocol type.
That would have the benefit of making sure that the probe
packets get the same treatment as the data packets.

Can we say that we are reaching consensus on some of the
above? Can we get Dino and company to build us routers that
can cope with the 2-fragment cutting and pasting for the
short term that we hope will be rarely needed as the core
transitions to Gig-E?

Thanks - Fred

---

From: "Templin, Fred L" <[email-masked]>
Date: Fri, 4 Jan 2008 14:14:06 -0800

It might be worth noting that many of the ideas we
have been discussing in these threads are already
touched on in some fashion in RFC4459. (However,
RFC4459 is more of a problem statement and we are
considering solution space here...)

Thanks - Fred

---

From: Yakov Rekhter <[email-masked]>
Date: Sun, 06 Jan 2008 10:14:08 -0800

Dino,

> this needs to go fast, the MacBook memory won't run at 40-100G.

For the purpose of this discussion we need to look separately at
the memory used by the control plane and the memory used by the
data plane. Your arguments that "the MacBook memory won't run at
40-100G" may be relevant in the context of the memory used by the
data plane, but is *totally irrelevant* in the context of the memory
used by the control plane.

The point raised by Brian about "a step backwards, from CEF to
pre-CEF bad-old-days" is an important one. Namely, by what kind
of "magic" all the problems that motivated development of CEF would
disappear in the context of ITR/ETR caches ?  And if they would not
disappear, then why would they be not as important now, as they
have been when CEF was developed ?

Yakov.

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 6 Jan 2008 10:29:54 -0800

> used by the control plane.

Yes, agree. That is what I implied since control-plane memory won't  
have to run at speeds 40-100G.

> pre-CEF bad-old-days" is an important one. Namely, by what kind

Let me put it another way. Could any box run with a full set of DNS  
entries for the entire Internet. At some point you have no choice but  
to go with on-demand caching.

> disappear in the context of ITR/ETR caches ?  And if they would not

You don't do packet-time population of the cache like CEF did. In  
LISP, you do packet-time Map-Requests, but the Replies populate the  
cache at control-plane time. That is the difference, subtle but  
important.

Dino

---

From: Robert Raszuk <[email-masked]>
Date: Sun, 06 Jan 2008 12:45:57 -0800

Dino,

> cache at control-plane time. That is the difference, subtle but 

But the subtle difference also is that before the reply for such request 
is received you have two choices:

* drop packets /* not saying this is bad .. just static the facts when 
comparing to today's FIB approach */

or

* forward it to practically non existent and managed by unknown entity 
virtual GRE based LISP-ALT topology ...

I like APT proposal much more robust in that respect enforcing that all 
ISPs have a default mapper and locally packets undergo just two stage 
tunneling process if topologically required.

Cheers,
R.

---

From: Tony Li <[email-masked]>
Date: Sun, 6 Jan 2008 16:21:32 -0800

On Jan 6, 2008, at 10:29 AM, Dino Farinacci wrote:

> You don't do packet-time population of the cache like CEF did.

Just for the record, CEF did not do any caching.  In fact, the whole  
point of the design was to stop caching, since it was ineffective.   
The working set was essentially the full space, so there was no  
benefit and significant overhead.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 6 Jan 2008 20:27:57 -0800

> But the subtle difference also is that before the reply for such  
> request is received you have two choices:
>
> * drop packets /* not saying this is bad .. just static the facts  
> when comparing to today's FIB approach */
>
> or
>
> * forward it to practically non existent and managed by unknown  
> entity virtual GRE based LISP-ALT topology ...

Yes, we have mentioned this many times.

> I like APT proposal much more robust in that respect enforcing that  
> all ISPs have a default mapper and locally packets undergo just two  
> stage tunneling process if topologically required.

That means that every ISP from source-site to destination-site needs  
to run APT. We have decided for LISP for the best place to put xTRs  
are at the site, BECAUSE LESS INFRASTRUCTURE NEEDS TO CHANGE.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 6 Jan 2008 20:30:29 -0800

> benefit and significant overhead.

Well, you know I know that. But I was staying with Yakov's lingo. What  
Yakov is referring to is cisco's original fast-switching cache where  
host addresses were populated by software switching.

It's not at all bad with LISP because we are aggregating all site- 
based addresses into an EID-prefix so any new host at a site with a  
cached EID-prefix for a destination site that talks to a new host at  
the destination site, won't have a "cache fault" or have to drop or  
send data probes.

Dino

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 07 Jan 2008 02:33:14 -0800

Hi Dino,

> are at the site, BECAUSE LESS INFRASTRUCTURE NEEDS TO CHANGE.

Well the way I see APT model it does not require to change any 
infrastructure nor build any new virtual one.

It just offers the way to reduce the control plane load on all routers 
in a given ISP to one (or two for redundancy) to def mappers. Rest 
remains the same as is today.

I also do not see a must requirement that all ISPs in the chain need to 
run APT. If some ISP in the middle wants to continue with today's hop by 
hop switching there should be nothing to prohibit one from doing so. 
With any flavor of LISP I don't see this as even an option.

Cheers,
R.

---

From: Eliot Lear <[email-masked]>
Date: Mon, 07 Jan 2008 13:11:57 +0100

Hi Robert,

It was good seeing you last month.

The big problem with APT as I understood it from the RRG meeting was 
that it was an SP-provided solution, when the SPs are not motivated to 
actually fix the problem.  As I mentioned at the RRG, I believe that we 
have different understandings of what provider independence is.  To me, 
provider independence means that it should be possible to change 
providers without permission or even coordination of either the old or 
the new.  If someone can explain to me how that is possible with APT, it 
wasn't clear at the RRG meeting in December.  As a bonus, it should be 
possible to do all of this without adverse impact on the routing system.

Eliot

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 07 Jan 2008 08:27:31 -0800

Hi Eliot,

 > If someone can explain to me how that is possible with APT

Let me take a shot ...

Assume you are allocating some address block /28 for customer from 240 
pool. Today you are connected to two ISPs. Mapping entry list two ETRs 
for your block either your CE or your ISP PE router. When you need to 
switch one ISP with another all you do is to change the ETR address in 
the mapping database.

ETR address is a routable address in any of the schemes. Also in any of 
the schemes you will get it in some way from an upstream ISP if ETR is 
on CE.

Moreover scale*rate equation is happy ... proposed BGP to provide 
mapping services while does grow in scale ... goes very well down in 
rate. ETR addresses need to fast converge not mapping database.

If customer owns ETRs then transit ISPs may not even participate in the 
mapping business as long as they can route to ETRs.

Cheers,
R.

---

From: Yakov Rekhter <[email-masked]>
Date: Mon, 07 Jan 2008 08:47:37 -0800

Dino,

> have to run at speeds 40-100G.

Since the control plane memory does not seem to be a bottleneck, 
why do we need caches in the control plane ?

Yakov.

---

From: Yakov Rekhter <[email-masked]>
Date: Mon, 07 Jan 2008 08:58:57 -0800

Dino,

> Yes, we have mentioned this many times.

Just because "we have mentioned this many times" does not make
the problems go away. 

Yakov.

---

From: Yakov Rekhter <[email-masked]>
Date: Mon, 07 Jan 2008 09:02:38 -0800

Dino,

> the destination site, won't have a "cache fault" or have to drop or  

Whether "it's not at all bad" depends on the locality of the traffic.
To preserve "truth in advertising" the LISP spec needs (a) to clearly
spelled out the assumptions you make about the locality of the
traffic, as well as (b) to document the system behavior if these assumptions 
turned out to be incorrect.

Yakov.

---

From: Yakov Rekhter <[email-masked]>
Date: Mon, 07 Jan 2008 09:55:04 -0800

Robert,

> rate. 

> ETR addresses need to fast converge not mapping database.

The above fixation on keeping the scale*rate equation "happy", and
on fast convergence of ETR addresses shows the lack of the system-wide
perspective.

If the mapping databased does not reflect the actual state of
reachability, then fast convergence on ETR addresses is not sufficient.
In fact, to be of any use such fast convergence also requires fast
convergence of the actual reachability information. Whether one
carries the actual reachability information in BGP, or via some
other mechanism does not change this.

Moreover, if one carries the reachability information by means other
than BGP, then one needs to show the benefits of doing this on the
overall system behavior vs carrying this information in BGP. Just
because one replaces BGP with some other mechanism to provide the
reachability information does not guaratee that this other mechanism
would consume less resources than BGP while providing comparable
results in terms of timeliness and scalability.

Finally, in terms of keeping the scale*rate equation "happy", there are
possible mechanisms to control the rate besides APT (or LISP for
that matter). E.g., see presentation by John Scudder and David Ward
at IETF-68. 

Yakov.

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 7 Jan 2008 10:37:53 -0800

> why do we need caches in the control plane ?

The control plane memory could be a bottleneck and lack capacity for  
10^9 entries. But granted, the LISP-ALT database (extended to carry  
mapping entries which it does not do now) could be stored in control- 
plane memory only and if you were doing software switching you could  
use this larger database for forwarding and not a cache.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 7 Jan 2008 10:38:43 -0800

> Just because "we have mentioned this many times" does not make

Just stating this is not news.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 7 Jan 2008 10:39:50 -0800

> Whether "it's not at all bad" depends on the locality of the traffic.

Right, the guys at UCLB are gathering data on this.

> turned out to be incorrect.

Right, but we don't have the data yet so that is why it's not  
documented.

Dino

---

From: Yakov Rekhter <[email-masked]>
Date: Mon, 07 Jan 2008 10:46:05 -0800

Dino,

> Right, the guys at UCLB are gathering data on this.

Ok.

> Right, but we don't have the data yet so that is why it's not  

Just because "we don't have the data yet" is *not* a valid reason for
why (a) and (b) are "not documented". This is because to document
*assumptions* does not require the data - the data is required to
test the assumptions. Likewise, documenting the system behavior if
the assumptions turned out to be incorrect does not require the
data.

Yakov.

---

From: Eliot Lear <[email-masked]>
Date: Mon, 07 Jan 2008 20:01:48 +0100

Greetings, Yakov,
> other mechanism does not change this.

Precisely so.
> results in terms of timeliness and scalability.

Again, right on the money.  In the case of LISP I think we're there, but 
we would love lots more analysis.  The whole point of offering a whole 
new tunneling approach is to provide for locator reachability bits in 
line with the data.  By doing this, a failure on the part of one of the 
far end ITRs can be transmitted to the near end ETR using those bits.  
Similarly, when a failed far end ITR returns to service, it or another 
far end ITR can indicate its reachability.  Now, tell me how fast can 
BGP handle either a withdraw or an announcement? 

At the same time, if we look at the system-wide effects we see that 
since the operational state has moved from a broadcast DFZ to a 
bilateral mechanism, only communicating parties need to retain that 
state.  How shall we quantify that? 
> that matter). E.g., see presentation by John Scudder and David Ward

Sure.

Regards,

Eliot

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 7 Jan 2008 11:11:53 -0800

> on fast convergence of ETR addresses shows the lack of the system-wide

I don't know what "scale*rate" really means because previous  
references have documented "state*rate" which makes more sense to me.

> reachability, then fast convergence on ETR addresses is not  

Well if a path changes in the core to reach a specific ETR address,  
you want change quickly. And that will use BGP like it does today.

So, not sure what your point is.

> other mechanism does not change this.

Right, and by determining reachability in a smaller topological region  
(the IGP) you have a better opportunity for faster convergence (inside  
of the site). And then if this new reachability status is carry in the  
data-plane, I think you have done pretty good. But if you don't agree,  
please tell me why not.

> than BGP, then one needs to show the benefits of doing this on the

LISP is not replacing BGP. LISP is conveying 1) the ETR is up, 2) the  
ETR's CE-PE link is up and 3) the ETR thinks the PE is up. BGP still  
controls the policy and reachability of the locator addresses (the  
addresses of the ETRs).

> results in terms of timeliness and scalability.

The EID-prefixes don't have to go into the BGP core routers. Those  
addresses are the ones that decouple site addressing from physical  
topology.

So Yakov, do you not believe this level of indirection doesn't solve  
anything?

If not, how would you solve this problem? That is, if you really  
wanted to reduce the size of the core routing tables, how would you do  
it?

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 7 Jan 2008 11:24:18 -0800

> the assumptions turned out to be incorrect does not require the

We are assuming, at this point, nothing in terms of traffic locality.  
We are assuming the cache can be as large as the number of sites. But  
you can make guesses easily that a few number of sites will have to  
hold this large of a mapping database.

Dino

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 07 Jan 2008 11:35:50 -0800

Hi Dino,

One question ...

> Well if a path changes in the core to reach a specific ETR address, you 
> want change quickly. And that will use BGP like it does today.

Correct.

> controls the policy and reachability of the locator addresses (the 

If we assume that ETR addresses (unicast or anycast) are in the BGP as 
today, and agreed that there would be much less of them then EIDs why 
LISP (presumably you are referring to the data plane idea) has to convey 
if ETR is up ?

Am I right that the assumption is that the major reason for this is that 
you do not want to run BGP on ETRs ? You would not need to ... You could 
  even run BFD between PE-CE/ETR to indicate to PE that CE/ETR is down. 
  PE would then re propagate this fast in BGP.

I am just trying to see a consistency in reachability propagation end to 
end. BGP may say ETR is up while LISP data plane idea that is went down. 
Actually for unicast this may work well but for anycast ETR address I am 
not that sure during the failure of one ETR from given anycast group.

Cheers,
R.

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 07 Jan 2008 11:41:03 -0800

Eliot,

Mapping is sourced by the web page. Neither CE nor PE router. The web 
page allows to change ETR addresses as you like. ETR addresses 
modification is not related to the ISP connected to customer site. Such 
web page would be managed by whoever assigned you the EID for your site.

ISP just provides ETR addresses for the PE-CE link. And you do not need 
to call anyone .. ISP as long as it operates would still announce his 
block. PE-CE interface you were using will be cleared once you stop 
paying for the service. That is normal process not much different from 
today.

I am just trying to avoid additional complexity for no clear gain ... 
Let me know where is the gap I am missing ...

Cheers,
R.

> Robert Raszuk wrote:
>  >
>  > [...] Today you are connected to two ISPs. Mapping entry list two ETRs
> Where is the mapping sourced?  If it is in your CE router, then you have
> rate*state problems when that line flaps (and we have reason to believe
> it will flap).  If it is in the PE router, I have to call my now former
> service provider to tell them to stop announcing for me.  That's the
> provider independence part I want.
> 
> Regards,
> 
> Eliot
>

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 7 Jan 2008 12:42:51 -0800

> If we assume that ETR addresses (unicast or anycast) are in the BGP  
> as today, and agreed that there would be much less of them then EIDs  
> why LISP (presumably you are referring to the data plane idea) has  
> to convey if ETR is up ?

Because if one of the failure cases I mentioned occurred, you want a  
source-site to use *another* locator from the locator-set that is  
mapped from the EID-prefix for the destination site.

> Am I right that the assumption is that the major reason for this is  
> that you do not want to run BGP on ETRs ? You would not need to ...  
> You could  even run BFD between PE-CE/ETR to indicate to PE that CE/ 
> ETR is down.  PE would then re propagate this fast in BGP.

No, that's not the reason. Eliminating BGP from the CE routers is a  
side benefit. But if you want to choose locators based on BGP policy,  
the CE routers must run BGP.

> I am just trying to see a consistency in reachability propagation  
> end to end.

Understand, no problem.

> BGP may say ETR is up while LISP data plane idea that is went down.  
> Actually for unicast

BGP does not specifically convey ETR reachability. It conveys a prefix  
that includes a bunch of ETR addresses. So if an ETR goes down, the  
prefix won't change in the core, so the fact the ETR went down cannot  
be propagated far away. This is a good thing IMO. But the ETR failure  
only goes to the place where the "more-specific route" travels and  
then suppressed by prefix aggregation.

I know I am preaching to the choir on this point.

> this may work well but for anycast ETR address I am not that sure  
> during the failure of one ETR from given anycast group.

Well for an anycast ETR that goes away, most of world thinks nothing  
happens. Only the place close to the failure detects "the new path to  
the address" where, in turn, is actually a new place and not just a  
new path. Again preaching to the choir.

Dino

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 08 Jan 2008 14:22:19 +1300

On 2008-01-08 05:27, Robert Raszuk wrote:

...

> mapping business as long as they can route to ETRs.

That appears to me to be a very big "if" except for large and
sophisticated customers; it seems to me that the large majority
of medium size sites will be very unlikely to run an ETR, even if
they are connected to more than one ISP.

     Brian

---

From: Eliot Lear <[email-masked]>
Date: Tue, 08 Jan 2008 08:19:30 +0100

Brian,
> they are connected to more than one ISP.

I think this depends on the complexity of running one.  If it adds no 
operational complexity, why not have them in a Linksys box?

Eliot

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 08 Jan 2008 01:06:11 -0800

Hi Eliot,

I agree with you. If ETR/ITR function will not be automatic and 
transparent to end sites running on a very lowest end boxes I think any 
of the solutions discussed here will completely fail deployment wise.

Cheers,
R.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 8 Jan 2008 14:58:32 +0100

> 10^9 entries.

Since we have no upper limit on the number of EID prefixes = RIB  
entries, it's impossible to say what will not be a bottleneck. More  
practically, with BGP the RIB is some multiple of the FIB, but  
assuming that multiple stays within a reasonable range, the  
relationship is linear. As long as every destination in the RIB needs  
to go in the FIB (= no caching) the control plane probably won't be a  
bottleneck as long as we can afford the data plane.

However, what we really want is to avoid having to build a bigger box  
any time the number of EID prefixes increases. What we need is  
something that allows us to split the used EID space (not necessarily  
the possible EID space) into more or less equal parts that can be  
processed on separate small and affordable boxes.

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 08 Jan 2008 06:03:00 -0800

Eliot,

> line with the data.  

Just because you piggyback control information on data does not
change the fact that this is control information, and thus
has to be processed by the control plane.

> By doing this, a failure on the part of one of the 

What matters is how fast one could restore reachability, as the
service is reachability, not BGP.

With LISP in order to restore reachability the failure information
has to be propagated from ETRs all the way to ITRs.  In contrast
to this, with the current routing restoring reachability may require
(much) narrow scope of the the failure information propagation.
E.g., if a site is multi-homed to the same service provider, then
the reachability restoration requires to propagate PE/CE failure
*only* within that provider. E.g., if a site is multi-homed to two
providers, and these providers have a direct peering with each
other, then the reachability restoration requires to propagate PE/CE
failure to only these two providers.

Yakov.

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 08 Jan 2008 06:12:39 -0800

Dino,

> We are assuming, at this point, nothing in terms of traffic locality.  

First you agreed that whether "it's not at all bad" depends
on the locality of the traffic. But then you assume "nothing
in terms of traffic locality". Putting the two together
means that you have no clue on how bad that is going to be.

And, by the way, you still did not answer my original question.
Namely, what were the problems that motivated development of CEF,
and how these problems would be solved in the context of LISP ?

Yakov.

---

From: Eliot Lear <[email-masked]>
Date: Tue, 08 Jan 2008 15:32:24 +0100

> has to be processed by the control plane.

True, but let's not get hung up just yet on how we process control plane 
information.

> service is reachability, not BGP.

Right.  But I'm looking for a comparison between methods to restore 
reachability ;-)

> has to be propagated from ETRs all the way to ITRs.
Well, let's put this in more quantifiable terms.  Link goes down.  IGP 
floods that to other ETRs as traffic shifts from one ETR to another.  
Let's agree that IGP has to converge no matter whether we're talking 
LISP or BGP ;-)  Now it is a mere matter of 1/2 RTT between the new ETR 
and ITR.  So, when you say "all the way", sure.  But put in terms of 
time, I'd like to understand the numbers, especially if the router has 
failed.  A count to infinity is not fun.  I've tried it ;-)

>   In contrast

This has always been an option, but it's not solely used by any serious 
enterprise.  So why do you think it will be acceptable in the future?  
Einstein had something to say about that logic.  And where it's not 
particularly useful to the enterprise, it's downright hostile to the 
consumer.  Today the consumer has really two wires into her house: phone 
and cable.  We ought to engineer for that at least for today instead of 
insisting that she have two phone or two cable lines for redundancy, or 
worse imposing business practices on the service providers to manage the 
redundancy through wholesale mechanisms.

Eliot

---

From: Eliot Lear <[email-masked]>
Date: Tue, 08 Jan 2008 15:35:27 +0100

Iljitsch van Beijnum wrote:
> entries, it's impossible to say what will not be a bottleneck. 

Why do you say that?  We have a population limit, if nothing else.  
Perhaps things won't scale if birds start having IP addresses...

Eliot

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 8 Jan 2008 16:25:54 +0100

On 8 jan 2008, at 15:35, Eliot Lear wrote:

>>> The control plane memory could be a bottleneck and lack capacity  
>>> for 10^9 entries.

> Perhaps things won't scale if birds start having IP addresses...

Last time I check it's still possible to have a child without a  
license... Obviously the number of EID prefixes won't be infinite, but  
there is no figure you can come up with that satisfies both the  
condition that it's not reasonably possible to have more prefixes than  
that on the one hand and hardware to handle that number of prefixes  
can be made within the forseeable future at reasonable prices.

The problem that we're faced with is rate*size. If we split the  
traffic over multiple boxes we limit rate for any particular box, if  
we split the routing information over muliple boxes we limit the size.  
This way, we should be able to create clusters of smaller boxes than  
can provide the necessary performance much more easily than in the  
situation where out protocols force every update/packet to go through  
a single bottleneck.

---

From: Eliot Lear <[email-masked]>
Date: Tue, 08 Jan 2008 16:38:50 +0100

> can be made within the forseeable future at reasonable prices.

Remember my presentation in Madrid.  I've compared two substantially 
different models and they actually both agree on growth targets until 
well after 2050.  Would you comment on those?

Eliot

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 09:38:24 -0800

> and how these problems would be solved in the context of LISP ?

The problem that motivated the development of CEF was the observation  
that for core routers, the per-prefix cache filled to 80-85% of the  
full size of the RIB almost immediately.

I'll let the LISP folks respond to their half of the question.

Tony

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 09:50:33 -0800

On Jan 8, 2008, at 6:35 AM, Eliot Lear wrote:

> We have a population limit, if nothing else.

The number of hosts on the net is only loosely coupled to the  
population.  As we continue to make the 'net ubiquitous, there will  
continue to be more and more applications resulting in more addresses  
per person.  Assuming linearity would be a mistake.

For an example, consider the applications that are emerging from  
sensor networks or the automotive industry.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 09 Jan 2008 10:05:17 +1300

On 2008-01-09 06:50, Tony Li wrote:
> For an example, consider the applications that are emerging from sensor 
> networks or the automotive industry.

Sure, but for EID *prefixes* I understood we were aiming at
100 million as the high-end limit. (My original SWAG was
10 million, i.e. a rough estimate of the number of medium
and large organizations in a world of 10 billion humans,
but people seemed to think that was too low.)

     Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 09 Jan 2008 10:09:04 +1300

Robert,

> of the solutions discussed here will completely fail deployment wise.

That really depends on whether you expect the ETRs to be deployed by
ISPs on behalf of SMB customers, or whether you expect the SMB customers
to buy them at the supermarket. Since it's the ISPs that will suffer
directly from BGP4 collapse, I think the economic incentive will
apply to the ISPs.

     Brian

---

From: Eliot Lear <[email-masked]>
Date: Tue, 08 Jan 2008 22:24:41 +0100

Brian,
> directly from BGP4 collapse, I think the economic incentive will

Well, *an* incentive is at work today: it is not economically feasible 
for consumers to be multihomed at L3.  But that doesn't mean that ISPs 
have to be the center of the solution.  LISP, for instance, can be 
implemented without the cooperation of a particular ISP, although I 
believe there ARE economic incentives for ISPs to implement LISP ITRs in 
the consumer space.

Eliot

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 08 Jan 2008 13:24:36 -0800

Hi Brian,

 > directly from BGP4 collapse

Maybe I have missed some threads on RRG but this is first time I see 
such term about "BGP4 collapsing". Why it this going to collapse ? What 
elements of BGP4 are going to collapse ? What would make it's 
replacement not to collapse ? I am just trying to understand your line 
of thinking in regards of BGP4 collapsing ....

In BGP4 we have a lot of machinery build into the protocol for it not to 
collapse. Most of them can be just configured in most of the shipping & 
deployed implementation of BGP. Introducing the explicit indirection in 
what we have today would make such configuration much easier.

Also ... are you saying that any proposal (like APT) which uses proven 
BGP4 for propagating mapping information will collapse while other 
proposals will last really long just because they do not use BGP4 ?

Thx,
R.

>> transparent to end sites running on a very lowest end boxes I think 
>> any of the solutions discussed here will completely fail deployment wise.
>

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 13:47:34 -0800

On Jan 8, 2008, at 1:05 PM, Brian E Carpenter wrote:

> 100 million as the high-end limit.

I could have sworn for sure that at least one topic under discussion  
was individual host-specific reachability for ETRs.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 09 Jan 2008 10:52:56 +1300

> of thinking in regards of BGP4 collapsing ....

Well, we're here because of the concern that BGP4 updates will become
prohibitive as multihoming expands, aren't we?

     Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 09 Jan 2008 10:59:28 +1300

On 2008-01-09 10:47, Tony Li wrote:
> I could have sworn for sure that at least one topic under discussion was 
> individual host-specific reachability for ETRs.

That is a truly scary goal IMHO, unless it's very exceptional.

     Brian

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 08 Jan 2008 14:09:44 -0800

Hi Brian,

 > prohibitive as multihoming expands, aren't we ?

It is actually a very good question why we are here :).

There was a number of reasons stated in Amsterdam IAB meeting. I don't 
think there was one stating that "BGP4 updates will become prohibitive".

Today BGP runs flat with next hops rewritten at each EBGP peering. APT 
is a first attempt I see to make it run in real hierarchy by just 
calling next hops as locators and keeping it unchanged across EBGP 
boundaries.

There are other ideas along the same lines and few trying to replace BGP 
control plane with something virtual ... something new.

I do encourage all ongoing research for a better control plane 
especially having it's deployment targets 5-10 years from now.

But I would like to also see the real list of what are the issue in BGP 
we are trying to address ... Is this point-to-point model, is this TCP 
transport, is this update format ... No one yet stated what is broken. 
And when we do not know what is broken .. or which link of BGP chain is 
fragile it is quite a challenge to design new thing around the unknown.

Cheers,
R.

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 14:15:42 -0800

> prohibitive as multihoming expands, aren't we?

Nope.  We're here because routing convergence will continue to  
degrade as the number of prefixes scales.  There are multiple reasons  
for the scaling issue, and BGP is irrelevant to the scaling problem,  
as the scaling of the information content is independent of the  
delivery mechanism.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 09 Jan 2008 11:37:38 +1300

On 2008-01-09 11:15, Tony Li wrote:
> Nope.  We're here because routing convergence will continue to degrade 
> as the number of prefixes scales.  There are multiple reasons for the 
> scaling issue, and BGP is irrelevant to the scaling problem, as the 
> scaling of the information content is independent of the delivery 
> mechanism.

That's undeniable. I guess I believe that an unsustainable level of
BGP update traffic will be the first practical consequence to hit us.

     Brian

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 14:55:18 -0800

Forwarded due to the original having got caught in the mailing list  
filters...

Tony

On Jan 8, 2008, at 2:49 PM, Tony Li wrote:

>
> On Jan 8, 2008, at 2:37 PM, Brian E Carpenter wrote:
>
>>  I guess I believe that an unsustainable level of
> The two router vendors that are vocally represented here don't seem  
> to support that view, however.  How do you define "unsustainable"?   
> You can create non-convergence today in the lab by simply causing a  
> set of BGP speakers generate flap  faster than the unit under  
> test.  You can also create that in the field today by putting  
> woefully underpowered CPU (anyone still got a CSC-4 handy? ;-) in  
> the core.  What we see today is that convergence is slowing, but  
> it's difficult to argue about when (or if) it will get to non- 
> convergence, given Moore's law and technology refresh cycles.  This  
> is exactly why we try to focus the issue around clearly  
> quantifiable issues.
>
> Tony
>
>
>

---

From: "PAPADIMITRIOU Dimitri" <[email-masked]>
Date: Wed, 9 Jan 2008 00:05:31 +0100

tony, 

>> Well, we're here because of the concern that BGP4 updates 
>> will become prohibitive as multihoming expands, aren't we?
> 

the design-goals doc. - section 3.8 states

"A solution is strongly desired to provide routing quality equivalent
 to what is available today or better."

where

"The quality of the routes that are computed can be measured by a number
 of metrics, such as convergence, stability, and stretch."
 
as convergence gets affected by approaches that are not preserving the
locality principle due to the ITR-ETR relationship they involve (see
also e-mail from Yakov along the same line) 

-> how are they positioned as fulfilling the initial design goals ?
 
thanks
-dimitri.

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 09 Jan 2008 12:08:37 +1300

Tony,

On 2008-01-09 11:49, Tony Li wrote:
> The two router vendors that are vocally represented here don't seem to 
> support that view, however.  How do you define "unsustainable"?  You can 
> create non-convergence today in the lab by simply causing a set of BGP 
> speakers generate flap  faster than the unit under test.  You can also 
> create that in the field today by putting woefully underpowered CPU 
> (anyone still got a CSC-4 handy? ;-) in the core.  What we see today is 
> that convergence is slowing, but it's difficult to argue about when (or 
> if) it will get to non-convergence, given Moore's law and technology 
> refresh cycles.  

Indeed. That's why I used the unscientific word "believe", and
I certainly wouldn't care to put a date on it.

> This is exactly why we try to focus the issue around 
> clearly quantifiable issues.

I agree with you. Peace.

   Brian

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 08 Jan 2008 15:06:06 -0800

Hi Tony,

 > What we see today is that convergence is slowing,

That is good observation ... but I want to also point out that there is 
already a deployed technology to offer prefix independent convergence.

So far deployed within an AS scope .. but very possible to be deployed 
system-wide if we go to two tier BGP hierarchy.

We have said that control plane is pretty much not the issue. So perhaps 
we should shift the discussion into ways to fit control plane into data 
plane so PIC would be achievable system-wide ?

Cheers,
R.

> refresh cycles.  This is exactly why we try to focus the issue around

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 15:38:05 -0800

Robert,

On Jan 8, 2008, at 3:06 PM, Robert Raszuk wrote:

> That is good observation ... but I want to also point out that  
> there is already a deployed technology to offer prefix independent  
> convergence.
>
> So far deployed within an AS scope .. but very possible to be  
> deployed system-wide if we go to two tier BGP hierarchy.

Thanks for pointing that out.  I'm no expert in PIC, but it would  
seem to address purely the cases where there is little state flux in  
the control plane.  Consider the case of when a new router first  
joins the BGP mesh today.  This is when we will see the biggest  
impact in the number of prefixes carried.

> We have said that control plane is pretty much not the issue. So  
> perhaps we should shift the discussion into ways to fit control  
> plane into data plane so PIC would be achievable system-wide ?

I guess I'm disagreeing with you.  The control plane is very much the  
issue.  The control plane *mechanism* is not the issue, but the  
scalability of the data manipulated by the control plane very much is  
at issue.

Regards,
Tony

---

From: Robert Raszuk <[email-masked]>
Date: Tue, 08 Jan 2008 15:50:36 -0800

Hi Tony,

>> That is good observation ... but I want to also point out that there 
>> is already a deployed technology to offer prefix independent convergence.
>>
> Thanks for pointing that out.  I'm no expert in PIC, but it would seem 
> to address purely the cases where there is little state flux in the 
> control plane.  Consider the case of when a new router first joins the 
> BGP mesh today.  This is when we will see the biggest impact in the 
> number of prefixes carried.

That's as you may perhaps noticed I am a big supporter of two stage 
tunneling within each AS or within each POP. So only very limited number 
of routers per domain would need to go via this biggest impact cycle .. 
clearly not all of them. And as we all know we do have tools to allow 
for graceful initial convergence.

>> perhaps we should shift the discussion into ways to fit control plane 
>> into data plane so PIC would be achievable system-wide ?
> 
> scalability of the data manipulated by the control plane very much is at 
> issue.

I am not questioning that at all ... especially thinking about the scale 
involved going into the future. I am just trying to determine if current 
mechanics of the control plane .. when decoupled from being responsible 
for fast locator/next hop reachability vehicle could not meet the new 
scale requirements. And if not ... why.

I guess the real question get's down to either carry or not to carry all 
EIDs at each let's call it default mapper or even as in NERD each ITR. I 
  am not sure if on demand caching will be the answer to this question. 
Personally I doubt it.

Cheers,
R.

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 15:56:50 -0800

On Jan 8, 2008, at 3:49 PM, Brian Dickson wrote:

> Incidentally, what about solutions that might improve BGP update  
> rates themselves?
> Would that be an issue for the IDR WG, or is that an RRG thing?
> (I'm working on the stuff we talked about before, but my time gets  
> divided by lots of things, sadly.)

We've tried to direct that work to IDR.

Tony

---

From: Brian Dickson <[email-masked]>
Date: Tue, 08 Jan 2008 19:06:09 -0500

> -> how are they positioned as fulfilling the initial design goals ?
What is interesting, is observing what is really control-plane, versus 
carried via control-plane mechanisms.

Reachability from "pure" BGP, which needs to converge and which feeds 
the FIB, e.g. the DFZ prefixes, is
clearly control plane.

However, when BGP is used in an opaque manner to pass information that 
doesn't go into local FIB, it then
isn't a convergence or control plane issue.

If, for example, reachability on RLOC->EID mappings were passed as 
opaque elements via BGP, the only
impact outside of xTRs would be the memory consumption and bandwidth 
associated with passing the updates
end-to-end.

Add one interesting twist to that:
If you combine effectively static RLOC->EID info, with RLOC reachability 
which is propagated as an opaque
item to xTRs, that might have good scaling characteristics.

What I'm thinking of is, have aggregators suppress the more-specifics, 
but when a more-specific goes away,
pass the *un*-reachability "hole" as an opaque item.

It would be of interest almost exclusively to xTRs, and the scalability 
would depend on "what is down",
rather than "what is out there".

And it would do so without directly affecting the DFZ.

Thoughts?

Brian D

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 08 Jan 2008 16:19:13 -0800

Tony,

> degrade as the number of prefixes scales.  

Whether the routing convergence will continue to degrade as the
number of prefixes scale depends on the scalability of the control 
plane CPU/memory.

Yakov.

---

From: Brian Dickson <[email-masked]>
Date: Tue, 08 Jan 2008 19:20:50 -0500

On Jan 8, 2008, at 2:49 PM, Tony Li wrote:

>>  I guess I believe that an un-sustainable level of
(edited to get around silly mail filter problem)
>> BGP update traffic will be the first practical consequence to hit us.
It may be an issue at some point.
However, the near-term consequences of growth in the DFZ, are that
*forwarding-plane* (FIB, i.e. TCAM) growth exceeds the hardware refresh
cycle.
(i.e. the bottom line $$$ impact breaks business models substantially,
even universally.)

Heck, it even exceeds the rate at which TCAM manufacturers can up the
size they support.

So, the important thing about LISP, is that it keeps EIDs out of the
DFZ, making the DFZ scale better.
The question is, is there a solution which does this while also ensuring
that the edges scale well?
Both on the control plane, and the forwarding plane?
And with "convergence" (reachability state updates) that are no worse
than they are today?
>
> This is exactly why we try to focus the issue around clearly 
> quantifiable issues.
>
> Tony 

Incidentally, what about solutions that might improve BGP update rates
themselves?
Would that be an issue for the IDR WG, or is that an RRG thing?
(I'm working on the stuff we talked about before, but my time gets
divided by lots of things, sadly.)

Brian

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 16:27:50 -0800

> number of prefixes scale depends on the scalability of the control

Correct.  We've shown that the growth in the speed of normal DRAM is  
slower than the prefix growth rate.  Thus, simply the act of writing  
a list of all prefixes to memory (e.g., at initial convergence time)  
is taking longer each year.

Tony

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 08 Jan 2008 16:32:46 -0800

Tony,

> is taking longer each year.

That, of course, assumes that we *have to* use DRAM. But do we
really have to ?

Yakov.

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 16:51:55 -0800

Hi Brian,

On Jan 8, 2008, at 4:06 PM, Brian Dickson wrote:

> Reachability from "pure" BGP, which needs to converge and which  
> feeds the FIB, e.g. the DFZ prefixes, is
> clearly control plane.
>
> However, when BGP is used in an opaque manner to pass information  
> that doesn't go into local FIB, it then

Not necessarily.

Gedanken experiment: Suppose that a BGP speaker interleaves BGP  
update messages containing DFZ prefixes with one full minutes worth  
of 'opaque' data.  Does this have an effect on the control plane?   
Two minutes?  Ten?

The control plane is concerned with responsiveness.

> impact outside of xTRs would be the memory consumption and  
> bandwidth associated with passing the updates
> end-to-end.

And processing power, and delay.  Remember that the control plane  
*is* a control loop, and changing the time constants of that control  
loop *do* change the characteristics of the control plane.

Consuming state in other applications also takes away from the state  
that can be devoted to the control plane.

> If you combine effectively static RLOC->EID info, with RLOC  
> reachability which is propagated as an opaque
> What I'm thinking of is, have aggregators suppress the more- 
> specifics, but when a more-specific goes away,
> It would be of interest almost exclusively to xTRs, and the  
> scalability would depend on "what is down",

Yet still with an indirect effect.  Please don't ignore it.

Tony

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 16:57:51 -0800

> That, of course, assumes that we *have to* use DRAM. But do we

No, it's not a requirement.  If your employer chooses to implement  
BGP with a disk drive, that's fine by me.  ;-)

You can also go in the opposite direction and go to non-commodity  
memories, but then you go off of the commodity cost curves.  Once you  
do that, it's hard to continue to sustain our growth rate at constant  
cost, and that's simply another way of failing to scale.

Tony

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 08 Jan 2008 17:24:15 -0800

Eliot,

> True, but let's not get hung up just yet on how we process control plane 

Ok, let's gloss over details... After all, it is precisely
in the details where the devil is...

> Right.  But I'm looking for a comparison between methods to restore 

So am I.

> failed.  A count to infinity is not fun.  I've tried it ;-)

Consider a multi-homed site connected to two ISPs, ISP1 and ISP2.
The ETRs are maintained by ISPs. How would you get the information
about ETR failure via IGP in this scenario ?

> enterprise.  

You are mistaken - this is exactly how the Internet routing system
works today. Specifically, the time to restore reachability is
less then the time it takes to propagate the failure information
Internet-wide.

> So why do you think it will be acceptable in the future?  

Because it works.

Yakov.

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 08 Jan 2008 17:47:44 -0800

Tony,

> BGP with a disk drive, that's fine by me.  ;-)

Since you propose this, I would rather let your employer to do this :-)
  
> cost, and that's simply another way of failing to scale.

What is a non-commodity memory today need not be non-commodity
memory tomorrow.

Moreover, what really matters is not whether "you go off of the
commodity cost curves", but how far are you off.

Finally, while the argument about "constant cost" focuses on CAPEX,
let's not forget OPEX. The cost of operating the new system could
completely overshadow all the OPEX considerations.

Yakov.

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 18:27:31 -0800

Yakov,

> What is a non-commodity memory today need not be non-commodity

True, but it's been a VERY long time since the basic architecture for  
commodity memory has changed in a significant way that changed random  
access speeds.  The last big change that I can think of was the  
original introduction of DRAM, back in the (yes, I'm dating myself)  
late 70's and early 80's.  Original microprocessors were normally  
mated with SRAM, and DRAM was a new and welcome innovation, even  
though refresh was an annoyance.  Since then, we've seen page mode,  
burst mode, and DDR.  Some of those have helped, but many of them  
don't apply directly to the tree-structures that we normally need to  
manipulate.

In short, I don't think that we should really count on the commodity  
market to change its memory architectures anytime soon.  We are  
certainly not enough of a market to have any kind of impact, and  
there's nothing in my crystal ball about any other drivers in the PC  
marketplace either.  Thus, we should reasonably expect to stay on the  
current technology curves.

> commodity cost curves", but how far are you off.

To a point.  How far off you are only determines when costs become  
unsustainable.  As soon as the cost curve to support the growth rate  
exceeds constant cost and there's no way to bring that curve back  
under control, you're
inevitably going to diverge.

> completely overshadow all the OPEX considerations.

A fine point.  A revised routing architecture that is so expensive to  
maintain that it also cannot be deployed is not helpful.  For  
example, a proposal that required manual propagation of mapping  
updates would instantly fail this test.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 09 Jan 2008 15:48:25 +1300

> number of prefixes scale depends on the scalability of the control 

Isn't there also a limit where the number of bits of update info to
be sent over some links per unit time exceeds the spare capacity on
those links, in such a way that convergence becomes impossible,
just as much as if you exceed the memory speed?

     Brian

---

From: Tony Li <[email-masked]>
Date: Tue, 8 Jan 2008 18:58:16 -0800

> just as much as if you exceed the memory speed?

True, but the spare capacity on most links these days is orders of  
magnitude more than is necessary for BGP even at its peak.  Consider  
that core routers today typically have 10Gb/s interfaces (or more)  
and a single lowly CPU computing BGP updates.  I'd be impressed if  
you could generate even a burst at 1Gb/s.  ;-)

Tony

---

From: Dan Jen <[email-masked]>
Date: Tue, 08 Jan 2008 19:01:24 -0800

Just a little clarification on the functionality of APT.  See comments
inline.

> web page would be managed by whoever assigned you the EID for your site.

Actually, mapping information is flooded to all providers via a mapping
distribution protocol.  See our draft for details.

> paying for the service. That is normal process not much different from 

Exactly.  Under APT, when a customer-provider contract terminates, the
provider will withdraw its mappings to the customer's EID prefixes.
Elliot, do you consider this an unacceptable violation of your 'provider
independence' principle?  Perhaps I am misunderstanding your criticism
of APT.

Salutations all,

Dan Jen

---

From: [email-masked] (Noel Chiappa)
Date: Tue, 8 Jan 2008 22:25:13 -0500 (EST)

> From: Brian E Carpenter <[email-masked]>

    > Isn't there also a limit where the number of bits of update info to be
    > sent over some links per unit time exceeds the spare capacity on those
    > links, in such a way that convergence becomes impossible,

I would assume that any sane design/-er would give priority on the link's
capacity over to control traffic. There's no point in sending user data if the
routing table is out of date (and possibly wrong).

Link capacities today are so high I don't think those are likely to be the
bottlenecks. Rather, it's the CPU, and the overall 'time to go around around
the entire topology cycle, i.e. across many routers, including inter-node
propogation, and intra-node processing delays' which I suspect are most
likely to be the problem area (if anything is).

	Noel

---

From: Brian Dickson <[email-masked]>
Date: Tue, 08 Jan 2008 23:15:16 -0500

Tony Li wrote:
> Gedanken experiment: Suppose that a BGP speaker interleaves BGP update 
> messages containing DFZ prefixes with one full minutes worth of 
> 'opaque' data.  Does this have an effect on the control plane?  Two 
> minutes?  Ten?
>
I agree.

However, the angel (rather than devil) is in the details.

If the opaque data is orders of magnitude smaller, it's less of a concern.
Ditto if it is possible to ensure non-head-of-line blocking between the 
two streams.
> And processing power, and delay.  Remember that the control plane *is* 
> a control loop, and changing the time constants of that control loop 
> *do* change the characteristics of the control plane.
>
Yep. It's far from overlooked - I'd even go so far as to say, there's 
work to be done on the control plane methods,
and on the OS models used (e.g. real-time with maximum delays on 
operations.)
>> What I'm thinking of is, have aggregators suppress the 
>> more-specifics, but when a more-specific goes away,
Let me expound on this some more...

If the ETRs were announcing only *negative* information (as opaque 
data), the semantics would also change.

In the case of a local upstream link failure:
The end-site ETR (or mesh of ETRs) would announce local unavailability 
of RLOC(s) upstream via links that are *not* down.
This would be a *sender* rather than *receiver* model for state 
detection, announcement, and propagation.

There are risks, of course - a complete site outage would not have state 
announced, and would globally appear "up", falsely.
But, at the same time, that consequence would be moot, as the site would 
be completely unreachable. :-)

Failures further upstream than the PE-CE link are not likely to induce 
full outages.
Only the aggregate itself need be affected if ISP upstream links fail, 
and then only in the DFZ,
*not* the opaque data.

Since only link-down state (on RLOC links) needs to be captured and 
flooded, the optimum condition (no failures) would be
expressed via the empty set. (!!)

And the locality and scalability have nice characteristics. No shared 
fate on link failures, only one update (and one opaque data entry)
are generated by *any* single failure *anywhere*.

The biggest hit would likely occur if a CLEC (remember those?) lost a 
bunch of fibre.

In general, this scales by the probability of outages, rather than the 
size of the deployed networks or the size of the DFZ.
> Yet still with an indirect effect.  Please don't ignore it.
No, definitely not.

I'd rather characterize and model it, and see if it plays well with 
others. :-)

Brian D

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 9 Jan 2008 00:08:50 -0800

> means that you have no clue on how bad that is going to be.

We have a rough idea but no data yet to back it. That is all I am  
saying Yakov.

> and how these problems would be solved in the context of LISP ?

I did answer it. It was software switching based population of the  
hardware or faster path forwarding cache.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 9 Jan 2008 00:12:10 -0800

Yakov, now that I have answered your questions, can you answer the  
ones I have asked yesterday. See questions below, they are at the end.  
Thanks.

Dino

Begin forwarded message:

> From: Dino Farinacci <[email-masked]>
> Date: January 7, 2008 11:11:53 AM PST
> To: Yakov Rekhter <[email-masked]>
> Cc: [email-masked], Eliot Lear <[email-masked]>, Routing  
> Research Group list <[email-masked]>
> Subject: Re: [RRG] Tunnel fragmentation/reassembly for RRG map-and- 
> encaps architectures
>
> Right, and by determining reachability in a smaller topological  
> region (the IGP) you have a better opportunity for faster  
> convergence (inside of the site). And then if this new reachability  
> status is carry in the data-plane, I think you have done pretty  
> good. But if you don't agree, please tell me why not.
>
> LISP is not replacing BGP. LISP is conveying 1) the ETR is up, 2)  
> the ETR's CE-PE link is up and 3) the ETR thinks the PE is up. BGP  
> still controls the policy and reachability of the locator addresses  
> (the addresses of the ETRs).
>
> wanted to reduce the size of the core routing tables, how would you  
> do it?
>
> Dino
>
> --

---

From: Eliot Lear <[email-masked]>
Date: Wed, 09 Jan 2008 12:07:46 +0100

Yakov,
> [Control plane v. Data plane]

The relation to control plane and data plane isn't some fixed thing.  
Even within the data plane you make decisions based on the data that is 
in the packet.  What you cache and where it is kept cannot itself 
dictate a solution, because that leads to circular logic.  We're here 
because of precisely what we cache and where it is kept, and we need to 
make a change.  Anyone who thinks differently should be satisfied today 
and for the future with what we have because that's all we'll have.

LISP offers a slightly different view of what needs to be managed 
where.  It takes very little imagination to understand how to manage the 
new "control plane" elements in the data plane at line rate.

> about ETR failure via IGP in this scenario ?

The obvious answer is "some other way".  There is an architectural 
assumption that if you want fast failover between two ETRs they must 
somehow communicate with each other.  However, this is not the case I 
would optimize first.  I would expect the enterprise to manage both 
ETRs, as the configuration complexity of doing so is looking to be 
considerably lower than that of BGP.

> less then the time it takes to propagate the failure information

I disagree and I believe it is you who are mistaken.  Enterprises want 
more than just line redundancy.  They want protection against a provider 
failure and path diversity, as happens occasionally due to fiber cuts, 
data center failures, and the like.  The consumer space is even more 
clear.  Why should one install more lines into the home and pay 
additional costs relating to those lines when the wires are already 
there today, but happen to be separated by two carriers?

>> So why do you think it will be acceptable in the future?  

I personally have an aversion to rejected technical solutions that are  
known not to satisfy clear business cases.

Eliot

---

From: Eliot Lear <[email-masked]>
Date: Wed, 09 Jan 2008 12:09:29 +0100

> independence' principle?  Perhaps I am misunderstanding your criticism

I consider it unwanted need for coordination between providers where 
none is necessary using other mechanisms.

Eliot

---

From: Robert Raszuk <[email-masked]>
Date: Wed, 09 Jan 2008 05:17:39 -0800

Hi Dino,

> hardware or faster path forwarding cache.

One huge benefit CEF brings is the ability to resolve not only an active 
path to it's adj but also the backup paths. So during the failure of an 
active path you have immediate candidate already pre-resolved as backup.

Perhaps this entire discussion mixes the terminology ?

Isn't it possible for ITR to do both ? To cache mapping entires (to 
eliminate the amount of them on the ITR) which would contain multiple 
ETR locators and then pre-resolve all such locator candidates in CEF ?

So forwarding will be still cef based ... not cache based. Caching would 
be only related to keeping mapping entires in the control plane to 
eliminate the need for storing them all on all ITRs ?

Cheers,
R.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 9 Jan 2008 14:42:42 +0100

On 8 jan 2008, at 16:38, Eliot Lear wrote:

>> license... Obviously the number of EID prefixes won't be infinite,  
>> but there is no figure you can come up with that satisfies both the  
>> condition that it's not reasonably possible to have more prefixes  
>> than that on the one hand and hardware to handle that number of  
>> prefixes can be made within the forseeable future at reasonable  
>> prices.

> different models and they actually both agree on growth targets  
> until well after 2050.  Would you comment on those?

Let me quote Nils Bohr:

"Prediction is very difficult, especially if it's about the future."

For an illustration, have a look at the various predictions of when  
we'd run out of IPv4 address space that have been made over the years.

But have a look at this page with how many people have to "share" an  
AS number in different countries: http://bgpexpert.com/asespercountry.php

As always, the US is at the top of the list with 18k ASes and 15k  
people per AS (it's millions in some countries). If we extrapolate  
this to a world with 9 billion people that's only 600,000 AS numbers...

The problem that I have is not so much with any particular prediction,  
but with the situation we'll find ourselves in if the predictions are  
wrong and our protocols are such that it's impossible to make the  
equipment scale to the needed numbers.

However, don't forget that the problem is limited to the place where  
the entire global RIB must be managed and/or for a high number of  
packets per second, a global RIB sized FIB must be consulted. Having  
two boxes do half of twice the work increases the price by 2. Having  
one box do twice the work increases the price by more than 2.

---

From: Eliot Lear <[email-masked]>
Date: Wed, 09 Jan 2008 15:27:22 +0100

Iljitisch,
> equipment scale to the needed numbers.

Unless market economics collapse entirely, I am less concerned about 
what is possible versus impossible.  It's just a matter of price.  And 
reduced price demands that one make certain engineering assumptions and 
at least optimize toward those choices.

This discussion about CEF perhaps should spur some research.  What 
percentage of the world's networks would need to be cached AT THE EDGES 
today?

Eliot

---

From: Tony Li <[email-masked]>
Date: Wed, 9 Jan 2008 11:05:14 -0800

On Jan 9, 2008, at 6:27 AM, Eliot Lear wrote:

> percentage of the world's networks would need to be cached AT THE  
> EDGES today?

Better yet, we should simply morph this into a more general  
discussion about properties of mapping solutions.

Presumably, the set of identifiers in the world is going to be very,  
very large.  Simply pushing a full map to everywhere is going to be  
expensive, both in space and time.  Pulling has latency issues.   
Reducing the number of places that have a full map seems like an  
attractive solution, but still leaves the push scalability problem,  
albeit with one less order of magnitude of an issue.  For the places  
that have only a cache, how do you deal with cache misses?

What's the right approach here?  Let's have a conceptual discussion  
and leave out the mechanisms, please.

Tony

---

From: Brian Dickson <[email-masked]>
Date: Wed, 09 Jan 2008 14:42:59 -0500

Tony Li wrote:
> Better yet, we should simply morph this into a more general discussion 
> about properties of mapping solutions.
>
> very large.
There are quantifiers that we may want to place on this, including 
discussing granularity of mappings.

How long will it take to reach specific (arbitrary) size(s), for 
instance? E.g., to reach the current level of multihoming sites, which 
is roughly the number of 16-bit ASNs (65k)?

What do we think the growth curve will look like, and what the maximum 
rate of growth will be in, for example, 3 years' time?
(My guess is the curve will look like a disease propagation curve, with 
the rate being about C*(x)*(1-x) where x is the percentage "with" 
multihoming, and C is some constant.
> Simply pushing a full map to everywhere is going to be expensive, both 
> in space and time.  Pulling has latency issues.  Reducing the number 
> of places that have a full map seems like an attractive solution, but 
> still leaves the push scalability problem, albeit with one less order 
> of magnitude of an issue.  For the places that have only a cache, how 
> do you deal with cache misses?
>

The scaling issue is going to hit ITRs, almost exclusively.

ETRs will only need to know about RLOC->EID mappings (either popping off 
the outer tunnel header, or a deterministic transmogrification, possibly 
statically configured), which are very local in scope.

I think one question that might be helpful is, are there ways to scale 
things somewhat arbitrarily (possibly at modest hardware cost)?

Consider the following:

host -> mini-ITR -> (set of ITRs) -> (Internet) -> ETR -> host

I.e., the map is split across a set of ITRs, and front-ended with a box 
that knew how the EID space was partitioned across those ITRs.
The upper limit on per-ITR capacity (for push or pull of map contents) 
doesn't affect the size limit of the whole map. It scales arbitrarily.
(The specific mechanism choices of how to accomplish this are details 
that don't affect the concept.)

The scaling issue then becomes economic rather than technical.

As for map data propagation - the map data *should* be relatively 
static, since it won't contain reachability info (ideally).
Any combination of technologies (BitTorrent, AXFR/IXFR (DNS concept), 
multicast, ftp, LDAP) can be considered.
Scoping and localizing the data, authentication, delegation, and 
synchronization, are the major issues or trade-offs.

Brian D

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 10 Jan 2008 11:11:37 +1300

On 2008-01-10 08:05, Tony Li wrote:
> What's the right approach here?  Let's have a conceptual discussion and 
> leave out the mechanisms, please.

Can we clarify that conceptually we are talking about prefixes and not
individual interface EIDs, as far as the full map goes?
(Except, presumably, for a few special cases such as root servers.)

    Brian

---

From: Tony Li <[email-masked]>
Date: Wed, 9 Jan 2008 15:15:34 -0800

> (Except, presumably, for a few special cases such as root servers.)

Well, this should spark some useful discussion...  ;-)

Sorry, no, I don't think that you can make that assumption without a  
lot more justification and/or consensus building.  There are large  
organizations (you used to work for one of them,  I believe ;-) where  
there are multiple Internet connections that have geographically  
widely dispersed contact points.  Optimal  routing implies that there  
will be different locator preferences for different hosts.  Mobility  
within the organization itself implies that creating and maintaining  
meaningful identifier prefixes is going to prove challenging.

In other words, I think that we need host level granularity in the  
mapping function.

I *don't* think that we need per-interface granularity, as the  
semantics of an identifier should be host-specific, not identifier  
specific.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 9 Jan 2008 22:28:22 -0800

> One huge benefit CEF brings is the ability to resolve not only an  
> active path to it's adj but also the backup paths. So during the  
> failure of an active path you have immediate candidate already pre- 
> resolved as backup.

Yes, that is an implementation issue that provided a level of  
indirection. This helped the amount of data transmitted from the  
control-plane process to the line-card processors when an IGP path  
changed for an external prefix.

> Perhaps this entire discussion mixes the terminology ?

Yes, I think it does. CEF was not created because caching failed. It  
was created because the way caching was implemented was not optimal.

It was not a question of having a partial table (i.e. cache) versus a  
full table (i.e. a RIB's worth of data), but how the forwarding table  
was populated.

> eliminate the amount of them on the ITR) which would contain  
> multiple ETR locators and then pre-resolve all such locator  
> candidates in CEF ?

That is the way I have implemented it because when the locator  
priority and weights are the same, you want to hash at packet  
encapsulation time to select a locator address.

> So forwarding will be still cef based ... not cache based. Caching  
> would be only related to keeping mapping entires in the control  
> plane to eliminate the need for storing them all on all ITRs ?

I don't understand what is meant by "cached-based" versus "cef-based".  
An ITR can have this population rules:

1) Populate the mapping cache for active flows only.
2) Install a default mapping cache entry that points to an ETR that  
has more mapping
    entries.
3) Put all mapping entries from the Internet into the site ITR.

DNS does 1), CEF does 3), and 2) is done by doing a hybrid. We can  
swing on this pendulum based on traffic patterns. But here are the  
disadvantages of each:

1) Data-plane induced requests cause population. So latency is  
incurred. But latency
    is only for the first destination site request.
2) Stretch is increased to not require all ITRs must have a full table.
3) Requires lots of memory to store all mappings so latency can be  
eliminated. Solving
    this in one in scalable way will help scale xTRs in 2).

So choose your poison, you have to make a hard decision. So we start  
with caching and if the cache gets as large as full table, then we  
have moved the pendulum full swing.

Having said that, Eliot has mentioned with NERD, to start with a full  
table because it will begin small and then deal with the scaling as  
LISP or any other Loc/ID split solution becomes popular and ubiquitous.

Dino

---

From: Tony Li <[email-masked]>
Date: Thu, 10 Jan 2008 01:26:21 -0800

> CEF was not created because caching failed. It was created because  
> the way caching was implemented was not optimal.

Excuse me?  Caching failed miserably.  Per-host caching was growing  
to be larger than the number of prefixes in the RIB, and per-prefix  
caching would have covered 80% of the RIB.

Caching is NOT worthwhile when the working set is 80% of the full table.

> It was not a question of having a partial table (i.e. cache) versus  
> a full table (i.e. a RIB's worth of data), but how the forwarding  
> table was populated.

The population was expensive, but originally it was deemed worthwhile  
because the cached lookups were faster and certain folks didn't know  
how to do a tree walk and there was no regard for the resulting space  
complexity when used in the core.  The original host cache was simply  
designed for the enterprise and made no sense anywhere else.  In  
fact, even in large enterprises, there were issues simply due to the  
number of hosts and the smallish number of cache buckets originally  
allocated.

> So choose your poison, you have to make a hard decision. So we  
> start with caching and if the cache gets as large as full table,  
> then we have moved the pendulum full swing.

Or....  you cache in some locations, where the working set is small  
and you can afford latency (which, as we've discussed many times, can  
be further eliminated by piggybacking the mapping request with the  
DNS request) and you have other locations that get a partial or full  
feed.  [Sean Doran will note that this is Yet Another Problem That  
Was Already Solved Once For NNTP.]

The nice thing about this approach is that you make this "hard  
decision" on a per-box basis, so that you don't have to make one  
decision for the entire 'net.  Ya pays your money and you get service  
proportional to the money that you put in...

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 10 Jan 2008 01:45:39 -0800

> caching would have covered 80% of the RIB.

That's because of the granularity of the cache which required more  
entries. If the original fastswitching design used prefix-based  
population, it would have suffice.

And from today's statistics that in an average router, only 10% of the  
FIB entries are typically in use, the forwarding cache could be much  
smaller than the RIB.

> Caching is NOT worthwhile when the working set is 80% of the full  

I agree with that.

> The population was expensive, but originally it was deemed  
> worthwhile because the cached lookups were faster and certain folks  
> didn't know how to do a tree walk and there was no regard for the  
> resulting space complexity when used in the core.  The original host  
> cache was simply designed for the enterprise and made no sense  
> anywhere else.  In fact, even in large enterprises, there were  
> issues simply due to the number of hosts and the smallish number of  
> cache buckets originally allocated.

Yes, I am well aware there were more than one problem.

Who do you think reviewed for original CEF code?   ;-)

> and you can afford latency (which, as we've discussed many times,  
> can be further eliminated by piggybacking the mapping request with  
> the DNS request) and you have other locations that get a partial or  
> full feed.  [Sean Doran will note that this is Yet Another Problem  
> That Was Already Solved Once For NNTP.]

As you know, all the LISP mapping database mechanisms touches on all  
tradeoffs. We know how to do it each way, what's left is  
experimentation and a decision to pick one, or blend two.

LISP 2.0 is this design but many objected to having routing depend on  
directory when directory needed to depend on routing.

> decision for the entire 'net.  Ya pays your money and you get  
> service proportional to the money that you put in...

We can do that with a blend of LISP-ALT and NERD. Or LISP-ALT in the  
core with ITRs having a default mapping (so it's the default-mapper  
approach).

We presented this at the last two RRGs.

Dino

---

From: Tony Li <[email-masked]>
Date: Thu, 10 Jan 2008 02:25:26 -0800

On Jan 10, 2008, at 1:45 AM, Dino Farinacci wrote:

>>> Excuse me?  Caching failed miserably.  Per-host caching was  
>>> growing to be larger than the number of prefixes in the RIB, and  
>>> per-prefix caching would have covered 80% of the RIB.
>

Negatory there, good buddy.  Please read what I wrote.  A prefix  
based cache would have provided NO advantages whatsoever, as it would  
have instantly been fully populated.

> And from today's statistics that in an average router, only 10% of  
> the FIB entries are typically in use, the forwarding cache could be  
> much smaller than the RIB.

Which stats are these?  From an enterprise?  Or a core box?

>> Caching is NOT worthwhile when the working set is 80% of the full  

You seem to disagree with it above.

>>> It was not a question of having a partial table (i.e. cache)  
>>> versus a full table (i.e. a RIB's worth of data), but how the  
>>> forwarding table was populated.
>>
>>
>> worthwhile because the cached lookups were faster and certain  
>> folks didn't know how to do a tree walk and there was no regard  
>> for the resulting space complexity when used in the core.  The  
>> original host cache was simply designed for the enterprise and  
>> made no sense anywhere else.  In fact, even in large enterprises,  
>> there were issues simply due to the number of hosts and the  
>> smallish number of cache buckets originally allocated.
>

I do remember that.  I also remember who wrote it.  ;-)

>> Or....  you cache in some locations, where the working set is  
>> small and you can afford latency (which, as we've discussed many  
>> times, can be further eliminated by piggybacking the mapping  
>> request with the DNS request) and you have other locations that  
>> get a partial or full feed.  [Sean Doran will note that this is  
>> Yet Another Problem That Was Already Solved Once For NNTP.]
>
> As you know, all the LISP mapping database mechanisms touches on  
> all tradeoffs. We know how to do it each way, what's left is  

?  You missed my point: you pick all, simultaneously.  You let your  
particular working set characteristics in your particular location  
select which particular approach you use at that particular  
location.  All of the choices need to be integrated so that they  
result in one clean mechanism.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 10 Jan 2008 02:38:43 -0800

> based cache would have provided NO advantages whatsoever, as it  
> would have instantly been fully populated.

I don't believe the 80% number.

So we are not going anywhere. So let me ask this, if DNS resolvers  
need to have caches and browsers need to have caches, why shouldn't a  
mapping cache that could be as large as these other databases have a  
cache.

You guys that are not favoring caches can other favor full tables and  
that can't scale to 10^10.

So do you have a proposal?

> result in one clean mechanism.

We have already made that conclusion. You should have seen that at RRG.

Dino

---

From: Tony Li <[email-masked]>
Date: Thu, 10 Jan 2008 02:59:05 -0800

> I don't believe the 80% number.

Fine.  Call me a liar.  No more donuts for you.

> need to have caches and browsers need to have caches, why shouldn't  
> a mapping cache that could be as large as these other databases  
> have a cache.

Hello...  that's not a related point.

DNS resolvers don't have a working set that's 80% of all possible  
domain names.  Browsers don't have a working set that's 80% of all  
web pages.

A mapping cache is a fine and tractable object IF AND ONLY IF the  
working set at that location is tractable.

> You guys that are not favoring caches can other favor full tables  
> and that can't scale to 10^10.
>

I don't fall into "you guys" because a) I'm in favor of caches in  
some places and b) I'm against them in others.  I haven't noticed  
that opinion expressed by anyone else yet.  Yes, that's something of  
a proposal.

>> ?  You missed my point: you pick all, simultaneously.  You let  
>> your particular working set characteristics in your particular  
>> location select which particular approach you use at that  
>> particular location.  All of the choices need to be integrated so  
>> that they result in one clean mechanism.
>

No, what I saw was a total mess of mechanisms, with no coherency.

Upset,
Tony

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 10 Jan 2008 11:04:40 -0500 (EST)

> From: Tony Li <[email-masked]>

    > working set at that location is tractable.

Definitely a key architectual observation, although I'd rephrase it more
explicitly (although this is no doubt what you meant with your abbreviated
version) as:

 "A mapping cache is a fine and tractable object IF AND ONLY IF the working
  set at that location is enough smaller than the full map that the savings
  are significantly larger than the overhead (complexity, etc) of having a
  cache."

So there are two questions. The first is 'is this the case here'? The second
is, 'if not, is it practical to keep the full map'? Because if the answers
are 'no' and 'no', it's back to the drawing board....

So what about the first question? I think for a lot of ITR's (and maybe
almost all), this could be true. (Although this is just a guess, and could be
way wrong. For instance, spam and port-scanning seem to be from everywhere,
to everywhere, and that will blow the caches. Although since those are all
incoming traffic, if we design the system so that incoming requests carry, as
an optimization, the reverse mapping, we'd be OK, in terms of load on the
resolution system.)

Anyway, for 'normal' users, for smaller sites, even when you integrate across
a number of users, they are communicating with only a fraction of the
endpoints in the Internet anyway.

For another (and I think this is a more important factor), as the Internet
grows and the Web has a lot more content in other languages, you'll see a
natural splitting up of the user population into communities of interest;
English-speakers aren't going to be looking at a lot of sites in Mandarin,
etc, etc.

One thing that could throw a monkey wrench into this is if we see a lot of
cross-group hosting; i.e. web servers which contain content in many
languages, so that even if the user communities are disjoint, they may be
interacting with a single shared substrate of servers.

So except for the Googles of the world, maybe caching will work?

The obvious counter-point is going to be 'well, why doesn't caching work in
the routers, then'? I think that's because (especially in core routers) the
traffic aggregation as you go up the transmission hierarchy (think of it as
the same as going from surface roads up to high-speed limited-access
highways) naturally brings up a bigger set of sources and destinations. E.g.
in the US there's a lot of 'through' traffic (q.v. all the razz-ma-tazz in
the US about eavesdropping on transit traffic from a non-US-source to a
non-US-destination).

Now, maybe I'm wrong, and caching doesn't work in edge routers either (which
are in the same places ITR's will be), in which case maybe we do have a
problem. Anyone have any insight?

    > a) I'm in favor of caches in some places and b) I'm against them in
    > others.

More detail? Remember, there are no 'core ITR's'...

    >>> You let your particular working set characteristics in your particular
    >>> location select which particular approach you use at that particular
    >>> location. All of the choices need to be integrated so that they result
    >>> in one clean mechanism.

    >> We have already made that conclusion.

    > No, what I saw was a total mess of mechanisms, with no coherency.

Is coherency in the eye of the beholder? Systems with radically different
operating points are going to look radically different.

As long as each operates well, they don't interfere with one another, and
there is a good algorithm/whatever for deciding which one to use in a given
situation, is it a problem if they are very dissimilar?

	Noel

---

From: Tony Li <[email-masked]>
Date: Thu, 10 Jan 2008 09:04:49 -0800

Noel,

>   are significantly larger than the overhead (complexity, etc) of  

I disagree here, a bit.  It's possible to make the full map tractable  
and in that case, the cache is still tractable.  It would provide no  
savings over the full map at that point.  There are other  
architectural drivers that might still make it the preferred approach.

> So there are two questions. The first is 'is this the case here'?

It is in some cases.   Certainly in the SOHO kind of setting, the  
working set is likely to be trivially small.  However, (and Dino is  
the one who pointed this out) there are a number of large content  
providers that have content that has extremely broad distribution,  
are exceedingly latency sensitive, and thus would have a working set  
that's effectively the full map.

> The second

That very much goes to the granularity of the map.  If you go to a  
per-host map, then I have some concerns.  It would make things very  
expensive.  However, the number of places that would have this level  
of expense is very, very small.  Architecturally, it might still fly.

> So except for the Googles of the world, maybe caching will work?

Yes, I have to agree.  In fact, if you can make the system carry the  
reverse mappings (do they need to be secured?) you might even make  
the Googles work.

> the US about eavesdropping on transit traffic from a non-US-source  

That's correct.  At the edge of the network, the working set will be  
far smaller because you have a much smaller cross section of sources  
and destinations.  In the transit case, you'll simply die.

Note that we also saw this with netflow.  ;-) ;-(

> More detail? Remember, there are no 'core ITR's'...

Again, it's all about the working set.  Normal enterprises should be  
cacheable.  Google's might not be.  Comcasts would be cacheable, but  
you have to put the cache in the PE box, not the CE because the end  
user can't manage it.

> situation, is it a problem if they are very dissimilar?

Something that looks like three different systems still looks like  
three different systems.  What we're talking here is a smooth  
continuum of solutions with a common infrastructure.  There was no  
dial that you could set for "light", "normal", and "heavy duty".

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 11 Jan 2008 10:02:12 +1300

On 2008-01-10 12:15, Tony Li wrote:
> Sorry, no, I don't think that you can make that assumption without a lot 
> more justification and/or consensus building.  There are large 
> there are multiple Internet connections that have geographically widely 
> dispersed contact points. 

Correct. And that is a significantly harder problem than multihoming
for an enterprise network that only has one point of interconnection
to the outside.

> Optimal  routing implies that there will be 
> different locator preferences for different hosts.   Mobility within the
> organization itself implies that creating and maintaining meaningful 
> identifier prefixes is going to prove challenging.

Indeed it is challenging, so why bother? Having roamed around that
organization pretty widely over ten years, and roamed around it
virtually by remote VPN on a daily basis, I never had or needed
a meaningful prefix beyond 9/8. Internal servers, otoh, don't roam.
Externally visible servers aren't even in Net 9, because of various
techniques for security, load balancing, and traffic management.

Certainly I'd expect EID space for large enterprises to be sliced
and diced down to the geographical-site or even server-farm level.
I don't think it's necessary down to host level.

> In other words, I think that we need host level granularity in the 

I'd prefer to say: we need to support arbitrary granularity, but the
normal level will remain as a site (for some definition of site).
I wonder who's correct ?-)
> 
> I *don't* think that we need per-interface granularity, as the semantics 
> of an identifier should be host-specific, not identifier specific.

I hope that's right, but since you can't tell by looking at two IP
addresses if they refer to two interfaces on the same host, it's
unenforcable.

     Brian

---

From: Tony Li <[email-masked]>
Date: Thu, 10 Jan 2008 13:23:10 -0800

> for an enterprise network that only has one point of interconnection

Our job is to solve the hard problems, not just the easy ones.

>> Optimal  routing implies that there will be different locator  
>> preferences for different hosts.   Mobility within the
>> organization itself implies that creating and maintaining  
> Indeed it is challenging, so why bother?

Because our job is to fix the routing and addressing architecture.

> Having roamed around that

I'd say that's an admission (ok, Yet Another Admission) that the  
routing & addressing architecture isn't working.  When a site needs  
multiple prefixes for whatever reason, that's a problem that we  
should solve.

> I don't think it's necessary down to host level.

Why not?  That seems like a fairly arbitrary architectural decision.

> normal level will remain as a site (for some definition of site).

The distinction here escapes me (unless you're already thinking  
mechanisms).

>> semantics of an identifier should be host-specific, not identifier  

Oops.  s/identifier specific/interface specific/

> addresses if they refer to two interfaces on the same host, it's

Fair, but we needn't architect to assume interface specificity either.

Tony

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 11 Jan 2008 10:50:07 +1300

> Our job is to solve the hard problems, not just the easy ones.

Yes, of course - I was attempting to agree with you that we must
not ignore this case.

> Because our job is to fix the routing and addressing architecture.

OK, I was too telegraphic. I don't believe that mobility that preserves
a global routing prefix is a requirement. [Discussion of the value of
Mobile IP elided.] I do mean global - there are certainly scenarios where
mobile prefixes are a requirement, but those won't be prefixes that ever
need to be in the public Internet, so they aren't part of what I thought
we were discussing here.

> I'd say that's an admission (ok, Yet Another Admission) that the routing
> & addressing architecture isn't working.  When a site needs multiple
> prefixes for whatever reason, that's a problem that we should solve.

Actually I suspect that when you analyze *why* IBM's public web servers
aren't in Net 9, it will turn out to be because they need RLOCs but
Net 9 addresses behave like EIDs. So yes, I didn't mean to imply that
everything is hunky-dory.

> Why not?  That seems like a fairly arbitrary architectural decision.

Well, it's not so much a decision as a prediction of likely
operational practice... YMMV.

> The distinction here escapes me (unless you're already thinking

See previous comment - I think we need an architecturally general
solution but the scaling target is a matter of prediction.
> Fair, but we needn't architect to assume interface specificity either.

We agree on that.

   Brian

---

From: Tony Li <[email-masked]>
Date: Thu, 10 Jan 2008 13:57:19 -0800

On Jan 10, 2008, at 1:50 PM, Brian E Carpenter wrote:

> I think we need an architecturally general

Ok, that's a fair point.  I agree.

Tony

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Fri, 11 Jan 2008 11:24:40 +0100

On 10 jan 2008, at 22:02, Brian E Carpenter wrote:

>> There are large organizations (you used to work for one of them,  I  
>> believe ;-) where there are multiple Internet connections that have  
>> geographically widely dispersed contact points.

> for an enterprise network that only has one point of interconnection

People blame the routing table growth on multihoming (although it's  
obvious from the number of active ASes that one prefix/one AS  
multihoming can be blamed for only about 10% of the current DFZ) but  
now that PI is possible for IPv6 it's only a matter of time before the  
cat comes out of the bag that large organizations actually want  
multiple PI prefixes rather than just one.

> I don't think it's necessary down to host level.

Today, if I announce a /16 the whole world sees a /16. If I announce  
256 /24s, the whole world sees 256 /24s, and I can't announce 65536 / 
32s.

We could make a new system such that the length of cached prefixes  
isn't fixed, but can be adjusted based on the needs of the originating  
network, the amount of traffic and the availability of cache resources.

I.e., if an organization has a /16 EID prefix that is split up in a  
bunch of /24 used in different geographical/topological locations, and  
some of the individual addresses within those /24s are used by mobile  
hosts, it would be possible to push out a set of RLOCs for that /16.  
Those RLOCs map to the biggest links of the biggest locations used by  
the organization. Basically, these are home agents for all the  
addresses in the /16 that can tunnel any traffic that arrives for any  
address in that /16 to the host holding that address, whereever it  
happens to be at any given time. However, if the ITR has the caching  
resources and/or the amount of traffic is significant enough, the ETR  
can signal a more specific mapping back to the ITR.

In the case of a single organization with a short prefix that covers  
multiple more specifics, this is easy. More generally, the same thing  
could be done by aggregating a bunch of neighboring prefixes belonging  
to different organizations. This is harder because the aggregation  
point must be managed and it can't become a choke point.

---

From: Luigi Iannone <[email-masked]>
Date: Fri, 11 Jan 2008 11:51:59 +0100

Début du message réexpédié :

> De : Luigi Iannone <[email-masked]>
> Date : 10 janvier 2008 19:53:32 GMT+01:00
> À : Dino Farinacci <[email-masked]>
> Cc : Yakov Rekhter <[email-masked]>, Tony Li <[email-masked]>,  
> Brian Dickson <[email-masked]>, Brian E Carpenter  
> <[email-masked]>, "Templin, Fred L"  
> <[email-masked]>, Routing Research Group list <[email-masked]>
> Objet : Rép : [RRG] Tunnel fragmentation/reassembly for RRG map-and- 
> encaps architectures
>
>> We are assuming, at this point, nothing in terms of traffic  
>> locality. We are assuming the cache can be as large as the number  
>> of sites. But you can make guesses easily that a few number of  
>> sites will have to hold this large of a mapping database.
>>
>
> Unless a large number of sites use LISP-NERD ;-)
>
> Luigi
>
>
>
>> Dino
>>
>> --
> Luigi Iannone
> [email-masked]
>
>
>

Luigi Iannone

[email-masked]

---

From: Luigi Iannone <[email-masked]>
Date: Fri, 11 Jan 2008 11:52:36 +0100

Hi,

> Right, the guys at UCLB are gathering data on this.

Unfortunately we can offer only one viewpoint: ours ;-)

We have only traces from our gateway, would be very helpfull if  
someone can provides us with traces from other vanatge points.
Or, if privacy is an issue, we would be happy to lend out our code to  
analyze traces.

Luigi

Luigi Iannone

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 14 Jan 2008 11:23:31 +1300

Iljitsch,

On 2008-01-11 23:24, Iljitsch van Beijnum wrote:
> multihoming can be blamed for only about 10% of the current DFZ) but now
> that PI is possible for IPv6 it's only a matter of time before the cat
> comes out of the bag that large organizations actually want multiple PI
> prefixes rather than just one.
> 
> Today, if I announce a /16 the whole world sees a /16. If I announce 256
> /24s, the whole world sees 256 /24s, and I can't announce 65536 /32s.
> 
> We could make a new system such that the length of cached prefixes isn't
> fixed, but can be adjusted based on the needs of the originating
> the organization. Basically, these are home agents for all the addresses
> in the /16 that can tunnel any traffic that arrives for any address in
> that /16 to the host holding that address, whereever it happens to be at
> any given time.

For non-mobile hosts, I don't see why there'd be a tunnel; the
packet can simply be forwarded to the organization's IGP. For
mobile hosts, you seem to be describing a MIP proxy.

> However, if the ITR has the caching resources and/or the
> amount of traffic is significant enough, the ETR can signal a more
> specific mapping back to the ITR.

Iff the organization's ETRs communicate with each other.

> to different organizations. This is harder because the aggregation point
> must be managed and it can't become a choke point.

That sounds pretty messy from an admin point of view.

   Brian

---

From: Xu Xiaohu <[email-masked]>
Date: Mon, 14 Jan 2008 11:43:43 +0100

> -----邮件原件-----
> 发件人: [email-masked] [mailto:[email-masked]] 代表 Tony Li
> 发送时间: 2008年1月10日 18:05
> 收件人: Noel Chiappa
> 抄送: [email-masked]; [email-masked]
> 主题: Re: [RRG] Tunnel fragmentation/reassembly for RRG map-and-encaps
> architectures
> > The second
With regard to per-host map, even the number of places carrying full map is
very, very small, I believe we still need to adopt the distributed mapping
database, like CRIO or CONS, so as to scale well. CONS is an overlay just
for mapping purpose, not for user traffic forwarding, if the cache mechanism
is not acceptable for the reason of latency, initial packet loss or the DDoS
attack risk, is CRIO or home agent in Mobile IP an option?  The major
drawback of CRIO or home agent mechanism is longer forwarding path, so can
we use some anycast mechanism together to alleviate this pain?

Best wishes,
Xiaohu Xu

---

From: Christian Vogt <[email-masked]>
Date: Tue, 15 Jan 2008 13:34:57 +0200

Tony and Noel -

> reverse mappings (do they need to be secured?) you might even make

Two thoughts regarding the benefit of carrying reverse mappings in-band:

(1)  Does it really matter whether the cache is populated from a mapping
      table look-up or from mapping info carried in packets?  In the end,
      reverse and forward mappings consume the same cache resources.

(2)  You already hinted it:  Reverse mappings need to be secured.
      Verification will likely cause the same overhead at a packet
      receiver as a mapping table look-up.

- Christian

---

From: [email-masked] (Noel Chiappa)
Date: Tue, 15 Jan 2008 21:35:42 -0500 (EST)

> From: Christian Vogt <[email-masked]>

    > Reverse mappings need to be secured.

That was my conclusion too. I spent a great deal of time working out an
efficient and tractable way of securing the reverse mappings (by signing
them, using public/private key pairs); not sure if all that has made it into
the LISP documentation yet.

It's somewhat complicated (as is any well-designed secure system, because you
have to deal with all sorts of cimcumstances), but it has the advantage that
whenever you get a binding (from any part of the namespace), you can tell if
it's a legit binding just from the data that comes along with the binding.

    > receiver as a mapping table look-up.

Not sure what you mean here; if you mean just in terms of computation, I
think verification will be more expensive than looking up a mapping,x but you
only need to verify a mapping when you get it in, not every time you use it.
(And why would a receive be looking up mappings anyway? Surely it's the
sender that has to look up mappings, no?)

	Noel

---

From: Christian Vogt <[email-masked]>
Date: Wed, 16 Jan 2008 10:19:44 +0200

Hi Noel!

Would public-key authentication of an ID/locator mapping really reduce
the overhead at the receiving side compared to a look-up of the mapping
in a global, trusted directory (or in a local copy of the directory)?

I don't think so because, for the receiving side to verify that the keys
used to sign the ID/locator mapping really belong to the ID owner, the
receiving side has to check the ID/public-key binding, and this requires
a look-up in a trusted directory (PKI in this case) as well.  So the
receiving side has to do a directory look-up in any case -- be it to get
the ID/locator mapping, or to verify an ID/public-key mapping.

> Not sure what you mean here; if you mean just in terms of computation [...]

I meant in terms of required directory look-ups.  Computational overhead
of public-key authentication comes in addition to the overhead of
looking up the ID/public-key mapping.

> sender that has to look up mappings, no?)

In a world without evil, I would agree.  But since we have to combat
mapping spoofing, either we use self-certifying mappings (as in Six/One,
e.g.), or the receiver must do a look-up in some trusted directory, too.

- Christian

PS:  In all of the above, we are talking about the initial mapping
provisioning for the receiving side.  While the benefits of public-key
authentication are IMO limited in this case, public-key authentication
may very well be suited for mapping /updates/, which a sending side may
want to communicate to a receiving side for TE reasons.

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 16 Jan 2008 10:53:21 -0500 (EST)

> in a global, trusted directory ..
    > I don't think so because, for the receiving side to verify that the
    > keys used to sign the ID/locator mapping really belong to the ID owner,
    > the receiving side has to check the ID/public-key binding, and this
    > requires a look-up in a trusted directory (PKI in this case) as well.
    > So the receiving side has to do a directory look-up in any case -- be
    > it to get the ID/locator mapping, or to verify an ID/public-key mapping.

{Visualize JNC with a *very* large Cheshire-Cat grin!}

Yes, this was the exact difficulty I struggled with for some weeks! I finally
had a brainwave, and realized that if the mountain will not come to Mohammed,
then Mohammed must go to the mountain...

In a simplified form (to make understand the basic concept easier), the
signing is not done by each individual aCAR (i.e. authoritative source for
bindings - which would necessitate, as you observe, each aCAR having a
separate key, which you'd have to acquire securely, putting you right back
where you were, in terms of communication overhead); rather, the aCAR passes
its bindings up the hierarchy to the root, which signs them, and passes the
signed bindings back down to the aCAR. It is those signed bindings which the
appropriate entity hands out (either in response to a request, or piggybacked
on a request for another binding).

Since we trust the delegation hierarchy already (if you are doing a classical
lookup), if we use the same hierarchy to pass bindings up to be signed, and
then returned, we have exactly the same level of dependability.

In practise, for purely practical reasons (i.e. limiting damage in case of a
security breach) there wouldn't be a single root key (these improvements were
mostly suggested by Dave Oran, IIRC). Rather, we'd divide the namespace up
into a series of zones, each of which would have a separate key, and no
machine should hold more than one. In addition, there'd be a two-phase
system, with 'master' zone keys kept offline in a secure facility, and used
to sign 'secondary' sequence-numbered zone keys, which are what is actually
used online to sign bindings.

Yes, I know it sounds complicated, and it is - and I worry about that a lot,
because complexity always worries me a lot. ("Perfection has been attained,
not when there is nothing left to add, but when there is nothing left to take
away.") This seems to be a typical thing with security, though, that it gets
complicated - seemingly much more complex than the typical security that we
use e.g. on our houses.

The way I look at it, though, is that in a world where a master lock-picker
could try hundreds of doors in a second, we'd all be using much better locks
on our houses - and the wonderful Internet brings us not just data from a
myriad of sources around the world in the blink of an eye, it brings us
croooks from a myriad of sources around the world in the blink of an eye.
Sigh, progress always has costs as well as benefits...

    > Computational overhead of public-key authentication comes in addition
    > to the overhead of looking up the ID/public-key mapping.

Right, but I am informed that checking authentication is a lot less
computationally intensive than signing something - which is good for us, and
(helpfully) just the right direction for such an asymmetry!

    >> (And why would a receive be looking up mappings anyway? Surely it's
    >> the sender that has to look up mappings, no?)

    > But since we have to combat mapping spoofing, either we use
    > self-certifying mappings (as in Six/One, e.g.), or the receiver must do
    > a look-up in some trusted directory, too.

Sorry, not sure that I followed that. Did you mean that if you received a
'gratuitous' binding, piggybacked on a request for a binding that you held,
you'd have to do a query on that gratuitously-provided binding, to verify that
it was valid, and not a spoof?

If so, I think the built-in authentication of bindings (above) solves that one.

    > In all of the above, we are talking about the initial mapping
    > provisioning for the receiving side.

"Receiving" is a little confusing to me, since both sides are receiving
stuff. I prefer the terms 'client' and 'server', on the assumption that
although not all pairwise connections are client/server, many are, and for
all client/server interactions, the client does the lookup of the 'server
binding' first.

So, in that terminology, what I think you said there was: "In all of the
above, we are talking about providing the binding of the client, at the server
side", right?

    > While the benefits of public-key authentication are IMO limited in this
    > case

On the contrary, it's the only way I can see to authenticate the client's
binding 'on the spot' (i.e. without additional network traffic) if you
gratuitously provide it to the server, piggybacked on the client's request
for the server's binding.

    > public-key authentication may very well be suited for mapping
    > /updates/, which a sending side may want to communicate to a receiving
    > side for TE reasons.

I'm assuming this is because you're working with a model where, along with
the binding, one would have gotten a key which could/would be used to sign
updates to the binding?

	Noel

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 16 Jan 2008 11:10:13 -0500 (EST)

PS: I don't know if this is all covered in the CONS documentation yet; I did
a lot of thinking/work on CONS last summer, and it may not have all be
written up in specs yet.

My advice to the LISP people was that they didn't need to implement this
security stuff in any prototype implemenatations they were doing (where
manpower is limited, and the chief concern is trying to get some real-world
data on things like delays, unforseen operational issues, etc), because it
doesn't change the fundamentals of the operation at all; it's just security
sugar layered over everything.

However, it has all been thought through and worked out, to make sure that
the basic architecture they are trying out *is* securable.

	Noel

---

From: Brian Dickson <[email-masked]>
Date: Wed, 16 Jan 2008 11:33:50 -0500

(Sorry for top-replying, but for a short reply to a big message, it's a 
bit nicer for the reader.)

One obvious place to put the delegations, and to manage the PKI, is with 
dnssec signed DNS zones,
where the delegations themselves would already be done. I don't know 
about the timeline for deployment
of signed root/TLD zones (especially not for specific TLDs), but 
something like either ip6.arpa (or in-addr.arpa
for IPv4), or some new second-level domain under a signed TLD.

If the EID->RLOC mappings are done in DNS, with some kind of resource 
record under a delegated
address-specific zone tree (such as, or similar to, ip6.arpa), the 
signing works very well, and additionally,
the tree can be walked to fully populate the entire set of EID->RLOC 
mappings.

We don't need to reinvent the wheel, IMHO - just take advantage of the 
dnssec.

Brian Dickson

---

From: Eliot Lear <[email-masked]>
Date: Wed, 16 Jan 2008 17:53:36 +0100

For a number of these approaches, reverse mapping is all but impossible 
for the simple reason that there could be ambiguity when a particular 
end point in the DFZ represents connectivity for more than one "client" 
network.  Put in terms of LISP: the ambiguity hits when an ETR 
represents more than one EID prefix.

Eliot

---

From: Brian Dickson <[email-masked]>
Date: Wed, 16 Jan 2008 12:06:07 -0500

Eliot Lear wrote:
> For a number of these approaches, reverse mapping is all but 
> impossible for the simple reason that there could be ambiguity when a 
> particular end point in the DFZ represents connectivity for more than 
> one "client" network.  Put in terms of LISP: the ambiguity hits when 
> an ETR represents more than one EID prefix.
>
This ambiguity would only be the case if the ETR has only one RLOC.
(Hint - this is a "design implementation" detail that differentiates 
different LISP proposals, either formally documented or under discussion 
on the list.)

If a single ETR has multiple EID prefixes, *and* multiple RLOC addresses 
(possibly RLOC *block* addresses) assigned to it, then it *may* be 
feasible to have an unambiguous (and possibly even completely 
deterministic) reverse mapping.

Brian Dickson

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 16 Jan 2008 12:20:54 -0500 (EST)

> From: Eliot Lear <[email-masked]>

    > For a number of these approaches, reverse mapping

First, a terminology suggestion: I have also been called the binding between
the client's EID and RLOC the 'reverse' bindings, but that is probably not
the best term for that binding, because a 'reverse binding' is usually the
binding between two names, but in the other direction to normal, e.g. in our
case an RLOC->EID binding.

So I've tried to started calling these second EID->RLOC bindings (of the
pair\ of EID->RLOC bindings needed for two endpoints to communicate) 'client
bindings'; to be exact, I use this term for the second of a pair of bindings,
one from each end - on the assumption that although not all pairwise
connections are client/server, many are, and for all client/server
interactions, the client does the lookup of the 'server binding' first.

    > is all but impossible for the simple reason that there could be
    > ambiguity when a particular end point in the DFZ represents
    > connectivity for more than one "client" network.

The use of the term "end point" there is probably a bad idea, because an 'end
point' is the thing an EID names. I assume you meant 'exit point'?

If so, I agree with you, but because it is actually 'client bindings' we are
talking about, not 'reverse mappings' (which is where the many EID's -> one
RLOC ambiguity arises), it is not a problem - I don't offhand know of many
uses for reverse bindings.

	Noel

---

From: Christian Vogt <[email-masked]>
Date: Wed, 16 Jan 2008 19:29:20 +0200

Eliot,

I disagree because we are talking about mapping validation here.  And
for this, we need a mapping look-up that is the same as the normal
forward mapping look-up:  given an ID, you get a list of locators.

But I guess this was a misunderstanding anyway.  I shouldn't have called
it "reverse mapping", but rather "mapping validation".

- Christian

---

From: Christian Vogt <[email-masked]>
Date: Wed, 16 Jan 2008 19:56:28 +0200

Noel -

Ah, you are using global trust anchors.  That will work, yes.

One question, though:  Who will be the entity in charge of operating a
root CDR (and hence of signing ID/locator mappings)?  This entity will
be in a very powerful position -- more powerful than any entity can be
in today's Internet.  There is no single entity today that has control
over IP connectivity in a large part of the Internet.

OTOH, we do have a similar dependency on root DNS(SEC) servers.  That's
for domain-name/address mappings, though, not for base IP connectivity.

Now back to your response:

>> self-certifying mappings (as in Six/One, e.g.), or the receiver
>> must do a look-up in some trusted directory, too.
> 
> Sorry, not sure that I followed that. Did you mean that if you
> received a 'gratuitous' binding, piggybacked on a request for a
> binding that you held, you'd have to do a query on that
> gratuitously-provided binding, to verify that it was valid, and not a
> spoof?
> 

Yes, that's correct.

> "Receiving" is a little confusing to me, since both sides are
> receiving stuff.

By receiving side I meant a tunnel router receiving a gratuitous mapping
in-band in a packet.  My focus here was on *initial*, though, as opposed
to a mapping update that the tunnel router may receive *subsequently*.

>> /updates/, which a sending side may want to communicate to a
>> receiving side for TE reasons.
> 
> I'm assuming this is because you're working with a model where, along
> with the binding, one would have gotten a key which could/would be
> used to sign updates to the binding?

Yes, that's right.

Thanks for discussing this in detail!

- Christian

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 16 Jan 2008 10:54:29 -0800

> impossible for the simple reason that there could be ambiguity when  
> a particular end point in the DFZ represents connectivity for more  
> than one "client" network.  Put in terms of LISP: the ambiguity hits  
> when an ETR represents more than one EID prefix.

Not a problem Eliot, you use the mapping that is associated with the  
EID-prefix the source address matches.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 16 Jan 2008 10:56:29 -0800

> different LISP proposals, either formally documented or under  
> discussion on the list.)

Only true if the ETR is gleaning a source EID to a source RLOC. But  
you want to validate the mapping so the ETR sends a Map-Request (with  
a newly allocated nonce) back to the ITR where the Map-Reply in  
response has a complete locator-set for the *EID-prefix* (that the  
original invoking source EID matches to).

This is the mobility feature we prototyped in LISP and are not  
publicly admitting.  ;-)

Dino

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 16 Jan 2008 14:06:05 -0500 (EST)

> be in a very powerful position

Well, to start with, there is no single entity which signs bindings for the
entire namespace - as I mentioned, we would probably want to split the
namespace up into zones (e.g. maybe /8's), and have a separate key (and
signing entity) for each zone, in part so that no single break-in can
compromise (and require re-signing of) bindings across the entire nameapace.

Your question raises a separate issue, though, which is that in that scheme
as I describd it, each portion of the namespace would indeed have one entity
which is in charge of signing bindings for it, and yes, that would be a
powerful position.

We can change that, but it's really a question of how much configuration
overhead one wishes to incur, versus the amount of flexibility in terms of
distributing that 'power'. E.g. we could have multiple *wholly independent*
signers for each zone of the namespace (each would have a separate private
'primary' key), and so a signed binding would be marked with the identity of
the verifier which has signed each.

Etc, etc, etc. It's all depends on how much flexibility the users want; more
can be built in, but it has a cost.

    > more powerful than any entity can be in today's Internet. There is no u
    > single entity today that has control over IP connectivity in a large
    > part of the Internet.

Well, what about the DNS root? Yes, there are multiple roots, but they contain

    > for domain-name/address mappings, though, not for base IP connectivity.

True.

    > Thanks for discussing this in detail!

Thanks, but no thanks are really needed - I am very interested to hear any
comments people have to make, because I am concerned that there are things I
have missed, or that there are operational aspects which I haven't taken
sufficiently into consideration, stuff like that. I'm always ready to hear
anything that might improve the design!

So, let me know what you think about the 'multiple independent signing
authorities' concept as a way to deal with the sole (per zone) global trust
anchor issue you raised; if that doesn't work, I'll see if I can come up with
something better.

	Noel

---

From: Brian Dickson <[email-masked]>
Date: Wed, 16 Jan 2008 14:44:37 -0500

> which is in charge of signing bindings for it, and yes, that would be a
To use the DNSSEC model, you *don't* want the top level entity signing 
the *data*.
(It has the power/security/trust issues described above, *and* it 
doesn't scale well at all.)

What DNSSEC does, is sign *delegations*, until the leaf nodes, who sign 
their own data.

The proper analog for EID->RLOC binding mappings would be:

DNS root zone signs delegation to appropriate TLD operator (e.g. arpa).
TLD operator signs delegations to RIRs
RIRs sign delegations to LIRs
LIRs sign delegations to customers
[and further delegations are certainly possible to essentially arbitrary 
depth].

In each case, the zone is self-signed as well as signed by the parent.

Since in no case is the data itself signed by anyone other than the 
delegatee, the risk is limited to key data scoped
appropriately, where key rollover is handled by the parent. Only root 
key rollover results in "flag day" issues,
something already well known for the whole trust anchor model.

Brian Dickson

---

From: David Conrad <[email-masked]>
Date: Wed, 16 Jan 2008 12:01:32 -0800

Noel,

> compromise (and require re-signing of) bindings across the entire  

Isn't the implication of this a need to rollover multiple keys for the  
multiple namespace authorities, that is, instead of having 1 trust  
anchor that you periodically rollover, you have 256?  (I'm assuming  
you would need to rollover keys as a normal part of security hygiene).

> distributing that 'power'.

And how much 'touching' of the trust hierarchy you want to impose on  
the lookup agents.

>> for domain-name/address mappings, though, not for base IP  

Being somewhat in the crosshairs of the root signing situation with  
DNSSEC, I should probably point out that the political ramifications  
of a single root are decidedly non-trivial (and that's just for  
something that has limited impact on whether packets get from A to  
B).  But then again, having multiple roots means the lookup agents  
have multiple chances of getting things wrong.

> anchor issue you raised; if that doesn't work, I'll see if I can  

What are your thoughts on multiple independent signing authorities,  
with each authority signing the bindings for the entire namespace?  If  
you have (say) 2 independent trust anchors for the entire namespace  
then you could cross validate (if necessary... sort of like getting a  
second opinion if validation fails) while only having 2 things to  
break when you configure your lookup agent...

Regards,
-drc

---

From: Brian Dickson <[email-masked]>
Date: Wed, 16 Jan 2008 15:40:17 -0500

> want to communicate to a receiving side for TE reasons.
I think discussion on this is certainly going to be good at 
understanding the security
implications of various design decisions and models, including looking 
at where "evil"
packets might be seen, what they might look like, and what impact they 
could have.

(I'll try to keep this short and structured.)

We're considering traffic between a client and server.
We'll use lower-case "c" and "s" to designate respective elements.

Hc -> Hs (client sends packet to server):

    Hc(EIDc,EIDs) -> ITRc

        ITRc(RLOCc1,RLOCs1) -> {Internet} -> ETRs
        ETRs(EIDc,EIDs) -> Hs

Hs -> Hc (server sends response):

    Design choice 1a (asymmetric use of  ITR/ETR pairs):

        Hs(EIDs,EIDc) -> ITRs
        ITRs(RLOCs2,RLOCc2) -> {Internet} -> ETRc
        ETRc(EIDs,EIDc) -> Hc

    Design choice 1b (symmetric function on ITRs and ETRs):

        Hs(EIDs,EIDc) -> ETRs
        ETRs(RLOCs2,RLOCc2) -> {Internet} -> ITRc
        ITRc(EIDs,EIDc) -> Hc

For purposes of this analysis, we will presume that "evil" packets will 
only show up via "Internet" paths above.

Possible "evil" intentions:

   1. Hijack client identity
   2. Hijack server identity
   3. Spoof packets into stream
   4. Denial of Service
   5. (Any others I have overlooked?)

Hijack client identity: This would require changing either static 
mapping, or dynamic (update) mapping.
Prevention methods:

    * Secure static mappings (e.g. via DNSSEC)
    * Limit dynamic information to reachability only (relative to static
      mappings)
    * Require forward lookups on EIDc for any Hs->Hc traffic

Hijack server identity: same as Hijack client identity

Spoof packets into stream:

    Spoofed packets have spoofed-EID with actual RLOC values (can't be
    stopped by BCP-38)
    Prevention methods:

        * validate source EID->RLOC (as appropriate, if possible),
          reject mismatches

    Spoofed packets have spoofed-EID with spoofed RLOC values (spoof
    with real EID->RLOC mapping)

        * cannot be detected by ETRs (!!)
        * can be prevented by BCP-38 (which is far from universal)
        * likely to be one DoS vector

Denial of Service: in addition to any vectors above, spoofed 
reachability signaling can result in complete DoS
Prevention methods:

    * secure signaling control plane/path (may not scale)
    * limit exposure by de-preferring RLOCs rather than withdrawing them
          o DoS only possible if one or more RLOCs is truly suffering an
            outage
          o window of vulnerability can be further limited by updates to
            static mappings, either when an outage happens, or in
            response to a DoS+outage
          o TE capability may be best accomplished administratively
            rather than dynamically, analogous to MX preference levels
            on EID->RLOC map entries

Summary:
Any design should include:

    * secure EID->RLOC mappings
    * signaling of reachability rather than new RLOC mappings
    * signaling of degradation (deprefering RLOCs) rather than outage
      (unreachable)
    * forward lookups on source EID->RLOC to validate received packets
    * TE done by administrative control on mappings rather than via
      signalling
    * push further adoption of BCP-38 in the operator community

All other kinds of DoS traffic, are not unique to LISP, but rather are 
general to any client-server or p2p connections.

Brian Dickson

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 16 Jan 2008 16:38:48 -0500 (EST)

> From: Brian Dickson <[email-masked]>

    > One obvious place to put the delegations, and to manage the PKI, is
    > with dnssec signed DNS zones, where the delegations themselves would
    > already be done.

Using the DNS to hold EID->RLOC mappings was discussed earlier (and in fact,
one version of LISP, I forget which now) proposes doing that. I got the
impression that people weren't wild about the concept, for a variety of
reasons, which I will let them give lest I not do a very good job of it.

    > If the EID->RLOC mappings are done in DNS ... the tree can be walked to
    > fully populate the entire set of EID->RLOC mappings.

That's not a very efficient way to give everyone a copy of the table of
bindings, in advance. If we want to operate in that mode (and there are
doubters, see the previous conversation betwen Tony and, Yakov, I think it
was), there are much better ways to do that.

<different message>

    > the *data*. ... it doesn't scale well at all.

Well, again, in the design I described the root isn't signing anything,
because the signing authority of the namespace is partitioned into zones, and
separate machines would usually be responsible for each zone (both to limit
both the scope of what's affected by a security breach, and to reduce the
amount of stuff that has to be resigned when there is a breach).

Second, given that in most cases bindings should be being updated 'often', is
there really a problem here? I mean, as long as it's a constant slow trickle
of requests for resigning, it shouldn't be a problem. If the load does become
too high, since any reasonable design should allow replicated servers, just
add more servers to that pseudo-node in their resolution hierarchy.

The only time there might be an issue is if there's a security breach, and a
lot of stuff has to be re-signed in a hurry. Not sure how hard we need to
provide for that one.

    > delegatee, the risk is limited to key data scoped appropriately, where
    > key rollover is handled by the parent.

The problem is that now we have lots of keys - lots and lots of keys. Enough
keys so that you probably don't have them all pre-loaded.

Only now we're back to the problem Christian alluded to, which is that you've
bought yourself a zero performance gain: instead of needing to go out and ask
for a binding, you try and speed things up by 'gratuitously' getting the
signed binding you will need - but before you can trust it, you have to go get
the key it was signed with - which is just as slow as getting the binding!

The system I described, with the namespace dividided into a modest number of
zones, each with a separate key, was designed to balance two competing
problems: having too many keys, and the hassle caused by the compromise of a
key. Turn the knob too far one way, you have too many keys; turn it too far
the other way, and a compromise results in too big a problem.

I don't know what the right setting is, I'm keen to have the users figure
that out for themselves. But it can't be a totally local choice, because if
*I* want minute zones to minimize the effects of compromises, *other* people
wind up paying a big part of the cost (by having to support those small
signing zones).

I dunno, my email to Christian earlier discussed the possibility of having
multiple different keys (and signers) for a zone (to avoid giving the signer
too much power); a possibility for this situation is to extend that to allow
multiple zone signing delegation hierarchies, so people who wanted different
settings on that virtual 'knob' (above) could chose different ones.

(So you could have, e.g. a coarse delegation hierarchy, and a fine one, and
people could pick which one they wanted; if they wanted to have to have the
greater security of more keys, they'd also be accepting the greater overhead
of more keys.)

The thing is that that is again more complexity, and I'm wondering if it's
really worth it. I'm very concerned about the complexity level as it is. In
fact, I think I'd be more likely to say: 'if anyone wants better security,
they'll have to build a separate system to sign bindings, rather than make
the default public one overly complex'. I think that's a viable design
approach; people who want triple-titanium security can roll their own.

	Noel

---

From: Brian Dickson <[email-masked]>
Date: Wed, 16 Jan 2008 17:11:49 -0500

> was), there are much better ways to do that.
There's two distinct things:
1) how to *publish* the data;
2) how to *serve* the data

Both need to be secure to be trustworthy. But they do not need to be the 
same.

For example, one or more secured servers, walking the tree (which is 
dnssec-signed), and then
publishing the mapping table suitable for fast queries/responses, or 
pushed to whoever wants the full table.

Having the publishing of data being directly under end-site control, 
IMHO, is an operational must.

Having the data serving stuff done some other way, is an optimization.

(The issue of trust, is not limited to the query/answer stuff; it also 
has to handle cross-jurisdictional,
third-party, and contractual transitive-ness types of requirements. If I 
can't sue you, I'm not going
to trust you to do something for me.)

Brian Dickson

---

From: Tony Li <[email-masked]>
Date: Wed, 16 Jan 2008 15:21:47 -0800

[Multi-reply...]

> the basic architecture they are trying out *is* securable.

As you mentioned elsewhere, there is no progress without pain.  One  
of those pain points is that security is now a much more stringent  
requirement today than it was previously, and having proven, deployed  
security mechanisms as part of a proposal would seem to be a Very  
Good Thing, IMHO.  Just having the claim that something is securable  
is only going to hold so much water and will definitely attract  
skeptics.

On Jan 16, 2008, at 8:33 AM, Brian Dickson wrote:
> We don't need to reinvent the wheel, IMHO - just take advantage of  
> the dnssec.

That would be fine by me.  However, DNSsec has been awaiting  
deployment for about a decade now.  I'm not hopeful that this is  
going to happen anytime soon.

More generally, my friends in the security and operations communities  
point out that, in general, approaches with a full blown PKI  
infrastructure are simply too heavyweight to be pragmatically  
deployable.  There are simply too many interdependencies.  Their  
strong suggestions point much more towards pairwise security and/or  
web-of-trust approaches (ala PGP).

On Jan 16, 2008, at 2:11 PM, Brian Dickson wrote:
> Both need to be secure to be trustworthy.

Is this really true?  Does serving the data truly need to be secure  
as long as the data is authentic, accurate, timely, etc.?

If we can avoid securing the mapping transport layer, it would be a  
very big win.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 16 Jan 2008 15:23:45 -0800

> sugar layered over everything.

And we took your advice.

Dino

---

From: Brian Dickson <[email-masked]>
Date: Wed, 16 Jan 2008 19:05:59 -0500

Tony Li wrote:
> deployment for about a decade now.  I'm not hopeful that this is going 
> to happen anytime soon.
>
At this point, IMHO, DNSsec is likely to see reasonably wide deployment 
before the really wide deployment of IPv6. (0.5-1.5 years for sure.)
> web-of-trust approaches (ala PGP).
That works for only so many degrees of separation, IMHO.
On the other hand, I would expect the value of LISP is only seen when 
sites whose multihoming is dependent on LISP, are globally reachable via 
LISP.
Which means that arbitrary unrelated entities need some way of trusting 
"the system", rather than each other.
Especially if a LISP site is offering "real" services (e.g. any kind of 
sales function).
> Is this really true?  Does serving the data truly need to be secure as 
> long as the data is authentic, accurate, timely, etc.?
>
It needs to be reliably reachable, un-hijackable from a routing 
perspective, and read-only (i.e. get its data via a secure channel).
But it does not actually need to be secure, if these other things are 
true, IMHO.
> If we can avoid securing the mapping transport layer, it would be a 
Yep.

Brian

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 17 Jan 2008 11:10:54 +0900

> (helpfully) just the right direction for such an asymmetry!

Ok. I used to be paranoid for a living (=work with security stuff)..  
There are certain schemes where the verification of something is  
considerably more expensive (for example, check http://en.wikipedia.org/wiki/Hashcash) 
, but in public-key cryptography the cost of encryption, decryption,  
signing and signature verification are typically roughly of same  
minimum cost[1]. For example, with RSA, all four operations boil down  
to exponentiation + modulo operations with big numbers, give or take  
hashing along the way.

Looking at the 'success' of anything that involves something  
certificate-like (hint: https is only really successful 'open' system,  
and that works by ignoring half the security features such as key  
lengths, certificate revocation lists and so forth), I would really,  
really like to steer clear of any really secure public-key based  
scheme in this system.

Considering the BGP+TCP-MD5 is considered 'secure enough' by the  
people around these days, while it is in truth about as secure as  
sending data in envelopes made of clear plastic, I don't think this  
system needs to be more ambitious if it means orders of magnitude  
worse performance.

>> must do
> received a

Unfortunately it is not computationally feasible.

> for the server's binding.

I am not actually claiming all of this is completely impossible; the  
actual public-key infrastructure itself I find deeply depressing  
though, so I would prefer to avoid it if possible. For end nodes/edge  
routers, piggybacking+signature verification would still work  
reasonably well, given appropriate rate limiting, due to the extra  
processing power and potential slight performance savings involved.  
For anything in the core, 'not going to happen' sums what I think of  
the piggybacking schemes that involve anything else than blind trust.

Blind trust sounds slightly dangerous though..

Cheers,

-Markus

[1] This assumes _small_ data length; the sign+verify is faster than  
encrypt+decrypt over large blocks of data due to the fact that only  
hashing is performed on the data itself, but given small input data  
amounts, the costs are similar. Sign/verify stay same cost regardless  
of data size, however.

---

From: Christian Vogt <[email-masked]>
Date: Thu, 17 Jan 2008 13:33:51 +0200

Dino -

> Only true if the ETR is gleaning a source EID to a source RLOC. But you 
> want to validate the mapping so the ETR sends a Map-Request (with a 
> newly allocated nonce) back to the ITR where the Map-Reply in response 
> has a complete locator-set for the *EID-prefix* (that the original 
> invoking source EID matches to).

This is a lightweight alternative to the public-key-crypto approach that
Noel is proposing.  Its advantage:  less overhead in terms of processing
and administration.  Its disadvantage:  need to buffer or drop packets
during the mapping validation round-trip (Map-Request/Reply).

Are you buffering or dropping in your current LISP implementation?

- Christian

---

From: Christian Vogt <[email-masked]>
Date: Thu, 17 Jan 2008 13:32:25 +0200

> So, let me know what you think about the 'multiple independent
> signing authorities' concept as a way to deal with the sole (per
> zone) global trust anchor issue you raised; if that doesn't work,
> I'll see if I can come up with something better.

Noel,

the importance of DNS for most of today's Internet traffic is IMO an
indication that a similar dependency on a mapping system -- which your
proposal would bring about -- may well be acceptable.

It is certainly true that a dependency on DNS is less critical than a
dependency on an address mapping system because the former does not
directly affect IP connectivity.  (I brought up this argument myself.)
But this difference in criticality may be negligible given that most of
today's use of the Internet would still fail if DNS misbehaved.

I do not (yet) have a strong opinion on this matter, however.  I brought
it up in order discuss it and get a better understanding.  Would be
interesting to hear also other people's opinion about it.

- Christian

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 17 Jan 2008 09:08:22 -0500 (EST)

> From: David Conrad <[email-masked]>

    >> there is no single entity which signs bindings for the entire
    >> namespace - as I mentioned, we would probably want to split the
    >> namespace up into zones (e.g. maybe /8's), and have a separate key
    >> (and signing entity) for each zone, in part so that no single break-in
    >> can compromise (and require re-signing of) bindings across the entire
    >> nameapace.

    > Isn't the implication of this a need to rollover multiple keys ... that
    > is, instead of having 1 trust anchor that you periodically rollover,
    > you have 256? (I'm assuming you would need to rollover keys as a normal
    > part of security hygiene).

Well, I'm not so sure. I'm not a crypto math expert, but... my understanding
was that systems which generate new keys periodically (such as WPA) do so
because in the particular encryptions systems they use, if you have enough
encrypted text, it increases the chances you can find the key. So, they
change their keys on a regular basis.

AFAIK, this isn't an issue with public-private encryption, so I don't see a
need to do periodic key rollover. (If I'm wrong about any of the crypto
aspects of all this, someone please enlighten me! :-)

    >> it's really a question of how much configuration overhead one wishes
    >> to incur, versus the amount of flexibility in terms of distributing
    >> that 'power'.

    > And how much 'touching' of the trust hierarchy you want to impose on

Sorry, didn't follow that - can you expand a bit? I would have assumed that
there's no extra overhead in the lookup agents (unless they want to be
paranoid and check out that *all* the signatures are valid). And course
there's no extra network traffic at the lookup agents because the whole point
of this scheme is to have *no* network traffic at a lookup agent to check the
signature on a binding!

    >> authorities' concept as a way to deal with the sole (per zone) [signing
    >> authority] issue you raised

    > with each authority signing the bindings for the entire namespace?
    > ... then you could cross validate (if necessary... sort of like getting
    > a second opinion if validation fails)

The rationale behind splitting the namespace up into zones, and signing each
zone independently, was to i) limit the damage if there is a security breach,
and ii) limit the number of bindings which have to be resigned if there's a
security breach. Having multiple signing authorities (whether it's per-zone,
or for the entire namespace) is really orthagonal to that, multiple signers is
more a "limit the power" kind of thing.

The sole exception is that if you had *more* than two, you could do a
"majority votes" kind of thing to limit the results of a security breach...
but what if you get in a binding that only has one signature? Is it valid, or
the result of a security breach? So I guess the answer is that if a binding is
only valid if it has M valid signatures (where M >> 1, and somewhat less than
the total number of signing authorities), then I suppose you could get goal i)
out of a single large zone with multiple signing authorities - whilst not
giving any one signing authority too much leverage.

I don't really have any axe at all to grind on i) how many zones the system
has, or ii) how many signing authorities we have. Whatever answers people
think will provide the best cost/benefit results are fine with me.

    > while only having 2 things to break when you configure your lookup
    > agent...

I don't expect people to be typing the master keys in! Yes, they would be
distributed out-of-band ("printed in the newspaper", one wag suggested), but
I was assuming they would more be included in software distributions as a
file. I mean, nobody's going to type in a 1024-bit (or longer) key! So
whether it's 2, 256, or 768, would it really matter that much?

	Noel

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 17 Jan 2008 10:23:28 -0800

> Are you buffering or dropping in your current LISP implementation?

Dropping packets until the Map-Request/Map-Reply interchange is  
complete.

Dino

---

From: [email-masked] (Sandy Murphy)
Date: Thu, 17 Jan 2008 15:32:05 -0500 (EST)

>system needs to be more ambitious if it means orders of magnitude  

I lurk here occasionally, but I had to chime in on this one.

TCP MD5 protects the links between routers.  It does nothing at all,
de nada, zero, zip, about protecting what the routers
say.  (What's more, it is cryptographically unsophisticated and
outmoded.)

There's the SIDR wg looking at providing authentication and authorization
for what the routers say in their BGP updates.

There's the work in TCPM wg looking at a better alternative to TCP MD5.

I don't know which failing of TCP MD5 you mean when you say "about
as secure as sending data in envelopes made of clear plastic".  That
sounds like a reference to a need for confidentiality. Neither SIDR
nor TCPM is looking at needs for confidentiality.

--Sandy

---

From: Markus Stenberg <[email-masked]>
Date: Fri, 18 Jan 2008 12:07:06 +0900

> say.  (What's more, it is cryptographically unsophisticated and

Yes.. This is what I was trying to point out, with a broken example.

Anyway, even with the admittedly broken key handling (static manual  
keying), broken protocol (replay attacks and such), and partially  
broken digest algorithm, it seems to be still working well enough. I  
haven't heard about any attacks against the BGP+TCP-MD5 really  
happening out there in the wild.

I'm not sure if this effort should aim for anything insanely complex  
and computationally expensive (global CA hierarchy is typically an  
example of that - there is only one that has been really deployed), as  
that's unlikely to work out in practise, but the downside of any  
piggybacking scheme is that _does_ need to be authenticated in some  
way, as it comes directly from potentially untrustworthy source.  
Attacks using that mechanism (traffic redirection/DoS/blackholing)  
seem both more desirable and easier to implement in practise than  
attacks on BGP (which is unavailable to be attacked for most people, I  
suppose).

Conclusion? I'd prefer to keep piggybacking out of the picture  
altogether, if security framework that it requires makes the solution  
more complex (and CA hierarchy is typically no-no if you want things  
to happen in real world anyway).

Cheers,

-Markus

---

From: "Templin, Fred L" <[email-masked]>
Date: Fri, 18 Jan 2008 10:19:38 -0800

Folks,

Returning to the subject matter that started this
thread, the tunnel MTU question has come up also
on the MANET mailing list - please see the archive
there under subject heading of "SMF-06 comments".

The approach is very similar to the one I am currently
writing up in an internet-draft-to-be called "LISP
Fragmentation and Reassembly", except that the use case
for MANET is multicast encapsulation while the use case
for LISP is unicast.

I will post the LISP fragmentation and reassembly draft
and announce it to this list as soon as I am able - the
text is largely derived from my two earlier RRG postings.

Fred

---

From: David Conrad <[email-masked]>
Date: Fri, 18 Jan 2008 13:05:24 -0800

Noel,

On Jan 17, 2008, at 6:08 AM, Noel Chiappa wrote:
> Well, I'm not so sure. I'm not a crypto math expert, but...

Neither am I, but...

> aspects of all this, someone please enlighten me! :-)

My understanding is that you need to periodically replace keys in  
order to thwart brute force attacks (among other reasons).  RFC 4641  
discusses this in the context of DNSSEC in section 3.3.

> Sorry, didn't follow that - can you expand a bit?

Typically, the lookup agents will need to have the trust anchors  
configured by some means (usually, manually).  If you have multiple  
trust anchors, you'll need to reconfigure those trust anchors in the  
lookup agents every time there is a change.  In RFC 4641, the  
recommended period for key rollover is 12 months.  If you're  
partitioning the namespace into 256 pieces, this implies making (at  
least) 256 changes to the configuration of each lookup agent you are  
responsible for per year where one implication of doing it wrong is to  
completely disable routing of systems dependent on that lookup agent  
for some or all of the partitions of the namespace.

> file.

This puts much trust in the software distribution mechanism (chicken- 
or-egg problems may lie here).  In the case of DNSSEC, this turns out  
to be a non-trivial problem.  This may be because of the  
idiosyncrasies of the DNS (e.g., distributed authority) and may not be  
applicable to what we're discussing here, however one of the lessons  
DNSSEC has taught me (over the 10+ years I've been involved in it,  
either directly or on the periphery): ignoring operational key  
management requirements can render whatever you come up with  
completely useless.  FWIW.

Regards,
-drc

---

From: Scott Brim <[email-masked]>
Date: Tue, 22 Jan 2008 17:17:23 -0500

I'm starting to catch up ... sorry I'm so far behind ... starting with
this sub-thread.

Excerpts from Tony Li on Wed, Jan 09, 2008 03:15:34PM -0800:
>> Can we clarify that conceptually we are talking about prefixes and
>> not individual interface EIDs, as far as the full map goes?
> organizations (you used to work for one of them,  I believe ;-)
> where there are multiple Internet connections that have
> geographically widely dispersed contact points.  Optimal  routing
> implies that there will be different locator preferences for
> different hosts.  Mobility within the organization itself implies
> that creating and maintaining meaningful identifier prefixes is
> going to prove challenging.

There are two questions in here.  

- What do multiply-connected large organizations do?

  Putting mobility aside for the moment (see question 2) ... First,
  they can do something common today, which is to have different
  prefixes reflect different geographic locations.  If some
  governments have their way, this will be required in any case.  If
  they want more fine-grain control, for example due to internal
  movement where they don't want to renumber ... if they are running
  ALT the ETRs themselves reply to Map-Requests and decide what will
  go in Map-Replies (with what ETR priority), so this can be
  controlled by the receiving organization's policy.  If they are not
  running ALT, that can be taken care of piggybacking in the LISP
  header of the data packets.  The good thing about ALT is that this
  fine granularity is not visible above the first 1-2 levels of the
  ALT hierarchy.

- What is the effect of mobility within the organization?

  Let's be clear that in LISP an EID is not a persistent identifier of
  a *device*.  It names a network attachment point or (from the other
  side) an interface.  So "slow mobility" -- without a need for
  session continuity -- will involve assignment of a new EID.  If
  there is a need for session continuity, then the problem is better
  solved at a higher layer.  If it cannot be solved up there, then
  fast mobility mechanisms -- MIPv6 or whatever we settle on -- are
  appropriate.  Solve it in per-connection signaling, not in the
  fundamental routing exchanges.

> In other words, I think that we need host level granularity in the

It can be provided if needed, although I don't think it should be.  In
ALT, single EID prefixes can be advertised to ALT routers which will
then aggregate them, so the effect of long prefixes will damp out
quickly.  

> No, what I saw was a total mess of mechanisms, with no coherency.

I like your idea, but there are complexity tradeoffs.  You can get
some of that dynamic adaptation with hybrid push/pull models, where
the boundary between "push" and "pull" can move depending on load ...
but we had better be sure we can debug problems with it before we
allow that kind of dynamicity.  Map&Encap and 8+8 are very different,
but if we use Dino's idea of how to use IPv6 and map&encap maybe we
could get dynamic boundaries between all of them.  Should be studied
further.

Excerpts from Brian E Carpenter on Fri, Jan 11, 2008 10:50:07AM +1300:
> OK, I was too telegraphic. I don't believe that mobility that
> preserves a global routing prefix is a requirement. [Discussion of
> the value of Mobile IP elided.] I do mean global - there are
> certainly scenarios where mobile prefixes are a requirement, but
> those won't be prefixes that ever need to be in the public Internet,
> so they aren't part of what I thought we were discussing here.

A node *can* roam and preserve its original IP address, but we should
not put that in the underlying routing.  It can be done in connection
signaling a la MIPv6.

Scott

---

From: Tony Li <[email-masked]>
Date: Tue, 22 Jan 2008 14:48:02 -0800

Hi Scott,

>> There are large
>   ....  The good thing about ALT is that this

I thought that ALT carried aggregated EID information.  How does the  
correspondent host get EID-specific information?  Did I misunderstand  
ALT?

>   fundamental routing exchanges.

If you go down this path, I'm having a hard time really reconciling  
the difference between an RLOC and an EID.  It seems like if I move,  
I might change both, so that some location semantics has leaked into  
the EID definition.

> then aggregate them, so the effect of long prefixes will damp out

Which implies that EID-specific information will be lost, which in  
turn costs us functionality.

>> No, what I saw was a total mess of mechanisms, with no coherency.

Man, that came out snarky.  Apologies, it wasn't meant to be.

> could get dynamic boundaries between all of them.  Should be studied

Just in case I've confused anyone, I side with Einstein when it comes  
to complexity.  ;-)

> not put that in the underlying routing.  It can be done in connection

Fair, but unless we're willing to open the transports to actually add  
that to connection signaling, that's going to prove challenging.  So  
far, all of the feedback on host changes (transport layer or  
otherwise) is all negative.

In fact, if we're willing to open the transports, then we really have  
to question why we couldn't take an SCTP-like approach.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 22 Jan 2008 15:17:55 -0800

> correspondent host get EID-specific information?  Did I  
> misunderstand ALT?

Site-based EID-prefixes are injected into the ALT topology. ALT  
routers can further aggregate into the core. A source site sends a  
data packet or Map-Request to an specific EID that follows the route  
on the ALT topology to get to the ETR at the destination site which  
returns a Map-Reply with the a locator-set for the site-based EID- 
prefix.

> I might change both, so that some location semantics has leaked into  

If you move and you don't need session survivability you *can* change  
both. And to make that movement compatible with existing trends and  
deployed sites, you get a DHCP address (you as a host) that will be  
used as an EID. You (as a host) don't have locators per say, but the  
site you are at does (the IP addresses of the ETRs).

If you move and want session survivability, the EID must move with the  
host (and the host stack has to retain the address when the interface  
goes down, this is not common). This is the case where the RLOCs  
change for a single EID (versus the EID-prefix because the home site  
doesn't move, NEMO aside for a moment).

> turn costs us functionality.

The more specific bits of an EID will be lost, but the mapping data is  
not lost because it is returned in the Map-Reply.

> Man, that came out snarky.  Apologies, it wasn't meant to be.

Thanks for the apology.   ;-)

> Just in case I've confused anyone, I side with Einstein when it  
> comes to complexity.  ;-)

So using one mapping system would be better then.

> Fair, but unless we're willing to open the transports to actually  
> add that to connection signaling, that's going to prove  
> challenging.  So far, all of the feedback on host changes (transport  
> layer or otherwise) is all negative.

If the original IP address *stays* with the host, it continues to use  
it. So there are no hot changes.

Dino

---

From: Tony Li <[email-masked]>
Date: Tue, 22 Jan 2008 17:55:13 -0800

>> I thought that ALT carried aggregated EID information.  How does  
>> the correspondent host get EID-specific information?
>
> data packet or Map-Request to an specific EID that follows the  
> route on the ALT topology to get to the ETR at the destination site  
> which returns a Map-Reply with the a locator-set for the site-based  
> EID-prefix.

Again leaving you at prefix granularity.  ;-(

> If you move and you don't need session survivability you *can*  
> change both. And to make that movement compatible with existing  
> trends and deployed sites, you get a DHCP address (you as a host)  
> that will be used as an EID. You (as a host) don't have locators  
> per say, but the site you are at does (the IP addresses of the ETRs).
>
> If you move and want session survivability, the EID must move with  
> the host (and the host stack has to retain the address when the  
> interface goes down, this is not common). This is the case where  
> the RLOCs change for a single EID (versus the EID-prefix because  
> the home site doesn't move, NEMO aside for a moment).

Why do we need both options?

> The more specific bits of an EID will be lost, but the mapping data  
> is not lost because it is returned in the Map-Reply.

I get that, but if you have EID-specific mapping data, doesn't it get  
lost in preference to a EID prefix reply?

> So using one mapping system would be better then.

Not what I meant.  Einstein said ~as simple as possible, but no  
simpler~.  One, integrated mapping system that has multiple modes may  
be the right answer.  Pushes to some nodes, pulls from others, etc....

>> challenging.  So far, all of the feedback on host changes  
>> (transport layer or otherwise) is all negative.
>
> If the original IP address *stays* with the host, it continues to  
> use it. So there are no hot changes.

Then how do you change the connection signaling?

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 27 Jan 2008 02:28:24 -0800

> Again leaving you at prefix granularity.  ;-(

Can be very coarse prefix granularity.

> Why do we need both options?

It is not very clear an end-user needs TCP-connection survivability  
across moves but would require sessions (moving watching, phone calls,  
etc) to have survivability.

> I get that, but if you have EID-specific mapping data, doesn't it  
> get lost in preference to a EID prefix reply?
>
> simpler~.  One, integrated mapping system that has multiple modes  
> may be the right answer.  Pushes to some nodes, pulls from others,  
> etc....

Right, but it's not clear that the way we present them as different  
mapping systems, cannot be integrated into one protocol. So don't rule  
out this option.

> Then how do you change the connection signaling?

I don't understand the question.

Dino

---

From: Tony Li <[email-masked]>
Date: Mon, 28 Jan 2008 10:26:44 -0800

Hi Dino,

>>>> Can be very coarse prefix granularity.

Even worse.  ;-(

>>> If you move and want session survivability, the EID must move  
>>> with the host (and the host stack has to retain the address when  
>>> the interface goes down, this is not common). This is the case  
>>> where the RLOCs change for a single EID (versus the EID-prefix  
>>> because the home site doesn't move, NEMO aside for a moment).
>>
> across moves but would require sessions (moving watching, phone  
> calls, etc) to have survivability.

So I guess I"m not seeing anything that's TCP specific here.  If you  
can provide survivability for one transport, isn't it going to fall  
out for other transports?

>>>> Fair, but unless we're willing to open the transports to  
>>>> actually add that to connection signaling, that's going to prove  

So we're postulating that we accomplish some level of mobility by  
connection level signaling.  This is certainly doable.  However, you  
seem to claim that you can do this connection level signaling without  
involving host changes.  I'm trying to understand how this is  
possible.  Implementing MIPv6 does seem like a host change.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 28 Jan 2008 14:14:32 -0800

>>>>> Can be very coarse prefix granularity.

No not worse. Good when it can be coarse. And when it can't because of  
locator-set differences, then a site's allocation because more specific.

> out for other transports?

If you do it at the session layer, then you don't care what transport  
you use so you don't care if the transport can support it.

> seem to claim that you can do this connection level signaling  
> without involving host changes.  I'm trying to understand how this  
> is possible.  Implementing MIPv6 does seem like a host change.

I think you can do it with application changes and not protocol stack  
changes.

Dino

---

From: Tony Li <[email-masked]>
Date: Mon, 28 Jan 2008 23:02:19 -0800

> No not worse. Good when it can be coarse. And when it can't because  
> of locator-set differences, then a site's allocation because more  
> specific.

I'm getting confused here.  Are you admitting that you could support  
host-specific mappings?

> If you do it at the session layer, then you don't care what  
> transport you use so you don't care if the transport can support it.

Ok, I'll bite.  What session layer is this that doesn't require host  
changes?

>> connection level signaling.  This is certainly doable.  However,  
>> you seem to claim that you can do this connection level signaling  
> I think you can do it with application changes and not protocol  
> stack changes.

Isn't that worse?  Changing every application in the known universe?

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 28 Jan 2008 23:05:18 -0800

> I'm getting confused here.  Are you admitting that you could support  

I mentioned at the last RRG where we can verify a new ITR for a given  
moved EID by creating /32 state in the CN's ETR. We had that working  
in our prototype of doing LISP mobility.

> Isn't that worse?  Changing every application in the known universe?

No, only the ones that might need session survivability. Which I think  
are very few and far between.

Dino

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 30 Jan 2008 16:52:08 +1300

> are very few and far between.

Like any form of media streaming, including telephony?

I don't think we know how to persuade those people to roll out new code
except by breaking things for them. Good luck with that ;-)

   Brian