Subject: [RRG] ALT's strong aggregation often leads to *very* long paths

From: Robin Whittle <[email-masked]>
Date: Tue, 29 Jan 2008 11:33:37 +1100

Even assuming a global query server (and initial packet delivery)
network was desirable, which I think it is not, ALT suffers from the
problem that many paths from ITR to ETR will be extremely long -
longer than half-way round the Earth.

The paths will often be far longer than via the most direct path via
BGP routers.  So a global ALT network would be very costly, slow and
unreliable for delivering initial traffic packets and map queries.
Likewise if it is used to return the mapping response. (It seems
much smarter to send the response directly to the ITR over the
Internet - which is referred to in the ID as the "underlying
topology".  This is an option mentioned in draft-fuller-lisp-alt-01.)

ALT mandates that the hierarchy of ALT routers be highly aggregated:

   LISP-ALT routers are deployed in a hierarchy which matches the
   EID prefix allocation hierarchy.  LISP-ALT routers at each level
   in the this hierarchy are responsible for aggregating all EID
   prefixes learned from LISP-ALT routers logically "below" them and
   advertising summary prefixes to the LISP-ALT routers logically
   "above" them.

   ... LISP-ALT uses existing BGP mechanisms to aggressively
   aggregate this information.

This is presumably impossible at the edge of the network, since the
location of ETRs for a given EIDs are scattered around the place
with little or no correlation with geography.  Assuming that it is
desired to have short paths between the ETR and the lowest level of
ALT router, that lowest level of the ALT hierarchy will not be doing
much aggregation.

A very high degree of address aggregation is a core principle of ALT.

So the higher levels of the hierarchy will be highly aggregated.
Since there is little correlation between geography and IP address,
and since these ALT routers will be physically located according to
the operators who are (however determined) responsible for some
subset of the address space, the problem arises:

By mandating the structure of the ALT network be strongly driven by
address aggregation, this means the connections between one router
and the next in the hierarchy will have little or no relation to
geography.  Therefore, the average length of inter-router distance
will be far longer than for ordinary BGP routers, where the network
structure is based primarily on linking to geographic neighbours,
and not at all on address aggregation.

I imagine the following scenario would be common:

An ITR in Melbourne Australia needs to send an encapsulated traffic
packet or map request to an ETR in the Netherlands.  The IP
addresses of the ITR (150.101.162.123) and ETR (83.149.65.1) have no
correlation whatsoever.  This is typically the case for Internet
communications, except between some geographically neighbouring
hosts which happen to be on the same ISP or on ISPs which got
similar address ranges from the one RIR.

The sequence of LISP ITRs through which the packet travels is
something like this.  I am assuming each level of hierarchy
aggregates 3 bits, meaning each router has about 8 below it.  For
simplicity I am assuming the ETR advertises a /24 EID.  The problem
would be worse, due to more layers in the hierarchy, for longer EIDs
(which I think are desirable and often necessary) and of course for
IPv6.

Hierarchy  24 MSB Address                    Location
Level      bits

ITR      1001 0110  0110 0101  1010 0010     Melbourne

1        1001 0110  0110 0101  1010 0***     Melbourne

2        1001 0110  0110 0101  10** ****     Melbourne

3        1001 0110  0110 010*  **** ****     Sydney

4        1001 0110  0110 ****  **** ****     Sydney

5        1001 0110  0*** ****  **** ****     Somewhere-1

6        1001 01**  **** ****  **** ****     Somewhere-2

7        100* ****  **** ****  **** ****     Somewhere-3

7        010* ****  **** ****  **** ****     Somewhere-4

6        0101 00**  **** ****  **** ****     Somewhere-5

5        0101 0011  1*** ****  **** ****     Somewhere-6

4        0101 0011  1001 ****  **** ****     Somewhere-7

3        0101 0011  1001 010*  **** ****     Amsterdam

2        0101 0011  1001 0101  01** ****     Amsterdam

1        0101 0011  1001 0101  0100 0***     The Hague

ETR      0101 0011  1001 0101  0100 0001     The Hague

I am assuming some meshiness at the top levels of the hierarchy -
such as between the "100*" ALT router(s) and the "010*" router(s).
Without that, all queries would have to go up a level to router or
set of ALT routers for "1***", which would be very busy indeed,
including meshing to another set of ALT routers for "0***".

Meshiness at lower levels would generally reduce path lengths -
since the packet could travel to a lower level ALT router which is
topologically close to the destination, rather than having to
traverse more ALT routers up and down the hierarchy.

However, this would involve a large number of GRE links between ALT
routers.  That is OK, since GRE is not like paying for a fibre link.
 Taken to a logical extreme, all level 1 ALT routers could be fully
meshed and have a GRE tunnel to all other ALT routers - then the
higher levels wouldn't be needed.  But that would be fragile and
hard to administer due to the hundreds of thousands of GRE tunnels
for each ALT router.

I have made assumptions about the lower levels being geographically
close, due to a presumption that the ALT system would not be highly
aggregated at the lower levels.  That means the ALT router at level
1 in The Hague would be handling many unrelated aggregates, each
sparsely populated, according to whatever nearby ETRs advertised
their EIDs to it.

Alternatively, there could be strong aggregation at all levels of
the ALT hierarchy.  In that case, the problem I am discussing is
worse, since the level 1 ALT router could be anywhere in the world
with respect to the ETR in The Hague, or the Seychelles, or wherever
the the network (or single host) with this EID is physically located
at the current time.

The big questions are:

1 - Where are these ALT routers "Somewhere-x"?

2 - What is the total geographical path length (and number
    of routers in each GRE tunnel) from Somewhere-1 to
    Somewhere-7?

Because the IP addresses are assigned to organisations with little
regard for geography, and since those organisations are going to be
running these ALT routers at their own sites, it is most likely that
the locations of these 7 ALT routers will not be highly correlated
in a geographical sense.  Maybe some are in Europe and some in the
USA, China or Singapore.

So the path length for the whole trip could be be very long indeed -
longer than the longest path one could create on the Internet - due
to the need to tunnel back and forth between geographically
dispersed ALT routers at various levels of the hierarchy.

I think a global query network is a really bad idea.  ALT is a poor
way of building a global query network - since it tries to impose
the mathematical purity of strong aggregation, without considering
how this will generally greatly extend the total geographic path length.

(I never really understood how CONS would work, but perhaps CONS
would be subject to this same critique, since its structure was also
to be based on strong address aggregation.)

My guess is that the attraction of ALT (CONS too?) is primarily one
of feel - the attraction of concepts which have not been fully
considered.  After two or so decades of frustration, battling to
help the BGP network run efficiently, by trying to impose address
aggregation on it - and largely or utterly failing - ALT is a
satisfying fresh start.

By administrative fiat, the ALT hierarchy is structured to strongly
aggregate addresses.

The trouble is, this makes things far slower, when implemented on a
global scale.  This will not show up in experiments, except on a
very large, genuinely geographically dispersed, prototype network.

The only workaround I can imagine would be to locate all the higher
level ALT routers in the same place - "ALT-Central".  Then the
system becomes a star-structured thing, with links out to ETRs and
ITRs all over the world.  There will be little or no correlation
between the EID addresses of those ETRs and geography.

So almost all queries and encapsulated traffic packets would leave
the ITR, travel to wherever ALT-Central is located, and then to the
ETR.  If both were 1/4 Earth circumference from ALT-Central, this is
a half-way round the Earth one-way trip, even if the ITR and ETR are
physically very close to each other.

This would make the responsiveness of the system dependent on how
far the ITR and ETR are from ALT-central.  This would not be
acceptable to folks in Australia, New Zealand, Japan or Moscow - who
are far from ALT-Central's most likely location: the USA.

I suppose there could be multiple ALT-Centrals, in Europe, the USA,
Japan etc. - all meshed with each other - but this would be really
expensive and ugly.

The only way I can imagine the new architecture operating without
dropping or unreasonably delaying traffic packets is to allow for a
flexible deployment of:

1 - Full database ITRs

2 - Caching ITRs close to:

3 - Full database query servers

  - Robin        http://www.firstpr.com.au/ip/ivip/

--
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: Xu Xiaohu <[email-masked]>
Date: Tue, 29 Jan 2008 15:20:13 +0100

>    advertising summary prefixes to the LISP-ALT routers logically
Does LISP-ALT seem like a variation or a simplified instance of LISP-CONS? 
Both of them introduce a hierarchical overlay network which is
topology-independent. The difference is: in LISP-CONS, the overlay network
is just used for mapping query and reply. While in LISP-ALT, the overlay can
also be used for forwarding the initial traffic in order to solve the
initial packets loss in ITR when cache missed. Is that correct?

> with little or no correlation with geography. 
...
> and not at all on address aggregation.
If the overlay network is used for traffic forwarding, what you mentioned is
inevitable. And if the usage of PI address is desired and encouraged, the
major assumption of ALT will have not a leg to stand on and the things will
become worse.

Xiaohu XU

---

From: "K. Sriram" <[email-masked]>
Date: Tue, 29 Jan 2008 18:40:30 -0500

>and not at all on address aggregation.

I am attaching a slide which provides a diagram similar to
the scenario that Robin has used; it shows a sequence of LISP ITRs
that a packets traverses from source host to the destination host,
while passing through several levels of aggregation hierarchy.
I do need to read the LISP-ALT document carefully, but my
quick question for now is:
Referring to the diagram, once the EID space x/24 has been mapped
to locator ETR1 and this mapping information is known,
then why can't ITR4 have a route entry that points to ITR8
(pink arrow) as the next hop towards destination x/24 (locator ETR1).
Note that ITR4 and ITR8 are have a direct link (topologically).
If the packet can cut across from ITR4 to ITR8 at mid-level
in the hierarchy of ITRs (i.e., when topology allows it), then the
very long path (shown by the sequence of black arrows) can be avoided.
What does LISP-ALT gain in principle by preventing ITR4 from having
this route entry (i.e., ITR8 as next hop for EID space x/24 at ETR1)?

Sriram

K. Sriram
E-Mail: [email-masked]
Web:  http://www.antd.nist.gov/~ksriram/

---

From: Robin Whittle <[email-masked]>
Date: Wed, 30 Jan 2008 11:26:07 +1100

Hi Xu,

You wrote:

>> EID prefix allocation hierarchy.  LISP-ALT routers at each
>> level in the this hierarchy are responsible for aggregating all
>> EID prefixes learned from LISP-ALT routers logically "below"
>> them and advertising summary prefixes to the LISP-ALT routers
>> logically "above" them.

> Does LISP-ALT seem like a variation or a simplified instance of
> LISP-CONS? Both of them introduce a hierarchical overlay network
> which is topology-independent.

I think CONS and ALT are driven by a common goal - to build a new
network of routers in which aggregation is achieved to a very high
degree.  On the face of it, this should make the network highly
efficient - but this won't be true when the routers are physically
scattered all round the world, with their geographic location having
little or nothing to do with the prefixes they are handling.

It probably should have been clear to me that this was a problem
with CONS too.  I didn't clearly recognise this because I had too
much difficulty understanding how CONS would work anyway.

> The difference is: in LISP-CONS, the overlay network is just used
> for mapping query and reply.  While in LISP-ALT, the overlay can
> also be used for forwarding the initial traffic in order to solve
> the initial packets loss in ITR when cache missed. Is that
> correct?

This is one difference, and in principle it is a nifty thing to do
with the ALT network - sending the initial traffic packets and using
them as mapping requests.  This is the same nifty technique APT
caching ITRs use with their Default Mapper - but that APT is
practical, since the Default Mapper is local, with low delays, low
communication costs and high reliability.  APT's default mapper
tunnels the traffic packet directly to the ETR it chooses, in the
usual ITR fashion - whereas ALT is used to deliver the traffic
packet to the appropriate ETR via a probably circuitous path over
the ALT topology.

Another difference is that ALT is made from existing protocols - GRE
and BGP.  This saves defining new protocols and writing a bunch of
new software for each implementation.

Another critique of ALT (and I think CONS) is how to secure the way
ETRs advertise their EID prefixes.  How can any or all of the ALT
routers verify that some device, ostensibly the (or one of the)
authoritative ETR really is authoritative, right now, for the EID it
is advertising?

The ETR(s) chosen by the end-user will be changing from
time-to-time.  I think there needs to be some crypto and a method of
 verifying these advertisements before traffic packets are sent to
the device which advertises these EIDs.  That has to have some
degree or centralised and/or distributed coordination which I think
is not covered by the ALT ID.

The security of Ivip's mapping information depends on some crypto
protection of the multiple streams of mapping updates (and likewise
downloads of the current maps, for ITRD/QSD start-up) and on the
Root Update Authorisation Server ensuring it only accepts mapping
changes from users via an authenticated method:

  http://tools.ietf.org/html/draft-whittle-ivip-arch-01#page-60

This makes security a lot easier.  It also completely separates the
mapping database part of the system from the ETRs, though there is
nothing to stop an end-user embedding mapping update functions in
their ETR(s), with the required username and password for accessing
the Update Authorisation Server system which handles their micronet.

>> This is presumably impossible at the edge of the network, since
>> the location of ETRs for a given EIDs are scattered around the
>> place with little or no correlation with geography.
>
> ...
>
>> By mandating the structure of the ALT network be strongly
>> driven by address aggregation, this means the connections
>> between one router and the next in the hierarchy will have
>> little or no relation to geography.  Therefore, the average
>> length of inter-router distance will be far longer than for
>> ordinary BGP routers, where the network structure is based
>> primarily on linking to geographic neighbours, and not at all
>> on address aggregation.
>
> If the overlay network is used for traffic forwarding, what you
> mentioned is inevitable.

My understanding is that the ALT network has 3 or 4 functions:

  1 - ITR sends map query.  ALT network forwards this to an
      authoritative query server, which is typically one of
      the currently active ETRs.

  2 - That ETR (or whatever responds to the query) sends the
      query back through the ALT network.  However, this is
      not required and the ID says it can be sent back
      directly to the ITR.  (The same option was added to
      CONS, or at least acknowledged as a possibility on
      the mailing list, after I questioned why the reply
      had to go back through the CONS network.)

  3 - The ITR encapsulates a traffic packet (raising PMTU
      and fragmentation problems ...) and the ALT network
      forwards it as for a mapping query.  It functions as
      a mapping query and also, ideally, gets to the ETR -
      so no traffic packets are lost.

  4 - I think there is some suggestion ("gleaning") of
      piggybacking some EID-RLOC mapping information onto
      1 or 3 above, on the basis that the ETR is (or is
      near) and ITR which will soon want to know the mapping
      of the sending host.  My understanding may be quite
      wrong.

So I don't think that ALT is unworkable only if it is used to
forward initial traffic packets.  I think it is unworkable because
it is a global query server system.  I think it is even more
unworkable because the path for queries, traffic packets and perhaps
replies would often criss-cross countries and oceans.  Living in
Australia, I know all about the latency of the Pacific Ocean, under
which most packets to the outside world travel.

> And if the usage of PI address is
> desired and encouraged, the major assumption of ALT will have not
> a leg to stand on and the things will become worse.

I think ALT is completely unviable.  I am keen for the the LISP team
respond to my critique - now beautifully illustrated by K. Sriram.

---

From: Robin Whittle <[email-masked]>
Date: Wed, 30 Jan 2008 13:22:02 +1100

Hello K. Sriram,

Thanks very much for this beautiful illustration of the problem I
tried to describe.  For those without PowerPoint, I have a PNG of it
 here:

http://www.firstpr.com.au/ip/ivip/misc/strong-aggregation-k.sriram.png

You wrote:

> I am attaching a slide which provides a diagram similar to the
> scenario that Robin has used; it shows a sequence of LISP ITRs 
> that a packets traverses from source host to the destination
> host, while passing through several levels of aggregation
> hierarchy. I do need to read the LISP-ALT document carefully, but
> my quick question for now is: Referring to the diagram, once the
> EID space x/24 has been mapped to locator ETR1 and this mapping
> information is known, then why can't ITR4 have a route entry that
> points to ITR8 (pink arrow) as the next hop towards destination
> x/24 (locator ETR1). 

As far as I understand ALT, it can.  This would be an instance of
"meshiness" - links between branches of what would otherwise be a
purely tree-like, highly aggregated, structure.  The sole mention of
"mesh" in the ID is:

  http://tools.ietf.org/html/draft-fuller-lisp-alt-01#section-7

    EID-Prefix Aggregation

      The LAT peering topology should be arranged in a tree-like
      fashion (with some meshiness), both with redundancy to deal
      with crashes.

> If the packet can cut across from ITR4 to ITR8 at mid-level in
> the hierarchy of ITRs (i.e., when topology allows it), then the
> very long path (shown by the sequence of black arrows) can be
> avoided. What does LISP-ALT gain in principle by preventing ITR4
> from having this route entry (i.e.,  ITR8 as next hop for EIDspace
> x/24 at ETR1)?

It is not actually prevented, but what it gains, in principle, is
that the future architecture of the Internet is to be based on a
**highly aggregated** global network.  I figure this feels good
because it is a relief from the terribly disaggregated network of
the present Internet.

The naturally somewhat tree-like topology of the Net (largely
according to geographic distance to peers with which traffic will
flow) is a problem for routers unless the allocation of address
space closely matches the topology.  So for all of its history,
including to the present day, there has been pressure to allocate IP
addresses according to geography and/or topology, and to resist
disaggregation.  Those who push for this (the folks who pay $$$$$$$
to own and run BGP routers, for instance), have valid concerns, but
are effectively the fun-police from the point of view of end-users
who want and need to make their slices of space appear at various
diverse physical locations.

("Fun" means using their limited address space efficiently,
achieving reliable multihoming, and using the space for multiple
sites in geographically different locations - so this is really a
set of pressures for address allocation which is contrary to the
business needs of most end-users.)

All this stress over disaggregation is resolved, after a fashion,
with ALT - a clean, new network with nice orderly aggregation.

I think that is all that is gained in principle.

I think that ALT or any other global query server system is not
required for the new map-encap architecture.

However, consider the fate of the ALT network if all these ALT
routers (ITR1 to ITR8 in the diagram) had not only links to their
peers according to the edict of a hierarchy based strictly address
aggregation, but also according to which other ALT routers were
nearby (at least in terms of existing links via the Internet).

With the pure ALT approach (a pure aggregated tree) with each router
handling 3 bits of aggregation (as per my example) then each router
has 9 peers - one up the hierarchy and 8 down.  This is a manageable
number of GRE tunnels and a manageable number of peers for the BGP
instance to handle.

Suppose we added another 8 geographic peers.  This would be fine
too: 17 GRE tunnels and 17 BGP peering sessions is manageable.

In this particular example, the total path for the mapping query or
encapsulated traffic packet (also a query) would be shorter, because
it happens that ITR4 has ITR8 as one of its 8 geographic neighbours
- saving the packet a trip across the Atlantic and back.

But how often in real life would such a level of meshiness result in
a shorter path?   This would need to be determined by a computer
modelling.

First there would need to be some explicit assumptions about the
physical location of ALT routers - exactly where the one or more ALT
routers for each particular part of the hierarchy would be located
in today's Internet topology.

Then there would have to be a rule about how many bits were
aggregated by each level of the hierarchy - or to run the model with
a variety of settings for this parameter.  Then run the model with
ITRs in general linking to various numbers of geographic neighbours.
 Then with a representative sample of ITRs and ETRs, according to
known (does anyone really know?) traffic patterns, simulate the path
taken by the request or traffic packet to see the total path length.
 There would be a wide distribution, with some improvement from the
geographic neighbour links.

Perhaps there would be some value of geographic neighbours which was
both feasible for each ALT ITR and which produced significant
overall benefits.  However, the worst case would still involve very
long paths.

Imagine if ITR4 wasn't linked to ITR8, but to ITR9, which was also
linked to ITR8.  Does ITR9 only advertise the prefixes of its place
in the ALT hierarchy?  If so, then ITR4 will not see it as a
shortcut to ITR8.  If so, then how far does this go in the ALT
system?  What is to stop the system propagating vast numbers of
prefixes via BGP, peer-to-peer.  Then every ALT router would have
routes within the ALT topology to every other ALT router.  I think
this is not what the ALT developers intend.

---

From: [email-masked] (Noel Chiappa)
Date: Tue, 29 Jan 2008 22:15:54 -0500 (EST)

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

    > degree.

This doesn't match my understanding of CONS at all. CONS nodes are not
routers, any more than nodes in the DNS hierarchy are routers. CONS is just a
resolution hierarchy, just like DNS; at a very high level, the only
difference between DNS and CONS is that DNS maps from DNS names to A/etc
records, whereas CONS maps from IDs to RLOCs.

The only thing I've heard of that is not this way is that IIRC there has been
some discussion of using the CONS resolution hierarchy to forward *data*
packets during the period when the ITR doesn't have the appropriate ID->RLOC
mapping for a particular destination. This is analogous to having the DNS
hierarchy forward data packets while the host is waiting to get the
DNS->IP_address mapping.

This is a potential optimization, and not an architectural fundamental to
CONS; a number of other approaches have been suggested for the 'how to handle
data packets while the ITR it waiting for the ID->RLOC mapping' issue, ones
that do not involve the CONS hierarchy in handling such data packets.

    > I had too much difficulty understanding how CONS would work anyway.

CONS is conceptually fairly simple; think DNS, but replace "DNS names" with
"IDs" and "A/etc records" with "RLOCs". The fine details differ a fair
amount, for a long list of reasons having to do with the operational
environment and requirements, etc, but that's the broad-stroke picture.

	Noel

---

From: [email-masked] (Noel Chiappa)
Date: Tue, 29 Jan 2008 22:41:31 -0500 (EST)

> Thanks very much for this beautiful illustration ....
    > For those without PowerPoint, I have a PNG of it here

Thanks for that.

Looking at the picture, though, I am completely confused by this one too (in
the sense of 'it has no relationship to how I thought things worked').

ITRs (and ETRs) are not routers (although they are colocated with routers in
a single box), and they are not connected in a mesh. In other words, I would
never expect to see a packet sent from one ITR to another. Ever.

ITRs are mapping/wrapping devices: they take a packet, map the destination ID
to an RLOC (of the ETR), wrap the packet up in a wrapper with that RLOC as
the destination, and send that wrapped packet off through the *router*
network to the ETR. When it gets there, the ETR takes the wrapper off, and
forwards the packet onto the destination.

In other words, the path for the average inter-site packet looks like:

Step A - 0 or more local routers
Step B - ITR
Step C - 1 or more backbone routers
Step D - ETR
Step E - 0 or more local routers

    >> it shows a sequence of LISP ITRs that a packets traverses from source
    >> host to the destination host

A packet would normally only ever transit a single ITR.

    >> while passing through several levels of aggregation hierarchy.

The aggregation hierarchy is only there for the *resolution* phase (like
DNS); there is no hierarchy associated with the handling of user data packets.

    >> Referring to the diagram, once the EID space x/24 has been mapped to
    >> locator ETR1 and this mapping information is known, then why can't
    >> ITR4 have a route entry that points to ITR8 (pink arrow) as the next
    >> hop towards destination x/24 (locator ETR1).

Mapping entries are not routing entries; i.e. one mapping entry never points
to another mapping entry. A mapping entry only ever points to the destination
ETR.

	Noel

---

From: Robin Whittle <[email-masked]>
Date: Wed, 30 Jan 2008 15:26:33 +1100

Hi Noel,

I am replying to your two messages, in which you wrote, in part, and
in a different order:

> CONS is conceptually fairly simple; think DNS, but replace "DNS
> names" with "IDs" and "A/etc records" with "RLOCs". The fine
> details differ a fair amount, for a long list of reasons having
> to do with the operational environment and requirements, etc, but
> that's the broad-stroke picture.

I think that function of the entire CONS network, treating it as a
black box, was to look up a distributed global database and return
the answer.  In this respect, it resembles the DNS.

However the CONS network was a network of message passing devices,
not unlike routers.

>> I think CONS and ALT are driven by a common goal - to build a
>> new network of routers in which aggregation is achieved to a
>> very high degree.
>
> This doesn't match my understanding of CONS at all. CONS nodes
> are not routers, any more than nodes in the DNS hierarchy are
> routers. CONS is just a resolution hierarchy, just like DNS; at a
> very high level, the only difference between DNS and CONS is that
> DNS maps from DNS names to A/etc records, whereas CONS maps from
> IDs to RLOCs.

The CONS nodes (CARs and CDRs) were functioning as peer elements in
a message passing network, organised in a way which resembles a
network of routers.  I recall that the topology of their connections
was supposed to be organised according to the address ranges they
were responsible for.  Likewise the topology of connections between
ALT routers in the ALT network.

CONS involved new protocols and software.  The ALT network ferries
queries, initial traffic packets and perhaps responses back and
forth in a broadly similar way, without the need for new protocols
or software.

Regarding my critique and K. Sriram's diagram:

> Looking at the picture, though, I am completely confused by this
> one too (in the sense of 'it has no relationship to how I thought
> things worked').
> 
> ITRs (and ETRs) are not routers (although they are colocated with
> routers in a single box), and they are not connected in a mesh.
> In other words, I would never expect to see a packet sent from
> one ITR to another. Ever.

I agree.  If you imagine a modified version of the diagram, with
"ITR2" to "ITR8" converted to "ALT router 2" to "ALT router 8", then
 I think there will be no difficulty seeing it as an example of how
a query or initial traffic packet is passed from ITR1 to ETR1 via
the ALT network.

> The aggregation hierarchy is only there for the *resolution*
> phase (like DNS); there is no hierarchy associated with the
> handling of user data packets.

Yes - except for the initial traffic packets the ITR sends on the
ALT network when it doesn't yet have mapping data for those packet's
destination EIDs.

 - Robin

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 30 Jan 2008 08:05:07 -0500 (EST)

>> The fine details differ a fair amount, for a long list of reasons
    >> having to do with the operational environment and requirements, etc,

    > ... function of the entire CONS network .. was to look up a distributed
    > global database and return the answer. ..
    > However the CONS network was a network of message passing devices, not
    > unlike routers.

It is true that the CONS system operates in detail somewhat differently from
the DNS (but I already said as much :-).

One of those differences, as you point out, is that when traversing the
hierarchy to resolve a hierarchically structured name, in CONS the entities
in the hierarchy talk to one another on the requester's behalf, whereas in
DNS, generally (i.e. in non-recursive mode) the entity trying to acquire the
mapping talks directly to each node in the hierarchy in turn.

I wasn't in the loop when this operational mode was originally picked for
CONS, but I imagine it was done for two main reasons: efficiency, but mostly
security. (If I've guessed wrong, hopefully the initial CONS designers will
enlighten me!)

Efficiency because to the degree that the path between the entities in the
resolution hiearchy to the entity holding the desired mapping is shorter than
a path that repetitively loops back to the source of the request (as it will
be in all but pathological cases), reponse time will be faster.

Security is because the limited number of inter-node links are configured and
protected, whereas if the 'original requester communicates directly with each
entity in the hierarchy' model is used, there was originally no signing
mechanism in CONS to protect the data, and thus no way to authenticate the
reponses - other than a painfully slow specially-opened TCP connection. (These
days, security - particularly against DoS attacks - is more of an concern than
back when the DNS was designed.)

Although the CONS network is indeed a network of message passing devices, I
think it's unwise to think of it as being "not unlike routers" because I think
it's too easy to thereby confuse people (into thinking, e.g. that it forwards
user data traffic). Once might just as well say that the network of SMTP
servers is "not unlike routers"!

    > The CONS nodes (CARs and CDRs) were functioning as peer elements in a
    > message passing network

The word "peer" is one I find slightly confusing when used to describe a
system which explicitly has "child" and "parent" nodes/entities; to me,
intuitively, a peer can only be something at the same level in the hierarchy,
not at a level above or below.

It was explained to me that the use of peer to mean 'entity with which one
communicates directly' came from BGP, and BGP peers. However, this seems to
me to ignore the fact that in BGP, there is no hierarchy - all BGP nodes are
'at the same level', at least in terms of the operation of the protocol (I am
aware that in operational terms, we have lots of non-transit leaf nodes).

    > If you imagine a modified version of the diagram, with "ITR2" to "ITR8"
    > converted to "ALT router 2" to "ALT router 8"

This is a reminder that we need to be careful with terminology. People are
discussing a number of similar mapping systems, and components thereof, and
we need to be careful to not mix them up. (E.g. CONS is not LISP - it's just
one potential way to provide the mappings which LISP needs.)

	Noel

---

From: Robin Whittle <[email-masked]>
Date: Thu, 31 Jan 2008 08:37:53 +1100

Hi Noel,

I am keen to know what you and others think of my critique of ALT's
core design principle of strong address aggregation being at odds
with the need for short total path lengths.

  http://psg.com/lists/rrg/2008/msg00229.html
  http://psg.com/lists/rrg/2008/msg00237.html

In two days only two people - Xiaohu Xu and K. Sriram - have
commented on it.

Likewise my constructive critique of ALT + NERD, which points out
deficiencies and proposes a series of improvements:

  http://psg.com/lists/rrg/2008/msg00176.html
  http://psg.com/lists/rrg/2008/msg00189.html

That was nine days ago.

Only Eliot Lear and David Meyer responded to this critique, and so
far no-one has debated the merits of the series of improvements I
suggest, starting with the desirability of local query servers in or
near NERD ITRs to support caching ITRs.

Since most attention on this list is focussed on LISP, I would have
thought that more people would have something to say about these
critiques.

ALT is a network of routers.  CONS didn't refer to its CDRs and CARs
as "routers", but like ALT's routers, they formed a mesh and/or tree
structure for passing messages back and forth between ITRs and ETRs,
with each making some decisions about which neighbouring device to
send the message to.  In that way, I think CONS much more resembles
a network of routers and the ALT network than does DNS.

  - Robin

---

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

Regardless of the details, is it a surprise that the path
taken by initial packets while waiting for a mapping have
significantly greater length than the path established
after the mapping arrives? There seems to be an inevitable
design choice between:

1. Discard those packets;
2. Queue them;
3. Send them a long way round.

All these choices are compatible with the datagram model,
so I don't see how any of them can be architecturally
"wrong". From an engineering viewpoint, #3 seems
reasonable (i.e. this minor delay will be added to the
other delays for starting an application-level session).

    Brian

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 30 Jan 2008 18:32:32 -0500 (EST)

> core design principle

Alas, I haven't had the time to study ALT in detail, so I can't help here.

    > strong address aggregation being at odds with the need for short
    > total path lengths.

In both ALT (I think - perhaps I'm confused about this detail of ALT, if so
someone please enlighten me) and LISP+CONS, only the first/first-few data
packets (i.e. until the EID->RLOC mapping gets propogated back to the ITR)
will be sent (inefficiently) along the server hierarchy; after that, they
go direct. Is this slight temporary inefficiency really that important?

    > CONS didn't refer to its CDRs and CARs as "routers", but like ALT's
    > routers, they formed a mesh and/or tree structure for passing messages
    > back and forth between ITRs and ETRs

I responded to this in a previous message: unlike DNS (which requires the
entity desiring a mapping to potentially communicate directly with each node
which is part of the path through the resolution hierarchy, in turn - i.e.
first the root, then .EDU, then .MIT.EDU, then .LCS.MIT.EDU, etc), CONS does
this all internally, and passes only the final answer to the requester. (I
gave some of what I perceived to be the rationale for this design choice in
that same message.)

	Noel

---

From: [email-masked]
Date: Wed, 30 Jan 2008 19:43:39 -0500

Noel:

Many thanks to you and Robin for detailed comments/responses to my question
(motivated by Robin's original email on this topic).
I have updated the diagram to replace "ITR2" through "ITR8" with
"ALT-rtr2" through "ALT-rtr8" (new PNG link below):
http://www.antd.nist.gov/~ksriram/strong_aggregation.png

With this, let me restate my question/suggestion slightly differently.

> DNS); there is no hierarchy associated with the handling of user data

Yes, but as you have also acknowledged in your more recent email -- 
query/response messages and first-few (or perhaps first-several) "data
packets will be sent (inefficiently) along the server hierarchy".  

> go direct. Is this slight temporary inefficiency really that important?

So my question is: Can we not make an enhancement to the way the
query/response messages and first data packets are handled in ALT routers to 
take advantage of any available shorter paths (bypassing the hierarchy as and
when feasible)? In the example in the diagram, the topological (pink) link 
from ALT-rtr4 to ALT-rtr8 can be exploited to obtain a much shorter path 
and reduce the delays substantially. Robin had some interesting thoughts 
about how this was doable in principle but will add some complexity.
http://psg.com/lists/rrg/2008/msg00237.html
I would like to hear your thoughts on this and from others who may be 
interested in these details of LISP-ALT.

Modeling needs to be done to quantify the delays due to potentially
very long paths along the ALT-rtr hierarchy and their performance impacts.
Meanwhile, I think it is worth exploring some enhancements that can 
potentially improve performance under these circumstances.
 
Sriram
http://www.antd.nist.gov/~ksriram/

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 30 Jan 2008 19:49:56 -0500 (EST)

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

    > Regardless of the details, is it a surprise that the path taken by
    > initial packets while waiting for a mapping have significantly greater
    > length than the path established after the mapping arrives?

Except in full-push systems like NERD...

    > There seems to be an inevitable design choice between:

Excellent point. There are obviously engineering implications behind doors #2
(queue management) and #3 (hot-spots at the top of the resolution hierarchy,
if you do some sort of hierarchy-based alternative forwarding), but that's to
be expected.

    > All these choices are compatible with the datagram model, so I don't
    > see how any of them can be architecturally "wrong".

