Subject: Re: [lisp] lisp Digest, Vol 13, Issue 13

From: Charrie Sun <[email-masked]>
Date: Sun, 6 Dec 2009 23:28:41 +0800

Hi Noel,

> From: [email-masked] (Noel Chiappa)
> To: [email-masked]
> Date: Sat, 5 Dec 2009 12:00:39 -0500 (EST)
> Subject: Re: [lisp] ALT and EID blocks (was: lisp Digest, Vol 13, Issue 10)
>    > 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.
>
> How do ALT nodes know which are his related nodes (parents or children) if
no specification is made? What i suggest is that the ALT hierarchy should be
well designed in advance, with careful thinking about the levels and node
degrees to gain a sound tradeoff. At least the system should be constructed
in a from top down fashion...

> 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.
>
> That's why we need to carefully design the hierarchy. Besides,
the requesting overhead of ALT nodes should also be taken in control,
especially for those upper-layer nodes who are prone to be bottlenecks.

> 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
>
>
> Yes, i've read that paper and benefited from that much. While now
i'm thinking that this is the IPv4 scene, an ITR can actually contains all
the pointer information of EID mapping, i.e. we needn't the first level of
ALT nodes since there are only 2^8 nodes in the second level. And these
second-level nodes can be a full mesh. But what if EID is based on IPv6? In
my design in the proposal there can be 5 layers and node degree up to 2^24.
Well this means that a longest map request path would be of 8 hops. Based on
the assumption that average delay between two random nodes be 115ms, this
means a 1s delay around. This is critical for ITRs for an ITR is expected to
(at least in LISP?) buffer the unsolved packets, especially in the
high-speed network. So additional mechanism need to be digged out, as well
as the careful design of the ALT architecture.
Right?

>
> From: Florin Coras <[email-masked]>
> To: Noel Chiappa <[email-masked]>
> Date: Sat, 05 Dec 2009 19:44:04 +0100
> Subject: Re: [lisp] ALT and EID blocks (was: lisp Digest, Vol 13, Issue 10)
> Hello Noel,
>
> Noel Chiappa wrote:
> [snip]
> > 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
> >
> 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
>
>
> Florin,
As ALT nodes are communicated on an overlay and use tunnels, can i discard
the actual delays between two nodes and use a more general value to measure
the reponse delay, that is, the measurement would be solely bounded with the
hops they experience.

Best regards,
Letong

---

From: Florin Coras <[email-masked]>
Date: Sun, 06 Dec 2009 18:10:27 +0100

Hello Letong,

Charrie Sun wrote:
> second-level nodes can be a full mesh. 
The issue with this approach is that you need to keep hundreds of GRE
tunnels and BGP sessions. Not having practical experience with such
large networks I wouldn't know what the upper bound is. Either way,
already the second level routers aggregate thousands of prefixes from
lower level ones and these values might not be sustainable. The trivial
solution to this would be to use more levels which would result in
higher latencies.
> But what if EID is based on IPv6? In
As far as I know packets are dropped at the ITR when there is no mapping
for a certain destination and the host applications are expected cope
with this.
> the reponse delay, that is, the measurement would be solely bounded with the
Not sure I understand this correctly but given the variability of the
delays we got, between some ms to 2.5s, (or if you exclude the top and
bottom 10% values 400ms to 800ms) I'm not sure if that would be wise.
On the other hand, if you are reassured (by feedback on the list) that
the hierarchy would be built from grounds up and the ALT routers at a
certain level in the ALT hierarchy would have a similar geographical
distance (i.e. would be geographically close) to those that aggregate
their announced prefixes I suppose your approximation would work.

Florin

---

From: Robin Whittle <[email-masked]>
Date: Mon, 07 Dec 2009 13:48:57 +1100

Short version:   How can the ALT structure scale to 10^8, 10^9 or
                 10^10 EIDs with minimal delay times and robustness
                 against single points of failure?

                 If it can't, then there's no advantage in using ALT
                 compared to the simpler NERD, which does not delay
                 packets - or APT or Ivip, which delay initial
                 packets by at  most a few tens of milliseconds.

In the thread "Re: [lisp] lisp Digest, Vol 13, Issue 13", Florin

> solution to this would be to use more levels which would result in

Yes - in order to maintain some reasonable limit on the number of GRE
tunnels and therefore the number of BGP neighbours for each ALT
router, there needs to be a limit to how much aggregation takes place
in each level of the ALT structure.

> for a certain destination and the host applications are expected cope

With ALT, the initial packets in a new communication flow (to a
destination EID the ITR has no mapping for) will either be dropped or
delayed.  I understand they are dropped in the current
implementation, since it is not known how long it will be before the
map reply arrives - and by then it may be more disruptive to send a
delayed packet than to drop it.

Therefore, when an application starts sending packets to an IP
address it has not used before, if its ITR has no mapping, the
application will frequently receive no response.  It may retry, or it
may try another IP address, so potentially restarting the process.

In a system such as LISP-NERD, there is no delay since the ITRs have
the full mapping database.

With APT or Ivip, the delay would typically be in the millisecond or
a few tens of millisecond range, since the mapping queries go to
local full database query servers (in the same ISP or end-user
network).  So there is little chance of lost query or response
packets and the response will normally arrive very quickly.  Such
delays are probably small enough to be of no practical significance
to the application or end-user, so the ITR would buffer the packet
and send it milliseconds later, once the mapping reply arrives.

At some level of the ALT structure all the routers are full meshed.

Using an IPv4 example, in the simplest possible ALT structure, and
meshing at the /8 level, there would be 224 routers at this level,
each with 223 GRE tunnels and neighbours at that level.

