Subject: [lisp] Comments on draft-fuller-lisp-alt-04

From: Olivier Bonaventure <[email-masked]>
Date: Fri, 06 Feb 2009 20:11:17 +0100

Hello,

I did a detailed review of draft-fuller-list-alt-04 and have several
comments on the document.

1. I think that it would be useful to add in the document an example
deployment scenario with a few xTR and a few ALT-routers. This would
allow the reader to better understand how the ALT topology operates.

2. The types of messages that are transmitted on the ALT-topology are
unclear. From my reading of the text, it seems that the ALT-topology
(i.e. the tunnels between ALT routers) is only used to forward two types
of messages :
- Data Probes
- Map Requests

However, at several places in the paper, e.g. in section 5, you also
include Map Replies in the types of messages that travel through the ALT
topology. At other places you indicate more clearly that Map replies are
sent on the normal topology. I think that you should be more specific on
the types of packets that are accepted on the ALT topology. ALT routers
might apply filters on their GRE tunnels to only accept such Data Probes
and Map Requests packets.

3. Map Requests and Data Probes that are sent on the ALT topology should
be rate limited. This is mentionned in draft-lisp-11, but I think that
it would be worthwhile to mention this again here.

4. Section 5.2 on EID assignment - Hierarchy and topology
This is a key section of the document that needs to be expanded and
detailed.

A first approach would be to define a tree-shaped ALT network, with the
RIR reponsible for each aggregated EID block at the root. These RIRs
should have ALT routers and be interconnected by a full mesh of ALT-BGP
sessions.

A more detailed example would be useful in this section. You might
consider RIR1 which is responsible for the allocation of 1.0.0.0/8 and
RIR2 which is responsible for the allocation of 2.0.0.0/8

The first two nodes of the ALT topology would then be

RIR1 ------ RIR2

If RIR1 allocates 1.0.0.0/16 to ISP1 and 1.1.0.0/16 to ISP2/. ISP1 could
suballocate 1.0.10.0/24 to Cust1. Then the topology would become

RIR1 ----- RIR12
| |
| +---- ISP2
|
+--- ISP1
      |
      +--- cust1

The advantage of this kind of topology is that it, in theory allows
aggregation of the prefixes that are advertised. However, it suffers
from the following drawbacks :

4a : BGP assumes that an AS identifier is allocated to each AS and the
current BGP aggregation algorithm preserves the ASes by building an
AS_SET when it aggregates several prefixes. Assuming that the
aggregation works perfectly at the prefix level, it still creates large
BGP messages. For an ALT deployment, we will probably consider 32 bits
ASes. Given the maximum size of 4096 bytes for the BGP message, we will
not be able to aggregate more than 1000 different prefixes in a single
BGP message. This is an improvement compared to today's BGP table, but
limits the scalability of the approach.

4b : This tree-shaped topology does not include any redundancy.
Redundancy is important to deal with link and node failures. There are
two possible ways to provide redundancy :
- duplicate the ALT routers on each branch of the tree
- add redundant connectivity between the ALT routers

Duplicating the ALT routers is clearly desireable and should be part of
the ongoing LISP experiment. The two ALT routers that correspond to a
branch of the tree could be connected by an iBGP session.

Adding redundant connections between ALT routers is also an interesting
solution, but this could completely break aggregation is if it used
incorrectly. I will come back to this in another email that discusses
the types of policies that could be applied on ALT BGP sessions.

5. What should an ALT router do when it receives a packet whose
destination EID is unreachable (either because of the failure of an ALT
session or because the corresponding EID block has not been allocated) ?
 Should it drop the packet or send back an ICMP destination unreachable
over the normal topology towards the source RLOC ?

6. Section 7 : BGP configuration and protocol configuration

The question of allocating AS numbers to the ALT routers is important
and should be discussed in more details. I agree that a new Sub-Address
Family Identifier should be defined for LISP+ALT to avoid confusion
between EID prefixes advertised in the ALT topology and normal prefixes.
When a RIR allocates EID blocks to registries, it should also allocate
32 bits AS numbers that could be allocated by the registry to its
customers.

Olivier

-- 
http://inl.info.ucl.ac.be , UCLouvain, Belgium

---

From: David Meyer <[email-masked]>
Date: Fri, 6 Feb 2009 13:15:47 -0800

Olivier,

> comments on the document.

	Thanks, much appreciated.

> allow the reader to better understand how the ALT topology operates.

	Good suggestion. We'll work on that.

> and Map Requests packets.

	Again, thanks for spotting that. We'll fix.

> it would be worthwhile to mention this again here.

	Again, good suggestion.

