Subject: [RRG] Short explanation: Ivip6's "Core Routing Label Forwarding"

From: Robin Whittle <[email-masked]>
Date: Mon, 04 Aug 2008 22:17:06 +1000

Hi Iljitsch,

Thanks for making it to the 50kB mark!  Regarding your complaint and
critique:

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

The explanation was long because I figure not everyone knows the
Ivip approach to ITRs, Mapped Address Blocks etc.  These are
important - for instance that Ivip ITRs are simple, tunneling
packets to only one ETR, doing no ETR reachability testing etc.

If I was writing just for you, message would have been a third the
length.  I could explain this to you face-to-face in 2 or 3 minutes.

I am working on a better explanation, to appear here ASAP:

  http://www.firstpr.com.au/ip/ivip/ivip6/

Using terminology which is in accordance with that new explanation,
 here is a brief response to:

> your solution is basically a subset/optimization of MPLS.

Ivip6's "Core Routing Label Forwarding" (or "Core Routing Label
Tunneling"?) technique is unrelated to MPLS:

   There is no additional header.

   The label has the same value for the whole journey.

   There is no state to be set up in the routers.

   There is no predefined path.

   There is no QoS.

"Core Routing Label Forwarding" could be used for other purposes,
but an Ivip6 ITR uses this technique without any pre-arrangement, to
get the otherwise unmodified traffic packet safely across the core
to the border router of a provider network in which an ETR function
delivers the packet to the destination network.

This is achieved without the ETR address being in the packet at all
- only the 20 bits which directly identifies the prefix of the
destination provider network.

> Earlier, requiring MPLS was categorized as a non-starter. Not sure
> if I agree with that, MPLS implementations are widely available
> and running MPLS without too much overhead in the form of
> signaling protocols seems like a fair tradeoff to gain routing
> scalability to me.

There is no overhead or signalling protocol with this technique.

Let's assume we use all 20 bits of the old Flow Label as a Routing
Label (which is what I will refer to as below), to have significance
only in core routers.

   (We don't need a million label values, so I am developing the
    proposal to use half of these for this Ivip6 "ITR --> ETR via
    the core" purpose - with the other half reserved for private
    use however people like in their own networks).

All of the new kind of end-user networks connect to the Net via
providers whose sites have a "Core Egress Prefix" (CEP).  For
example, these are 2^20 contiguous /32 prefixes in E00::/12:

         CEP-0 E000:0000::/32  (Not used)
         CEP-1 E000:0001::/32
         CEP-2 E000:0002::/32

 and the highest is:

   CEP-1048575 E00F:FFFF::/32

Micronets are the more flexibly defined Ivip to a LISP EID prefix.
They are in units of /64 and can be any number (to 2^32) of /64s in
length. (Mapping granularity = /64.)

All the "end user networks" I discuss here are of the new kind,
using Ivip6-managed micronet address space.

The "recipient provider network" is the network which contains the
ETR function (tunnel endpoint) for the packet being forwarded from
an ITR to an end-user network.

In this example, the sending host emits a packet addressed to a host
in a particular micronet, and the mapping of that micronet is to
some 128 bit "ETR" address, in this example:

   E000:0003:0000:0055::7

This packet reaches an ITR, which for simplicity of explanation is a
border network of some provider network A.  It looks up the mapping
- or already has it cached.  (Ivip lookups are to local query
servers, so this the delay is insignificant.)

In Ivip4, the mapping system provides the full 32 bit address of the
ETR.  In Ivip6, it only provides 20 bits of the full address of the
"ETR".  In this example, the mapping is to:

  0 0003    (bits 115 to 96 of the "ETR" address)

The ITR writes these 20 bits into the Routing Label and then
performs the following operation on it, which is the same as is
performed by all core routers, up to the border router of the
recipient provider network.

This operation involves the first upgrade to BGP core routers, in
this case to the FIB.  There are no changes to the BGP
implementation or to the way these routers communicate with BGP peers.

   The core router's FIB receives the packet and because it has a
   non-zero Routing Label, it takes no notice of the destination
   address.

   Instead, it takes the 20 bit value of the Routing Label as an
   index to read a value in an array RLFEC[].  This has 2^20
   elements, each already set to the Forwarding Equivalence Class
   for the same-numbered CEP prefix.

   In our example, the Routing Label is 0 0003, and RLFEC[3]
   contains some number which tells the FIB which of the router's
   interfaces the packet should be forwarded on.

   The router forwards the packet to that interface.

