[RRG] Ivip6: number of "Flow Label" bits required

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

Short version:   The Ivip6 (formerly FLOWv6) proposal won't
                 need the full 2^20 range of bits in the IPv6
                 Flow Label.  Each possible value is for a
                 BGP-advertised prefix for forwarding packets to
                 when they are addressed to the new kind of
                 end-user network.

                 Each such prefix can be advertised by one or more
                 provider border routers, so there can be plenty
                 of load sharing for each such prefix.  There is
                 no limit to the number of end-user networks each
                 such prefix could support.

                 There only needs to be one such prefix for every
                 relatively isolated provider "site" - and I think
                 half a million is more than enough for however
                 many such sites will ever exist.

                 I initially designed this proposal assuming there
                 would be an ETR-like function.  Now I suspect
                 that for many networks, there may be no ETR - just
                 a BGP border router after which the packet is
                 routed in the provider's internal routing system
                 according to its destination address, rather than
                 using the Routing Label which took it across the
                 core.

                 However, I don't think it will always be practical
                 to have every router in the provider's network
                 know about every address range of each end-user
                 network, so I will explore using the Routing Label
                 again, within a separate namespace for each
                 provider network, in a different range of values to
                 that of the one global namespace used in the core,
                 to get the packet from the border router to some
                 other router, like a very minimal ETR, which
                 forwards the packet to the end-user network.


Hi Brian,

Here is a detailed response to something you wrote.  You can see the
design developing as I write it.

In a recent message:

  Re: RFC3697 [Re: [RRG] FLOWv6: IPv6 Flow Label to control DFZ
  forwarding]
  http://psg.com/lists/rrg/2008/msg02055.html

you wrote of my "FLOWv6" proposal, now known as "Ivip6":

> However, I don't think 20 bits is enough for what Robin has in
> mind.  Effectively it only allows for 2^20 RLOCs and that is only
> 4 times today's DFZ if I have the arithmetic right.

Perhaps my use of up to 20 bits of the Flow Label (which would be
renamed to "Routing Label") is different from your understanding.

I think you are seeing a 1:1 relationship between each of the 2^20
values and an ETR.  (The following discussion assumes there will be
ETRs, but later I decide there need not be ETRs at all!)

I will be retaining familiar map-encap terminology when I rewrite
this proposal soon, so we can stick with the ITR and ETR terms,
rather than the IFR and EFR terms I created for my FLOWv6 email a
few days ago.

Let's assume we use the full 20 bits for this Ivip6 purpose - I will
later propose we use less, probably 19.

The purpose is to give the core routers a way of delivering the
packet to the correct provider network where the ETR is located -
without:

   a - Adding to the packet length, or

   b - Changing the source or destination address, or

   c - Doing anything to the packet which would upset IPsec.

This only gets the packet as far as the border router of the
provider network which advertises this prefix - or to one of the
border routers which advertise it.

Each such provider network can have an effectively unlimited number
of ETRs.  Each such provider network, and each such prefix, can
support an unlimited number of end-user networks.

I will make this clearer when I rewrite the proposal at:

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

For now, referring to the example in my initial description:

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

this "Routing Label" use of the current "Flow Label" only works with
a specific set of advertised prefixes, which form a regular set in
the address space.  Each one is an Egress Block Prefix (EBP).

In the example, there are 2^20 of them in E00::/12.  Consequently,
the first few EBPs are:

       EBP-0  E000:0000::/32
       EBP-1  E000:0001::/32
       EBP-2  E000:0002::/32

and the highest is:

 EBP-1048575  E00F:FFFF::/32

The idea is that providers have these EBP prefixes, and they are
assigned with some care and restriction so they only go to providers
according to need.  A provider with a single network in a single
city would only need one.

Providers with multiple such "sites" would probably want one EPB per
site.  Exactly how this would play out remains to be determined, but
the idea is that if a provider has, for instance, a bunch of ETRs in
Phoenix and another bunch in Denver (really, a bunch of end-user
networks connecting in Phoenix and another bunch in Denver), and if
its networks in these cities are relatively isolated and advertise
different prefixes, then they would get an EPB for their sites in
each city.

There probably needs to be some ongoing fee for this, since each
such prefix burdens all core routers.

Each such site may have one or more border routers advertising each
EPB prefix.

BGP works as usual with these prefixes.  For all currently
advertised EBP prefixes, the RIB will have (or will be able to
easily create) a list of FEC values, one for each prefix in the
complete range:

         EBP-0  E000:0000::/32
to
   EBP-1048575  E00F:FFFF::/32

The FEC value tells the FIB which interface the packet should be
forwarded on, or whether it should be dropped or processed in some
other way.  The FEC value is in principle about as many bits as is
required to specify one of the output interfaces, but I understand
it is more likely to be 16 or 32 bits or so, specifying a bunch of
options, including choosing between multiple output queues in each
interface.  Let's assume it is a 32 bit integer.

These FEC values are copied to an array in the FIB, which I called
FINDEX[] but will rename to something like RLFEC[].


