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

[Robin Whittle <rw@firstpr.com.au>]

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:

>> 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 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.


> 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 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.

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


--
to unsubscribe send a message to rrg-request@psg.com 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