"The difference between theory and practise is even bigger in practise than it
is in theory." :-) Yes, in theory one could chose door #1, and just toss them,
but in the real world people don't seem to like that one.

    > From an engineering viewpoint, #3 seems reasonable (i.e. this minor
    > delay will be added to the other delays for starting an
    > application-level session).

Yes... which is why a number of ideas have been floated for how to do that
(multicast groups, forwarding along the resolution tree, etc). I wonder if
there are any good ideas we haven't explored yet on how to do this?

	Noel

---

From: Robin Whittle <[email-masked]>
Date: Thu, 31 Jan 2008 12:27:29 +1100

Hi Brian and Noel,

I understand you agree with my critique of ALT - that it would delay
initial traffic packets, due to it being a global query server
system and moreso due to its requirement for strong address
aggregation.  Both of you seem to regard this as unimportant, or at
least as being non-fatal:

BC > From an engineering viewpoint, #3 [Send them a long way round.]
BC > seems reasonable (i.e. this minor delay will be added to the
BC > other delays for starting an application-level session).

NC > In both ALT (I think - perhaps I'm confused about this detail
NC > of ALT, if so someone please enlighten me) and LISP+CONS, only
NC > the first/first-few data packets (i.e. until the EID->RLOC
NC > mapping gets propogated back to the ITR) will be sent
NC > (inefficiently) along the server hierarchy; after that, they
NC > go direct. Is this slight temporary inefficiency really that
NC > important?

