[RRG] Solving the routing scaling problem for internal networks too? Ivip may be able to help

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

Short version:   To what extent do currently proposed solutions for
                 the DFZ routing scaling problem help with
                 scaling problems in large internal networks?

                 Not at all, as far as I can tell.

                 I guess the scaling problems of internal networks
                 are of quite a different nature to the problems
                 faced by BGP routers in the DFZ.

                 I explore how Ivip's encapsulation and two
                 Forwarding approaches could be used to help
                 with internal routing systems, in addition to
                 or independently of their use in the DFZ.

                 The Forwarding approaches have no overhead -
                 which is a significant problem for IPv6 map-encap,
                 especially for VoIP packets.  They are 100%
                 efficient and involve no PMTUD problems.


In "Re: 2 billion IP cellphones in 2103 & mass adoption of IPv6 by
current IPv4 users" http://psg.com/lists/rrg/2008/msg02594.html
Wesley George wrote about the scaling problem in internal networks,
wondering whether the solution we are seeking for the DFZ scaling
problem will help with this.

Referring initially to the scaling problem in the IPv6 DFZ
developing later than the scaling problem of internal networks of 3G
cellphone operators, he wrote:

> Admittedly the problem may be further off in the DFZ. However, I
> don't know why we would design something that only applies to the
> DFZ, since the route scale problem has potential to be much worse
> within a given network than outside it. 

I wonder how many ISP and end-user networks have more internal
routes than the DFZ's 260k?

I understand that internal routing systems use OSPF or IS-IS, which
operate on completely different principles to BGP, which is entirely
decentralised.

The scaling properties of these internal systems are presumably very
different from BGP.  I think it is true to say that BGP suits the
interdomain core better than OSPF or IS-IS, because BGP can work
fine in a system with no central coordination, even when the size of
the network is not known, while the other two assume a centrally
administrated and carefully managed network?

I understand that in terms of the forwarding (FIB) part of the
router, every extra route is another load on the system like any
other.  I understand that the FIB doesn't distinguish between routes
which come from BGP and those from the IGP (OSPF or IS-IS).  Despite
the heroics necessary to classify and forward packets at 1 and 10
GBps for millions of prefixes, I understand this is not the primary
problem with the routing scaling problem.

The RIB control plane scaling problems affecting any one BGP router
include:

  1 - Amount of RAM and CPU power required to handle a given number
      of prefixes.  This scales directly with number of prefixes
      multiplied by the number of neighbour routers, since the
      router needs to conduct a separate conversation with each
      neighbour about each prefix.

  2 - Traffic requirements for the routing protocol.  I figure this
      is a relatively minor concern.

  3 - Difficulties with the CPU and RAM coping with large floods of
      changed routes, such as when one nearby or distant link or
      router goes down, or comes up, affecting hundreds of thousands
      of prefixes.

  4 - Point 3 manifests in the router as excessive delays in
      adjusting its best path to the changed conditions.

As the number of prefixes rises, and as the rate of updates rise, in
order to keep to certain standards of correct and rapid operation,
each router needs to be upgraded at great expense, either  with more
RAM or perhaps with a complete replacement.  Alternatively, any
given router may need to be restricted to operating with fewer
neighbours than it would be if the number of prefixes had not grown
so much.

So these points add up to a major financial burden for any network
operating DFZ routers.

Also, the scaling problems for the whole BGP network include:

  5 - Slower propagation of updates - slower response to outages
      and therefore more packets going to black holes during a
      major change to the topology of the network.

  6 - Greater concern about the stability and robustness of the
      whole network, considering that no-one really understands it.
      No-one even knows for sure the structure of the network or
      how many DFZ and single-homed BGP routers there are.
      How is the overall behavior affected by some routers passing
      on changes much slower then others?  It is hard to estimate,
      but in general it can't be good.


I understand that some networks have millions of internal routes.  I
assume this is sustainable - so OSPF or IS-IS presumably scales
somewhat better than BGP.  Part of this ability to handle larger
numbers of prefixes is probably due to the internal routing system
being more controlled than the DFZ.  In the DFZ, there is no control
or influence on the rate of updates arriving from neighbouring
networks.  Other than crude filtering to the point of ignoring some
of them, and potentially upsetting connectivity to some parts of the
Net, a DFZ router needs to respond to them all.

In these very large internal networks, what are all these routes
for?  Is it all internal stuff for the ISP/carrier?  Does it carry a
large number of routes for PA customer networks?   This is probably
too big a question to answer in the RRG.  Can anyone point me to
resources concerning this?