Note there is non rewriting the value of the Routing Label, no state
previously established for this packet or any other such packet.
This is much less expensive then the FIB's usual approach of having
the Tree-Bitmap algorithm chew through the destination address, for
up to 48 bits, until it matches it to a prefix for which it knows
the FEC.

These CEP prefixes are ordinary BGP prefixes - with one exception:
it is verboten to advertise more specifics within them. They must be
advertised as /32s.

Every micronet must be mapped to an address which fits within one of
the currently advertised CEP prefixes.  We won't need a million of
them, but for now this example assumes there could be 2^20 of them.
 CEP-0 is not used.

The BGP implementation of all core routers does as usual for these
prefixes - it figures out the best path for forwarding packets
addressed to this prefix, and writing the appropriate FEC value into
the relevant part of its FIB.

The second modification to core routers does the following:

   The RIB periodically reads through the FEC values of these
   2^20 CEP prefixes and copies them sequentially to the RLFEC[]
   array in the FIB.

That's it.

Any questions?

Q1: What happens when the packet arrives at the border router of the
    recipient provider network?

Good question.

But first let's marvel at the fact that it was transported across
 the core, with minimal router effort, no protocol to set up a path
etc. to a border router which advertises a prefix which is unrelated
to the packet's destination address, except by the fact that the
packet's destination micronet is currently mapped to an ETR address
inside this prefix.

A1: If there are multiple ETRs in the recipient provider network,
    the recipient border router needs to look up the mapping of the
    destination address.  The result is the ETR address within that
    recipient provider network.  (Alert readers will have a Q2 at
    this point.)

    Alternatively, there may be no need for an ETR at all.  Let's
    say the recipient provider network's internal routing system has
    a route for the destination end-user's network, which this
    packet is addressed to.  Then the border router simply zeroes
    the Routing Label and forwards the packet according to that
    internal route.

Let us also note:

  There is no header overhead.

  No MTU problems due to longer packets.

  Traceroute works fine for the whole path.

  PMTUD works fine for the whole path.

  Core router workload is decreased.

Q2: How does the receiving provider network's border router look up
    the full "ETR" address in the mapping system, when the mapping
    system only provides bits 115 to 96 of that address to the
    full database Query Servers, due to this being all that the ITR
    needs to know about the "ETR" address?

A2: Good question!  In some cases, such as when the provider network
    has a business relationship with the end-user network, that
    relationship provides the information about which end-user
    networks have which pieces of micronet space, and which "ETR"
    the packets should be forwarded to in order that the ETR
    can forward the packet to the end-user network.

    However, in other cases, such as the TTR mobility model, there
    is no such relationship and the border router needs to use
    the mapping system to find out the full "ETR" address.  I am
    still working on this.

Q3: What about support for packets from non-upgraded networks?

A3: OITRDs (Open ITRs in the DFZ) advertise MABs (Mapped Address
    Blocks) in the DFZ, attracting packets sent to micronet
    addresses by hosts in networks without ITRs.  All micronets and
    therefore MABs are (in this example) in the prefix 4::/3, which
    simplifies the operation of OITRDs.

I can anticipate enough questions to write plenty more - but out of
respect for buffers, will sign off now.

  - Robin

--
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 Aug 2008 23:57:07 +1000

Hi Iljitsch,

Please abandon the thread with the old "FLOWv6" name.

In "Re: [RRG] FLOWv6: IPv6 Flow Label to control DFZ forwarding" you
wrote:

>> My proposal is not related to MPLS.  I will reply to your
>> critique soon in the "Ivip6 (previously FLOWv6), Ivip4 and Ivip"
>> thread.
>
> Well, MPLS is also based on encoding routing decisions in a 20-bit
> field to avoid a full lookup...

This is a coincidence.

> I'm not talking about the details, obviously.

I think you should be if you chide people on the RRG list about what
they write.

We are attempting to do something really challenging and important
here - devise a new architecture for the Internet, in three ways at
once: for IPv4, for IPv6 and potentially for a whole new clean slate
approach.

If we ignore important details or expect everything significant to
fit in a few pages or on the back of a drink coaster, then we won't
produce the excellent results which are needed.

> The way I see it, the main issue is the mapping system. If we can
> figure that part out, I'm not too worried about the encapsulation
> stuff because a good modular mapping system should of course work
> with a variety of encapsulation systems.