I think it is really important.  Even a half-second delay in session
establishment is an enormous burden on all users, since the new kind
of mapped address space will, ideally, be used at one or both ends
of most Internet communications.

Even a half-second delay would make this new kind of address space
suck so much that it would be much harder to convince people to use it.

Christian Vogt wrote about the slowdown in TCP due to delay or loss
of initial packets:

  http://psg.com/lists/rrg/2008/msg00162.html

I wrote in more detail about this:

  http://psg.com/lists/rrg/2007/msg00462.html

My critique of ALT's insistence on strong address aggregation
indicates that it will be common for initial packets to be delayed
much more than half a second.  Beyond a second or so, I think it is
fair to say the packet is useless - that the higher layers will have
given up and will be try to start another session, perhaps with
another destination host where the same trouble might reoccur.

The delayed packet may be worse than useless, since it is travelling
round the ALT network (and so encumbering the Internet), using
resources in ALT routers, eventually emerging at the ETR, using
resources there and then being sent to the destination host, which
will probably send a response back (more mapping lookups and delays,
if the original sender used an EID address too).  The response
packet will be worse than useless too, since by the time it arrives,
the upper layers will be trying to establish another session.

I doubt that there could be consensus in the RRG that such delays in
initial packet delivery and session establishment would be
acceptable unless there was also consensus that all other schemes
which do not delay packets (NERD, APT and Ivip) were completely
unworkable.