I am not convinced that the internal network's scaling problems are
identical or even close to those of the DFZ.  Even if they were
identical, I would argue that they are not so much of a concern to
us as the DFZ:

Firstly, it is a conscious decision by administrators to make a
network so big that it has a million or more internal routes.
No-one is forcing them to do this, or is saying it is a good idea.

Only a small proportion of ISP and end-user networks have such
numbers of internal routes, and it is probably a fairly low priority
for the IETF's to reduce the costs of such large organisations.

Secondly, since these internal networks are fully managed by the
organisation, including presumably the ability to reduce the updates
sent by any one router, the scaling problems and stability
difficulties can be controlled in this way, rather than by changing
protocols or spending more money on routers.


Since any substantial ISP must deploy routers in the DFZ, the costs
of doing so, and the instability and long convergence time problems
resulting from the growing size of the DFZ routing table are major
barriers to any ISP operating.  Therefore, the DFZ scaling problem
has a pervasive impact on the cost and quality of all Internet
communications.  The same goes for any end-user network which wants
or needs portability and multihoming.  This is a very high priority
for the IETF.


Even if we accept that the scaling problems of internal networks are
very different from those of BGP in the DFZ and even if we decide it
is not our concern if internal routing systems have scaling
problems, we might still want to consider how our proposed routing
scaling solution would help or otherwise with the internal routing
scaling problem.  We need to convince ISPs and both large and small
to invest in  changes to routing and addressing, this looks like an
important question:

> What incentive do I have
> as an operator to deploy some fantastic new thing for the DFZ if
> I still have to have routers that cost millions to deal with my
> internal network routing table?

In the APT business model, as described in a recent message from
Michael Meisel:

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

The decision to adopt APT is taken by the ISP, for the ISP's own
immediate and lasting benefit: improved efficiency in some way.  (I
don't know how this is achieved, and I don't understand how an ISP
could do this without checking with the end-user network whose space
is being converted to an APT EID and so will be withdrawn sooner or
later from the DFZ.)

In the Ivip model:

  Re: Comparing APT & Ivip - new business models
  http://psg.com/lists/rrg/2008/msg02593.html

ISPs are not necessarily the primary driving force behind Ivip
adoption.  They will be the most direct beneficiary of Ivip's effect
of reducing or eliminating the routing scaling problem - and their
lower costs will be passed onto all Internet users.

However, on a network-by-network basis, the impetus for adopting
Ivip-managed SPI address space, or for converting an existing PI
prefix to SPI space, will mainly come from the end-user networks
whose space this is.  Existing PI end-user networks would seek
either better flexibility (many more micronets, including down to
single IPv4 addresses, with potentially fast and frequent mapping
changes to implement real-time load sharing) by converting their
prefix to SPI space.  Alternatively, by relinquishing their PI space
and BGP expertise, and renting a probably smaller, and therefore
probably cheaper, amount of SPI space from a MAB operating company,
they would achieve improved flexibility and reduced costs.

End user networks with PA space will be motivated to adopt Ivip by
the desire for portable, multihomeable, space - making them
independent of any one particular ISP.  Their current ISP is
unlikely to push them to adopt Ivip, except in the hope of keeping
them as current customers, rather than them doing on their own, or
at the urging of a competing ISP.

The direct benefit of Ivip to ISPs comes slowly, as the DFZ routing
table either drops in size, or at least doesn't grow as fast as it
otherwise would have.  ISPs may in general want every end-user
network to adopt Ivip, for this reason.  However, any PA end-user
customer of theirs which adopts Ivip will be less tied to this ISP
than before, because they can now multihome their new SPI space with
another ISP, or leave the current ISP entirely.

So ISPs might in the short term be unmotivated to deploy Ivip
themselves, except as required to meet the needs of their customers
who want to use it.  An ISP's interests might be served well by
letting all other ISPs and end-user networks adopt Ivip, while
itself doing nothing and keeping its current PA customers.  However,
competition ensures that such a complacent approach would lead to
loss of customers.


> Assuming that always-on IP-enabled applications continue taking
> off, I have ~55M handsets to address. Accepting in the short term
> (5 yrs or so) there will be some significant amount of IPv4-only
> devices, as those age out, the IPv6 table continues to grow in my
> network. The DFZ may not have to see much of that except in some
> mobility cases (depends on implementation), but you can't argue
> with the idea that even with well-built address hierarchies, some
> routers in the network are going to have to deal with orders of
> magnitude more routes than they do today. What better place to
> test out a new scalable routing infrastructure than in a
> controllable network before it has to be implemented by the DFZ
> across multiple networks?

The RRG's charter is purely to deal with the scaling problem in the DFZ.