But this problem is complex enough that the optimal design will
surely involve certain characteristics of the mapping system fitting
particularly well with however the ITRs send packets to the ETRs.

For instance, Ivip's simple ITR functionality - requiring end-users
to supply the multihoming service restoration stuff - means the
mapping data is simpler, since there is only one ETR address to specify.

The map-encap systems have important distinctions between them - and
encapsulation sucks for a number of reasons, not least of which is
the PMTUD problems which require a complex solution:

  http://www.firstpr.com.au/ip/ivip/pmtud-frag/

Also, the encapsulation overhead sucks even worse for IPv6 than for
IPv4.  For LISP it is a 40 byte IPv6 header, a 12 byte UDP header
and an 8 byte LISP header.

If you think it doesn't really matter about IPv4 vs. IPv6 and that
the solution should work just the same for both of them, then I
don't think you have looked at my Ivip6 proposal properly, or really
considered the trouble ITRs and ETRs have to go to in order to
handle PMTUD with map-encap.

Ivip6's approach has no PMTUD problems, no encapsulation overhead,
no disruption of Traceroute - and no problem with IPsec etc.

> So we could use LISP as the default

Sure, but IMHO LISP has all sorts of failings compared to Ivip, as I
note in the comparison page and the partial list of critiques of LISP:

  http://www.firstpr.com.au/ip/ivip/comp/
  http://www.firstpr.com.au/ip/ivip/lisp-links/#critiques

> and then define additional ways to do this with MPLS and maybe
> even with light path stuff.

MPLS requires extensive set-up.  There's no time or resources for
that.  The ITR gets a packet it needs to send to an ETR it has never
heard of.  There is no time for sending a packet to the ETR, for
testing the PMTU to the ETR etc.

This is a very tight situation and MPLS or anything elaborate won't
scale at all.

Like a few other folks on this list you seem at times to be happy to
talk at length about high-level architectural concepts while
avoiding important low-level details.  Yet you were the only person
who took a real interest in Fred Templin's or my work on solving the
PMTUD problems inherent in map-encap.

Some folks here seem happy to discuss proposals such as ILMP -
whilst taking little apparent interest in proposals which have a
real chance of being implemented.

All the map-encap proposals, in principle, could be adopted -
because they do not require host changes.

ILMP, GSE etc. may be mathematically or in architecturally
attractive - but they will *never* be adopted, because they require
everyone change their applications.

That will never happen.

The Internet is not that broken that everyone that the fix must
involve everyone changing to a new set of applications, or have all
the current ones rewritten.

There are fixes for the routing scaling problem, for IPv4 and for
IPv6.  I am confident Ivip4 and Ivip6 will do the trick.  Perhaps
better solutions will be developed.  Other people think their
map-encap systems are better than Ivip4 - and they think it is
easier and better to upgrade a subset of routers than to change
hosts, applications etc.

(Ivip6 does require modest changes to all core routers.  I think
that is easier than coping with the packet overheads and PMTUD
problems of map-encap for IPv6.)

> (Electronics is sooo last century...)

I have a vision of you elevating yourself further and further away
from this Earth!  Kicking away from Mortal Detail . . . Seeking
Enlightenment and the Ultimate Scalable Routing Solution in a
mystical Vision which can only come from On High!

>From far enough up in the sky, one map-encap system probably looks
pretty much like any other map-encap system.

There is good cause to forget about low-level details for a while to
break old patterns of thought - and maybe find a new solution.

However, much of the RRG discussion recently has been directed away
from actual solutions which have a chance of being widely adopted,
in favour of half-developed proposals which definitely will not be
adopted in any realistic version of the foreseeable future.

A complex problem like this required detailed thinking, including
especially about electronics:

  TCAM sucks - way to low density and high power consumption.

  48 bits of IPv6 addresses being significant to each core
  router really sucks, because it takes far too much CPU power
  and DRAM accesses to chew through each packet's destination
  address - just to figure out which interface to forward it on.

  Part of the cost of our Internet access is ISPs spending more
  and more on purchasing, maintaining powering and cooling routers.
  For instance the FIB board on a CRS-1 (CRS-MSC) costs USD$80,000
  and dissipates 375 watts.

    http://www.firstpr.com.au/ip/sram-ip-forwarding/router-fib/

  The original sales material for this device didn't guarantee
  it could handle IPv6 packets at full rate.  I don't know if
  it can do that now, but I think it would have trouble chewing
  through 40Gbps of short incoming IPv6 packets addressed to a
  variety of the /48 prefixes now being assigned for PI end-user
  networks.

  The problems of electronics are the primary cause of the routing
  scaling problem.  If electronics wasn't a problem, we would
  just throw more of it at BGP routers and crank the clock speed
  to 50GHz.