Even if ALT could be tweaked to improve its meshiness so as to
generally reduce the path length (but meshiness is unlikely to help
in every ITR-ETR case), it is still a global query server network -
meaning it is slow and unreliable.  I think it would probably be
more expensive and harder to manage than the push systems it is
intended to avoid the need for.

  - Robin

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 30 Jan 2008 20:47:27 -0500 (EST)

> From: [email-masked]

    > very long paths along the ALT-rtr hierarchy and their performance
    > impacts. Meanwhile, I think it is worth exploring some enhancements
    > that can potentially improve performance under these circumstances.

Yes, but that behaviour (forwarding the first/first-few packets along the
resolution hierarchy) in itself is an optimization (see Brian's previous
message) affecting only a small share of user data packets.

Do you really want to try and optimize an optimization, and only for that
small share of traffic?

    > Can we not make an enhancement to the way the query/response messages
    > and first data packets are handled in ALT routers to take advantage of
    > any available shorter paths (bypassing the hierarchy as and when
    > feasible)?

I can't respond about ALT, but adding these kind of short-cuts in the
resolution hierarchy was something that was considered at some length for
CONS, in order to speed up resolution (i.e. reduce resolution delay), and
also avoid a load concentration at the root.

A number of other optimizations which had the same effect (reducing
resolution delay) were developed, and since this particular one i) added a
fair amount of complexity, and ii) didn't buy that much with the other
optimizations in place, it was dropped.