Assuming an even distribution of EIDs over the 224 /8 prefixes, and
assuming no correlation between EID and the part of the ALT structure
the requesting ITR connects to, then each one of these routers has to
handle most of the map requests for a single /8 of EID space.

For instance, the single ALT router which aggregates 55.0.0.0/8
handles the map requests from all ITRs apart from the small (1/224)
subset which connect to the ALT network somewhere in the 55.0.0.0
inverted tree below this ALT router.

To minimise the number of GRE tunnels and BGP neighbours at the
highest level of the ALT network, we would raise the aggregation
level - such as to /7 or /6.  However, this doubles or quadruples the
traffic handled by each of the now smaller number of top level routers.

It looks highly unscalable to concentrate about 1/224 of the world's
map requests through a single router.

So the solution is to either lower the level of full aggregation:

   /9, means each router has 511 GRE tunnels and BGP neighbours

or to retain the /8 full mesh, and implement some kind of meshiness
below that level.  However, this leads to only a partial set of
connections and to a huge increase in the number of GRE tunnels and
BGP peers for routers at lower levels.

While in practice there would probably be some centralization of the
physical locations of the highest level ALT routers, such as in North
America, to be properly scalable the ALT design needs to cope with
the ALT routers at all levels being pretty much randomly distributed
around the Earth, or at least those parts of the Earth with Internet
infrastructure.

This is because the organisations which run them, each somehow being
responsible for a part of the ALT address space, should be assumed to
have their facilities pretty much randomly distributed around the Net.

So a GRE tunnel between one ALT router and the next - either a mesh
across the same level, or a link from one level to the another -
would physically be carried via multiple Internet routers and data
links.  This would often be a long physical length, involving a dozen
or so routers and one or more trans-oceanic cables.

Just because the ALT network in its simplest form can be depicted by
a neat diagram, doesn't mean that the path-lengths from one ALT
router to the next will be short.  Typically, they will be long,
because typically, the whole purpose of LISP or the other core-edge
separation schemes is to make it easy to use EID address space
anywhere in the Net.  So the LISP-ALT design must assume that ALT
routers, or the locations of the authoritative query servers (ETRs
for non-mobile LISP) are going to be randomly physically distributed.

A simple arrangement for ALT in IPv4 would be to assume that EIDs are
no longer than /24 and that the ALT network is fully meshed at /8.
This leaves 16 bits to span.  If we set a limit of 16 GRE tunnels to
the ALT routers in the next lowest level, and one to the ALT router
in the level above, then we get a network like this:

   L0    224 ALT routers each for a /8

   L1    224 x 16 = 3584 ALT routers, each for a /12.
         One set of 16 under each of the L0 routers.

   L2    3584 x 16 = 57344 ALT routers, each for a /16.
         One set of 16 under each of the L1 routers.

   L3    57344 x 16 = 458752 ALT routers, each for a /20.
         One set of 16 under each of the L2 routers.
         Each such router connects via a tunnel to up to
         16 ETRs, each of which could be anywhere in the
         world and each of which is the authoritative
         query server for a /24 EID.

In reality, not every part of the hierarchy would be populated, since
only a substantial subset of the address space will be used for EIDs.

Also, some EIDs will be shorter than /24, so there will be less EIDs
than depicted above, requiring fewer ALT routers.

However, the ALT network should scale to cope well with hundreds of
millions, to billions, of EIDs.  In IPv4 this means most of them will
be /30, /31 or /32.

An ALT router doesn't need to maintain expensive GRE tunnels and of
course not BGP links to each ETR - and the ALT routers will probably
link to Map Servers which themselves link to multiple ETRs, so this
does somewhat reduce the number of ALT routers needed at the lower
levels of the inverted tree (those with numerically higher L numbers).

But ALT needs to scale to hundreds of millions, and ideally billions
of EIDs.  If ALT can't scale to this, then there's no point to it at
all.  The sole advantage of the ALT (or CONS or TRRP) decentralised,
global, mapping query server system is that no single device needs to
handle the whole mapping database.

I argue that even the largest conceivable mapping database, of 10
billion EIDs each with 100 bytes or so, is perfectly feasible to
transport the database to, and store it within, many single devices.
 This is a terabyte and it fits on a consumer hard drive today.  APT
and Ivip involve hundreds of thousands of local query servers which
can do this.

Even if it is argued that it is impossible or undesirable to have any
single device, much less tens of thousands of them, store the entire
mapping database of 10^7 EIDs, it is still true that APT needs to
scale to some largish number of EIDs, such as 100M to 1B.

If LISP is not required to scale to such numbers of EIDs, then it
would make sense to use NERD, since an individual ITR can easily
store 100M EIDs.  The bandwidth requirements for updating the ITR
would not be a significant problem in the scheme of things by the
time such numbers of EIDs are used.

So let's assume at least 10^8 EIDs, and ideally 10^9 or 10^10 - and
consider the structure of the ALT network in IPv6.

I assume the longest EID would be a /64.  Wherever the top level of
the ALT hierarchy is, such as /8 or /12, this is a lot of bits to
span.   Many parts of the address space will not be EIDs, but the
parts which are will collectively contain vast numbers of EIDs.

Due to the portability which is a requirement of any scalable mapping
solution, we must design for a case where there is little or no
discernible relationship between the EID address and the topological
location of the ETR which is authoritative for this EID's mapping.

So the first level of aggregation - whether it is Map Servers under
ALT routers directly, or ALT routers linking directly to ETRs - will
involve tunnels or some other kind of communication session leading
to ETRs all over the world.