As currently presented, the core-edge separation schemes: LISP, APT,
Ivip, TRRP and Six/One Router are all intended to relieve pressure
on the DFZ core by enabling end-user networks to have a new kind of
PI space, which I call Scalable PI space, without each SPI prefix
appearing in the DFZ.

In a recent message:

  Re: Comparing APT & Ivip
  http://psg.com/lists/rrg/2008/msg02589.html

Michael Meisel wrote of APT:

   Below, you describe your doubts about how a single ISP could
   deploy APT unilaterally, without the involvement of their
   customers. Allowing for this, and giving ISPs an incentive to do
   so, is perhaps *the* primary goal of our incremental deployment
   scheme. As I mentioned before, we should have a new document
   describing the updated details sometime in the next few months.
   But, to summarize, you can think of a single ISP deploying APT
   as similar (in concept) to a single ISP deploying MPLS, or
   some other internal efficiency improvement. The difference is,
   APT allows for a potential increase in benefits with every other
   ISP that deploys it.

As I wrote in that thread, I don't understand how APT could be
deployed by an ISP without coordinating with the end-user network.
However, Michael indicates that APT could improve efficiency within
the ISP network.  If so, then perhaps it helps in some way with the
scaling problem of the internal network, perhaps in terms of the
number of BGP routes its internal BGP system carries.


Ivip, as currently described, does not aim to help with the scaling
problems of large internal networks.  Here I will explore how Ivip
might be used to do this.

While Ivip began as a map-encap scheme - like LISP, APT and TRRP -
the long term goal for Ivip is to use Forwarding, instead of
encapsulation:

   ETR Address Forwarding (EAF) - for IPv4
   http://tools.ietf.org/html/draft-whittle-ivip4-etr-addr-forw-01

   Prefix Label Forwarding (PLF) - for IPv6
   http://www.firstpr.com.au/ip/ivip/ivip6/

These both have two major advantages - no encapsulation overhead and
no need for greater ITR and ETR complexity with extra protocols and
probing etc. to solve the Path MTU Discovery (PMTUD) problems
inherent in map-encap:

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

These two Forwarding schemes operate in different ways.  Both make
use of currently un-used, or little-used, bits in the existing IPv4
and IPv6 header.  They both require upgraded FIB functions in DFZ
routers, and to some extent in internal routers.  The PLF approach
for IPv6 also requires a small change to the RIB.  Neither involves
new routing protocols or any change to the BGP (or internal routing
protocol) implementation.

Perhaps it will be easiest to implement these changes in routers and
then deploy Ivip purely on a forwarding basis.  Otherwise, we need
to devise and introduce the more complex map-encap approach - and
upgrade progressively to Forwarding in the longer-term future.

Here is how Ivip might be used to help with the scaling problems of
internal networks.

Firstly, considering IPv4 and IPv6 done purely with encapsulation:
This requires no changes to DFZ or internal routers, so can be
deployed by adding ITRs, ETRs and a mapping system.

I will consider the potential for helping with the scaling problems
of both large ISPs / telco-mobile carriers and big end-user
organisations, such as large universities, governments and
corporations.  I will refer to these as Big networks.

In the standard Ivip arrangement, the Big network has multiple full
database query servers (QSDs).  These all receive a full, real-time,
flow of mapping updates from the global fast-push mapping system:

  http://tools.ietf.org/html/draft-whittle-ivip-db-fast-push