Now that it is proposed to use the resolution hierarchy to forward packets
for which the mapping is missing, I think it might be worth taking another
look at that optimization, but it would only be to avoid creating a potential
load hot-spot at the root, and not for any slight increase in perfomance for
that small share of the traffic which used it.

	Noel

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 31 Jan 2008 15:31:59 +1300

Robin,

<snip>
> 
> ...  Even a half-second delay in session

Certainly there's an issue if the initial retransmission timeout
is systematically less than the actual initial RTT. I believe
the Windows default is 3 seconds, for example. If the RTT turns
out to be 4 seconds, we have a problem. But as long as we
steer clear of that problem, I still don't see why adding
the mapping delay to the DNS delay (given that both answers
will be cached in the case of repeated sessions to the same
server) is going to be a significant problem for the users.

> the upper layers will be trying to establish another session.

Not if the timers are right. TCP will still be quietly waiting
for its SYN/ACK. Media streams will start up just a second or two
more slowly. I really don't see why users will be any more
disturbed than they are today by existing session set-up delays.

> which do not delay packets (NERD, APT and Ivip) were completely

Certainly, no delay is better than delay.

> intended to avoid the need for.

I assume you mean "push-everything" schemes, and given that some
are arguing for 10^10 map entries, I have great difficulty agreeing
that any push-everything scheme is deployable. At the 10^8 level
it seems conceivable.

     Brian