> should have ALT routers and be interconnected by a full mesh of ALT-BGP

	While I agree, that's actually more of an operational
	issue, which is why its not prescibed here. And while I
	agree that a full mesh on eBGP sessions makes sense, its
	not the only possiblity.

> limits the scalability of the approach.

	There are other ways of doing this, such as are common in
	the ISP world, i.e., nailing up the aggregate with a
	route to null0. I'm not suggesting that one would want to
	do this, but again, this is an operational issue.
> - add redundant connectivity between the ALT routers

	Any level of the hierarchy can be an iBGP mesh, and you
	can peer with one or more of the routers in the level
	above, just like today in the Internet.

> branch of the tree could be connected by an iBGP session.

	We have that in two instances already.

> the types of policies that could be applied on ALT BGP sessions.

	Great, look forward to it.

> over the normal topology towards the source RLOC ?

	Again, lots of thoughts on this one. One possibility
	would for the ALT router to send some kind of negative
	indication back to the source of the map-request.

> and should be discussed in more details.

	Can you explain what you mean a bit more? 

> I agree that a new Sub-Address

	Sure.

> 32 bits AS numbers that could be allocated by the registry to its

	Possibly, but that's registry business, and not in the IETF's
	purview.

	Dave

---

From: Scott Brim <[email-masked]>
Date: Fri, 6 Feb 2009 16:32:38 -0500

My opinions ...

Excerpts from Olivier Bonaventure on Fri, Feb 06, 2009 08:11:17PM +0100:
> aggregation of the prefixes that are advertised. 

Hierarchy of prefix _allocation_ is administrative and has nothing to
do with ALT hierarchy.  How RIRs allocate prefixes, via ISPs or in PI
prefixes directly to sites, is independent of how the ALT routers are
organized.  Whether the ALT, as a whole, effectively aggregates
prefixes (in BGP) is independent of how those prefixes are initially
handed out.

> 4a : BGP assumes that an AS identifier is allocated to each AS and
> the current BGP aggregation algorithm preserves the ASes by building
> an AS_SET when it aggregates several prefixes. Assuming that the
> aggregation works perfectly at the prefix level, it still creates
> large BGP messages. For an ALT deployment, we will probably consider
> 32 bits ASes. Given the maximum size of 4096 bytes for the BGP
> message, we will not be able to aggregate more than 1000 different
> prefixes in a single BGP message. This is an improvement compared to
> today's BGP table, but limits the scalability of the approach.

An ALT aggregator shouldn't have to put more than 1000 prefixes in a
single BGP _message_.  Within the ALT a message heading up the
hierarchy will have just one prefix, and a message heading down the
hierarchy will contain a default route plus perhaps a few more.  An
ALT router may connect to many peers, but the messages exchanged
between them will be small.  There is a tiny chance that a particular
xTR might need to advertise a large number of subprefixes, all in the
same shorter prefix, to a particular ALT router but I have trouble
imagining that happening.  

> Redundancy is important to deal with link and node failures. There
> are two possible ways to provide redundancy :

Yes.  

> Duplicating the ALT routers is clearly desireable and should be part
> of the ongoing LISP experiment. The two ALT routers that correspond
> to a branch of the tree could be connected by an iBGP session.

Lateral connections aren't necessary, but I can see how they might be
useful.  They would allow a site to only connect to certain ALT
aggregators.  However, depending on lateral connections may also
introduce some complexity I would be concerned about.  But they're
possible, and can be deployed or not.

> over the normal topology towards the source RLOC ?

