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

From: Robin Whittle <[email-masked]>
Date: Sun, 03 Aug 2008 16:01:31 +1000

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 [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: Brian E Carpenter <[email-masked]>
Date: Sun, 03 Aug 2008 18:22:39 +1200

>                  when they are addressed to the new kind of

OK, explained like that, it seems coherent with Pouzin's
proposal in 1974 that the catenet address format should be

<Format> <PSN name> <Local name>

where you propose to put the <PSN name> in the current flow label
field. Pouzin's full explanation read:
"There is no need to interpret the destination address any more than
required to find an appropriate gateway in the correct direction.
Putting gateway names in addresses is unacceptable, as it would
tie up addressing and network topology. Thus, only PSN [packet
switched network] names should be used as catenet [internet]
addresses. Delivering a message to a final destination is carried
out only by the final PSN."

[Pouzin74] Pouzin, L., Interconnection of packet switching networks,
7th Hawaii International Conference on System Sciences, Supplement,
pp. 108-109, 1974.

     Brian

---

From: Robin Whittle <[email-masked]>
Date: Sun, 03 Aug 2008 20:15:13 +1000

Hi Brian,

This is very cool.  I understand you are sitting in an airport
lounge in Japan, drawing from experience which goes waaay back:

> field. 

Yes.

> Pouzin's full explanation read:
>

That's right.  I couldn't find the paper on the Net, so I guess you
have it on your laptop - maybe as part of your teaching materials.
Searching for the text turns up your message:

  http://psg.com/lists/rrg/2008/msg01384.html  2008-05-29

in which you wrote:

> Now, I fear he was right, but that's not what got implemented.
>
> We got a model based on fixed length addresses without a format
> prefix. I didn't see in the IPng discussion and don't see now how
> we can jettison that.

I think we can use use the 20 bits of "Flow Label" in the IPv6 for a
different purpose.  As you wrote in an earlier message, this would
be completely contrary to the intention that they not be used as a
"routing handle".	

This would be an adjunct to the current system, for the particular
purpose of getting packets from an ITR across the core to the
provider network where the destination network is located.  However,
if the system is successful, this would include the great majority
of traffic in the core.

This proposal uses the existing BGP network, with somewhat modified
routers, while doing less work in the FIB, and delivering the packet
to the the single border router for that prefix, or to one of the
several border routers which advertise it.

You also wrote:

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

> Pouzin's catenet paper from 1974 clearly shows hosts
> multihomed to two different networks. He even had virtualized
> multihomed hosts in there. That paper is hard to find without
> going to a copyright library.

It looks like there is a copy here at Monash Uni Library.

Perhaps a similar paper is:

   Pouzin, L., "A Proposal for Interconnecting Packet Switching
   Networks," Proceedings of EUROCOMP, Brunel University, May 1974,
   pp. 1023-36.

I am looking for a term for using this Routing Label approach to
forwarding a packet across the core, since it is not a map-encap
"tunnel" and nor is it using "translation".  Maybe I can work Louis
Pouzin's name into the terminology.

  - Robin

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 05 Aug 2008 12:15:01 +1200

>    Networks," Proceedings of EUROCOMP, Brunel University, May 1974,

I suspect those are basically the same paper, but when I went looking,
I could only find the Hawaii version, via the British Library iirc.
I'm not supposed to post it, for copyright reasons.

   Brian