There is unlikely to be much geographic or topological closeness
between ALT routers at different levels, so each GRE tunnels which
querys ascend and descend up and down the hierarchy must be assumed
to be often quite long, and potentially involve one or more long
transoceanic cable links.

With a full scale IPv6 deployment, such as 10^9 EIDs, the simplest
form of ALT hierarchy is going to have many levels - considering
whatever limits there are on how many GRE tunnels and BGP neighbours
each ALT router can have.

Since each of these tunnels is sometimes - often - geographically and
topographically long, it is clear that the total path taken by many
mapping requests is going to be physically very long indeed.

Most requests will ascend to the top level, traversing as many GRE
tunnels and ALT routers as there are in the hierarchy.  A few will
not need to ascend so high before they find an ALT router which
aggregates the destination EID.  Then, the request needs to descend
down the hierarchy with a similar number of GRE tunnels and ALT
routers.  Both up and down, each GRE tunnel involves typically many
Internet routers and long-distance data-links.

Clearly there are problems with scaling the ALT network to the sizes
which are required to give it any advantage over the simpler, faster
and more robust alternatives of NERD, APT or Ivip.

When the ALT network has so many levels, there are going to be
serious problems with the time taken for the request to ascend and
descend the hierarchy, and likewise serious problems with query
packets being dropped.

But the above discussion is for a strictly aggregated ALT network -
the simplest possible arrangement which does the job and respects the
limits of each router in terms of GRE tunnels and BGP neighbours.

How is the above simple tree-like structure going to be elaborated
upon so the system continues to work when one or more ALT routers, or
their GRE tunnels, suffers transient or lasting failure?

The ALT designers have never proposed how they would solve these
problems.

I think ALT or any other global query server approach is a
non-starter because the delays it causes will make it impossible to
have the scheme adopted widely enough on a voluntary basis.  The
initial packet delay problem, due to the global nature of the query
system made much worse by the "long-path" problem of GRE links often
being geographically very long, means that ALT fails to meet
constraint 9 of:

  http://www.firstpr.com.au/ip/ivip/RRG-2009/constraints/

If there were no competing alternative, violating this constraint
might not be such a problem.  However, NERD, APT and Ivip meet all
the constraints.  In particularly, they meet 9 because they do not
significantly delay any packets, including initial packets.

> their announced prefixes I suppose your approximation would work.

It can't be assumed that ALT routers at a certain level would all be
in the same geographical location.  The whole idea of a routing
scaling solution is to make EID space equally usable in any location
in the Net.  This means there are no particular locations where an
ALT router could be close to the ETRs which are authoritative for the
EIDs whose space the router is aggregating.

You could put all the ALT routers for the 55.0.0.0/8 section of EID
space close together, such as in Shanghai, Los Angeles or London.
That would work fine between these routers, but that means they can't
be close to most of the locations where the ETRs are located which
are authoritative for the millions of EIDs in this range.

Nor does it mean that the top router in this branch is going to be
close to the other /8 ALT routers at the top level.

Before anyone thinks they can simulate the ALT network, they need to
decide its structure, for a given number of EIDs, in either IPv4 or
IPv6.  This is all guesswork, as far as I know, since the ALT
designers have never given detailed examples of how a full scale
production ALT network would be structured.

The only advantages of ALT over NERD, APT or Ivip its that it can:

  1 - Theoretically scale to any number of EIDs, since no one device
      is required to store the entire mapping database.

  2 - Enable each EID to change its mapping, and to change its
      authoritative ETR (which is the same thing in LISP), as often
      as required, without requiring this information to be
      propagated very far.  For NERD, APT and Ivip, mapping
      changes need to propagated to every ITR (NERD) or every local
      query server (APT or Ivip).

      With ALT, the ETR changes only need to be propagated to the
      lowest level ALT router, or to the Map Server - whichever is
      the lowest level.

      With ALT, the mapping changes are not propagated anywhere,
      since the mapping is internal state of each ETR, and nothing
      in the ALT network, including the Map Servers (AFAIK) caches
      the mapping.  (However, maybe the changes need to be
      propagated to some ITRs which recently requested it or which
      for some other reason are identified as needing the update.)

So the ALT network needs to scale well to 10^8, 10^9 or 10^10 EIDs,
while minimising delays and remaining robust in the event of link and
router failure.   No-one has ever explained how this can be done.

 - Robin

Further discussion and a diagram of the "long-path problem" is at:

  http://www.firstpr.com.au/ip/ivip/lisp-links/#critiques
  http://www.antd.nist.gov/~ksriram/strong_aggregation.png

---

From: Robin Whittle <[email-masked]>
Date: Mon, 07 Dec 2009 16:48:53 +1100

Further to my last message, there has been some concern that I was
assuming certain things which the WG has not reached consensus on -
such as the goals for LISP-ALT or how competing goals should be
prioritized.  I did not mean to make any such assumptions.

I understand the WG is chartered to develop LISP-ALT as an
experimental protocol.

I understand that LISP-ALT has been proposed as the best solution for
the routing scaling problem and that some people consider it to be a
transitional step towards something better in the longer term -
perhaps something based on hosts doing more work, and the network
less.  However, the scope of the WG is a carefully focused subset of
all the things which might be discussed about LISP.

I understand the scaling issues of ALT, including questions of
robustness, delay and loss of packets, are in scope for this WG.
However, I understand that mobility and the discussion of other
proposals are out of scope.

 - Robin

---

From: Florin Coras <[email-masked]>
Date: Mon, 07 Dec 2009 14:49:18 +0100