Send an ICMP back to whom?  The ALT is (should be) multiply connected.
Sending an ICMP back to the original requestor doesn't do much good
because the original requestor doesn't know if there is an alternative
path through the ALT (so it doesn't know what to do), and even if it
did it wouldn't be able to persuade the ALT to use a different path.
My personal opinion: drop the packet, but the ALT should be sure that
repeated Map-Requests take (randomly) different paths through
different aggregators.  That way even though routes are aggregated, if
there is a viable path to the xTR it will be taken.

Scott

---

From: Olivier Bonaventure <[email-masked]>
Date: Fri, 06 Feb 2009 23:11:42 +0100

Scott,
> Hierarchy of prefix _allocation_ is administrative 

I agree

> and has nothing to

The topology of the ALT overlay will influence how well the EID prefixes
are aggregated or not. If we want to have an ALT system that scales, it
should be designed to ease aggregation. An ALT hierarchy could be a way
to ease aggregation.

> single BGP _message_. 

Why not ? An ISP can have much more than 1000 SMEs as cutomers and each
of these SMEs can be allocated a single EID prefix.

> Within the ALT a message heading up the
> hierarchy will have just one prefix, 

The message heading up will contain one prefix, but many ASes in its AS_SET.

> and a message heading down the

My comment was more on the AS numbers inside the AS_SET than the
prefixes themselves.

> useful.  

I meant that the two ALT routers that are responsible for a given prefix
in the same site are connected by iBGP sessions.

> They would allow a site to only connect to certain ALT

We need to be careful with the ALT topology that we create and the
policies that are used on the BGP sessions if we want to ensure that BGP
will converge. We know that the classical customer-provider and shared
cost peerings combined with restrictions on the topology ensure that BGP
will converge. It would be useful to develop similar rules for ALT as well.

> there is a viable path to the xTR it will be taken.

This implies that ALT routers need to be able to load balance packets
over multiple BGP paths and that retransmitted Map-Requests should be
send with different UDP ports to hope that the ECM hash will cause them
to follow a different path.

Olivier

---

From: Scott Brim <[email-masked]>
Date: Fri, 6 Feb 2009 23:16:07 -0500

> should be designed to ease aggregation. An ALT hierarchy could be a way

Agreed, but are you connecting your RIR _allocation_ scheme (see
above) with the ALT _aggregation_ scheme?  

> of these SMEs can be allocated a single EID prefix.

Assume xTRs are at the border of the ISP.  Each of those SME customers
has an EID prefix.  The xTRs do have to announce thousands of
prefixes, but not all to the same ALT router.  For each customer
prefix, an xTR would connect to the appropriate ALT aggregator for
that prefix.  At one extreme, each customer prefix would go to a
different ALT aggregator.  In that case (as was said), the xTR would
have many BGP connections but the messages on each would be small.  At
the other extreme, all of those prefixes would go to the same
aggregator.  If they could not be aggregated, that would be a very
large BGP update, but I have trouble believing this situation would
arise in real operations.  If it did I can think of at least one
workaround.

> The message heading up will contain one prefix, but many ASes in its AS_SET.

Since ALT BGP is completely separate from base BGP, the customer AS
number in base BGP doesn't show up in ALT BGP.  ALT BGP starts at the
xTR, so there would only be one ALT AS number for this whole
collection.  Unless I'm confused.

> >> Duplicating the ALT routers is clearly desireable and should be
> >> part of the ongoing LISP experiment. The two ALT routers that
> >> correspond to a branch of the tree could be connected by an iBGP
> >> session.
> > 
> > Lateral connections aren't necessary, but I can see how they might
> > be useful.  
> 
> I meant that the two ALT routers that are responsible for a given
> prefix in the same site are connected by iBGP sessions.

I don't quite understand.  For redundancy there can be multiple ALT
routers at any level in the ALT hierarchy responsible for the same
prefix.  They don't have to be in the same (base) site.

> >> destination EID is unreachable (either because of the failure of
> >> an ALT session or because the corresponding EID block has not
> >> been allocated) ?  Should it drop the packet or send back an ICMP
> >> destination unreachable over the normal topology towards the
> >> source RLOC ?
> > 
> > Send an ICMP back to whom?  The ALT is (should be) multiply
> > connected.  Sending an ICMP back to the original requestor doesn't
> > do much good because the original requestor doesn't know if there
> > is an alternative path through the ALT (so it doesn't know what to
> > do), and even if it did it wouldn't be able to persuade the ALT to
> > use a different path.  My personal opinion: drop the packet, but
> > the ALT should be sure that repeated Map-Requests take (randomly)
> > different paths through different aggregators.  That way even
> > though routes are aggregated, if there is a viable path to the xTR
> > it will be taken.
> 
> This implies that ALT routers need to be able to load balance
> packets over multiple BGP paths and that retransmitted Map-Requests
> should be send with different UDP ports to hope that the ECM hash
> will cause them to follow a different path.

I think so.

Scott

---

From: Vince Fuller <[email-masked]>
Date: Tue, 17 Feb 2009 17:20:17 -0800

> allow the reader to better understand how the ALT topology operates.

This is a good suggestion but I question whether I could do a good job of
describing such an example using text and ASCII art. I will consult with my
co-authors to see what they think.

> (i.e. the tunnels between ALT routers) is only used to forward two types

You are correct. The references to routing Map-Replies over the ALT were
relics of earlier thinking. The -05 draft will eliminate all such references
with the caveat that there may be future experiments involving routing of
Map-Replies over the ALT.

> it would be worthwhile to mention this again here.

This is mentioned briefly in the security section under "Scaling of LISP+ALT
router Resources". I will add additional text to strengthen this.

Note also that the -05 draft will discourage the use of Data Probes as there
are a number of open issues that make prove them infeasible.

> RIR2 which is responsible for the allocation of 2.0.0.0/8

Another good suggestion. Again, I will discuss with my co-authors whether
we should add more example configuraation scenarios to the document.

> over the normal topology towards the source RLOC ?

There are actually multiple cases here.

If an ALT router receives a Map-Request or Data Probe that matches an EID
Prefix that it knows does not exist (e.g. if it is the aggregator for
10.1.0.0/16, the prefix 10.1.254.0/24 is not assigned, and it receives
a Map-Request or Data Probe destined to 10.1.254.1), it returns a Negative
Map-Reply for the shortest covering prefix that is not a LISP EID. A
Negative Map-Reply is a Map-Reply with zero RLOCs. In this example, the
EID prefix in the Map-Reply could be anything from 10.1.254.1/32 to
10.1.0.0/16 and would depend on what, if any, assignments had been made from
10.1.0.0/16.

The case where an EID prefix does exist in the LISP database but has no
reachable RLOCs is, in some sense, more interesting. Dino - what do is the
correct behavior for an aggregating ALT router in this case?

	--Vince

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 17 Feb 2009 17:14:41 -0800

> correct behavior for an aggregating ALT router in this case?

No reachable RLOCs and no RLOCs in the map-cache entry are two  
different things. For the former, you drop the packet, for the later  
you don't encapsulate it because you have concluded that the site is  
not LISP capable so you forward packet natively (unencapsulated).

Dino

---

From: Vince Fuller <[email-masked]>
Date: Tue, 17 Feb 2009 17:36:14 -0800

On Tue, Feb 17, 2009 at 05:14:41PM -0800, Dino Farinacci wrote:
> No reachable RLOCs and no RLOCs in the map-cache entry are two different 
> things. For the former, you drop the packet, for the later you don't 
> encapsulate it because you have concluded that the site is not LISP 
> capable so you forward packet natively (unencapsulated).

That's what an ITR does if it is asked to forward a packet when an EID
prefix is shown as unreachable in it's map cache: if something (a map server
or ALT router) returned a negative Map-Reply indicating that a covering
prefix is not a LISP destination, then it fowards natively. If none of
the RLOCs are reachable, then the destination is unreachable and the ITR
drops the packet.

