Subject: Re: [RRG] Solving the routing scaling problem for internal networks too? Ivi...

From: [email-masked]
Date: Tue, 30 Sep 2008 04:59:47 EDT

Robin,
Be assured that TARA can be done such that each single next hop, no matter  
whether intra- or inter-domain, is a matter of just one single table  lookup.  
75600 table entries are sufficient to cope with a density where  two routers 
are away from each other by a half yard ( IMO 72 000 should be  sufficient too).
I have never heard a convincing argument why intra- and inter-domain   
routing have to be such orthogonal as is the case today. 
TARA's routing table could be derived from viewing a topology where each  
router is immediately surrounded by a strict network followed by loose and  
looser networks according to the geographical remoteness,
PLUS (!!!) an extension of the strict network which is the entire  
intra-domain network without geographical limitations.
 
I would be grateful if you could provide an estimation how much faster a  
packet may be forwarded via an average (intra-and inter-domain) path by means of  
a single table-offset rather than a binary search across a classical FIB at 
each  router.
 
Heiner

In einer eMail vom 30.09.2008 09:47:15 Westeuropäische Normalzeit schreibt  
[email-masked]:

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