Hello Robin,

Thanks for raising these questions. You have my opinions and objections
inline.

Robin Whittle wrote:

> > Short version:   How can the ALT structure scale to 108, 109 or
> >                  1010 EIDs with minimal delay times and robustness
>>> >>> ALT nodes since there are only 28 nodes in the second level. And these
>>> >>> my design in the proposal there can be 5 layers and node degree up to 224.
> > application will frequently receive no response. 
>   
It seems that you are ignoring the ITR cache. If you read Luigi's [1]
you will see that cache misses are quite infrequent. Moreover we
confirmed his results. So in this light I think one could say that more
than 95 times in 100 an application will get a response than not. OK,
the trace was from UCL but if someone provides a trace from an ISP's
border router we will run the experiment again a come up with a number
 :)  for the cache miss.

> >  It may retry, or it
The arrangement at the higher levels of LISP+ALT is and probably will
be, for the time being, debatable. I would argue that only the organic
growth of a possible LISP internetwork will show how the bit masks will
look like. In the meantime we do guesswork.

> > have their facilities pretty much randomly distributed around the Net.
I agree that the organizations will be randomly spread across the
Internet but I don't see your second idea following from the first.
Those organizations (and this is my guesswork) would be responsible for
certain EID-prefixes and those prefixes have certain "geographical
locality". In other words the prefixes are not expected to be
"continentally dispersed".

> > for non-mobile LISP) are going to be randomly physically distributed.
This is a worst case scenario and I think it would be too much to call
it typical.

> > millions, to billions, of EIDs.  In IPv4 this means most of them will
This is to be expected with IPv6. Are we to allocate the remaining 2 and
something billion addresses from the IPv4 pool to mobile devices? 
Notice that we are talking about very different EID pools and hierarchy sizes. For IPv4 the hierarchy is considerably smaller. We can't use IPv6 hierarchy size arguments for IPv4.

> > mapping database of 107 EIDs, it is still true that APT needs to
Are you speaking about EIDs or EID-prefixes here?

> > So let's assume at least 108 EIDs, and ideally 109 or 1010 - and
The ETR announces the EID-prefix (therefore the EID address) so they are
topologically the same. I suppose you wanted to say that: when a company
decides to move from one place to another it should be able to reuse its
PI space. Therefore there is no topological relation between the ETR and
the first LISP+ALT aggregating router? I used ALT router and not
Map-Server because it is not (at least for me) certain where the
Map-Server resides. If it belongs to the same AS as the ETR then you
would argue that there will be no topological relation between the ETR
and the first LISP+ALT router. On the other hand if the MS is part of
the ALT then there would be no relationship between the ETR and the MS.
Agreed. But how often do you expect a company to move from Europe to
North America and decide they still want to use the same EID-prefix?
Just as a side note, if an AS decides to use another upstream provider
the topological relation between the ETR, MS and the first ALT router
says the same. And this is the portability, of PI address space,  SPs
want today but it seems that its implementation is filling today's
routing tables.

> > With a full scale IPv6 deployment, such as 109 EIDs, the simplest
The ALT designers should be better at answering this than me.

> > being geographically very long, means that ALT fails to meet
Again you are ignoring the ITR cache. Indeed there are cases when the
delay can be very long and the responsiveness of the user applications
will have to suffer but that is why the LISP+ALT topology needs to be
carefully designed. "Long-path" problems might be alleviated. At least,
hopefully, the "long-paths" will reside within one continent.

> > are authoritative for the millions of EIDs in this range.
But the ALT tree under 55/8 will be on the same continent therefore the
latencies are expected to be small. When an EID is mobile the latency
from its position to the MapServer would be considerable but again this
is for a mobile user and only for the first packet. When you say that
the ALT routers responsible for the 55/8 can't be close to the ETRs
announcing EID-prefixes in that range do you expect that an ETR
(together with all the network "behind it") will move to a new continent?
As an example for latency within one continent: the *RTT* from Spain and
Romania to lisp.ripe.net (193.0.0.170) is 58ms and 50ms. The computers I
just used are in two technical universities not the border routers of their
ASes. 

> > close to the other /8 ALT routers at the top level.
Are you expecting to see /8 responsible LISP+ALT routers connected on
DSL links or well provisioned in the global hierarchy? Dino has reported
a RTT of 300ms from California to Amsterdam (at RIPE) where hist
Map-Server resides.