But what does an ALT router do if it receives a Map-Request for an EID-prefix
that is unreachable? If the ALT router knows a covering EID-prefix does not
exist in the ALT database, then it returns the negative Map-Reply. But what
if it knows that the EID-prefix does exist (i.e. it is configured to accept
the EID-prefix via BGP from one of its "downstream" ETRs) but it has no
mapping because either the BGP sessions to all downstream ETRs are down or
none of the downstream ETRs are actively advertising the EID-prefix?

Should it signal anything to the querying ITR that the ETRs are not reachable,
through ICMP or otherwise? If it simply drops the Map-Request, what will the
ITR do when it gets no response at all after some timeout? Conclude that the
destination is unreachable and drop any traffic to it? Conclude that the
ALT is broken and that it should try to forward the traffic natively?

	--Vince

---

From: Vince Fuller <[email-masked]>
Date: Wed, 18 Feb 2009 11:18:16 -0800

> 10.1.0.0/16 and would depend on what, if any, assignments had been made from

In a separate discussion, Dino pointed-out that an ALT router may be running
vanilla BGP and GRE with no knowledge at all of LISP. This may, in fact, be
the common case. If so, then the ALT router will not know anything about the
Map-Request - it will only know that the destination IP address (the EID) is
unreachable and will simply drop the packet. Not clear whether it should even
return an ICMP unreachable.

I'm going to have additional discussions with my co-authors to determine
what, if any, special processing an ALT router, either one that is
configured to run LISP or one that isn't, should do in this case.

Thanks for pointing it out.

	--Vince

---

From: Scott Brim <[email-masked]>
Date: Wed, 18 Feb 2009 15:14:15 -0500

Excerpts from Vince Fuller on Wed, Feb 18, 2009 11:18:16AM -0800:
> In a separate discussion, Dino pointed-out that an ALT router may be
> running vanilla BGP and GRE with no knowledge at all of LISP. This
> may, in fact, be the common case. If so, then the ALT router will
> not know anything about the Map-Request - it will only know that the
> destination IP address (the EID) is unreachable and will simply drop
> the packet. Not clear whether it should even return an ICMP
> unreachable.

How would you make the distinction between a prefix that is
operational but not reachable, and one that just isn't operational?
Are you going to configure all intermediate ALT routers with all of
the allocated prefixes?  How is it going to know which ones are not
just allocated but operational?  Not only that, but suppose a
high-in-the-hierarchy ALT router loses all routes to a next-longer
prefix, even though that next-longer prefix is an aggregate?  How is
it going to know if all of that prefix is supposed to be operational?
This is a lot of configuration.  I think you're better off not trying
to be too smart here, and if there truly isn't a route on the ALT,
just drop the Map-Request