---

From: Robin Whittle <[email-masked]>
Date: Thu, 31 Jan 2008 14:47:47 +1100

Hi Brian,

Thanks for your response.

> Certainly, no delay is better than delay.

but I do not believe we should accept a new architecture which
typically delays any packets more than a very short time, say 100ms
at the very most.  I think a few ms to a few tens of ms would be
achievable in most cases with local Query Servers - meaning within a
few hundred km of the caching ITRs.

> are arguing for 10^10 map entries, I have great difficulty
> agreeing that any push-everything scheme is deployable. At the
> 10^8 level it seems conceivable.

I think such numbers beyond 10^9 are achievable by the time any such
growth would occur - with a mix of caching ITRs, local Query Servers
and full database ITRs.  This is the principle of APT and Ivip.

I discussed these large numbers of EIDs/micronets in a message
"Single Host Granularity (SHG) with full database ITRs & Query
Servers", which I posted yesterday, and will post again, since it
has not yet appeared on the list.

 - Robin

---

From: David Conrad <[email-masked]>
Date: Wed, 30 Jan 2008 19:57:17 -0800

Robin,

> which do not delay packets (NERD, APT and Ivip) were completely

It seems we have a choice:

a) scalable to host granularity but imposing some delay at session  
initiation

- or -

b) no additional latency but more limited scalability.

