Subject: [RRG] Tradeoff between anycast and tree-hierarchy

From: Xu Xiaohu <[email-masked]>
Date: Thu, 31 Jan 2008 10:54:47 +0100

Hi All,

LISP+CONS and ALT are based on tree-hierarchy overlay, and the initial
traffic will be allowed to travel along the overlay in order to avoid
initial packets loss. However, this approach not only results in a longer
forwarding path but also a high forwarding pressure on the highest-level
nodes (like honey point). The initial traffic volume is not in the same
magnitude with the query messages in DNS hierarchy.

APT and ivip, based on the anycast idea, not only avoids the long path and
large-latency for the initial packets but also share the initial traffic
pressure among the different default mappers. However, they are not so
scalable to support host or micro-net granularity.

Could we consider some tradeoff between these two approaches? For example,
replace the default mapper with multiple mappers which are responsible for
different address-prefix blocks in APT and ivip, or allocate multiple
highest-level nodes in CONS or ALT, which are responsible for the same
address block, to many different network locations. 

Best regards,
 
Xiaohu Xu

--
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: Robin Whittle <[email-masked]>
Date: Mon, 04 Feb 2008 15:20:15 +1100

Hello Xiaohu,

You proposed some load-sharing techniques:

> LISP+CONS and ALT are based on tree-hierarchy overlay, and the
> initial traffic will be allowed to travel along the overlay in
> order to avoid initial packets loss. However, this approach not
> only results in a longer forwarding path but also a high
> forwarding pressure on the highest-level nodes (like honey
> point). The initial traffic volume is not in the same magnitude
> with the query messages in DNS hierarchy.

Traffic concentration at the highest-level nodes could be reduced by
having having all ALT routers fully meshed at a particular level -
beyond which there would be no need for higher levels.  For
instance, 221 ALT routers (or multiple routers for load-sharing and
redundancy) each aggregating one of the IPv4 /8 prefixes.  (221 is
the 0 to 223, not counting 127, 10 and 0, which is perhaps not
suitable for traffic).

> APT and ivip, based on the anycast idea, not only avoids the long
> path and large-latency for the initial packets but also share the
> initial traffic pressure among the different default mappers.
> However, they are not so scalable to support host or micro-net
> granularity.

I will write another message about why I think the mapping database
will never be so big that it would be impractical to have multiple
copies of it all over the Net.  So I think ALT etc. (global query
server systems) are not needed at all.

APT and Ivip share the encapsulation load between hundreds of
thousands of ITRs all over the Net, though at this stage APT doesn't
have an "anycast ITRs in the core" / "Proxy Tunnel Router" approach
to handling packets from networks without ITRs.

Your proposal aims to spread the load of encapsulating traffic
packets at any one ITR location between multiple ITRs.

> Could we consider some tradeoff between these two approaches? For
> example, replace the default mapper with multiple mappers which
> are responsible for different address-prefix blocks in APT and
> ivip, or allocate multiple highest-level nodes in CONS or ALT,
> which are responsible for the same address block, to many
> different network locations.

Ivip provides for load sharing amongst ITRs by having one ITR handle
one subset of the BGP-advertised prefixes while other ITRs handle
the remaining subsets.  This is not mandatory - most ITRs would
handle all these prefixes.  However, it remains an option for
spreading load at busy sites.

The idea is that an ITR would advertise, either in the internal
routing system or in the global BGP system, just those prefixes
which it handles.  These prefixes are called "Ivip Mapped Address
Blocks" in the current ID.  They are known as "MABs" - "Mapped
Address Blocks" in my attempt to define some terminology:

  http://psg.com/lists/rrg/2007/msg00533.html
  http://psg.com/lists/rrg/2007/msg00535.html
  http://psg.com/lists/rrg/2007/msg00719.html

This has been part of Ivip since July (the 01 draft is the same as
July's 00):

  http://tools.ietf.org/html/draft-whittle-ivip-arch-01#section-1.8

    In this introduction, I assume each ITR handles the full range
    of IMABs (Ivip Mapped Address Blocks) in the Ivip system.

    However, to spread load over multiple ITRs in a single location,
    several could be configured so they each cover a fraction of the
    total Ivip-mapped address space.

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

    Where a single large range of contiguous addresses is for
    some scaling reason handled with separate database dumps and
    update streams, it should be divided into separate IMABs.  This
    increases the number of BGP advertised prefixes, but may be
    justifiable, for instance within a large (eg. /8) prefix of IMIP
    (Ivip-Mapped IP address) space, so that ITRs can load share by
    each handling a subset of the entire /8.

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

    Also, by splitting something big like a /8 into four or 16
    smaller IMABs, there is only a slight extra burden on the global
    BGP routing table, but the process of booting, downloading
    IMAB-DBD files, buffering a stream of US-IMAB updates, etc. can
    be done in smaller chunks, including especially smaller
    allocations of RAM inside the ITRD or QSD.  This would also
    facilitate finer control of load balancing when a single ITRD
    couldn't handle the traffic in one location, and several ITRDs
    were used there with different IMABs for each one.

As far as I know, APT has no such provision.  I think LISP's Proxy
Tunnel Routers (applicable to ALT or NERD) could be operated as just
described for Ivip - each handling a subset of the BGP prefixes
which are for EID address space.

NERD ITRs request mapping data and updates themselves.  So a NERD
ITR handling a subset of the total EID space would only request the
appropriate subset of mapping updates.

A full database Ivip ITR normally gets the full feed of mapping
updates.  There could be some facility in the mapping distribution
system (currently called the "Replicator" system) to send only
packets concerning this subset.

It would be tricky to split up the address range for which an Ivip
QSD (full database Query Server) was responsible, because that would
require the requesting devices (caching ITRs and caching query
servers) to know which range of addresses each of the multiple query
servers were responsible for.

There could be two or more linked QSDs, each receiving queries, but
each having only a subset of the mapping database - passing queries
to the a nearby QSD for the addresses they don't have the data for
themselves.  This would be possible, but there would have to be a
truly massive amount of mapping data to make it worth the trouble.

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