[RRG] Comparing BGP with map-encap schemes

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

The previous message went out with with lines of unlimited length 
due to "Format Flowed" being on - sorry about this.   To turn it off 
in Thunderbird:  http://www.firstpr.com.au/web-mail/Mozilla-mail/#FF



Short version: The functions and communication needs of the various
               map-encap schemes vary enormously from each other and
               from those of the BGP system.  So it is not very
               helpful to try to compare their efficiency directly
               with BGP's efficiency.


There has been discussion of whether the techniques used by a
map-encap (ITR-ETR) scheme such as LISP-ALT are more efficient than
using BGP to convey a similar amount of information across the Net.

BGP couldn't be used for LISP's purposes unless it was required that
all ITRs and ETRs be BGP routers, or be connected very closely to
them - which I think would be an unreasonable restriction.

Even if BGP could be used, I think the comparison is not very
helpful, because the map-encap scheme is doing something very
different from the BGP system.  So the information which needs to be
transacted is of a very different nature and quantity.

The BGP system provides connectivity between ISPs and PI end-user
networks.  It does a good job of this, and the idea is that this
will continue, while the map-encap scheme provides a new type of
address space (a subset of current addresses) which is suitable for
multi-homed end-user networks - without directly involving the BGP
system.

The BGP network needs to send a flurry of information some distance
- perhaps close or perhaps a long way away - every time a router is
connected or disconnected, typically when one link goes up or down,
and always when a prefix is advertised or withdrawn.  Some BGP
messages are vital to connectivity.  However, the effect of most of
them is simply to enable better (or occasionally worse) paths for
packets than what would have occurred without the message.

Some features of the BGP system are:

1 - There are huge peaks in message volume whenever a link/router
    up/down event affects a large number of prefixes.

2 - The routers' CPUs have a very complex job handling incoming
    BGP messages, deciding how best to forward packets addressed
    to each of 250k+ prefixes and producing outgoing messages.  They
    also have to hold the outgoing queue of messages to each peer
    according to the rate the peer can accept them.  They apply
    complex local policy while doing all this.

3 - The convergence to the final optimal (or as optimal as BGP
    can achieve) state often involves a large number of messages as
    various routers adjust themselves to different forwarding
    arrangements based on the messages received from peers.  The
    whole BGP system works via the effect of information rippling
    from one router to the next, where each router makes decisions
    about the information and so potentially transforms it, or does
    not pass it on.

3 - The load on routers and the convergence time tends to get worse
    with the growth in advertised prefixes - which is why we are
    here.


There are 3 types of map-encap scheme:

  SP-C  Slow Push, Complex ITR with TE.

     APT
     LISP-NERD


  GQ-C  Global Query network, Complex ITR with TE.

     LISP-CONS
     LISP-ALT
     TRRP


  FP-S  Fast Push, Simple ITR with no specific TE functions.
        Also supports a powerful new approach to mobility.

     Ivip


The mapping data of SP-C and GQ-C schemes is basically the same.
For each micronet (a prefix which has all the same mapping
information, and serves one end-user network, though each such
network might have multiple micronets), there is:

   Description of the micronet by prefix and prefix length -
   micronets in these schemes are on binary boundaries.

   The addresses of at least one but typically two or more (for
   multihoming) ETRs.

   Some kind of priority information, regarding TE and/or
   selecting one ETR ahead of the other when the ITR finds two or
   more are reachable.

This data changes only slowly.  It may remain the same for months or
years.  The rate of change is relatively low compared to that of
Ivip's, but the mapping data is more complex and lengthy.

The SP-C and GQ-C schemes require the ITRs to decide which ETR to
use, based on the likely arduous and error-prone task of determining
reachability to multiple ETRs.  This involves a large body of work
for ITRs and ETRs, with consequent traffic.

CONS and ALT remove the need for pushing the global mapping database
to ITRs and storing it in each one, but they involve the ITR being
unable to tunnel traffic packets until a query and a response have
traversed a global query network.