For me, it isn't a question of 'workability'.  Both options can be  
made to work.  In case (a), people just learn to deal with the  
additional delay and modify protocols appropriately.  In case (b), you  
limit the size/granularity of the PI Internet and people adjust  
accordingly.  The question is which is less likely to bite us before  
we migrate to IPvN+1?

> meaning it is slow and unreliable.

A pull system would indeed be slower at session initiation.  After  
that, it isn't clear to me that there would be a latency difference.   
However, I will admit some confusion about the lethality of this.   
Session establishment invariably already needs to deal with  
unreliability and various delays (DNS, ARP), yet the Internet  
functions.  Why do you feel the additional latency of a pull system is  
fatal?

> I think it would probably be

I'm much more skeptical of this claim.  Compare the cost of building  
and maintaining a caching-only DNS server to a Netnews server with a  
reasonable set of feeds...

Regards,
-drc

---

From: Robin Whittle <[email-masked]>
Date: Thu, 31 Jan 2008 16:17:55 +1100

Hi David,

> b) no additional latency but more limited scalability.

My understanding of what you wrote is:

  a) Scaling to the largest number of EIDs/micronets of any
     possible system, by having a pure pull system, with a global
     query server network (ALT) - and thereby not pushing the full
     database anywhere, or even necessarily having it all at any
     one location.

  b) Less ability to scale (absolute physical limits and/or
     more costs) to the largest numbers of EIDs/micronets due to
     the requirement of pushing the full database to some or all
     ITRs (and perhaps local query servers) and to store it at each
     such location.