> > production ALT network would be structured.
Agreed. There is no agreement about how the ALT topology should look
like but our experiment was meant to test one such possible topology. We
felt it would provide the best results in IPv4 context and we drew part
of that conclusion from the opinions expressed on this mailinglist
(including yours  :)  ). Also it does take into account the current IPv4
deployment and measured latencies in the Internet (see iPlane project).
Again, our topology is *not* the best (and you may improved it in
certain ways but we couldn't model those improvements). But the results
obtained by simulating traffic over it give us an approximation of what
the Internet latencies would be if LISP with IPv4 EIDs and LISP+ALT as
mapping system were to be deployed today.

> > So the ALT network needs to scale well to 108, 109 or 1010 EIDs,
> >   http://www.antd.nist.gov/~ksriram/strong_aggregation.pn
>   
Relative to this last png. As far as I know IANA allocates /8 to the 5
RIRs. Therefore my question: is it possible to have the /8 in North
America the /12 in Europe and the /21 in Asia?
Also, this discussion is relative to the current IPv4 deployment which
some might argue is chaotic but if IPv6 were used for the EID space I
suppose we could do a better job allocating it (maybe I'm just naive).
Furthermore, in this context, because I noticed you raised the question
about portability, (I'm repeating one of my questions) do you think it
is to be expected that an AS would move with its whole EID space to
another continent? How often?

Florin

[1]
http://www.net.t-labs.tu-berlin.de/~luigi/Papers/Conext-2007-CRV-UCL-v2-Clean.pdf

---

From: Sam Hartman <[email-masked]>
Date: Mon, 07 Dec 2009 09:20:13 -0500

>>>>> "Florin" == Florin Coras <[email-masked]> writes:
    >> 
    Florin> It seems that you are ignoring the ITR cache. If you read
    Florin> Luigi's [1] you will see that cache misses are quite
    Florin> infrequent. Moreover we confirmed his results. So in this
    Florin> light I think one could say that more than 95 times in 100
    Florin> an application will get a response than not. OK, the trace
    Florin> was from UCL but if someone provides a trace from an ISP's
    Florin> border router we will run the experiment again a come up
    Florin> with a number :) for the cache miss.

This seems like an important result (and thanks for sending me a
pointer; I joined late enough I didn't see this)

However That's only one of the important traffic patterns.  I think we
also need to examine the hit rate for servers sending responses assuming
I'm running a server at a LISP-enabled site and also examine the
application impact of both the client and server running LISP.

---

From: Florin Coras <[email-masked]>
Date: Mon, 07 Dec 2009 16:15:10 +0100

> application impact of both the client and server running LISP.
Agreed but I don't think the WG has reached consensus regarding
gleaning? At least the issue #8 from the tracker seems still open. Thus
the questions: is gleaning going to be used in combination with a
Map-Request or xTRs are not supposed to use it?
Still there are the corner cases(?) when the server domain egress path
is different from the ingress one relative to client.

Florin

---

From: Sam Hartman <[email-masked]>
Date: Mon, 07 Dec 2009 10:43:13 -0500

My position as an individual is that data plane gleaning is never
acceptable on the internet from a security standpoint.

I think we can make control-plane gleaning (including map reply in map
request) secure enough by having the mapping system validate the reply
record as it transits the mapping system.  Doing so will end up building
a fair bit of intelligence into the mapping system--certainly more than
a simple relay network.

(I'm happy to go into more details about why these are my opinions--was
simply trying to state my personal opinion in terms of what research
assumptions I personally would find most useful.)

Put another way, the less gleaning we get away with while still
maintaining the performance we need, the better security we get.

---

From: Charrie Sun <[email-masked]>
Date: Tue, 8 Dec 2009 08:30:12 +0800

Sorry for not forwarding the letter to all.
---------- Forwarded message ----------
From: Charrie Sun <[email-masked]>
Date: 2009/12/8
Subject: Re: ALT structure, robustness and the long-path problem
To: Robin Whittle <[email-masked]>

Hi Robin, i will answer your question inside the letter:

2009/12/7 Robin Whittle <[email-masked]>

> I always has this in mind, that what's the main difference between these
schemes and the current routing system, as to scalability properties?
Since a whole mapping table would be only equal or larger than the current
routing table, and there may well be flooded updates due to edge link
flapping, just as today. So wouldn't the centralized mapping schemes face
the same problem as the current routing system?

> In my mind dropping packets is always the last thing a router should do.
Also I made some experiments which show that with good cache mechanism in
the ITR the buffer size (where i choose to buffer the unsolved packets) is
affordable.

> Yes, centralized mapping has no or little problems of request delays.

> Florin simulated /3 nodes in the top level, and the result is good. In
my idea i propose /0 (a root) in the top level!

> Yes, that's a problem the word-wide ALT system faces. Especially for
upper-layer nodes. However, each logical nodes should be backed
up with multiple phisical nodes (or mirrors), both for burden sharing and
redundancy. We can draw lessons from DNS where mirrors work happily :) Also,
we may, like DNS, add cache in every level mapping nodes to avoid requesting
the upper-level nodes. My two-staged cache at the ITR made down to zero
request to the root in the mapping system (see Attachment).

> Yes, to minimize full mesh we should let as few (logical) nodes in the top
layer as possible.

> Yes, but with the aid of continously joined redundancy physical nodes (for
a logical ALT node) the delay should become optimistic.

> the ALT routers in the next lowest level,

Why limit such a low number of downward tunnels? As far as i think a mapping
server can well handle up to 2^16 children, as to storage memories and
processing abilities, both. (I put my analysis of the feasibility of our
design in the Attachment, Section 6.4.)

> and one to the ALT router

---

From: Charrie Sun <[email-masked]>
Date: Tue, 8 Dec 2009 09:26:38 +0800

2009/12/7 Florin Coras <[email-masked]>

> is different from the ingress one relative to client.

Yes, i think it is the corner case (you mentioned) as well as security
concerns that we may not use gleaning. When a customer sends a packet to
another it certainly wants the remote ITR to know all its ETRs when the
remote ITR returns packets, and thus to implement traffic engineering.

---

From: Charrie Sun <[email-masked]>
Date: Tue, 8 Dec 2009 09:36:57 +0800

2009/12/7 Sam Hartman <[email-masked]>

> record as it transits the mapping system.

Is it a consensus that a reply should go through the mapping system to the
request ITR? I think it would cause large delay and increase heavy loads on
the mapping system. Do I miss something?

> Doing so will end up building

---

From: Robin Whittle <[email-masked]>
Date: Tue, 08 Dec 2009 16:28:36 +1100

Hi Florin,

> border router we will run the experiment again a come up with a number

Your predictions depends entirely on the traffic patterns the ITR has
been handling.

If there are hundreds of millions of EIDs then the chance that the
ITR has recently received the mapping for each EID is remote.  So the
initial packet delay/drop problem would be quite frequent.

> look like. In the meantime we do guesswork.

Yes - this seems to me like an inadequate approach when designing an
upgrade to the Net, which is supposed to *solve* scaling problems and
also scale to hundreds of millions of EIDs or more.

The test network will never be anything like the size of a full-scale
deployment.  Rather than relying on experience with this, we need to
anticipate all the scaling problems of full-scale 10^9 etc. EID
deployment and solve them.

> "continentally dispersed".

I would like to see some detailed discussion of this from the
LISP-ALT designers.

I agree that the distribution would probably not be completely
random.  My argument is that for the system to scale well, it needs
to scale with arbitrary arrangements of who is responsible for each
prefix and where they run their ALT routers.

If the scalability of the ALT network depends on assumptions about
where the ALT routers will be located, I would like to see explicit
statements of these assumptions and debate about how realistic these
are in a full-scale deployment.

> This is a worst case scenario and I think it would be too much to call

I think that it would be common enough that the design should scale
well even with random distributions.

Again, if scaling depends on some non-random physical placement of
ALT routers, I would like to see clear statements of what the
placement requirements are.

> something billion addresses from the IPv4 pool to mobile devices? 

Probably not, but we can't rule out being stuck with IPv4
indefinitely, and there being very large numbers (a billion or so) of
EID prefixes - where most of them are for one, two or a handful of IP
addresses.  Many of these might be for mobile devices.  I doubt that
there will ever be more than 10^7 non-mobile networks which are
sufficiently motivated to achieve portability or multihoming to get
two physical links to two ISPs.  (Although a second wireless link
could be very inexpensive and easy to install.)

In principle, a core-edge separation scheme could devote a large part
of the available 3.7 billion IPv4 addresses to EID space.

If the ALT network can't cope with this, then how could it cope with
IPv6 with 10^9 or 10^10 EIDs?   There are other techniques, without
ALT's delay and scaling problems, which would scale without problems
if we don't need such numbers of EIDs.

> Notice that we are talking about very different EID pools and
> hierarchy sizes. For IPv4 the hierarchy is considerably smaller. We
> can't use IPv6 hierarchy size arguments for IPv4.

I agree.  Whatever the span of bits between the fully meshed top of
the ALT hierarchy and the longest length of EID prefixes, the ALT
network has to use multiple levels aggregate EID prefixes.  The more
EID prefixes, the more levels, considering each ALT router has some
limit to the number of GRE tunnels and BGP neighbours it can handle.

The lowest level of aggregation may well be Map Servers, which is
good.  Map Servers don't do GRE and BGP to ETRs, and I guess they
don't do it to their upstream ALT routers either.

Still, there is a huge task of aggregation, while trying to minimise
the maximum and typical physical path lengths taken by the map
requests, and while trying to make the whole thing robust against
link and router failure.

> Are you speaking about EIDs or EID-prefixes here?

EID prefixes.

> the first LISP+ALT aggregating router? 

Exactly.

> I used ALT router and not
> and the first LISP+ALT router. 

In general, there will never be any topological relationship between
the ETR which handles a given EID prefix and the lowest level ALT
router which aggregates that prefix.  This is because the whole
purpose of a core-edge separation scheme such as LISP is to make EID
prefixes completely portable between ISPs - any ISP in the world.

If the MS is part of the ISP, then the same applies.  Lets' say I
have an EID prefix of 44.55.66.16/20 and I am using two ISPs in
Melbourne Australia.  Both have MSes and each of my ETRs is either in
each of the ISPs, or is at my site and links to those ISPs.  The ETR
for ISP-A communicates with the MS of ISP-A and likewise for the
other ETR for ISP-B and its MS.

The location of the ISP and MS are not important to the fact that
somewhere in the world, there is one ALT router which is the first
level aggregation point for some prefix, such as 44.55.64.00/12 or
whatever, in to which my EID prefix fits.

>From a LISP-ALT design perspective, wherever that ALT router is, the
system must work well no matter where my one or more ETRs are which
are the authoritative query server for EID prefixes this router is
aggregating.

This is assuming a single ALT router.  The LISP designers are yet to
propose how the ALT network would be structured to cope with failures
- but there needs to be some other ALT router, somewhere physically
and topologically different from this first ALT router, to which my
ETRs (maybe via MSes) can register and so receive map requests.

> On the other hand if the MS is part of

All the time if this is a mobile device - and LISP is now supposed to
support mobility, though mobility is out of scope in this WG.

In terms of using EID prefixes in ISPs all over the world, I
understand this is a goal of LISP and the other core-edge separation
schemes.  So I could get a /24 of EID space and split it up as I
wish, including into256 /32s, and use each such EID prefix in any ISP
anywhere in the world.  I might want to do this to run a bunch of
branch offices or for many other purposes.

If LISP-ALT is not meant to work well with completely scattered
points of connection for EID prefixes, then there needs to be a
specification for whatever restrictions must be followed.

> says the same. 

I understand you mean something like this, in the scenario where the
MS is close to the ALT router for the EID prefix in question:

  If an end-user network (which uses LISP EID space) remains in the
  same physical location, but decides to use another ISP, then
  this involves no change in topological relationships between the
  ETR, MS and lowest level ALT router.

Assuming the second ISP is located topologically similarly to the
first, then the ETR's position in the topology won't change much.

"AS" means end-user network with an Autonomous System number.  As far
as I know, end-user networks get an AS so they can firstly gain some
PI space and secondly so they can advertise it in the DFZ.

While it may be possible for an end-user network with an AS and PI
space to convert that space to EID space under LISP, my understanding
of the goal of all core-edge separation schemes is that end-user
networks can get their own EID space and use it for portability,
multihoming and inbound TE, without advertising it in the DFZ.

Maybe the end-user network gets this space from an RIR, in which case
maybe they need an AS.

However, when the system scales to a billion or more EIDs, belonging
to a similar number of end-user networks (most of them cell-phones)
then administratively these networks clearly won't need to get an AS
number.

> And this is the portability, of PI address space,  SPs

Indeed.

> The ALT designers should be better at answering this than me.

OK.

> hopefully, the "long-paths" will reside within one continent.

The long paths may reside in a single continent, but a great deal of
Internet communication crosses between continents.  It is possible
that if the sending host and the destination ETR are in the one
continent that the path between the ITR and the ETR, up and down the
ALT hierarchy, will be in the one continent.

However the routing scaling solution needs to be highly attractive
even when the sending and receiving hosts are in different
continents.  If even a small fraction of initial packets are delayed
or dropped, this will make it very hard to have the solution widely
enough adopted on a voluntary basis.  ALT is competing with other
solutions which do not have this initial packet drop/delay problem.

I have been raising these problems of long paths and difficulties
structuring the ALT network for robustness while reducing path
lengths since ALT was announced, in November 2007:

  http://www.ietf.org/mail-archive/web/rrg/current/msg00554.html

> latencies are expected to be small. 

There's nothing in the current IDs or in anything I recall the LISP
designers writing about the ALT structure which indicates that all
ALT routers under an IPv4 /8 would be on the one continent.

I agree this would make sense, but who is going to be running these
routers?  The address space is already significantly scattered
between continents.  Within a single /8, the space can be, and often
is, used in any location.

Perhaps it could be mandated as part of the ALT specification that
the ALT network meshes fully at some level XX bits and that the ALT
routers for each such prefix are all on the one "continent" or
whatever.  (But how would this be made robust?  That requires
geographic diversity.)

Then, there are effectively 2^XX clusters of ALT routers, with the
routers at the top of each cluster fully meshed with all the top
routers of the other clusters.   This would significantly reduce
worst-case and typical paths, compared to a random distribution.

The greater the value of XX, the less trouble there is with each top
ALT router being overloaded with map requests - but the more
difficulty there is in meshing them all together.

However, there would still be a global path for the map request to
travel when the sending and receiving hosts (and therefore the ITR
and ETR) are on opposite sides of the Earth.

At present I can send a packet to Iceland from Australia and it goes
straight there - straight as the physical topography allows, subject
to how the DFZ routers have organised their paths.

With LISP ALT, unless my ITR happened to have cached the mapping for
the destination host's EID prefix (which is highly unlikely with
hundreds of millions or EID prefixes) my ITR's map reply traverses
the ALT network and crosses the Pacific, North America and probably
goes to London before heading west again to Iceland.  The map reply
follows the same path back to my ITR.  Then, when my host sends
another such packet (the first one or more was dropped by the ITR)
after the mapping arrives, that packet will go via the ETR to
Iceland.  Then, assuming my host is on EID space, the host in Iceland
has to play the same game with its ITR and my ETR.

So what is currently:

   A ==========================================> B
   A <========================================== B

becomes much more complex, much slower, and much more prone to packet
loss with LISP ALT.

ALT involves both hosts having to resend the initial packet after the
mapping arrives at the ITR, and the mapping lookup stuff at least
triples the total time for the initial exchange to take place.  It
will actually be longer than this, since the sending host shouldn't
fire out initial packets ten times a second so one is sent within
100msec of the ITR getting the mapping.  The sending host has no idea
whether the ITR has the mapping or how long it would take to get it.

So with the mapping stuff as "---->"

 A ==> ITR-A drops it
       ITR-A -----(via potentially long ALT path)---> ETR-B
       ITR-A <----(direct via the Net)--------------- ETR-B
  (variable delay, waiting for A to send another packet)
 A ==> ITR-A========================================> ETR-B ==> B
                                           dropped by ITR-B <==  B
       ETR-A <----(via potentially long ALT path)---- ITR-B
       ETR-A -----(direct via the Net)--------------> ITR-B
  (variable delay, waiting for B to send another packet)
 A <== ETR-A========================================= ITR-B <== B

So there are four extra "cross the Earth" delays - which will be
longer still if the ALT network is not structured to avoid
significant extra paths, plus too variable retry times.

This is for A knowing B's address.  If A has to do a DNS lookup, and
the DNS server for B is on EID space too (as it may well be, since
end-user networks may run their own DNS), then the same process would
occur for the DNS query to B's DNS server.  (However, this may alter
the bottom part of the chart above, if the DNS server used the same
ITR as B, in which case ITR-B would already have mapping for A's EID
by the time it received the B ==> A traffic packet.)

