Subject: Re: [lisp] ALT and EID blocks (was: lisp Digest, Vol 13, Issue 10)

From: [email-masked] (Noel Chiappa)
Date: Sat, 5 Dec 2009 12:00:39 -0500 (EST)

> From: Charrie Sun <[email-masked]>

    > Yes, that's exactly what i was asking.

Ah, good.

    > Apologize for the mistaken words of "each node contains full mapping
    > table"

That is not a big problem, so do not worry, but for the future, it is
important to be very careful to say the exact thing you mean, because
otherwise confusion can result!

    > what i mean is that each ALT node contains routes to ETRs of the
    > whole EID namespace. Wouldn't that be huge?

Not necessarily. Remember the the ALT is a _virtual_ topology (i.e.
connectivity graph), arranged according to the organization of the
namespace (the EIDs). In other words, an ALT node does not (or, at least,
_should_ not) connect to other ALT nodes that are _closest_ (in terms of
distance in the network), but rather to ALT nodes with which it has
a hierarchical relationship in the namespace.

To make this more plain, let me give an example. An ALT node which is
advertizing 1.2.3.* should _not_ connect to an ALT node which is
advertizing 7.8.*, even if that node is right next to it in the physical
network. Rather, it should connect to the ALT node which is advertizing
1.2.*, even if that node is on the far side of the physical network.

That way, we can maximize the amount of aggregation (i.e. replacing a
number of ALT routing table entries, with a single entry which covers all
of the other entries), and keep the table size in any one ALT node as
small as possible.

Of course, in practise, there might be reasons why we don't always do this,
but if we can do it _most_ of the time, it will really help with keeping
the table size down.

    > My idea is to clearly define the structure of the ALT system, as to
    > the layer number and node degree, so each ALT node need only to know
    > a few nodes (ancestors and children) and communicate with them.

I have not yet had a chance to study your document in detail, but let me
make a few comments based on what you say here. I think perhaps your idea
is fairly close to what I am thinking of (above).

The one place I might differ is in wanting to reduce the degree of ALT
nodes to the smallest possible number; the problem with doing that is that
it will increase the path length. Even if there are a small number of
levels, if all requests have to take a stricly hierarchical path through
the ALT mesh (since we are using BGP, the inter-node connections are not
restricted to a pure tree, we can add extra links so it is not a pure
tree), it will produce longer paths than a mesh would. Of course, that
means some nodes will have to have a higher degree of connectivity, but
that is the inevitable price you pay for having shorter path lengths.

Florin Coras and his colleagues have done a very good simulation on this;
they had a presentation at the previous IETF which you can find here:

  www.ietf.org/proceedings/75/slides/lisp-4.pdf

which shows how a strict three-layer ALT hierarchy produces Round Trip
Times through the ALT which are more than twice the RTT to the ETR via a
direct path.

	Noel

---

From: Florin Coras <[email-masked]>
Date: Sat, 05 Dec 2009 19:44:04 +0100

Hello Noel,

Noel Chiappa wrote:
[snip]
> Times through the ALT which are more than twice the RTT to the ETR via a
In fact you can see from the attached CDF (lookup.pdf) that for 50% of
the cases (the upper part) the ALT delay is lower than 2xRTT. For a
small number of cases (lower than 3%, check lookup_UCL.pdf) the ALT
performs better than the one way delay (case of overlay faster than the
underlying routing or unrealistic latencies from iPlane :) ).

Florin