If you are depicting a choice between pure pull and pure pull, then
I think you should consider a hybrid system.

If, within b) you include the hybrid push-pull systems, with local
full-database Query Servers, caching ITRs as well as full database
ITRs (APT and Ivip), then in absolute terms, I agree with you:  A
hybrid push-pull system will be less scalable to astronomical
numbers of EIDs/micronets than a pure pull system.

The question then becomes:

  Is it possible to craft a hybrid push-pull architecture which
  we believe will scale to the very high numbers of EIDs/micronets
  which may be required in the decades to come?

and

  Will the extra effort (if indeed it is harder than pure pull
  on a global basis) be justified by the benefits of little or
  no delay of initial packets, better reliability or other things
  - such as mobility?

To answer this, we would need some not completely ridiculous
estimates, which I discussed in a message just posted on "Single
Host Granularity (SHG)".

Without some sensible bounds on the expected numbers at a series of
dates in the future (say 2015, 2020, 2025, 2030) of EIDs/micronets,
the arguments for pure push or hybrid push-pull can always be
derailed by some ridiculously high guesstimate of future numbers.

I think it can be done.  I think APT or "NERD extended with local
query servers and caching ITRs" would be have a much better
combination of cost, low-delay performance and scalability than pure
NERD or pure ALT.

I think Ivip would be better still.

While APT imposes some restrictions on where the Default Mappers
need to be, Ivip enables the full database Query Server and ITR
functions of the Default Mapper to be handled by separate devices,
if desired, and for them to be located anywhere.

I believe this flexibility enables the one architecture to be
adapted to suit current conditions - both the local conditions of
particular ISPs (traffic patterns, hardware and connectivity costs
etc.) and and the global situation: number of micronets, rate of
updates, financial burden or profit to be made by running ITRDs and
QSDs, depending on degree of micronet end-user charging etc.

That way, in the future, if it turns out to be best for some or all
operators to have pure push, Ivip can be progressively deployed that
way by those operators.  Likewise, if it is very costly or
impractical to maintain ITRDs and QSDs, then these will retreat from
the edge, and there will be more caching ITRs.

Only if that "retreat" process continues to the point where these
full database devices are so far away from caching ITRs as to impose
excessive delays or unreliability could we say that the architecture
failed to achieve its goal.  That seems unlikely, because having as
few as a hundred locations which contained full database ITRs and
Query Servers would be much faster, more robust and probably easier
to manage than a pure ALT system - which is a single global system,
and therefore bound to be slow and unreliable.

> I'm much more sceptical of this claim.  Compare the cost of
> building and maintaining a caching-only DNS server to a Netnews
> server with a reasonable set of feeds...

Your scepticism is perfectly reasonable.  My task is to show that
fast push will be feasible and desirable.  It is an unusual task to
fan data out reliable and securely, with a few seconds latency on a
global scale.

In the next few weeks I plan to revise the Ivip material to make it
less monolithic and to provide more details of how the mapping data
could be pushed out *fast* to hundreds of thousands or millions of
ITRDs and QSDs.

  - Robin

---

From: Xu Xiaohu <[email-masked]>
Date: Thu, 31 Jan 2008 11:16:41 +0100

> when feasible)?
ALT routers use EBGP session, so the next-hop of the prefix will be
rewritten by each ALT router hop even it doesn't aggregate that prefix. 

Maybe Iljitsch's suggestion of a new attribute that contains the originator
of the prefix is useful.

Xiaohu Xu