In LISP-ALT, this could easily involve a path longer than halfway
round the world, since the structure of routers is determined by the
aim of aggregating IP addresses, resulting in one router being in
location X and the next level router for the request to be sent to
being in some other location Y, which is on Earth somewhere, but not
necessarily close to X.  (Since IP addresses are scattered
geographically all round the planet, aggregation by address means
inter-router links can't be optimised according to their physical
location.)

Consequently, the ALT query system will be slow and traffic packets
addressed to EID prefixes the ITR has no cached mapping information
for will will need to be dropped or sent to the ETR via the ALT
system itself - which would be slow, burdensome and not necessarily
reliable.


Ivip's mapping information consists of:

  Description of the micronet by starting address and length.

  A single ETR address.

The ITRs do not need to make any decisions or test reachability to
ETRs, so ETRs can be very simple.  (For the purposes of this
discussion I am ignoring PMTUD and fragmentation problems.  Ivip
will involve extra ITR and ETR complexity to deal with these.  The
other schemes are currently not committed to solving these problems.)

Ivip mapping data changes more frequently than that of the other
schemes.  This is because Ivip is not directly involved in sensing
reachability or in restoring multi-homed connectivity.  Ivip
requires the end user to have their own multihoming monitoring
system - which automatically (or perhaps manually) changes the
mapping to whatever the user desires.

While Ivip does not specifically provide TE, the end-user can
achieve load spreading to a resolution of one IP address, by having
micronets of any size, down to one IP address, and mapping them to
different ETRs.  (If one IP address carries too much traffic for
load spreading to be achieved this way, it would be necessary for
the user to use multiple DNS names etc. to spread their traffic over
a handful of IP addresses to achieve the granularity of traffic
volume they require.)

To achieve multihoming, Ivip's mapping data is changed only when an
ETR actually becomes unreachable.  This is far less frequent than
the average rate of messages in BGP concerning the advertised prefix
within which this ETR is located.

So it is not as if Ivip involves a global distribution of a BGP-like
level of messages for each micronet.

There could be lots of BGP messages concerning the ETR's prefix, but
as long as the ETR was still reachable, there would be no need to
change the Ivip mapping in order to maintain the end-user's
connectivity.

TE would require more frequent changes to the mapping information.

When Ivip is used to provide mobility (IPv4 and IPv6, with minimal
new functionality required for the mobile host and none for the
correspondent hosts), there will be a mapping change ever time the
mobile host chooses to use a new ETR or TTR (Translating Tunnel
Router - which performs its ETR functions and may be located outside
the network it is currently connected to).

So both TE and mobility involve potentially high levels of mapping
change.  I think there needs to be some kind of charging system for
mapping changes, because these changes will be sent to hundreds of
thousands of ITRDs (full database ITRs) and QSDs (full database
Query Servers) all over the world.

Depending on how Ivip is used for TE and mobility, the flow of
mapping data is likely to be much higher than that of the other schemes.

Even if Ivip was used solely for multihoming, the rate of mapping
changes would be higher than the other schemes.

However, Ivip involves a specially designed push system which will
handle these messages with *far* greater ease than would be the case
for them being passed peer-to-peer in BGP.  (APT proposes a separate
BGP system to push mapping data to each ISP.)

Ivip doesn't require that the full mapping data be pushed to every
ITR.  Caching ITRs and ITRFs (ITR function in sending host) can use
nearby full database query servers.  Ivip is more flexible regarding
how far the mapping data needs to be pushed than LISP-NERD (all ITRs
need the full feed) or APT (every ISP needs a full feed).


The nature of the mapping data and the way it flows in all these
schemes is very different from what happens in BGP.

Push systems are in principle much cleaner, faster and easier to
predict than the only apparent alternative - the global query server
systems of LISP-CONS, LISP-ALT and TRRP.  I am convinced that
LISP-ALT would be so slow, in many cases, that significant numbers
of initial packets would be dropped, making the system unworkable.

  - 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