We need to think of some gutsy, practical solution which is as
elegant as we can make it, and which will really really work - AND
which will be attractive to most people who run end-user networks.

That won't happen by taking a birds-eye view of the whole scene and
avoiding messy details such as PMTUD, packet bloating encapsulation
overheads, or overly complex ITRs and ETRs trying to do their own
multihoming service testing and restoration decisions.

I am surprised that all the other schemes assume you can't push
mapping data quickly around the world.  It is not that much data
that we should be so scared of doing this.  To assume this is
impossible is to doom the solution to monolithically integrating
multihoming fault detection and service restoration decision-making
into the scalable routing solution itself.  That should never
happen.  So far, only Ivip proposes to make that separate, so the
routing scaling solution becomes a modular part of multihoming and
TE, not a ponderous, limited, boxed up, slow solution which can't be
extended without upgrading every ITR and ETR.

> The part that worries me about reusing the flow label is that the
> flow label is defined to be non-mutable-in-transit.

Sure, but no-one uses it.

RFCs are not written in stone - they are composed entirely of
electrons which have already been recycled many times.

RFC 3697 can be withdrawn when we define a much better use for these
bits, as a Routing Label to be used under carefully defined
conditions.

It is no fault of RFC 3697 that the Flow Label is not used.  RFC
3697 does a great job of defining the semantics of the Flow Label.

> So it would be ok for the source host to use the flow label in
> this way, but not for routers to change it.

No-one seems to have bothered to actually use the IPv6 flow label in
the 14 or so years it has been available for experimentation and
practical use.

The other morning, these 20 bits intimated to me clearly that they
are bored witless being set to 0000 0000 0000 0000 0000 year after
year.

They are keen to be set to Meaningful Values and so to do something
Useful!

> Also, we would still need some bits to allow for different
> flows towards the same destinations to be treated differently as
> per the original flow label semantics.

The Flow Label is only of value if at three conditions are met:

  1 - The sending host sets it according to some pretty complex
      rules which are spelt out in RFC 3697.  These involve
      coordination with the OS to make sure the same number is
      not used by different apps, and that no number is reused
      for another flow within 120 seconds.

         Do you know if popular operating systems have an API
         for requesting a value for the Flow Label, or for
         setting it when sending packets?

  2 - The deployment of routers - let's assume BGP routers in the
      core of the Internet - which can use flows intelligently
      to spread the traffic over multiple paths, without separating
      flows.  This is a huge project, and so far hardly anyone seems
      to be motivated to research it seriously - yet IPv6 is
      crawling with researchers.  (It seems to be used primarily
      for research.)

  3 - The Flow Label is only used to distinguish between two or more
      flows from one single source IP address to another single IP
      address.  If either are different, the Flow Label is ignored.

A reasonably easy approach to ensuring that any routers doing
flow-aware multipath sharing of resources (point 2, if it ever
happens) can do their work correctly, without relying on the Flow
Label is this:

  Either the source or the destination host (or both) can use two
  or more separate IP addresses for their end of the communication,
  for each flow.

This is only necessary when two or more flows really are being sent
to another host.

That might require some OS coordination of applications, and of
course it would require each host have multiple IP addresses.  This
wouldn't be practical for IPv4, but there is plenty of space in
every IPv6 /64, to each host can think of 128 random or numbers - or
128 sequential numbers from a random starting point - and try to
make them IP addresses.  It will usually succeed.

So the workaround for for flow separation between two hosts without
the use of a Flow Label is for one or the other or both hosts to use
a different IP address.

> BTW, why is it Ivip and not ivip or IVIP?

Because the Internet deserves its capital I, to distinguish Ivip
from iPod, iPhone etc. etc. and to encourage pronunciation of
Eye-vip, as in "ivy", not as in "skivvy". A full explanation is:

  http://tools.ietf.org/html/draft-whittle-ivip-arch-01#appendix-B

and will disappear from future revisions.

  - Robin