In this example, I assume the ITR is a border router and that inside
the network, the value of the Routing Label (the 20 bits currently
known as "Flow Label" will either be zero, or are ignored.

That is 4 Megabytes, but I will show later that it probably doesn't
need to be this big - and in principle, each entry really just needs
to indicate which of the output interfaces the packet must be sent
on, so it could be 16 or probably 8 bits or less.


In the example, an ITR (IRF in the original description) looks up
the mapping for a packet and finds it should be tunneled to an ETR
(EFR in the original description) at:

  E000:0003:0000:0055::7

All ETRs are in the E00::/12  prefix.

   (Hmmm . . . so this means each mapping entry doesn't need to
    specify the "E00" bits in positions 127 to 116.)

The ITR ignores all bits in this result apart from the 20 bits 115
to 96 inclusive . . .

   (Better still . . . this means ETRs only need to get 20 bits of
    mapping information, not the full 128 bit ETR address.

    This *greatly reduces* the volume of mapping information the
    mapping distribution system needs to send to the ITRs and the
    full database query servers.  It would be even less than with
    IPv4.)

These bits, in this example, are hex:

   0 0003

The ITR simply copies this into the packet's 20 bit Routing Label,
and then treats it as all (upgraded) core routers do:

  If the Routing Label is non-zero, use it as an index into the
  RLFEC[] array. This returns the FEC, which tells the router which
  of its interfaces on which to forward the packet.

The same process occurs in all (upgraded) core routers.  We would
need a way to ensure most BGP routers are upgraded to do this, and a
way to keep these packets with non-zero Routing Labels from being
sent to core routers which did not handle them in this way.

This process causes the packet to arrive at the border router (or
one of multiple border routers) of the provider which advertised:

  EBP-2  E000:0002::/32

We don't use EPB-0, since that corresponds to a Routing Label value
of zero - which means the packet should not get this special
forwarding treatment by core routers.

This border router has a special role to play.  In the original
description I called it the "FPER" router.  I will create a new name
for this, probably RLPER (Routing Label Path Exit Router).

Perhaps the RLPER router *is* the ETR.  Then the packet's
destination address and this router's knowledge of the end-user
networks which use its ETR functions tells it all it need to know to
forward the packet correctly.

If the RLPER router is not the ETR itself then it needs to forward
the packet to the correct ETR which handles the end-user network
specified in the packet's destination address.

This can't be determined from the Routing Label.

In this case, the RLPER needs to do a mapping lookup, using the full
destination address.  That gives it the full ETR address, and then
it can somehow forward the packet to that ETR.  In practice, this
lookup will not involve delays since the RLPER will already have the
required information anyway. (Even with a lookup to a remote query
server, and in Ivip, all mapping lookups are to local query servers,
so there is insignificant delay.)

The RLPER will have this information already cached, since it is
constantly handling packets addressed to the various end-user
networks in its own site, and this provider has a business
relationship with all of those end-user networks.  So strictly
speaking, the global mapping distribution system doesn't need to
provide anything more than the 20 bit Routing Label value, since
this RLPER can get all the information it needs about which ETR to
use from the local network.

There can be effectively any number of ETRs and it is a private
matter within the provider network how the RLPER forwards each
packet to each ETR.  Ivip6 doesn't necessarily have to specify how
this is done, since it does not involve the core.

However, perhaps there is a role for using the Routing Label again,
with a meaning specific to this provider network, to enable an
efficient method of forwarding the packet inside the provider
network, to the ETR - ideally without encapsulating it, adding to
its length, altering the addresses etc.

But let's reconsider the role of the "ETR".

In Ivip6, the ETR has virtually nothing to do.  There is no
encapsulating header to strip off, and no addresses to rewrite.

It is not involved in reachability testing from the ITRs.  The ITRs
never communicate with it for any other purpose, such as the thorny
business of PMTUD which is required with map-encap.

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

So why do we need an ETR?

Maybe we don't.


The provider network could have one or more RLPER routers - however
many advertise the E000:0002::/32 prefix.

The packet's Routing Label, having been set by the ITR, has now done
its job of delivering the packet across the core to the correct
provider network.

If we assume three things, then this RLPER router has nothing to do:

  1 - We assume that the internal routing system of the provider's
      network is capable of correctly forwarding the packet, based
      on its destination address.

  2 - We assume that these routers take no notice of the Routing
      Label - its role so far in this explanation is purely in
      the core, and when leaving an border router for some other
      core router.

If so, then in a sense, your initial observation was correct:

> Effectively it only allows for 2^20 RLOCs

Yes, but if the above assumptions are true, this really means:

  2^20 provider prefixes for delivering packets to the new kind
  of end-user networks.

Each such prefix can be handled by any number of border routers
(RLPERs) - and that is just fine.  This enables incoming traffic to
be distributed across multiple RLPERs, according to their various
links to the rest of the Net.

There is no ETR function - the packet just continues on its way in
the provider's network and is naturally forwarded there to the
end-user network.

So there is no RLPER function either - it is just a term for the
border router beyond which the packet is forwarded in the provider's
internal network according to its destination address, after
travelling across the core based purely on the value of its Routing
Label.

As to whether 2^20 is sufficient into the long-term future, this
depends on several things, including:

  How many ISPs there will ever be.

  To what degree their networks are split into multiple sites
  with such expensive communication between each one, such that each
  one needs to advertise a separate EBP prefix.


My sense is that 2^20 is more then enough for the long-term future.

Let's say there are 10 billion people, split into cities of 1
million each: 10k cities.  Let's say the average ISP serves a
million customers, but has branches in 5 cities.  So each ISP has 5
sites and we need 50k EBP prefixes.

The reality is likely to be a far lower figure.

In another message I will explore using the 20 bit Routing Label in
two ways.  One range (say 0xxx xxxx xxxx xxxx xxxx) being for
private use inside networks, and the other (1xxx xxxx xxxx xxxx
xxxx) for the core functions I am proposing for Ivip6.

The example above about the provider network knowing how to forward
all packets addressed to any of the new kind of end-user network it
connect to the Net is somewhat contrived.

For very large provider networks, I think this would be oppressive.

So I will consider the use of some some fairly trivial ETR-like
function in the provider network, without all the routers in the
whole provider network knowing anything about the exact address
ranges used by the various end-user networks, and using the Routing
Label again, with a namespace specific to this provider network, to
forward packets efficiently from the one or more border routers
(RLPERs) which receive these packets from the core, to whichever
"ETR" forwards the packets to the particular end-user network.

  - Robin


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