> When an EID is mobile the latency

Sure - the whole idea is to be able to put EID address space in any
ISP in the world, and to split it up as finely as the end-user
network desires.  Mobility and branch offices are the most obvious
examples.

If LISP-ALT isn't supposed to support this, then I think there needs
to be a specification of its limitations.

> just used are in two technical universities not the border routers of their

If ALT delayed initial packets by 50ms, I think that would not be a
problem.

However, it will add the following delays, assuming both hosts are on
EID addresses, which we should assume for wide enough adoption to
solve the routing scaling problem:

  1 - As per the above diagram, at least twice the physical delay
      due to the ALT traversal of the request packet and the Internet
      traversal of the reply.

  2 - The variable delay time between the ITR getting the mapping and
      the host sending another packet.  (Otherwise the ITR has to
      buffer packets and send one or more whenever the mapping
      arrives - and by then, the older packets may be more trouble
      than they are worth.)

  3 - Sometimes, delays due to loss of request or reply packets, with
      the sending host and/or the ITR having to time out so a second
      map request packet is sent.

> a RTT of 300ms from California to Amsterdam (at RIPE) where hist

I assume ALT routers would be on fibre connections in data centres.

Melbourne to (I assume) the UK (www.direct.gov.uk) is about 360ms or
more RTT, not counting DSL at this end, via Los Angeles, the
Netherlands and Germany.