ITRs in the Big network send queries to these QSDs and get mapping
replies very quickly and reliably (like APT's ITRs and Default
Mappers, and much faster and more reliably than with LISP-ALT's or
TRRP's global distribution of potentially millions of query servers.

ETRs can be located on any conventionally BGP managed address - not
on SPI address.  This means for a Big end-user network to have its
own internal ETRs, it must have some part of its network running
with either its own conventional PI address space, or perhaps with
some PA space it gets from one or more ISPs.  For instance, a
multihomed-user network could have ETRs in its network, on two
separate pieces of address space, one from each of its two upstream
ISPs.

ITRs can be on any public address - conventional BGP managed or SPI.
 They can't ordinarily be behind NAT, since they need to be able to
receive mapping updates from a nearby QSD for some prefix they
recently requested mapping for.

Here is how such a Big network could use Ivip to reduce the number
of prefixes in its internal routing table.  The Big network would
establish its own internal mapping system, to generate mapping for
internal micronets, and to map them to any of its internal ETRs.
Actually, each internal micronet could be mapped to any ETR in the
world - its just that the system would only catch packets sent to
these micronets from within this Big network, or from within any
other network which also used this second set of internal mapping
information to drive its QSDs and ITRs.

The QSDs would all be sent this internal mapping information in
addition to the global feed, as sent to all QSDs everywhere.

Caching ITRs (and any full database ITRs, which are effectively a
caching ITRs coupled directly to a QSD) would then be able to
encapsulate packets sent within the internal routing system and
tunnel them to whatever ETR was specified in the mapping.

With an internal fast-push mapping system - without the need for
multiple RUASes or the Launch server system - this mapping could
probably be pushed to all internal QSDs in a fraction of a second.
I don't know how responsive OSPF or IS-IS is in large networks, but
perhaps this internal Ivip mapping system would be more responsive
than these internal routing systems.  ITR behaviour could probably
be changed in less than a second.

Assuming that most routers remain as they are now, and that ITRs are
either hardware based routers (Cisco and Juniper style) or specially
programmed COTS hosts, then there needs to be a way to attract raw
packets to these ITRs when their destination address matches the
prefix of an Internal MAB (Mapped Address Block) of Big network
Ivip-managed space.  (I probably need another term for this other
than SPI space.)

 So we need the concept of an IMAB in addition to the global MABs
which the global Ivip system manages.  These ITRs would be an
internal equivalent of the Open ITRs in the DFZ (OITRDs) - maybe
call them Open Internal ITRs (OIITRs) or Open ITRs in the Internal
network (OITRIs).  These are all tongue-twisters . . .

For internal purposes only, ITRs and ETRs could probably be on
private addresses too.  Likewise, private address space could be
managed by this internal Ivip system.

In this way, the internal routing system can handle a much smaller
number of prefixes, since most of the prefixes the internal routing
system currently handles could be done with the internal mapping
system and internal ITRs and ETRs.

The destination ETR for an internal micronet doesn't have to be an
internal ETR.  It could be any ETR in the world.  Maybe this could
help link the network to other networks.  This is getting complex,
but these are optional complexities and this should be expected in
any flexible, useful, TCP/IP routing and addressing scheme.

The PMTUD problems inherent in map-encap may be significantly
reduced in this internal application of Ivip, because the network
administrators may be able to ensure that all devices between the
ITRs and the ETR have MTUs of 9000 bytes or so.  That doesn't
necessarily solve PMTU problems for an application which thinks it
can send packets of this length, when those packets are encapsulated
and become longer than 9000 bytes - and the encapsulation makes a
mess of a Packet Too Big message which is created by a router in the
ITR -> ETR path.  However, there may be ways in an internal network
for handling this which are simpler than those required in
interdomain routing.  For instance, every ITR could reject a packet
of length > (9000 minus encapsulation overhead), if it can be
assured that the MTU to the ETR which is known to be in the Big
network is exactly 9000.  Upgrading everything to Gigabit Ethernet
and 9000 byte MTU would be quite a task, but over a few years as
part of the upgrade to an internal Ivip system, the whole network
could be significantly streamlined.


Now consider Ivip operating with ETR Address Forwarding (EAF) for
IPv4.  The internal routing system would need to have most or all
its routers upgraded to forward packets according to the 30
available bits in the IPv4 header when the header is in the new
format, signified by the "Evil bit" being set to 1.

Maybe some smaller, older, routers near the periphery of the network
are not upgraded in this way.  So within the network there is a
"Forwarding Upgraded Zone for IPv4" (FUZv4) where Forwarding based
ITRs and ETRs can operate freely, without any PMTUD problems.  This
means they have 1500 or 9000 byte or whatever PMTUs and handle
traffic packets of these lengths, with no encapsulation overhead.
PMTUD would operate normally with these routers, including when
these routers are between the ITR and the ETR - the sending host's
application adjusts the packet length to suit the total PMTU between
it and the destination host.

ITRs can have their packets forwarded to any ETR, and the ETRs must
be located on addresses such as x.x.x.0, x.x.x.4, x.x.x.8 etc. due
to the use of only 30 bits for a forwarding address, rather than the
ideal of 32 bits.

This would probably work really well.  There is no change to the RIB
of the internal routers.  They still work with OSPF or IS-IS and
their RIB contains the same information.  Its just that instead of
forwarding the packet based on its destination address, the new kind
of packet (with the Evil Bit set to 1) is forwarded according to the
30 bits in the header which were previously used for fragmentation
offset and checksum.

There are some restrictions on sending fragmentable packets which
are longer than some limit - see:

http://tools.ietf.org/html/draft-whittle-ivip4-etr-addr-forw-01#section-5

Since the internal network could have different PMTU characteristics
than those assumed when setting the global MinCoreMTU value for the
whole of the Ivip system, perhaps internal micronets could be less
restricted in terms of fragmentable packets.  However, overall, I
think it is best to discourage the use of fragmentable packets.


The IPv6 Forwarding approach operates on different principles from
the IPv4 approach.  With ETR Address Forwarding (EAF) for IPv4 there
are 30 bits available - enough to uniquely identify every ETR.

With  Prefix Label Forwarding (PLF) for IPv6, there are only 20 bits
available.  The current plan is to use have half of these codepoints
(524,287) used in the global IPv6 Ivip system to identify the BGP
prefix by which the ETR can be reached.  On arrival at the border
router which advertises that prefix, a second operation is required
if there is more than one ETR in that prefix.  The mapping needs to
be looked up again, for the destination address of the packet, and
the result of the mapping lookup (the ETR's exact address) may
result in the packet being sent to the ETR by one of several methods:

1 - Forwarded over a direct link to the ETR.

2 - Encapsulated to the ETR (but this raises the PMTUD problems
    again, which Forwarding otherwise avoids).

3 - A similar approach to Forwarding across the DFZ, based on the 20
    bits in the  header, but this time using the other 524,287 code
    points, which internal routers in the ISP network map to
    prefixes handled by the internal routing system.

This is more complex than the IPv4 approach, but it is the best we
can do with IPv6's horrendously long 128 bit addresses for ETRs,
when we have only 20 bits to play with.   While remaining compatible
with the existing IPv6 header size, this looks like the only way of
avoiding encapsulation and its PMTUD problems.

How could this system be used to help with the scaling of internal
networks?

As with the IPv4 approach, the network would have its own internal
mapping system and its QSDs (and therefore its ITRs) would work from
this mapping information as well as from the global mapping feed.

The above system provides 524,287 micronets which could replace
existing internal prefixes, and be mapped to any internal ETR.

Perhaps these internal micronets could be remapped with lower costs
and higher speeds than are possible with these being prefixes in the
internal routing system.  If so, this would be benefit in addition
to removing this number of prefixes from the internal routing system
- though they do need to be covered by some much smaller number of
Internal Mapped Address Blocks.


If internal routing systems are currently coping with more than a
million internal routes, and this is somehow not regarded as causing
a serious scaling problem, then it looks like this IPv6 approach to
forwarding in Ivip is not going to make such a difference, since it
could at best reduce the load by half a million prefixes.   But if
these prefixes were frequently changing, and this was a serious
burden for the current internal routing system, perhaps it would be
a worthwhile approach.

As with the IPv4 approach, all paths between ITRs and ETRs need to
have routers upgraded to handle the new header format.  With a Big
network, this gives rise to a Forwarding Upgraded Zone (FUZv6) - the
part or parts of the network where all routers handle the new
Forwarding format of the IPv6 header.  These upgrades are more
complex than the upgrade for IPv4 forwarding.  Still, I guess they
might be done with a software update for existing routers.  The IPv6
approach to Forwarding require some further management compared to
the more direct IPv4 approach.

For the 524,287 interdomain code-points in Prefix Label Forwarding
(PLF) for IPv6, I propose that there be a direct, globally assumed,
mapping between each of these code-points and a particular "Core
Egress Prefix" all of which are in a contiguous block.  For
instance, they would match:

  CEP-0       E000:0000::/32
  CEP-1       E000:0001::/32
  CEP-2       E000:0002::/32
  . . .
  CEP-524287  E007:FFFF::/32


For the internal 524,287 code-points, it is up to the network
administrators which code-point matches which prefix.  So all the
routers would need to be configured in the same way.  There could be
 some range of codepoints assigned to one set of contiguous prefixes
in one part of the IPv6 address space, and other ranges of
code-points assigned to other parts.


So both the encapsulation and the two Forwarding approaches to Ivip
could be used to help internal networks scale.

These techniques do not absolutely depend on the development of a
global Ivip system.  One or more big ISPs or end-user network
operators could, in principle, talk to their router vendor(s) and
ask them to develop ITR, ETR and mapping systems to work just within
their networks.  The Forwarding approaches would require software
updates to existing routers, but the ITR and ETR functions would be
simpler than for map-encap due to the lack of PMTUD problems.
Router vendors would tend to implement new features in their
existing devices, but it would also be possible to implement ITR,
ETR and mapping distribution functions in software for ordinary COTS
hosts.

I suspect that the scaling problems of internal routing systems are
not yet so pressing as to prompt a development like this, but at
least there is some prospect for synergies between using these
techniques internally as well as for their original purpose - to
help solve the interdomain routing scaling problem.

  - 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