> (including yours  :)  ). 

OK - thanks!

> Also it does take into account the current IPv4

OK.

> America the /12 in Europe and the /21 in Asia?

As far as I know, just because an RIR gives some space to an
organisation does not mean the organisation needs to use that space
in any particular region.

I think that if a routing scaling solution makes assumptions about
where its devices need to be with respect to each other, to achieve
acceptable scaling and performance, than this needs to be fully
specified.

> suppose we could do a better job allocating it (maybe I'm just naive).

I think it would make sense to have certain prefixes of IPv6 space
just for EID space.  However, this would be for ease of
administration and debugging - it would probably not be best to have
a scheme which relied on such an assignment unless there were
compelling reasons to do so.

> another continent? How often?

I think a good core-edge separation scheme should support EIDs being
used anywhere - and most end-user networks won't have an ASN.  For
mobility, it should support the mapping changing from one or more
ETRs which might be anywhere, to one or more ETRs which might be
anywhere else.  I think the ETRs should be fixed devices, near the
MNs - the MNs should not in general be their own ETRs.  I think the
system would support this changed mapping in a few seconds, including
so that all ITRs currently sending packets to the previous ETR are
notified within a few seconds.  This is what I try to do with Ivip.

 - Robin

---

From: Robin Whittle <[email-masked]>
Date: Tue, 08 Dec 2009 16:35:06 +1100

Hi Sam,

> acceptable on the internet from a security standpoint.

I agree.

It would offer an opportunity to alter the behaviour of the control
plane just by sending spoofed packets, unless there were elaborate
protections against this.  This could lead to a denial of service or
perhaps (I don't have a specific example) to the altered behaviour
divulging information about real traffic to the attacker.  No doubt
there are other arguments too.

I think it would be best if a core-edge separation scheme achieves
good performance directly - without fussing around trying to guess or
prepare for what might happen soon by looking at user traffic.

  - Robin

---

From: Sam Hartman <[email-masked]>
Date: Tue, 08 Dec 2009 06:17:39 -0500

>>>>> "Charrie" == Charrie Sun <[email-masked]> writes:

    Charrie> 2009/12/7 Sam Hartman <[email-masked]>

    Charrie>     My position as an individual is that data plane
    Charrie> gleaning is never acceptable on the internet from a
    Charrie> security standpoint.

    Charrie>     I think we can make control-plane gleaning (including
    Charrie> map reply in map request) secure enough by having the
    Charrie> mapping system validate the reply record as it transits the
    Charrie> mapping system.

    Charrie> Is it a consensus that a reply should go through the
    Charrie> mapping system to the request ITR? I think it would cause
    Charrie> large delay and increase heavy loads on the mapping
    Charrie> system. Do I miss something?

Yes.  I'm talking about the map reply record in a map request, *not* the
map reply record in a map reply.  That often but not always travels the
mapping system.

My personal opinion is that you can only use that record to establish a
new reverse mapping entry when it does travel the mapping system and
only if the mapping system is changed to modify it.

---

From: Sam Hartman <[email-masked]>
Date: Tue, 08 Dec 2009 07:06:04 -0500

>>>>> "Robin" == Robin Whittle <[email-masked]> writes:

    Robin> Hi Sam,

    >> acceptable on the internet from a security standpoint.

    Robin> I agree.

    Robin> It would offer an opportunity to alter the behaviour of the
    Robin> control plane just by sending spoofed packets, unless there
    Robin> were elaborate protections against this.  This could lead to
    Robin> a denial of service or perhaps (I don't have a specific
    Robin> example) to the altered behaviour divulging information about
    Robin> real traffic to the attacker.  No doubt there are other
    Robin> arguments too.

I'll give you an example where it's where than DOS.  I know you contact
gmail regularly, but have been away long enough your map cache entries
timed out.  I send you packets claiming to be from gmail to set up
gleaned entries and establish the map cache.  You come back and send
packets to gmail; I forward them along, but get to see the contents,
including your session cookies, etc.

Making this work in case of verifying map requests is harder, but there
are definitely attacks that depend on getting only one packet back from
an attacker.

However, I think there's a fairly strong agreement that data plane
gleaning is not OK for capital-i Internet.  My preference would be to
take it out of the spec entirely and focus the spec on Internet
deployment.  People in closed enviorments can have whatever extensions
they like without us having to spend cycles doing security analysis on
things we know are inappropriate for the Internet.
That position is not shared by everyone:-)

---

From: Charrie Sun <[email-masked]>
Date: Tue, 8 Dec 2009 21:22:33 +0800

2009/12/8 Sam Hartman <[email-masked]>

> are definitely attacks that depend on getting only one packet back from

Yes, that's right.

> That position is not shared by everyone:-)

I agree that detailed work or possible improvements should be left to local
area and they should decide actions based on pratical situations. What we
should do is an architectual work: )